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