src/linked_list.c@31bf97fdbf71
src/linked_list.c
Sat, 04 Dec 2021 17:38:23 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Sat, 04 Dec 2021 17:38:23 +0100
- changeset 475
- 31bf97fdbf71
- parent 474
- 9c1fccda16bc
- child 476
- 60ff4561dc04
- permissions
- -rw-r--r--
add cx_linked_list_first() + cx_linked_list_prepend()
removes concatenating behavior of cx_linked_list_add()
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 links of adjacent nodes
154 if (prev != NULL) {
155 CX_LL_PTR(prev, loc_next) = next;
156 }
157 if (next != NULL && loc_prev >= 0) {
158 CX_LL_PTR(next, loc_prev) = prev;
159 }
161 // erase links of the target node
162 CX_LL_PTR(node, loc_next) = NULL;
163 if (loc_prev >= 0) {
164 CX_LL_PTR(node, loc_prev) = NULL;
165 }
167 // update begin, if required
168 if (*begin == node) {
169 *begin = next;
170 }
172 // update end, if required
173 if (end != NULL && *end == node) {
174 *end = prev;
175 }
177 return prev == NULL ? next : prev;
178 }
180 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
181 assert(loc_next >= 0);
182 size_t size = 0;
183 while (node != NULL) {
184 node = CX_LL_PTR(node, loc_next);
185 size++;
186 }
187 return size;
188 }
190 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
191 #define ll_next(node) CX_LL_PTR(node, loc_next)
192 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
194 static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next,
195 ptrdiff_t loc_data, int follow_ptr,
196 size_t length, void *ls, void *le, void *re,
197 CxListComparator cmp_func) {
198 const size_t sbo_len = 1024;
199 void *sbo[sbo_len];
200 void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
201 void *rc, *lc;
203 lc = ls;
204 rc = le;
205 size_t n = 0;
206 while (lc && lc != le && rc != re) {
207 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
208 sorted[n] = lc;
209 lc = ll_next(lc);
210 } else {
211 sorted[n] = rc;
212 rc = ll_next(rc);
213 }
214 n++;
215 }
216 while (lc && lc != le) {
217 sorted[n] = lc;
218 lc = ll_next(lc);
219 n++;
220 }
221 while (rc && rc != re) {
222 sorted[n] = rc;
223 rc = ll_next(rc);
224 n++;
225 }
227 // Update pointer
228 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
229 for (size_t i = 0; i < length - 1; i++) {
230 ll_next(sorted[i]) = sorted[i + 1];
231 if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i];
232 }
233 ll_next(sorted[length - 1]) = NULL;
235 void *ret = sorted[0];
236 if (sorted != sbo) {
237 free(sorted);
238 }
239 return ret;
240 }
242 void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
243 ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
244 assert(begin != NULL);
245 assert(loc_next >= 0);
246 assert(loc_data >= 0);
247 assert(cmp_func);
249 void *lc, *ls, *le, *re;
251 // set start node
252 ls = *begin;
254 // check how many elements are already sorted
255 lc = ls;
256 size_t ln = 1;
257 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
258 lc = ll_next(lc);
259 ln++;
260 }
261 le = ll_next(lc);
263 // if first unsorted node is NULL, the list is already completely sorted
264 if (le != NULL) {
265 void *rc;
266 size_t rn = 1;
267 rc = le;
268 // skip already sorted elements
269 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
270 rc = ll_next(rc);
271 rn++;
272 }
273 re = ll_next(rc);
275 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
276 void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
277 ln + rn, ls, le, re, cmp_func);
279 // Something left? Sort it!
280 size_t remainder_length = cx_linked_list_size(re, loc_next);
281 if (remainder_length > 0) {
282 void *remainder = re;
283 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func);
285 // merge sorted list with (also sorted) remainder
286 *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
287 ln + rn + remainder_length,
288 sorted, remainder, NULL, cmp_func);
289 } else {
290 // no remainder - we've got our sorted list
291 *begin = sorted;
292 }
293 if (end) *end = cx_linked_list_last(sorted, loc_next);
294 }
295 }
297 #undef ll_next
298 #undef ll_data
300 void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) {
301 assert(begin != NULL);
302 assert(loc_next >= 0);
304 // swap all links
305 void *prev = NULL;
306 void *cur = *begin;
307 while (cur != NULL) {
308 void *next = CX_LL_PTR(cur, loc_next);
310 CX_LL_PTR(cur, loc_next) = prev;
311 if (loc_prev >= 0) {
312 CX_LL_PTR(cur, loc_prev) = next;
313 }
315 prev = cur;
316 cur = next;
317 }
319 // update begin and end
320 if (end != NULL) {
321 *end = *begin;
322 }
323 *begin = prev;
324 }
326 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
328 typedef struct cx_linked_list_node cx_linked_list_node;
329 struct cx_linked_list_node {
330 cx_linked_list_node *prev;
331 cx_linked_list_node *next;
332 char payload[];
333 };
335 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
336 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
337 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
339 typedef struct {
340 cx_list_s base;
341 cx_linked_list_node *begin;
342 cx_linked_list_node *end;
343 } cx_linked_list;
345 static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) {
346 if (index >= list->base.size) {
347 return NULL;
348 } else if (index > list->base.size / 2) {
349 return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
350 } else {
351 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
352 }
353 }
355 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
356 // out-of bounds check
357 if (index > list->size) return 1;
359 // cast a linked list pointer
360 cx_linked_list *ll = (cx_linked_list *) list;
362 // create the new node
363 cx_linked_list_node *node = cxMalloc(list->allocator,
364 sizeof(cx_linked_list_node) + list->itemsize);
366 // sortir if failed
367 if (node == NULL) return 1;
369 // copy payload to the new node
370 memcpy(node->payload, elem, list->itemsize);
372 // check if this is the first node
373 if (ll->begin == NULL) {
374 node->prev = node->next = NULL;
375 ll->begin = ll->end = node;
376 } else {
377 // check if this shall be the new end node
378 if (index == list->size) {
379 ll->end->next = node;
380 node->prev = ll->end;
381 node->next = NULL;
382 ll->end = node;
383 }
384 // check if this shall be the new start node
385 else if (index == 0) {
386 ll->begin->prev = node;
387 node->next = ll->begin;
388 node->prev = NULL;
389 ll->begin = node;
390 } else {
391 // find the node at the current index
392 cx_linked_list_node *cur = cx_ll_node_at(ll, index);
394 // insert before that node
395 // (we know all ptr are non-null because we handled all other cases before)
396 node->next = cur;
397 node->prev = cur->prev;
398 cur->prev = node;
399 node->prev->next = node;
400 }
401 }
403 // increase the size and return
404 list->size++;
405 return 0;
406 }
408 static int cx_ll_add(cx_list_s *list, void *elem) {
409 return cx_ll_insert(list, list->size, elem);
410 }
412 static int cx_pll_insert(cx_list_s *list, size_t index, void *elem) {
413 return cx_ll_insert(list, index, &elem);
414 }
416 static int cx_pll_add(cx_list_s *list, void *elem) {
417 return cx_ll_insert(list, list->size, &elem);
418 }
420 static int cx_ll_remove(cx_list_s *list, size_t index) {
421 cx_linked_list *ll = (cx_linked_list *) list;
422 cx_linked_list_node *node = cx_ll_node_at(ll, index);
424 // out-of-bounds check
425 if (node == NULL) return 1;
427 // change left side connection
428 if (node->prev == NULL) {
429 ll->begin = node->next;
430 } else {
431 node->prev->next = node->next;
432 }
434 // change right side connection
435 if (node->next == NULL) {
436 ll->end = node->prev;
437 } else {
438 node->next->prev = node->prev;
439 }
441 // adjust size
442 list->size--;
444 // free and return
445 cxFree(list->allocator, node);
447 return 0;
448 }
450 static void *cx_ll_at(cx_list_s *list, size_t index) {
451 cx_linked_list *ll = (cx_linked_list *) list;
452 cx_linked_list_node *node = cx_ll_node_at(ll, index);
453 return node == NULL ? NULL : node->payload;
454 }
456 static void *cx_pll_at(cx_list_s *list, size_t index) {
457 cx_linked_list *ll = (cx_linked_list *) list;
458 cx_linked_list_node *node = cx_ll_node_at(ll, index);
459 return node == NULL ? NULL : *(void **) node->payload;
460 }
462 static size_t cx_ll_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 = node->payload;
470 if (cmp(current, elem) == 0) {
471 return index;
472 }
473 node = node->next;
474 }
475 return index;
476 }
478 static size_t cx_pll_find(cx_list_s *list, void *elem) {
479 CxListComparator cmp = list->cmpfunc;
480 cx_linked_list *ll = (cx_linked_list *) list;
482 size_t index;
483 cx_linked_list_node *node = ll->begin;
484 for (index = 0; index < list->size; index++) {
485 void *current = *(void **) node->payload;
486 if (cmp(current, elem) == 0) {
487 return index;
488 }
489 node = node->next;
490 }
491 return index;
492 }
494 static void cx_ll_sort(cx_list_s *list) {
495 cx_linked_list *ll = (cx_linked_list *) list;
496 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
497 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
498 0, list->cmpfunc);
499 }
501 static void cx_pll_sort(cx_list_s *list) {
502 cx_linked_list *ll = (cx_linked_list *) list;
503 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
504 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
505 1, list->cmpfunc);
506 }
508 static cx_list_class cx_linked_list_class = {
509 cx_ll_add,
510 cx_ll_insert,
511 cx_ll_remove,
512 cx_ll_at,
513 cx_ll_find,
514 cx_ll_sort
515 };
517 static cx_list_class cx_pointer_linked_list_class = {
518 cx_pll_add,
519 cx_pll_insert,
520 cx_ll_remove,
521 cx_pll_at,
522 cx_pll_find,
523 cx_pll_sort
524 };
526 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {
527 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
528 if (list == NULL)
529 return NULL;
531 list->base.cl = &cx_linked_list_class;
532 list->base.allocator = allocator;
533 list->base.cmpfunc = comparator;
534 list->base.itemsize = item_size;
535 list->base.capacity = SIZE_MAX;
536 list->base.size = 0;
538 list->begin = NULL;
539 list->end = NULL;
541 return (CxList) list;
542 }
544 CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator) {
545 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
546 if (list == NULL)
547 return NULL;
549 list->base.cl = &cx_pointer_linked_list_class;
550 list->base.allocator = allocator;
551 list->base.cmpfunc = comparator;
552 list->base.itemsize = sizeof(void *);
553 list->base.capacity = SIZE_MAX;
554 list->base.size = 0;
556 list->begin = NULL;
557 list->end = NULL;
559 return (CxList) list;
560 }
562 void cxLinkedListDestroy(CxList list) {
563 cx_linked_list *ll = (cx_linked_list *) list;
565 cx_linked_list_node *node = ll->begin;
566 while (node) {
567 void *next = node->next;
568 cxFree(list->allocator, node);
569 node = next;
570 }
572 cxFree(list->allocator, list);
573 }
