wsutil/wmem/wmem_list.c

   1 /* wmem_list.c
   2  * Wireshark Memory Manager Doubly-Linked List
   3  * Copyright 2012, Evan Huus <eapache@gmail.com>
   4  *
   5  * Wireshark - Network traffic analyzer
   6  * By Gerald Combs <gerald@wireshark.org>
   7  * Copyright 1998 Gerald Combs
   8  *
   9  * SPDX-License-Identifier: GPL-2.0-or-later
  10  */
  11
  12 #include <string.h>
  13 #include <glib.h>
  14
  15 #include "wmem_core.h"
  16 #include "wmem_list.h"
  17
  18 struct _wmem_list_frame_t {
  19     struct _wmem_list_frame_t *next, *prev;
  20     void *data;
  21 };
  22
  23 struct _wmem_list_t {
  24     unsigned count;
  25     wmem_list_frame_t  *head, *tail;
  26     wmem_allocator_t   *allocator;
  27 };
  28
  29 unsigned
  30 wmem_list_count(const wmem_list_t *list)
  31 {
  32     return list->count;
  33 }
  34
  35 wmem_list_frame_t *
  36 wmem_list_head(const wmem_list_t *list)
  37 {
  38     return list->head;
  39 }
  40
  41 wmem_list_frame_t *
  42 wmem_list_tail(const wmem_list_t *list)
  43 {
  44     return list->tail;
  45 }
  46
  47 wmem_list_frame_t *
  48 wmem_list_frame_next(const wmem_list_frame_t *frame)
  49 {
  50     return frame->next;
  51 }
  52
  53 wmem_list_frame_t *
  54 wmem_list_frame_prev(const wmem_list_frame_t *frame)
  55 {
  56     return frame->prev;
  57 }
  58
  59 void *
  60 wmem_list_frame_data(const wmem_list_frame_t *frame)
  61 {
  62     return frame->data;
  63 }
  64
  65 void
  66 wmem_list_remove(wmem_list_t *list, void *data)
  67 {
  68     wmem_list_frame_t *frame;
  69
  70     frame = list->head;
  71
  72     while (frame && frame->data != data) {
  73         frame = frame->next;
  74     }
  75
  76     if (frame == NULL) {
  77         return;
  78     }
  79
  80     wmem_list_remove_frame(list, frame);
  81 }
  82
  83 void
  84 wmem_list_remove_frame(wmem_list_t *list, wmem_list_frame_t *frame)
  85 {
  86     if (frame->prev) {
  87         frame->prev->next = frame->next;
  88     }
  89     else {
  90         list->head = frame->next;
  91     }
  92
  93     if (frame->next) {
  94         frame->next->prev = frame->prev;
  95     }
  96     else {
  97         list->tail = frame->prev;
  98     }
  99
 100     list->count--;
 101     wmem_free(list->allocator, frame);
 102 }
 103
 104 wmem_list_frame_t *
 105 wmem_list_find(wmem_list_t *list, const void *data)
 106 {
 107     wmem_list_frame_t *cur;
 108
 109     for (cur = list->head; cur; cur = cur->next) {
 110         if(cur->data == data)
 111             return cur;
 112     }
 113
 114     return NULL;
 115 }
 116
 117 wmem_list_frame_t *
 118 wmem_list_find_custom(wmem_list_t *list, const void *data, GCompareFunc compare_func)
 119 {
 120     wmem_list_frame_t *cur;
 121
 122     for (cur = list->head; cur != NULL; cur = cur->next) {
 123         if (compare_func(cur->data, data) == 0) {
 124             return cur;
 125         }
 126     }
 127
 128     return NULL;
 129 }
 130
 131 void
 132 wmem_list_prepend(wmem_list_t *list, void *data)
 133 {
 134     wmem_list_frame_t *new_frame;
 135
 136     new_frame = wmem_new(list->allocator, wmem_list_frame_t);
 137
 138     new_frame->data = data;
 139     new_frame->next = list->head;
 140     new_frame->prev = NULL;
 141
 142     if (list->head) {
 143         list->head->prev = new_frame;
 144     }
 145     else {
 146         list->tail = new_frame;
 147     }
 148
 149     list->head = new_frame;
 150     list->count++;
 151 }
 152
 153 void
 154 wmem_list_append(wmem_list_t *list, void *data)
 155 {
 156     wmem_list_frame_t *new_frame;
 157
 158     new_frame = wmem_new(list->allocator, wmem_list_frame_t);
 159     new_frame->data = data;
 160     new_frame->next = NULL;
 161     new_frame->prev = list->tail;
 162
 163     if (list->tail) {
 164         list->tail->next = new_frame;
 165     }
 166     else {
 167         list->head = new_frame;
 168     }
 169
 170     list->tail = new_frame;
 171     list->count++;
 172 }
 173
 174 void
 175 wmem_list_insert_sorted(wmem_list_t *list, void* data, GCompareFunc func)
 176 {
 177     wmem_list_frame_t *new_frame;
 178     wmem_list_frame_t *cur;
 179     wmem_list_frame_t *prev;
 180
 181     new_frame = wmem_new(list->allocator, wmem_list_frame_t);
 182     new_frame->data = data;
 183     new_frame->next = NULL;
 184     new_frame->prev = NULL;
 185
 186     list->count++;
 187
 188     if (!list->head) {
 189         list->head = new_frame;
 190         list->tail = new_frame;
 191         return;
 192     }
 193
 194     cur = list->head;
 195
 196     if (func(cur->data, data) >= 0) {
 197         cur->prev = new_frame;
 198         new_frame->next = cur;
 199         list->head = new_frame;
 200         return;
 201     }
 202
 203     do {
 204         prev = cur;
 205         cur = cur->next;
 206     } while (cur && func(cur->data, data) <= 0);
 207
 208     if (!cur) {
 209         prev->next = new_frame;
 210         new_frame->prev = prev;
 211         list->tail = new_frame;
 212         return;
 213     }
 214
 215     new_frame->prev = prev;
 216     new_frame->next = cur;
 217     new_frame->prev->next = new_frame;
 218     new_frame->next->prev = new_frame;
 219 }
 220
 221 void
 222 wmem_list_append_sorted(wmem_list_t *list, void* data, GCompareFunc func)
 223 {
 224     wmem_list_frame_t *new_frame;
 225     wmem_list_frame_t *cur;
 226     wmem_list_frame_t *next;
 227
 228     new_frame = wmem_new(list->allocator, wmem_list_frame_t);
 229     new_frame->data = data;
 230     new_frame->next = NULL;
 231     new_frame->prev = NULL;
 232
 233     list->count++;
 234
 235     if (!list->head) {
 236         list->head = new_frame;
 237         list->tail = new_frame;
 238         return;
 239     }
 240
 241     cur = list->tail;
 242
 243     /* best case scenario: append */
 244     if (func(cur->data, data) <= 0) {
 245         cur->next = new_frame;
 246         new_frame->prev = cur;
 247         list->tail = new_frame;
 248         return;
 249     }
 250
 251     do {
 252         next = cur;
 253         cur = cur->prev;
 254     } while (cur && func(cur->data, data) >= 0);
 255
 256     /* worst case scenario: prepend */
 257     if (!cur) {
 258         next->prev = new_frame;
 259         new_frame->next = next;
 260         list->head = new_frame;
 261         return;
 262     }
 263
 264     /* ordinary case: insert */
 265     new_frame->next = next;
 266     new_frame->prev = cur;
 267     new_frame->prev->next = new_frame;
 268     new_frame->next->prev = new_frame;
 269 }
 270
 271 wmem_list_t *
 272 wmem_list_new(wmem_allocator_t *allocator)
 273 {
 274     wmem_list_t *list;
 275
 276     list =  wmem_new(allocator, wmem_list_t);
 277
 278     list->count     = 0;
 279     list->head      = NULL;
 280     list->tail      = NULL;
 281     list->allocator = allocator;
 282
 283     return list;
 284 }
 285
 286 void
 287 wmem_destroy_list(wmem_list_t *list)
 288 {
 289     wmem_list_frame_t *cur, *next;
 290
 291     if (list == NULL) {
 292         return;
 293     }
 294
 295     cur = list->head;
 296
 297     while (cur) {
 298         next = cur->next;
 299         wmem_free(list->allocator, cur);
 300         cur = next;
 301     }
 302
 303     wmem_free(list->allocator, list);
 304 }
 305
 306 void
 307 wmem_list_foreach(wmem_list_t *list, GFunc foreach_func, void * user_data)
 308 {
 309     wmem_list_frame_t *cur;
 310
 311     cur = list->head;
 312
 313     while (cur) {
 314         foreach_func(cur->data, user_data);
 315         cur = cur->next;
 316     }
 317 }
 318
 319 /*
 320  * Editor modelines  -  https://www.wireshark.org/tools/modelines.html
 321  *
 322  * Local variables:
 323  * c-basic-offset: 4
 324  * tab-width: 8
 325  * indent-tabs-mode: nil
 326  * End:
 327  *
 328  * vi: set shiftwidth=4 tabstop=8 expandtab:
 329  * :indentSize=4:tabSize=8:noTabs=true:
 330  */