Mon, 27 Sep 2021 18:33:30 +0200
add function cx_linked_list_at()
This commit also makes glue functions static.
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 struct cx_linked_list_node {
97 void *prev;
98 void *next;
99 char payload[];
100 };
102 typedef struct {
103 cx_list_s base;
104 void *begin;
105 void *end;
106 ptrdiff_t loc_prev;
107 ptrdiff_t loc_next;
108 } cx_linked_list;
110 static int cx_ll_add(cx_list_s *list, void *elem) {
111 cx_linked_list *ll = (cx_linked_list *) list;
113 struct cx_linked_list_node *node = cxMalloc(list->allocator,
114 sizeof(struct cx_linked_list_node) + list->itemsize);
115 if (node == NULL)
116 return 1;
118 node->next = node->prev = NULL;
119 memcpy(node->payload, elem, list->itemsize);
121 int ret = cx_linked_list_add(
122 &ll->begin, &ll->end,
123 offsetof(struct cx_linked_list_node, prev),
124 offsetof(struct cx_linked_list_node, next),
125 node
126 );
127 if (ret == 0) {
128 list->size++;
129 return 0;
130 } else {
131 return ret;
132 }
133 }
135 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
136 cx_linked_list *ll = (cx_linked_list *) list;
137 // TODO: implement using low level API
138 return 1;
139 }
141 static int cx_ll_remove(cx_list_s *list, size_t index) {
142 if (index >= list->size) {
143 return 1;
144 }
145 cx_linked_list *ll = (cx_linked_list *) list;
146 // TODO: implement using low level API
147 return 0;
148 }
150 static size_t cx_ll_find(cx_list_s *list, void *elem) {
151 CxListComparator cmp = list->cmpfunc;
152 cx_linked_list *ll = (cx_linked_list *) list;
154 size_t index;
155 struct cx_linked_list_node* node = ll->begin;
156 for (index = 0 ; index < list->size ; index++) {
157 void* current = node->payload;
158 if (cmp(current, elem) == 0) {
159 return index;
160 }
161 node = node->next;
162 }
163 return index;
164 }
166 static void *cx_ll_last(cx_list_s *list) {
167 cx_linked_list *linkedList = (cx_linked_list *) list;
168 struct cx_linked_list_node *last = cx_linked_list_last(
169 NULL, &linkedList->end, offsetof(struct cx_linked_list_node, next));
170 return &last->payload;
171 }
173 cx_list_class cx_linked_list_class = {
174 cx_ll_add,
175 cx_ll_insert,
176 cx_ll_remove,
177 cx_ll_find,
178 cx_ll_last
179 };
181 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {
182 cx_linked_list* list = cxMalloc(allocator, sizeof(cx_linked_list));
183 if (list == NULL)
184 return NULL;
186 list->base.cl = &cx_linked_list_class;
187 list->base.allocator = allocator;
188 list->base.cmpfunc = comparator;
189 list->base.itemsize = item_size;
190 list->base.capacity = SIZE_MAX;
192 list->begin = NULL;
193 list->loc_prev = offsetof(struct cx_linked_list_node, prev);
194 list->loc_next = offsetof(struct cx_linked_list_node, next);
196 CxList result = (CxList) list;
197 cxLinkedListRecalculateSize(result);
198 return result;
199 }
201 void cxLinkedListDestroy(CxList list) {
202 cx_linked_list* ll = (cx_linked_list*) list;
204 struct cx_linked_list_node* node = ll->begin;
205 while (node) {
206 void* next = node->next;
207 cxFree(list->allocator, node);
208 node = next;
209 }
211 cxFree(list->allocator, list);
212 }
214 size_t cxLinkedListRecalculateSize(CxList list) {
215 cx_linked_list *ll = (cx_linked_list *) list;
217 if (ll->begin == NULL) {
218 ll->base.size = 0;
219 ll->end = NULL;
220 return 0;
221 } else {
222 void *cur = ll->begin;
223 void *last;
224 size_t size = 0;
225 do {
226 last = cur;
227 size++;
228 } while ((cur = *CX_LL_PTR(cur, ll->loc_next)) != NULL);
229 ll->end = last;
230 ll->base.size = size;
231 return size;
232 }
233 }