--- a/ucx/array_list.c Fri Dec 12 10:42:53 2025 +0100
+++ b/ucx/array_list.c Fri Dec 19 17:22:03 2025 +0100
@@ -26,82 +26,16 @@
* POSSIBILITY OF SUCH DAMAGE.
*/
+#ifdef WITH_MEMRCHR
+#define _GNU_SOURCE
+#endif
+
#include "cx/array_list.h"
#include "cx/compare.h"
#include <assert.h>
#include <string.h>
#include <errno.h>
-// 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,
- };
-}
-
// LOW LEVEL ARRAY LIST FUNCTIONS
/**
@@ -128,295 +62,139 @@
return cap - (cap % alignment) + alignment;
}
-int cx_array_reserve(
- void **array,
- void *size,
- void *capacity,
- unsigned width,
- size_t elem_size,
- size_t elem_count,
- CxArrayReallocator *reallocator
-) {
- // assert pointers
- assert(array != NULL);
- assert(size != NULL);
- assert(capacity != NULL);
+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;
+}
- // default reallocator
- if (reallocator == NULL) {
- reallocator = cx_array_default_reallocator;
+int cx_array_copy_to_new_(const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity) {
+ CxArray heap_array;
+ if (cx_array_init_(allocator, &heap_array, elem_size, capacity)) {
+ return -1; // LCOV_EXCL_LINE
+ }
+ heap_array.size = array->size;
+ memcpy(heap_array.data, array->data, elem_size * array->size);
+ *array = heap_array;
+ return 0;
+}
+
+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;
+ if (n == 0) return 0;
+
+ // guarantee enough capacity
+ if (array->capacity < array->size + n) {
+ const size_t new_capacity = cx_array_grow_capacity(array->capacity,array->size + n);
+ if (cxReallocateArray(allocator, &array->data, new_capacity, elem_size)) {
+ return -1; // LCOV_EXCL_LINE
+ }
+ array->capacity = new_capacity;
}
- // 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;
+ // determine insert position
+ 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 = dst + n * elem_size;
+ memmove(target, dst, elems_to_move * elem_size);
}
- // assert that the array is allocated when it has capacity
- assert(*array != NULL || oldcap == 0);
-
- // check for overflow
- if (elem_count > max_size - oldsize) {
- errno = EOVERFLOW;
- return 1;
+ // place the new elements, if any
+ // otherwise, this function just reserved the memory (a.k.a emplace)
+ if (other != NULL) {
+ memcpy(dst, other, n * elem_size);
}
-
- // determine new capacity
- size_t newcap = oldsize + elem_count;
-
- // reallocate if possible
- if (newcap > oldcap) {
- void *newmem = reallocator->realloc(
- *array, oldcap, newcap, elem_size, reallocator
- );
- if (newmem == NULL) {
- return 1; // LCOV_EXCL_LINE
- }
-
- // store new pointer
- *array = newmem;
-
- // store new capacity
- if (width == 0 || width == sizeof(size_t)) {
- *(size_t*) capacity = newcap;
- } else if (width == sizeof(uint16_t)) {
- *(uint16_t*) capacity = (uint16_t) newcap;
- } else if (width == sizeof(uint8_t)) {
- *(uint8_t*) capacity = (uint8_t) newcap;
- }
-#if CX_WORDSIZE == 64
- else if (width == sizeof(uint32_t)) {
- *(uint32_t*) capacity = (uint32_t) newcap;
- }
-#endif
- }
+ array->size += n;
return 0;
}
-int cx_array_copy(
- void **target,
- void *size,
- void *capacity,
- unsigned width,
- size_t index,
- const void *src,
+int cx_array_insert_sorted_c_(
+ 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,
+ cx_compare_func2 cmp_func,
+ void *context,
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);
+ di = cx_array_binary_search_sup_c(dest, old_size, elem_size, src, cmp_func, context);
dest += di * elem_size;
// move the remaining elements in the array completely to the right
// 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,8 +208,8 @@
// Therefore, the buffer can never contain an element that is smaller
// 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
+ copy_len = cx_array_binary_search_inf_c(
+ src, n - si, elem_size, bptr, cmp_func, context
);
copy_len++;
@@ -450,17 +228,17 @@
// for being a duplicate of the bptr
const char *end_of_src = src + (copy_len - 1) * elem_size;
size_t skip_len = 0;
- while (copy_len > 0 && cmp_func(bptr, end_of_src) == 0) {
+ while (copy_len > 0 && cmp_func(bptr, end_of_src, context) == 0) {
end_of_src -= elem_size;
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;
for (unsigned j = 0; j < copy_len; j++) {
- if (last != NULL && cmp_func(last, src) == 0) {
+ if (last != NULL && cmp_func(last, src, context) == 0) {
// duplicate - skip
src += elem_size;
si++;
@@ -479,20 +257,21 @@
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(
+ copy_len = cx_array_binary_search_sup_c(
bptr,
new_size - bi,
elem_size,
src,
- cmp_func
+ cmp_func,
+ context
);
// restore the buffered elements
@@ -505,24 +284,24 @@
}
// 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);
+ int d = cmp_func(left_src, right_src, context);
if (d < 0) {
if (skip_len > 0) {
// new larger element found;
@@ -545,13 +324,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));
@@ -560,41 +339,116 @@
return 0;
}
-int cx_array_insert_sorted(
- void **target,
- size_t *size,
- size_t *capacity,
- cx_compare_func cmp_func,
+int cx_array_insert_sorted_(
+ const CxAllocator *allocator,
+ CxArray *array,
+ size_t elem_size,
const void *sorted_data,
- size_t elem_size,
- size_t elem_count,
- CxArrayReallocator *reallocator
+ size_t n,
+ cx_compare_func cmp_func,
+ bool allow_duplicates
) {
- return cx_array_insert_sorted_impl(target, size, capacity,
- cmp_func, sorted_data, elem_size, elem_count, reallocator, true);
+ cx_compare_func_wrapper wrapper = {cmp_func};
+ return cx_array_insert_sorted_c_(allocator, array, elem_size, sorted_data,
+ n, cx_ccmp_wrap, &wrapper, allow_duplicates);
+}
+
+#ifndef WITH_QSORT_R
+static thread_local cx_compare_func2 cx_array_fn_for_qsort;
+static thread_local void *cx_array_context_for_qsort;
+static int cx_array_qsort_wrapper(const void *l, const void *r) {
+ return cx_array_fn_for_qsort(l, r, cx_array_context_for_qsort);
+}
+#endif
+
+void cx_array_qsort_c(void *array, size_t nmemb, size_t size,
+ cx_compare_func2 fn, void *context) {
+#ifdef WITH_QSORT_R
+ qsort_r(array, nmemb, size, fn, context);
+#else
+ cx_array_fn_for_qsort = fn;
+ cx_array_context_for_qsort = context;
+ qsort(array, nmemb, size, cx_array_qsort_wrapper);
+#endif
+}
+
+void cx_array_sort_(CxArray *array, size_t elem_size,
+ cx_compare_func fn) {
+ qsort(array->data, array->size, elem_size, fn);
+}
+
+void cx_array_sort_c_(CxArray *array, size_t elem_size,
+ cx_compare_func2 fn, void *context) {
+ cx_array_qsort_c(array->data, array->size, elem_size, fn, context);
+}
+
+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);
}
-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);
+void cx_array_remove_(CxArray *array, size_t elem_size, size_t index, size_t n, bool fast) {
+ if (n == 0) return;
+ if (index >= array->size) return;
+ if (index + n >= array->size) {
+ // only tail elements are removed
+ array->size = index;
+ return;
+ }
+ array->size -= n;
+ size_t remaining = array->size - index;
+ char *dest = ((char*)array->data) + index * elem_size;
+ if (fast) {
+ char *src = dest + remaining * elem_size;
+ if (n == 1 && elem_size <= CX_WORDSIZE/8) {
+ // try to optimize int-sized values
+ // (from likely to unlikely)
+ if (elem_size == sizeof(int32_t)) {
+ *(int32_t*)dest = *(int32_t*)src;
+ return;
+ }
+#if CX_WORDSIZE == 64
+ if (elem_size == sizeof(int64_t)) {
+ *(int64_t*)dest = *(int64_t*)src;
+ return;
+ }
+#endif
+ if (elem_size == sizeof(int8_t)) {
+ *(int8_t*)dest = *(int8_t*)src;
+ return;
+ }
+ if (elem_size == sizeof(int16_t)) {
+ *(int16_t*)dest = *(int16_t*)src;
+ return;
+ }
+ // note we cannot optimize the last branch, because
+ // the elem_size could be crazily misaligned
+ }
+ memcpy(dest, src, n * elem_size);
+ } else {
+ char *src = dest + n * elem_size;
+ memmove(dest, src, remaining * elem_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,
size_t size,
size_t elem_size,
const void *elem,
- cx_compare_func cmp_func
+ cx_compare_func2 cmp_func,
+ void *context
) {
// special case: empty array
if (size == 0) return 0;
@@ -606,7 +460,7 @@
const char *array = arr;
// check the first array element
- result = cmp_func(elem, array);
+ result = cmp_func(elem, array, context);
if (result < 0) {
return size;
} else if (result == 0) {
@@ -617,7 +471,7 @@
if (size == 1) return 0;
// check the last array element
- result = cmp_func(elem, array + elem_size * (size - 1));
+ result = cmp_func(elem, array + elem_size * (size - 1), context);
if (result >= 0) {
return size - 1;
}
@@ -626,12 +480,12 @@
// so start the binary search
size_t left_index = 1;
size_t right_index = size - 1;
- size_t pivot_index;
+ size_t pivot_index = 0;
while (left_index <= right_index) {
pivot_index = left_index + (right_index - left_index) / 2;
const char *arr_elem = array + pivot_index * elem_size;
- result = cmp_func(elem, arr_elem);
+ result = cmp_func(elem, arr_elem, context);
if (result == 0) {
// found it!
return pivot_index;
@@ -648,6 +502,74 @@
return result < 0 ? (pivot_index - 1) : pivot_index;
}
+size_t cx_array_binary_search_inf_c(
+ const void *arr,
+ size_t size,
+ size_t elem_size,
+ const void *elem,
+ cx_compare_func2 cmp_func,
+ void *context
+) {
+ size_t index = cx_array_binary_search_inf_impl(
+ arr, size, elem_size, elem, cmp_func, context);
+ // in case of equality, report the largest index
+ const char *e = ((const char *) arr) + (index + 1) * elem_size;
+ while (index + 1 < size && cmp_func(e, elem, context) == 0) {
+ e += elem_size;
+ index++;
+ }
+ return index;
+}
+
+size_t cx_array_binary_search_c(
+ const void *arr,
+ size_t size,
+ size_t elem_size,
+ const void *elem,
+ cx_compare_func2 cmp_func,
+ void *context
+) {
+ size_t index = cx_array_binary_search_inf_c(
+ arr, size, elem_size, elem, cmp_func, context
+ );
+ if (index < size && cmp_func(((const char *) arr) + index * elem_size,
+ elem, context) == 0) {
+ return index;
+ } else {
+ return size;
+ }
+}
+
+size_t cx_array_binary_search_sup_c(
+ const void *arr,
+ size_t size,
+ size_t elem_size,
+ const void *elem,
+ cx_compare_func2 cmp_func,
+ void *context
+) {
+ size_t index = cx_array_binary_search_inf_impl(
+ arr, size, elem_size, elem, cmp_func, context
+ );
+ const char *e = ((const char *) arr) + index * elem_size;
+ if (index == size) {
+ // no infimum means the first element is supremum
+ return 0;
+ } else if (cmp_func(e, elem, context) == 0) {
+ // found an equal element, search the smallest index
+ e -= elem_size; // e now contains the element at index-1
+ while (index > 0 && cmp_func(e, elem, context) == 0) {
+ e -= elem_size;
+ index--;
+ }
+ return index;
+ } else {
+ // we already have the largest index of the infimum (by design)
+ // the next element is the supremum (or there is no supremum)
+ return index + 1;
+ }
+}
+
size_t cx_array_binary_search_inf(
const void *arr,
size_t size,
@@ -655,15 +577,8 @@
const void *elem,
cx_compare_func cmp_func
) {
- size_t index = cx_array_binary_search_inf_impl(
- arr, size, elem_size, elem, cmp_func);
- // in case of equality, report the largest index
- const char *e = ((const char *) arr) + (index + 1) * elem_size;
- while (index + 1 < size && cmp_func(e, elem) == 0) {
- e += elem_size;
- index++;
- }
- return index;
+ cx_compare_func_wrapper wrapper = {cmp_func};
+ return cx_array_binary_search_inf_c(arr, size, elem_size, elem, cx_ccmp_wrap, &wrapper);
}
size_t cx_array_binary_search(
@@ -673,15 +588,8 @@
const void *elem,
cx_compare_func cmp_func
) {
- size_t index = cx_array_binary_search_inf(
- arr, size, elem_size, elem, cmp_func
- );
- if (index < size &&
- cmp_func(((const char *) arr) + index * elem_size, elem) == 0) {
- return index;
- } else {
- return size;
- }
+ cx_compare_func_wrapper wrapper = {cmp_func};
+ return cx_array_binary_search_c(arr, size, elem_size, elem, cx_ccmp_wrap, &wrapper);
}
size_t cx_array_binary_search_sup(
@@ -691,26 +599,8 @@
const void *elem,
cx_compare_func cmp_func
) {
- size_t index = cx_array_binary_search_inf_impl(
- arr, size, elem_size, elem, cmp_func
- );
- const char *e = ((const char *) arr) + index * elem_size;
- if (index == size) {
- // no infimum means the first element is supremum
- return 0;
- } else if (cmp_func(e, elem) == 0) {
- // found an equal element, search the smallest index
- e -= elem_size; // e now contains the element at index-1
- while (index > 0 && cmp_func(e, elem) == 0) {
- e -= elem_size;
- index--;
- }
- return index;
- } else {
- // we already have the largest index of the infimum (by design)
- // the next element is the supremum (or there is no supremum)
- return index + 1;
- }
+ cx_compare_func_wrapper wrapper = {cmp_func};
+ return cx_array_binary_search_sup_c(arr, size, elem_size, elem, cx_ccmp_wrap, &wrapper);
}
#ifndef CX_ARRAY_SWAP_SBO_SIZE
@@ -763,7 +653,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) {
@@ -794,42 +683,47 @@
const void *array,
size_t n
) {
- // out of bounds and special case check
- if (index > list->collection.size || n == 0) return 0;
-
- // get a correctly typed pointer to the list
cx_array_list *arl = (cx_array_list *) list;
-
- // guarantee enough capacity
- if (arl->capacity < list->collection.size + n) {
- const size_t new_capacity = cx_array_grow_capacity(arl->capacity,list->collection.size + n);
- if (cxReallocateArray(
- list->collection.allocator,
- &arl->data, new_capacity,
- list->collection.elem_size)
- ) {
- return 0; // LCOV_EXCL_LINE
- }
- arl->capacity = new_capacity;
+ CxArray wrap = {
+ arl->data, list->collection.size, arl->capacity
+ };
+ if (cx_array_insert_(list->collection.allocator, &wrap,
+ list->collection.elem_size, index, array, n)) {
+ return 0;
}
+ arl->data = wrap.data;
+ arl->capacity = wrap.capacity;
+ list->collection.size = wrap.size;
+ return n;
+}
- // determine insert position
- char *arl_data = arl->data;
- char *insert_pos = arl_data + index * list->collection.elem_size;
+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
+ };
- // do we need to move some elements?
- if (index < list->collection.size) {
- size_t elems_to_move = list->collection.size - index;
- char *target = insert_pos + n * list->collection.elem_size;
- memmove(target, insert_pos, elems_to_move * list->collection.elem_size);
+ if (cx_array_insert_sorted_c_(
+ list->collection.allocator,
+ &wrap,
+ list->collection.elem_size,
+ sorted_data,
+ n,
+ cx_list_compare_wrapper,
+ list,
+ allow_duplicates
+ )) {
+ // array list implementation is "all or nothing"
+ return 0; // LCOV_EXCL_LINE
}
-
- // place the new elements, if any
- if (array != NULL) {
- memcpy(insert_pos, array, n * list->collection.elem_size);
- }
- list->collection.size += n;
-
+ arl->data = wrap.data;
+ arl->capacity = wrap.capacity;
+ list->collection.size = wrap.size;
return n;
}
@@ -838,24 +732,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_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(
@@ -863,24 +740,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(
@@ -959,24 +819,20 @@
);
}
+ // 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 *dst_move = arl->data;
+ dst_move += index * list->collection.elem_size;
+ char *first_remaining = dst_move + remove * list->collection.elem_size;
+ memmove(dst_move, first_remaining, remaining * list->collection.elem_size);
// decrease the size
list->collection.size -= remove;
@@ -1037,18 +893,18 @@
bool remove
) {
assert(list != NULL);
- assert(list->collection.cmpfunc != NULL);
if (list->collection.size == 0) return 0;
char *cur = ((const cx_array_list *) list)->data;
// optimize with binary search, when sorted
if (list->collection.sorted) {
- size_t i = cx_array_binary_search(
+ size_t i = cx_array_binary_search_c(
cur,
list->collection.size,
list->collection.elem_size,
elem,
- list->collection.cmpfunc
+ cx_list_compare_wrapper,
+ list
);
if (remove && i < list->collection.size) {
cx_arl_remove(list, i, 1, NULL);
@@ -1058,7 +914,7 @@
// fallback: linear search
for (size_t i = 0; i < list->collection.size; i++) {
- if (0 == list->collection.cmpfunc(elem, cur)) {
+ if (0 == cx_list_compare_wrapper(elem, cur, list)) {
if (remove) {
cx_arl_remove(list, i, 1, NULL);
}
@@ -1070,11 +926,11 @@
}
static void cx_arl_sort(struct cx_list_s *list) {
- assert(list->collection.cmpfunc != NULL);
- qsort(((cx_array_list *) list)->data,
+ cx_array_qsort_c(((cx_array_list *) list)->data,
list->collection.size,
list->collection.elem_size,
- list->collection.cmpfunc
+ cx_list_compare_wrapper,
+ list
);
}
@@ -1082,12 +938,11 @@
const struct cx_list_s *list,
const struct cx_list_s *other
) {
- assert(list->collection.cmpfunc != NULL);
if (list->collection.size == other->collection.size) {
const char *left = ((const cx_array_list *) list)->data;
const char *right = ((const cx_array_list *) other)->data;
for (size_t i = 0; i < list->collection.size; i++) {
- int d = list->collection.cmpfunc(left, right);
+ int d = cx_list_compare_wrapper(left, right, (void*)list);
if (d != 0) {
return d;
}
@@ -1200,7 +1055,6 @@
CxList *cxArrayListCreate(
const CxAllocator *allocator,
- cx_compare_func comparator,
size_t elem_size,
size_t initial_capacity
) {
@@ -1211,7 +1065,7 @@
cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
if (list == NULL) return NULL;
cx_list_init((CxList*)list, &cx_array_list_class,
- allocator, comparator, elem_size);
+ allocator, elem_size);
list->capacity = initial_capacity;
// allocate the array after the real elem_size is known
@@ -1222,8 +1076,5 @@
return NULL;
} // LCOV_EXCL_STOP
- // configure the reallocator
- list->reallocator = cx_array_reallocator(allocator, NULL);
-
return (CxList *) list;
}