Mercurial > hg > ucx / changeset

--- 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(

--- a/src/cx/array_list.h	Tue Sep 17 19:08:22 2024 +0200
+++ b/src/cx/array_list.h	Tue Sep 17 19:38:41 2024 +0200
@@ -55,6 +55,8 @@
  * @see cx_array_simple_add()
  * @see cx_array_simple_copy()
  * @see cx_array_initialize()
+ * @see cx_array_simple_add_sorted()
+ * @see cx_array_simple_insert_sorted()
  */
 #define CX_ARRAY_DECLARE(type, name) \
     type * name;                     \
@@ -147,7 +149,8 @@
  * @param target a pointer to the target array
  * @param size a pointer to the size of the target array
  * @param capacity a pointer to the target array's capacity -
- * \c NULL if only the size shall be used to bound the array
+ * \c NULL if only the size shall be used to bound the array (reallocations
+ * will NOT be supported in that case)
  * @param index the index where the copied elements shall be placed
  * @param src the source array
  * @param elem_size the size of one element
@@ -174,6 +177,7 @@
  * @param index the index where the copied elements shall be placed
  * @param src the source array
  * @param count the number of elements to copy
+ * @see CX_ARRAY_DECLARE()
  */
 #define cx_array_simple_copy(array, index, src, count) \
     cx_array_copy((void**)&(array), &(array##_size), &(array##_capacity), \
@@ -202,14 +206,94 @@
     cx_array_copy((void**)(target), size, capacity, *(size), elem, elem_size, 1, reallocator)
 
 /**
- * Convenience macro that uses cx_array_add() with a default layout and the default reallocator.
+ * Convenience macro that uses cx_array_add() with a default layout and
+ * the default reallocator.
  *
  * @param array the name of the array (NOT a pointer to the array)
  * @param elem the element to add (NOT a pointer, address is automatically taken)
+ * @see CX_ARRAY_DECLARE()
  */
 #define cx_array_simple_add(array, elem) \
     cx_array_simple_copy(array, array##_size, &(elem), 1)
 
+
+/**
+ * Inserts a sorted array into another sorted array.
+ *
+ * If either the target or the source array is not already sorted with respect
+ * to the specified \p cmp_func, the behavior is undefined.
+ *
+ * If the capacity is insufficient to hold the new data, a reallocation
+ * attempt is made.
+ *
+ * @param target a pointer to the target array
+ * @param size a pointer to the size of the target array
+ * @param capacity a pointer to the target array's capacity
+ * @param cmp_func the compare function for the elements
+ * @param src the source array
+ * @param elem_size the size of one element
+ * @param elem_count the number of elements to insert
+ * @param reallocator the array reallocator to use
+ * @return zero on success, non-zero error code on failure
+ */
+enum cx_array_result cx_array_insert_sorted(
+        void **target,
+        size_t *size,
+        size_t *capacity,
+        cx_compare_func cmp_func,
+        void const *src,
+        size_t elem_size,
+        size_t elem_count,
+        struct cx_array_reallocator_s *reallocator
+) __attribute__((__nonnull__));
+
+/**
+ * Inserts an element into a sorted array.
+ *
+ * If the target array is not already sorted with respect
+ * to the specified \p cmp_func, the behavior is undefined.
+ *
+ * If the capacity is insufficient to hold the new data, a reallocation
+ * attempt is made.
+ *
+ * @param target a pointer to the target array
+ * @param size a pointer to the size of the target array
+ * @param capacity a pointer to the target array's capacity
+ * @param elem_size the size of one element
+ * @param elem a pointer to the element to add
+ * @param reallocator the array reallocator to use
+ * @return zero on success, non-zero error code on failure
+ */
+#define cx_array_add_sorted(target, size, capacity, elem_size, elem, cmp_func, reallocator) \
+    cx_array_insert_sorted((void**)(target), size, capacity, cmp_func, elem, elem_size, 1, reallocator)
+
+/**
+ * Convenience macro for cx_array_add_sorted() with a default
+ * layout and the default reallocator.
+ *
+ * @param array the name of the array (NOT a pointer to the array)
+ * @param elem the element to add (NOT a pointer, address is automatically taken)
+ * @param cmp_func the compare function for the elements
+ * @see CX_ARRAY_DECLARE()
+ */
+#define cx_array_simple_add_sorted(array, elem, cmp_func) \
+    cx_array_add_sorted(&array, &(array##_size), &(array##_capacity), \
+        sizeof((array)[0]), &(elem), cmp_func, cx_array_default_reallocator)
+
+/**
+ * Convenience macro for cx_array_insert_sorted() with a default
+ * layout and the default reallocator.
+ *
+ * @param array the name of the array (NOT a pointer to the array)
+ * @param src pointer to the source array
+ * @param n number of elements in the source array
+ * @param cmp_func the compare function for the elements
+ * @see CX_ARRAY_DECLARE()
+ */
+#define cx_array_simple_insert_sorted(array, src, n, cmp_func) \
+    cx_array_insert_sorted((void**)(&array), &(array##_size), &(array##_capacity), \
+        cmp_func, src, sizeof((array)[0]), n, cx_array_default_reallocator)
+
 /**
  * Swaps two array elements.
  *

--- a/tests/test_list.c	Tue Sep 17 19:08:22 2024 +0200
+++ b/tests/test_list.c	Tue Sep 17 19:38:41 2024 +0200
@@ -99,6 +99,53 @@
     free(heaparray);
 }
 
+CX_TEST(test_array_insert_sorted) {
+    int d1 = 50;
+    int d2 = 80;
+    int d3 = 60;
+    int d4 = 40;
+    int d5 = 70;
+    int d6a[6] = {52, 54, 56, 62, 64, 75};
+    int d7a[6] = {51, 57, 58, 65, 77, 78};
+    int d8 = 90;
+    int expected[18] = {
+            40, 50, 51, 52, 54, 56, 57, 58, 60,
+            62, 64, 65, 70, 75, 77, 78, 80, 90
+    };
+
+    CX_ARRAY_DECLARE(int, array);
+    cx_array_initialize(array, 4);
+
+    CX_TEST_DO {
+        CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d1, cx_cmp_int));
+        CX_TEST_ASSERT(array_size == 1);
+        CX_TEST_ASSERT(array_capacity == 4);
+        CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d2, cx_cmp_int));
+        CX_TEST_ASSERT(array_size == 2);
+        CX_TEST_ASSERT(array_capacity == 4);
+        CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d3, cx_cmp_int));
+        CX_TEST_ASSERT(array_size == 3);
+        CX_TEST_ASSERT(array_capacity == 4);
+        CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d4, cx_cmp_int));
+        CX_TEST_ASSERT(array_size == 4);
+        CX_TEST_ASSERT(array_capacity == 4);
+        CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d5, cx_cmp_int));
+        CX_TEST_ASSERT(array_size == 5);
+        CX_TEST_ASSERT(array_capacity >= 5);
+        CX_TEST_ASSERT(0 == cx_array_simple_insert_sorted(array, d6a, 6, cx_cmp_int));
+        CX_TEST_ASSERT(array_size == 11);
+        CX_TEST_ASSERT(array_capacity >= 11);
+        CX_TEST_ASSERT(0 == cx_array_simple_insert_sorted(array, d7a, 6, cx_cmp_int));
+        CX_TEST_ASSERT(array_size == 17);
+        CX_TEST_ASSERT(array_capacity >= 17);
+        CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d8, cx_cmp_int));
+        CX_TEST_ASSERT(array_size == 18);
+        CX_TEST_ASSERT(array_capacity >= 18);
+
+        CX_TEST_ASSERT(0 == memcmp(array, expected, 18 * sizeof(int)));
+    }
+}
+
 typedef struct node {
     struct node *next;
     struct node *prev;
@@ -1534,6 +1581,7 @@
     CxTestSuite *suite = cx_test_suite_new("array_list");
 
     cx_test_register(suite, test_array_add);
+    cx_test_register(suite, test_array_insert_sorted);
 
     cx_test_register(suite, test_list_arl_create);
     cx_test_register(suite, test_list_arl_create_simple);