# HG changeset patch # User Mike Becker # Date 1766144458 -3600 # Node ID a2565f9fc6debd321f306632acb4bc35c7264677 # Parent 89a2d53308e4d0955f70a58cdff1017e8992f32b add cx_array_remove() and cx_array_remove_fast() relates to #787 and relates to #619 diff -r 89a2d53308e4 -r a2565f9fc6de docs/Writerside/topics/array_list.h.md --- 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 + +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 diff -r 89a2d53308e4 -r a2565f9fc6de src/array_list.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 diff -r 89a2d53308e4 -r a2565f9fc6de src/cx/array_list.h --- 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. * diff -r 89a2d53308e4 -r a2565f9fc6de src/json.c --- 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; } diff -r 89a2d53308e4 -r a2565f9fc6de tests/test_list.c --- 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); diff -r 89a2d53308e4 -r a2565f9fc6de tests/ucxtest.c --- 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(),