Mercurial > hg > dav / file diff

--- a/ucx/array_list.c	Mon Jan 06 21:18:56 2025 +0100
+++ b/ucx/array_list.c	Sun Feb 23 13:11:32 2025 +0100
@@ -856,32 +856,42 @@
     }
 }
 
-static ssize_t cx_arl_find_remove(
+static size_t cx_arl_find_remove(
         struct cx_list_s *list,
         const void *elem,
         bool remove
 ) {
+    assert(list != NULL);
     assert(list->collection.cmpfunc != NULL);
-    assert(list->collection.size < SIZE_MAX / 2);
+    if (list->collection.size == 0) return 0;
     char *cur = ((const cx_array_list *) list)->data;
 
-    for (ssize_t i = 0; i < (ssize_t) list->collection.size; i++) {
+    // optimize with binary search, when sorted
+    if (list->collection.sorted) {
+        size_t i = cx_array_binary_search(
+            cur,
+            list->collection.size,
+            list->collection.elem_size,
+            elem,
+            list->collection.cmpfunc
+        );
+        if (remove && i < list->collection.size) {
+            cx_arl_remove(list, i, 1, NULL);
+        }
+        return i;
+    }
+
+    // fallback: linear search
+    for (size_t i = 0; i < list->collection.size; i++) {
         if (0 == list->collection.cmpfunc(elem, cur)) {
             if (remove) {
-                if (1 == cx_arl_remove(list, i, 1, NULL)) {
-                    return i;
-                } else {
-                    // should be unreachable
-                    return -1;  // LCOV_EXCL_LINE
-                }
-            } else {
-                return i;
+                cx_arl_remove(list, i, 1, NULL);
             }
+            return i;
         }
         cur += list->collection.elem_size;
     }
-
-    return -1;
+    return list->collection.size;
 }
 
 static void cx_arl_sort(struct cx_list_s *list) {
@@ -1013,22 +1023,13 @@
 
     cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
     if (list == NULL) return NULL;
-
-    list->base.cl = &cx_array_list_class;
-    list->base.collection.allocator = allocator;
+    cx_list_init((CxList*)list, &cx_array_list_class,
+        allocator, comparator, elem_size);
     list->capacity = initial_capacity;
 
-    if (elem_size > 0) {
-        list->base.collection.elem_size = elem_size;
-        list->base.collection.cmpfunc = comparator;
-    } else {
-        elem_size = sizeof(void *);
-        list->base.collection.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator;
-        cxListStorePointers((CxList *) list);
-    }
-
     // allocate the array after the real elem_size is known
-    list->data = cxCalloc(allocator, initial_capacity, elem_size);
+    list->data = cxCalloc(allocator, initial_capacity,
+        list->base.collection.elem_size);
     if (list->data == NULL) { // LCOV_EXCL_START
         cxFree(allocator, list);
         return NULL;