Mercurial > hg > ucx / changeset

--- a/CHANGELOG	Tue Jan 07 19:16:03 2025 +0100
+++ b/CHANGELOG	Wed Jan 08 20:06:37 2025 +0100
@@ -21,6 +21,7 @@
  * adds runtime constants to read out the actual SBO sizes
  * adds improved version of UCX 2 Test framework (now a self-contained header)
  * adds cx_nmemb() utility function to common.h
+ * changes that CxMap returns own CxMapIterator to save memory in CxIterator
  * changes all functions, for which there is no dedicated xyz_a variant,
    to accept NULL as allocator argument (in which case a default allocator will be used)
  * changes the name of destroy functions that actually free the memory to better indicate their behavior

--- a/src/cx/iterator.h	Tue Jan 07 19:16:03 2025 +0100
+++ b/src/cx/iterator.h	Wed Jan 08 20:06:37 2025 +0100
@@ -120,27 +120,6 @@
     } 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.
-         */
-        const 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.
      */

--- a/src/cx/map.h	Tue Jan 07 19:16:03 2025 +0100
+++ b/src/cx/map.h	Wed Jan 08 20:06:37 2025 +0100
@@ -51,6 +51,9 @@
 /** Type for a map entry. */
 typedef struct cx_map_entry_s CxMapEntry;
 
+/** Type for a map iterator. */
+typedef struct cx_map_iterator_s CxMapIterator;
+
 /** Type for map class definitions. */
 typedef struct cx_map_class_s cx_map_class;
 
@@ -65,6 +68,20 @@
 };
 
 /**
+ * A map entry.
+ */
+struct cx_map_entry_s {
+    /**
+     * A pointer to the key.
+     */
+    const CxHashKey *key;
+    /**
+     * A pointer to the value.
+     */
+    void *value;
+};
+
+/**
  * The type of iterator for a map.
  */
 enum cx_map_iterator_type {
@@ -83,6 +100,76 @@
 };
 
 /**
+ * Internal iterator struct - use CxMapIterator.
+ */
+struct cx_map_iterator_s {
+    /**
+     * Inherited common data for all iterators.
+     */
+    CX_ITERATOR_BASE;
+
+    /**
+     * Handle for the source map.
+     */
+    union {
+        /**
+         * Access for mutating iterators.
+         */
+        CxMap *m;
+        /**
+         * Access for normal iterators.
+         */
+        const CxMap *c;
+    } map;
+
+    /**
+     * Handle for the current element.
+     *
+     * @attention Depends on the map implementation, do not assume a type (better: do not use!).
+     */
+    void *elem;
+
+    /**
+     * Reserved memory for a map entry.
+     *
+     * If a map implementation uses an incompatible layout, the iterator needs something
+     * to point to during iteration which @em is compatible.
+     */
+    CxMapEntry entry;
+
+    /**
+     * Field for storing the current slot number.
+     *
+     * (Used internally)
+     */
+    size_t slot;
+
+    /**
+     * Counts the elements successfully.
+     * It usually does not denote a stable index within the map as it would be for arrays.
+     */
+    size_t index;
+
+    /**
+     * The size of a value stored in this map.
+     */
+    size_t elem_size;
+
+    /**
+     * May contain the total number of elements, if known.
+     * Set to @c SIZE_MAX when the total number is unknown during iteration.
+     *
+     * @remark The UCX implementations of #CxMap always know the number of elements they store.
+     */
+    size_t elem_count;
+
+    /**
+     * The type of this iterator.
+     */
+    enum cx_map_iterator_type type;
+};
+
+/**
  * The class definition for arbitrary maps.
  */
 struct cx_map_class_s {
@@ -132,21 +219,7 @@
     /**
      * Creates an iterator for this map.
      */
-    CxIterator (*iterator)(const CxMap *map, enum cx_map_iterator_type type);
-};
-
-/**
- * A map entry.
- */
-struct cx_map_entry_s {
-    /**
-     * A pointer to the key.
-     */
-    const CxHashKey *key;
-    /**
-     * A pointer to the value.
-     */
-    void *value;
+    CxMapIterator (*iterator)(const CxMap *map, enum cx_map_iterator_type type);
 };
 
 /**
@@ -195,6 +268,10 @@
 /**
  * Creates a value iterator for a map.
  *
+ * When the map is storing pointers, those pointers are returned.
+ * Otherwise, the iterator iterates over pointers to the memory within the map where the
+ * respective elements are stored.
+ *
  * @note An iterator iterates over all elements successively. Therefore, the order
  * highly depends on the map implementation and may change arbitrarily when the contents change.
  *
@@ -203,14 +280,15 @@
  */
 cx_attr_nonnull
 cx_attr_nodiscard
