src/linked_list.c@60ff4561dc04
src/linked_list.c
Mon, 20 Dec 2021 11:17:06 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Mon, 20 Dec 2021 11:17:06 +0100
- changeset 476
- 60ff4561dc04
- parent 475
- 31bf97fdbf71
- child 477
- 73a93c7a56ae
- permissions
- -rw-r--r--
change contract of cx_linked_list_remove()
also use cx_linked_list_remove() in high level API
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
29 #include "cx/linked_list.h"
30 #include <stdint.h>
31 #include <string.h>
32 #include <assert.h>
34 /* LOW LEVEL LINKED LIST FUNCTIONS */
36 #define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off))
38 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
39 assert(start != NULL);
40 assert(loc_advance >= 0);
41 size_t i = start_index;
42 void *cur = start;
43 while (i != index && cur != NULL) {
44 cur = CX_LL_PTR(cur, loc_advance);
45 i < index ? i++ : i--;
46 }
47 return cur;
48 }
50 void *cx_linked_list_first(void *node, ptrdiff_t loc_prev) {
51 return cx_linked_list_last(node, loc_prev);
52 }
54 void *cx_linked_list_last(void *node, ptrdiff_t loc_next) {
55 assert(loc_next >= 0);
56 if (node == NULL)
57 return NULL;
59 void *cur = node;
60 void *last;
61 do {
62 last = cur;
63 } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL);
65 return last;
66 }
68 void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node) {
69 assert(begin != NULL);
70 assert(loc_next >= 0);
71 if (begin == node) return NULL;
72 void *cur = begin;
73 void *next;
74 while (1) {
75 next = CX_LL_PTR(cur, loc_next);
76 if (next == node) return cur;
77 cur = next;
78 }
79 }
81 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
82 assert(loc_next >= 0);
83 assert(CX_LL_PTR(new_node, loc_next) == NULL);
84 void *last;
85 if (end == NULL) {
86 assert(begin != NULL);
87 last = cx_linked_list_last(*begin, loc_next);
88 } else {
89 last = *end;
90 }
91 if (last == NULL) {
92 if (begin != NULL) {
93 *begin = new_node;
94 }
95 } else {
96 // if there is a last node, update its next pointer
97 CX_LL_PTR(last, loc_next) = new_node;
98 }
100 // if there is an end pointer, update it
101 if (end != NULL) {
102 *end = new_node;
103 }
105 // if the nodes use a prev pointer, update it
106 if (loc_prev >= 0) {
107 assert(CX_LL_PTR(new_node, loc_prev) == NULL);
108 CX_LL_PTR(new_node, loc_prev) = last;
109 }
110 }
112 void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
113 assert(loc_next >= 0);
114 assert(CX_LL_PTR(new_node, loc_next) == NULL);
115 void *first;
116 if (begin == NULL) {
117 assert(end != NULL);
118 assert(loc_prev >= 0);
119 first = cx_linked_list_first(*end, loc_prev);
120 } else {
121 first = *begin;
122 }
123 if (first == NULL) {
124 if (end != NULL) {
125 *end = new_node;
126 }
127 } else {
128 CX_LL_PTR(new_node, loc_next) = first;
129 if (loc_prev >= 0) {
130 CX_LL_PTR(first, loc_prev) = new_node;
131 }
132 }
134 if (begin != NULL) {
135 assert(loc_prev < 0 || CX_LL_PTR(new_node, loc_prev) == NULL);
136 *begin = new_node;
137 }
138 }
140 void cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) {
141 assert(loc_next >= 0);
142 assert(loc_prev >= 0 || begin != NULL);
144 // find adjacent nodes
145 void *next = CX_LL_PTR(node, loc_next);
146 void *prev;
147 if (loc_prev >= 0) {
148 prev = CX_LL_PTR(node, loc_prev);
149 } else {
150 prev = cx_linked_list_prev(*begin, loc_next, node);
151 }
153 // update next pointer of prev node, or set begin
154 if (prev == NULL) {
155 if (begin != NULL) {
156 *begin = next;
157 }
158 } else {
159 CX_LL_PTR(prev, loc_next) = next;
160 }
162 // update prev pointer of next node, or set end
163 if (next == NULL) {
164 if (end != NULL) {
165 *end = prev;
166 }
167 } else if (loc_prev >= 0) {
168 CX_LL_PTR(next, loc_prev) = prev;
169 }
170 }
172 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
173 assert(loc_next >= 0);
174 size_t size = 0;
175 while (node != NULL) {
176 node = CX_LL_PTR(node, loc_next);
177 size++;
178 }
179 return size;
180 }
182 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
183 #define ll_next(node) CX_LL_PTR(node, loc_next)
184 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
186 static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next,
187 ptrdiff_t loc_data, int follow_ptr,
188 size_t length, void *ls, void *le, void *re,
189 CxListComparator cmp_func) {
190 const size_t sbo_len = 1024;
191 void *sbo[sbo_len];
192 void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
193 void *rc, *lc;
195 lc = ls;
196 rc = le;
197 size_t n = 0;
198 while (lc && lc != le && rc != re) {
199 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
200 sorted[n] = lc;
201 lc = ll_next(lc);
202 } else {
203 sorted[n] = rc;
204 rc = ll_next(rc);
205 }
206 n++;
207 }
208 while (lc && lc != le) {
209 sorted[n] = lc;
210 lc = ll_next(lc);
211 n++;
212 }
213 while (rc && rc != re) {
214 sorted[n] = rc;
215 rc = ll_next(rc);
216 n++;
217 }
219 // Update pointer
220 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
221 for (size_t i = 0; i < length - 1; i++) {
222 ll_next(sorted[i]) = sorted[i + 1];
223 if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i];
224 }
225 ll_next(sorted[length - 1]) = NULL;
227 void *ret = sorted[0];
228 if (sorted != sbo) {
229 free(sorted);
230 }
231 return ret;
232 }
234 void cx_linked_list_sort( /* NOLINT(misc-no-recursion) - purposely recursive function */
235 void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
236 ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
237 assert(begin != NULL);
238 assert(loc_next >= 0);
239 assert(loc_data >= 0);
240 assert(cmp_func);
242 void *lc, *ls, *le, *re;
244 // set start node
245 ls = *begin;
247 // check how many elements are already sorted
248 lc = ls;
249 size_t ln = 1;
250 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
251 lc = ll_next(lc);
252 ln++;
253 }
254 le = ll_next(lc);
256 // if first unsorted node is NULL, the list is already completely sorted
257 if (le != NULL) {
258 void *rc;
259 size_t rn = 1;
260 rc = le;
261 // skip already sorted elements
262 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
263 rc = ll_next(rc);
264 rn++;
265 }
266 re = ll_next(rc);
268 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
269 void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
270 ln + rn, ls, le, re, cmp_func);
272 // Something left? Sort it!
273 size_t remainder_length = cx_linked_list_size(re, loc_next);
274 if (remainder_length > 0) {
275 void *remainder = re;
276 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func);
278 // merge sorted list with (also sorted) remainder
279 *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
280 ln + rn + remainder_length,
281 sorted, remainder, NULL, cmp_func);
282 } else {
283 // no remainder - we've got our sorted list
284 *begin = sorted;
285 }
286 if (end) *end = cx_linked_list_last(sorted, loc_next);
287 }
288 }
290 #undef ll_next
291 #undef ll_data
293 void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) {
294 assert(begin != NULL);
295 assert(loc_next >= 0);
297 // swap all links
298 void *prev = NULL;
299 void *cur = *begin;
300 while (cur != NULL) {
301 void *next = CX_LL_PTR(cur, loc_next);
303 CX_LL_PTR(cur, loc_next) = prev;
304 if (loc_prev >= 0) {
305 CX_LL_PTR(cur, loc_prev) = next;
306 }
308 prev = cur;
309 cur = next;
310 }
312 // update begin and end
313 if (end != NULL) {
314 *end = *begin;
315 }
316 *begin = prev;
317 }
319 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
321 typedef struct cx_linked_list_node cx_linked_list_node;
322 struct cx_linked_list_node {
323 cx_linked_list_node *prev;
324 cx_linked_list_node *next;
325 char payload[];
326 };
328 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
329 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
330 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
332 typedef struct {
333 cx_list_s base;
334 cx_linked_list_node *begin;
335 cx_linked_list_node *end;
336 } cx_linked_list;
338 static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) {
339 if (index >= list->base.size) {
340 return NULL;
341 } else if (index > list->base.size / 2) {
342 return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
343 } else {
344 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
345 }
346 }
348 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
349 // out-of bounds check
350 if (index > list->size) return 1;
352 // cast a linked list pointer
353 cx_linked_list *ll = (cx_linked_list *) list;
355 // create the new node
356 cx_linked_list_node *node = cxMalloc(list->allocator,
357 sizeof(cx_linked_list_node) + list->itemsize);
359 // sortir if failed
360 if (node == NULL) return 1;
362 // copy payload to the new node
363 memcpy(node->payload, elem, list->itemsize);
365 // check if this is the first node
366 if (ll->begin == NULL) {
367 node->prev = node->next = NULL;
368 ll->begin = ll->end = node;
369 } else {
370 // check if this shall be the new end node
371 if (index == list->size) {
372 ll->end->next = node;
373 node->prev = ll->end;
374 node->next = NULL;
375 ll->end = node;
376 }
377 // check if this shall be the new start node
378 else if (index == 0) {
379 ll->begin->prev = node;
380 node->next = ll->begin;
381 node->prev = NULL;
382 ll->begin = node;
383 } else {
384 // find the node at the current index
385 cx_linked_list_node *cur = cx_ll_node_at(ll, index);
387 // insert before that node
388 // (we know all ptr are non-null because we handled all other cases before)
389 node->next = cur;
390 node->prev = cur->prev;
391 cur->prev = node;
392 node->prev->next = node;
393 }
394 }
396 // increase the size and return
397 list->size++;
398 return 0;
399 }
401 static int cx_ll_add(cx_list_s *list, void *elem) {
402 return cx_ll_insert(list, list->size, elem);
403 }
405 static int cx_pll_insert(cx_list_s *list, size_t index, void *elem) {
406 return cx_ll_insert(list, index, &elem);
407 }
409 static int cx_pll_add(cx_list_s *list, void *elem) {
410 return cx_ll_insert(list, list->size, &elem);
411 }
413 static int cx_ll_remove(cx_list_s *list, size_t index) {
414 cx_linked_list *ll = (cx_linked_list *) list;
415 cx_linked_list_node *node = cx_ll_node_at(ll, index);
417 // out-of-bounds check
418 if (node == NULL) return 1;
420 // remove
421 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
422 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
424 // adjust size
425 list->size--;
427 // free and return
428 cxFree(list->allocator, node);
430 return 0;
431 }
433 static void *cx_ll_at(cx_list_s *list, size_t index) {
434 cx_linked_list *ll = (cx_linked_list *) list;
435 cx_linked_list_node *node = cx_ll_node_at(ll, index);
436 return node == NULL ? NULL : node->payload;
437 }
439 static void *cx_pll_at(cx_list_s *list, size_t index) {
440 cx_linked_list *ll = (cx_linked_list *) list;
441 cx_linked_list_node *node = cx_ll_node_at(ll, index);
442 return node == NULL ? NULL : *(void **) node->payload;
443 }
445 static size_t cx_ll_find(cx_list_s *list, void *elem) {
446 CxListComparator cmp = list->cmpfunc;
447 cx_linked_list *ll = (cx_linked_list *) list;
449 size_t index;
450 cx_linked_list_node *node = ll->begin;
451 for (index = 0; index < list->size; index++) {
452 void *current = node->payload;
453 if (cmp(current, elem) == 0) {
454 return index;
455 }
456 node = node->next;
457 }
458 return index;
459 }
461 static size_t cx_pll_find(cx_list_s *list, void *elem) {
462 CxListComparator cmp = list->cmpfunc;
463 cx_linked_list *ll = (cx_linked_list *) list;
465 size_t index;
466 cx_linked_list_node *node = ll->begin;
467 for (index = 0; index < list->size; index++) {
468 void *current = *(void **) node->payload;
469 if (cmp(current, elem) == 0) {
470 return index;
471 }
472 node = node->next;
473 }
474 return index;
475 }
477 static void cx_ll_sort(cx_list_s *list) {
478 cx_linked_list *ll = (cx_linked_list *) list;
479 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
480 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
481 0, list->cmpfunc);
482 }
484 static void cx_pll_sort(cx_list_s *list) {
485 cx_linked_list *ll = (cx_linked_list *) list;
486 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
487 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
488 1, list->cmpfunc);
489 }
491 static cx_list_class cx_linked_list_class = {
492 cx_ll_add,
493 cx_ll_insert,
494 cx_ll_remove,
495 cx_ll_at,
496 cx_ll_find,
497 cx_ll_sort
498 };
500 static cx_list_class cx_pointer_linked_list_class = {
501 cx_pll_add,
502 cx_pll_insert,
503 cx_ll_remove,
504 cx_pll_at,
505 cx_pll_find,
506 cx_pll_sort
507 };
509 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {
510 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
511 if (list == NULL)
512 return NULL;
514 list->base.cl = &cx_linked_list_class;
515 list->base.allocator = allocator;
516 list->base.cmpfunc = comparator;
517 list->base.itemsize = item_size;
518 list->base.capacity = SIZE_MAX;
519 list->base.size = 0;
521 list->begin = NULL;
522 list->end = NULL;
524 return (CxList) list;
525 }
527 CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator) {
528 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
529 if (list == NULL)
530 return NULL;
532 list->base.cl = &cx_pointer_linked_list_class;
533 list->base.allocator = allocator;
534 list->base.cmpfunc = comparator;
535 list->base.itemsize = sizeof(void *);
536 list->base.capacity = SIZE_MAX;
537 list->base.size = 0;
539 list->begin = NULL;
540 list->end = NULL;
542 return (CxList) list;
543 }
545 void cxLinkedListDestroy(CxList list) {
546 cx_linked_list *ll = (cx_linked_list *) list;
548 cx_linked_list_node *node = ll->begin;
549 while (node) {
550 void *next = node->next;
551 cxFree(list->allocator, node);
552 node = next;
553 }
555 cxFree(list->allocator, list);
556 }
