lists.c

   1
   2 #include <stdlib.h>
   3
   4 #include "lists.h"
   5 #include "alloc.h"
   6 #include "utils.h"
   7
   8 struct _element {
   9   struct _listpool *const pool;
  10
  11   struct _list *lst;
  12   struct _element *next;
  13   struct _element *prev;
  14
  15   void *value;
  16 };
  17
  18 struct _list {
  19   struct _listpool *const pool;
  20   struct _element *head;
  21   struct _element *tail;
  22   int size;
  23 };
  24
  25 struct _listpool {
  26   fixedpool lstpool;
  27   fixedpool elmpool;
  28 };
  29
  30 listpool listpool_create (size_t numelms, size_t numlsts)
  31 {
  32   listpool result = (listpool) xmalloc (sizeof (struct _listpool));
  33   result->elmpool = fixedpool_create (sizeof (struct _element), numelms, 0);
  34   result->lstpool = fixedpool_create (sizeof (struct _list), numlsts, 0);
  35   return result;
  36 }
  37
  38 void listpool_destroy (listpool pool)
  39 {
  40   fixedpool_destroy (pool->lstpool, NULL, NULL);
  41   fixedpool_destroy (pool->elmpool, NULL, NULL);
  42   free (pool);
  43 }
  44
  45
  46 list list_alloc (listpool pool)
  47 {
  48   list l;
  49   listpool *ptr;
  50   l = fixedpool_alloc (pool->lstpool);
  51
  52   ptr = (listpool *) &l->pool;
  53   *ptr = pool;
  54   l->head = l->tail = NULL;
  55   l->size = 0;
  56   return l;
  57 }
  58
  59 void list_free (list l)
  60 {
  61   listpool pool;
  62   list_reset (l);
  63   pool = l->pool;
  64   fixedpool_free (pool->lstpool, l);
  65 }
  66
  67 void list_reset (list l)
  68 {
  69   element el, ne;
  70   for (el = l->head; el; el = ne) {
  71     ne = el->next;
  72     element_free (el);
  73   }
  74   l->head = l->tail = NULL;
  75   l->size = 0;
  76 }
  77
  78 int list_size (list l)
  79 {
  80   return l->size;
  81 }
  82
  83 element list_head (list l)
  84 {
  85   return l->head;
  86 }
  87
  88 void *list_headvalue (list l)
  89 {
  90   if (list_head (l))
  91     return element_getvalue (list_head (l));
  92   return NULL;
  93 }
  94
  95 element list_tail (list l)
  96 {
  97   return l->tail;
  98 }
  99
 100 void *list_tailvalue (list l)
 101 {
 102   if (list_tail (l))
 103     return element_getvalue (list_tail (l));
 104   return NULL;
 105 }
 106
 107 element list_inserthead (list l, void *val)
 108 {
 109   element el = element_alloc (l->pool, val);
 110   if (l->size == 0) {
 111     el->lst = l;
 112     l->size++;
 113     l->head = l->tail = el;
 114   } else {
 115     element_insertbefore (l->head, el);
 116   }
 117   return el;
 118 }
 119
 120 element list_inserttail (list l, void *val)
 121 {
 122   element el = element_alloc (l->pool, val);
 123   if (l->size == 0) {
 124     el->lst = l;
 125     l->size++;
 126     l->head = l->tail = el;
 127   } else {
 128     element_insertafter (l->tail, el);
 129   }
 130   return el;
 131 }
 132
 133 void *list_removehead (list l)
 134 {
 135   element el;
 136   el = list_head (l);
 137   if (!el) return NULL;
 138   return element_free (el);
 139 }
 140
 141 void *list_removetail (list l)
 142 {
 143   element el;
 144   el = list_tail (l);
 145   if (!el) return NULL;
 146   return element_free (el);
 147 }
 148
 149
 150
 151 element element_alloc (listpool pool, void *val)
 152 {
 153   element el;
 154   listpool *ptr;
 155   el = fixedpool_alloc (pool->elmpool);
 156
 157   ptr = (listpool *) &el->pool;
 158   *ptr = pool;
 159   el->prev = NULL;
 160   el->next = NULL;
 161   el->value = val;
 162   el->lst = NULL;
 163
 164   return el;
 165 }
 166
 167 void element_remove (element el)
 168 {
 169   list l = el->lst;
 170   if (l) l->size--;
 171
 172   if (!el->next) {
 173     if (l) l->tail = el->prev;
 174   } else {
 175     el->next->prev = el->prev;
 176   }
 177
 178   if (!el->prev) {
 179     if (l) l->head = el->next;
 180   } else {
 181     el->prev->next = el->next;
 182   }
 183   el->next = el->prev = NULL;
 184   el->lst = NULL;
 185 }
 186
 187 void *element_free (element el)
 188 {
 189   listpool pool;
 190   void *val;
 191   val = element_getvalue (el);
 192   pool = el->pool;
 193   element_remove (el);
 194   fixedpool_free (pool->elmpool, el);
 195   return val;
 196 }
 197
 198 void *element_getvalue (element el)
 199 {
 200   return el->value;
 201 }
 202
 203 void element_setvalue (element el, void *val)
 204 {
 205   el->value = val;
 206 }
 207
 208 element element_next (element el)
 209 {
 210   return el->next;
 211 }
 212
 213 element element_previous (element el)
 214 {
 215   return el->prev;
 216 }
 217
 218
 219 void element_insertbefore (element el, element inserted)
 220 {
 221   inserted->lst = el->lst;
 222   inserted->prev = el->prev;
 223   inserted->next = el;
 224   if (el->prev) el->prev->next = inserted;
 225   el->prev = inserted;
 226
 227   if (inserted->lst) {
 228     inserted->lst->size++;
 229     if (!inserted->prev) inserted->lst->head = inserted;
 230   }
 231 }
 232
 233 void element_insertafter (element el, element inserted)
 234 {
 235   inserted->lst = el->lst;
 236   inserted->next = el->next;
 237   inserted->prev = el;
 238   if (el->next) el->next->prev = inserted;
 239   el->next = inserted;
 240
 241   if (inserted->lst) {
 242     inserted->lst->size++;
 243     if (!inserted->next) inserted->lst->tail = inserted;
 244   }
 245 }