src/linked_list.c@e3be53a3354f
src/linked_list.c
Mon, 20 Dec 2021 13:01:38 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Mon, 20 Dec 2021 13:01:38 +0100
- changeset 480
- e3be53a3354f
- parent 478
- 599770bb6314
- child 481
- eef025d82a34
- permissions
- -rw-r--r--
add cx_linked_list_find()
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))
37 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
38 #define ll_next(node) CX_LL_PTR(node, loc_next)
39 #define ll_advance(node) CX_LL_PTR(node, loc_advance)
40 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
42 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
43 assert(start != NULL);
44 assert(loc_advance >= 0);
45 size_t i = start_index;
46 void *cur = start;
47 while (i != index && cur != NULL) {
48 cur = ll_advance(cur);
49 i < index ? i++ : i--;
50 }
51 return cur;
52 }
54 size_t cx_linked_list_find(void *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, int follow_ptr,
55 CxListComparator cmp_func, void *elem) {
56 assert(start != NULL);
57 assert(loc_advance >= 0);
58 assert(loc_data >= 0);
59 assert(cmp_func);
61 void *node = start;
62 size_t index = 0;
63 do {
64 void *current = ll_data(node);
65 if (cmp_func(current, elem) == 0) {
66 return index;
67 }
68 node = ll_advance(node);
69 index++;
70 } while (node != NULL);
71 return index;
72 }
74 void *cx_linked_list_first(void *node, ptrdiff_t loc_prev) {
75 return cx_linked_list_last(node, loc_prev);
76 }
78 void *cx_linked_list_last(void *node, ptrdiff_t loc_next) {
79 assert(node != NULL);
80 assert(loc_next >= 0);
82 void *cur = node;
83 void *last;
84 do {
85 last = cur;
86 } while ((cur = ll_next(cur)) != NULL);
88 return last;
89 }
91 void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node) {
92 assert(begin != NULL);
93 assert(node != NULL);
94 assert(loc_next >= 0);
95 if (begin == node) return NULL;
96 void *cur = begin;
97 void *next;
98 while (1) {
99 next = ll_next(cur);
100 if (next == node) return cur;
101 cur = next;
102 }
103 }
105 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
106 assert(new_node != NULL);
107 assert(loc_next >= 0);
108 assert(ll_next(new_node) == NULL);
109 void *last;
110 if (end == NULL) {
111 assert(begin != NULL);
112 last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next);
113 } else {
114 last = *end;
115 }
116 if (last == NULL) {
117 if (begin != NULL) {
118 *begin = new_node;
119 }
120 } else {
121 // if there is a last node, update its next pointer
122 ll_next(last) = new_node;
123 }
125 // if there is an end pointer, update it
126 if (end != NULL) {
127 *end = new_node;
128 }
130 // if the nodes use a prev pointer, update it
131 if (loc_prev >= 0) {
132 assert(ll_prev(new_node) == NULL);
133 ll_prev(new_node) = last;
134 }
135 }
137 void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
138 assert(new_node != NULL);
139 assert(loc_next >= 0);
140 assert(ll_next(new_node) == NULL);
141 void *first;
142 if (begin == NULL) {
143 assert(end != NULL);
144 assert(loc_prev >= 0);
145 first = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);
146 } else {
147 first = *begin;
148 }
149 if (first == NULL) {
150 if (end != NULL) {
151 *end = new_node;
152 }
153 } else {
154 ll_next(new_node) = first;
155 if (loc_prev >= 0) {
156 ll_prev(first) = new_node;
157 }
158 }
160 if (begin != NULL) {
161 assert(loc_prev < 0 || ll_prev(new_node) == NULL);
162 *begin = new_node;
163 }
164 }
166 void cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) {
167 assert(node != NULL);
168 assert(loc_next >= 0);
169 assert(loc_prev >= 0 || begin != NULL);
171 // find adjacent nodes
172 void *next = ll_next(node);
173 void *prev;
174 if (loc_prev >= 0) {
175 prev = ll_prev(node);
176 } else {
177 prev = cx_linked_list_prev(*begin, loc_next, node);
178 }
180 // update next pointer of prev node, or set begin
181 if (prev == NULL) {
182 if (begin != NULL) {
183 *begin = next;
184 }
185 } else {
186 ll_next(prev) = next;
187 }
189 // update prev pointer of next node, or set end
190 if (next == NULL) {
191 if (end != NULL) {
192 *end = prev;
193 }
194 } else if (loc_prev >= 0) {
195 ll_prev(next) = prev;
196 }
197 }
199 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
200 assert(loc_next >= 0);
201 size_t size = 0;
202 while (node != NULL) {
203 node = ll_next(node);
204 size++;
205 }
206 return size;
207 }
209 static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next,
210 ptrdiff_t loc_data, int follow_ptr,
211 size_t length, void *ls, void *le, void *re,
212 CxListComparator cmp_func) {
213 const size_t sbo_len = 1024;
214 void *sbo[sbo_len];
215 void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
216 void *rc, *lc;
218 lc = ls;
219 rc = le;
220 size_t n = 0;
221 while (lc && lc != le && rc != re) {
222 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
223 sorted[n] = lc;
224 lc = ll_next(lc);
225 } else {
226 sorted[n] = rc;
227 rc = ll_next(rc);
228 }
229 n++;
230 }
231 while (lc && lc != le) {
232 sorted[n] = lc;
233 lc = ll_next(lc);
234 n++;
235 }
236 while (rc && rc != re) {
237 sorted[n] = rc;
238 rc = ll_next(rc);
239 n++;
240 }
242 // Update pointer
243 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
244 for (size_t i = 0; i < length - 1; i++) {
245 ll_next(sorted[i]) = sorted[i + 1];
246 if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i];
247 }
248 ll_next(sorted[length - 1]) = NULL;
250 void *ret = sorted[0];
251 if (sorted != sbo) {
252 free(sorted);
253 }
254 return ret;
255 }
257 void cx_linked_list_sort( /* NOLINT(misc-no-recursion) - purposely recursive function */
258 void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
259 ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
260 assert(begin != NULL);
261 assert(loc_next >= 0);
262 assert(loc_data >= 0);
263 assert(cmp_func);
265 void *lc, *ls, *le, *re;
267 // set start node
268 ls = *begin;
270 // check how many elements are already sorted
271 lc = ls;
272 size_t ln = 1;
273 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
274 lc = ll_next(lc);
275 ln++;
276 }
277 le = ll_next(lc);
279 // if first unsorted node is NULL, the list is already completely sorted
280 if (le != NULL) {
281 void *rc;
282 size_t rn = 1;
283 rc = le;
284 // skip already sorted elements
285 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
286 rc = ll_next(rc);
287 rn++;
288 }
289 re = ll_next(rc);
291 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
292 void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
293 ln + rn, ls, le, re, cmp_func);
295 // Something left? Sort it!
296 size_t remainder_length = cx_linked_list_size(re, loc_next);
297 if (remainder_length > 0) {
298 void *remainder = re;
299 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func);
301 // merge sorted list with (also sorted) remainder
302 *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
303 ln + rn + remainder_length,
304 sorted, remainder, NULL, cmp_func);
305 } else {
306 // no remainder - we've got our sorted list
307 *begin = sorted;
308 }
309 if (end) *end = cx_linked_list_last(sorted, loc_next);
310 }
311 }
313 void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) {
314 assert(begin != NULL);
315 assert(loc_next >= 0);
317 // swap all links
318 void *prev = NULL;
319 void *cur = *begin;
320 while (cur != NULL) {
321 void *next = ll_next(cur);
323 ll_next(cur) = prev;
324 if (loc_prev >= 0) {
325 ll_prev(cur) = next;
326 }
328 prev = cur;
329 cur = next;
330 }
332 // update begin and end
333 if (end != NULL) {
334 *end = *begin;
335 }
336 *begin = prev;
337 }
339 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
341 typedef struct cx_linked_list_node cx_linked_list_node;
342 struct cx_linked_list_node {
343 cx_linked_list_node *prev;
344 cx_linked_list_node *next;
345 char payload[];
346 };
348 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
349 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
350 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
352 typedef struct {
353 cx_list_s base;
354 cx_linked_list_node *begin;
355 cx_linked_list_node *end;
356 } cx_linked_list;
358 static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) {
359 if (index >= list->base.size) {
360 return NULL;
361 } else if (index > list->base.size / 2) {
362 return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
363 } else {
364 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
365 }
366 }
368 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
369 // out-of bounds check
370 if (index > list->size) return 1;
372 // cast a linked list pointer
373 cx_linked_list *ll = (cx_linked_list *) list;
375 // create the new node
376 cx_linked_list_node *node = cxMalloc(list->allocator,
377 sizeof(cx_linked_list_node) + list->itemsize);
379 // sortir if failed
380 if (node == NULL) return 1;
382 // copy payload to the new node
383 memcpy(node->payload, elem, list->itemsize);
385 // check if this is the first node
386 if (ll->begin == NULL) {
387 node->prev = node->next = NULL;
388 ll->begin = ll->end = node;
389 } else {
390 // check if this shall be the new end node
391 if (index == list->size) {
392 ll->end->next = node;
393 node->prev = ll->end;
394 node->next = NULL;
395 ll->end = node;
396 }
397 // check if this shall be the new start node
398 else if (index == 0) {
399 ll->begin->prev = node;
400 node->next = ll->begin;
401 node->prev = NULL;
402 ll->begin = node;
403 } else {
404 // find the node at the current index
405 cx_linked_list_node *cur = cx_ll_node_at(ll, index);
407 // insert before that node
408 // (we know all ptr are non-null because we handled all other cases before)
409 node->next = cur;
410 node->prev = cur->prev;
411 cur->prev = node;
412 node->prev->next = node;
413 }
414 }
416 // increase the size and return
417 list->size++;
418 return 0;
419 }
421 static int cx_ll_add(cx_list_s *list, void *elem) {
422 return cx_ll_insert(list, list->size, elem);
423 }
425 static int cx_pll_insert(cx_list_s *list, size_t index, void *elem) {
426 return cx_ll_insert(list, index, &elem);
427 }
429 static int cx_pll_add(cx_list_s *list, void *elem) {
430 return cx_ll_insert(list, list->size, &elem);
431 }
433 static int cx_ll_remove(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);
437 // out-of-bounds check
438 if (node == NULL) return 1;
440 // remove
441 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
442 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
444 // adjust size
445 list->size--;
447 // free and return
448 cxFree(list->allocator, node);
450 return 0;
451 }
453 static void *cx_ll_at(cx_list_s *list, size_t index) {
454 cx_linked_list *ll = (cx_linked_list *) list;
455 cx_linked_list_node *node = cx_ll_node_at(ll, index);
456 return node == NULL ? NULL : node->payload;
457 }
459 static void *cx_pll_at(cx_list_s *list, size_t index) {
460 cx_linked_list *ll = (cx_linked_list *) list;
461 cx_linked_list_node *node = cx_ll_node_at(ll, index);
462 return node == NULL ? NULL : *(void **) node->payload;
463 }
465 static size_t cx_ll_find(cx_list_s *list, void *elem) {
466 return cx_linked_list_find(((cx_linked_list *) list)->begin,
467 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
468 0, list->cmpfunc, elem);
469 }
471 static size_t cx_pll_find(cx_list_s *list, void *elem) {
472 return cx_linked_list_find(((cx_linked_list *) list)->begin,
473 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
474 1, list->cmpfunc, elem);
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 }
