Mercurial > hg > toolkit / file diff

--- a/ucx/linked_list.c	Sun Feb 11 15:44:33 2024 +0100
+++ b/ucx/linked_list.c	Sun Feb 11 22:06:23 2024 +0100
@@ -28,6 +28,7 @@
 
 #include "cx/linked_list.h"
 #include "cx/utils.h"
+#include "cx/compare.h"
 #include <string.h>
 #include <assert.h>
 
@@ -63,6 +64,23 @@
         cx_compare_func cmp_func,
         void const *elem
 ) {
+    void *dummy;
+    return cx_linked_list_find_node(
+            &dummy, start,
+            loc_advance, loc_data,
+            cmp_func, elem
+    );
+}
+
+ssize_t cx_linked_list_find_node(
+        void **result,
+        void const *start,
+        ptrdiff_t loc_advance,
+        ptrdiff_t loc_data,
+        cx_compare_func cmp_func,
+        void const *elem
+) {
+    assert(result != NULL);
     assert(start != NULL);
     assert(loc_advance >= 0);
     assert(loc_data >= 0);
@@ -73,11 +91,13 @@
     do {
         void *current = ll_data(node);
         if (cmp_func(current, elem) == 0) {
+            *result = (void*) node;
             return index;
         }
         node = ll_advance(node);
         index++;
     } while (node != NULL);
+    *result = NULL;
     return -1;
 }
 
@@ -460,8 +480,6 @@
 
 // HIGH LEVEL LINKED LIST IMPLEMENTATION
 
-bool CX_DISABLE_LINKED_LIST_SWAP_SBO = false;
-
 typedef struct cx_linked_list_node cx_linked_list_node;
 struct cx_linked_list_node {
     cx_linked_list_node *prev;
@@ -609,6 +627,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;
 
 static int cx_ll_swap(
         struct cx_list_s *list,
@@ -633,6 +652,7 @@
     if (left < mid && right < mid) {
         // case 1: both items left from mid
         nleft = cx_ll_node_at(ll, left);
+        assert(nleft != NULL);
         nright = nleft;
         for (size_t c = left; c < right; c++) {
             nright = nright->next;
@@ -640,6 +660,7 @@
     } else if (left >= mid && right >= mid) {
         // case 2: both items right from mid
         nright = cx_ll_node_at(ll, right);
+        assert(nright != NULL);
         nleft = nright;
         for (size_t c = right; c > left; c--) {
             nleft = nleft->prev;
@@ -686,7 +707,7 @@
         }
     }
 
-    if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) {
+    if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE) {
         cx_linked_list_node *prev = nleft->prev;
         cx_linked_list_node *next = nright->next;
         cx_linked_list_node *midstart = nleft->next;
@@ -735,13 +756,35 @@
     return node == NULL ? NULL : node->payload;
 }
 
-static ssize_t cx_ll_find(
-        struct cx_list_s const *list,
-        void const *elem
+static ssize_t cx_ll_find_remove(
+        struct cx_list_s *list,
+        void const *elem,
+        bool remove
 ) {
-    return cx_linked_list_find(((cx_linked_list *) list)->begin,
-                               CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
-                               list->cmpfunc, elem);
+    if (remove) {
+        cx_linked_list *ll = ((cx_linked_list *) list);
+        cx_linked_list_node *node;
+        ssize_t index = cx_linked_list_find_node(
+                (void **) &node,
+                ll->begin,
+                CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
+                list->cmpfunc, elem
+        );
+        if (node != NULL) {
+            cx_invoke_destructor(list, node->payload);
+            cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
+                                  CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
+            list->size--;
+            cxFree(list->allocator, node);
+        }
+        return index;
+    } else {
+        return cx_linked_list_find(
+                ((cx_linked_list *) list)->begin,
+                CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
+                list->cmpfunc, elem
+        );
+    }
 }
 
 static void cx_ll_sort(struct cx_list_s *list) {
@@ -894,7 +937,7 @@
         cx_ll_clear,
         cx_ll_swap,
         cx_ll_at,
-        cx_ll_find,
+        cx_ll_find_remove,
         cx_ll_sort,
         cx_ll_compare,
         cx_ll_reverse,
@@ -915,11 +958,12 @@
 
     list->base.cl = &cx_linked_list_class;
     list->base.allocator = allocator;
-    list->base.cmpfunc = comparator;
 
     if (item_size > 0) {
         list->base.item_size = item_size;
+        list->base.cmpfunc = comparator;
     } else {
+        list->base.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator;
         cxListStorePointers((CxList *) list);
     }