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
  20 _check(const list *l)
  21 {
  22         assert(l);
  23         assert( (!l->head && l->length == 0) ||
  24                 ( l->head && l->length != 0) );
  25         assert( (!l->head && !l->tail) ||
  26                 ( l->head &&  l->tail) );
  27 }
  28
  29 list *
  30 l_new(void (*elt_dtor)(void *))
  31 {
  32         list *l = malloc(sizeof *l);
  33         if (!l)
  34                 return NULL;
  35         *l = (list){.elt_dtor = elt_dtor};
  36         CHECK(l);
  37         return l;
  38 }
  39
  40 void
  41 l_free(list *l)
  42 {
  43         l_clear(l);
  44         free(l);
  45 }
  46
  47 size_t
  48 l_length(const list *l)
  49 {
  50         return l ? l->length : 0;
  51 }
  52
  53 bool
  54 l_is_empty(const list *l)
  55 {
  56         return !l || !l->head;
  57 }
  58
  59 list_item *
  60 l_first(const list *l)
  61 {
  62         return l ? l->head : NULL;
  63 }
  64
  65 list_item *
  66 l_last(const list *l)
  67 {
  68         return l ? l->tail : NULL;
  69 }
  70
  71 bool
  72 l_append(list *l, void *data)
  73 {
  74         return l_insert_after(l, l_last(l), data);
  75 }
  76
  77 bool
  78 l_prepend(list *l, void *data)
  79 {
  80         return l_insert(l, l_first(l), data);
  81 }
  82
  83 list_item *
  84 l_remove_first(list *l)
  85 {
  86         list_item *old_head = l_first(l);
  87         return l_remove(l, old_head) ? old_head : NULL;
  88 }
  89
  90 list_item *
  91 l_remove_last(list *l)
  92 {
  93         list_item *old_tail = l_last(l);
  94         return l_remove(l, old_tail) ? old_tail : NULL;
  95 }
  96
  97 bool
  98 l_remove(list *l, list_item *li)
  99 {
 100         if (!l || !li || l->length < 1)
 101                 return false;
 102         list_item *p = li->prev, *n = li->next;
 103         if (p)
 104                 p->next = n;
 105         if (n)
 106                 n->prev = p;
 107         if (li == l->head)
 108                 l->head = n;
 109         if (li == l->tail)
 110                 l->tail = p;
 111         l->length--;
 112
 113         CHECK(l);
 114         return true;
 115 }
 116
 117 bool
 118 l_insert(list *l, list_item *pos, void *data)
 119 {
 120         if (!l)
 121                 return false;
 122         if (!pos)
 123                 pos = l->head;
 124         list_item *li = malloc(sizeof *li);
 125         if (!li)
 126                 return false;
 127         *li = (list_item){
 128                 .prev = pos->prev,
 129                 .next = pos,
 130                 .data = data
 131         };
 132         if (pos->prev)
 133                 pos->prev->next = li;
 134         pos->prev = li;
 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->next,
 159                 .data = data
 160         };
 161         if (pos->next)
 162                 pos->next->prev = li;
 163         pos->next = li;
 164
 165         if (!l->tail)
 166                 l->head = l->tail = li;
 167         else if (pos == l->tail)
 168                 l->tail = li;
 169         l->length++;
 170
 171         CHECK(l);
 172         return true;
 173 }
 174
 175 bool
 176 l_clear(list *l)
 177 {
 178         if (!l)
 179                 return false;
 180         list_item *li = l_first(l);
 181         while (li)
 182         {
 183                 list_item *n = li->next;
 184                 if (l->elt_dtor)
 185                         l->elt_dtor(li->data);
 186                 free(li);
 187                 li = n;
 188         }
 189         l->head = l->tail = NULL;
 190         l->length = 0;
 191
 192         CHECK(l);
 193         return true;
 194 }