--- a/ucx/array_list.c Sun Oct 19 21:20:08 2025 +0200
+++ b/ucx/array_list.c Mon Nov 10 21:52:51 2025 +0100
@@ -50,7 +50,7 @@
}
CxArrayReallocator cx_array_default_reallocator_impl = {
- cx_array_default_realloc, NULL, NULL, 0, 0
+ cx_array_default_realloc, NULL, NULL
};
CxArrayReallocator *cx_array_default_reallocator = &cx_array_default_reallocator_impl;
@@ -72,11 +72,11 @@
}
// retrieve the pointer to the actual allocator
- const CxAllocator *al = alloc->ptr1;
+ const CxAllocator *al = alloc->allocator;
// check if the array is still located on the stack
void *newmem;
- if (array == alloc->ptr2) {
+ if (array == alloc->stack_ptr) {
newmem = cxMalloc(al, n);
if (newmem != NULL && array != NULL) {
memcpy(newmem, array, old_capacity*elem_size);
@@ -89,27 +89,45 @@
struct cx_array_reallocator_s cx_array_reallocator(
const struct cx_allocator_s *allocator,
- const void *stackmem
+ const void *stack_ptr
) {
if (allocator == NULL) {
allocator = cxDefaultAllocator;
}
return (struct cx_array_reallocator_s) {
cx_array_advanced_realloc,
- (void*) allocator, (void*) stackmem,
- 0, 0
+ allocator, stack_ptr,
};
}
// LOW LEVEL ARRAY LIST FUNCTIONS
-static size_t cx_array_align_capacity(
- size_t cap,
- size_t alignment,
- size_t max
+/**
+ * Intelligently calculates a new capacity, reserving some more
+ * elements than required to prevent too many allocations.
+ *
+ * @param current_capacity the current capacity of the array
+ * @param needed_capacity the required capacity of the array
+ * @param maximum_capacity the maximum capacity (given by the data type)
+ * @return the new capacity
+ */
+static size_t cx_array_grow_capacity(
+ size_t current_capacity,
+ size_t needed_capacity,
+ size_t maximum_capacity
) {
- if (cap > max - alignment) {
- return cap;
+ if (current_capacity >= needed_capacity) {
+ return current_capacity;
+ }
+ size_t cap = needed_capacity;
+ size_t alignment;
+ if (cap < 128) alignment = 16;
+ else if (cap < 1024) alignment = 64;
+ else if (cap < 8192) alignment = 512;
+ else alignment = 1024;
+
+ if (cap - 1 > maximum_capacity - alignment) {
+ return maximum_capacity;
} else {
return cap - (cap % alignment) + alignment;
}
@@ -177,10 +195,6 @@
// reallocate if possible
if (newcap > oldcap) {
- // calculate new capacity (next number divisible by 16)
- newcap = cx_array_align_capacity(newcap, 16, max_size);
-
- // perform reallocation
void *newmem = reallocator->realloc(
*array, oldcap, newcap, elem_size, reallocator
);
@@ -270,22 +284,18 @@
}
// check if resize is required
- size_t minsize = index + elem_count;
- size_t newsize = oldsize < minsize ? minsize : oldsize;
+ const size_t minsize = index + elem_count;
+ const size_t newsize = oldsize < minsize ? minsize : oldsize;
- // reallocate if possible
- size_t newcap = oldcap;
- if (newsize > oldcap) {
- // check, if we need to repair the src pointer
+ // reallocate if necessary
+ const size_t newcap = cx_array_grow_capacity(oldcap, newsize, max_size);
+ 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;
- // calculate new capacity (next number divisible by 16)
- newcap = cx_array_align_capacity(newsize, 16, max_size);
- assert(newcap > newsize);
-
// perform reallocation
void *newmem = reallocator->realloc(
*target, oldcap, newcap, elem_size, reallocator
@@ -368,16 +378,16 @@
}
// store some counts
- size_t old_size = *size;
- size_t old_capacity = *capacity;
+ const size_t old_size = *size;
+ const size_t old_capacity = *capacity;
// the necessary capacity is the worst case assumption, including duplicates
- size_t needed_capacity = old_size + elem_count;
+ const size_t needed_capacity = cx_array_grow_capacity(old_capacity,
+ old_size + elem_count, SIZE_MAX);
// if we need more than we have, try a reallocation
if (needed_capacity > old_capacity) {
- size_t new_capacity = cx_array_align_capacity(needed_capacity, 16, SIZE_MAX);
void *new_mem = reallocator->realloc(
- *target, old_capacity, new_capacity, elem_size, reallocator
+ *target, old_capacity, needed_capacity, elem_size, reallocator
);
if (new_mem == NULL) {
// give it up right away, there is no contract
@@ -385,7 +395,7 @@
return 1; // LCOV_EXCL_LINE
}
*target = new_mem;
- *capacity = new_capacity;
+ *capacity = needed_capacity;
}
// now we have guaranteed that we can insert everything
@@ -782,8 +792,8 @@
// guarantee enough capacity
if (arl->capacity < list->collection.size + n) {
- size_t new_capacity = list->collection.size + n;
- new_capacity = new_capacity - (new_capacity % 16) + 16;
+ const size_t new_capacity = cx_array_grow_capacity(arl->capacity,
+ list->collection.size + n, SIZE_MAX);
if (cxReallocateArray(
list->collection.allocator,
&arl->data, new_capacity,
@@ -881,7 +891,7 @@
const void *elem,
int prepend
) {
- struct cx_list_s *list = iter->src_handle.m;
+ struct cx_list_s *list = iter->src_handle;
if (iter->index < list->collection.size) {
if (cx_arl_insert_element(list,
iter->index + 1 - prepend, elem) == NULL) {
@@ -1092,7 +1102,7 @@
static bool cx_arl_iter_valid(const void *it) {
const struct cx_iterator_s *iter = it;
- const struct cx_list_s *list = iter->src_handle.c;
+ const struct cx_list_s *list = iter->src_handle;
return iter->index < list->collection.size;
}
@@ -1105,31 +1115,39 @@
struct cx_iterator_s *iter = it;
if (iter->base.remove) {
iter->base.remove = false;
- cx_arl_remove(iter->src_handle.m, iter->index, 1, NULL);
+ cx_arl_remove(iter->src_handle, iter->index, 1, NULL);
iter->elem_count--;
} else {
iter->index++;
iter->elem_handle =
((char *) iter->elem_handle)
- + ((const struct cx_list_s *) iter->src_handle.c)->collection.elem_size;
+ + ((const struct cx_list_s *) iter->src_handle)->collection.elem_size;
}
}
static void cx_arl_iter_prev(void *it) {
struct cx_iterator_s *iter = it;
- const cx_array_list *list = iter->src_handle.c;
if (iter->base.remove) {
iter->base.remove = false;
- cx_arl_remove(iter->src_handle.m, iter->index, 1, NULL);
+ cx_arl_remove(iter->src_handle, iter->index, 1, NULL);
iter->elem_count--;
}
iter->index--;
+ cx_array_list *list = iter->src_handle;
if (iter->index < list->base.collection.size) {
iter->elem_handle = ((char *) list->data)
+ iter->index * list->base.collection.elem_size;
}
}
+static int cx_arl_change_capacity(
+ struct cx_list_s *list,
+ size_t new_capacity
+) {
+ cx_array_list *arl = (cx_array_list *)list;
+ return cxReallocateArray(list->collection.allocator,
+ &arl->data, new_capacity, list->collection.elem_size);
+}
static struct cx_iterator_s cx_arl_iterator(
const struct cx_list_s *list,
@@ -1139,7 +1157,7 @@
struct cx_iterator_s iter;
iter.index = index;
- iter.src_handle.c = list;
+ iter.src_handle = (void*)list;
iter.elem_handle = cx_arl_at(list, index);
iter.elem_size = list->collection.elem_size;
iter.elem_count = list->collection.size;
@@ -1147,7 +1165,7 @@
iter.base.current = cx_arl_iter_current;
iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next;
iter.base.remove = false;
- iter.base.mutating = false;
+ iter.base.allow_remove = true;
return iter;
}
@@ -1167,6 +1185,7 @@
cx_arl_sort,
cx_arl_compare,
cx_arl_reverse,
+ cx_arl_change_capacity,
cx_arl_iterator,
};
