src/linked_list.c@1bd4b8c28722
src/linked_list.c
Fri, 08 Oct 2021 19:47:31 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Fri, 08 Oct 2021 19:47:31 +0200
- changeset 473
- 1bd4b8c28722
- parent 469
- 0458bff0b1cd
- child 474
- 9c1fccda16bc
- permissions
- -rw-r--r--
add cx_linked_list_{prev, remove, reverse}
changes assertions for some low level methods (loc_next is now always mandatory)
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_last(void *begin, ptrdiff_t loc_next) {
51 assert(loc_next >= 0);
52 if (begin == NULL)
53 return NULL;
55 void *cur = begin;
56 void *last;
57 do {
58 last = cur;
59 } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL);
61 return last;
62 }
64 void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node) {
65 assert(begin != NULL);
66 assert(loc_next >= 0);
67 if (begin == node) return NULL;
68 void *cur = begin;
69 void *next;
70 while (1) {
71 next = CX_LL_PTR(cur, loc_next);
72 if (next == node) return cur;
73 cur = next;
74 }
75 }
77 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
78 assert(loc_next >= 0);
79 void *last;
80 if (end == NULL) {
81 assert(begin != NULL);
82 last = cx_linked_list_last(*begin, loc_next);
83 } else {
84 last = *end;
85 }
86 if (last == NULL) {
87 assert(begin != NULL);
88 *begin = new_node;
89 } else {
90 // if there is a last node, update its next pointer
91 CX_LL_PTR(last, loc_next) = new_node;
92 }
94 // if there is an end pointer, update it
95 if (end != NULL) {
96 *end = cx_linked_list_last(new_node, loc_next);
97 }
99 // if the nodes use a prev pointer, update it
100 if (loc_prev >= 0) {
101 CX_LL_PTR(new_node, loc_prev) = last;
102 }
103 }
105 void *cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) {
106 assert(loc_next >= 0);
107 assert(loc_prev >= 0 || begin != NULL);
109 // find adjacent nodes
110 void *next = CX_LL_PTR(node, loc_next);
111 void *prev;
112 if (loc_prev >= 0) {
113 prev = CX_LL_PTR(node, loc_prev);
114 } else {
115 prev = cx_linked_list_prev(*begin, loc_next, node);
116 }
118 // update links of adjacent nodes
119 if (prev != NULL) {
120 CX_LL_PTR(prev, loc_next) = next;
121 }
122 if (next != NULL && loc_prev >= 0) {
123 CX_LL_PTR(next, loc_prev) = prev;
124 }
126 // erase links of the target node
127 CX_LL_PTR(node, loc_next) = NULL;
128 if (loc_prev >= 0) {
129 CX_LL_PTR(node, loc_prev) = NULL;
130 }
132 // update begin, if required
133 if (*begin == node) {
134 *begin = next;
135 }
137 // update end, if required
138 if (end != NULL && *end == node) {
139 *end = prev;
140 }
142 return prev == NULL ? next : prev;
143 }
145 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
146 assert(loc_next >= 0);
147 size_t size = 0;
148 while (node != NULL) {
149 node = CX_LL_PTR(node, loc_next);
150 size++;
151 }
152 return size;
153 }
155 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
156 #define ll_next(node) CX_LL_PTR(node, loc_next)
157 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
159 static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next,
160 ptrdiff_t loc_data, int follow_ptr,
161 size_t length, void *ls, void *le, void *re,
162 CxListComparator cmp_func) {
163 const size_t sbo_len = 1024;
164 void *sbo[sbo_len];
165 void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
166 void *rc, *lc;
168 lc = ls;
169 rc = le;
170 size_t n = 0;
171 while (lc && lc != le && rc != re) {
172 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
173 sorted[n] = lc;
174 lc = ll_next(lc);
175 } else {
176 sorted[n] = rc;
177 rc = ll_next(rc);
178 }
179 n++;
180 }
181 while (lc && lc != le) {
182 sorted[n] = lc;
183 lc = ll_next(lc);
184 n++;
185 }
186 while (rc && rc != re) {
187 sorted[n] = rc;
188 rc = ll_next(rc);
189 n++;
190 }
192 // Update pointer
193 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
194 for (size_t i = 0; i < length - 1; i++) {
195 ll_next(sorted[i]) = sorted[i + 1];
196 if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i];
197 }
198 ll_next(sorted[length - 1]) = NULL;
200 void *ret = sorted[0];
201 if (sorted != sbo) {
202 free(sorted);
203 }
204 return ret;
205 }
207 void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
208 ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
209 assert(begin != NULL);
210 assert(loc_next >= 0);
211 assert(loc_data >= 0);
212 assert(cmp_func);
214 void *lc, *ls, *le, *re;
216 // set start node
217 ls = *begin;
219 // check how many elements are already sorted
220 lc = ls;
221 size_t ln = 1;
222 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
223 lc = ll_next(lc);
224 ln++;
225 }
226 le = ll_next(lc);
228 // if first unsorted node is NULL, the list is already completely sorted
229 if (le != NULL) {
230 void *rc;
231 size_t rn = 1;
232 rc = le;
233 // skip already sorted elements
234 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
235 rc = ll_next(rc);
236 rn++;
237 }
238 re = ll_next(rc);
240 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
241 void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
242 ln + rn, ls, le, re, cmp_func);
244 // Something left? Sort it!
245 size_t remainder_length = cx_linked_list_size(re, loc_next);
246 if (remainder_length > 0) {
247 void *remainder = re;
248 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func);
250 // merge sorted list with (also sorted) remainder
251 *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
252 ln + rn + remainder_length,
253 sorted, remainder, NULL, cmp_func);
254 } else {
255 // no remainder - we've got our sorted list
256 *begin = sorted;
257 }
258 if (end) *end = cx_linked_list_last(sorted, loc_next);
259 }
260 }
262 #undef ll_next
263 #undef ll_data
265 void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) {
266 assert(begin != NULL);
267 assert(loc_next >= 0);
269 // swap all links
270 void *prev = NULL;
271 void *cur = *begin;
272 while (cur != NULL) {
273 void *next = CX_LL_PTR(cur, loc_next);
275 CX_LL_PTR(cur, loc_next) = prev;
276 if (loc_prev >= 0) {
277 CX_LL_PTR(cur, loc_prev) = next;
278 }
280 prev = cur;
281 cur = next;
282 }
284 // update begin and end
285 if (end != NULL) {
286 *end = *begin;
287 }
288 *begin = prev;
289 }
291 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
293 typedef struct cx_linked_list_node cx_linked_list_node;
294 struct cx_linked_list_node {
295 cx_linked_list_node *prev;
296 cx_linked_list_node *next;
297 char payload[];
298 };
300 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
301 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
302 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
304 typedef struct {
305 cx_list_s base;
306 cx_linked_list_node *begin;
307 cx_linked_list_node *end;
308 } cx_linked_list;
310 static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) {
311 if (index >= list->base.size) {
312 return NULL;
313 } else if (index > list->base.size / 2) {
314 return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
315 } else {
316 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
317 }
318 }
320 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
321 // out-of bounds check
322 if (index > list->size) return 1;
324 // cast a linked list pointer
325 cx_linked_list *ll = (cx_linked_list *) list;
327 // create the new node
328 cx_linked_list_node *node = cxMalloc(list->allocator,
329 sizeof(cx_linked_list_node) + list->itemsize);
331 // sortir if failed
332 if (node == NULL) return 1;
334 // copy payload to the new node
335 memcpy(node->payload, elem, list->itemsize);
337 // check if this is the first node
338 if (ll->begin == NULL) {
339 node->prev = node->next = NULL;
340 ll->begin = ll->end = node;
341 } else {
342 // check if this shall be the new end node
343 if (index == list->size) {
344 ll->end->next = node;
345 node->prev = ll->end;
346 node->next = NULL;
347 ll->end = node;
348 }
349 // check if this shall be the new start node
350 else if (index == 0) {
351 ll->begin->prev = node;
352 node->next = ll->begin;
353 node->prev = NULL;
354 ll->begin = node;
355 } else {
356 // find the node at the current index
357 cx_linked_list_node *cur = cx_ll_node_at(ll, index);
359 // insert before that node
360 // (we know all ptr are non-null because we handled all other cases before)
361 node->next = cur;
362 node->prev = cur->prev;
363 cur->prev = node;
364 node->prev->next = node;
365 }
366 }
368 // increase the size and return
369 list->size++;
370 return 0;
371 }
373 static int cx_ll_add(cx_list_s *list, void *elem) {
374 return cx_ll_insert(list, list->size, elem);
375 }
377 static int cx_pll_insert(cx_list_s *list, size_t index, void *elem) {
378 return cx_ll_insert(list, index, &elem);
379 }
381 static int cx_pll_add(cx_list_s *list, void *elem) {
382 return cx_ll_insert(list, list->size, &elem);
383 }
385 static int cx_ll_remove(cx_list_s *list, size_t index) {
386 cx_linked_list *ll = (cx_linked_list *) list;
387 cx_linked_list_node *node = cx_ll_node_at(ll, index);
389 // out-of-bounds check
390 if (node == NULL) return 1;
392 // change left side connection
393 if (node->prev == NULL) {
394 ll->begin = node->next;
395 } else {
396 node->prev->next = node->next;
397 }
399 // change right side connection
400 if (node->next == NULL) {
401 ll->end = node->prev;
402 } else {
403 node->next->prev = node->prev;
404 }
406 // adjust size
407 list->size--;
409 // free and return
410 cxFree(list->allocator, node);
412 return 0;
413 }
415 static void *cx_ll_at(cx_list_s *list, size_t index) {
416 cx_linked_list *ll = (cx_linked_list *) list;
417 cx_linked_list_node *node = cx_ll_node_at(ll, index);
418 return node == NULL ? NULL : node->payload;
419 }
421 static void *cx_pll_at(cx_list_s *list, size_t index) {
422 cx_linked_list *ll = (cx_linked_list *) list;
423 cx_linked_list_node *node = cx_ll_node_at(ll, index);
424 return node == NULL ? NULL : *(void **) node->payload;
425 }
427 static size_t cx_ll_find(cx_list_s *list, void *elem) {
428 CxListComparator cmp = list->cmpfunc;
429 cx_linked_list *ll = (cx_linked_list *) list;
431 size_t index;
432 cx_linked_list_node *node = ll->begin;
433 for (index = 0; index < list->size; index++) {
434 void *current = node->payload;
435 if (cmp(current, elem) == 0) {
436 return index;
437 }
438 node = node->next;
439 }
440 return index;
441 }
443 static size_t cx_pll_find(cx_list_s *list, void *elem) {
444 CxListComparator cmp = list->cmpfunc;
445 cx_linked_list *ll = (cx_linked_list *) list;
447 size_t index;
448 cx_linked_list_node *node = ll->begin;
449 for (index = 0; index < list->size; index++) {
450 void *current = *(void **) node->payload;
451 if (cmp(current, elem) == 0) {
452 return index;
453 }
454 node = node->next;
455 }
456 return index;
457 }
459 static void *cx_ll_last(cx_list_s *list) {
460 cx_linked_list *ll = (cx_linked_list *) list;
461 cx_linked_list_node *last = ll->end;
462 return last == NULL ? NULL : last->payload;
463 }
465 static void *cx_pll_last(cx_list_s *list) {
466 cx_linked_list *ll = (cx_linked_list *) list;
467 cx_linked_list_node *last = ll->end;
468 return last == NULL ? NULL : *(void **) last->payload;
469 }
471 static void cx_ll_sort(cx_list_s *list) {
472 cx_linked_list *ll = (cx_linked_list *) list;
473 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
474 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
475 0, list->cmpfunc);
476 }
478 static void cx_pll_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 1, list->cmpfunc);
483 }
485 static cx_list_class cx_linked_list_class = {
486 cx_ll_add,
487 cx_ll_insert,
488 cx_ll_remove,
489 cx_ll_at,
490 cx_ll_find,
491 cx_ll_last,
492 cx_ll_sort
493 };
495 static cx_list_class cx_pointer_linked_list_class = {
496 cx_pll_add,
497 cx_pll_insert,
498 cx_ll_remove,
499 cx_pll_at,
500 cx_pll_find,
501 cx_pll_last,
502 cx_pll_sort
503 };
505 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {
506 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
507 if (list == NULL)
508 return NULL;
510 list->base.cl = &cx_linked_list_class;
511 list->base.allocator = allocator;
512 list->base.cmpfunc = comparator;
513 list->base.itemsize = item_size;
514 list->base.capacity = SIZE_MAX;
515 list->base.size = 0;
517 list->begin = NULL;
518 list->end = NULL;
520 return (CxList) list;
521 }
523 CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator) {
524 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
525 if (list == NULL)
526 return NULL;
528 list->base.cl = &cx_pointer_linked_list_class;
529 list->base.allocator = allocator;
530 list->base.cmpfunc = comparator;
531 list->base.itemsize = sizeof(void *);
532 list->base.capacity = SIZE_MAX;
533 list->base.size = 0;
535 list->begin = NULL;
536 list->end = NULL;
538 return (CxList) list;
539 }
541 void cxLinkedListDestroy(CxList list) {
542 cx_linked_list *ll = (cx_linked_list *) list;
544 cx_linked_list_node *node = ll->begin;
545 while (node) {
546 void *next = node->next;
547 cxFree(list->allocator, node);
548 node = next;
549 }
551 cxFree(list->allocator, list);
552 }
