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