lib/llist.c

   1 /* llist.c - Linked list functions
   2  *
   3  * Linked list structures have a next pointer as their first element.
   4  */
   5
   6 #include "toys.h"
   7
   8 // Callback function to free data pointer of double_list or arg_list
   9
  10 void llist_free_arg(void *node)
  11 {
  12   struct arg_list *d = node;
  13
  14   free(d->arg);
  15   free(d);
  16 }
  17
  18 void llist_free_double(void *node)
  19 {
  20   struct double_list *d = node;
  21
  22   free(d->data);
  23   free(d);
  24 }
  25
  26 // Call a function (such as free()) on each element of a linked list.
  27 void llist_traverse(void *list, void (*using)(void *node))
  28 {
  29   void *old = list;
  30
  31   while (list) {
  32     void *pop = llist_pop(&list);
  33     using(pop);
  34
  35     // End doubly linked list too.
  36     if (old == list) break;
  37   }
  38 }
  39
  40 // Return the first item from the list, advancing the list (which must be called
  41 // as &list)
  42 void *llist_pop(void *list)
  43 {
  44   // I'd use a void ** for the argument, and even accept the typecast in all
  45   // callers as documentation you need the &, except the stupid compiler
  46   // would then scream about type-punned pointers.  Screw it.
  47   void **llist = (void **)list;
  48   void **next = (void **)*llist;
  49   *llist = *next;
  50
  51   return (void *)next;
  52 }
  53
  54 void *dlist_pop(void *list)
  55 {
  56   struct double_list **pdlist = (struct double_list **)list, *dlist = *pdlist;
  57
  58   if (dlist->next == dlist) *pdlist = 0;
  59   else {
  60     dlist->next->prev = dlist->prev;
  61     dlist->prev->next = *pdlist = dlist->next;
  62   }
  63
  64   return dlist;
  65 }
  66
  67 void dlist_add_nomalloc(struct double_list **list, struct double_list *new)
  68 {
  69   if (*list) {
  70     new->next = *list;
  71     new->prev = (*list)->prev;
  72     (*list)->prev->next = new;
  73     (*list)->prev = new;
  74   } else *list = new->next = new->prev = new;
  75 }
  76
  77
  78 // Add an entry to the end of a doubly linked list
  79 struct double_list *dlist_add(struct double_list **list, char *data)
  80 {
  81   struct double_list *new = xmalloc(sizeof(struct double_list));
  82
  83   new->data = data;
  84   dlist_add_nomalloc(list, new);
  85
  86   return new;
  87 }
  88
  89 // Terminate circular list for traversal in either direction. Returns end *.
  90 void *dlist_terminate(void *list)
  91 {
  92   struct double_list *end = list;
  93
  94   if (!list) return 0;
  95
  96   end = end->prev;
  97   end->next->prev = 0;
  98   end->next = 0;
  99
 100   return end;
 101 }
 102
 103 // Find num in cache
 104 struct num_cache *get_num_cache(struct num_cache *cache, long long num)
 105 {
 106   while (cache) {
 107     if (num==cache->num) return cache;
 108     cache = cache->next;
 109   }
 110
 111   return 0;
 112 }
 113
 114 // Uniquely add num+data to cache. Updates *cache, returns pointer to existing
 115 // entry if it was already there.
 116 struct num_cache *add_num_cache(struct num_cache **cache, long long num,
 117   void *data, int len)
 118 {
 119   struct num_cache *old = get_num_cache(*cache, num);
 120
 121   if (old) return old;
 122
 123   old = xzalloc(sizeof(struct num_cache)+len);
 124   old->next = *cache;
 125   old->num = num;
 126   memcpy(old->data, data, len);
 127   *cache = old;
 128
 129   return 0;
 130 }