src/linked_list.c@599770bb6314
src/linked_list.c
Mon, 20 Dec 2021 11:58:36 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Mon, 20 Dec 2021 11:58:36 +0100
- changeset 478
- 599770bb6314
- parent 477
- 73a93c7a56ae
- child 480
- e3be53a3354f
- permissions
- -rw-r--r--
add more nonnull attributes
This also changes the contract for last/first in the sense that these
functions now also require a valid pointer.
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(node != NULL);
56 assert(loc_next >= 0);
58 void *cur = node;
59 void *last;
60 do {
61 last = cur;
62 } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL);
64 return last;
65 }
67 void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node) {
68 assert(begin != NULL);
69 assert(node != 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(new_node != NULL);
83 assert(loc_next >= 0);
84 assert(CX_LL_PTR(new_node, loc_next) == NULL);
85 void *last;
86 if (end == NULL) {
87 assert(begin != NULL);
88 last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next);
89 } else {
90 last = *end;
91 }
92 if (last == NULL) {
93 if (begin != NULL) {
94 *begin = new_node;
95 }
96 } else {
97 // if there is a last node, update its next pointer
98 CX_LL_PTR(last, loc_next) = new_node;
99 }
101 // if there is an end pointer, update it
102 if (end != NULL) {
103 *end = new_node;
104 }
106 // if the nodes use a prev pointer, update it
107 if (loc_prev >= 0) {
108 assert(CX_LL_PTR(new_node, loc_prev) == NULL);
109 CX_LL_PTR(new_node, loc_prev) = last;
110 }
111 }
113 void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
114 assert(new_node != NULL);
115 assert(loc_next >= 0);
116 assert(CX_LL_PTR(new_node, loc_next) == NULL);
117 void *first;
118 if (begin == NULL) {
119 assert(end != NULL);
120 assert(loc_prev >= 0);
121 first = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);
122 } else {
123 first = *begin;
124 }
125 if (first == NULL) {
126 if (end != NULL) {
127 *end = new_node;
128 }
129 } else {
130 CX_LL_PTR(new_node, loc_next) = first;
131 if (loc_prev >= 0) {
132 CX_LL_PTR(first, loc_prev) = new_node;
133 }
134 }
136 if (begin != NULL) {
137 assert(loc_prev < 0 || CX_LL_PTR(new_node, loc_prev) == NULL);
138 *begin = new_node;
139 }
140 }
142 void cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) {
143 assert(node != NULL);
144 assert(loc_next >= 0);
145 assert(loc_prev >= 0 || begin != NULL);
147 // find adjacent nodes
148 void *next = CX_LL_PTR(node, loc_next);
149 void *prev;
150 if (loc_prev >= 0) {
151 prev = CX_LL_PTR(node, loc_prev);
152 } else {
153 prev = cx_linked_list_prev(*begin, loc_next, node);
154 }
156 // update next pointer of prev node, or set begin
157 if (prev == NULL) {
158 if (begin != NULL) {
159 *begin = next;
160 }
161 } else {
162 CX_LL_PTR(prev, loc_next) = next;
163 }
165 // update prev pointer of next node, or set end
166 if (next == NULL) {
167 if (end != NULL) {
168 *end = prev;
169 }
170 } else if (loc_prev >= 0) {
171 CX_LL_PTR(next, loc_prev) = prev;
172 }
173 }
175 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
176 assert(loc_next >= 0);
177 size_t size = 0;
178 while (node != NULL) {
179 node = CX_LL_PTR(node, loc_next);
180 size++;
181 }
182 return size;
183 }
185 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
186 #define ll_next(node) CX_LL_PTR(node, loc_next)
187 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
189 static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next,
190 ptrdiff_t loc_data, int follow_ptr,
191 size_t length, void *ls, void *le, void *re,
192 CxListComparator cmp_func) {
193 const size_t sbo_len = 1024;
194 void *sbo[sbo_len];
195 void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
196 void *rc, *lc;
198 lc = ls;
199 rc = le;
200 size_t n = 0;
201 while (lc && lc != le && rc != re) {
202 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
203 sorted[n] = lc;
204 lc = ll_next(lc);
205 } else {
206 sorted[n] = rc;
207 rc = ll_next(rc);
208 }
209 n++;
210 }
211 while (lc && lc != le) {
212 sorted[n] = lc;
213 lc = ll_next(lc);
214 n++;
215 }
216 while (rc && rc != re) {
217 sorted[n] = rc;
218 rc = ll_next(rc);
219 n++;
220 }
222 // Update pointer
223 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
224 for (size_t i = 0; i < length - 1; i++) {
225 ll_next(sorted[i]) = sorted[i + 1];
226 if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i];
227 }
228 ll_next(sorted[length - 1]) = NULL;
230 void *ret = sorted[0];
231 if (sorted != sbo) {
232 free(sorted);
233 }
234 return ret;
235 }
237 void cx_linked_list_sort( /* NOLINT(misc-no-recursion) - purposely recursive function */
238 void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
239 ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
240 assert(begin != NULL);
241 assert(loc_next >= 0);
242 assert(loc_data >= 0);
243 assert(cmp_func);
245 void *lc, *ls, *le, *re;
247 // set start node
248 ls = *begin;
250 // check how many elements are already sorted
251 lc = ls;
252 size_t ln = 1;
253 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
254 lc = ll_next(lc);
255 ln++;
256 }
257 le = ll_next(lc);
259 // if first unsorted node is NULL, the list is already completely sorted
260 if (le != NULL) {
261 void *rc;
262 size_t rn = 1;
263 rc = le;
264 // skip already sorted elements
265 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
266 rc = ll_next(rc);
267 rn++;
268 }
269 re = ll_next(rc);
271 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
272 void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
273 ln + rn, ls, le, re, cmp_func);
275 // Something left? Sort it!
276 size_t remainder_length = cx_linked_list_size(re, loc_next);
277 if (remainder_length > 0) {
278 void *remainder = re;
279 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func);
281 // merge sorted list with (also sorted) remainder
282 *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
283 ln + rn + remainder_length,
284 sorted, remainder, NULL, cmp_func);
285 } else {
286 // no remainder - we've got our sorted list
287 *begin = sorted;
288 }
289 if (end) *end = cx_linked_list_last(sorted, loc_next);
290 }
291 }
293 #undef ll_next
294 #undef ll_data
296 void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) {
297 assert(begin != NULL);
298 assert(loc_next >= 0);
300 // swap all links
301 void *prev = NULL;
302 void *cur = *begin;
303 while (cur != NULL) {
304 void *next = CX_LL_PTR(cur, loc_next);
306 CX_LL_PTR(cur, loc_next) = prev;
307 if (loc_prev >= 0) {
308 CX_LL_PTR(cur, loc_prev) = next;
309 }
311 prev = cur;
312 cur = next;
313 }
315 // update begin and end
316 if (end != NULL) {
317 *end = *begin;
318 }
319 *begin = prev;
320 }
322 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
324 typedef struct cx_linked_list_node cx_linked_list_node;
325 struct cx_linked_list_node {
326 cx_linked_list_node *prev;
327 cx_linked_list_node *next;
328 char payload[];
329 };
331 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
332 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
333 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
335 typedef struct {
336 cx_list_s base;
337 cx_linked_list_node *begin;
338 cx_linked_list_node *end;
339 } cx_linked_list;
341 static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) {
342 if (index >= list->base.size) {
343 return NULL;
344 } else if (index > list->base.size / 2) {
345 return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
346 } else {
347 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
348 }
349 }
351 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
352 // out-of bounds check
353 if (index > list->size) return 1;
355 // cast a linked list pointer
356 cx_linked_list *ll = (cx_linked_list *) list;
358 // create the new node
359 cx_linked_list_node *node = cxMalloc(list->allocator,
360 sizeof(cx_linked_list_node) + list->itemsize);
362 // sortir if failed
363 if (node == NULL) return 1;
365 // copy payload to the new node
366 memcpy(node->payload, elem, list->itemsize);
368 // check if this is the first node
369 if (ll->begin == NULL) {
370 node->prev = node->next = NULL;
371 ll->begin = ll->end = node;
372 } else {
373 // check if this shall be the new end node
374 if (index == list->size) {
375 ll->end->next = node;
376 node->prev = ll->end;
377 node->next = NULL;
378 ll->end = node;
379 }
380 // check if this shall be the new start node
381 else if (index == 0) {
382 ll->begin->prev = node;
383 node->next = ll->begin;
384 node->prev = NULL;
385 ll->begin = node;
386 } else {
387 // find the node at the current index
388 cx_linked_list_node *cur = cx_ll_node_at(ll, index);
390 // insert before that node
391 // (we know all ptr are non-null because we handled all other cases before)
392 node->next = cur;
393 node->prev = cur->prev;
394 cur->prev = node;
395 node->prev->next = node;
396 }
397 }
399 // increase the size and return
400 list->size++;
401 return 0;
402 }
404 static int cx_ll_add(cx_list_s *list, void *elem) {
405 return cx_ll_insert(list, list->size, elem);
406 }
408 static int cx_pll_insert(cx_list_s *list, size_t index, void *elem) {
409 return cx_ll_insert(list, index, &elem);
410 }
412 static int cx_pll_add(cx_list_s *list, void *elem) {
413 return cx_ll_insert(list, list->size, &elem);
414 }
416 static int cx_ll_remove(cx_list_s *list, size_t index) {
417 cx_linked_list *ll = (cx_linked_list *) list;
418 cx_linked_list_node *node = cx_ll_node_at(ll, index);
420 // out-of-bounds check
421 if (node == NULL) return 1;
423 // remove
424 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
425 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
427 // adjust size
428 list->size--;
430 // free and return
431 cxFree(list->allocator, node);
433 return 0;
434 }
436 static void *cx_ll_at(cx_list_s *list, size_t index) {
437 cx_linked_list *ll = (cx_linked_list *) list;
438 cx_linked_list_node *node = cx_ll_node_at(ll, index);
439 return node == NULL ? NULL : node->payload;
440 }
442 static void *cx_pll_at(cx_list_s *list, size_t index) {
443 cx_linked_list *ll = (cx_linked_list *) list;
444 cx_linked_list_node *node = cx_ll_node_at(ll, index);
445 return node == NULL ? NULL : *(void **) node->payload;
446 }
448 static size_t cx_ll_find(cx_list_s *list, void *elem) {
449 CxListComparator cmp = list->cmpfunc;
450 cx_linked_list *ll = (cx_linked_list *) list;
452 size_t index;
453 cx_linked_list_node *node = ll->begin;
454 for (index = 0; index < list->size; index++) {
455 void *current = node->payload;
456 if (cmp(current, elem) == 0) {
457 return index;
458 }
459 node = node->next;
460 }
461 return index;
462 }
464 static size_t cx_pll_find(cx_list_s *list, void *elem) {
465 CxListComparator cmp = list->cmpfunc;
466 cx_linked_list *ll = (cx_linked_list *) list;
468 size_t index;
469 cx_linked_list_node *node = ll->begin;
470 for (index = 0; index < list->size; index++) {
471 void *current = *(void **) node->payload;
472 if (cmp(current, elem) == 0) {
473 return index;
474 }
475 node = node->next;
476 }
477 return index;
478 }
480 static void cx_ll_sort(cx_list_s *list) {
481 cx_linked_list *ll = (cx_linked_list *) list;
482 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
483 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
484 0, list->cmpfunc);
485 }
487 static void cx_pll_sort(cx_list_s *list) {
488 cx_linked_list *ll = (cx_linked_list *) list;
489 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
490 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
491 1, list->cmpfunc);
492 }
494 static cx_list_class cx_linked_list_class = {
495 cx_ll_add,
496 cx_ll_insert,
497 cx_ll_remove,
498 cx_ll_at,
499 cx_ll_find,
500 cx_ll_sort
501 };
503 static cx_list_class cx_pointer_linked_list_class = {
504 cx_pll_add,
505 cx_pll_insert,
506 cx_ll_remove,
507 cx_pll_at,
508 cx_pll_find,
509 cx_pll_sort
510 };
512 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {
513 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
514 if (list == NULL)
515 return NULL;
517 list->base.cl = &cx_linked_list_class;
518 list->base.allocator = allocator;
519 list->base.cmpfunc = comparator;
520 list->base.itemsize = item_size;
521 list->base.capacity = SIZE_MAX;
522 list->base.size = 0;
524 list->begin = NULL;
525 list->end = NULL;
527 return (CxList) list;
528 }
530 CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator) {
531 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
532 if (list == NULL)
533 return NULL;
535 list->base.cl = &cx_pointer_linked_list_class;
536 list->base.allocator = allocator;
537 list->base.cmpfunc = comparator;
538 list->base.itemsize = sizeof(void *);
539 list->base.capacity = SIZE_MAX;
540 list->base.size = 0;
542 list->begin = NULL;
543 list->end = NULL;
545 return (CxList) list;
546 }
548 void cxLinkedListDestroy(CxList list) {
549 cx_linked_list *ll = (cx_linked_list *) list;
551 cx_linked_list_node *node = ll->begin;
552 while (node) {
553 void *next = node->next;
554 cxFree(list->allocator, node);
555 node = next;
556 }
558 cxFree(list->allocator, list);
559 }
