|
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 |
|
33 // LOW LEVEL ARRAY LIST FUNCTIONS |
|
34 |
|
35 enum cx_array_copy_result cx_array_copy( |
|
36 void **target, |
|
37 size_t *size, |
|
38 size_t *capacity, |
|
39 size_t index, |
|
40 void const *src, |
|
41 size_t elem_size, |
|
42 size_t elem_count, |
|
43 struct cx_array_reallocator_s *reallocator |
|
44 ) { |
|
45 // assert pointers |
|
46 assert(target != NULL); |
|
47 assert(size != NULL); |
|
48 assert(src != NULL); |
|
49 |
|
50 // determine capacity |
|
51 size_t cap = capacity == NULL ? *size : *capacity; |
|
52 |
|
53 // check if resize is required |
|
54 size_t minsize = index + elem_count; |
|
55 size_t newsize = *size < minsize ? minsize : *size; |
|
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 // calculate new capacity (next number divisible by 16) |
|
72 cap = newsize - (newsize % 16) + 16; |
|
73 assert(cap > newsize); |
|
74 |
|
75 // perform reallocation |
|
76 void *newmem = reallocator->realloc( |
|
77 *target, cap, elem_size, reallocator |
|
78 ); |
|
79 if (newmem == NULL) { |
|
80 return CX_ARRAY_COPY_REALLOC_FAILED; |
|
81 } |
|
82 |
|
83 // repair src pointer, if necessary |
|
84 if (repairsrc) { |
|
85 src = ((char *) newmem) + (srcaddr - targetaddr); |
|
86 } |
|
87 |
|
88 // store new pointer and capacity |
|
89 *target = newmem; |
|
90 *capacity = cap; |
|
91 } |
|
92 |
|
93 // determine target pointer |
|
94 char *start = *target; |
|
95 start += index * elem_size; |
|
96 |
|
97 // copy elements and set new size |
|
98 memmove(start, src, elem_count * elem_size); |
|
99 *size = newsize; |
|
100 |
|
101 // return successfully |
|
102 return CX_ARRAY_COPY_SUCCESS; |
|
103 } |
|
104 |
|
105 #ifndef CX_ARRAY_SWAP_SBO_SIZE |
|
106 #define CX_ARRAY_SWAP_SBO_SIZE 512 |
|
107 #endif |
|
108 |
|
109 void cx_array_swap( |
|
110 void *arr, |
|
111 size_t elem_size, |
|
112 size_t idx1, |
|
113 size_t idx2 |
|
114 ) { |
|
115 assert(arr != NULL); |
|
116 |
|
117 // short circuit |
|
118 if (idx1 == idx2) return; |
|
119 |
|
120 char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE]; |
|
121 void *tmp; |
|
122 |
|
123 // decide if we can use the local buffer |
|
124 if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) { |
|
125 tmp = malloc(elem_size); |
|
126 // we don't want to enforce error handling |
|
127 if (tmp == NULL) abort(); |
|
128 } else { |
|
129 tmp = sbo_mem; |
|
130 } |
|
131 |
|
132 // calculate memory locations |
|
133 char *left = arr, *right = arr; |
|
134 left += idx1 * elem_size; |
|
135 right += idx2 * elem_size; |
|
136 |
|
137 // three-way swap |
|
138 memcpy(tmp, left, elem_size); |
|
139 memcpy(left, right, elem_size); |
|
140 memcpy(right, tmp, elem_size); |
|
141 |
|
142 // free dynamic memory, if it was needed |
|
143 if (tmp != sbo_mem) { |
|
144 free(tmp); |
|
145 } |
|
146 } |
|
147 |
|
148 // HIGH LEVEL ARRAY LIST FUNCTIONS |
|
149 |
|
150 typedef struct { |
|
151 struct cx_list_s base; |
|
152 void *data; |
|
153 size_t capacity; |
|
154 struct cx_array_reallocator_s reallocator; |
|
155 } cx_array_list; |
|
156 |
|
157 static void *cx_arl_realloc( |
|
158 void *array, |
|
159 size_t capacity, |
|
160 size_t elem_size, |
|
161 struct cx_array_reallocator_s *alloc |
|
162 ) { |
|
163 // retrieve the pointer to the list allocator |
|
164 CxAllocator const *al = alloc->ptr1; |
|
165 |
|
166 // use the list allocator to reallocate the memory |
|
167 return cxRealloc(al, array, capacity * elem_size); |
|
168 } |
|
169 |
|
170 static void cx_arl_destructor(struct cx_list_s *list) { |
|
171 cx_array_list *arl = (cx_array_list *) list; |
|
172 cxFree(list->allocator, arl->data); |
|
173 } |
|
174 |
|
175 static size_t cx_arl_insert_array( |
|
176 struct cx_list_s *list, |
|
177 size_t index, |
|
178 void const *array, |
|
179 size_t n |
|
180 ) { |
|
181 // out of bounds and special case check |
|
182 if (index > list->size || n == 0) return 0; |
|
183 |
|
184 // get a correctly typed pointer to the list |
|
185 cx_array_list *arl = (cx_array_list *) list; |
|
186 |
|
187 // do we need to move some elements? |
|
188 if (index < list->size) { |
|
189 char const *first_to_move = (char const *) arl->data; |
|
190 first_to_move += index * list->item_size; |
|
191 size_t elems_to_move = list->size - index; |
|
192 size_t start_of_moved = index + n; |
|
193 |
|
194 if (CX_ARRAY_COPY_SUCCESS != cx_array_copy( |
|
195 &arl->data, |
|
196 &list->size, |
|
197 &arl->capacity, |
|
198 start_of_moved, |
|
199 first_to_move, |
|
200 list->item_size, |
|
201 elems_to_move, |
|
202 &arl->reallocator |
|
203 )) { |
|
204 // if moving existing elems is unsuccessful, abort |
|
205 return 0; |
|
206 } |
|
207 } |
|
208 |
|
209 // note that if we had to move the elements, the following operation |
|
210 // is guaranteed to succeed, because we have the memory already allocated |
|
211 // therefore, it is impossible to leave this function with an invalid array |
|
212 |
|
213 // place the new elements |
|
214 if (CX_ARRAY_COPY_SUCCESS == cx_array_copy( |
|
215 &arl->data, |
|
216 &list->size, |
|
217 &arl->capacity, |
|
218 index, |
|
219 array, |
|
220 list->item_size, |
|
221 n, |
|
222 &arl->reallocator |
|
223 )) { |
|
224 return n; |
|
225 } else { |
|
226 // array list implementation is "all or nothing" |
|
227 return 0; |
|
228 } |
|
229 } |
|
230 |
|
231 static int cx_arl_insert_element( |
|
232 struct cx_list_s *list, |
|
233 size_t index, |
|
234 void const *element |
|
235 ) { |
|
236 return 1 != cx_arl_insert_array(list, index, element, 1); |
|
237 } |
|
238 |
|
239 static int cx_arl_insert_iter( |
|
240 struct cx_mut_iterator_s *iter, |
|
241 void const *elem, |
|
242 int prepend |
|
243 ) { |
|
244 struct cx_list_s *list = iter->src_handle; |
|
245 if (iter->index < list->size) { |
|
246 int result = cx_arl_insert_element( |
|
247 list, |
|
248 iter->index + 1 - prepend, |
|
249 elem |
|
250 ); |
|
251 if (result == 0 && prepend != 0) { |
|
252 iter->index++; |
|
253 iter->elem_handle = ((char *) iter->elem_handle) + list->item_size; |
|
254 } |
|
255 return result; |
|
256 } else { |
|
257 int result = cx_arl_insert_element(list, list->size, elem); |
|
258 iter->index = list->size; |
|
259 return result; |
|
260 } |
|
261 } |
|
262 |
|
263 static int cx_arl_remove( |
|
264 struct cx_list_s *list, |
|
265 size_t index |
|
266 ) { |
|
267 cx_array_list *arl = (cx_array_list *) list; |
|
268 |
|
269 // out-of-bounds check |
|
270 if (index >= list->size) { |
|
271 return 1; |
|
272 } |
|
273 |
|
274 // content destruction |
|
275 cx_invoke_destructor(list, ((char *) arl->data) + index * list->item_size); |
|
276 |
|
277 // short-circuit removal of last element |
|
278 if (index == list->size - 1) { |
|
279 list->size--; |
|
280 return 0; |
|
281 } |
|
282 |
|
283 // just move the elements starting at index to the left |
|
284 int result = cx_array_copy( |
|
285 &arl->data, |
|
286 &list->size, |
|
287 &arl->capacity, |
|
288 index, |
|
289 ((char *) arl->data) + (index + 1) * list->item_size, |
|
290 list->item_size, |
|
291 list->size - index - 1, |
|
292 &arl->reallocator |
|
293 ); |
|
294 if (result == 0) { |
|
295 // decrease the size |
|
296 list->size--; |
|
297 } |
|
298 return result; |
|
299 } |
|
300 |
|
301 static void cx_arl_clear(struct cx_list_s *list) { |
|
302 if (list->size == 0) return; |
|
303 |
|
304 cx_array_list *arl = (cx_array_list *) list; |
|
305 char *ptr = arl->data; |
|
306 |
|
307 if (list->simple_destructor) { |
|
308 for (size_t i = 0; i < list->size; i++) { |
|
309 cx_invoke_simple_destructor(list, ptr); |
|
310 ptr += list->item_size; |
|
311 } |
|
312 } |
|
313 if (list->advanced_destructor) { |
|
314 for (size_t i = 0; i < list->size; i++) { |
|
315 cx_invoke_advanced_destructor(list, ptr); |
|
316 ptr += list->item_size; |
|
317 } |
|
318 } |
|
319 |
|
320 memset(arl->data, 0, list->size * list->item_size); |
|
321 list->size = 0; |
|
322 } |
|
323 |
|
324 static int cx_arl_swap( |
|
325 struct cx_list_s *list, |
|
326 size_t i, |
|
327 size_t j |
|
328 ) { |
|
329 if (i >= list->size || j >= list->size) return 1; |
|
330 cx_array_list *arl = (cx_array_list *) list; |
|
331 cx_array_swap(arl->data, list->item_size, i, j); |
|
332 return 0; |
|
333 } |
|
334 |
|
335 static void *cx_arl_at( |
|
336 struct cx_list_s const *list, |
|
337 size_t index |
|
338 ) { |
|
339 if (index < list->size) { |
|
340 cx_array_list const *arl = (cx_array_list const *) list; |
|
341 char *space = arl->data; |
|
342 return space + index * list->item_size; |
|
343 } else { |
|
344 return NULL; |
|
345 } |
|
346 } |
|
347 |
|
348 static size_t cx_arl_find( |
|
349 struct cx_list_s const *list, |
|
350 void const *elem |
|
351 ) { |
|
352 assert(list->cmpfunc != NULL); |
|
353 char *cur = ((cx_array_list const *) list)->data; |
|
354 |
|
355 for (size_t i = 0; i < list->size; i++) { |
|
356 if (0 == list->cmpfunc(elem, cur)) { |
|
357 return i; |
|
358 } |
|
359 cur += list->item_size; |
|
360 } |
|
361 |
|
362 return list->size; |
|
363 } |
|
364 |
|
365 static void cx_arl_sort(struct cx_list_s *list) { |
|
366 assert(list->cmpfunc != NULL); |
|
367 qsort(((cx_array_list *) list)->data, |
|
368 list->size, |
|
369 list->item_size, |
|
370 list->cmpfunc |
|
371 ); |
|
372 } |
|
373 |
|
374 static int cx_arl_compare( |
|
375 struct cx_list_s const *list, |
|
376 struct cx_list_s const *other |
|
377 ) { |
|
378 assert(list->cmpfunc != NULL); |
|
379 if (list->size == other->size) { |
|
380 char const *left = ((cx_array_list const *) list)->data; |
|
381 char const *right = ((cx_array_list const *) other)->data; |
|
382 for (size_t i = 0; i < list->size; i++) { |
|
383 int d = list->cmpfunc(left, right); |
|
384 if (d != 0) { |
|
385 return d; |
|
386 } |
|
387 left += list->item_size; |
|
388 right += other->item_size; |
|
389 } |
|
390 return 0; |
|
391 } else { |
|
392 return list->size < other->size ? -1 : 1; |
|
393 } |
|
394 } |
|
395 |
|
396 static void cx_arl_reverse(struct cx_list_s *list) { |
|
397 if (list->size < 2) return; |
|
398 void *data = ((cx_array_list const *) list)->data; |
|
399 size_t half = list->size / 2; |
|
400 for (size_t i = 0; i < half; i++) { |
|
401 cx_array_swap(data, list->item_size, i, list->size - 1 - i); |
|
402 } |
|
403 } |
|
404 |
|
405 static bool cx_arl_iter_valid(void const *it) { |
|
406 struct cx_iterator_s const *iter = it; |
|
407 struct cx_list_s const *list = iter->src_handle; |
|
408 return iter->index < list->size; |
|
409 } |
|
410 |
|
411 static void *cx_arl_iter_current(void const *it) { |
|
412 struct cx_iterator_s const *iter = it; |
|
413 return iter->elem_handle; |
|
414 } |
|
415 |
|
416 static void cx_arl_iter_next(void *it) { |
|
417 struct cx_iterator_base_s *itbase = it; |
|
418 if (itbase->remove) { |
|
419 struct cx_mut_iterator_s *iter = it; |
|
420 itbase->remove = false; |
|
421 cx_arl_remove(iter->src_handle, iter->index); |
|
422 } else { |
|
423 struct cx_iterator_s *iter = it; |
|
424 iter->index++; |
|
425 iter->elem_handle = |
|
426 ((char *) iter->elem_handle) |
|
427 + ((struct cx_list_s const *) iter->src_handle)->item_size; |
|
428 } |
|
429 } |
|
430 |
|
431 static void cx_arl_iter_prev(void *it) { |
|
432 struct cx_iterator_base_s *itbase = it; |
|
433 struct cx_mut_iterator_s *iter = it; |
|
434 cx_array_list *const list = iter->src_handle; |
|
435 if (itbase->remove) { |
|
436 itbase->remove = false; |
|
437 cx_arl_remove(iter->src_handle, iter->index); |
|
438 } |
|
439 iter->index--; |
|
440 if (iter->index < list->base.size) { |
|
441 iter->elem_handle = ((char *) list->data) |
|
442 + iter->index * list->base.item_size; |
|
443 } |
|
444 } |
|
445 |
|
446 static bool cx_arl_iter_flag_rm(void *it) { |
|
447 struct cx_iterator_base_s *iter = it; |
|
448 if (iter->mutating) { |
|
449 iter->remove = true; |
|
450 return true; |
|
451 } else { |
|
452 return false; |
|
453 } |
|
454 } |
|
455 |
|
456 static struct cx_iterator_s cx_arl_iterator( |
|
457 struct cx_list_s const *list, |
|
458 size_t index, |
|
459 bool backwards |
|
460 ) { |
|
461 struct cx_iterator_s iter; |
|
462 |
|
463 iter.index = index; |
|
464 iter.src_handle = list; |
|
465 iter.elem_handle = cx_arl_at(list, index); |
|
466 iter.base.valid = cx_arl_iter_valid; |
|
467 iter.base.current = cx_arl_iter_current; |
|
468 iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next; |
|
469 iter.base.flag_removal = cx_arl_iter_flag_rm; |
|
470 iter.base.remove = false; |
|
471 iter.base.mutating = false; |
|
472 |
|
473 return iter; |
|
474 } |
|
475 |
|
476 static cx_list_class cx_array_list_class = { |
|
477 cx_arl_destructor, |
|
478 cx_arl_insert_element, |
|
479 cx_arl_insert_array, |
|
480 cx_arl_insert_iter, |
|
481 cx_arl_remove, |
|
482 cx_arl_clear, |
|
483 cx_arl_swap, |
|
484 cx_arl_at, |
|
485 cx_arl_find, |
|
486 cx_arl_sort, |
|
487 cx_arl_compare, |
|
488 cx_arl_reverse, |
|
489 cx_arl_iterator, |
|
490 }; |
|
491 |
|
492 CxList *cxArrayListCreate( |
|
493 CxAllocator const *allocator, |
|
494 cx_compare_func comparator, |
|
495 size_t item_size, |
|
496 size_t initial_capacity |
|
497 ) { |
|
498 if (allocator == NULL) { |
|
499 allocator = cxDefaultAllocator; |
|
500 } |
|
501 |
|
502 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list)); |
|
503 if (list == NULL) return NULL; |
|
504 |
|
505 list->base.cl = &cx_array_list_class; |
|
506 list->base.allocator = allocator; |
|
507 list->base.cmpfunc = comparator; |
|
508 list->capacity = initial_capacity; |
|
509 |
|
510 if (item_size > 0) { |
|
511 list->base.item_size = item_size; |
|
512 } else { |
|
513 item_size = sizeof(void *); |
|
514 cxListStorePointers((CxList *) list); |
|
515 } |
|
516 |
|
517 // allocate the array after the real item_size is known |
|
518 list->data = cxCalloc(allocator, initial_capacity, item_size); |
|
519 if (list->data == NULL) { |
|
520 cxFree(allocator, list); |
|
521 return NULL; |
|
522 } |
|
523 |
|
524 // configure the reallocator |
|
525 list->reallocator.realloc = cx_arl_realloc; |
|
526 list->reallocator.ptr1 = (void *) allocator; |
|
527 |
|
528 return (CxList *) list; |
|
529 } |