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