|
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 */ |
|
28 |
|
29 #include "cx/array_list.h" |
|
30 #include <assert.h> |
|
31 #include <string.h> |
|
32 #include <stdint.h> |
|
33 |
|
34 /* LOW LEVEL ARRAY LIST FUNCTIONS */ |
|
35 |
|
36 enum cx_array_copy_result cx_array_copy( |
|
37 void **target, |
|
38 size_t *size, |
|
39 size_t *capacity, |
|
40 size_t index, |
|
41 void const *src, |
|
42 size_t elem_size, |
|
43 size_t elem_count, |
|
44 struct cx_array_reallocator_s *reallocator |
|
45 ) { |
|
46 /* assert pointers */ |
|
47 assert(target != NULL); |
|
48 assert(size != NULL); |
|
49 assert(src != NULL); |
|
50 |
|
51 /* determine capacity */ |
|
52 size_t cap = capacity == NULL ? *size : *capacity; |
|
53 |
|
54 /* check if resize is required */ |
|
55 size_t newsize = index + elem_count; |
|
56 bool needrealloc = newsize > cap; |
|
57 |
|
58 /* reallocate if possible */ |
|
59 if (needrealloc) { |
|
60 /* a reallocator and a capacity variable must be available */ |
|
61 if (reallocator == NULL || capacity == NULL) { |
|
62 return CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED; |
|
63 } |
|
64 |
|
65 /* check, if we need to repair the src pointer */ |
|
66 uintptr_t targetaddr = (uintptr_t) *target; |
|
67 uintptr_t srcaddr = (uintptr_t) src; |
|
68 bool repairsrc = targetaddr <= srcaddr |
|
69 && srcaddr < targetaddr + cap * elem_size; |
|
70 |
|
71 /* increase capacity linearly */ |
|
72 cap += 16; |
|
73 |
|
74 /* perform reallocation */ |
|
75 void *newmem = reallocator->realloc( |
|
76 *target, cap, elem_size, reallocator |
|
77 ); |
|
78 if (newmem == NULL) { |
|
79 return CX_ARRAY_COPY_REALLOC_FAILED; |
|
80 } |
|
81 |
|
82 /* repair src pointer, if necessary */ |
|
83 if (repairsrc) { |
|
84 src = ((char *) newmem) + (srcaddr - targetaddr); |
|
85 } |
|
86 |
|
87 /* store new pointer and capacity */ |
|
88 *target = newmem; |
|
89 *capacity = cap; |
|
90 } |
|
91 |
|
92 /* determine target pointer */ |
|
93 char *start = *target; |
|
94 start += index * elem_size; |
|
95 |
|
96 /* copy elements and set new size */ |
|
97 memmove(start, src, elem_count * elem_size); |
|
98 *size = newsize; |
|
99 |
|
100 /* return successfully */ |
|
101 return CX_ARRAY_COPY_SUCCESS; |
|
102 } |
|
103 |
|
104 /* HIGH LEVEL ARRAY LIST FUNCTIONS */ |
|
105 |
|
106 typedef struct { |
|
107 struct cx_list_s base; |
|
108 void *data; |
|
109 struct cx_array_reallocator_s reallocator; |
|
110 } cx_array_list; |
|
111 |
|
112 static void *cx_arl_realloc( |
|
113 void *array, |
|
114 size_t capacity, |
|
115 size_t elem_size, |
|
116 struct cx_array_reallocator_s *alloc |
|
117 ) { |
|
118 /* retrieve the pointer to the list allocator */ |
|
119 CxAllocator const *al = alloc->ptr1; |
|
120 |
|
121 /* use the list allocator to reallocate the memory */ |
|
122 return cxRealloc(al, array, capacity * elem_size); |
|
123 } |
|
124 |
|
125 static void cx_arl_destructor(struct cx_list_s *list) { |
|
126 cx_array_list *arl = (cx_array_list *) list; |
|
127 cxFree(list->allocator, arl->data); |
|
128 } |
|
129 |
|
130 static int cx_arl_add( |
|
131 struct cx_list_s *list, |
|
132 void const *elem |
|
133 ) { |
|
134 cx_array_list *arl = (cx_array_list *) list; |
|
135 return cx_array_copy( |
|
136 &arl->data, |
|
137 &list->size, |
|
138 &list->capacity, |
|
139 list->size, |
|
140 elem, |
|
141 list->itemsize, |
|
142 1, |
|
143 &arl->reallocator |
|
144 ); |
|
145 } |
|
146 |
|
147 static int cx_arl_insert( |
|
148 struct cx_list_s *list, |
|
149 size_t index, |
|
150 void const *elem |
|
151 ) { |
|
152 if (index > list->size) { |
|
153 return 1; |
|
154 } else if (index == list->size) { |
|
155 return cx_arl_add(list, elem); |
|
156 } else { |
|
157 cx_array_list *arl = (cx_array_list *) list; |
|
158 |
|
159 /* move elements starting at index to the right */ |
|
160 if (cx_array_copy( |
|
161 &arl->data, |
|
162 &list->size, |
|
163 &list->capacity, |
|
164 index + 1, |
|
165 ((char *) arl->data) + index * list->itemsize, |
|
166 list->itemsize, |
|
167 list->size - index, |
|
168 &arl->reallocator |
|
169 )) { |
|
170 return 1; |
|
171 } |
|
172 |
|
173 /* place the element */ |
|
174 memcpy(((char *) arl->data) + index * list->itemsize, |
|
175 elem, list->itemsize); |
|
176 |
|
177 return 0; |
|
178 } |
|
179 } |
|
180 |
|
181 static int cx_arl_insert_iter( |
|
182 struct cx_iterator_s *iter, |
|
183 void const *elem, |
|
184 int prepend |
|
185 ) { |
|
186 return 1; |
|
187 } |
|
188 |
|
189 static int cx_arl_remove( |
|
190 struct cx_list_s *list, |
|
191 size_t index |
|
192 ) { |
|
193 /* out-of-bounds check */ |
|
194 if (index >= list->size) { |
|
195 return 1; |
|
196 } |
|
197 |
|
198 cx_array_list *arl = (cx_array_list *) list; |
|
199 |
|
200 /* just move the elements starting at index to the left */ |
|
201 int result = cx_array_copy( |
|
202 &arl->data, |
|
203 &list->size, |
|
204 &list->capacity, |
|
205 index, |
|
206 ((char *) arl->data) + (index + 1) * list->itemsize, |
|
207 list->itemsize, |
|
208 list->size - index, |
|
209 &arl->reallocator |
|
210 ); |
|
211 if (result == 0) { |
|
212 /* decrease the size */ |
|
213 list->size--; |
|
214 } |
|
215 return result; |
|
216 } |
|
217 |
|
218 static void *cx_arl_at( |
|
219 struct cx_list_s const *list, |
|
220 size_t index |
|
221 ) { |
|
222 if (index < list->size) { |
|
223 cx_array_list const *arl = (cx_array_list const *) list; |
|
224 char *space = arl->data; |
|
225 return space + index * list->itemsize; |
|
226 } else { |
|
227 return NULL; |
|
228 } |
|
229 } |
|
230 |
|
231 static size_t cx_arl_find( |
|
232 struct cx_list_s const *list, |
|
233 void const *elem |
|
234 ) { |
|
235 char *cur = ((cx_array_list const *) list)->data; |
|
236 |
|
237 for (size_t i = 0; i < list->size; i++) { |
|
238 if (0 == list->cmpfunc(elem, cur)) { |
|
239 return i; |
|
240 } |
|
241 cur += list->itemsize; |
|
242 } |
|
243 |
|
244 return list->size; |
|
245 } |
|
246 |
|
247 static void cx_arl_sort(struct cx_list_s *list) { |
|
248 qsort(((cx_array_list *) list)->data, |
|
249 list->size, |
|
250 list->itemsize, |
|
251 list->cmpfunc |
|
252 ); |
|
253 } |
|
254 |
|
255 static int cx_arl_compare( |
|
256 struct cx_list_s const *list, |
|
257 struct cx_list_s const *other |
|
258 ) { |
|
259 |
|
260 } |
|
261 |
|
262 static void cx_arl_reverse(struct cx_list_s *list) { |
|
263 |
|
264 } |
|
265 |
|
266 static bool cx_arl_iter_valid(struct cx_iterator_s const *iter) { |
|
267 struct cx_list_s const *list = iter->src_handle; |
|
268 return iter->index < list->size; |
|
269 } |
|
270 |
|
271 static void *cx_arl_iter_current(struct cx_iterator_s const *iter) { |
|
272 return iter->elem_handle; |
|
273 } |
|
274 |
|
275 static void cx_arl_iter_next(struct cx_iterator_s *iter) { |
|
276 if (iter->remove) { |
|
277 iter->remove = false; |
|
278 cx_arl_remove(iter->src_handle, iter->index); |
|
279 } else { |
|
280 iter->index++; |
|
281 iter->elem_handle = cx_arl_at(iter->src_handle, iter->index); |
|
282 } |
|
283 } |
|
284 |
|
285 static struct cx_iterator_s cx_arl_iterator( |
|
286 struct cx_list_s *list, |
|
287 size_t index |
|
288 ) { |
|
289 struct cx_iterator_s iter; |
|
290 |
|
291 iter.index = index; |
|
292 iter.src_handle = list; |
|
293 iter.elem_handle = cx_arl_at(list, index); |
|
294 iter.valid = cx_arl_iter_valid; |
|
295 iter.current = cx_arl_iter_current; |
|
296 iter.next = cx_arl_iter_next; |
|
297 iter.remove = false; |
|
298 |
|
299 return iter; |
|
300 } |
|
301 |
|
302 static cx_list_class cx_array_list_class = { |
|
303 cx_arl_destructor, |
|
304 cx_arl_add, |
|
305 cx_arl_insert, |
|
306 cx_arl_insert_iter, |
|
307 cx_arl_remove, |
|
308 cx_arl_at, |
|
309 cx_arl_find, |
|
310 cx_arl_sort, |
|
311 cx_arl_compare, |
|
312 cx_arl_reverse, |
|
313 cx_arl_iterator, |
|
314 }; |
|
315 |
|
316 CxList *cxArrayListCreate( |
|
317 CxAllocator const *allocator, |
|
318 CxListComparator comparator, |
|
319 size_t item_size, |
|
320 size_t initial_capacity |
|
321 ) { |
|
322 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list)); |
|
323 if (list == NULL) return NULL; |
|
324 |
|
325 list->data = cxCalloc(allocator, initial_capacity, item_size); |
|
326 if (list->data == NULL) { |
|
327 cxFree(allocator, list); |
|
328 return NULL; |
|
329 } |
|
330 |
|
331 list->base.cl = &cx_array_list_class; |
|
332 list->base.allocator = allocator; |
|
333 list->base.cmpfunc = comparator; |
|
334 list->base.itemsize = item_size; |
|
335 list->base.capacity = initial_capacity; |
|
336 |
|
337 /* configure the reallocator */ |
|
338 list->reallocator.realloc = cx_arl_realloc; |
|
339 list->reallocator.ptr1 = (void *) allocator; |
|
340 |
|
341 return (CxList *) list; |
|
342 } |