Sun, 03 Oct 2021 13:07:48 +0200
add __alloc_size__ attribute
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>
33 /* LOW LEVEL LINKED LIST FUNCTIONS */
35 #define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off))
37 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
38 size_t i = start_index;
39 void *cur = start;
40 while (i != index && cur != NULL) {
41 cur = *CX_LL_PTR(cur, loc_advance);
42 i < index ? i++ : i--;
43 }
44 return cur;
45 }
47 void *cx_linked_list_last(void **begin, void **end, ptrdiff_t loc_next) {
48 if (end != NULL) {
49 return *end;
50 } else {
51 if (begin == NULL || *begin == NULL)
52 return NULL;
54 void *cur = *begin;
55 void *last;
56 do {
57 last = cur;
58 } while ((cur = *CX_LL_PTR(cur, loc_next)) != NULL);
60 return last;
61 }
62 }
64 int cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
65 void *last = cx_linked_list_last(begin, end, loc_next);
66 if (last == NULL) {
67 if (begin == NULL) {
68 // no current list and no begin ptr to write to - we don't find something to append to
69 return 1;
70 } else {
71 // start fresh list
72 *begin = new_node;
73 }
74 } else {
75 // if there is a last node, update its next pointer
76 void **next = CX_LL_PTR(last, loc_next);
77 *next = new_node;
78 }
80 // if there is an end pointer, update it
81 if (end != NULL) {
82 *end = cx_linked_list_last(&new_node, NULL, loc_next);
83 }
85 // if the nodes use a prev pointer, update it
86 if (loc_prev >= 0) {
87 void **prev = CX_LL_PTR(new_node, loc_prev);
88 *prev = last;
89 }
91 return 0;
92 }
94 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
96 typedef struct cx_linked_list_node cx_linked_list_node;
97 struct cx_linked_list_node {
98 cx_linked_list_node *prev;
99 cx_linked_list_node *next;
100 char payload[];
101 };
103 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
104 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
106 typedef struct {
107 cx_list_s base;
108 cx_linked_list_node *begin;
109 cx_linked_list_node *end;
110 } cx_linked_list;
112 static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) {
113 if (index >= list->base.size) {
114 return NULL;
115 } else if (index > list->base.size / 2) {
116 return cx_linked_list_at(list->end, list->base.size, CX_LL_LOC_PREV, index);
117 } else {
118 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
119 }
120 }
122 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
123 // out-of bounds check
124 if (index > list->size) return 1;
126 // cast a linked list pointer
127 cx_linked_list *ll = (cx_linked_list *) list;
129 // create the new node
130 cx_linked_list_node *node = cxMalloc(list->allocator,
131 sizeof(cx_linked_list_node) + list->itemsize);
133 // sortir if failed
134 if (node == NULL) return 1;
136 // copy payload to the new node
137 memcpy(node->payload, elem, list->itemsize);
139 // check if this is the first node
140 if (ll->begin == NULL) {
141 node->prev = node->next = NULL;
142 ll->begin = ll->end = node;
143 } else {
144 // check if this shall be the new end node
145 if (index == list->size) {
146 ll->end->next = node;
147 node->prev = ll->end;
148 node->next = NULL;
149 ll->end = node;
150 }
151 // check if this shall be the new start node
152 else if (index == 0) {
153 ll->begin->prev = node;
154 node->next = ll->begin;
155 node->prev = NULL;
156 ll->begin = node;
157 } else {
158 // find the node at the current index
159 cx_linked_list_node *cur = cx_ll_node_at(ll, index);
161 // insert before that node
162 // (we know all ptr are non-null because we handled all other cases before)
163 node->next = cur;
164 node->prev = cur->prev;
165 cur->prev = node;
166 node->prev->next = node;
167 }
168 }
170 // increase the size and return
171 list->size++;
172 return 0;
173 }
175 static int cx_ll_add(cx_list_s *list, void *elem) {
176 return cx_ll_insert(list, list->size, elem);
177 }
179 static int cx_ll_remove(cx_list_s *list, size_t index) {
180 cx_linked_list *ll = (cx_linked_list *) list;
181 cx_linked_list_node *node = cx_ll_node_at(ll, index);
183 // out-of-bounds check
184 if (node == NULL) return 1;
186 // change left side connection
187 if (node->prev == NULL) {
188 ll->begin = node->next;
189 } else {
190 node->prev->next = node->next;
191 }
193 // change right side connection
194 if (node->next == NULL) {
195 ll->end = node->prev;
196 } else {
197 node->next->prev = node->prev;
198 }
200 // adjust size
201 list->size--;
203 // free and return
204 cxFree(list->allocator, node);
206 return 0;
207 }
209 static void *cx_ll_at(cx_list_s *list, size_t index) {
210 cx_linked_list *ll = (cx_linked_list *) list;
211 cx_linked_list_node *node = cx_ll_node_at(ll, index);
212 return node == NULL ? NULL : &node->payload;
213 }
215 static size_t cx_ll_find(cx_list_s *list, void *elem) {
216 CxListComparator cmp = list->cmpfunc;
217 cx_linked_list *ll = (cx_linked_list *) list;
219 size_t index;
220 cx_linked_list_node *node = ll->begin;
221 for (index = 0; index < list->size; index++) {
222 void *current = node->payload;
223 if (cmp(current, elem) == 0) {
224 return index;
225 }
226 node = node->next;
227 }
228 return index;
229 }
231 static void *cx_ll_last(cx_list_s *list) {
232 cx_linked_list *ll = (cx_linked_list *) list;
233 cx_linked_list_node *last = cx_linked_list_last(NULL, (void **) &ll->end, CX_LL_LOC_NEXT);
234 return &last->payload;
235 }
237 static cx_list_class cx_linked_list_class = {
238 cx_ll_add,
239 cx_ll_insert,
240 cx_ll_remove,
241 cx_ll_at,
242 cx_ll_find,
243 cx_ll_last
244 };
246 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {
247 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
248 if (list == NULL)
249 return NULL;
251 list->base.cl = &cx_linked_list_class;
252 list->base.allocator = allocator;
253 list->base.cmpfunc = comparator;
254 list->base.itemsize = item_size;
255 list->base.capacity = SIZE_MAX;
256 list->base.size = 0;
258 list->begin = NULL;
259 list->end = NULL;
261 return (CxList) list;
262 }
264 void cxLinkedListDestroy(CxList list) {
265 cx_linked_list *ll = (cx_linked_list *) list;
267 cx_linked_list_node *node = ll->begin;
268 while (node) {
269 void *next = node->next;
270 cxFree(list->allocator, node);
271 node = next;
272 }
274 cxFree(list->allocator, list);
275 }
277 size_t cxLinkedListRecalculateSize(CxList list) {
278 cx_linked_list *ll = (cx_linked_list *) list;
280 if (ll->begin == NULL) {
281 ll->base.size = 0;
282 ll->end = NULL;
283 return 0;
284 } else {
285 cx_linked_list_node *cur = ll->begin;
286 cx_linked_list_node *last;
287 size_t size = 0;
288 do {
289 last = cur;
290 size++;
291 } while ((cur = cur->next) != NULL);
292 ll->end = last;
293 ll->base.size = size;
294 return size;
295 }
296 }