Home | History | Annotate | Download | only in lib 
      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 }
    131