-static inline CxIterator cxMapIteratorValues(const CxMap *map) {
+static inline CxMapIterator cxMapIteratorValues(const CxMap *map) {
     return map->cl->iterator(map, CX_MAP_ITERATOR_VALUES);
 }
 
 /**
  * Creates a key iterator for a map.
  *
- * The elements of the iterator are keys of type CxHashKey.
+ * The elements of the iterator are keys of type CxHashKey and the pointer returned
+ * during iterator shall be treated as @c const @c CxHashKey* .
  *
  * @note An iterator iterates over all elements successively. Therefore, the order
  * highly depends on the map implementation and may change arbitrarily when the contents change.
@@ -220,14 +298,15 @@
  */
 cx_attr_nonnull
 cx_attr_nodiscard
-static inline CxIterator cxMapIteratorKeys(const CxMap *map) {
+static inline CxMapIterator cxMapIteratorKeys(const CxMap *map) {
     return map->cl->iterator(map, CX_MAP_ITERATOR_KEYS);
 }
 
 /**
  * Creates an iterator for a map.
  *
- * The elements of the iterator are key/value pairs of type CxMapEntry.
+ * The elements of the iterator are key/value pairs of type CxMapEntry and the pointer returned
+ * during iterator shall be treated as @c const @c CxMapEntry* .
  *
  * @note An iterator iterates over all elements successively. Therefore, the order
  * highly depends on the map implementation and may change arbitrarily when the contents change.
@@ -239,7 +318,7 @@
  */
 cx_attr_nonnull
 cx_attr_nodiscard
-static inline CxIterator cxMapIterator(const CxMap *map) {
+static inline CxMapIterator cxMapIterator(const CxMap *map) {
     return map->cl->iterator(map, CX_MAP_ITERATOR_PAIRS);
 }
 
@@ -247,6 +326,10 @@
 /**
  * Creates a mutating iterator over the values of a map.
  *
+ * When the map is storing pointers, those pointers are returned.
+ * Otherwise, the iterator iterates over pointers to the memory within the map where the
+ * respective elements are stored.
+ *
  * @note An iterator iterates over all elements successively. Therefore, the order
  * highly depends on the map implementation and may change arbitrarily when the contents change.
  *
@@ -255,12 +338,13 @@
  */
 cx_attr_nonnull
 cx_attr_nodiscard
-CxIterator cxMapMutIteratorValues(CxMap *map);
+CxMapIterator cxMapMutIteratorValues(CxMap *map);
 
 /**
  * Creates a mutating iterator over the keys of a map.
  *
- * The elements of the iterator are keys of type CxHashKey.
+ * The elements of the iterator are keys of type CxHashKey and the pointer returned
+ * during iterator shall be treated as @c const @c CxHashKey* .
  *
  * @note An iterator iterates over all elements successively. Therefore, the order
  * highly depends on the map implementation and may change arbitrarily when the contents change.
@@ -270,12 +354,13 @@
  */
 cx_attr_nonnull
 cx_attr_nodiscard
-CxIterator cxMapMutIteratorKeys(CxMap *map);
+CxMapIterator cxMapMutIteratorKeys(CxMap *map);
 
 /**
  * Creates a mutating iterator for a map.
  *
- * The elements of the iterator are key/value pairs of type CxMapEntry.
+ * The elements of the iterator are key/value pairs of type CxMapEntry and the pointer returned
+ * during iterator shall be treated as @c const @c CxMapEntry* .
  *
  * @note An iterator iterates over all elements successively. Therefore, the order
  * highly depends on the map implementation and may change arbitrarily when the contents change.
@@ -287,7 +372,7 @@
  */
 cx_attr_nonnull
 cx_attr_nodiscard
-CxIterator cxMapMutIterator(CxMap *map);
+CxMapIterator cxMapMutIterator(CxMap *map);
 
 #ifdef __cplusplus
 } // end the extern "C" block here, because we want to start overloading

--- a/src/hash_map.c	Tue Jan 07 19:16:03 2025 +0100
+++ b/src/hash_map.c	Wed Jan 08 20:06:37 2025 +0100
@@ -253,22 +253,22 @@
 }
 
 static void *cx_hash_map_iter_current_entry(const void *it) {
-    const struct cx_iterator_s *iter = it;
-    // struct has to have a compatible signature
-    return (struct cx_map_entry_s *) &(iter->kv_data);
+    const CxMapIterator *iter = it;
+    // we have to cast away const, because of the signature
+    return (void*) &iter->entry;
 }
 
 static void *cx_hash_map_iter_current_key(const void *it) {
-    const struct cx_iterator_s *iter = it;
-    struct cx_hash_map_element_s *elm = iter->elem_handle;
+    const CxMapIterator *iter = it;
+    struct cx_hash_map_element_s *elm = iter->elem;
     return &elm->key;
 }
 
 static void *cx_hash_map_iter_current_value(const void *it) {
-    const struct cx_iterator_s *iter = it;
-    const struct cx_hash_map_s *map = iter->src_handle.c;
-    struct cx_hash_map_element_s *elm = iter->elem_handle;
-    if (map->base.collection.store_pointer) {
+    const CxMapIterator *iter = it;
+    const CxMap *map = iter->map.c;
+    struct cx_hash_map_element_s *elm = iter->elem;
+    if (map->collection.store_pointer) {
         return *(void **) elm->data;
     } else {
         return elm->data;
@@ -276,14 +276,15 @@
 }
 
 static bool cx_hash_map_iter_valid(const void *it) {
-    const struct cx_iterator_s *iter = it;
-    return iter->elem_handle != NULL;
+    const CxMapIterator *iter = it;
+    return iter->elem != NULL;
 }
 
 static void cx_hash_map_iter_next(void *it) {
-    struct cx_iterator_s *iter = it;
-    struct cx_hash_map_element_s *elm = iter->elem_handle;
-    struct cx_hash_map_s *map = iter->src_handle.m;
+    CxMapIterator *iter = it;
+    CxMap *map = iter->map.m;
+    struct cx_hash_map_s *hmap = (struct cx_hash_map_s *) map;
+    struct cx_hash_map_element_s *elm = iter->elem;
 
     // remove current element, if asked
     if (iter->base.remove) {
@@ -296,18 +297,18 @@
 
         // search the previous element
         struct cx_hash_map_element_s *prev = NULL;
-        if (map->buckets[iter->slot] != elm) {
-            prev = map->buckets[iter->slot];
+        if (hmap->buckets[iter->slot] != elm) {
+            prev = hmap->buckets[iter->slot];
             while (prev->next != elm) {
                 prev = prev->next;
             }
         }
 
         // destroy
-        cx_invoke_destructor((struct cx_map_s *) map, elm->data);
+        cx_invoke_destructor(map, elm->data);
 
         // unlink
-        cx_hash_map_unlink(map, iter->slot, prev, elm);
+        cx_hash_map_unlink(hmap, iter->slot, prev, elm);
 
         // advance
         elm = next;
@@ -318,32 +319,31 @@
     }
 
     // search the next bucket, if required
-    while (elm == NULL && ++iter->slot < map->bucket_count) {
-        elm = map->buckets[iter->slot];
+    while (elm == NULL && ++iter->slot < hmap->bucket_count) {
+        elm = hmap->buckets[iter->slot];
     }
+    iter->elem = elm;
 
-    // fill the struct with the next 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;
-        if (map->base.collection.store_pointer) {
-            iter->kv_data.value = *(void **) elm->data;
+    // copy data to a location where the iterator can point to
+    // we need to do it here, because the iterator function call
+    // must not modify the iterator (the parameter is const)
+    if (elm != NULL) {
+        iter->entry.key = &elm->key;
+        if (iter->map.c->collection.store_pointer) {
+            iter->entry.value = *(void **) elm->data;
         } else {
-            iter->kv_data.value = elm->data;
+            iter->entry.value = elm->data;
         }
     }
 }
 
-static CxIterator cx_hash_map_iterator(
+static CxMapIterator cx_hash_map_iterator(
         const CxMap *map,
         enum cx_map_iterator_type type
 ) {
-    CxIterator iter;
+    CxMapIterator iter;
 
-    iter.src_handle.c = map;
+    iter.map.c = map;
     iter.elem_count = map->collection.size;
 
     switch (type) {
@@ -377,17 +377,15 @@
         while (elm == NULL) {
             elm = hash_map->buckets[++iter.slot];
         }
-        iter.elem_handle = elm;
-        iter.kv_data.key = &elm->key;
+        iter.elem = elm;
+        iter.entry.key = &elm->key;
         if (map->collection.store_pointer) {
-            iter.kv_data.value = *(void **) elm->data;
+            iter.entry.value = *(void **) elm->data;
         } else {
-            iter.kv_data.value = elm->data;
+            iter.entry.value = elm->data;
         }
     } else {
-        iter.elem_handle = NULL;
-        iter.kv_data.key = NULL;
-        iter.kv_data.value = NULL;
+        iter.elem = NULL;
     }
 
     return iter;

--- a/src/map.c	Tue Jan 07 19:16:03 2025 +0100
+++ b/src/map.c	Wed Jan 08 20:06:37 2025 +0100
@@ -46,12 +46,12 @@
     return false;
 }
 
-static CxIterator cx_empty_map_iterator(
+static CxMapIterator cx_empty_map_iterator(
         const struct cx_map_s *map,
         cx_attr_unused enum cx_map_iterator_type type
 ) {
-    CxIterator iter = {0};
-    iter.src_handle.c = map;
+    CxMapIterator iter = {0};
+    iter.map.c = map;
     iter.base.valid = cx_empty_map_iter_valid;
     return iter;
 }
@@ -83,20 +83,20 @@
 
 // </editor-fold>
 
-CxIterator cxMapMutIteratorValues(CxMap *map) {
-    CxIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_VALUES);
+CxMapIterator cxMapMutIteratorValues(CxMap *map) {
+    CxMapIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_VALUES);
     it.base.mutating = true;
     return it;
 }
 
-CxIterator cxMapMutIteratorKeys(CxMap *map) {
-    CxIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_KEYS);
+CxMapIterator cxMapMutIteratorKeys(CxMap *map) {
+    CxMapIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_KEYS);
     it.base.mutating = true;
     return it;
 }
 
-CxIterator cxMapMutIterator(CxMap *map) {
-    CxIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_PAIRS);
+CxMapIterator cxMapMutIterator(CxMap *map) {
+    CxMapIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_PAIRS);
     it.base.mutating = true;
     return it;
 }

--- a/tests/test_hash_map.c	Tue Jan 07 19:16:03 2025 +0100
+++ b/tests/test_hash_map.c	Wed Jan 08 20:06:37 2025 +0100
@@ -209,7 +209,7 @@
 
         // iterate
         bool s3found = false, s4found = false, s5found = false;
-        CxIterator iter = cxMapIteratorValues(map);
+        CxMapIterator iter = cxMapIteratorValues(map);
         cx_foreach(cxstring*, s, iter) {
             s3found |= s3.ptr == s->ptr;
             s4found |= s4.ptr == s->ptr;
@@ -237,7 +237,7 @@
         cxMapPut(map, "key 5", (void *) "val 5");
         cxMapPut(map, "key 6", (void *) "val 6");
 
-        CxIterator iter = cxMapMutIterator(map);
+        CxMapIterator iter = cxMapMutIterator(map);
         cx_foreach(CxMapEntry*, entry, iter) {
             if (((const char *)entry->key->data)[4] % 2 == 1) cxIteratorFlagRemoval(iter);
         }
@@ -338,13 +338,13 @@
     // now remove k1 via key iterator and k5 (val 5) via value iterator
     v1[0] = 'y'; // mark v1 and check that destr is not called for previous val
     {
-        CxIterator iter = cxMapMutIteratorKeys(map);
+        CxMapIterator iter = cxMapMutIteratorKeys(map);
         cx_foreach(CxHashKey*, key, iter) {
             if (((char*)key->data)[4] == '1') cxIteratorFlagRemoval(iter);
         }
     }
     {
-        CxIterator iter = cxMapMutIteratorValues(map);
+        CxMapIterator iter = cxMapMutIteratorValues(map);
         cx_foreach(struct test_destr_struct*, v, iter) {
             if (v->str[4] == '5') cxIteratorFlagRemoval(iter);
         }
@@ -437,12 +437,12 @@
 CX_TEST(test_empty_map_iterator) {
     CxMap *map = cxEmptyMap;
 
-    CxIterator it1 = cxMapIterator(map);
-    CxIterator it2 = cxMapIteratorValues(map);
-    CxIterator it3 = cxMapIteratorKeys(map);
-    CxIterator it4 = cxMapMutIterator(map);
-    CxIterator it5 = cxMapMutIteratorValues(map);
-    CxIterator it6 = cxMapMutIteratorKeys(map);
+    CxMapIterator it1 = cxMapIterator(map);
+    CxMapIterator it2 = cxMapIteratorValues(map);
+    CxMapIterator it3 = cxMapIteratorKeys(map);
+    CxMapIterator it4 = cxMapMutIterator(map);
+    CxMapIterator it5 = cxMapMutIteratorValues(map);
+    CxMapIterator it6 = cxMapMutIteratorKeys(map);
 
     CX_TEST_DO {
         CX_TEST_ASSERT(!cxIteratorValid(it1));
@@ -607,7 +607,7 @@
     // verify key iterator
     {
         // collect the keys from the map iterator
-        CxIterator keyiter = cxMapIteratorKeys(map);
+        CxMapIterator keyiter = cxMapIteratorKeys(map);
         CX_TEST_ASSERT(keyiter.elem_size == sizeof(CxHashKey));
         CX_TEST_ASSERT(keyiter.elem_count == map->collection.size);
         CxHashKey *keys = calloc(map->collection.size, sizeof(CxHashKey));
@@ -628,7 +628,7 @@
     {
         // 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);
+        CxMapIterator valiter = cxMapIteratorValues(map);
         CX_TEST_ASSERT(valiter.elem_size == map->collection.elem_size);
         CX_TEST_ASSERT(valiter.elem_count == map->collection.size);
         const char ** values = calloc(map->collection.size, sizeof(const char *));
@@ -652,7 +652,7 @@
 
     // verify pair iterator
     {
-        CxIterator pairiter = cxMapIterator(map);
+        CxMapIterator pairiter = cxMapIterator(map);
         CX_TEST_ASSERT(pairiter.elem_size == sizeof(CxMapEntry));
         CX_TEST_ASSERT(pairiter.elem_count == map->collection.size);
         struct test_map_kv *pairs = calloc(map->collection.size, sizeof(struct test_map_kv));