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         if (!l)
  44                 return;
  45         l_clear(l);
  46         free(l);
  47 }
  48
  49 size_t
  50 l_length(const list *l)
  51 {
  52         return l ? l->length : 0;
  53 }
  54
  55 bool
  56 l_is_empty(const list *l)
  57 {
  58         return !l || !l->head;
  59 }
  60
  61 list_item *
  62 l_first(const list *l)
  63 {
  64         return l ? l->head : NULL;
  65 }
  66
  67 list_item *
  68 l_last(const list *l)
  69 {
  70         return l ? l->tail : NULL;
  71 }
  72
  73 bool
  74 l_append(list *l, void *data)
  75 {
  76         if (!l)
  77                 return false;
  78         return l_insert_after(l, l->tail, data);
  79 }
  80
  81 bool
  82 l_prepend(list *l, void *data)
  83 {
  84         if (!l)
  85                 return false;
  86         return l_insert(l, l->head, data);
  87 }
  88
  89 list_item *
  90 l_remove_first(list *l)
  91 {
  92         if (!l)
  93                 return NULL;
  94         list_item *old_head = l->head;
  95         if (old_head)
  96         {
  97                 l->head = old_head->next;
  98                 old_head->next = NULL;
  99                 l->head->prev = NULL;
 100                 l->length--;
 101         }
 102         return old_head;
 103 }
 104
 105 list_item *
 106 l_remove_last(list *l)
 107 {
 108         if (!l)
 109                 return NULL;
 110         list_item *old_tail = l->tail;
 111         if (old_tail)
 112         {
 113                 l->tail = old_tail->prev;
 114                 old_tail->prev = NULL;
 115                 l->tail->next = NULL;
 116                 l->length--;
 117         }
 118         return old_tail;
 119 }
 120
 121 bool
 122 l_insert(list *l, list_item *pos, void *data)
 123 {
 124         if (!l)
 125                 return false;
 126         if (!pos)
 127                 pos = l->head;
 128         list_item *li = malloc(sizeof *li);
 129         if (!li)
 130                 return false;
 131         *li = (list_item){
 132                 .prev = pos->prev,
 133                 .next = pos,
 134                 .data = data
 135         };
 136         if (pos->prev)
 137                 pos->prev->next = li;
 138         pos->prev = li;
 139
 140         if (!l->head)
 141                 l->head = l->tail = li;
 142         else if (pos == l->head)
 143                 l->head = li;
 144         l->length++;
 145
 146         CHECK(l);
 147         return true;
 148 }
 149
 150 bool
 151 l_insert_after(list *l, list_item *pos, void *data)
 152 {
 153         if (!l)
 154                 return false;
 155         if (!pos)
 156                 pos = l->tail;
 157         list_item *li = malloc(sizeof *li);
 158         if (!li)
 159                 return false;
 160         *li = (list_item){
 161                 .prev = pos,
 162                 .next = pos->next,
 163                 .data = data
 164         };
 165         if (pos->next)
 166                 pos->next->prev = li;
 167         pos->next = li;
 168
 169         if (!l->tail)
 170                 l->head = l->tail = li;
 171         else if (pos == l->tail)
 172                 l->tail = li;
 173         l->length++;
 174
 175         CHECK(l);
 176         return true;
 177 }