begriffs open source - libderp/blob - src/list.c

   1 #include "list.h"
   2
   3 #include <assert.h>
   4 #include <stdlib.h>
   5
   6 #ifdef NDEBUG
   7         #define CHECK(x) (void)(x)
   8 #else
   9         #define CHECK(x) _check(x)
  10 #endif
  11
  12 struct list
  13 {
  14         list_item *head, *tail;
  15         dtor *elt_dtor;
  16         void *dtor_aux;
  17         size_t length;
  18 };
  19
  20 static void        _check(const list *l);
  21 static list_item * _merge(list_item *, list_item *,
  22                           comparator *, void *);
  23 static list_item * _bisect(list_item *);
  24 static list_item * _sort(list_item *,
  25                          comparator *, void *);
  26
  27 list *
  28 l_new(void)
  29 {
  30         list *l = malloc(sizeof *l);
  31         if (!l)
  32                 return NULL;
  33         *l = (list){0};
  34         CHECK(l);
  35         return l;
  36 }
  37
  38 void
  39 l_dtor(list *l, dtor *elt_dtor, void *dtor_aux)
  40 {
  41         if (!l)
  42                 return;
  43         l->elt_dtor = elt_dtor;
  44         l->dtor_aux = dtor_aux;
  45 }
  46
  47 void
  48 l_free(list *l)
  49 {
  50         l_clear(l);
  51         free(l);
  52 }
  53
  54 size_t
  55 l_length(const list *l)
  56 {
  57         return l ? l->length : 0;
  58 }
  59
  60 bool
  61 l_is_empty(const list *l)
  62 {
  63         return !l || !l->head;
  64 }
  65
  66 list_item *
  67 l_first(const list *l)
  68 {
  69         return l ? l->head : NULL;
  70 }
  71
  72 list_item *
  73 l_last(const list *l)
  74 {
  75         return l ? l->tail : NULL;
  76 }
  77
  78 list_item *
  79 l_find(const list *l, const void *needle,
  80        comparator *cmp, void *aux)
  81 {
  82         if (!l || !cmp)
  83                 return NULL;
  84         for (list_item *li = l_first(l); li; li = li->next)
  85                 if (cmp(li->data, needle, aux) == 0)
  86                         return li;
  87         return NULL;
  88 }
  89
  90 list_item *
  91 l_find_last(const list *l, const void *needle,
  92             comparator *cmp, void *aux)
  93 {
  94         if (!l || !cmp)
  95                 return NULL;
  96         for (list_item *li = l_last(l); li; li = li->prev)
  97                 if (cmp(li->data, needle, aux) == 0)
  98                         return li;
  99         return NULL;
 100 }
 101
 102 bool
 103 l_append(list *l, void *data)
 104 {
 105         return l_insert_after(l, l_last(l), data);
 106 }
 107
 108 bool
 109 l_prepend(list *l, void *data)
 110 {
 111         return l_insert(l, l_first(l), data);
 112 }
 113
 114 void *
 115 l_remove_first(list *l)
 116 {
 117         list_item *old_head = l_first(l);
 118         void *data = old_head ? old_head->data : NULL;
 119         l_remove(l, old_head);
 120         return data;
 121 }
 122
 123 void *
 124 l_remove_last(list *l)
 125 {
 126         list_item *old_tail = l_last(l);
 127         void *data = old_tail ? old_tail->data : NULL;
 128         l_remove(l, old_tail);
 129         return data;
 130 }
 131
 132 bool
 133 l_remove(list *l, list_item *li)
 134 {
 135         if (!l || !li || l->length < 1)
 136                 return false;
 137         list_item *p = li->prev, *n = li->next;
 138         if (p)
 139                 p->next = n;
 140         if (n)
 141                 n->prev = p;
 142         if (li == l->head)
 143                 l->head = n;
 144         if (li == l->tail)
 145                 l->tail = p;
 146         l->length--;
 147         free(li);
 148
 149         CHECK(l);
 150         return true;
 151 }
 152
 153 bool
 154 l_insert(list *l, list_item *pos, void *data)
 155 {
 156         if (!l)
 157                 return false;
 158         if (!pos)
 159                 pos = l->head;
 160         list_item *li = malloc(sizeof *li);
 161         if (!li)
 162                 return false;
 163         *li = (list_item){
 164                 .prev = pos ? pos->prev : NULL,
 165                 .next = pos,
 166                 .data = data
 167         };
 168         if (pos)
 169         {
 170                 if (pos->prev)
 171                         pos->prev->next = li;
 172                 pos->prev = li;
 173         }
 174
 175         if (!l->head)
 176                 l->head = l->tail = li;
 177         else if (pos == l->head)
 178                 l->head = li;
 179         l->length++;
 180
 181         CHECK(l);
 182         return true;
 183 }
 184
 185 bool
 186 l_insert_after(list *l, list_item *pos, void *data)
 187 {
 188         if (!l)
 189                 return false;
 190         if (!pos)
 191                 pos = l->tail;
 192         list_item *li = malloc(sizeof *li);
 193         if (!li)
 194                 return false;
 195         *li = (list_item){
 196                 .prev = pos,
 197                 .next = pos ? pos->next : NULL,
 198                 .data = data
 199         };
 200         if (pos)
 201         {
 202                 if (pos->next)
 203                         pos->next->prev = li;
 204                 pos->next = li;
 205         }
 206
 207         if (!l->tail)
 208                 l->head = l->tail = li;
 209         else if (pos == l->tail)
 210                 l->tail = li;
 211         l->length++;
 212
 213         CHECK(l);
 214         return true;
 215 }
 216
 217 bool
 218 l_clear(list *l)
 219 {
 220         if (!l)
 221                 return false;
 222         list_item *li = l_first(l);
 223         while (li)
 224         {
 225                 list_item *n = li->next;
 226                 if (l->elt_dtor)
 227                         l->elt_dtor(li->data, l->dtor_aux);
 228                 free(li);
 229                 li = n;
 230         }
 231         l->head = l->tail = NULL;
 232         l->length = 0;
 233
 234         CHECK(l);
 235         return true;
 236 }
 237
 238 bool
 239 l_sort(list *l, comparator *cmp, void *aux)
 240 {
 241         if (!l || !cmp)
 242                 return false;
 243         if (l_length(l) < 2)
 244                 return true;
 245
 246         l->head = _sort(l->head, cmp, aux);
 247         list_item *t = l->head;
 248         while (t && t->next)
 249                 t = t->next;
 250         l->tail = t;
 251         CHECK(l);
 252         return true;
 253 }
 254
 255
 256 /*** Internals ***/
 257
 258 static void
 259 _check(const list *l)
 260 {
 261         assert(l);
 262         assert( (!l->head && l->length == 0) ||
 263                 ( l->head && l->length != 0) );
 264         assert( (!l->head && !l->tail) ||
 265                 ( l->head &&  l->tail) );
 266
 267         /* for extra assurance, could test that the list
 268          * is connected front to back and back to front.
 269          *
 270          * Probably adds a good bit of overhead.
 271         list_item *li = l_first(l);
 272         while (li && li->next)
 273                 li = li->next;
 274         assert(li == l_last(l));
 275
 276         li = l_last(l);
 277         while (li && li->prev)
 278                 li = li->prev;
 279         assert(li == l_first(l));
 280         */
 281 }
 282
 283 static list_item *
 284 _merge(list_item *a, list_item *b,
 285        comparator *cmp, void *aux)
 286 {
 287         if (!a)
 288                 return b;
 289         if (!b)
 290                 return a;
 291         list_item *ret, *n;
 292         if (cmp(a->data, b->data, aux) <= 0)
 293         {
 294                 ret = a;
 295                 n = _merge(a->next, b, cmp, aux);
 296         }
 297         else
 298         {
 299                 ret = b;
 300                 n = _merge(a, b->next, cmp, aux);
 301         }
 302         ret->next = n;
 303         n->prev = ret;
 304         return ret;
 305 }
 306
 307 static list_item *
 308 _bisect(list_item *li)
 309 {
 310         assert(li);
 311         list_item *fast = li;
 312         while (fast && fast->next)
 313         {
 314                 li = li->next;
 315                 fast = fast->next->next;
 316         }
 317         if (li->prev) /* cut in twain */
 318                 li->prev = li->prev->next = NULL;
 319         return li;
 320 }
 321
 322 static list_item *
 323 _sort(list_item *l, comparator *cmp, void *aux)
 324 {
 325         assert(l);
 326         assert(cmp);
 327         if (!l->next)
 328                 return l;
 329         list_item *r = _bisect(l);
 330         l = _sort(l, cmp, aux);
 331         r = _sort(r, cmp, aux);
 332         return _merge(l, r, cmp, aux);
 333 }