1 /*
2 ** Copyright (C) 2007-2020 by Carnegie Mellon University.
3 **
4 ** @OPENSOURCE_LICENSE_START@
5 ** See license information in ../../LICENSE.txt
6 ** @OPENSOURCE_LICENSE_END@
7 */
8
9 /*
10 ** Am implementation of doubly-linked lists.
11 **
12 */
13
14
15 #include <silk/silk.h>
16
17 RCSIDENT("$SiLK: skdllist.c ef14e54179be 2020-04-14 21:57:45Z mthomas $");
18
19 #include <silk/utils.h>
20 #include <silk/skdllist.h>
21
22 /* LOCAL DEFINES AND TYPEDEFS */
23
24 typedef enum sk_dll_dir_en {
25 FORWARD = 1,
26 BACKWARD = 0,
27 TAIL = 0,
28 HEAD = 1
29 } sk_dll_dir_t;
30
31 /* a node is equivalent to an iterator */
32 typedef sk_dll_iter_t sk_dll_node_t;
33
34 struct sk_dllist_st {
35 sk_dll_node_t list;
36 sk_dll_free_fn_t data_free_fn;
37 };
38
39
40 /* LOCAL VARIABLE DEFINITIONS */
41
42 static void *null_value = &null_value;
43
44
45 /* FUNCTION DEFINITIONS */
46
47 sk_dllist_t *
skDLListCreate(sk_dll_free_fn_t free_fn)48 skDLListCreate(
49 sk_dll_free_fn_t free_fn)
50 {
51 sk_dllist_t *list = (sk_dllist_t *)malloc(sizeof(*list));
52
53 if (list != NULL) {
54 list->list.data = null_value;
55 list->list.link[TAIL] = list->list.link[HEAD] = &list->list;
56 list->data_free_fn = free_fn;
57 }
58
59 return list;
60 }
61
62
63 void
skDLListDestroy(sk_dllist_t * list)64 skDLListDestroy(
65 sk_dllist_t *list)
66 {
67 sk_dll_node_t *node, *next;
68
69 if (NULL == list) {
70 return;
71 }
72
73 node = list->list.link[TAIL];
74 while (node->data != null_value) {
75 if (list->data_free_fn) {
76 list->data_free_fn(node->data);
77 }
78 next = node->link[BACKWARD];
79 free(node);
80 node = next;
81 }
82 free(list);
83 }
84
85
86 int
skDLListIsEmpty(const sk_dllist_t * list)87 skDLListIsEmpty(
88 const sk_dllist_t *list)
89 {
90 assert(list);
91 return list->list.link[TAIL] == &list->list;
92 }
93
94
95 static int
sk_dll_peek(const sk_dllist_t * list,void ** data,sk_dll_dir_t dir)96 sk_dll_peek(
97 const sk_dllist_t *list,
98 void **data,
99 sk_dll_dir_t dir)
100 {
101 sk_dll_node_t *node;
102
103 assert(list);
104 assert(data);
105
106 node = list->list.link[dir];
107
108 if (node->data == null_value) {
109 return -1;
110 }
111 *data = node->data;
112
113 return 0;
114 }
115
116
117 int
skDLListPeekTail(const sk_dllist_t * list,void ** data)118 skDLListPeekTail(
119 const sk_dllist_t *list,
120 void **data)
121 {
122 return sk_dll_peek(list, data, TAIL);
123 }
124
125
126 int
skDLListPeekHead(const sk_dllist_t * list,void ** data)127 skDLListPeekHead(
128 const sk_dllist_t *list,
129 void **data)
130 {
131 return sk_dll_peek(list, data, HEAD);
132 }
133
134
135 static void
sk_dll_node_del(sk_dll_node_t * node)136 sk_dll_node_del(
137 sk_dll_node_t *node)
138 {
139 node->link[FORWARD]->link[BACKWARD] = node->link[BACKWARD];
140 node->link[BACKWARD]->link[FORWARD] = node->link[FORWARD];
141 free(node);
142 }
143
144
145 static int
sk_dll_pop(sk_dllist_t * list,void ** data,sk_dll_dir_t dir)146 sk_dll_pop(
147 sk_dllist_t *list,
148 void **data,
149 sk_dll_dir_t dir)
150 {
151 sk_dll_node_t *node;
152
153 assert(list);
154
155 node = list->list.link[dir];
156 if (node->data == null_value) {
157 return -1;
158 }
159 if (data != NULL) {
160 *data = node->data;
161 }
162 sk_dll_node_del(node);
163
164 return 0;
165 }
166
167
168 int
skDLListPopTail(sk_dllist_t * list,void ** data)169 skDLListPopTail(
170 sk_dllist_t *list,
171 void **data)
172 {
173 return sk_dll_pop(list, data, TAIL);
174 }
175
176
177 int
skDLListPopHead(sk_dllist_t * list,void ** data)178 skDLListPopHead(
179 sk_dllist_t *list,
180 void **data)
181 {
182 return sk_dll_pop(list, data, HEAD);
183 }
184
185
186 static int
sk_dll_node_add(sk_dll_iter_t * iter,void * data,sk_dll_dir_t dir)187 sk_dll_node_add(
188 sk_dll_iter_t *iter,
189 void *data,
190 sk_dll_dir_t dir)
191 {
192 sk_dll_node_t *node, *truenode;;
193
194 assert(iter);
195
196 node = (sk_dll_node_t *)malloc(sizeof(*node));
197 if (node == NULL) {
198 return -1;
199 }
200
201 truenode = iter->link[FORWARD]->link[BACKWARD];
202
203 node->data = data;
204 node->link[dir] = truenode->link[dir];
205 node->link[1-dir] = truenode;
206
207 node->link[FORWARD]->link[BACKWARD] = node;
208 node->link[BACKWARD]->link[FORWARD] = node;
209
210 if (truenode != iter) {
211 iter->link[FORWARD] = truenode->link[FORWARD];
212 iter->link[BACKWARD] = truenode->link[BACKWARD];
213 }
214
215 return 0;
216 }
217
218
219 int
skDLListPushTail(sk_dllist_t * list,void * data)220 skDLListPushTail(
221 sk_dllist_t *list,
222 void *data)
223 {
224 return sk_dll_node_add(&list->list, data, TAIL);
225 }
226
227
228 int
skDLListPushHead(sk_dllist_t * list,void * data)229 skDLListPushHead(
230 sk_dllist_t *list,
231 void *data)
232 {
233 return sk_dll_node_add(&list->list, data, HEAD);
234 }
235
236
237 int
skDLListJoin(sk_dllist_t * head,sk_dllist_t * tail)238 skDLListJoin(
239 sk_dllist_t *head,
240 sk_dllist_t *tail)
241 {
242 sk_dll_node_t *tail_h, *tail_t;
243
244 assert(head);
245 assert(tail);
246
247 /* Return an error if the free functions do not match. */
248 if (head->data_free_fn != tail->data_free_fn) {
249 return -1;
250 }
251
252 /* If tail is empty, destroy the tail and return */
253 if (skDLListIsEmpty(tail)) {
254 skDLListDestroy(tail);
255 return 0;
256 }
257
258 /* Save links to the head and tail nodes of tail */
259 tail_h = tail->list.link[HEAD];
260 tail_t = tail->list.link[TAIL];
261
262 /* Reset tail to empty, and destroy */
263 tail->list.link[HEAD] = tail->list.link[TAIL] = &tail->list;
264 skDLListDestroy(tail);
265
266 /* Update the links to insert the list */
267 tail_h->link[BACKWARD] = head->list.link[TAIL];
268 tail_t->link[FORWARD] = &head->list;
269 head->list.link[TAIL]->link[FORWARD] = tail_h;
270 head->list.link[TAIL] = tail_t;
271
272 return 0;
273 }
274
275
276 void
skDLLAssignIter(sk_dll_iter_t * iter,sk_dllist_t * list)277 skDLLAssignIter(
278 sk_dll_iter_t *iter,
279 sk_dllist_t *list)
280 {
281 assert(list);
282 (*iter) = list->list;
283 }
284
285
286 static int
sk_dll_iter_get_next(sk_dll_iter_t * iter,void ** data,sk_dll_dir_t dir)287 sk_dll_iter_get_next(
288 sk_dll_iter_t *iter,
289 void **data,
290 sk_dll_dir_t dir)
291 {
292 *iter = *iter->link[dir];
293 if (iter->data == null_value) {
294 return -1;
295 }
296 if (data != NULL) {
297 *data = iter->data;
298 }
299 return 0;
300 }
301
302
303 int
skDLLIterForward(sk_dll_iter_t * iter,void ** data)304 skDLLIterForward(
305 sk_dll_iter_t *iter,
306 void **data)
307 {
308 return sk_dll_iter_get_next(iter, data, FORWARD);
309 }
310
311
312 int
skDLLIterBackward(sk_dll_iter_t * iter,void ** data)313 skDLLIterBackward(
314 sk_dll_iter_t *iter,
315 void **data)
316 {
317 return sk_dll_iter_get_next(iter, data, BACKWARD);
318 }
319
320
321 int
skDLLIterDel(sk_dll_iter_t * iter)322 skDLLIterDel(
323 sk_dll_iter_t *iter)
324 {
325 assert(iter);
326 if (iter->data == null_value) {
327 return -1;
328 }
329 sk_dll_node_del(iter->link[FORWARD]->link[BACKWARD]);
330 return 0;
331 }
332
333
334 int
skDLLIterAddAfter(sk_dll_iter_t * iter,void * data)335 skDLLIterAddAfter(
336 sk_dll_iter_t *iter,
337 void *data)
338 {
339 return sk_dll_node_add(iter, data, FORWARD);
340 }
341
342
343 int
skDLLIterAddBefore(sk_dll_iter_t * iter,void * data)344 skDLLIterAddBefore(
345 sk_dll_iter_t *iter,
346 void *data)
347 {
348 return sk_dll_node_add(iter, data, BACKWARD);
349 }
350
351
352 int
skDLLIterValue(const sk_dll_iter_t * iter,void ** data)353 skDLLIterValue(
354 const sk_dll_iter_t *iter,
355 void **data)
356 {
357 assert(iter);
358 assert(data);
359
360 if (iter->data == null_value) {
361 return -1;
362 }
363 *data = iter->data;
364 return 0;
365 }
366
367
368 /*
369 ** Local Variables:
370 ** mode:c
371 ** indent-tabs-mode:nil
372 ** c-basic-offset:4
373 ** End:
374 */
375