1 /* llist.c - Linked list functions
3  * Linked list structures have a next pointer as their first element.
14   free(d->arg);  in llist_free_arg()
22   free(d->data);  in llist_free_double()
26 // Call a function (such as free()) on each element of a linked list.
27 void llist_traverse(void *list, void (*using)(void *node))  in llist_traverse()  argument
29   void *old = list;  in llist_traverse()
31   while (list) {  in llist_traverse()
32     void *pop = llist_pop(&list);  in llist_traverse()
35     // End doubly linked list too.  in llist_traverse()
36     if (old == list) break;  in llist_traverse()
40 // Return the first item from the list, advancing the list (which must be called
41 // as &list)
42 void *llist_pop(void *list)  in llist_pop()  argument
44   void **llist = list, **next;  in llist_pop()
46   if (!list || !*llist) return 0;  in llist_pop()
53 // Remove first item from &list and return it
54 void *dlist_pop(void *list)  in dlist_pop()  argument
56   struct double_list **pdlist = (struct double_list **)list, *dlist = *pdlist;  in dlist_pop()
59   if (dlist->next == dlist) *pdlist = 0;  in dlist_pop()
61     if (dlist->next) dlist->next->prev = dlist->prev;  in dlist_pop()
62     if (dlist->prev) dlist->prev->next = dlist->next;  in dlist_pop()
63     *pdlist = dlist->next;  in dlist_pop()
69 // remove last item from &list and return it (stack pop)
70 void *dlist_lpop(void *list)  in dlist_lpop()  argument
72   struct double_list *dl = *(struct double_list **)list;  in dlist_lpop()
76     dl = dl->prev;  in dlist_lpop()
78     if (!dl) *(void **)list = 0;  in dlist_lpop()
84 // Append to list in-order (*list unchanged unless empty, ->prev is new node)
85 void dlist_add_nomalloc(struct double_list **list, struct double_list *new)  in dlist_add_nomalloc()  argument
87   if (*list) {  in dlist_add_nomalloc()
88     new->next = *list;  in dlist_add_nomalloc()
89     new->prev = (*list)->prev;  in dlist_add_nomalloc()
90     (*list)->prev->next = new;  in dlist_add_nomalloc()
91     (*list)->prev = new;  in dlist_add_nomalloc()
92   } else *list = new->next = new->prev = new;  in dlist_add_nomalloc()
95 // Add an entry to the end of a doubly linked list
96 struct double_list *dlist_add(struct double_list **list, char *data)  in dlist_add()  argument
100   new->data = data;  in dlist_add()
101   dlist_add_nomalloc(list, new);  in dlist_add()
106 // Terminate circular list for traversal in either direction. Returns end *.
107 void *dlist_terminate(void *list)  in dlist_terminate()  argument
109   struct double_list *end = list;  in dlist_terminate()
111   if (!end || !end->prev) return 0;  in dlist_terminate()
113   end = end->prev;  in dlist_terminate()
114   end->next->prev = 0;  in dlist_terminate()
115   end->next = 0;  in dlist_terminate()