# HG changeset patch # User Mike Becker # Date 1653124967 -7200 # Node ID 2946e13c89a415ca84a78ea2165ad6a8877f444f # Parent 89b2a83728b165956263a330a7a6da8388e2a727 #189 implement map iterators diff -r 89b2a83728b1 -r 2946e13c89a4 src/cx/common.h --- a/src/cx/common.h Thu May 19 14:30:20 2022 +0200 +++ b/src/cx/common.h Sat May 21 11:22:47 2022 +0200 @@ -100,7 +100,7 @@ /** * A pointer to the data. */ - unsigned const char *data; + unsigned char const *data; /** * The length of the data. */ diff -r 89b2a83728b1 -r 2946e13c89a4 src/cx/iterator.h --- a/src/cx/iterator.h Thu May 19 14:30:20 2022 +0200 +++ b/src/cx/iterator.h Sat May 21 11:22:47 2022 +0200 @@ -46,17 +46,20 @@ /** * True iff the iterator points to valid data. */ - bool (*valid)(struct cx_iterator_s const *) __attribute__ ((__nonnull__)); + __attribute__ ((__nonnull__)) + bool (*valid)(struct cx_iterator_s const *); /** * Returns a pointer to the current element. */ - void *(*current)(struct cx_iterator_s const *) __attribute__ ((__nonnull__)); + __attribute__ ((__nonnull__)) + void *(*current)(struct cx_iterator_s const *); /** * Advances the iterator. */ - void (*next)(struct cx_iterator_s *) __attribute__ ((__nonnull__)); + __attribute__ ((__nonnull__)) + void (*next)(struct cx_iterator_s *); /** * Handle for the current element, if required. @@ -69,6 +72,27 @@ void *src_handle; /** + * Field for storing a key-value pair. + * May be used by iterators that iterate over k/v-collections. + */ + struct { + /** + * A pointer to the key. + */ + void *key; + /** + * A pointer to the value. + */ + void *value; + } kv_data; + + /** + * Field for storing a slot number. + * May be used by iterators that iterate over multi-bucket collections. + */ + size_t slot; + + /** * If the iterator is position-aware, contains the index of the element in the underlying collection. * Otherwise, this field is usually uninitialized. */ diff -r 89b2a83728b1 -r 2946e13c89a4 src/cx/map.h --- a/src/cx/map.h Thu May 19 14:30:20 2022 +0200 +++ b/src/cx/map.h Sat May 21 11:22:47 2022 +0200 @@ -113,19 +113,19 @@ * Iterator over the key/value pairs. */ __attribute__((__nonnull__, __warn_unused_result__)) - CxIterator (*iterator)(CxMap const *map); + CxIterator (*iterator)(CxMap *map); /** * Iterator over the keys. */ __attribute__((__nonnull__, __warn_unused_result__)) - CxIterator (*iterator_keys)(CxMap const *map); + CxIterator (*iterator_keys)(CxMap *map); /** * Iterator over the values. */ __attribute__((__nonnull__, __warn_unused_result__)) - CxIterator (*iterator_values)(CxMap const *map); + CxIterator (*iterator_values)(CxMap *map); }; /** @@ -133,13 +133,13 @@ */ struct cx_map_entry_s { /** - * The key. + * A pointer to the key. */ - CxDataPtr key; + CxDataPtr const *key; /** - * The value. + * A pointer to the value. */ - void const *value; + void *value; }; @@ -224,7 +224,7 @@ * @return an iterator for the currently stored values */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxIterator cxMapIteratorValues(CxMap const *map) { +static inline CxIterator cxMapIteratorValues(CxMap *map) { return map->cl->iterator_values(map); } @@ -238,7 +238,7 @@ * @return an iterator for the currently stored keys */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxIterator cxMapIteratorKeys(CxMap const *map) { +static inline CxIterator cxMapIteratorKeys(CxMap *map) { return map->cl->iterator_keys(map); } @@ -256,7 +256,7 @@ * @see cxMapIteratorValues() */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxIterator cxMapIterator(CxMap const *map) { +static inline CxIterator cxMapIterator(CxMap *map) { return map->cl->iterator(map); } diff -r 89b2a83728b1 -r 2946e13c89a4 src/hash_map.c --- a/src/hash_map.c Thu May 19 14:30:20 2022 +0200 +++ b/src/hash_map.c Sat May 21 11:22:47 2022 +0200 @@ -175,6 +175,25 @@ return 0; } +static void cx_hash_map_unlink( + struct cx_hash_map_s *hash_map, + size_t slot, + struct cx_hash_map_element_s *prev, + struct cx_hash_map_element_s *elm +) { + // unlink + if (prev == NULL) { + hash_map->buckets[slot] = elm->next; + } else { + prev->next = elm->next; + } + // free element + cxFree(hash_map->base.allocator, elm->key.data); + cxFree(hash_map->base.allocator, elm); + // decrease size + hash_map->base.size--; +} + /** * Helper function to avoid code duplication. * @@ -200,17 +219,7 @@ if (memcmp(elm->key.data, key.data, key.len) == 0) { void *data = elm->data; if (remove) { - // unlink - if (prev) { - prev->next = elm->next; - } else { - hash_map->buckets[slot] = elm->next; - } - // free element - cxFree(map->allocator, elm->key.data); - cxFree(map->allocator, elm); - // decrease size - map->size--; + cx_hash_map_unlink(hash_map, slot, prev, elm); } return data; } @@ -237,21 +246,120 @@ return cx_hash_map_get_remove(map, key, true); } -static CxIterator cx_hash_map_iterator(CxMap const *map) { +static void *cx_hash_map_iter_current_entry(CxIterator const *iter) { + // struct has to have a compatible signature + struct cx_map_entry_s *entry = (struct cx_map_entry_s *) &(iter->kv_data); + return entry; +} + +static void *cx_hash_map_iter_current_key(CxIterator const *iter) { + struct cx_hash_map_element_s *elm = iter->elem_handle; + return &elm->key; +} + +static void *cx_hash_map_iter_current_value(CxIterator const *iter) { + struct cx_hash_map_element_s *elm = iter->elem_handle; + // TODO: return a pointer to data if this map is storing copies + return elm->data; +} + +static bool cx_hash_map_iter_valid(CxIterator const *iter) { + return iter->elem_handle != NULL; +} + +static void cx_hash_map_iter_next(CxIterator *iter) { + struct cx_hash_map_s *map = iter->src_handle; + struct cx_hash_map_element_s *elm = iter->elem_handle; + + // remove current element, if asked + if (iter->remove) { + // clear the flag + iter->remove = false; + + // determine the next element + struct cx_hash_map_element_s *next = elm->next; + + // search the previous element + struct cx_hash_map_element_s *prev = NULL; + if (map->buckets[iter->slot] != elm) { + prev = map->buckets[iter->slot]; + while (prev->next != elm) { + prev = prev->next; + } + } + + // unlink + cx_hash_map_unlink(map, iter->slot, prev, elm); + + // advance + elm = next; + } else { + // just advance + elm = elm->next; + } + + // do we leave the bucket? + if (elm == NULL) { + // search the next bucket + for (; elm == NULL && iter->slot < map->bucket_count; iter->slot++) { + elm = map->buckets[iter->slot]; + } + } + + // advance the index in any case + iter->index++; + + // fill the struct with the current element + iter->elem_handle = elm; + if (elm == NULL) { + iter->kv_data.key = NULL; + iter->kv_data.value = NULL; + } else { + iter->kv_data.key = &elm->key; + // TODO: pointer to data if this map is storing copies + iter->kv_data.value = elm->data; + } +} + +static CxIterator cx_hash_map_iterator(CxMap *map) { CxIterator iter; - // TODO: initialize iter + + iter.src_handle = map; + iter.valid = cx_hash_map_iter_valid; + iter.next = cx_hash_map_iter_next; + iter.current = cx_hash_map_iter_current_entry; + + iter.slot = 0; + iter.index = 0; + iter.remove = false; + + if (map->size > 0) { + struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; + struct cx_hash_map_element_s *elem = NULL; + for (; elem == NULL; iter.slot++) { + elem = hash_map->buckets[iter.slot]; + } + iter.elem_handle = elem; + iter.kv_data.key = NULL; + iter.kv_data.value = NULL; + } else { + iter.elem_handle = NULL; + iter.kv_data.key = NULL; + iter.kv_data.value = NULL; + } + return iter; } -static CxIterator cx_hash_map_iterator_keys(CxMap const *map) { - CxIterator iter; - // TODO: initialize iter +static CxIterator cx_hash_map_iterator_keys(CxMap *map) { + CxIterator iter = cx_hash_map_iterator(map); + iter.current = cx_hash_map_iter_current_key; return iter; } -static CxIterator cx_hash_map_iterator_values(CxMap const *map) { - CxIterator iter; - // TODO: initialize iter +static CxIterator cx_hash_map_iterator_values(CxMap *map) { + CxIterator iter = cx_hash_map_iterator(map); + iter.current = cx_hash_map_iter_current_value; return iter; }