Sun, 03 Oct 2021 14:06:57 +0200
add some documentation and changes some signatures
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, void **end, ptrdiff_t loc_next) {
49 if (end != NULL) {
50 return *end;
51 } else {
52 if (begin == NULL || *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 }
63 }
65 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
66 void *last = cx_linked_list_last(begin, end, loc_next);
67 if (last == NULL) {
68 assert(begin != NULL);
69 *begin = new_node;
70 } else {
71 // if there is a last node, update its next pointer
72 void **next = CX_LL_PTR(last, loc_next);
73 *next = new_node;
74 }
76 // if there is an end pointer, update it
77 if (end != NULL) {
78 *end = cx_linked_list_last(&new_node, NULL, loc_next);
79 }
81 // if the nodes use a prev pointer, update it
82 if (loc_prev >= 0) {
83 void **prev = CX_LL_PTR(new_node, loc_prev);
84 *prev = last;
85 }
86 }
88 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
90 typedef struct cx_linked_list_node cx_linked_list_node;
91 struct cx_linked_list_node {
92 cx_linked_list_node *prev;
93 cx_linked_list_node *next;
94 char payload[];
95 };
97 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
98 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
100 typedef struct {
101 cx_list_s base;
102 cx_linked_list_node *begin;
103 cx_linked_list_node *end;
104 } cx_linked_list;
106 static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) {
107 if (index >= list->base.size) {
108 return NULL;
109 } else if (index > list->base.size / 2) {
110 return cx_linked_list_at(list->end, list->base.size, CX_LL_LOC_PREV, index);
111 } else {
112 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
113 }
114 }
116 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
117 // out-of bounds check
118 if (index > list->size) return 1;
120 // cast a linked list pointer
121 cx_linked_list *ll = (cx_linked_list *) list;
123 // create the new node
124 cx_linked_list_node *node = cxMalloc(list->allocator,
125 sizeof(cx_linked_list_node) + list->itemsize);
127 // sortir if failed
128 if (node == NULL) return 1;
130 // copy payload to the new node
131 memcpy(node->payload, elem, list->itemsize);
133 // check if this is the first node
134 if (ll->begin == NULL) {
135 node->prev = node->next = NULL;
136 ll->begin = ll->end = node;
137 } else {
138 // check if this shall be the new end node
139 if (index == list->size) {
140 ll->end->next = node;
141 node->prev = ll->end;
142 node->next = NULL;
143 ll->end = node;
144 }
145 // check if this shall be the new start node
146 else if (index == 0) {
147 ll->begin->prev = node;
148 node->next = ll->begin;
149 node->prev = NULL;
150 ll->begin = node;
151 } else {
152 // find the node at the current index
153 cx_linked_list_node *cur = cx_ll_node_at(ll, index);
155 // insert before that node
156 // (we know all ptr are non-null because we handled all other cases before)
157 node->next = cur;
158 node->prev = cur->prev;
159 cur->prev = node;
160 node->prev->next = node;
161 }
162 }
164 // increase the size and return
165 list->size++;
166 return 0;
167 }
169 static int cx_ll_add(cx_list_s *list, void *elem) {
170 return cx_ll_insert(list, list->size, elem);
171 }
173 static int cx_ll_remove(cx_list_s *list, size_t index) {
174 cx_linked_list *ll = (cx_linked_list *) list;
175 cx_linked_list_node *node = cx_ll_node_at(ll, index);
177 // out-of-bounds check
178 if (node == NULL) return 1;
180 // change left side connection
181 if (node->prev == NULL) {
182 ll->begin = node->next;
183 } else {
184 node->prev->next = node->next;
185 }
187 // change right side connection
188 if (node->next == NULL) {
189 ll->end = node->prev;
190 } else {
191 node->next->prev = node->prev;
192 }
194 // adjust size
195 list->size--;
197 // free and return
198 cxFree(list->allocator, node);
200 return 0;
201 }
203 static void *cx_ll_at(cx_list_s *list, size_t index) {
204 cx_linked_list *ll = (cx_linked_list *) list;
205 cx_linked_list_node *node = cx_ll_node_at(ll, index);
206 return node == NULL ? NULL : &node->payload;
207 }
209 static size_t cx_ll_find(cx_list_s *list, void *elem) {
210 CxListComparator cmp = list->cmpfunc;
211 cx_linked_list *ll = (cx_linked_list *) list;
213 size_t index;
214 cx_linked_list_node *node = ll->begin;
215 for (index = 0; index < list->size; index++) {
216 void *current = node->payload;
217 if (cmp(current, elem) == 0) {
218 return index;
219 }
220 node = node->next;
221 }
222 return index;
223 }
225 static void *cx_ll_last(cx_list_s *list) {
226 cx_linked_list *ll = (cx_linked_list *) list;
227 cx_linked_list_node *last = cx_linked_list_last(NULL, (void **) &ll->end, CX_LL_LOC_NEXT);
228 return &last->payload;
229 }
231 static cx_list_class cx_linked_list_class = {
232 cx_ll_add,
233 cx_ll_insert,
234 cx_ll_remove,
235 cx_ll_at,
236 cx_ll_find,
237 cx_ll_last
238 };
240 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {
241 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
242 if (list == NULL)
243 return NULL;
245 list->base.cl = &cx_linked_list_class;
246 list->base.allocator = allocator;
247 list->base.cmpfunc = comparator;
248 list->base.itemsize = item_size;
249 list->base.capacity = SIZE_MAX;
250 list->base.size = 0;
252 list->begin = NULL;
253 list->end = NULL;
255 return (CxList) list;
256 }
258 void cxLinkedListDestroy(CxList list) {
259 cx_linked_list *ll = (cx_linked_list *) list;
261 cx_linked_list_node *node = ll->begin;
262 while (node) {
263 void *next = node->next;
264 cxFree(list->allocator, node);
265 node = next;
266 }
268 cxFree(list->allocator, list);
269 }
271 size_t cxLinkedListRecalculateSize(CxList list) {
272 cx_linked_list *ll = (cx_linked_list *) list;
274 if (ll->begin == NULL) {
275 ll->base.size = 0;
276 ll->end = NULL;
277 return 0;
278 } else {
279 cx_linked_list_node *cur = ll->begin;
280 cx_linked_list_node *last;
281 size_t size = 0;
282 do {
283 last = cur;
284 size++;
285 } while ((cur = cur->next) != NULL);
286 ll->end = last;
287 ll->base.size = size;
288 return size;
289 }
290 }