--- a/ucx/array_list.c Sun Feb 16 17:38:07 2025 +0100
+++ b/ucx/array_list.c Tue Feb 25 21:12:11 2025 +0100
@@ -126,27 +126,31 @@
assert(array != NULL);
assert(size != NULL);
assert(capacity != NULL);
- assert(reallocator != 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 == 8*sizeof(size_t)) {
+ if (width == 0 || width == sizeof(size_t)) {
oldcap = *(size_t*) capacity;
oldsize = *(size_t*) size;
max_size = SIZE_MAX;
- } else if (width == 16) {
+ } else if (width == sizeof(uint16_t)) {
oldcap = *(uint16_t*) capacity;
oldsize = *(uint16_t*) size;
max_size = UINT16_MAX;
- } else if (width == 8) {
+ } 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 == 32) {
+ else if (width == sizeof(uint32_t)) {
oldcap = *(uint32_t*) capacity;
oldsize = *(uint32_t*) size;
max_size = UINT32_MAX;
@@ -186,15 +190,15 @@
*array = newmem;
// store new capacity
- if (width == 0 || width == 8*sizeof(size_t)) {
+ if (width == 0 || width == sizeof(size_t)) {
*(size_t*) capacity = newcap;
- } else if (width == 16) {
+ } else if (width == sizeof(uint16_t)) {
*(uint16_t*) capacity = (uint16_t) newcap;
- } else if (width == 8) {
+ } else if (width == sizeof(uint8_t)) {
*(uint8_t*) capacity = (uint8_t) newcap;
}
#if CX_WORDSIZE == 64
- else if (width == 32) {
+ else if (width == sizeof(uint32_t)) {
*(uint32_t*) capacity = (uint32_t) newcap;
}
#endif
@@ -219,27 +223,31 @@
assert(size != NULL);
assert(capacity != NULL);
assert(src != NULL);
- assert(reallocator != 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 == 8*sizeof(size_t)) {
+ if (width == 0 || width == sizeof(size_t)) {
oldcap = *(size_t*) capacity;
oldsize = *(size_t*) size;
max_size = SIZE_MAX;
- } else if (width == 16) {
+ } else if (width == sizeof(uint16_t)) {
oldcap = *(uint16_t*) capacity;
oldsize = *(uint16_t*) size;
max_size = UINT16_MAX;
- } else if (width == 8) {
+ } 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 == 32) {
+ else if (width == sizeof(uint32_t)) {
oldcap = *(uint32_t*) capacity;
oldsize = *(uint32_t*) size;
max_size = UINT32_MAX;
@@ -303,18 +311,18 @@
// if any of size or capacity changed, store them back
if (newsize != oldsize || newcap != oldcap) {
- if (width == 0 || width == 8*sizeof(size_t)) {
+ if (width == 0 || width == sizeof(size_t)) {
*(size_t*) capacity = newcap;
*(size_t*) size = newsize;
- } else if (width == 16) {
+ } else if (width == sizeof(uint16_t)) {
*(uint16_t*) capacity = (uint16_t) newcap;
*(uint16_t*) size = (uint16_t) newsize;
- } else if (width == 8) {
+ } 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 == 32) {
+ else if (width == sizeof(uint32_t)) {
*(uint32_t*) capacity = (uint32_t) newcap;
*(uint32_t*) size = (uint32_t) newsize;
}
@@ -341,7 +349,11 @@
assert(capacity != NULL);
assert(cmp_func != NULL);
assert(sorted_data != NULL);
- assert(reallocator != NULL);
+
+ // default reallocator
+ if (reallocator == NULL) {
+ reallocator = cx_array_default_reallocator;
+ }
// corner case
if (elem_count == 0) return 0;
@@ -844,32 +856,42 @@
}
}
-static ssize_t cx_arl_find_remove(
+static size_t cx_arl_find_remove(
struct cx_list_s *list,
const void *elem,
bool remove
) {
+ assert(list != NULL);
assert(list->collection.cmpfunc != NULL);
- assert(list->collection.size < SIZE_MAX / 2);
+ if (list->collection.size == 0) return 0;
char *cur = ((const cx_array_list *) list)->data;
- for (ssize_t i = 0; i < (ssize_t) list->collection.size; i++) {
+ // optimize with binary search, when sorted
+ if (list->collection.sorted) {
+ size_t i = cx_array_binary_search(
+ cur,
+ list->collection.size,
+ list->collection.elem_size,
+ elem,
+ list->collection.cmpfunc
+ );
+ if (remove && i < list->collection.size) {
+ cx_arl_remove(list, i, 1, NULL);
+ }
+ return i;
+ }
+
+ // fallback: linear search
+ for (size_t i = 0; i < list->collection.size; i++) {
if (0 == list->collection.cmpfunc(elem, cur)) {
if (remove) {
- if (1 == cx_arl_remove(list, i, 1, NULL)) {
- return i;
- } else {
- // should be unreachable
- return -1; // LCOV_EXCL_LINE
- }
- } else {
- return i;
+ cx_arl_remove(list, i, 1, NULL);
}
+ return i;
}
cur += list->collection.elem_size;
}
-
- return -1;
+ return list->collection.size;
}
static void cx_arl_sort(struct cx_list_s *list) {
@@ -1001,22 +1023,13 @@
cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
if (list == NULL) return NULL;
-
- list->base.cl = &cx_array_list_class;
- list->base.collection.allocator = allocator;
+ cx_list_init((CxList*)list, &cx_array_list_class,
+ allocator, comparator, elem_size);
list->capacity = initial_capacity;
- if (elem_size > 0) {
- list->base.collection.elem_size = elem_size;
- list->base.collection.cmpfunc = comparator;
- } else {
- elem_size = sizeof(void *);
- list->base.collection.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator;
- cxListStorePointers((CxList *) list);
- }
-
// allocate the array after the real elem_size is known
- list->data = cxCalloc(allocator, initial_capacity, elem_size);
+ list->data = cxCalloc(allocator, initial_capacity,
+ list->base.collection.elem_size);
if (list->data == NULL) { // LCOV_EXCL_START
cxFree(allocator, list);
return NULL;