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 void **llist = list, **next;
45
46 if (!list || !*llist) return 0;
47 next = (void **)*llist;
48 *llist = *next;
49
50 return next;
51 }
52
53 // Remove first item from &list and return it
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) return 0;
59 if (dlist->next == dlist) *pdlist = 0;
60 else {
61 if (dlist->next) dlist->next->prev = dlist->prev;
62 if (dlist->prev) dlist->prev->next = dlist->next;
63 *pdlist = dlist->next;
64 }
65
66 return dlist;
67 }
68
69 // remove last item from &list and return it (stack pop)
dlist_lpop(void * list)70 void *dlist_lpop(void *list)
71 {
72 struct double_list *dl = *(struct double_list **)list;
73 void *v = 0;
74
75 if (dl) {
76 dl = dl->prev;
77 v = dlist_pop(&dl);
78 if (!dl) *(void **)list = 0;
79 }
80
81 return v;
82 }
83
84 // Append to list in-order (*list unchanged unless empty, ->prev is new node)
dlist_add_nomalloc(struct double_list ** list,struct double_list * new)85 void dlist_add_nomalloc(struct double_list **list, struct double_list *new)
86 {
87 if (*list) {
88 new->next = *list;
89 new->prev = (*list)->prev;
90 (*list)->prev->next = new;
91 (*list)->prev = new;
92 } else *list = new->next = new->prev = new;
93 }
94
95 // Add an entry to the end of a doubly linked list
dlist_add(struct double_list ** list,char * data)96 struct double_list *dlist_add(struct double_list **list, char *data)
97 {
98 struct double_list *new = xmalloc(sizeof(struct double_list));
99
100 new->data = data;
101 dlist_add_nomalloc(list, new);
102
103 return new;
104 }
105
106 // Terminate circular list for traversal in either direction. Returns end *.
dlist_terminate(void * list)107 void *dlist_terminate(void *list)
108 {
109 struct double_list *end = list;
110
111 if (!end || !end->prev) return 0;
112
113 end = end->prev;
114 end->next->prev = 0;
115 end->next = 0;
116
117 return end;
118 }
119