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