lists.c

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