• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
llist_free_arg(void * node)10 void llist_free_arg(void *node)
11 {
12   struct arg_list *d = node;
13 
14   free(d->arg);
15   free(d);
16 }
17 
llist_free_double(void * node)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.
llist_traverse(void * list,void (* using)(void * node))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)
llist_pop(void * 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 
dlist_pop(void * list)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 
dlist_add_nomalloc(struct double_list ** list,struct double_list * new)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
dlist_add(struct double_list ** list,char * data)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 *.
dlist_terminate(void * list)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
get_num_cache(struct num_cache * cache,long long num)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.
add_num_cache(struct num_cache ** cache,long long num,void * data,int len)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