Mercurial > hg > toolkit / file diff

--- a/ucx/linked_list.c	Sun Jan 05 17:41:39 2025 +0100
+++ b/ucx/linked_list.c	Sun Jan 05 22:00:39 2025 +0100
@@ -27,7 +27,6 @@
  */
 
 #include "cx/linked_list.h"
-#include "cx/utils.h"
 #include "cx/compare.h"
 #include <string.h>
 #include <assert.h>
@@ -91,7 +90,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 +335,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 +358,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 +381,8 @@
     } else if (loc_prev >= 0) {
         ll_prev(next) = prev;
     }
+
+    return removed;
 }
 
 size_t cx_linked_list_size(
@@ -436,13 +446,13 @@
 
     // Update pointer
     if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
-    cx_for_n (i, length - 1) {
+    for (size_t i = 0 ; i < length - 1; i++) {
         cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next);
     }
     ll_next(sorted[length - 1]) = NULL;
 
     *begin = sorted[0];
-    *end = sorted[length-1];
+    *end = sorted[length - 1];
     if (sorted != sbo) {
         free(sorted);
     }
@@ -646,9 +656,7 @@
     cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
 
     // perform first insert
-    if (0 != cx_ll_insert_at(list, node, array)) {
-        return 1;
-    }
+    if (0 != cx_ll_insert_at(list, node, array)) return 1;
 
     // is there more?
     if (n == 1) return 1;
@@ -660,9 +668,7 @@
     const char *source = array;
     for (size_t i = 1; i < n; i++) {
         source += list->collection.elem_size;
-        if (0 != cx_ll_insert_at(list, node, source)) {
-            return i;
-        }
+        if (0 != cx_ll_insert_at(list, node, source)) return i;
         node = node->next;
     }
     return n;
@@ -733,30 +739,61 @@
     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;
+        for (size_t i = 0; i < removed; i++) {
+            // element destruction
+            cx_invoke_destructor(list, n->payload);
 
-    // free and return
-    cxFree(list->collection.allocator, node);
+            // free the node and advance
+            void *next = n->next;
+            cxFree(list->collection.allocator, n);
+            n = next;
+        }
+    } else {
+        char *dest = targetbuf;
+        cx_linked_list_node *n = node;
+        for (size_t i = 0; i < removed; i++) {
+            // copy payload
+            memcpy(dest, n->payload, list->collection.elem_size);
 
-    return 0;
+            // advance target buffer
+            dest += list->collection.elem_size;
+
+            // free the node and advance
+            void *next = n->next;
+            cxFree(list->collection.allocator, n);
+            n = next;
+        }
+    }
+
+    return removed;
 }
 
 static void cx_ll_clear(struct cx_list_s *list) {
@@ -777,7 +814,7 @@
 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
 #define CX_LINKED_LIST_SWAP_SBO_SIZE 128
 #endif
-unsigned cx_linked_list_swap_sbo_size = CX_LINKED_LIST_SWAP_SBO_SIZE;
+const unsigned cx_linked_list_swap_sbo_size = CX_LINKED_LIST_SWAP_SBO_SIZE;
 
 static int cx_ll_swap(
         struct cx_list_s *list,
@@ -798,7 +835,7 @@
         left = j;
         right = i;
     }
-    cx_linked_list_node *nleft, *nright;
+    cx_linked_list_node *nleft = NULL, *nright = NULL;
     if (left < mid && right < mid) {
         // case 1: both items left from mid
         nleft = cx_ll_node_at(ll, left);