src/linked_list.c@0458bff0b1cd
src/linked_list.c
Wed, 06 Oct 2021 14:10:19 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Wed, 06 Oct 2021 14:10:19 +0200
- changeset 469
- 0458bff0b1cd
- parent 468
- 75ae1dccd101
- child 473
- 1bd4b8c28722
- permissions
- -rw-r--r--
add high level list sort and inlines method invocation functions
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 size_t i = start_index;
40 void *cur = start;
41 while (i != index && cur != NULL) {
42 cur = CX_LL_PTR(cur, loc_advance);
43 i < index ? i++ : i--;
44 }
45 return cur;
46 }
48 void *cx_linked_list_last(void *begin, ptrdiff_t loc_next) {
49 if (begin == NULL)
50 return NULL;
52 void *cur = begin;
53 void *last;
54 do {
55 last = cur;
56 } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL);
58 return last;
59 }
61 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
62 void *last;
63 if (end == NULL) {
64 assert(begin != NULL);
65 last = cx_linked_list_last(*begin, loc_next);
66 } else {
67 last = *end;
68 }
69 if (last == NULL) {
70 assert(begin != NULL);
71 *begin = new_node;
72 } else {
73 // if there is a last node, update its next pointer
74 CX_LL_PTR(last, loc_next) = new_node;
75 }
77 // if there is an end pointer, update it
78 if (end != NULL) {
79 *end = cx_linked_list_last(new_node, loc_next);
80 }
82 // if the nodes use a prev pointer, update it
83 if (loc_prev >= 0) {
84 CX_LL_PTR(new_node, loc_prev) = last;
85 }
86 }
88 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
89 size_t size = 0;
90 while (node != NULL) {
91 node = CX_LL_PTR(node, loc_next);
92 size++;
93 }
94 return size;
95 }
97 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
98 #define ll_next(node) CX_LL_PTR(node, loc_next)
99 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
101 static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next,
102 ptrdiff_t loc_data, int follow_ptr,
103 size_t length, void *ls, void *le, void *re,
104 CxListComparator cmp_func) {
105 const size_t sbo_len = 1024;
106 void *sbo[sbo_len];
107 void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
108 void *rc, *lc;
110 lc = ls;
111 rc = le;
112 size_t n = 0;
113 while (lc && lc != le && rc != re) {
114 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
115 sorted[n] = lc;
116 lc = ll_next(lc);
117 } else {
118 sorted[n] = rc;
119 rc = ll_next(rc);
120 }
121 n++;
122 }
123 while (lc && lc != le) {
124 sorted[n] = lc;
125 lc = ll_next(lc);
126 n++;
127 }
128 while (rc && rc != re) {
129 sorted[n] = rc;
130 rc = ll_next(rc);
131 n++;
132 }
134 // Update pointer
135 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
136 for (size_t i = 0; i < length - 1; i++) {
137 ll_next(sorted[i]) = sorted[i + 1];
138 if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i];
139 }
140 ll_next(sorted[length - 1]) = NULL;
142 void *ret = sorted[0];
143 if (sorted != sbo) {
144 free(sorted);
145 }
146 return ret;
147 }
149 void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
150 ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
151 assert(begin != NULL);
153 void *lc, *ls, *le, *re;
155 // set start node
156 ls = *begin;
158 // check how many elements are already sorted
159 lc = ls;
160 size_t ln = 1;
161 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
162 lc = ll_next(lc);
163 ln++;
164 }
165 le = ll_next(lc);
167 // if first unsorted node is NULL, the list is already completely sorted
168 if (le != NULL) {
169 void *rc;
170 size_t rn = 1;
171 rc = le;
172 // skip already sorted elements
173 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
174 rc = ll_next(rc);
175 rn++;
176 }
177 re = ll_next(rc);
179 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
180 void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
181 ln + rn, ls, le, re, cmp_func);
183 // Something left? Sort it!
184 size_t remainder_length = cx_linked_list_size(re, loc_next);
185 if (remainder_length > 0) {
186 void *remainder = re;
187 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func);
189 // merge sorted list with (also sorted) remainder
190 *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
191 ln + rn + remainder_length,
192 sorted, remainder, NULL, cmp_func);
193 } else {
194 // no remainder - we've got our sorted list
195 *begin = sorted;
196 }
197 if (end) *end = cx_linked_list_last(sorted, loc_next);
198 }
199 }
201 #undef ll_next
202 #undef ll_data
204 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
206 typedef struct cx_linked_list_node cx_linked_list_node;
207 struct cx_linked_list_node {
208 cx_linked_list_node *prev;
209 cx_linked_list_node *next;
210 char payload[];
211 };
213 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
214 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
215 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
217 typedef struct {
218 cx_list_s base;
219 cx_linked_list_node *begin;
220 cx_linked_list_node *end;
221 } cx_linked_list;
223 static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) {
224 if (index >= list->base.size) {
225 return NULL;
226 } else if (index > list->base.size / 2) {
227 return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
228 } else {
229 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
230 }
231 }
233 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
234 // out-of bounds check
235 if (index > list->size) return 1;
237 // cast a linked list pointer
238 cx_linked_list *ll = (cx_linked_list *) list;
240 // create the new node
241 cx_linked_list_node *node = cxMalloc(list->allocator,
242 sizeof(cx_linked_list_node) + list->itemsize);
244 // sortir if failed
245 if (node == NULL) return 1;
247 // copy payload to the new node
248 memcpy(node->payload, elem, list->itemsize);
250 // check if this is the first node
251 if (ll->begin == NULL) {
252 node->prev = node->next = NULL;
253 ll->begin = ll->end = node;
254 } else {
255 // check if this shall be the new end node
256 if (index == list->size) {
257 ll->end->next = node;
258 node->prev = ll->end;
259 node->next = NULL;
260 ll->end = node;
261 }
262 // check if this shall be the new start node
263 else if (index == 0) {
264 ll->begin->prev = node;
265 node->next = ll->begin;
266 node->prev = NULL;
267 ll->begin = node;
268 } else {
269 // find the node at the current index
270 cx_linked_list_node *cur = cx_ll_node_at(ll, index);
272 // insert before that node
273 // (we know all ptr are non-null because we handled all other cases before)
274 node->next = cur;
275 node->prev = cur->prev;
276 cur->prev = node;
277 node->prev->next = node;
278 }
279 }
281 // increase the size and return
282 list->size++;
283 return 0;
284 }
286 static int cx_ll_add(cx_list_s *list, void *elem) {
287 return cx_ll_insert(list, list->size, elem);
288 }
290 static int cx_pll_insert(cx_list_s *list, size_t index, void *elem) {
291 return cx_ll_insert(list, index, &elem);
292 }
294 static int cx_pll_add(cx_list_s *list, void *elem) {
295 return cx_ll_insert(list, list->size, &elem);
296 }
298 static int cx_ll_remove(cx_list_s *list, size_t index) {
299 cx_linked_list *ll = (cx_linked_list *) list;
300 cx_linked_list_node *node = cx_ll_node_at(ll, index);
302 // out-of-bounds check
303 if (node == NULL) return 1;
305 // change left side connection
306 if (node->prev == NULL) {
307 ll->begin = node->next;
308 } else {
309 node->prev->next = node->next;
310 }
312 // change right side connection
313 if (node->next == NULL) {
314 ll->end = node->prev;
315 } else {
316 node->next->prev = node->prev;
317 }
319 // adjust size
320 list->size--;
322 // free and return
323 cxFree(list->allocator, node);
325 return 0;
326 }
328 static void *cx_ll_at(cx_list_s *list, size_t index) {
329 cx_linked_list *ll = (cx_linked_list *) list;
330 cx_linked_list_node *node = cx_ll_node_at(ll, index);
331 return node == NULL ? NULL : node->payload;
332 }
334 static void *cx_pll_at(cx_list_s *list, size_t index) {
335 cx_linked_list *ll = (cx_linked_list *) list;
336 cx_linked_list_node *node = cx_ll_node_at(ll, index);
337 return node == NULL ? NULL : *(void **) node->payload;
338 }
340 static size_t cx_ll_find(cx_list_s *list, void *elem) {
341 CxListComparator cmp = list->cmpfunc;
342 cx_linked_list *ll = (cx_linked_list *) list;
344 size_t index;
345 cx_linked_list_node *node = ll->begin;
346 for (index = 0; index < list->size; index++) {
347 void *current = node->payload;
348 if (cmp(current, elem) == 0) {
349 return index;
350 }
351 node = node->next;
352 }
353 return index;
354 }
356 static size_t cx_pll_find(cx_list_s *list, void *elem) {
357 CxListComparator cmp = list->cmpfunc;
358 cx_linked_list *ll = (cx_linked_list *) list;
360 size_t index;
361 cx_linked_list_node *node = ll->begin;
362 for (index = 0; index < list->size; index++) {
363 void *current = *(void **) node->payload;
364 if (cmp(current, elem) == 0) {
365 return index;
366 }
367 node = node->next;
368 }
369 return index;
370 }
372 static void *cx_ll_last(cx_list_s *list) {
373 cx_linked_list *ll = (cx_linked_list *) list;
374 cx_linked_list_node *last = ll->end;
375 return last == NULL ? NULL : last->payload;
376 }
378 static void *cx_pll_last(cx_list_s *list) {
379 cx_linked_list *ll = (cx_linked_list *) list;
380 cx_linked_list_node *last = ll->end;
381 return last == NULL ? NULL : *(void **) last->payload;
382 }
384 static void cx_ll_sort(cx_list_s *list) {
385 cx_linked_list *ll = (cx_linked_list *) list;
386 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
387 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
388 0, list->cmpfunc);
389 }
391 static void cx_pll_sort(cx_list_s *list) {
392 cx_linked_list *ll = (cx_linked_list *) list;
393 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
394 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
395 1, list->cmpfunc);
396 }
398 static cx_list_class cx_linked_list_class = {
399 cx_ll_add,
400 cx_ll_insert,
401 cx_ll_remove,
402 cx_ll_at,
403 cx_ll_find,
404 cx_ll_last,
405 cx_ll_sort
406 };
408 static cx_list_class cx_pointer_linked_list_class = {
409 cx_pll_add,
410 cx_pll_insert,
411 cx_ll_remove,
412 cx_pll_at,
413 cx_pll_find,
414 cx_pll_last,
415 cx_pll_sort
416 };
418 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {
419 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
420 if (list == NULL)
421 return NULL;
423 list->base.cl = &cx_linked_list_class;
424 list->base.allocator = allocator;
425 list->base.cmpfunc = comparator;
426 list->base.itemsize = item_size;
427 list->base.capacity = SIZE_MAX;
428 list->base.size = 0;
430 list->begin = NULL;
431 list->end = NULL;
433 return (CxList) list;
434 }
436 CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator) {
437 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
438 if (list == NULL)
439 return NULL;
441 list->base.cl = &cx_pointer_linked_list_class;
442 list->base.allocator = allocator;
443 list->base.cmpfunc = comparator;
444 list->base.itemsize = sizeof(void *);
445 list->base.capacity = SIZE_MAX;
446 list->base.size = 0;
448 list->begin = NULL;
449 list->end = NULL;
451 return (CxList) list;
452 }
454 void cxLinkedListDestroy(CxList list) {
455 cx_linked_list *ll = (cx_linked_list *) list;
457 cx_linked_list_node *node = ll->begin;
458 while (node) {
459 void *next = node->next;
460 cxFree(list->allocator, node);
461 node = next;
462 }
464 cxFree(list->allocator, list);
465 }
