# HG changeset patch # User Mike Becker # Date 1758386055 -7200 # Node ID a2cfbff39e5df58817c50ccb5b1978dfea1d0c3f # Parent 3db28cb1e5eca7574c9708604f08f55bf4b3c5d5 implement non-mutating iterator relates to #461 diff -r 3db28cb1e5ec -r a2cfbff39e5d src/kv_list.c --- a/src/kv_list.c Sat Sep 20 12:30:07 2025 +0200 +++ b/src/kv_list.c Sat Sep 20 18:34:15 2025 +0200 @@ -31,6 +31,7 @@ #include "cx/linked_list.h" #include +#include typedef struct cx_kv_list_s cx_kv_list; @@ -350,9 +351,110 @@ return 0; } +static void *cx_kvl_iter_current_entry(const void *it) { + const CxMapIterator *iter = it; + return (void*)&iter->entry; +} + +static void *cx_kvl_iter_current_key(const void *it) { + const CxMapEntry *entry = cx_kvl_iter_current_entry(it); + return (void*)entry->key; +} + +static void *cx_kvl_iter_current_value(const void *it) { + const CxMapEntry *entry = cx_kvl_iter_current_entry(it); + return entry->value; +} + +static void cx_kvl_iter_next(void *it) { + CxMapIterator *iter = it; + cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)iter->map.m)->list; + + // find the next list entry that has a key assigned + CxHashKey *key = NULL; + char *next = iter->elem; + while (true) { + next = *(char**)(next + kv_list->list.loc_next); + if (next == NULL) break; + key = cx_kv_list_loc_key(kv_list, next + kv_list->list.loc_data); + if (key->hash != 0) break; + } + if (next == NULL) { + iter->index = kv_list->list.base.collection.size; + iter->elem = NULL; + iter->entry = (CxMapEntry){NULL, NULL}; + return; + } + + // TODO: implement removal + + // advance to the next element + iter->index++; + iter->elem = next; + iter->entry.key = key; + if (kv_list->list.base.collection.store_pointer) { + iter->entry.value = *(void**)(next + kv_list->list.loc_data); + } else { + iter->entry.value = (void*)(next + kv_list->list.loc_data); + } +} + +static bool cx_kvl_iter_valid(const void *it) { + const CxMapIterator *iter = it; + return iter->elem != NULL; +} + CxMapIterator cx_kvl_map_iterator(const CxMap *map, enum cx_map_iterator_type type) { + CxMapIterator iter = {}; + + iter.type = type; + iter.map.c = map; + // although we iterate over the list, we only report that many elements that have a key in the map + iter.elem_count = map->collection.size; + + switch (type) { + case CX_MAP_ITERATOR_PAIRS: + iter.elem_size = sizeof(CxMapEntry); + iter.base.current = cx_kvl_iter_current_entry; + break; + case CX_MAP_ITERATOR_KEYS: + iter.elem_size = sizeof(CxHashKey); + iter.base.current = cx_kvl_iter_current_key; + break; + case CX_MAP_ITERATOR_VALUES: + iter.elem_size = map->collection.elem_size; + iter.base.current = cx_kvl_iter_current_value; + break; + default: + assert(false); // LCOV_EXCL_LINE + } + + iter.base.next = cx_kvl_iter_next; + iter.base.valid = cx_kvl_iter_valid; + + // find the first list entry that has a key assigned cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list; - return kv_list->map_methods->iterator(map, type); + CxHashKey *key = NULL; + char *next = kv_list->list.begin; + while (next != NULL) { + key = cx_kv_list_loc_key(kv_list, next + kv_list->list.loc_data); + if (key->hash != 0) break; + next = *(char**)(next + kv_list->list.loc_next); + } + if (next == NULL) { + iter.elem = NULL; + iter.entry = (CxMapEntry){NULL, NULL}; + } else { + iter.elem = next; + iter.entry.key = key; + if (kv_list->list.base.collection.store_pointer) { + iter.entry.value = *(void**)(next + kv_list->list.loc_data); + } else { + iter.entry.value = (void*)(next + kv_list->list.loc_data); + } + } + + return iter; } static cx_list_class cx_kv_list_class = { @@ -482,7 +584,7 @@ // add the key to the map; if (NULL == kv_list->map_methods->put(&kv_list->map->map_base.base, key, node_data)) { - return 1; + return 1; // LCOV_EXCL_LINE } // write the key to the list's node diff -r 3db28cb1e5ec -r a2cfbff39e5d tests/test_kv_list.c --- a/tests/test_kv_list.c Sat Sep 20 12:30:07 2025 +0200 +++ b/tests/test_kv_list.c Sat Sep 20 18:34:15 2025 +0200 @@ -808,6 +808,68 @@ cxMapFree(map); } +CX_TEST(test_kv_list_map_iterator) { + CxMap *map = cxKvListCreateAsMapSimple(sizeof(int)); + CX_TEST_DO { + int x; + x = 0xc0ffee; // this element shall be skipped + cxListAdd(cxKvListAsList(map), &x); + x = 815; + cxMapPut(map, "xyz", &x); + x = 8016; + cxMapPut(map, "abcd", &x); + x = 0xbeef; + cxListAdd(cxKvListAsList(map), &x); + x = 80017; + cxMapPut(map, "efghi", &x); + + const CxMapEntry *entry; + CxMapIterator it = cxMapIterator(map); + CX_TEST_ASSERT(it.elem_count == 3); + CX_TEST_ASSERT(it.elem_size == sizeof(CxMapEntry)); + + CX_TEST_ASSERT(cxIteratorValid(it)); + CX_TEST_ASSERT(it.index == 0); + entry = cxIteratorCurrent(it); + CX_TEST_ASSERT(*(int*)entry->value == 815); + CX_TEST_ASSERT(entry->key->len == 3); + CX_TEST_ASSERT(strncmp(entry->key->data, "xyz", 3) == 0); + + cxIteratorNext(it); + CX_TEST_ASSERT(cxIteratorValid(it)); + CX_TEST_ASSERT(it.index == 1); + entry = cxIteratorCurrent(it); + CX_TEST_ASSERT(*(int*)entry->value == 8016); + CX_TEST_ASSERT(entry->key->len == 4); + CX_TEST_ASSERT(strncmp(entry->key->data, "abcd", 4) == 0); + + cxIteratorNext(it); + CX_TEST_ASSERT(cxIteratorValid(it)); + CX_TEST_ASSERT(it.index == 2); + entry = cxIteratorCurrent(it); + CX_TEST_ASSERT(*(int*)entry->value == 80017); + CX_TEST_ASSERT(entry->key->len == 5); + CX_TEST_ASSERT(strncmp(entry->key->data, "efghi", 5) == 0); + + cxIteratorNext(it); + CX_TEST_ASSERT(!cxIteratorValid(it)); + + // remove the first element (which was skipped anyway) and try again + cxListRemove(cxKvListAsList(map), 0); + it = cxMapIterator(map); + CX_TEST_ASSERT(it.elem_count == 3); + CX_TEST_ASSERT(it.elem_size == sizeof(CxMapEntry)); + + CX_TEST_ASSERT(cxIteratorValid(it)); + CX_TEST_ASSERT(it.index == 0); + entry = cxIteratorCurrent(it); + CX_TEST_ASSERT(*(int*)entry->value == 815); + CX_TEST_ASSERT(entry->key->len == 3); + CX_TEST_ASSERT(strncmp(entry->key->data, "xyz", 3) == 0); + } + cxMapFree(map); +} + CxTestSuite *cx_test_suite_kv_list_specifics(void) { CxTestSuite *suite = cx_test_suite_new("kv_list specifics"); @@ -844,6 +906,7 @@ cx_test_register(suite, test_kv_list_map_clear_destr_in_list); cx_test_register(suite, test_kv_list_map_clear_destr_in_map); cx_test_register(suite, test_kv_list_destr_ptr); + cx_test_register(suite, test_kv_list_map_iterator); return suite; }