# HG changeset patch # User Mike Becker # Date 1716469524 -7200 # Node ID b2bc48c2b251079f59c7d7ae6a784332e947dfb5 # Parent edb9f875b7f9ed4f6aa03c3132c916291614d87d add iterator over raw C arrays - closes #389 diff -r edb9f875b7f9 -r b2bc48c2b251 CHANGELOG --- a/CHANGELOG Fri Apr 12 21:48:12 2024 +0200 +++ b/CHANGELOG Thu May 23 15:05:24 2024 +0200 @@ -1,6 +1,7 @@ Version 3.1 - tbd. ------------------------ * adds tree.h + * adds cxIterator() to create iterators over raw C arrays * adds cx_array_default_reallocator * adds several new cx_array_*() functions * adds cx_linked_list_find_node() diff -r edb9f875b7f9 -r b2bc48c2b251 src/Makefile --- a/src/Makefile Fri Apr 12 21:48:12 2024 +0200 +++ b/src/Makefile Thu May 23 15:05:24 2024 +0200 @@ -24,7 +24,8 @@ include ../config.mk SRC = allocator.c array_list.c buffer.c compare.c hash_key.c hash_map.c \ - linked_list.c list.c map.c tree.c mempool.c printf.c string.c utils.c + iterator.c linked_list.c list.c map.c mempool.c printf.c string.c tree.c \ + utils.c OBJ_EXT=.o OBJ=$(SRC:%.c=$(build_dir)/%$(OBJ_EXT)) @@ -89,6 +90,10 @@ @echo "Compiling $<" $(CC) -o $@ $(CFLAGS) -c $< +$(build_dir)/iterator$(OBJ_EXT): iterator.c cx/iterator.h cx/common.h + @echo "Compiling $<" + $(CC) -o $@ $(CFLAGS) -c $< + $(build_dir)/linked_list$(OBJ_EXT): linked_list.c cx/linked_list.h \ cx/common.h cx/list.h cx/collection.h cx/allocator.h cx/iterator.h \ cx/utils.h cx/compare.h diff -r edb9f875b7f9 -r b2bc48c2b251 src/array_list.c --- a/src/array_list.c Fri Apr 12 21:48:12 2024 +0200 +++ b/src/array_list.c Thu May 23 15:05:24 2024 +0200 @@ -503,6 +503,8 @@ iter.index = index; iter.src_handle = list; iter.elem_handle = cx_arl_at(list, index); + iter.elem_size = list->item_size; + iter.elem_count = list->size; iter.base.valid = cx_arl_iter_valid; iter.base.current = cx_arl_iter_current; iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next; diff -r edb9f875b7f9 -r b2bc48c2b251 src/cx/iterator.h --- a/src/cx/iterator.h Fri Apr 12 21:48:12 2024 +0200 +++ b/src/cx/iterator.h Thu May 23 15:05:24 2024 +0200 @@ -127,6 +127,17 @@ * Otherwise, this field is usually uninitialized. */ size_t index; + + /** + * The size of an individual element. + */ + size_t elem_size; + + /** + * May contain the total number of elements, if known. + * Shall be set to \c SIZE_MAX when the total number is unknown during iteration. + */ + size_t elem_count; }; /** @@ -191,6 +202,17 @@ * Otherwise, this field is usually uninitialized. */ size_t index; + + /** + * The size of an individual element. + */ + size_t elem_size; + + /** + * May contain the total number of elements, if known. + * Shall be set to \c SIZE_MAX when the total number is unknown during iteration. + */ + size_t elem_count; }; /** @@ -250,4 +272,36 @@ #define cx_foreach(type, elem, iter) \ for (type elem; cxIteratorValid(iter) && (elem = (type)cxIteratorCurrent(iter)) != NULL ; cxIteratorNext(iter)) + +/** + * Creates an iterator for the specified plain array. + * + * While the iterator is in use, the array may only be altered by removing + * elements through #cxIteratorFlagRemoval(). Every other change to the array + * will bring this iterator to an undefined state. + * + * When \p remove_keeps_order is set to \c false, removing an element will only + * move the last element to the position of the removed element, instead of + * moving all subsequent elements by one. Usually, when the order of elements is + * not important, this parameter should be set to \c false. + * + * The \p array can be \c NULL in which case the iterator will be immediately + * initialized such that #cxIteratorValid() returns \c false. + * + * + * @param array a pointer to the array (can be \c NULL) + * @param elem_size the size of one array element + * @param elem_count the number of elements in the array + * @param remove_keeps_order \c true if the order of elements must be preserved + * when removing an element + * @return an iterator for the specified array + */ +__attribute__((__warn_unused_result__)) +CxMutIterator cxIterator( // TODO: unify the iterator types + void *array, + size_t elem_size, + size_t elem_count, + bool remove_keeps_order +); + #endif // UCX_ITERATOR_H diff -r edb9f875b7f9 -r b2bc48c2b251 src/hash_map.c --- a/src/hash_map.c Fri Apr 12 21:48:12 2024 +0200 +++ b/src/hash_map.c Thu May 23 15:05:24 2024 +0200 @@ -333,23 +333,27 @@ CxIterator iter; iter.src_handle = map; - iter.base.valid = cx_hash_map_iter_valid; - iter.base.next = cx_hash_map_iter_next; + iter.elem_count = map->size; switch (type) { case CX_MAP_ITERATOR_PAIRS: + iter.elem_size = sizeof(CxMapEntry); iter.base.current = cx_hash_map_iter_current_entry; break; case CX_MAP_ITERATOR_KEYS: + iter.elem_size = sizeof(CxHashKey); iter.base.current = cx_hash_map_iter_current_key; break; case CX_MAP_ITERATOR_VALUES: + iter.elem_size = map->item_size; iter.base.current = cx_hash_map_iter_current_value; break; default: assert(false); } + iter.base.valid = cx_hash_map_iter_valid; + iter.base.next = cx_hash_map_iter_next; iter.base.remove = false; iter.base.mutating = false; diff -r edb9f875b7f9 -r b2bc48c2b251 src/iterator.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/iterator.c Thu May 23 15:05:24 2024 +0200 @@ -0,0 +1,106 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "cx/iterator.h" + +#include + +static bool cx_iter_valid(void const *it) { + struct cx_iterator_s const *iter = it; + return iter->index < iter->elem_count; +} + +static void *cx_iter_current(void const *it) { + struct cx_iterator_s const *iter = it; + return iter->elem_handle; +} + +static void cx_iter_next_fast(void *it) { + struct cx_iterator_base_s *itbase = it; + if (itbase->remove) { + struct cx_mut_iterator_s *iter = it; + itbase->remove = false; + iter->elem_count--; + // only move the last element when we are not currently aiming + // at the last element already + if (iter->index < iter->elem_count) { + void *last = ((char *) iter->src_handle) + + iter->elem_count * iter->elem_size; + memcpy(iter->elem_handle, last, iter->elem_size); + } + } else { + struct cx_iterator_s *iter = it; + iter->index++; + iter->elem_handle = ((char *) iter->elem_handle) + iter->elem_size; + } +} + +static void cx_iter_next_slow(void *it) { + struct cx_iterator_base_s *itbase = it; + if (itbase->remove) { + struct cx_mut_iterator_s *iter = it; + itbase->remove = false; + iter->elem_count--; + + // number of elements to move + size_t remaining = iter->elem_count - iter->index; + if (remaining > 0) { + memmove( + iter->elem_handle, + ((char *) iter->elem_handle) + iter->elem_size, + remaining * iter->elem_size + ); + } + } else { + struct cx_iterator_s *iter = it; + iter->index++; + iter->elem_handle = ((char *) iter->elem_handle) + iter->elem_size; + } +} + +CxMutIterator cxIterator( + void *array, + size_t elem_size, + size_t elem_count, + bool remove_keeps_order +) { + CxMutIterator iter; + + iter.index = 0; + iter.src_handle = array; + iter.elem_handle = array; + iter.elem_size = elem_size; + iter.elem_count = array == NULL ? 0 : elem_count; + iter.base.valid = cx_iter_valid; + iter.base.current = cx_iter_current; + iter.base.next = remove_keeps_order ? cx_iter_next_slow : cx_iter_next_fast; + iter.base.remove = false; + iter.base.mutating = true; + + return iter; +} diff -r edb9f875b7f9 -r b2bc48c2b251 src/linked_list.c --- a/src/linked_list.c Fri Apr 12 21:48:12 2024 +0200 +++ b/src/linked_list.c Thu May 23 15:05:24 2024 +0200 @@ -875,6 +875,8 @@ iter.index = index; iter.src_handle = list; iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index); + iter.elem_size = list->item_size; + iter.elem_count = list->size; iter.base.valid = cx_ll_iter_valid; iter.base.current = cx_ll_iter_current; iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next; diff -r edb9f875b7f9 -r b2bc48c2b251 tests/Makefile --- a/tests/Makefile Fri Apr 12 21:48:12 2024 +0200 +++ b/tests/Makefile Thu May 23 15:05:24 2024 +0200 @@ -28,8 +28,9 @@ TEST_DIR=$(build_dir)/tests SRC = util_allocator.c test_utils.c test_hash_key.c test_allocator.c \ - test_compare.c test_string.c test_buffer.c test_list.c test_tree.c \ - test_printf.c test_mempool.c test_hash_map.c ucxtest.c + test_compare.c test_string.c test_buffer.c test_iterator.c \ + test_list.c test_tree.c test_hash_map.c \ + test_printf.c test_mempool.c ucxtest.c OBJ_EXT=.o OBJ=$(SRC:%.c=$(TEST_DIR)/%$(OBJ_EXT)) @@ -77,6 +78,11 @@ @echo "Compiling $<" $(CC) -o $@ $(CFLAGS) -c $< +$(TEST_DIR)/test_iterator$(OBJ_EXT): test_iterator.c ../src/cx/test.h \ + ../src/cx/iterator.h ../src/cx/common.h + @echo "Compiling $<" + $(CC) -o $@ $(CFLAGS) -c $< + $(TEST_DIR)/test_list$(OBJ_EXT): test_list.c ../src/cx/test.h \ util_allocator.h ../src/cx/allocator.h ../src/cx/common.h \ ../src/cx/compare.h ../src/cx/utils.h ../src/cx/array_list.h \ diff -r edb9f875b7f9 -r b2bc48c2b251 tests/test_hash_map.c --- a/tests/test_hash_map.c Fri Apr 12 21:48:12 2024 +0200 +++ b/tests/test_hash_map.c Thu May 23 15:05:24 2024 +0200 @@ -545,6 +545,8 @@ { // collect the keys from the map iterator CxIterator keyiter = cxMapIteratorKeys(map); + CX_TEST_ASSERT(keyiter.elem_size == sizeof(CxHashKey)); + CX_TEST_ASSERT(keyiter.elem_count == map->size); CxHashKey *keys = calloc(map->size, sizeof(CxHashKey)); cx_foreach(CxHashKey*, elem, keyiter) { keys[keyiter.index] = *elem; @@ -564,6 +566,8 @@ // by using that the values in our test data are unique strings // we can re-use a similar approach as above CxIterator valiter = cxMapIteratorValues(map); + CX_TEST_ASSERT(valiter.elem_size == map->item_size); + CX_TEST_ASSERT(valiter.elem_count == map->size); char const** values = calloc(map->size, sizeof(char const*)); cx_foreach(char const*, elem, valiter) { values[valiter.index] = elem; @@ -586,6 +590,8 @@ // verify pair iterator { CxIterator pairiter = cxMapIterator(map); + CX_TEST_ASSERT(pairiter.elem_size == sizeof(CxMapEntry)); + CX_TEST_ASSERT(pairiter.elem_count == map->size); struct test_map_kv *pairs = calloc(map->size, sizeof(struct test_map_kv)); cx_foreach(CxMapEntry*, entry, pairiter) { CxHashKey const *key = entry->key; diff -r edb9f875b7f9 -r b2bc48c2b251 tests/test_iterator.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/test_iterator.c Thu May 23 15:05:24 2024 +0200 @@ -0,0 +1,178 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "cx/test.h" + +#include "cx/iterator.h" + +CX_TEST(test_iterator_create) { + size_t size = 20; + unsigned array[size]; + for (unsigned i = 0 ; i < size ; i++) array[i] = i; + + CxMutIterator iter = cxIterator(array, sizeof(unsigned), size, false); + CX_TEST_DO { + CX_TEST_ASSERT(iter.index == 0); + CX_TEST_ASSERT(iter.elem_size == sizeof(unsigned)); + CX_TEST_ASSERT(iter.elem_count == size); + CX_TEST_ASSERT(iter.src_handle == array); + CX_TEST_ASSERT(iter.elem_handle == &array[0]); + CX_TEST_ASSERT(cxIteratorValid(iter)); + } +} + +CX_TEST(test_iterator_create_null) { + CxMutIterator iter = cxIterator(NULL, sizeof(unsigned), 47, false); + CX_TEST_DO { + CX_TEST_ASSERT(iter.index == 0); + CX_TEST_ASSERT(iter.elem_size == sizeof(unsigned)); + CX_TEST_ASSERT(iter.elem_count == 0); + CX_TEST_ASSERT(iter.src_handle == NULL); + CX_TEST_ASSERT(iter.elem_handle == NULL); + CX_TEST_ASSERT(!cxIteratorValid(iter)); + } +} + +CX_TEST(test_iterator_iterate) { + size_t size = 20; + unsigned array[size]; + for (unsigned i = 0 ; i < size ; i++) array[i] = i; + + CxMutIterator iter = cxIterator(array, sizeof(unsigned), size, false); + CX_TEST_DO { + unsigned expected = 0; + cx_foreach(unsigned *, e, iter) { + CX_TEST_ASSERT(iter.index == expected); + CX_TEST_ASSERT(*e == expected); + CX_TEST_ASSERT(iter.elem_size == sizeof(unsigned)); + CX_TEST_ASSERT(iter.elem_count == size); + CX_TEST_ASSERT(iter.src_handle == array); + CX_TEST_ASSERT(iter.elem_handle == &array[expected]); + expected++; + } + CX_TEST_ASSERT(expected == size); + } +} + +CX_TEST(test_iterator_with_slow_remove) { + size_t size = 20; + unsigned array[size]; + for (unsigned i = 0 ; i < size ; i++) array[i] = i; + + size_t elem_counts[] = { + 20, 20, 19, 19, 18, 18, 17, 17, 16, 16, + 15, 15, 14, 14, 13, 13, 12, 12, 11, 11 + }; + size_t indices[] = { + 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, + 6, 6, 7, 7, 8, 8, 9, 9, 10 + }; + unsigned expected_result[] = { + 0, 2, 4, 6, 8, 10, 12, 14, 16, 18 + }; + + CxMutIterator iter = cxIterator(array, sizeof(unsigned), size, true); + CX_TEST_DO { + unsigned expected = 0; + cx_foreach(unsigned *, e, iter) { + CX_TEST_ASSERT(*e == expected); + CX_TEST_ASSERT(iter.index == indices[expected]); + CX_TEST_ASSERT(iter.elem_size == sizeof(unsigned)); + CX_TEST_ASSERT(iter.elem_count == elem_counts[expected]); + CX_TEST_ASSERT(iter.src_handle == array); + CX_TEST_ASSERT(iter.elem_handle == &array[indices[expected]]); + expected++; + if (expected % 2 == 0) { + cxIteratorFlagRemoval(iter); + } + } + CX_TEST_ASSERT(expected == 20); + CX_TEST_ASSERT(iter.index == 10); + CX_TEST_ASSERT(iter.elem_count == 10); + for (unsigned i = 0 ; i < 9 ; i++) { + CX_TEST_ASSERT(array[i] == expected_result[i]); + } + } +} + +CX_TEST(test_iterator_with_fast_remove) { + size_t size = 20; + unsigned array[size]; + for (unsigned i = 0 ; i < size ; i++) array[i] = i; + + size_t elem_counts[] = { + 20, 20, 19, 19, 18, 18, 17, 17, 16, 16, + 15, 15, 14, 14, 13, 13, 12, 12, 11, 11 + }; + size_t indices[] = { + 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, + 6, 6, 7, 7, 8, 8, 9, 9, 10 + }; + unsigned expected_result[] = { + 0, 19, 18, 17, 16, 15, 14, 13, 12, 11 + }; + unsigned expected_visits[] = { + 0, 1, 19, 2, 18, 3, 17, 4, 16, 5, + 15, 6, 14, 7, 13, 8, 12, 9, 11, 10 + }; + + CxMutIterator iter = cxIterator(array, sizeof(unsigned), size, false); + CX_TEST_DO { + unsigned expected = 0; + cx_foreach(unsigned *, e, iter) { + CX_TEST_ASSERT(*e == expected_visits[expected]); + CX_TEST_ASSERT(iter.index == indices[expected]); + CX_TEST_ASSERT(iter.elem_size == sizeof(unsigned)); + CX_TEST_ASSERT(iter.elem_count == elem_counts[expected]); + CX_TEST_ASSERT(iter.src_handle == array); + CX_TEST_ASSERT(iter.elem_handle == &array[indices[expected]]); + expected++; + if (expected % 2 == 0) { + cxIteratorFlagRemoval(iter); + } + } + CX_TEST_ASSERT(expected == 20); + CX_TEST_ASSERT(iter.index == 10); + CX_TEST_ASSERT(iter.elem_count == 10); + for (unsigned i = 0 ; i < 9 ; i++) { + CX_TEST_ASSERT(array[i] == expected_result[i]); + } + } +} + +CxTestSuite *cx_test_suite_iterator(void) { + CxTestSuite *suite = cx_test_suite_new("iterator"); + + cx_test_register(suite, test_iterator_create); + cx_test_register(suite, test_iterator_iterate); + cx_test_register(suite, test_iterator_with_slow_remove); + cx_test_register(suite, test_iterator_with_fast_remove); + + return suite; +} + diff -r edb9f875b7f9 -r b2bc48c2b251 tests/test_list.c --- a/tests/test_list.c Fri Apr 12 21:48:12 2024 +0200 +++ b/tests/test_list.c Thu May 23 15:05:24 2024 +0200 @@ -1207,6 +1207,8 @@ int *testdata = int_test_data_added_to_list(list, isptrlist, len); CxIterator iter = cxListIterator(list); + CX_TEST_ASSERT(iter.elem_size == list->item_size); + CX_TEST_ASSERT(iter.elem_count == list->size); size_t i = 0; cx_foreach(int*, x, iter) { CX_TEST_ASSERT(i == iter.index); @@ -1223,6 +1225,8 @@ CX_TEST_ASSERT(i == 0); i = len / 2; CxMutIterator mut_iter = cxListMutIteratorAt(list, i); + CX_TEST_ASSERT(mut_iter.elem_size == list->item_size); + CX_TEST_ASSERT(mut_iter.elem_count == list->size); size_t j = 0; cx_foreach(int*, x, mut_iter) { CX_TEST_ASSERT(mut_iter.index == len / 2 + j / 2); diff -r edb9f875b7f9 -r b2bc48c2b251 tests/ucxtest.c --- a/tests/ucxtest.c Fri Apr 12 21:48:12 2024 +0200 +++ b/tests/ucxtest.c Thu May 23 15:05:24 2024 +0200 @@ -36,6 +36,7 @@ CxTestSuite *cx_test_suite_string(void); CxTestSuite *cx_test_suite_buffer(void); CxTestSuite *cx_test_suite_printf(void); +CxTestSuite *cx_test_suite_iterator(void); CxTestSuite *cx_test_suite_empty_list(void); CxTestSuite *cx_test_suite_array_list(void); CxTestSuite *cx_test_suite_linked_list(void); @@ -60,6 +61,7 @@ cx_test_suite_string(), cx_test_suite_buffer(), cx_test_suite_printf(), + cx_test_suite_iterator(), cx_test_suite_empty_list(), cx_test_suite_array_list(), cx_test_suite_linked_list(),