src/linked_list.c@73a93c7a56ae
src/linked_list.c
Mon, 20 Dec 2021 11:26:39 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Mon, 20 Dec 2021 11:26:39 +0100
- changeset 477
- 73a93c7a56ae
- parent 476
- 60ff4561dc04
- child 478
- 599770bb6314
- permissions
- -rw-r--r--
add more explicit documentation to cx_linked_list_remove()
also require nonnull node argument
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(node != NULL);
142 assert(loc_next >= 0);
143 assert(loc_prev >= 0 || begin != NULL);
145 // find adjacent nodes
146 void *next = CX_LL_PTR(node, loc_next);
147 void *prev;
148 if (loc_prev >= 0) {
149 prev = CX_LL_PTR(node, loc_prev);
150 } else {
151 prev = cx_linked_list_prev(*begin, loc_next, node);
152 }
154 // update next pointer of prev node, or set begin
155 if (prev == NULL) {
156 if (begin != NULL) {
157 *begin = next;
158 }
159 } else {
160 CX_LL_PTR(prev, loc_next) = next;
161 }
163 // update prev pointer of next node, or set end
164 if (next == NULL) {
165 if (end != NULL) {
166 *end = prev;
167 }
168 } else if (loc_prev >= 0) {
169 CX_LL_PTR(next, loc_prev) = prev;
170 }
171 }
173 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
174 assert(loc_next >= 0);
175 size_t size = 0;
176 while (node != NULL) {
177 node = CX_LL_PTR(node, loc_next);
178 size++;
179 }
180 return size;
181 }
183 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
184 #define ll_next(node) CX_LL_PTR(node, loc_next)
185 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
187 static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next,
188 ptrdiff_t loc_data, int follow_ptr,
189 size_t length, void *ls, void *le, void *re,
190 CxListComparator cmp_func) {
191 const size_t sbo_len = 1024;
192 void *sbo[sbo_len];
193 void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
194 void *rc, *lc;
196 lc = ls;
197 rc = le;
198 size_t n = 0;
199 while (lc && lc != le && rc != re) {
200 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
201 sorted[n] = lc;
202 lc = ll_next(lc);
203 } else {
204 sorted[n] = rc;
205 rc = ll_next(rc);
206 }
207 n++;
208 }
209 while (lc && lc != le) {
210 sorted[n] = lc;
211 lc = ll_next(lc);
212 n++;
213 }
214 while (rc && rc != re) {
215 sorted[n] = rc;
216 rc = ll_next(rc);
217 n++;
218 }
220 // Update pointer
221 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
222 for (size_t i = 0; i < length - 1; i++) {
223 ll_next(sorted[i]) = sorted[i + 1];
224 if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i];
225 }
226 ll_next(sorted[length - 1]) = NULL;
228 void *ret = sorted[0];
229 if (sorted != sbo) {
230 free(sorted);
231 }
232 return ret;
233 }
235 void cx_linked_list_sort( /* NOLINT(misc-no-recursion) - purposely recursive function */
236 void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
237 ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
238 assert(begin != NULL);
239 assert(loc_next >= 0);
240 assert(loc_data >= 0);
241 assert(cmp_func);
243 void *lc, *ls, *le, *re;
245 // set start node
246 ls = *begin;
248 // check how many elements are already sorted
249 lc = ls;
250 size_t ln = 1;
251 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
252 lc = ll_next(lc);
253 ln++;
254 }
255 le = ll_next(lc);
257 // if first unsorted node is NULL, the list is already completely sorted
258 if (le != NULL) {
259 void *rc;
260 size_t rn = 1;
261 rc = le;
262 // skip already sorted elements
263 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
264 rc = ll_next(rc);
265 rn++;
266 }
267 re = ll_next(rc);
269 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
270 void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
271 ln + rn, ls, le, re, cmp_func);
273 // Something left? Sort it!
274 size_t remainder_length = cx_linked_list_size(re, loc_next);
275 if (remainder_length > 0) {
276 void *remainder = re;
277 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func);
279 // merge sorted list with (also sorted) remainder
280 *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
281 ln + rn + remainder_length,
282 sorted, remainder, NULL, cmp_func);
283 } else {
284 // no remainder - we've got our sorted list
285 *begin = sorted;
286 }
287 if (end) *end = cx_linked_list_last(sorted, loc_next);
288 }
289 }
291 #undef ll_next
292 #undef ll_data
294 void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) {
295 assert(begin != NULL);
296 assert(loc_next >= 0);
298 // swap all links
299 void *prev = NULL;
300 void *cur = *begin;
301 while (cur != NULL) {
302 void *next = CX_LL_PTR(cur, loc_next);
304 CX_LL_PTR(cur, loc_next) = prev;
305 if (loc_prev >= 0) {
306 CX_LL_PTR(cur, loc_prev) = next;
307 }
309 prev = cur;
310 cur = next;
311 }
313 // update begin and end
314 if (end != NULL) {
315 *end = *begin;
316 }
317 *begin = prev;
318 }
320 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
322 typedef struct cx_linked_list_node cx_linked_list_node;
323 struct cx_linked_list_node {
324 cx_linked_list_node *prev;
325 cx_linked_list_node *next;
326 char payload[];
327 };
329 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
330 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
331 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
333 typedef struct {
334 cx_list_s base;
335 cx_linked_list_node *begin;
336 cx_linked_list_node *end;
337 } cx_linked_list;
339 static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) {
340 if (index >= list->base.size) {
341 return NULL;
342 } else if (index > list->base.size / 2) {
343 return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
344 } else {
345 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
346 }
347 }
349 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
350 // out-of bounds check
351 if (index > list->size) return 1;
353 // cast a linked list pointer
354 cx_linked_list *ll = (cx_linked_list *) list;
356 // create the new node
357 cx_linked_list_node *node = cxMalloc(list->allocator,
358 sizeof(cx_linked_list_node) + list->itemsize);
360 // sortir if failed
361 if (node == NULL) return 1;
363 // copy payload to the new node
364 memcpy(node->payload, elem, list->itemsize);
366 // check if this is the first node
367 if (ll->begin == NULL) {
368 node->prev = node->next = NULL;
369 ll->begin = ll->end = node;
370 } else {
371 // check if this shall be the new end node
372 if (index == list->size) {
373 ll->end->next = node;
374 node->prev = ll->end;
375 node->next = NULL;
376 ll->end = node;
377 }
378 // check if this shall be the new start node
379 else if (index == 0) {
380 ll->begin->prev = node;
381 node->next = ll->begin;
382 node->prev = NULL;
383 ll->begin = node;
384 } else {
385 // find the node at the current index
386 cx_linked_list_node *cur = cx_ll_node_at(ll, index);
388 // insert before that node
389 // (we know all ptr are non-null because we handled all other cases before)
390 node->next = cur;
391 node->prev = cur->prev;
392 cur->prev = node;
393 node->prev->next = node;
394 }
395 }
397 // increase the size and return
398 list->size++;
399 return 0;
400 }
402 static int cx_ll_add(cx_list_s *list, void *elem) {
403 return cx_ll_insert(list, list->size, elem);
404 }
406 static int cx_pll_insert(cx_list_s *list, size_t index, void *elem) {
407 return cx_ll_insert(list, index, &elem);
408 }
410 static int cx_pll_add(cx_list_s *list, void *elem) {
411 return cx_ll_insert(list, list->size, &elem);
412 }
414 static int cx_ll_remove(cx_list_s *list, size_t index) {
415 cx_linked_list *ll = (cx_linked_list *) list;
416 cx_linked_list_node *node = cx_ll_node_at(ll, index);
418 // out-of-bounds check
419 if (node == NULL) return 1;
421 // remove
422 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
423 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
425 // adjust size
426 list->size--;
428 // free and return
429 cxFree(list->allocator, node);
431 return 0;
432 }
434 static void *cx_ll_at(cx_list_s *list, size_t index) {
435 cx_linked_list *ll = (cx_linked_list *) list;
436 cx_linked_list_node *node = cx_ll_node_at(ll, index);
437 return node == NULL ? NULL : node->payload;
438 }
440 static void *cx_pll_at(cx_list_s *list, size_t index) {
441 cx_linked_list *ll = (cx_linked_list *) list;
442 cx_linked_list_node *node = cx_ll_node_at(ll, index);
443 return node == NULL ? NULL : *(void **) node->payload;
444 }
446 static size_t cx_ll_find(cx_list_s *list, void *elem) {
447 CxListComparator cmp = list->cmpfunc;
448 cx_linked_list *ll = (cx_linked_list *) list;
450 size_t index;
451 cx_linked_list_node *node = ll->begin;
452 for (index = 0; index < list->size; index++) {
453 void *current = node->payload;
454 if (cmp(current, elem) == 0) {
455 return index;
456 }
457 node = node->next;
458 }
459 return index;
460 }
462 static size_t cx_pll_find(cx_list_s *list, void *elem) {
463 CxListComparator cmp = list->cmpfunc;
464 cx_linked_list *ll = (cx_linked_list *) list;
466 size_t index;
467 cx_linked_list_node *node = ll->begin;
468 for (index = 0; index < list->size; index++) {
469 void *current = *(void **) node->payload;
470 if (cmp(current, elem) == 0) {
471 return index;
472 }
473 node = node->next;
474 }
475 return index;
476 }
478 static void cx_ll_sort(cx_list_s *list) {
479 cx_linked_list *ll = (cx_linked_list *) list;
480 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
481 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
482 0, list->cmpfunc);
483 }
485 static void cx_pll_sort(cx_list_s *list) {
486 cx_linked_list *ll = (cx_linked_list *) list;
487 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
488 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
489 1, list->cmpfunc);
490 }
492 static cx_list_class cx_linked_list_class = {
493 cx_ll_add,
494 cx_ll_insert,
495 cx_ll_remove,
496 cx_ll_at,
497 cx_ll_find,
498 cx_ll_sort
499 };
501 static cx_list_class cx_pointer_linked_list_class = {
502 cx_pll_add,
503 cx_pll_insert,
504 cx_ll_remove,
505 cx_pll_at,
506 cx_pll_find,
507 cx_pll_sort
508 };
510 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {
511 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
512 if (list == NULL)
513 return NULL;
515 list->base.cl = &cx_linked_list_class;
516 list->base.allocator = allocator;
517 list->base.cmpfunc = comparator;
518 list->base.itemsize = item_size;
519 list->base.capacity = SIZE_MAX;
520 list->base.size = 0;
522 list->begin = NULL;
523 list->end = NULL;
525 return (CxList) list;
526 }
528 CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator) {
529 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
530 if (list == NULL)
531 return NULL;
533 list->base.cl = &cx_pointer_linked_list_class;
534 list->base.allocator = allocator;
535 list->base.cmpfunc = comparator;
536 list->base.itemsize = sizeof(void *);
537 list->base.capacity = SIZE_MAX;
538 list->base.size = 0;
540 list->begin = NULL;
541 list->end = NULL;
543 return (CxList) list;
544 }
546 void cxLinkedListDestroy(CxList list) {
547 cx_linked_list *ll = (cx_linked_list *) list;
549 cx_linked_list_node *node = ll->begin;
550 while (node) {
551 void *next = node->next;
552 cxFree(list->allocator, node);
553 node = next;
554 }
556 cxFree(list->allocator, list);
557 }
