Mercurial > hg > ucx / changeset

--- a/src/array_list.c	Thu Aug 29 21:30:52 2024 +0200
+++ b/src/array_list.c	Sun Sep 01 14:48:43 2024 +0200
@@ -521,6 +521,7 @@
         cx_arl_destructor,
         cx_arl_insert_element,
         cx_arl_insert_array,
+        cx_list_default_insert_sorted,
         cx_arl_insert_iter,
         cx_arl_remove,
         cx_arl_clear,

--- a/src/cx/list.h	Thu Aug 29 21:30:52 2024 +0200
+++ b/src/cx/list.h	Sun Sep 01 14:48:43 2024 +0200
@@ -98,6 +98,17 @@
     );
 
     /**
+     * Member function for inserting sorted elements into a sorted list.
+     *
+     * @see cx_list_default_insert_sorted()
+     */
+    size_t (*insert_sorted)(
+            struct cx_list_s *list,
+            void const *sorted_data,
+            size_t n
+    );
+
+    /**
      * Member function for inserting an element relative to an iterator position.
      */
     int (*insert_iter)(
@@ -200,6 +211,29 @@
 );
 
 /**
+ * Default implementation of a sorted insert.
+ *
+ * This function uses the array insert function to insert consecutive groups
+ * of sorted data.
+ *
+ * The source data \em must already be sorted wrt. the list's compare function.
+ *
+ * Use this in your own list class if you do not want to implement an optimized
+ * version for your list.
+ *
+ * @param list the list
+ * @param sorted_data a pointer to the array of pre-sorted data to insert
+ * @param n the number of elements to insert
+ * @return the number of elements actually inserted
+ */
+__attribute__((__nonnull__))
+size_t cx_list_default_insert_sorted(
+        struct cx_list_s *list,
+        void const *sorted_data,
+        size_t n
+);
+
+/**
  * Default unoptimized sort implementation.
  *
  * This function will copy all data to an array, sort the array with standard
@@ -345,6 +379,22 @@
 }
 
 /**
+ * Inserts an item into a sorted list.
+ *
+ * @param list the list
+ * @param elem a pointer to the element to add
+ * @return zero on success, non-zero on memory allocation failure
+ */
+__attribute__((__nonnull__))
+static inline int cxListInsertSorted(
+        CxList *list,
+        void const *elem
+) {
+    void const *data = list->collection.store_pointer ? &elem : elem;
+    return list->cl->insert_sorted(list, data, 1) == 0;
+}
+
+/**
  * Inserts multiple items to the list at the specified index.
  * If \p index equals the list size, this is effectively cxListAddArray().
  *
@@ -374,6 +424,32 @@
 }
 
 /**
+ * Inserts a sorted array into a sorted list.
+ *
+ * This method is usually more efficient than inserting each element separately,
+ * because consecutive chunks of sorted data are inserted in one pass.
+ *
+ * If there is not enough memory to add all elements, the returned value is
+ * less than \p n.
+ *
+ * If this list is storing pointers instead of objects \p array is expected to
+ * be an array of pointers.
+ *
+ * @param list the list
+ * @param array a pointer to the elements to add
+ * @param n the number of elements to add
+ * @return the number of added elements
+ */
+__attribute__((__nonnull__))
+static inline size_t cxListInsertSortedArray(
+        CxList *list,
+        void const *array,
+        size_t n
+) {
+    return list->cl->insert_sorted(list, array, n);
+}
+
+/**
  * Inserts an element after the current location of the specified iterator.
  *
  * The used iterator remains operational, but all other active iterators should

--- a/src/linked_list.c	Thu Aug 29 21:30:52 2024 +0200
+++ b/src/linked_list.c	Sun Sep 01 14:48:43 2024 +0200
@@ -927,6 +927,7 @@
         cx_ll_destructor,
         cx_ll_insert_element,
         cx_ll_insert_array,
+        cx_list_default_insert_sorted,
         cx_ll_insert_iter,
         cx_ll_remove,
         cx_ll_clear,

--- a/src/list.c	Thu Aug 29 21:30:52 2024 +0200
+++ b/src/list.c	Sun Sep 01 14:48:43 2024 +0200
@@ -79,6 +79,17 @@
     return list->climpl->insert_array(list, index, array, n);
 }
 
+static size_t cx_pl_insert_sorted(
+        struct cx_list_s *list,
+        void const *array,
+        size_t n
+) {
+    cx_pl_hack_cmpfunc(list);
+    size_t result = list->climpl->insert_sorted(list, array, n);
+    cx_pl_unhack_cmpfunc(list);
+    return result;
+}
+
 static int cx_pl_insert_iter(
         struct cx_iterator_s *iter,
         void const *elem,
@@ -167,6 +178,7 @@
         cx_pl_destructor,
         cx_pl_insert_element,
         cx_pl_insert_array,
+        cx_pl_insert_sorted,
         cx_pl_insert_iter,
         cx_pl_remove,
         cx_pl_clear,
@@ -239,6 +251,7 @@
         NULL,
         NULL,
         NULL,
+        NULL,
         cx_emptyl_noop,
         NULL,
         cx_emptyl_at,
@@ -290,6 +303,21 @@
     return i;
 }
 
+size_t cx_list_default_insert_sorted(
+        struct cx_list_s *list,
+        void const *sorted_data,
+        size_t n
+) {
+    size_t elem_size = list->collection.elem_size;
+    cx_compare_func cmp = list->collection.cmpfunc;
+    char const *src = sorted_data;
+
+    size_t r = cx_list_default_insert_array(list, 0, src, n);
+    cx_list_default_sort(list);
+
+    return r;
+}
+
 void cx_list_default_sort(struct cx_list_s *list) {
     size_t elem_size = list->collection.elem_size;
     size_t list_size = list->collection.size;

--- a/tests/test_list.c	Thu Aug 29 21:30:52 2024 +0200
+++ b/tests/test_list.c	Sun Sep 01 14:48:43 2024 +0200
@@ -962,6 +962,7 @@
     cx_list_class const *cl = list->climpl == NULL ? list->cl : list->climpl;
     memcpy(defaulted_cl, cl, sizeof(cx_list_class));
     defaulted_cl->insert_array = cx_list_default_insert_array;
+    defaulted_cl->insert_sorted = cx_list_default_insert_sorted;
     defaulted_cl->sort = cx_list_default_sort;
     defaulted_cl->swap = cx_list_default_swap;
     defaulted_cl->compare = NULL;
@@ -1099,6 +1100,54 @@
     CX_TEST_ASSERT(*(int *) cxListAt(list, 9) == 42);
 })
 
+roll_out_test_combos_with_defaulted_funcs(insert_sorted, {
+    int d1 = 50;
+    int d2 = 80;
+    int d3 = 60;
+    int d4 = 40;
+    int d5 = 70;
+    int d6a[6] = array_init(52, 54, 56, 62, 64, 75);
+    int d7a[6] = array_init(51, 57, 58, 65, 77, 78);
+    int d8 = 90;
+    int *d6ptr[6];
+    int *d7ptr[6];
+    cx_for_n(i, 6)
+    {
+        d6ptr[i] = &d6a[i];
+        d7ptr[i] = &d7a[i];
+    }
+    size_t inserted;
+    int expected[18] = array_init(
+            40, 50, 51, 52, 54, 56, 57, 58, 60,
+            62, 64, 65, 70, 75, 77, 78, 80, 90
+    );
+
+    CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d1));
+    CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d2));
+    CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d3));
+    CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d4));
+    CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d5));
+    if (isptrlist) {
+        inserted = cxListInsertSortedArray(list, d6ptr, 6);
+    } else {
+        inserted = cxListInsertSortedArray(list, d6a, 6);
+    }
+    CX_TEST_ASSERT(inserted == 6);
+    if (isptrlist) {
+        inserted = cxListInsertSortedArray(list, d7ptr, 6);
+    } else {
+        inserted = cxListInsertSortedArray(list, d7a, 6);
+    }
+    CX_TEST_ASSERT(inserted == 6);
+    CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d8));
+
+    CX_TEST_ASSERT(cxListSize(list) == 18);
+    cx_for_n(i, 18)
+    {
+        CX_TEST_ASSERT(*(int *) cxListAt(list, i) == expected[i]);
+    }
+})
+
 roll_out_test_combos(remove, {
     const size_t testdata_len = 32;
     int *testdata = int_test_data_added_to_list(list, isptrlist, testdata_len);
@@ -1499,6 +1548,8 @@
     cx_test_register(suite, test_list_parl_insert);
     cx_test_register(suite, test_list_arl_insert_array);
     cx_test_register(suite, test_list_parl_insert_array);
+    cx_test_register(suite, test_list_arl_insert_sorted);
+    cx_test_register(suite, test_list_parl_insert_sorted);
     cx_test_register(suite, test_list_arl_remove);
     cx_test_register(suite, test_list_parl_remove);
     cx_test_register(suite, test_list_arl_find_remove);
@@ -1542,6 +1593,8 @@
 
     cx_test_register(suite, test_list_arlm_insert_array);
     cx_test_register(suite, test_list_parlm_insert_array);
+    cx_test_register(suite, test_list_arlm_insert_sorted);
+    cx_test_register(suite, test_list_parlm_insert_sorted);
     cx_test_register(suite, test_list_arlm_swap);
     cx_test_register(suite, test_list_parlm_swap);
     cx_test_register(suite, test_list_arlm_sort);
@@ -1589,6 +1642,8 @@
     cx_test_register(suite, test_list_pll_insert);
     cx_test_register(suite, test_list_ll_insert_array);
     cx_test_register(suite, test_list_pll_insert_array);
+    cx_test_register(suite, test_list_ll_insert_sorted);
+    cx_test_register(suite, test_list_pll_insert_sorted);
     cx_test_register(suite, test_list_ll_remove);
     cx_test_register(suite, test_list_pll_remove);
     cx_test_register(suite, test_list_ll_find_remove);
@@ -1632,6 +1687,8 @@
 
     cx_test_register(suite, test_list_llm_insert_array);
     cx_test_register(suite, test_list_pllm_insert_array);
+    cx_test_register(suite, test_list_llm_insert_sorted);
+    cx_test_register(suite, test_list_pllm_insert_sorted);
     cx_test_register(suite, test_list_llm_swap);
     cx_test_register(suite, test_list_pllm_swap);
     cx_test_register(suite, test_list_llm_sort);