Fri, 12 Apr 2024 21:48:12 +0200
improves interface of cx_sprintf() variants
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_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_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_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_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_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_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 );
331 // cx_array_copy cannot fail, array cannot grow
332 assert(result == 0);
334 // decrease the size
335 list->size--;
337 return 0;
338 }
340 static void cx_arl_clear(struct cx_list_s *list) {
341 if (list->size == 0) return;
343 cx_array_list *arl = (cx_array_list *) list;
344 char *ptr = arl->data;
346 if (list->simple_destructor) {
347 for (size_t i = 0; i < list->size; i++) {
348 cx_invoke_simple_destructor(list, ptr);
349 ptr += list->item_size;
350 }
351 }
352 if (list->advanced_destructor) {
353 for (size_t i = 0; i < list->size; i++) {
354 cx_invoke_advanced_destructor(list, ptr);
355 ptr += list->item_size;
356 }
357 }
359 memset(arl->data, 0, list->size * list->item_size);
360 list->size = 0;
361 }
363 static int cx_arl_swap(
364 struct cx_list_s *list,
365 size_t i,
366 size_t j
367 ) {
368 if (i >= list->size || j >= list->size) return 1;
369 cx_array_list *arl = (cx_array_list *) list;
370 cx_array_swap(arl->data, list->item_size, i, j);
371 return 0;
372 }
374 static void *cx_arl_at(
375 struct cx_list_s const *list,
376 size_t index
377 ) {
378 if (index < list->size) {
379 cx_array_list const *arl = (cx_array_list const *) list;
380 char *space = arl->data;
381 return space + index * list->item_size;
382 } else {
383 return NULL;
384 }
385 }
387 static ssize_t cx_arl_find_remove(
388 struct cx_list_s *list,
389 void const *elem,
390 bool remove
391 ) {
392 assert(list->cmpfunc != NULL);
393 assert(list->size < SIZE_MAX / 2);
394 char *cur = ((cx_array_list const *) list)->data;
396 for (ssize_t i = 0; i < (ssize_t) list->size; i++) {
397 if (0 == list->cmpfunc(elem, cur)) {
398 if (remove) {
399 if (0 == cx_arl_remove(list, i)) {
400 return i;
401 } else {
402 return -1;
403 }
404 } else {
405 return i;
406 }
407 }
408 cur += list->item_size;
409 }
411 return -1;
412 }
414 static void cx_arl_sort(struct cx_list_s *list) {
415 assert(list->cmpfunc != NULL);
416 qsort(((cx_array_list *) list)->data,
417 list->size,
418 list->item_size,
419 list->cmpfunc
420 );
421 }
423 static int cx_arl_compare(
424 struct cx_list_s const *list,
425 struct cx_list_s const *other
426 ) {
427 assert(list->cmpfunc != NULL);
428 if (list->size == other->size) {
429 char const *left = ((cx_array_list const *) list)->data;
430 char const *right = ((cx_array_list const *) other)->data;
431 for (size_t i = 0; i < list->size; i++) {
432 int d = list->cmpfunc(left, right);
433 if (d != 0) {
434 return d;
435 }
436 left += list->item_size;
437 right += other->item_size;
438 }
439 return 0;
440 } else {
441 return list->size < other->size ? -1 : 1;
442 }
443 }
445 static void cx_arl_reverse(struct cx_list_s *list) {
446 if (list->size < 2) return;
447 void *data = ((cx_array_list const *) list)->data;
448 size_t half = list->size / 2;
449 for (size_t i = 0; i < half; i++) {
450 cx_array_swap(data, list->item_size, i, list->size - 1 - i);
451 }
452 }
454 static bool cx_arl_iter_valid(void const *it) {
455 struct cx_iterator_s const *iter = it;
456 struct cx_list_s const *list = iter->src_handle;
457 return iter->index < list->size;
458 }
460 static void *cx_arl_iter_current(void const *it) {
461 struct cx_iterator_s const *iter = it;
462 return iter->elem_handle;
463 }
465 static void cx_arl_iter_next(void *it) {
466 struct cx_iterator_base_s *itbase = it;
467 if (itbase->remove) {
468 struct cx_mut_iterator_s *iter = it;
469 itbase->remove = false;
470 cx_arl_remove(iter->src_handle, iter->index);
471 } else {
472 struct cx_iterator_s *iter = it;
473 iter->index++;
474 iter->elem_handle =
475 ((char *) iter->elem_handle)
476 + ((struct cx_list_s const *) iter->src_handle)->item_size;
477 }
478 }
480 static void cx_arl_iter_prev(void *it) {
481 struct cx_iterator_base_s *itbase = it;
482 struct cx_mut_iterator_s *iter = it;
483 cx_array_list *const list = iter->src_handle;
484 if (itbase->remove) {
485 itbase->remove = false;
486 cx_arl_remove(iter->src_handle, iter->index);
487 }
488 iter->index--;
489 if (iter->index < list->base.size) {
490 iter->elem_handle = ((char *) list->data)
491 + iter->index * list->base.item_size;
492 }
493 }
496 static struct cx_iterator_s cx_arl_iterator(
497 struct cx_list_s const *list,
498 size_t index,
499 bool backwards
500 ) {
501 struct cx_iterator_s iter;
503 iter.index = index;
504 iter.src_handle = list;
505 iter.elem_handle = cx_arl_at(list, index);
506 iter.base.valid = cx_arl_iter_valid;
507 iter.base.current = cx_arl_iter_current;
508 iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next;
509 iter.base.remove = false;
510 iter.base.mutating = false;
512 return iter;
513 }
515 static cx_list_class cx_array_list_class = {
516 cx_arl_destructor,
517 cx_arl_insert_element,
518 cx_arl_insert_array,
519 cx_arl_insert_iter,
520 cx_arl_remove,
521 cx_arl_clear,
522 cx_arl_swap,
523 cx_arl_at,
524 cx_arl_find_remove,
525 cx_arl_sort,
526 cx_arl_compare,
527 cx_arl_reverse,
528 cx_arl_iterator,
529 };
531 CxList *cxArrayListCreate(
532 CxAllocator const *allocator,
533 cx_compare_func comparator,
534 size_t item_size,
535 size_t initial_capacity
536 ) {
537 if (allocator == NULL) {
538 allocator = cxDefaultAllocator;
539 }
541 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
542 if (list == NULL) return NULL;
544 list->base.cl = &cx_array_list_class;
545 list->base.allocator = allocator;
546 list->capacity = initial_capacity;
548 if (item_size > 0) {
549 list->base.item_size = item_size;
550 list->base.cmpfunc = comparator;
551 } else {
552 item_size = sizeof(void *);
553 list->base.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator;
554 cxListStorePointers((CxList *) list);
555 }
557 // allocate the array after the real item_size is known
558 list->data = cxCalloc(allocator, initial_capacity, item_size);
559 if (list->data == NULL) {
560 cxFree(allocator, list);
561 return NULL;
562 }
564 // configure the reallocator
565 list->reallocator.realloc = cx_arl_realloc;
566 list->reallocator.ptr1 = (void *) allocator;
568 return (CxList *) list;
569 }