Mercurial > hg > ucx / changeset

--- a/src/array_list.c	Mon Sep 09 21:54:22 2024 +0200
+++ b/src/array_list.c	Mon Sep 16 19:52:17 2024 +0200
@@ -264,6 +264,113 @@
     }
 }
 
+static size_t cx_arl_insert_sorted(
+        struct cx_list_s *list,
+        void const *sorted_data,
+        size_t n
+) {
+    // corner case
+    if (n == 0) return 0;
+
+    // define some handy pointers
+    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;
+    }
+
+    // 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(
         struct cx_list_s *list,
         size_t index,
@@ -521,7 +628,7 @@
         cx_arl_destructor,
         cx_arl_insert_element,
         cx_arl_insert_array,
-        cx_list_default_insert_sorted,
+        cx_arl_insert_sorted,
         cx_arl_insert_iter,
         cx_arl_remove,
         cx_arl_clear,