Mercurial > hg > ucx / changeset

--- a/src/array_list.c	Sun Oct 06 19:17:41 2024 +0200
+++ b/src/array_list.c	Mon Oct 07 20:20:21 2024 +0200
@@ -494,35 +494,58 @@
     }
 }
 
-static int cx_arl_remove(
+static size_t cx_arl_remove(
         struct cx_list_s *list,
-        size_t index
+        size_t index,
+        size_t num,
+        void *targetbuf
 ) {
     cx_array_list *arl = (cx_array_list *) list;
 
     // out-of-bounds check
+    size_t remove;
     if (index >= list->collection.size) {
-        return 1;
+        remove = 0;
+    } else if (index + num > list->collection.size) {
+        remove = list->collection.size - index;
+    } else {
+        remove = num;
     }
 
-    // content destruction
-    cx_invoke_destructor(list, ((char *) arl->data) + index * list->collection.elem_size);
+    // easy exit
+    if (remove == 0) return 0;
 
-    // short-circuit removal of last element
-    if (index == list->collection.size - 1) {
-        list->collection.size--;
-        return 0;
+    // destroy or copy contents
+    if (targetbuf == NULL) {
+        for (size_t idx = index; idx < index + remove; idx++) {
+            cx_invoke_destructor(
+                    list,
+                    ((char *) arl->data) + idx * list->collection.elem_size
+            );
+        }
+    } else {
+        memcpy(
+                targetbuf,
+                ((char *) arl->data) + index * list->collection.elem_size,
+                remove * list->collection.elem_size
+        );
     }
 
-    // just move the elements starting at index to the left
+    // short-circuit removal of last elements
+    if (index + remove == list->collection.size) {
+        list->collection.size -= remove;
+        return remove;
+    }
+
+    // just move the elements to the left
     int result = cx_array_copy(
             &arl->data,
             &list->collection.size,
             &arl->capacity,
             index,
-            ((char *) arl->data) + (index + 1) * list->collection.elem_size,
+            ((char *) arl->data) + (index + remove) * list->collection.elem_size,
             list->collection.elem_size,
-            list->collection.size - index - 1,
+            list->collection.size - index - remove,
             &arl->reallocator
     );
 
@@ -530,9 +553,9 @@
     assert(result == 0);
 
     // decrease the size
-    list->collection.size--;
+    list->collection.size -= remove;
 
-    return 0;
+    return remove;
 }
 
 static void cx_arl_clear(struct cx_list_s *list) {
@@ -594,7 +617,7 @@
     for (ssize_t i = 0; i < (ssize_t) list->collection.size; i++) {
         if (0 == list->collection.cmpfunc(elem, cur)) {
             if (remove) {
-                if (0 == cx_arl_remove(list, i)) {
+                if (1 == cx_arl_remove(list, i, 1, NULL)) {
                     return i;
                 } else {
                     return -1;
@@ -664,7 +687,7 @@
     struct cx_iterator_s *iter = it;
     if (iter->base.remove) {
         iter->base.remove = false;
-        cx_arl_remove(iter->src_handle.m, iter->index);
+        cx_arl_remove(iter->src_handle.m, iter->index, 1, NULL);
     } else {
         iter->index++;
         iter->elem_handle =
@@ -678,7 +701,7 @@
     const cx_array_list *list = iter->src_handle.c;
     if (iter->base.remove) {
         iter->base.remove = false;
-        cx_arl_remove(iter->src_handle.m, iter->index);
+        cx_arl_remove(iter->src_handle.m, iter->index, 1, NULL);
     }
     iter->index--;
     if (iter->index < list->base.collection.size) {

--- a/src/cx/linked_list.h	Sun Oct 06 19:17:41 2024 +0200
+++ b/src/cx/linked_list.h	Mon Oct 07 20:20:21 2024 +0200
@@ -389,6 +389,37 @@
 );
 
 /**
+ * Removes a chain of nodes from the linked list.
+ *
+ * If one of the nodes to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end)
+ * addresses are provided, the pointers are adjusted accordingly.
+ *
+ * The following combinations of arguments are valid (more arguments are optional):
+ * \li \p loc_next and \p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance)
+ * \li \p loc_next and \p begin (ancestor node is determined by list traversal, overall O(n) performance)
+ *
+ * \remark The \c next and \c prev pointers of the removed node are not cleared by this function and may still be used
+ * to traverse to a former adjacent node in the list, or within the chain.
+ *
+ * @param begin a pointer to the begin node pointer (optional)
+ * @param end a pointer to the end node pointer (optional)
+ * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
+ * @param loc_next the location of a \c next pointer within your node struct (required)
+ * @param node the start node of the chain
+ * @param num the number of nodes to remove
+ * @return the actual number of nodes that were removed (may be less when the list did not have enough nodes)
+ */
+__attribute__((__nonnull__(5)))
+size_t cx_linked_list_remove_chain(
+        void **begin,
+        void **end,
+        ptrdiff_t loc_prev,
+        ptrdiff_t loc_next,
+        void *node,
+        size_t num
+);
+
+/**
  * Removes a node from the linked list.
  *
  * If the node to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end)
@@ -408,14 +439,15 @@
  * @param node the node to remove
  */
 __attribute__((__nonnull__(5)))
-void cx_linked_list_remove(
+static inline void cx_linked_list_remove(
         void **begin,
         void **end,
         ptrdiff_t loc_prev,
         ptrdiff_t loc_next,
         void *node
-);
-
+) {
+    cx_linked_list_remove_chain(begin, end, loc_prev, loc_next, node, 1);
+}
 
 /**
  * Determines the size of a linked list starting with \p node.

--- a/src/cx/list.h	Sun Oct 06 19:17:41 2024 +0200
+++ b/src/cx/list.h	Mon Oct 07 20:20:21 2024 +0200
@@ -118,11 +118,20 @@
     );
 
     /**
-     * Member function for removing an element.
+     * Member function for removing elements.
+     *
+     * Implementations SHALL check if \p targetbuf is set and copy the elements
+     * to the buffer without invoking any destructor.
+     * When \p targetbuf is not set, the destructors SHALL be invoked.
+     *
+     * The function SHALL return the actual number of elements removed, which
+     * might be lower than \p num when going out of bounds.
      */
-    int (*remove)(
+    size_t (*remove)(
             struct cx_list_s *list,
-            size_t index
+            size_t index,
+            size_t num,
+            void *targetbuf
     );
 
     /**
@@ -512,7 +521,73 @@
         CxList *list,
         size_t index
 ) {
-    return list->cl->remove(list, index);
+    return list->cl->remove(list, index, 1, NULL) == 0;
+}
+
+/**
+ * Removes and returns the element at the specified index.
+ *
+ * No destructor is called and instead the element is copied to the
+ * \p targetbuf which MUST be large enough to hold the removed element.
+ *
+ * @param list the list
+ * @param index the index of the element
+ * @param targetbuf a buffer where to copy the element
+ * @return zero on success, non-zero if the index is out of bounds
+ */
+__attribute__((__nonnull__))
+static inline int cxListRemoveAndGet(
+        CxList *list,
+        size_t index,
+        void *targetbuf
+) {
+    return list->cl->remove(list, index, 1, targetbuf) == 0;
+}
+
+/**
+ * Removes multiple element starting at the specified index.
+ *
+ * If an element destructor function is specified, it is called for each
+ * element. It is guaranteed that the destructor is called before removing
+ * the element, however, due to possible optimizations it is neither guaranteed
+ * that the destructors are invoked for all elements before starting to remove
+ * them, nor that the element is removed immediately after the destructor call
+ * before proceeding to the next element.
+ *
+ * @param list the list
+ * @param index the index of the element
+ * @param num the number of elements to remove
+ * @return the actual number of removed elements
+ */
+__attribute__((__nonnull__))
+static inline size_t cxListRemoveArray(
+        CxList *list,
+        size_t index,
+        size_t num
+) {
+    return list->cl->remove(list, index, num, NULL);
+}
+
+/**
+ * Removes and returns multiple element starting at the specified index.
+ *
+ * No destructor is called and instead the elements are copied to the
+ * \p targetbuf which MUST be large enough to hold all removed elements.
+ *
+ * @param list the list
+ * @param index the index of the element
+ * @param num the number of elements to remove
+ * @param targetbuf a buffer where to copy the elements
+ * @return the actual number of removed elements
+ */
+__attribute__((__nonnull__))
+static inline size_t cxListRemoveArrayAndGet(
+        CxList *list,
+        size_t index,
+        size_t num,
+        void *targetbuf
+) {
+    return list->cl->remove(list, index, num, targetbuf);
 }
 
 /**

--- a/src/linked_list.c	Sun Oct 06 19:17:41 2024 +0200
+++ b/src/linked_list.c	Mon Oct 07 20:20:21 2024 +0200
@@ -91,7 +91,7 @@
     do {
         void *current = ll_data(node);
         if (cmp_func(current, elem) == 0) {
-            *result = (void*) node;
+            *result = (void *) node;
             return index;
         }
         node = ll_advance(node);
@@ -336,19 +336,22 @@
     }
 }
 
-void cx_linked_list_remove(
+size_t cx_linked_list_remove_chain(
         void **begin,
         void **end,
         ptrdiff_t loc_prev,
         ptrdiff_t loc_next,
-        void *node
+        void *node,
+        size_t num
 ) {
     assert(node != NULL);
     assert(loc_next >= 0);
     assert(loc_prev >= 0 || begin != NULL);
 
+    // easy exit
+    if (num == 0) return 0;
+
     // find adjacent nodes
-    void *next = ll_next(node);
     void *prev;
     if (loc_prev >= 0) {
         prev = ll_prev(node);
@@ -356,6 +359,12 @@
         prev = cx_linked_list_prev(*begin, loc_next, node);
     }
 
+    void *next = ll_next(node);
+    size_t removed = 1;
+    for (; removed < num && next != NULL ; removed++) {
+        next = ll_next(next);
+    }
+
     // update next pointer of prev node, or set begin
     if (prev == NULL) {
         if (begin != NULL) {
@@ -373,6 +382,8 @@
     } else if (loc_prev >= 0) {
         ll_prev(next) = prev;
     }
+
+    return removed;
 }
 
 size_t cx_linked_list_size(
@@ -442,7 +453,7 @@
     ll_next(sorted[length - 1]) = NULL;
 
     *begin = sorted[0];
-    *end = sorted[length-1];
+    *end = sorted[length - 1];
     if (sorted != sbo) {
         free(sorted);
     }
@@ -733,30 +744,63 @@
     return inserted;
 }
 
-static int cx_ll_remove(
+static size_t cx_ll_remove(
         struct cx_list_s *list,
-        size_t index
+        size_t index,
+        size_t num,
+        void *targetbuf
 ) {
     cx_linked_list *ll = (cx_linked_list *) list;
     cx_linked_list_node *node = cx_ll_node_at(ll, index);
 
     // out-of-bounds check
-    if (node == NULL) return 1;
-
-    // element destruction
-    cx_invoke_destructor(list, node->payload);
+    if (node == NULL) return 0;
 
     // remove
-    cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
-                          CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
+    size_t removed = cx_linked_list_remove_chain(
+            (void **) &ll->begin,
+            (void **) &ll->end,
+            CX_LL_LOC_PREV,
+            CX_LL_LOC_NEXT,
+            node,
+            num
+    );
 
     // adjust size
-    list->collection.size--;
+    list->collection.size -= removed;
+
+    // copy or destroy the removed chain
+    if (targetbuf == NULL) {
+        cx_linked_list_node *n = node;
+        cx_for_n(i, removed) {
+            // element destruction
+            cx_invoke_destructor(list, n->payload);
+
+            // free the node
+            cxFree(list->collection.allocator, n);
 
-    // free and return
-    cxFree(list->collection.allocator, node);
+            // next
+            n = n->next;
+        }
+    } else {
+        char *dest = targetbuf;
+        cx_linked_list_node *n = node;
+        cx_for_n(i, removed) {
+            // copy payload
+            memcpy(dest, n->payload, list->collection.elem_size);
 
-    return 0;
+            // advance target buffer
+            dest += list->collection.elem_size;
+
+            // free the node
+            cxFree(list->collection.allocator, n);
+
+            // next
+            n = n->next;
+        }
+    }
+
+    return removed;
 }
 
 static void cx_ll_clear(struct cx_list_s *list) {

--- a/src/list.c	Sun Oct 06 19:17:41 2024 +0200
+++ b/src/list.c	Mon Oct 07 20:20:21 2024 +0200
@@ -99,11 +99,13 @@
     return list->climpl->insert_iter(iter, &elem, prepend);
 }
 
-static int cx_pl_remove(
+static size_t cx_pl_remove(
         struct cx_list_s *list,
-        size_t index
+        size_t index,
+        size_t num,
+        void *targetbuf
 ) {
-    return list->climpl->remove(list, index);
+    return list->climpl->remove(list, index, num, targetbuf);
 }
 
 static void cx_pl_clear(struct cx_list_s *list) {