--- a/src/array_list.c Sun Dec 14 23:17:48 2025 +0100
+++ b/src/array_list.c Mon Dec 15 19:00:51 2025 +0100
@@ -58,86 +58,25 @@
return cap - (cap % alignment) + alignment;
}
-// Default array reallocator
-
-static void *cx_array_default_realloc(
- void *array,
- cx_attr_unused size_t old_capacity,
- size_t new_capacity,
- size_t elem_size,
- cx_attr_unused CxArrayReallocator *alloc
-) {
- size_t n;
- // LCOV_EXCL_START
- if (cx_szmul(new_capacity, elem_size, &n)) {
- errno = EOVERFLOW;
- return NULL;
- } // LCOV_EXCL_STOP
- return cxReallocDefault(array, n);
-}
-
-CxArrayReallocator cx_array_default_reallocator_impl = {
- cx_array_default_realloc, NULL, NULL
-};
-
-CxArrayReallocator *cx_array_default_reallocator = &cx_array_default_reallocator_impl;
-
-// Stack-aware array reallocator
-
-static void *cx_array_advanced_realloc(
- void *array,
- size_t old_capacity,
- size_t new_capacity,
- size_t elem_size,
- cx_attr_unused CxArrayReallocator *alloc
-) {
- // check for overflow
- size_t n;
- // LCOV_EXCL_START
- if (cx_szmul(new_capacity, elem_size, &n)) {
- errno = EOVERFLOW;
- return NULL;
- } // LCOV_EXCL_STOP
-
- // retrieve the pointer to the actual allocator
- const CxAllocator *al = alloc->allocator;
-
- // check if the array is still located on the stack
- void *newmem;
- if (array == alloc->stack_ptr) {
- newmem = cxMalloc(al, n);
- if (newmem != NULL && array != NULL) {
- memcpy(newmem, array, old_capacity*elem_size);
- }
- } else {
- newmem = cxRealloc(al, array, n);
- }
- return newmem;
-}
-
-struct cx_array_reallocator_s cx_array_reallocator(
- const struct cx_allocator_s *allocator,
- const void *stack_ptr
-) {
- if (allocator == NULL) {
- allocator = cxDefaultAllocator;
- }
- return (struct cx_array_reallocator_s) {
- cx_array_advanced_realloc,
- allocator, stack_ptr,
- };
-}
-
int cx_array_init_(const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity) {
memset(array, 0, sizeof(CxArray));
return cx_array_reserve_(allocator, array, elem_size, capacity);
}
+void cx_array_init_fixed_(CxArray *array, const void *data, size_t capacity, size_t size) {
+ array->data = (void*) data;
+ array->capacity = capacity;
+ array->size = size;
+}
+
int cx_array_reserve_(const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity) {
if (cxReallocateArray(allocator, &array->data, capacity, elem_size)) {
return -1; // LCOV_EXCL_LINE
}
array->capacity = capacity;
+ if (array->size > capacity) {
+ array->size = capacity;
+ }
return 0;
}
@@ -152,22 +91,7 @@
return 0;
}
-int cx_array_add_(const CxAllocator *allocator, CxArray *array, size_t elem_size, void *element) {
- if (array->size >= array->capacity) {
- size_t newcap = cx_array_grow_capacity(array->capacity, array->capacity + 1);
- if (cxReallocateArray(allocator, &array->data, newcap, elem_size)) {
- return -1;
- }
- array->capacity = newcap;
- }
- char *dst = array->data;
- dst += elem_size * array->size;
- memcpy(dst, element, elem_size);
- array->size++;
- return 0;
-}
-
-int cx_array_insert_array_(const CxAllocator *allocator, CxArray *array,
+int cx_array_insert_(const CxAllocator *allocator, CxArray *array,
size_t elem_size, size_t index, const void *other, size_t n) {
// out of bounds and special case check
if (index > array->size) return -1;
@@ -183,224 +107,74 @@
}
// determine insert position
- char *arl_data = array->data;
- char *insert_pos = arl_data + index * elem_size;
+ char *dst = array->data;
+ dst += index * elem_size;
// do we need to move some elements?
if (index < array->size) {
size_t elems_to_move = array->size - index;
- char *target = insert_pos + n * elem_size;
- memmove(target, insert_pos, elems_to_move * elem_size);
+ char *target = dst + n * elem_size;
+ memmove(target, dst, elems_to_move * elem_size);
}
// place the new elements, if any
// otherwise, this function just reserved the memory (a.k.a emplace)
if (other != NULL) {
- memcpy(insert_pos, other, n * elem_size);
+ memcpy(dst, other, n * elem_size);
}
array->size += n;
return 0;
}
-CxIterator cx_array_iterator_(CxArray *array, size_t elem_size) {
- return cxIterator(array->data, elem_size, array->size);
-}
-
-CxIterator cx_array_iterator_ptr_(CxArray *array) {
- return cxIteratorPtr(array->data, array->size);
-}
-
-void cx_array_free_(const CxAllocator *allocator, CxArray *array) {
- cxFree(allocator, array->data);
- array->data = NULL;
- array->size = array->capacity = 0;
-}
-
-int cx_array_copy(
- void **target,
- void *size,
- void *capacity,
- unsigned width,
- size_t index,
- const void *src,
+int cx_array_insert_sorted_(
+ const CxAllocator *allocator,
+ CxArray *array,
size_t elem_size,
- size_t elem_count,
- CxArrayReallocator *reallocator
-) {
- // assert pointers
- assert(target != NULL);
- assert(size != NULL);
- assert(capacity != NULL);
- assert(src != NULL);
-
- // default reallocator
- if (reallocator == NULL) {
- reallocator = cx_array_default_reallocator;
- }
-
- // determine size and capacity
- size_t oldcap;
- size_t oldsize;
- size_t max_size;
- if (width == 0 || width == sizeof(size_t)) {
- oldcap = *(size_t*) capacity;
- oldsize = *(size_t*) size;
- max_size = SIZE_MAX;
- } else if (width == sizeof(uint16_t)) {
- oldcap = *(uint16_t*) capacity;
- oldsize = *(uint16_t*) size;
- max_size = UINT16_MAX;
- } else if (width == sizeof(uint8_t)) {
- oldcap = *(uint8_t*) capacity;
- oldsize = *(uint8_t*) size;
- max_size = UINT8_MAX;
- }
-#if CX_WORDSIZE == 64
- else if (width == sizeof(uint32_t)) {
- oldcap = *(uint32_t*) capacity;
- oldsize = *(uint32_t*) size;
- max_size = UINT32_MAX;
- }
-#endif
- else {
- errno = EINVAL;
- return 1;
- }
-
- // assert that the array is allocated when it has capacity
- assert(*target != NULL || oldcap == 0);
-
- // check for overflow
- if (index > max_size || elem_count > max_size - index) {
- errno = EOVERFLOW;
- return 1;
- }
-
- // check if resize is required
- const size_t minsize = index + elem_count;
- const size_t newsize = oldsize < minsize ? minsize : oldsize;
-
- // reallocate if necessary
- const size_t newcap = cx_array_grow_capacity(oldcap, newsize);
- if (newcap > oldcap) {
- // check if we need to repair the src pointer
- uintptr_t targetaddr = (uintptr_t) *target;
- uintptr_t srcaddr = (uintptr_t) src;
- bool repairsrc = targetaddr <= srcaddr
- && srcaddr < targetaddr + oldcap * elem_size;
-
- // perform reallocation
- void *newmem = reallocator->realloc(
- *target, oldcap, newcap, elem_size, reallocator
- );
- if (newmem == NULL) {
- return 1; // LCOV_EXCL_LINE
- }
-
- // repair src pointer, if necessary
- if (repairsrc) {
- src = ((char *) newmem) + (srcaddr - targetaddr);
- }
-
- // store new pointer
- *target = newmem;
- }
-
- // determine target pointer
- char *start = *target;
- start += index * elem_size;
-
- // copy elements and set new size
- // note: no overflow check here, b/c we cannot get here w/o allocation
- memmove(start, src, elem_count * elem_size);
-
- // if any of size or capacity changed, store them back
- if (newsize != oldsize || newcap != oldcap) {
- if (width == 0 || width == sizeof(size_t)) {
- *(size_t*) capacity = newcap;
- *(size_t*) size = newsize;
- } else if (width == sizeof(uint16_t)) {
- *(uint16_t*) capacity = (uint16_t) newcap;
- *(uint16_t*) size = (uint16_t) newsize;
- } else if (width == sizeof(uint8_t)) {
- *(uint8_t*) capacity = (uint8_t) newcap;
- *(uint8_t*) size = (uint8_t) newsize;
- }
-#if CX_WORDSIZE == 64
- else if (width == sizeof(uint32_t)) {
- *(uint32_t*) capacity = (uint32_t) newcap;
- *(uint32_t*) size = (uint32_t) newsize;
- }
-#endif
- }
-
- // return successfully
- return 0;
-}
-
-static int cx_array_insert_sorted_impl(
- void **target,
- size_t *size,
- size_t *capacity,
cx_compare_func cmp_func,
const void *sorted_data,
- size_t elem_size,
- size_t elem_count,
- CxArrayReallocator *reallocator,
+ size_t n,
bool allow_duplicates
) {
// assert pointers
- assert(target != NULL);
- assert(size != NULL);
- assert(capacity != NULL);
+ assert(allocator != NULL);
+ assert(array != NULL);
assert(cmp_func != NULL);
assert(sorted_data != NULL);
- // default reallocator
- if (reallocator == NULL) {
- reallocator = cx_array_default_reallocator;
- }
-
// corner case
- if (elem_count == 0) return 0;
+ if (n == 0) return 0;
// overflow check
// LCOV_EXCL_START
- if (elem_count > SIZE_MAX - *size) {
+ if (n > SIZE_MAX - array->size) {
errno = EOVERFLOW;
return 1;
}
// LCOV_EXCL_STOP
// store some counts
- const size_t old_size = *size;
- const size_t old_capacity = *capacity;
+ const size_t old_size = array->size;
+ const size_t old_capacity = array->capacity;
// the necessary capacity is the worst case assumption, including duplicates
- const size_t needed_capacity = cx_array_grow_capacity(old_capacity, old_size + elem_count);
+ const size_t needed_capacity = cx_array_grow_capacity(old_capacity, old_size + n);
// if we need more than we have, try a reallocation
if (needed_capacity > old_capacity) {
- void *new_mem = reallocator->realloc(
- *target, old_capacity, needed_capacity, elem_size, reallocator
- );
- if (new_mem == NULL) {
- // give it up right away, there is no contract
- // that requires us to insert as much as we can
- return 1; // LCOV_EXCL_LINE
+ if (cxReallocateArray(allocator, &array->data, needed_capacity, elem_size)) {
+ return -1; // LCOV_EXCL_LINE
}
- *target = new_mem;
- *capacity = needed_capacity;
+ array->capacity = needed_capacity;
}
// now we have guaranteed that we can insert everything
- size_t new_size = old_size + elem_count;
- *size = new_size;
+ size_t new_size = old_size + n;
+ array->size = new_size;
// declare the source and destination indices/pointers
size_t si = 0, di = 0;
const char *src = sorted_data;
- char *dest = *target;
+ char *dest = array->data;
// find the first insertion point
di = cx_array_binary_search_sup(dest, old_size, elem_size, src, cmp_func);
@@ -410,12 +184,12 @@
// we will call it the "buffer" for parked elements
size_t buf_size = old_size - di;
size_t bi = new_size - buf_size;
- char *bptr = ((char *) *target) + bi * elem_size;
+ char *bptr = ((char *) array->data) + bi * elem_size;
memmove(bptr, dest, buf_size * elem_size);
// while there are both source and buffered elements left,
// copy them interleaving
- while (si < elem_count && bi < new_size) {
+ while (si < n && bi < new_size) {
// determine how many source elements can be inserted.
// the first element that shall not be inserted is the smallest element
// that is strictly larger than the first buffered element
@@ -430,7 +204,7 @@
// than any element in the source and the infimum exists.
size_t copy_len, bytes_copied;
copy_len = cx_array_binary_search_inf(
- src, elem_count - si, elem_size, bptr, cmp_func
+ src, n - si, elem_size, bptr, cmp_func
);
copy_len++;
@@ -454,7 +228,7 @@
skip_len++;
copy_len--;
}
- char *last = dest == *target ? NULL : dest - elem_size;
+ char *last = dest == array->data ? NULL : dest - elem_size;
// then iterate through the source chunk
// and skip all duplicates with the last element in the array
size_t more_skipped = 0;
@@ -478,12 +252,12 @@
si += skip_len;
skip_len += more_skipped;
// reduce the actual size by the number of skipped elements
- *size -= skip_len;
+ array->size -= skip_len;
}
}
// when all source elements are in place, we are done
- if (si >= elem_count) break;
+ if (si >= n) break;
// determine how many buffered elements need to be restored
copy_len = cx_array_binary_search_sup(
@@ -504,22 +278,22 @@
}
// still source elements left?
- if (si < elem_count) {
+ if (si < n) {
if (allow_duplicates) {
// duplicates allowed or nothing inserted yet: simply copy everything
- memcpy(dest, src, elem_size * (elem_count - si));
+ memcpy(dest, src, elem_size * (n - si));
} else {
// we must check the remaining source elements one by one
// to skip the duplicates.
// Note that no source element can equal the last element in the
// destination, because that would have created an insertion point
// and a buffer, s.t. the above loop already handled the duplicates
- while (si < elem_count) {
+ while (si < n) {
// find a chain of elements that can be copied
size_t copy_len = 1, skip_len = 0;
{
const char *left_src = src;
- while (si + copy_len + skip_len < elem_count) {
+ while (si + copy_len + skip_len < n) {
const char *right_src = left_src + elem_size;
int d = cmp_func(left_src, right_src);
if (d < 0) {
@@ -544,13 +318,13 @@
src += bytes_copied + skip_len * elem_size;
si += copy_len + skip_len;
di += copy_len;
- *size -= skip_len;
+ array->size -= skip_len;
}
}
}
// buffered elements need to be moved when we skipped duplicates
- size_t total_skipped = new_size - *size;
+ size_t total_skipped = new_size - array->size;
if (bi < new_size && total_skipped > 0) {
// move the remaining buffer to the end of the array
memmove(dest, bptr, elem_size * (new_size - bi));
@@ -559,34 +333,21 @@
return 0;
}
-int cx_array_insert_sorted(
- void **target,
- size_t *size,
- size_t *capacity,
- cx_compare_func cmp_func,
- const void *sorted_data,
- size_t elem_size,
- size_t elem_count,
- CxArrayReallocator *reallocator
-) {
- return cx_array_insert_sorted_impl(target, size, capacity,
- cmp_func, sorted_data, elem_size, elem_count, reallocator, true);
+CxIterator cx_array_iterator_(CxArray *array, size_t elem_size) {
+ return cxIterator(array->data, elem_size, array->size);
}
-int cx_array_insert_unique(
- void **target,
- size_t *size,
- size_t *capacity,
- cx_compare_func cmp_func,
- const void *sorted_data,
- size_t elem_size,
- size_t elem_count,
- CxArrayReallocator *reallocator
-) {
- return cx_array_insert_sorted_impl(target, size, capacity,
- cmp_func, sorted_data, elem_size, elem_count, reallocator, false);
+CxIterator cx_array_iterator_ptr_(CxArray *array) {
+ return cxIteratorPtr(array->data, array->size);
}
+void cx_array_free_(const CxAllocator *allocator, CxArray *array) {
+ cxFree(allocator, array->data);
+ array->data = NULL;
+ array->size = array->capacity = 0;
+}
+
+
// implementation that finds ANY index
static size_t cx_array_binary_search_inf_impl(
const void *arr,
@@ -762,7 +523,6 @@
struct cx_list_s base;
void *data;
size_t capacity;
- CxArrayReallocator reallocator;
} cx_array_list;
static void cx_arl_destructor(struct cx_list_s *list) {
@@ -797,8 +557,8 @@
CxArray wrap = {
arl->data, list->collection.size, arl->capacity
};
- if (cx_array_insert_array_(list->collection.allocator, &wrap,
- list->collection.elem_size, index, array, n)) {
+ if (cx_array_insert_(list->collection.allocator, &wrap,
+ list->collection.elem_size, index, array, n)) {
return 0;
}
arl->data = wrap.data;
@@ -807,29 +567,41 @@
return n;
}
+static size_t cx_arl_insert_sorted_impl(
+ struct cx_list_s *list,
+ const void *sorted_data,
+ size_t n,
+ bool allow_duplicates
+) {
+ cx_array_list *arl = (cx_array_list *) list;
+ CxArray wrap = {
+ arl->data, list->collection.size, arl->capacity
+ };
+
+ if (cx_array_insert_sorted_(
+ list->collection.allocator,
+ &wrap,
+ list->collection.elem_size,
+ list->collection.cmpfunc,
+ sorted_data,
+ n,
+ allow_duplicates
+ )) {
+ // array list implementation is "all or nothing"
+ return 0; // LCOV_EXCL_LINE
+ }
+ arl->data = wrap.data;
+ arl->capacity = wrap.capacity;
+ list->collection.size = wrap.size;
+ return n;
+}
+
static size_t cx_arl_insert_sorted(
struct cx_list_s *list,
const void *sorted_data,
size_t n
) {
- // get a correctly typed pointer to the list
- cx_array_list *arl = (cx_array_list *) list;
-
- if (cx_array_insert_sorted(
- &arl->data,
- &list->collection.size,
- &arl->capacity,
- list->collection.cmpfunc,
- sorted_data,
- list->collection.elem_size,
- n,
- &arl->reallocator
- )) {
- // array list implementation is "all or nothing"
- return 0; // LCOV_EXCL_LINE
- } else {
- return n;
- }
+ return cx_arl_insert_sorted_impl(list, sorted_data, n, true);
}
static size_t cx_arl_insert_unique(
@@ -837,24 +609,7 @@
const void *sorted_data,
size_t n
) {
- // get a correctly typed pointer to the list
- cx_array_list *arl = (cx_array_list *) list;
-
- if (cx_array_insert_unique(
- &arl->data,
- &list->collection.size,
- &arl->capacity,
- list->collection.cmpfunc,
- sorted_data,
- list->collection.elem_size,
- n,
- &arl->reallocator
- )) {
- // array list implementation is "all or nothing"
- return 0; // LCOV_EXCL_LINE
- } else {
- return n;
- }
+ return cx_arl_insert_sorted_impl(list, sorted_data, n, false);
}
static void *cx_arl_insert_element(
@@ -933,24 +688,21 @@
);
}
+ // calculate how many elements would need to be moved
+ size_t remaining = list->collection.size - index - remove;
+
// short-circuit removal of last elements
- if (index + remove == list->collection.size) {
+ if (remaining == 0) {
list->collection.size -= remove;
return remove;
}
// just move the elements to the left
- cx_array_copy(
- &arl->data,
- &list->collection.size,
- &arl->capacity,
- 0,
- index,
- ((char *) arl->data) + (index + remove) * list->collection.elem_size,
- list->collection.elem_size,
- list->collection.size - index - remove,
- &arl->reallocator
- );
+ char *first_remaining = arl->data;
+ first_remaining += (index + remove) * list->collection.elem_size;
+ char *dst_move = arl->data;
+ dst_move += index * list->collection.elem_size;
+ memmove(dst_move, first_remaining, remaining * list->collection.elem_size);
// decrease the size
list->collection.size -= remove;
@@ -1195,8 +947,5 @@
return NULL;
} // LCOV_EXCL_STOP
- // configure the reallocator
- list->reallocator = cx_array_reallocator(allocator, NULL);
-
return (CxList *) list;
}