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                           int (*)(const void*, const void*));
  22 static list_item * _bisect(list_item *);
  23 static list_item * _sort(list_item *,
  24                          int (*)(const void*, const 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 bool
  69 l_append(list *l, void *data)
  70 {
  71         return l_insert_after(l, l_last(l), data);
  72 }
  73
  74 bool
  75 l_prepend(list *l, void *data)
  76 {
  77         return l_insert(l, l_first(l), data);
  78 }
  79
  80 list_item *
  81 l_remove_first(list *l)
  82 {
  83         list_item *old_head = l_first(l);
  84         return l_remove(l, old_head) ? old_head : NULL;
  85 }
  86
  87 list_item *
  88 l_remove_last(list *l)
  89 {
  90         list_item *old_tail = l_last(l);
  91         return l_remove(l, old_tail) ? old_tail : NULL;
  92 }
  93
  94 bool
  95 l_remove(list *l, list_item *li)
  96 {
  97         if (!l || !li || l->length < 1)
  98                 return false;
  99         list_item *p = li->prev, *n = li->next;
 100         if (p)
 101                 p->next = n;
 102         if (n)
 103                 n->prev = p;
 104         if (li == l->head)
 105                 l->head = n;
 106         if (li == l->tail)
 107                 l->tail = p;
 108         l->length--;
 109
 110         CHECK(l);
 111         return true;
 112 }
 113
 114 bool
 115 l_insert(list *l, list_item *pos, void *data)
 116 {
 117         if (!l)
 118                 return false;
 119         if (!pos)
 120                 pos = l->head;
 121         list_item *li = malloc(sizeof *li);
 122         if (!li)
 123                 return false;
 124         *li = (list_item){
 125                 .prev = pos ? pos->prev : NULL,
 126                 .next = pos,
 127                 .data = data
 128         };
 129         if (pos)
 130         {
 131                 if (pos->prev)
 132                         pos->prev->next = li;
 133                 pos->prev = li;
 134         }
 135
 136         if (!l->head)
 137                 l->head = l->tail = li;
 138         else if (pos == l->head)
 139                 l->head = li;
 140         l->length++;
 141
 142         CHECK(l);
 143         return true;
 144 }
 145
 146 bool
 147 l_insert_after(list *l, list_item *pos, void *data)
 148 {
 149         if (!l)
 150                 return false;
 151         if (!pos)
 152                 pos = l->tail;
 153         list_item *li = malloc(sizeof *li);
 154         if (!li)
 155                 return false;
 156         *li = (list_item){
 157                 .prev = pos,
 158                 .next = pos ? pos->next : NULL,
 159                 .data = data
 160         };
 161         if (pos)
 162         {
 163                 if (pos->next)
 164                         pos->next->prev = li;
 165                 pos->next = li;
 166         }
 167
 168         if (!l->tail)
 169                 l->head = l->tail = li;
 170         else if (pos == l->tail)
 171                 l->tail = li;
 172         l->length++;
 173
 174         CHECK(l);
 175         return true;
 176 }
 177
 178 bool
 179 l_clear(list *l)
 180 {
 181         if (!l)
 182                 return false;
 183         list_item *li = l_first(l);
 184         while (li)
 185         {
 186                 list_item *n = li->next;
 187                 if (l->elt_dtor)
 188                         l->elt_dtor(li->data);
 189                 free(li);
 190                 li = n;
 191         }
 192         l->head = l->tail = NULL;
 193         l->length = 0;
 194
 195         CHECK(l);
 196         return true;
 197 }
 198
 199 bool
 200 l_sort(list *l, int (*cmp)(const void*, const void*))
 201 {
 202         if (!l || !cmp)
 203                 return false;
 204         if (l_length(l) < 2)
 205                 return true;
 206
 207         l->head = _sort(l->head, cmp);
 208         list_item *t = l->head;
 209         while (t && t->next)
 210                 t = t->next;
 211         l->tail = t;
 212         CHECK(l);
 213         return true;
 214 }
 215
 216
 217 /*** Internals ***/
 218
 219 static void
 220 _check(const list *l)
 221 {
 222         assert(l);
 223         assert( (!l->head && l->length == 0) ||
 224                 ( l->head && l->length != 0) );
 225         assert( (!l->head && !l->tail) ||
 226                 ( l->head &&  l->tail) );
 227
 228         list_item *li = l_first(l);
 229         while (li && li->next)
 230                 li = li->next;
 231         assert(li == l_last(l));
 232
 233         li = l_last(l);
 234         while (li && li->prev)
 235                 li = li->prev;
 236         assert(li == l_first(l));
 237 }
 238
 239 static list_item *
 240 _merge(list_item *a, list_item *b,
 241        int (*cmp)(const void*, const void*))
 242 {
 243         if (!a)
 244                 return b;
 245         if (!b)
 246                 return a;
 247         list_item *ret, *n;
 248         if (cmp(a->data, b->data) <= 0)
 249         {
 250                 ret = a;
 251                 n = _merge(a->next, b, cmp);
 252         }
 253         else
 254         {
 255                 ret = b;
 256                 n = _merge(a, b->next, cmp);
 257         }
 258         ret->next = n;
 259         n->prev = ret;
 260         return ret;
 261 }
 262
 263 static list_item *
 264 _bisect(list_item *li)
 265 {
 266         assert(li);
 267         list_item *fast = li;
 268         while (fast && fast->next)
 269         {
 270                 li = li->next;
 271                 fast = fast->next->next;
 272         }
 273         if (li->prev) /* cut in twain */
 274                 li->prev = li->prev->next = NULL;
 275         return li;
 276 }
 277
 278 static list_item *
 279 _sort(list_item *l,
 280       int (*cmp)(const void*, const void*))
 281 {
 282         assert(l);
 283         assert(cmp);
 284         if (!l->next)
 285                 return l;
 286         list_item *r = _bisect(l);
 287         l = _sort(l, cmp);
 288         r = _sort(r, cmp);
 289         return _merge(l, r, cmp);
 290 }