--- a/src/array_list.c Tue Sep 17 19:08:22 2024 +0200
+++ b/src/array_list.c Tue Sep 17 19:38:41 2024 +0200
@@ -120,6 +120,122 @@
return CX_ARRAY_SUCCESS;
}
+enum cx_array_result cx_array_insert_sorted(
+ void **target,
+ size_t *size,
+ size_t *capacity,
+ cx_compare_func cmp_func,
+ void const *sorted_data,
+ size_t elem_size,
+ size_t elem_count,
+ struct cx_array_reallocator_s *reallocator
+) {
+ // assert pointers
+ assert(target != NULL);
+ assert(size != NULL);
+ assert(capacity != NULL);
+ assert(cmp_func != NULL);
+ assert(sorted_data != NULL);
+ assert(reallocator != NULL);
+
+ // corner case
+ if (elem_count == 0) return 0;
+
+ // store some counts
+ size_t old_size = *size;
+ size_t needed_capacity = old_size + elem_count;
+
+ // if we need more than we have, try a reallocation
+ if (needed_capacity > *capacity) {
+ size_t new_capacity = needed_capacity - (needed_capacity % 16) + 16;
+ void *new_mem = reallocator->realloc(
+ *target, new_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 CX_ARRAY_REALLOC_FAILED;
+ }
+ *target = new_mem;
+ *capacity = new_capacity;
+ }
+
+ // now we have guaranteed that we can insert everything
+ size_t new_size = old_size + elem_count;
+ *size = new_size;
+
+ // declare the source and destination indices/pointers
+ size_t si = 0, di = 0;
+ char const *src = sorted_data;
+ char *dest = *target;
+
+ // find the first insertion point
+ while (di < old_size) {
+ if (cmp_func(src, dest) < 0) {
+ break;
+ }
+ di++;
+ dest += 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;
+ 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) {
+ // determine how many source elements can be inserted
+ size_t copy_len = 1;
+ si++;
+ char const *next_src = src + elem_size;
+ while (si < elem_count) {
+ if (cmp_func(bptr, next_src) < 0) {
+ break;
+ }
+ copy_len++;
+ si++;
+ next_src += elem_size;
+ }
+
+ // copy the source elements
+ memcpy(dest, src, copy_len * elem_size);
+ dest += copy_len * elem_size;
+ src = next_src;
+
+ // determine how many buffered elements need to be restored
+ copy_len = 1;
+ bi++;
+ char *next_bptr = bptr + elem_size;
+ while (bi < new_size) {
+ if (cmp_func(src, next_bptr) < 0) {
+ break;
+ }
+ copy_len++;
+ bi++;
+ next_bptr += elem_size;
+ }
+
+ // restore the buffered elements
+ memmove(dest, bptr, copy_len * elem_size);
+ dest += copy_len * elem_size;
+ bptr = next_bptr;
+ }
+
+ // still source elements left? simply append them
+ if (si < elem_count) {
+ memcpy(dest, src, elem_size * (elem_count - si));
+ }
+
+ // still buffer elements left?
+ // don't worry, we already moved them to the correct place
+
+ return CX_ARRAY_SUCCESS;
+}
+
#ifndef CX_ARRAY_SWAP_SBO_SIZE
#define CX_ARRAY_SWAP_SBO_SIZE 128
#endif
@@ -269,106 +385,24 @@
void const *sorted_data,
size_t n
) {
- // corner case
- if (n == 0) return 0;
-
- // define some handy pointers
+ // get a correctly typed pointer to the list
cx_array_list *arl = (cx_array_list *) list;
- cx_compare_func cmp = list->collection.cmpfunc;
-
- // store some counts
- size_t old_size = list->collection.size;
- size_t capacity = arl->capacity;
- size_t needed_capacity = old_size + n;
- size_t elem_size = list->collection.elem_size;
-
- // if we need more than we have, try a reallocation
- if (needed_capacity > capacity) {
- capacity = needed_capacity - (needed_capacity % 16) + 16;
- if (0 != cxReallocate(list->collection.allocator,
- &(arl->data),
- capacity * elem_size)) {
- // give it up right away, there is no contract
- // that requires us to insert as much as we can
- return 0;
- }
- arl->capacity = capacity;
- }
-
- // now we have guaranteed that we can insert everything
- size_t new_size = list->collection.size + n;
- list->collection.size = new_size;
-
- // declare the source and destination indices/pointers
- size_t si = 0, di = 0;
- char const *src = sorted_data;
- char *dest = arl->data;
-
- // find the first insertion point
- while (di < old_size) {
- if (cmp(src, dest) < 0) {
- break;
- }
- di++;
- dest += 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 *) arl->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 < n && bi < new_size) {
- // determine how many source elements can be inserted
- size_t copy_len = 1;
- si++;
- char const *next_src = src + elem_size;
- while (si < n) {
- if (cmp(bptr, next_src) < 0) {
- break;
- }
- copy_len++;
- si++;
- next_src += elem_size;
- }
-
- // copy the source elements
- memcpy(dest, src, copy_len * elem_size);
- dest += copy_len * elem_size;
- src = next_src;
-
- // determine how many buffered elements need to be restored
- copy_len = 1;
- bi++;
- char *next_bptr = bptr + elem_size;
- while (bi < new_size) {
- if (cmp(src, next_bptr) < 0) {
- break;
- }
- copy_len++;
- bi++;
- next_bptr += elem_size;
- }
-
- // restore the buffered elements
- memmove(dest, bptr, copy_len * elem_size);
- dest += copy_len * elem_size;
- bptr = next_bptr;
+ if (CX_ARRAY_SUCCESS == cx_array_insert_sorted(
+ &arl->data,
+ &list->collection.size,
+ &arl->capacity,
+ list->collection.cmpfunc,
+ sorted_data,
+ list->collection.elem_size,
+ n,
+ &arl->reallocator
+ )) {
+ return n;
+ } else {
+ // array list implementation is "all or nothing"
+ return 0;
}
-
- // still source elements left? simply append them
- if (si < n) {
- memcpy(dest, src, elem_size * (n - si));
- }
-
- // still buffer elements left?
- // don't worry, we already moved them to the correct place
-
- return n;
}
static int cx_arl_insert_element(