Mercurial > hg > ucx / changeset

--- a/docs/Writerside/topics/array_list.h.md	Thu Dec 18 18:07:29 2025 +0100
+++ b/docs/Writerside/topics/array_list.h.md	Fri Dec 19 12:40:58 2025 +0100
@@ -118,6 +118,28 @@
 > with `cx_array_copy_to_new()` or `cx_array_copy_to_new_a()` before adding or inserting more elements.
 >{style="note"}
 
+## Remove Elements
+
+```C
+#include <cx/array_list.h>
+
+void cx_array_remove(CxArray array, size_t index);
+
+void cx_array_remove_fast(CxArray array, size_t index);
+
+void cx_array_remove_array(CxArray array, size_t index, size_t n);
+
+void cx_array_remove_array_fast(CxArray array, size_t index, size_t n);
+```
+
+The functions `cx_array_remove()` and `cx_array_remove_array()` remove one or more elements from the array by shifting the remaining elements by the number of removed elements.
+The functions `cx_array_remove_fast()` and `cx_array_remove_array_fast()` on the other hand copy elements from the end of the array into the gap to fill the removed elements.
+Therefore, if the order of the elements does not matter, you can use the fast versions of these functions for better performance.
+
+> When you specify an `index` that is out-of-bounds or choose a number `n` of elements that would overflow the array,
+> the above functions only remove as many elements as possible.
+> So it's safe to use them without any bounds checking.
+
 ## Sorting
 
 ```C

--- a/src/array_list.c	Thu Dec 18 18:07:29 2025 +0100
+++ b/src/array_list.c	Fri Dec 19 12:40:58 2025 +0100
@@ -390,6 +390,50 @@
     return cxIteratorPtr(array->data, array->size);
 }
 
+void cx_array_remove_(CxArray *array, size_t elem_size, size_t index, size_t n, bool fast) {
+    if (n == 0) return;
+    if (index >= array->size) return;
+    if (index + n >= array->size) {
+        // only tail elements are removed
+        array->size = index;
+        return;
+    }
+    array->size -= n;
+    size_t remaining = array->size - index;
+    char *dest = ((char*)array->data) + index * elem_size;
+    if (fast) {
+        char *src = dest + remaining * elem_size;
+        if (n == 1 && elem_size <= CX_WORDSIZE/8) {
+            // try to optimize int-sized values
+            // (from likely to unlikely)
+            if (elem_size == sizeof(int32_t)) {
+                *(int32_t*)dest = *(int32_t*)src;
+                return;
+            }
+#if CX_WORDSIZE == 64
+            if (elem_size == sizeof(int64_t)) {
+                *(int64_t*)dest = *(int64_t*)src;
+                return;
+            }
+#endif
+            if (elem_size == sizeof(int8_t)) {
+                *(int8_t*)dest = *(int8_t*)src;
+                return;
+            }
+            if (elem_size == sizeof(int16_t)) {
+                *(int16_t*)dest = *(int16_t*)src;
+                return;
+            }
+            // note we cannot optimize the last branch, because
+            // the elem_size could be crazily misaligned
+        }
+        memcpy(dest, src, n * elem_size);
+    } else {
+        char *src = dest + n * elem_size;
+        memmove(dest, src, remaining * elem_size);
+    }
+}
+
 void cx_array_free_(const CxAllocator *allocator, CxArray *array) {
     cxFree(allocator, array->data);
     array->data = NULL;
@@ -785,10 +829,9 @@
     }
 
     // just move the elements to the left
-    char *first_remaining = arl->data;
-    first_remaining += (index + remove) * list->collection.elem_size;
     char *dst_move = arl->data;
     dst_move += index * list->collection.elem_size;
+    char *first_remaining = dst_move + remove * list->collection.elem_size;
     memmove(dst_move, first_remaining, remaining * list->collection.elem_size);
 
     // decrease the size

--- a/src/cx/array_list.h	Thu Dec 18 18:07:29 2025 +0100
+++ b/src/cx/array_list.h	Fri Dec 19 12:40:58 2025 +0100
@@ -786,6 +786,9 @@
  *
  * The iterator will yield pointers to the elements.
  *
+ * This iterator cannot be used to remove elements
+ * because it does not get a modifiable reference to the array's size.
+ *
  * @param array the name of the array
  * @return an iterator over the elements
  * @see cx_array_iterator_ptr()
@@ -810,6 +813,9 @@
  * The iterator will yield the elements themselves, which are supposed to
  * be pointers.
  *
+ * This iterator cannot be used to remove elements
+ * because it does not get a modifiable reference to the array's size.
+ *
  * @param array the name of the array
  * @return an iterator over the elements
  * @see cx_array_iterator()
@@ -817,6 +823,87 @@
 #define cx_array_iterator_ptr(array) \
         cx_array_iterator_ptr_((CxArray*)&(array))
 
+
+/**
+ * Removes elements from the array.
+ *
+ * Internal function - do not use.
+ *
+ * @param array a pointer to the array structure
+ * @param elem_size the size of one element
+ * @param index the index of the first element to remove
+ * @param n the number of elements to remove
+ * @param fast indicates whether tail elements should be copied into the gap
+ */
+cx_attr_nonnull
+CX_EXPORT void cx_array_remove_(CxArray *array, size_t elem_size, size_t index, size_t n, bool fast);
+
+/**
+ * Removes one element from the array.
+ *
+ * Tail elements are all moved by one. If you don't need a stable order
+ * in the array, consider using cx_array_remove_fast().
+ *
+ * If the index is out of bounds, this function does nothing.
+ *
+ * @param array the name of the array
+ * @param index (@c size_t) the index of the element to remove
+ * @see cx_array_remove_fast()
+ */
+#define cx_array_remove(array, index) \
+        cx_array_remove_((CxArray*)&(array), sizeof((array).data[0]), index, 1, false)
+
+/**
+ * Removes one element from the array.
+ *
+ * The gap will be filled with a copy of the last element in the array.
+ * This changes the order of elements. If you want a stable order,
+ * use cx_array_remove() instead.
+ *
+ * If the index is out of bounds, this function does nothing.
+ *
+ * @param array the name of the array
+ * @param index (@c size_t) the index of the element to remove
+ * @see cx_array_remove()
+ */
+#define cx_array_remove_fast(array, index) \
+        cx_array_remove_((CxArray*)&(array), sizeof((array).data[0]), index, 1, true)
+
+/**
+ * Removes multiple elements from the array.
+ *
+ * Tail elements are all moved to close the gap. If you don't need a stable
+ * order in the array, consider using cx_array_remove_array_fast().
+ *
+ * If the index is out of bounds, this function does nothing.
+ * If @n overflows the array, this function removes as many elements as it can.
+ *
+ * @param array the name of the array
+ * @param index (@c size_t) the index of the first element to remove
+ * @param n (@c size_t) the number of elements to remove
+ * @see cx_array_remove_array_fast()
+ */
+#define cx_array_remove_array(array, index, n) \
+        cx_array_remove_((CxArray*)&(array), sizeof((array).data[0]), index, n, false)
+
+/**
+ * Removes multiple elements from the array.
+ *
+ * Tail elements are copied into the gap. If you have more tail elements
+ * than the number of elements that are removed, this will change the order
+ * of elements. If you want a stable order, use cx_array_remove_array() instead.
+ *
+ * If the index is out of bounds, this function does nothing.
+ * If @n overflows the array, this function removes as many elements as it can.
+ *
+ * @param array the name of the array
+ * @param index (@c size_t) the index of the first element to remove
+ * @param n (@c size_t) the number of elements to remove
+ * @see cx_array_remove_array()
+ */
+#define cx_array_remove_array_fast(array, index, n) \
+        cx_array_remove_((CxArray*)&(array), sizeof((array).data[0]), index, n, true)
+
 /**
  * Deallocates an array.
  *

--- a/src/json.c	Thu Dec 18 18:07:29 2025 +0100
+++ b/src/json.c	Fri Dec 19 12:40:58 2025 +0100
@@ -1083,12 +1083,7 @@
         return NULL;
     }
     CxJsonValue *ret = value->array.data[index];
-    // TODO: replace with a low level cx_array_remove()
-    size_t count = value->array.size - index - 1;
-    if (count > 0) {
-        memmove(value->array.data + index, value->array.data + index + 1, count * sizeof(CxJsonValue*));
-    }
-    value->array.size--;
+    cx_array_remove(value->array, index);
     return ret;
 }
 

--- a/tests/test_list.c	Thu Dec 18 18:07:29 2025 +0100
+++ b/tests/test_list.c	Fri Dec 19 12:40:58 2025 +0100
@@ -74,6 +74,166 @@
     cx_array_free(arr);
 }
 
+CX_TEST(test_array_remove) {
+    CX_ARRAY(int, arr);
+    cx_array_init(arr, 5);
+    arr.data[0] = 2;
+    arr.data[1] = 3;
+    arr.data[2] = 5;
+    arr.data[3] = 7;
+    arr.data[4] = 11;
+    arr.size = 5;
+    int expected[5];
+    const size_t len = 5*sizeof(int);
+    memcpy(expected, arr.data, len);
+    CX_TEST_DO {
+        // out-of-bounds
+        cx_array_remove(arr, 7);
+        CX_TEST_ASSERT(arr.capacity == 5);
+        CX_TEST_ASSERT(arr.size == 5);
+        CX_TEST_ASSERT(0 == memcmp(arr.data, expected, len));
+
+        // remove mid
+        cx_array_remove(arr, 2);
+        CX_TEST_ASSERT(arr.capacity == 5);
+        CX_TEST_ASSERT(arr.size == 4);
+        expected[2] = 7;
+        expected[3] = 11;
+        expected[4] = 11; // not cleared
+        CX_TEST_ASSERT(0 == memcmp(arr.data, expected, len));
+
+        // remove end
+        cx_array_remove(arr, 3);
+        CX_TEST_ASSERT(arr.capacity == 5);
+        CX_TEST_ASSERT(arr.size == 3);
+        CX_TEST_ASSERT(0 == memcmp(arr.data, expected, len));
+    }
+    cx_array_free(arr);
+}
+
+CX_TEST(test_array_remove_fast) {
+    CX_ARRAY(int, arr);
+    cx_array_init(arr, 5);
+    arr.data[0] = 2;
+    arr.data[1] = 3;
+    arr.data[2] = 5;
+    arr.data[3] = 7;
+    arr.data[4] = 11;
+    arr.size = 5;
+    int expected[5];
+    const size_t len = 5*sizeof(int);
+    memcpy(expected, arr.data, len);
+    CX_TEST_DO {
+        // out-of-bounds
+        cx_array_remove_fast(arr, 7);
+        CX_TEST_ASSERT(arr.capacity == 5);
+        CX_TEST_ASSERT(arr.size == 5);
+        CX_TEST_ASSERT(0 == memcmp(arr.data, expected, len));
+
+        // remove mid
+        cx_array_remove_fast(arr, 2);
+        CX_TEST_ASSERT(arr.capacity == 5);
+        CX_TEST_ASSERT(arr.size == 4);
+        expected[2] = 11;
+        expected[3] = 7;
+        expected[4] = 11; // not cleared
+        CX_TEST_ASSERT(0 == memcmp(arr.data, expected, len));
+
+        // remove end
+        cx_array_remove_fast(arr, 3);
+        CX_TEST_ASSERT(arr.capacity == 5);
+        CX_TEST_ASSERT(arr.size == 3);
+        CX_TEST_ASSERT(0 == memcmp(arr.data, expected, len));
+    }
+    cx_array_free(arr);
+}
+
+CX_TEST(test_array_remove_array) {
+    CX_ARRAY(int, arr);
+    cx_array_init(arr, 10);
+    arr.data[0] = 2;
+    arr.data[1] = 3;
+    arr.data[2] = 5;
+    arr.data[3] = 7;
+    arr.data[4] = 11;
+    arr.data[5] = 47;
+    arr.data[6] = 80;
+    arr.data[7] = 104;
+    arr.data[8] = 250;
+    arr.data[9] = 999;
+    arr.size = 10;
+    int expected[10];
+    const size_t len = 5*sizeof(int);
+    memcpy(expected, arr.data, len);
+    CX_TEST_DO {
+        // completely out-of-bounds
+        cx_array_remove_array(arr, 10, 3);
+        CX_TEST_ASSERT(arr.capacity == 10);
+        CX_TEST_ASSERT(arr.size == 10);
+        CX_TEST_ASSERT(0 == memcmp(arr.data, expected, len));
+
+        // somewhere in the middle
+        cx_array_remove_array(arr, 2, 3);
+        CX_TEST_ASSERT(arr.capacity == 10);
+        CX_TEST_ASSERT(arr.size == 7);
+        expected[2] = 47;
+        expected[3] = 80;
+        expected[4] = 104;
+        expected[5] = 250;
+        expected[6] = 999;
+        CX_TEST_ASSERT(0 == memcmp(arr.data, expected, len));
+
+        // partially out-of-bounds
+        cx_array_remove_array(arr, 5, 4);
+        CX_TEST_ASSERT(arr.capacity == 10);
+        CX_TEST_ASSERT(arr.size == 5);
+        CX_TEST_ASSERT(0 == memcmp(arr.data, expected, len));
+    }
+    cx_array_free(arr);
+}
+
+CX_TEST(test_array_remove_array_fast) {
+    CX_ARRAY(int, arr);
+    cx_array_init(arr, 10);
+    arr.data[0] = 2;
+    arr.data[1] = 3;
+    arr.data[2] = 5;
+    arr.data[3] = 7;
+    arr.data[4] = 11;
+    arr.data[5] = 47;
+    arr.data[6] = 80;
+    arr.data[7] = 104;
+    arr.data[8] = 250;
+    arr.data[9] = 999;
+    arr.size = 10;
+    int expected[10];
+    const size_t len = 5*sizeof(int);
+    memcpy(expected, arr.data, len);
+    CX_TEST_DO {
+        // completely out-of-bounds
+        cx_array_remove_array_fast(arr, 10, 3);
+        CX_TEST_ASSERT(arr.capacity == 10);
+        CX_TEST_ASSERT(arr.size == 10);
+        CX_TEST_ASSERT(0 == memcmp(arr.data, expected, len));
+
+        // somewhere in the middle
+        cx_array_remove_array_fast(arr, 2, 3);
+        CX_TEST_ASSERT(arr.capacity == 10);
+        CX_TEST_ASSERT(arr.size == 7);
+        expected[2] = 104;
+        expected[3] = 250;
+        expected[4] = 999;
+        CX_TEST_ASSERT(0 == memcmp(arr.data, expected, len));
+
+        // partially out-of-bounds
+        cx_array_remove_array_fast(arr, 5, 4);
+        CX_TEST_ASSERT(arr.capacity == 10);
+        CX_TEST_ASSERT(arr.size == 5);
+        CX_TEST_ASSERT(0 == memcmp(arr.data, expected, len));
+    }
+    cx_array_free(arr);
+}
+
 CX_TEST(test_array_reserve) {
     CX_ARRAY(int, arr);
     cx_array_init(arr, 5);
@@ -3277,10 +3437,14 @@
     cxListFree(array_list);
 }
 
-CxTestSuite *cx_test_suite_array_list(void) {
-    CxTestSuite *suite = cx_test_suite_new("array_list");
+CxTestSuite *cx_test_suite_array(void) {
+    CxTestSuite *suite = cx_test_suite_new("array (low-level)");
 
     cx_test_register(suite, test_array_add);
+    cx_test_register(suite, test_array_remove);
+    cx_test_register(suite, test_array_remove_fast);
+    cx_test_register(suite, test_array_remove_array);
+    cx_test_register(suite, test_array_remove_array_fast);
     cx_test_register(suite, test_array_reserve);
     cx_test_register(suite, test_array_copy_to_new);
     cx_test_register(suite, test_array_insert_sorted);
@@ -3288,6 +3452,12 @@
     cx_test_register(suite, test_array_binary_search);
     cx_test_register(suite, test_array_binary_search_with_duplicates);
 
+    return suite;
+}
+
+CxTestSuite *cx_test_suite_array_list(void) {
+    CxTestSuite *suite = cx_test_suite_new("array_list");
+
     cx_test_register(suite, test_list_arl_create);
     cx_test_register(suite, test_list_arl_create_simple);
     cx_test_register(suite, test_list_arl_create_simple_for_pointers);

--- a/tests/ucxtest.c	Thu Dec 18 18:07:29 2025 +0100
+++ b/tests/ucxtest.c	Fri Dec 19 12:40:58 2025 +0100
@@ -42,6 +42,7 @@
 CxTestSuite *cx_test_suite_hash_map(void);
 CxTestSuite *cx_test_suite_iterator(void);
 CxTestSuite *cx_test_suite_empty_list(void);
+CxTestSuite *cx_test_suite_array(void);
 CxTestSuite *cx_test_suite_array_list(void);
 CxTestSuite *cx_test_suite_array_list_defaulted_funcs(void);
 CxTestSuite *cx_test_suite_linked_list(void);
@@ -57,7 +58,7 @@
 CxTestSuite *cx_test_suite_printf(void);
 CxTestSuite *cx_test_suite_mempool(void);
 
-#define break_on_failure true
+#define break_on_failure false
 #define run_tests(suite) cx_test_run_stdout(suite); success += (suite)->success; failure += (suite)->failure; \
     if (!cx_testing_allocator_verify(&testing_allocator) || (break_on_failure && failure > 0)) break;
 #define execute_test_suites(...) unsigned success = 0, failure = 0; CxTestSuite* test_suites[] = {__VA_ARGS__}; \
@@ -98,6 +99,7 @@
             cx_test_suite_hash_map(),
             cx_test_suite_iterator(),
             cx_test_suite_empty_list(),
+            cx_test_suite_array(),
             cx_test_suite_array_list(),
             cx_test_suite_array_list_defaulted_funcs(),
             cx_test_suite_linked_list(),