Mercurial > hg > ucx / file diff

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