Kestrel Interface
Loading...
Searching...
No Matches
kest_linked_list.h
Go to the documentation of this file.
1#ifndef LINKED_LIST_H
2#define LINKED_LIST_H
3
4#ifndef LL_FREE
5#define LL_FREE kest_free
6#endif
7
8#ifndef LL_MALLOC
9#define LL_MALLOC kest_alloc
10#endif
11
12#define DECLARE_LINKED_LIST(X) struct X##_ll; \
13typedef struct X##_ll { \
14 X data; \
15 struct X##_ll *next; \
16} X##_ll; \
17 \
18X##_ll *X##_ll_new(X x); \
19void X##_ll_free(X##_ll *list); \
20X##_ll *X##_ll_tail(X##_ll *list); \
21X##_ll *X##_ll_append(X##_ll *list, X x); \
22int X##_ll_safe_append(X##_ll **list_ptr, X x); \
23X##_ll *X##_ll_append_return_tail(X##_ll **list, X x); \
24X##_ll *X##_ll_remove_next(X##_ll *list); \
25void X##_ll_destroy(X##_ll *list, void (*destructor)(X x)); \
26void X##_ll_map(X##_ll *list, X (*fmap)(X x)); \
27X##_ll *X##_ll_cmp_search(X##_ll *list, int (*cmp_function)(X, X), X x); \
28X##_ll *X##_ll_destructor_free_and_remove_matching(X##_ll *list, int (*cmp_function)(X, X), X x, void (*destructor)(X));
29
30#define IMPLEMENT_LINKED_LIST(X) \
31X##_ll *X##_ll_new(X x) \
32{ \
33 X##_ll *result = (X##_ll*)LL_MALLOC(sizeof(X##_ll)); \
34 \
35 if (result == NULL) \
36 return NULL; \
37 \
38 result->data = x; \
39 result->next = NULL; \
40 \
41 return result; \
42} \
43 \
44X##_ll *X##_ll_tail(X##_ll *list) \
45{ \
46 if (list == NULL) \
47 return NULL; \
48 \
49 X##_ll *current = list; \
50 \
51 while (current->next != NULL) \
52 current = current->next; \
53 \
54 return current; \
55} \
56 \
57void X##_ll_free(X##_ll *list) \
58{ \
59 if (list == NULL) \
60 return; \
61 X##_ll *current = list; \
62 X##_ll *next = NULL; \
63 while (current != NULL) { \
64 next = current->next; \
65 LL_FREE(current); \
66 current = next; \
67 } \
68} \
69 \
70void X##_ll_destroy(X##_ll *list, void (*destructor)(X x)) \
71{ \
72 if (list == NULL) \
73 return; \
74 \
75 X##_ll *current = list; \
76 X##_ll *next = NULL; \
77 \
78 while (current != NULL) { \
79 next = current->next; \
80 destructor(current->data); \
81 LL_FREE(current); \
82 current = next; \
83 } \
84} \
85 \
86X##_ll *X##_ll_append(X##_ll *list, X x) \
87{ \
88 X##_ll *next = X##_ll_new(x); \
89 if (list == NULL) return next; \
90 \
91 X##_ll *current = list; \
92 \
93 while (current->next != NULL) \
94 current = current->next; \
95 \
96 current->next = next; \
97 \
98 return list; \
99} \
100 \
101int X##_ll_safe_append(X##_ll **list_ptr, X x) \
102{ \
103 if (!list_ptr) return 0; \
104 X##_ll *next = X##_ll_new(x); \
105 if (!next) return 0; \
106 X##_ll *list = *list_ptr; \
107 if (list == NULL) \
108 { \
109 *list_ptr = next; \
110 return 1; \
111 } \
112 \
113 X##_ll *current = list; \
114 \
115 while (current->next != NULL) \
116 current = current->next; \
117 \
118 current->next = next; \
119 \
120 return 1; \
121} \
122 \
123X##_ll *X##_ll_append_return_tail(X##_ll **list, X x) \
124{ \
125 if (list == NULL) \
126 return NULL; \
127 \
128 X##_ll *next = X##_ll_new(x); \
129 if (*list == NULL) { \
130 *list = next; \
131 return next; \
132 } \
133 \
134 X##_ll *current = *list; \
135 \
136 while (current->next != NULL) \
137 current = current->next; \
138 \
139 current->next = next; \
140 \
141 return next; \
142} \
143 \
144X##_ll *X##_ll_remove_next(X##_ll *list) \
145{ \
146 if (list == NULL) \
147 return NULL; \
148 \
149 X##_ll *next = list->next; \
150 \
151 if (next == NULL) \
152 return NULL; \
153 \
154 list->next = list->next->next; \
155 \
156 return next; \
157} \
158 \
159void X##_ll_map(X##_ll *list, X (*fmap)(X x)) \
160{ \
161 if (list == NULL) \
162 return; \
163 \
164 list->data = fmap(list->data); \
165 X##_ll_map(list->next, fmap); \
166} \
167 \
168X##_ll *X##_ll_cmp_search(X##_ll *list, int (*cmp_function)(X, X), X x) \
169{ \
170 if (list == NULL) \
171 return NULL; \
172 \
173 X##_ll *current = list; \
174 \
175 while (current) { \
176 if (cmp_function(current->data, x) == 0) \
177 return current; \
178 \
179 current = current->next; \
180 } \
181 \
182 return NULL; \
183} \
184 \
185X##_ll *X##_ll_destructor_free_and_remove_matching(X##_ll *list, int (*cmp_function)(X, X), X x, void (*destructor)(X)) \
186{ \
187 if (list == NULL) \
188 return NULL; \
189 \
190 X##_ll *current = list; \
191 X##_ll *prev = NULL; \
192 X##_ll *next = NULL; \
193 \
194 while (current) { \
195 next = current->next; \
196 if (cmp_function(current->data, x) == 0) { \
197 if (current == list) \
198 list = next; \
199 destructor(current->data); \
200 LL_FREE(current); \
201 if (prev) \
202 prev->next = next; \
203 } else { \
204 prev = current; \
205 } \
206 current = next; \
207 } \
208 \
209 return list; \
210}
211
212#define DECLARE_LINKED_PTR_LIST(X) struct X##_pll; \
213typedef struct X##_pll { \
214 X *data; \
215 struct X##_pll *next; \
216} X##_pll; \
217 \
218X##_pll *X##_pll_new(X *value); \
219X##_pll *X##_pll_anew(X *value, void* (*allocator)(size_t size)); \
220void X##_pll_free(X##_pll *list); \
221X##_pll *X##_pll_tail(X##_pll *list); \
222X##_pll *X##_pll_append(X##_pll *list, X *value); \
223X##_pll *X##_pll_aappend(X##_pll *list, X *value, void* (*allocator)(size_t size)); \
224int X##_pll_safe_append(X##_pll **list_ptr, X *value); \
225int X##_pll_safe_aappend(X##_pll **list_ptr, X *value, void* (*allocator)(size_t size)); \
226X##_pll *X##_pll_append_return_tail(X##_pll **list, X *x); \
227X##_pll *X##_pll_aappend_return_tail(X##_pll **list, X *x, void* (*allocator)(size_t size)); \
228X##_pll *X##_pll_remove_next(X##_pll *list); \
229void X##_pll_free(X##_pll *list); \
230void X##_pll_destroy(X##_pll *list, void (*destructor)(X *x)); \
231X##_pll *X##_pll_cmp_search(X##_pll *list, int (*cmp_function)(const X*, const X*), const X *x); \
232X##_pll *X##_pll_destructor_free_and_remove_matching(X##_pll *list, int (*cmp_function)(X*, X*), X *x, void (*destructor)(X*));
233
234#define IMPLEMENT_LINKED_PTR_LIST(X) \
235 \
236X##_pll *X##_pll_new(X *value) \
237{ \
238 X##_pll *result = (X##_pll*)LL_MALLOC(sizeof(X##_pll)); \
239 \
240 if (result == NULL) \
241 return NULL; \
242 \
243 result->data = value; \
244 result->next = NULL; \
245 \
246 return result; \
247} \
248 \
249X##_pll *X##_pll_anew(X *value, void* (*allocator)(size_t size)) \
250{ \
251 X##_pll *result = (X##_pll*)allocator(sizeof(X##_pll)); \
252 \
253 if (result == NULL) \
254 return NULL; \
255 \
256 result->data = value; \
257 result->next = NULL; \
258 \
259 return result; \
260} \
261 \
262X##_pll *X##_pll_tail(X##_pll *list) \
263{ \
264 if (list == NULL) \
265 return NULL; \
266 \
267 X##_pll *current = list; \
268 \
269 while (current->next != NULL) \
270 current = current->next; \
271 \
272 return current; \
273} \
274 \
275X##_pll *X##_pll_append(X##_pll *list, X *x) \
276{ \
277 X##_pll *next = X##_pll_new(x); \
278 if (list == NULL) return next; \
279 \
280 X##_pll *current = list; \
281 \
282 while (current->next != NULL) \
283 current = current->next; \
284 \
285 current->next = next; \
286 \
287 return list; \
288} \
289 \
290X##_pll *X##_pll_aappend(X##_pll *list, X *x, void* (*allocator)(size_t size)) \
291{ \
292 X##_pll *next = X##_pll_anew(x, allocator); \
293 if (list == NULL) return next; \
294 \
295 X##_pll *current = list; \
296 \
297 while (current->next != NULL) \
298 current = current->next; \
299 \
300 current->next = next; \
301 \
302 return list; \
303} \
304 \
305int X##_pll_safe_append(X##_pll **list_ptr, X *x) \
306{ \
307 if (!list_ptr) return ERR_NULL_PTR; \
308 X##_pll *next = X##_pll_new(x); \
309 if (!next) return ERR_ALLOC_FAIL; \
310 X##_pll *list = *list_ptr; \
311 if (list == NULL) \
312 { \
313 *list_ptr = next; \
314 return NO_ERROR; \
315 } \
316 \
317 X##_pll *current = list; \
318 \
319 while (current->next != NULL) \
320 current = current->next; \
321 \
322 current->next = next; \
323 \
324 return NO_ERROR; \
325} \
326 \
327int X##_pll_safe_aappend(X##_pll **list_ptr, X *x, void* (*allocator)(size_t size)) \
328{ \
329 if (!list_ptr) return ERR_NULL_PTR; \
330 X##_pll *next = X##_pll_anew(x, allocator); \
331 if (!next) return ERR_ALLOC_FAIL; \
332 X##_pll *list = *list_ptr; \
333 if (list == NULL) \
334 { \
335 *list_ptr = next; \
336 return NO_ERROR; \
337 } \
338 \
339 X##_pll *current = list; \
340 \
341 while (current->next != NULL) \
342 current = current->next; \
343 \
344 current->next = next; \
345 \
346 return NO_ERROR; \
347} \
348 \
349X##_pll *X##_pll_append_return_tail(X##_pll **list, X *x) \
350{ \
351 if (list == NULL) \
352 return NULL; \
353 \
354 X##_pll *next = X##_pll_new(x); \
355 if (*list == NULL) { \
356 *list = next; \
357 return next; \
358 } \
359 \
360 X##_pll *current = *list; \
361 \
362 while (current->next != NULL) \
363 current = current->next; \
364 \
365 current->next = next; \
366 \
367 return next; \
368} \
369 \
370X##_pll *X##_pll_aappend_return_tail(X##_pll **list, X *x, void* (*allocator)(size_t size)) \
371{ \
372 if (list == NULL) \
373 return NULL; \
374 \
375 X##_pll *next = X##_pll_anew(x, allocator); \
376 if (*list == NULL) { \
377 *list = next; \
378 return next; \
379 } \
380 \
381 X##_pll *current = *list; \
382 \
383 while (current->next != NULL) \
384 current = current->next; \
385 \
386 current->next = next; \
387 \
388 return next; \
389} \
390 \
391 \
392void X##_pll_free(X##_pll *list) \
393{ \
394 if (list == NULL) \
395 return; \
396 X##_pll *current = list; \
397 X##_pll *next = NULL; \
398 while (current != NULL) { \
399 next = current->next; \
400 LL_FREE(current->data); \
401 LL_FREE(current); \
402 current = next; \
403 } \
404} \
405 \
406void X##_pll_destroy(X##_pll *list, void (*destructor)(X *x)) \
407{ \
408 if (list == NULL) \
409 return; \
410 \
411 X##_pll *current = list; \
412 X##_pll *next = NULL; \
413 while (current != NULL) { \
414 next = current->next; \
415 destructor(current->data); \
416 LL_FREE(current); \
417 current = next; \
418 } \
419} \
420 \
421X##_pll *X##_pll_remove_next(X##_pll *list) \
422{ \
423 if (list == NULL) \
424 return NULL; \
425 \
426 X##_pll *next = list->next; \
427 \
428 if (next == NULL) \
429 return NULL; \
430 \
431 list->next = next->next; \
432 \
433 return next; \
434} \
435 \
436void X##_pll_map(X##_pll *list, X *(*fmap)(X *x)) \
437{ \
438 if (list == NULL) \
439 return; \
440 \
441 list->data = fmap(list->data); \
442 X##_pll_map(list->next, fmap); \
443} \
444 \
445X##_pll *X##_pll_cmp_search(X##_pll *list, int (*cmp_function)(const X*, const X*), const X *x) \
446{ \
447 if (list == NULL) \
448 return NULL; \
449 \
450 X##_pll *current = list; \
451 \
452 while (current) { \
453 if (cmp_function(current->data, x) == 0) \
454 return current; \
455 \
456 current = current->next; \
457 } \
458 \
459 return NULL; \
460} \
461 \
462 \
463X##_pll *X##_pll_destructor_free_and_remove_matching(X##_pll *list, int (*cmp_function)(X*, X*), X *x, void (*destructor)(X*)) \
464{ \
465 if (list == NULL) \
466 return NULL; \
467 \
468 X##_pll *current = list; \
469 X##_pll *next = NULL; \
470 X##_pll *prev = NULL; \
471 \
472 while (current) { \
473 next = current->next; \
474 if (cmp_function(current->data, x) == 0) { \
475 if (current == list) \
476 list = next; \
477 destructor(current->data); \
478 LL_FREE(current); \
479 if (prev) \
480 prev->next = next; \
481 } else { \
482 prev = current; \
483 } \
484 current = next; \
485 } \
486 \
487 return list; \
488}
489
490#endif