simplify iterator structures

Thu, 23 May 2024 19:29:14 +0200

author
Mike Becker <universe@uap-core.de>
date
Thu, 23 May 2024 19:29:14 +0200
changeset 853
d4baf4dd55c3
parent 852
16e2a3391e88
child 854
fe0d69d72bcd

simplify iterator structures

docs/src/features.md file | annotate | diff | comparison | revisions
src/array_list.c file | annotate | diff | comparison | revisions
src/cx/iterator.h file | annotate | diff | comparison | revisions
src/cx/list.h file | annotate | diff | comparison | revisions
src/cx/map.h file | annotate | diff | comparison | revisions
src/cx/tree.h file | annotate | diff | comparison | revisions
src/hash_map.c file | annotate | diff | comparison | revisions
src/iterator.c file | annotate | diff | comparison | revisions
src/linked_list.c file | annotate | diff | comparison | revisions
src/list.c file | annotate | diff | comparison | revisions
src/map.c file | annotate | diff | comparison | revisions
src/tree.c file | annotate | diff | comparison | revisions
tests/test_hash_map.c file | annotate | diff | comparison | revisions
tests/test_iterator.c file | annotate | diff | comparison | revisions
tests/test_list.c file | annotate | diff | comparison | revisions
tests/test_tree.c file | annotate | diff | comparison | revisions
--- a/docs/src/features.md	Thu May 23 18:21:36 2024 +0200
+++ b/docs/src/features.md	Thu May 23 19:29:14 2024 +0200
@@ -186,15 +186,17 @@
 Sometimes you only need the `index` (for example when iterating over simple lists), and other times you will need the
 `slot` and `kv_data` fields (for example when iterating over maps).
 
+If the predefined fields are insufficient for your use case, you can alternatively create your own iterator structure
+and place the `CX_ITERATOR_BASE` macro inside.
+
 Usually an iterator is not mutating the collection it is iterating over.
 In some programming languages it is even disallowed to change the collection while iterating with foreach.
 But sometimes it is desirable to remove an element from the collection while iterating over it.
-This is, what the `CxMutIterator` is for.
+For this purpose, most collections allow the creation of a _mutating_ iterator.
 The only differences are, that the `mutating` flag is `true` and the `src_handle` is not const.
 On mutating iterators it is allowed to call the `cxFlagForRemoval()` function, which instructs the iterator to remove
 the current element from the collection on the next call to `cxIteratorNext()` and clear the flag afterward.
-If you are implementing your own iterator, it is up to you to implement this behavior in your `next` method, or
-make the implementation of the `flag_removal` method always return `false`.
+If you are implementing your own iterator, it is up to you to implement this behavior.
 
 ## Collection
 
--- a/src/array_list.c	Thu May 23 18:21:36 2024 +0200
+++ b/src/array_list.c	Thu May 23 19:29:14 2024 +0200
@@ -273,11 +273,11 @@
 }
 
 static int cx_arl_insert_iter(
-        struct cx_mut_iterator_s *iter,
+        struct cx_iterator_s *iter,
         void const *elem,
         int prepend
 ) {
-    struct cx_list_s *list = iter->src_handle;
+    struct cx_list_s *list = iter->src_handle.m;
     if (iter->index < list->size) {
         int result = cx_arl_insert_element(
                 list,
@@ -453,7 +453,7 @@
 
 static bool cx_arl_iter_valid(void const *it) {
     struct cx_iterator_s const *iter = it;
-    struct cx_list_s const *list = iter->src_handle;
+    struct cx_list_s const *list = iter->src_handle.c;
     return iter->index < list->size;
 }
 
@@ -463,27 +463,24 @@
 }
 
 static void cx_arl_iter_next(void *it) {
-    struct cx_iterator_base_s *itbase = it;
-    if (itbase->remove) {
-        struct cx_mut_iterator_s *iter = it;
-        itbase->remove = false;
-        cx_arl_remove(iter->src_handle, iter->index);
+    struct cx_iterator_s *iter = it;
+    if (iter->remove) {
+        iter->remove = false;
+        cx_arl_remove(iter->src_handle.m, iter->index);
     } else {
-        struct cx_iterator_s *iter = it;
         iter->index++;
         iter->elem_handle =
                 ((char *) iter->elem_handle)
-                + ((struct cx_list_s const *) iter->src_handle)->item_size;
+                + ((struct cx_list_s const *) iter->src_handle.c)->item_size;
     }
 }
 
 static void cx_arl_iter_prev(void *it) {
-    struct cx_iterator_base_s *itbase = it;
-    struct cx_mut_iterator_s *iter = it;
-    cx_array_list *const list = iter->src_handle;
-    if (itbase->remove) {
-        itbase->remove = false;
-        cx_arl_remove(iter->src_handle, iter->index);
+    struct cx_iterator_s *iter = it;
+    cx_array_list const* list = iter->src_handle.c;
+    if (iter->remove) {
+        iter->remove = false;
+        cx_arl_remove(iter->src_handle.m, iter->index);
     }
     iter->index--;
     if (iter->index < list->base.size) {
@@ -501,15 +498,15 @@
     struct cx_iterator_s iter;
 
     iter.index = index;
-    iter.src_handle = list;
+    iter.src_handle.c = 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;
-    iter.base.remove = false;
-    iter.base.mutating = false;
+    iter.valid = cx_arl_iter_valid;
+    iter.current = cx_arl_iter_current;
+    iter.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next;
+    iter.remove = false;
+    iter.mutating = false;
 
     return iter;
 }
--- a/src/cx/iterator.h	Thu May 23 18:21:36 2024 +0200
+++ b/src/cx/iterator.h	Thu May 23 19:29:14 2024 +0200
@@ -38,68 +38,64 @@
 
 #include "common.h"
 
-/**
- * The base of mutating and non-mutating iterators.
- */
-struct cx_iterator_base_s {
-    /**
-     * True iff the iterator points to valid data.
-     */
-    __attribute__ ((__nonnull__))
-    bool (*valid)(void const *);
+#define CX_ITERATOR_BASE \
+    /** \
+     * True iff the iterator points to valid data. \
+     */ \
+    __attribute__ ((__nonnull__)) \
+    bool (*valid)(void const *); \
+    /** \
+     * Returns a pointer to the current element. \
+     * \
+     * When valid returns false, the behavior of this function is undefined. \
+     */ \
+    __attribute__ ((__nonnull__)) \
+    void *(*current)(void const *); \
+    /** \
+     * Original implementation in case the function needs to be wrapped. \
+     */ \
+    __attribute__ ((__nonnull__)) \
+    void *(*current_impl)(void const *); \
+    /** \
+     * Advances the iterator. \
+     * \
+     * When valid returns false, the behavior of this function is undefined. \
+     */ \
+    __attribute__ ((__nonnull__)) \
+    void (*next)(void *); \
+    /** \
+     * Indicates whether this iterator may remove elements. \
+     */ \
+    bool mutating; \
+    /** \
+     * Internal flag for removing the current element when advancing. \
+     */ \
+    bool remove;
 
-    /**
-     * Returns a pointer to the current element.
-     *
-     * When valid returns false, the behavior of this function is undefined.
-     */
-    __attribute__ ((__nonnull__))
-    void *(*current)(void const *);
-
-    /**
-     * Original implementation in case the function needs to be wrapped.
-     */
-    __attribute__ ((__nonnull__))
-    void *(*current_impl)(void const *);
+/**
+ * Internal iterator struct - use CxIterator.
+ */
+struct cx_iterator_s {
+    CX_ITERATOR_BASE
 
     /**
-     * Advances the iterator.
-     *
-     * When valid returns false, the behavior of this function is undefined.
-     */
-    __attribute__ ((__nonnull__))
-    void (*next)(void *);
-
-    /**
-     * Indicates whether this iterator may remove elements.
-     */
-    bool mutating;
-
-    /**
-     * Internal flag for removing the current element when advancing.
-     */
-    bool remove;
-};
-
-/**
- * Internal iterator struct - use CxMutIterator.
- */
-struct cx_mut_iterator_s {
-
-    /**
-     * The base properties of this iterator.
-     */
-    struct cx_iterator_base_s base;
-
-    /**
-     * Handle for the current element, if required.
+     * Handle for the current element.
      */
     void *elem_handle;
 
     /**
      * Handle for the source collection, if any.
      */
-    void *src_handle;
+    union {
+        /**
+         * Access for mutating iterators.
+         */
+        void *m;
+        /**
+         * Access for normal iterators.
+         */
+        void const *c;
+    } src_handle;
 
     /**
      * Field for storing a key-value pair.
@@ -141,91 +137,15 @@
 };
 
 /**
- * Mutating iterator value type.
- *
- * An iterator points to a certain element in an (possibly unbounded) chain of elements.
- * Iterators that are based on collections (which have a defined "first" element), are supposed
- * to be "position-aware", which means that they keep track of the current index within the collection.
- *
- * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the
- * iterator is based on a collection and the underlying collection is mutated by other means than this iterator
- * (e.g. elements added or removed), the iterator becomes invalid (regardless of what cxIteratorValid() returns)
- * and MUST be re-obtained from the collection.
+ * Iterator type.
  *
- * @see CxIterator
- */
-typedef struct cx_mut_iterator_s CxMutIterator;
-
-/**
- * Internal iterator struct - use CxIterator.
- */
-struct cx_iterator_s {
-
-    /**
-     * The base properties of this iterator.
-     */
-    struct cx_iterator_base_s base;
-
-    /**
-     * Handle for the current element, if required.
-     */
-    void *elem_handle;
-
-    /**
-     * Handle for the source collection, if any.
-     */
-    void const *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 const *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.
-     */
-    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;
-};
-
-/**
- * Iterator value type.
  * An iterator points to a certain element in a (possibly unbounded) chain of elements.
  * Iterators that are based on collections (which have a defined "first" element), are supposed
  * to be "position-aware", which means that they keep track of the current index within the collection.
  *
  * @note Objects that are pointed to by an iterator are always mutable through that iterator. However,
- * this iterator cannot mutate the collection itself (add or remove elements) and any mutation of the
- * collection by other means makes this iterator invalid (regardless of what cxIteratorValid() returns).
- *
- * @see CxMutIterator
+ * any concurrent mutation of the collection other than by this iterator makes this iterator invalid
+ * and it must not be used anymore.
  */
 typedef struct cx_iterator_s CxIterator;
 
@@ -237,7 +157,7 @@
  * @param iter the iterator
  * @return true iff the iterator points to valid data
  */
-#define cxIteratorValid(iter) (iter).base.valid(&(iter))
+#define cxIteratorValid(iter) (iter).valid(&(iter))
 
 /**
  * Returns a pointer to the current element.
@@ -247,21 +167,21 @@
  * @param iter the iterator
  * @return a pointer to the current element
  */
-#define cxIteratorCurrent(iter) (iter).base.current(&iter)
+#define cxIteratorCurrent(iter) (iter).current(&iter)
 
 /**
  * Advances the iterator to the next element.
  *
  * @param iter the iterator
  */
-#define cxIteratorNext(iter) (iter).base.next(&iter)
+#define cxIteratorNext(iter) (iter).next(&iter)
 
 /**
  * Flags the current element for removal, if this iterator is mutating.
  *
  * @param iter the iterator
  */
-#define cxIteratorFlagRemoval(iter) (iter).base.remove |= (iter).base.mutating
+#define cxIteratorFlagRemoval(iter) (iter).remove |= (iter).mutating
 
 /**
  * Loops over an iterator.
@@ -316,7 +236,7 @@
  * @return an iterator for the specified array
  */
 __attribute__((__warn_unused_result__))
-CxMutIterator cxMutIterator(
+CxIterator cxMutIterator(
         void *array,
         size_t elem_size,
         size_t elem_count,
--- a/src/cx/list.h	Thu May 23 18:21:36 2024 +0200
+++ b/src/cx/list.h	Thu May 23 19:29:14 2024 +0200
@@ -100,7 +100,7 @@
      * Member function for inserting an element relative to an iterator position.
      */
     int (*insert_iter)(
-            struct cx_mut_iterator_s *iter,
+            struct cx_iterator_s *iter,
             void const *elem,
             int prepend
     );
@@ -336,10 +336,10 @@
  */
 __attribute__((__nonnull__))
 static inline int cxListInsertAfter(
-        CxMutIterator *iter,
+        CxIterator *iter,
         void const *elem
 ) {
-    return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 0);
+    return ((struct cx_list_s *) iter->src_handle.m)->cl->insert_iter(iter, elem, 0);
 }
 
 /**
@@ -359,10 +359,10 @@
  */
 __attribute__((__nonnull__))
 static inline int cxListInsertBefore(
-        CxMutIterator *iter,
+        CxIterator *iter,
         void const *elem
 ) {
-    return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 1);
+    return ((struct cx_list_s *) iter->src_handle.m)->cl->insert_iter(iter, elem, 1);
 }
 
 /**
@@ -481,7 +481,7 @@
  * @return a new iterator
  */
 __attribute__((__nonnull__, __warn_unused_result__))
-CxMutIterator cxListMutIteratorAt(
+CxIterator cxListMutIteratorAt(
         CxList *list,
         size_t index
 );
@@ -499,7 +499,7 @@
  * @return a new iterator
  */
 __attribute__((__nonnull__, __warn_unused_result__))
-CxMutIterator cxListMutBackwardsIteratorAt(
+CxIterator cxListMutBackwardsIteratorAt(
         CxList *list,
         size_t index
 );
@@ -530,7 +530,7 @@
  * @return a new iterator
  */
 __attribute__((__nonnull__, __warn_unused_result__))
-static inline CxMutIterator cxListMutIterator(CxList *list) {
+static inline CxIterator cxListMutIterator(CxList *list) {
     return cxListMutIteratorAt(list, 0);
 }
 
@@ -561,7 +561,7 @@
  * @return a new iterator
  */
 __attribute__((__nonnull__, __warn_unused_result__))
-static inline CxMutIterator cxListMutBackwardsIterator(CxList *list) {
+static inline CxIterator cxListMutBackwardsIterator(CxList *list) {
     return cxListMutBackwardsIteratorAt(list, list->size - 1);
 }
 
--- a/src/cx/map.h	Thu May 23 18:21:36 2024 +0200
+++ b/src/cx/map.h	Thu May 23 19:29:14 2024 +0200
@@ -268,7 +268,7 @@
  * @return an iterator for the currently stored values
  */
 __attribute__((__nonnull__, __warn_unused_result__))
-CxMutIterator cxMapMutIteratorValues(CxMap *map);
+CxIterator cxMapMutIteratorValues(CxMap *map);
 
 /**
  * Creates a mutating iterator over the keys of a map.
@@ -282,7 +282,7 @@
  * @return an iterator for the currently stored keys
  */
 __attribute__((__nonnull__, __warn_unused_result__))
-CxMutIterator cxMapMutIteratorKeys(CxMap *map);
+CxIterator cxMapMutIteratorKeys(CxMap *map);
 
 /**
  * Creates a mutating iterator for a map.
@@ -298,7 +298,7 @@
  * @see cxMapMutIteratorValues()
  */
 __attribute__((__nonnull__, __warn_unused_result__))
-CxMutIterator cxMapMutIterator(CxMap *map);
+CxIterator cxMapMutIterator(CxMap *map);
 
 #ifdef __cplusplus
 } // end the extern "C" block here, because we want to start overloading
--- a/src/cx/tree.h	Thu May 23 18:21:36 2024 +0200
+++ b/src/cx/tree.h	Thu May 23 19:29:14 2024 +0200
@@ -58,10 +58,7 @@
  * @see CxIterator
  */
 typedef struct cx_tree_iterator_s {
-    /**
-     * The base properties of this iterator.
-     */
-    struct cx_iterator_base_s base;
+    CX_ITERATOR_BASE
     /**
      * Indicates whether the subtree below the current node shall be skipped.
      */
@@ -97,7 +94,7 @@
      * Stores a copy of the next pointer of the visited node.
      * Allows freeing a node on exit without corrupting the iteration.
      */
-    void *next;
+    void *node_next;
     /**
      * Internal stack.
      * Will be automatically freed once the iterator becomes invalid.
@@ -157,10 +154,7 @@
  * @see CxIterator
  */
 typedef struct cx_tree_visitor_s {
-    /**
-     * The base properties of this iterator.
-     */
-    struct cx_iterator_base_s base;
+    CX_ITERATOR_BASE
     /**
      * Indicates whether the subtree below the current node shall be skipped.
      */
--- a/src/hash_map.c	Thu May 23 18:21:36 2024 +0200
+++ b/src/hash_map.c	Thu May 23 19:29:14 2024 +0200
@@ -252,7 +252,7 @@
 
 static void *cx_hash_map_iter_current_value(void const *it) {
     struct cx_iterator_s const *iter = it;
-    struct cx_hash_map_s const *map = iter->src_handle;
+    struct cx_hash_map_s const *map = iter->src_handle.c;
     struct cx_hash_map_element_s *elm = iter->elem_handle;
     if (map->base.store_pointer) {
         return *(void **) elm->data;
@@ -269,15 +269,13 @@
 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;
 
     // remove current element, if asked
-    if (iter->base.remove) {
-        // obtain mutable pointer to the map
-        struct cx_mut_iterator_s *miter = it;
-        struct cx_hash_map_s *map = miter->src_handle;
+    if (iter->remove) {
 
         // clear the flag
-        iter->base.remove = false;
+        iter->remove = false;
 
         // determine the next element
         struct cx_hash_map_element_s *next = elm->next;
@@ -306,7 +304,6 @@
     }
 
     // search the next bucket, if required
-    struct cx_hash_map_s const *map = iter->src_handle;
     while (elm == NULL && ++iter->slot < map->bucket_count) {
         elm = map->buckets[iter->slot];
     }
@@ -332,30 +329,30 @@
 ) {
     CxIterator iter;
 
-    iter.src_handle = map;
+    iter.src_handle.c = map;
     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;
+            iter.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;
+            iter.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;
+            iter.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;
+    iter.valid = cx_hash_map_iter_valid;
+    iter.next = cx_hash_map_iter_next;
+    iter.remove = false;
+    iter.mutating = false;
 
     iter.slot = 0;
     iter.index = 0;
--- a/src/iterator.c	Thu May 23 18:21:36 2024 +0200
+++ b/src/iterator.c	Thu May 23 19:29:14 2024 +0200
@@ -41,30 +41,27 @@
 }
 
 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;
+    struct cx_iterator_s *iter = it;
+    if (iter->remove) {
+        iter->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)
+            void *last = ((char *) iter->src_handle.m)
                          + 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;
+    struct cx_iterator_s *iter = it;
+    if (iter->remove) {
+        iter->remove = false;
         iter->elem_count--;
 
         // number of elements to move
@@ -77,30 +74,29 @@
             );
         }
     } else {
-        struct cx_iterator_s *iter = it;
         iter->index++;
         iter->elem_handle = ((char *) iter->elem_handle) + iter->elem_size;
     }
 }
 
-CxMutIterator cxMutIterator(
+CxIterator cxMutIterator(
         void *array,
         size_t elem_size,
         size_t elem_count,
         bool remove_keeps_order
 ) {
-    CxMutIterator iter;
+    CxIterator iter;
 
     iter.index = 0;
-    iter.src_handle = array;
+    iter.src_handle.m = 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;
+    iter.valid = cx_iter_valid;
+    iter.current = cx_iter_current;
+    iter.next = remove_keeps_order ? cx_iter_next_slow : cx_iter_next_fast;
+    iter.remove = false;
+    iter.mutating = true;
 
     return iter;
 }
@@ -110,11 +106,7 @@
         size_t elem_size,
         size_t elem_count
 ) {
-    CxMutIterator iter = cxMutIterator((void*)array, elem_size, elem_count, false);
-    iter.base.mutating = false;
-
-    // we know the iterators share the same memory layout
-    CxIterator ret;
-    memcpy(&ret, &iter, sizeof(CxIterator));
-    return ret;
+    CxIterator iter = cxMutIterator((void*)array, elem_size, elem_count, false);
+    iter.mutating = false;
+    return iter;
 }
--- a/src/linked_list.c	Thu May 23 18:21:36 2024 +0200
+++ b/src/linked_list.c	Thu May 23 19:29:14 2024 +0200
@@ -816,12 +816,11 @@
 }
 
 static void cx_ll_iter_next(void *it) {
-    struct cx_iterator_base_s *itbase = it;
-    if (itbase->remove) {
-        itbase->remove = false;
-        struct cx_mut_iterator_s *iter = it;
-        struct cx_list_s *list = iter->src_handle;
-        cx_linked_list *ll = iter->src_handle;
+    struct cx_iterator_s *iter = it;
+    if (iter->remove) {
+        iter->remove = false;
+        struct cx_list_s *list = iter->src_handle.m;
+        cx_linked_list *ll = iter->src_handle.m;
         cx_linked_list_node *node = iter->elem_handle;
         iter->elem_handle = node->next;
         cx_invoke_destructor(list, node->payload);
@@ -830,7 +829,6 @@
         list->size--;
         cxFree(list->allocator, node);
     } else {
-        struct cx_iterator_s *iter = it;
         iter->index++;
         cx_linked_list_node *node = iter->elem_handle;
         iter->elem_handle = node->next;
@@ -838,12 +836,11 @@
 }
 
 static void cx_ll_iter_prev(void *it) {
-    struct cx_iterator_base_s *itbase = it;
-    if (itbase->remove) {
-        itbase->remove = false;
-        struct cx_mut_iterator_s *iter = it;
-        struct cx_list_s *list = iter->src_handle;
-        cx_linked_list *ll = iter->src_handle;
+    struct cx_iterator_s *iter = it;
+    if (iter->remove) {
+        iter->remove = false;
+        struct cx_list_s *list = iter->src_handle.m;
+        cx_linked_list *ll = iter->src_handle.m;
         cx_linked_list_node *node = iter->elem_handle;
         iter->elem_handle = node->prev;
         iter->index--;
@@ -853,7 +850,6 @@
         list->size--;
         cxFree(list->allocator, node);
     } else {
-        struct cx_iterator_s *iter = it;
         iter->index--;
         cx_linked_list_node *node = iter->elem_handle;
         iter->elem_handle = node->prev;
@@ -873,24 +869,24 @@
 ) {
     CxIterator iter;
     iter.index = index;
-    iter.src_handle = list;
+    iter.src_handle.c = 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;
-    iter.base.mutating = false;
-    iter.base.remove = false;
+    iter.valid = cx_ll_iter_valid;
+    iter.current = cx_ll_iter_current;
+    iter.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next;
+    iter.mutating = false;
+    iter.remove = false;
     return iter;
 }
 
 static int cx_ll_insert_iter(
-        CxMutIterator *iter,
+        CxIterator *iter,
         void const *elem,
         int prepend
 ) {
-    struct cx_list_s *list = iter->src_handle;
+    struct cx_list_s *list = iter->src_handle.m;
     cx_linked_list_node *node = iter->elem_handle;
     if (node != NULL) {
         assert(prepend >= 0 && prepend <= 1);
--- a/src/list.c	Thu May 23 18:21:36 2024 +0200
+++ b/src/list.c	Thu May 23 19:29:14 2024 +0200
@@ -80,11 +80,11 @@
 }
 
 static int cx_pl_insert_iter(
-        struct cx_mut_iterator_s *iter,
+        struct cx_iterator_s *iter,
         void const *elem,
         int prepend
 ) {
-    struct cx_list_s *list = iter->src_handle;
+    struct cx_list_s *list = iter->src_handle.m;
     return list->climpl->insert_iter(iter, &elem, prepend);
 }
 
@@ -148,7 +148,7 @@
 
 static void *cx_pl_iter_current(void const *it) {
     struct cx_iterator_s const *iter = it;
-    void **ptr = iter->base.current_impl(it);
+    void **ptr = iter->current_impl(it);
     return ptr == NULL ? NULL : *ptr;
 }
 
@@ -158,8 +158,8 @@
         bool backwards
 ) {
     struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards);
-    iter.base.current_impl = iter.base.current;
-    iter.base.current = cx_pl_iter_current;
+    iter.current_impl = iter.current;
+    iter.current = cx_pl_iter_current;
     return iter;
 }
 
@@ -235,9 +235,9 @@
         __attribute__((__unused__)) bool backwards
 ) {
     CxIterator iter = {0};
-    iter.src_handle = list;
+    iter.src_handle.c = list;
     iter.index = index;
-    iter.base.valid = cx_emptyl_iter_valid;
+    iter.valid = cx_emptyl_iter_valid;
     return iter;
 }
 
@@ -317,28 +317,20 @@
     }
 }
 
-CxMutIterator cxListMutIteratorAt(
+CxIterator cxListMutIteratorAt(
         CxList *list,
         size_t index
 ) {
     CxIterator it = list->cl->iterator(list, index, false);
-    it.base.mutating = true;
-
-    // we know the iterators share the same memory layout
-    CxMutIterator iter;
-    memcpy(&iter, &it, sizeof(CxMutIterator));
-    return iter;
+    it.mutating = true;
+    return it;
 }
 
-CxMutIterator cxListMutBackwardsIteratorAt(
+CxIterator cxListMutBackwardsIteratorAt(
         CxList *list,
         size_t index
 ) {
     CxIterator it = list->cl->iterator(list, index, true);
-    it.base.mutating = true;
-
-    // we know the iterators share the same memory layout
-    CxMutIterator iter;
-    memcpy(&iter, &it, sizeof(CxMutIterator));
-    return iter;
+    it.mutating = true;
+    return it;
 }
--- a/src/map.c	Thu May 23 18:21:36 2024 +0200
+++ b/src/map.c	Thu May 23 19:29:14 2024 +0200
@@ -51,8 +51,8 @@
         __attribute__((__unused__)) enum cx_map_iterator_type type
 ) {
     CxIterator iter = {0};
-    iter.src_handle = map;
-    iter.base.valid = cx_empty_map_iter_valid;
+    iter.src_handle.c = map;
+    iter.valid = cx_empty_map_iter_valid;
     return iter;
 }
 
@@ -81,32 +81,20 @@
 
 // </editor-fold>
 
-CxMutIterator cxMapMutIteratorValues(CxMap *map) {
+CxIterator cxMapMutIteratorValues(CxMap *map) {
     CxIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_VALUES);
-    it.base.mutating = true;
-
-    // we know the iterators share the same memory layout
-    CxMutIterator iter;
-    memcpy(&iter, &it, sizeof(CxMutIterator));
-    return iter;
+    it.mutating = true;
+    return it;
 }
 
-CxMutIterator cxMapMutIteratorKeys(CxMap *map) {
+CxIterator cxMapMutIteratorKeys(CxMap *map) {
     CxIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_KEYS);
-    it.base.mutating = true;
-
-    // we know the iterators share the same memory layout
-    CxMutIterator iter;
-    memcpy(&iter, &it, sizeof(CxMutIterator));
-    return iter;
+    it.mutating = true;
+    return it;
 }
 
-CxMutIterator cxMapMutIterator(CxMap *map) {
+CxIterator cxMapMutIterator(CxMap *map) {
     CxIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_PAIRS);
-    it.base.mutating = true;
-
-    // we know the iterators share the same memory layout
-    CxMutIterator iter;
-    memcpy(&iter, &it, sizeof(CxMutIterator));
-    return iter;
+    it.mutating = true;
+    return it;
 }
--- a/src/tree.c	Thu May 23 18:21:36 2024 +0200
+++ b/src/tree.c	Thu May 23 19:29:14 2024 +0200
@@ -205,10 +205,10 @@
         cx_tree_iter_search_next:
         // check if there is a sibling
         if (iter->exiting) {
-            next = iter->next;
+            next = iter->node_next;
         } else {
             next = tree_next(iter->node);
-            iter->next = next;
+            iter->node_next = next;
         }
         if (next == NULL) {
             // no sibling, we are done with this node and exit
@@ -220,7 +220,7 @@
                 if (iter->depth == 1) {
                     // there is no parent - we have iterated the entire tree
                     // invalidate the iterator and free the node stack
-                    iter->node = iter->next = NULL;
+                    iter->node = iter->node_next = NULL;
                     iter->stack_capacity = iter->depth = 0;
                     free(iter->stack);
                     iter->stack = NULL;
@@ -272,7 +272,7 @@
 
     // visit the root node
     iter.node = root;
-    iter.next = NULL;
+    iter.node_next = NULL;
     iter.counter = 1;
     iter.depth = 1;
     iter.stack[0] = root;
@@ -280,12 +280,12 @@
     iter.skip = false;
 
     // assign base iterator functions
-    iter.base.mutating = false;
-    iter.base.remove = false;
-    iter.base.current_impl = NULL;
-    iter.base.valid = cx_tree_iter_valid;
-    iter.base.next = cx_tree_iter_next;
-    iter.base.current = cx_tree_iter_current;
+    iter.mutating = false;
+    iter.remove = false;
+    iter.current_impl = NULL;
+    iter.valid = cx_tree_iter_valid;
+    iter.next = cx_tree_iter_next;
+    iter.current = cx_tree_iter_current;
 
     return iter;
 }
@@ -389,12 +389,12 @@
     iter.queue_last = NULL;
 
     // assign base iterator functions
-    iter.base.mutating = false;
-    iter.base.remove = false;
-    iter.base.current_impl = NULL;
-    iter.base.valid = cx_tree_visitor_valid;
-    iter.base.next = cx_tree_visitor_next;
-    iter.base.current = cx_tree_visitor_current;
+    iter.mutating = false;
+    iter.remove = false;
+    iter.current_impl = NULL;
+    iter.valid = cx_tree_visitor_valid;
+    iter.next = cx_tree_visitor_next;
+    iter.current = cx_tree_visitor_current;
 
     return iter;
 }
--- a/tests/test_hash_map.c	Thu May 23 18:21:36 2024 +0200
+++ b/tests/test_hash_map.c	Thu May 23 19:29:14 2024 +0200
@@ -240,7 +240,7 @@
         cxMapPut(map, "key 5", (void *) "val 5");
         cxMapPut(map, "key 6", (void *) "val 6");
 
-        CxMutIterator iter = cxMapMutIterator(map);
+        CxIterator iter = cxMapMutIterator(map);
         cx_foreach(CxMapEntry*, entry, iter) {
             if (((char const *)entry->key->data)[4] % 2 == 1) cxIteratorFlagRemoval(iter);
         }
@@ -313,13 +313,13 @@
     cxMapPut(map, k5, (void *) v5);
 
     {
-        CxMutIterator iter = cxMapMutIteratorKeys(map);
+        CxIterator iter = cxMapMutIteratorKeys(map);
         cx_foreach(CxHashKey*, key, iter) {
             if (((char*)key->data)[4] == '1') cxIteratorFlagRemoval(iter);
         }
     }
     {
-        CxMutIterator iter = cxMapMutIteratorValues(map);
+        CxIterator iter = cxMapMutIteratorValues(map);
         cx_foreach(char*, v, iter) {
             if (v[4] == '5') cxIteratorFlagRemoval(iter);
         }
@@ -380,9 +380,9 @@
     CxIterator it1 = cxMapIterator(map);
     CxIterator it2 = cxMapIteratorValues(map);
     CxIterator it3 = cxMapIteratorKeys(map);
-    CxMutIterator it4 = cxMapMutIterator(map);
-    CxMutIterator it5 = cxMapMutIteratorValues(map);
-    CxMutIterator it6 = cxMapMutIteratorKeys(map);
+    CxIterator it4 = cxMapMutIterator(map);
+    CxIterator it5 = cxMapMutIteratorValues(map);
+    CxIterator it6 = cxMapMutIteratorKeys(map);
 
     CX_TEST_DO {
         CX_TEST_ASSERT(!cxIteratorValid(it1));
--- a/tests/test_iterator.c	Thu May 23 18:21:36 2024 +0200
+++ b/tests/test_iterator.c	Thu May 23 19:29:14 2024 +0200
@@ -40,7 +40,7 @@
         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.src_handle.c == array);
         CX_TEST_ASSERT(iter.elem_handle == &array[0]);
         CX_TEST_ASSERT(cxIteratorValid(iter));
     }
@@ -52,7 +52,7 @@
         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.src_handle.c == NULL);
         CX_TEST_ASSERT(iter.elem_handle == NULL);
         CX_TEST_ASSERT(!cxIteratorValid(iter));
     }
@@ -71,7 +71,7 @@
             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.src_handle.c == array);
             CX_TEST_ASSERT(iter.elem_handle == &array[expected]);
             expected++;
         }
@@ -96,7 +96,7 @@
             0, 2, 4, 6, 8, 10, 12, 14, 16, 18
     };
 
-    CxMutIterator iter = cxMutIterator(array, sizeof(unsigned), size, true);
+    CxIterator iter = cxMutIterator(array, sizeof(unsigned), size, true);
     CX_TEST_DO {
         unsigned expected = 0;
         cx_foreach(unsigned *, e, iter) {
@@ -104,7 +104,7 @@
             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.src_handle.m == array);
             CX_TEST_ASSERT(iter.elem_handle == &array[indices[expected]]);
             expected++;
             if (expected % 2 == 0) {
@@ -141,7 +141,7 @@
             15, 6, 14, 7, 13, 8, 12, 9, 11, 10
     };
 
-    CxMutIterator iter = cxMutIterator(array, sizeof(unsigned), size, false);
+    CxIterator iter = cxMutIterator(array, sizeof(unsigned), size, false);
     CX_TEST_DO {
         unsigned expected = 0;
         cx_foreach(unsigned *, e, iter) {
@@ -149,7 +149,7 @@
             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.src_handle.m == array);
             CX_TEST_ASSERT(iter.elem_handle == &array[indices[expected]]);
             expected++;
             if (expected % 2 == 0) {
--- a/tests/test_list.c	Thu May 23 18:21:36 2024 +0200
+++ b/tests/test_list.c	Thu May 23 19:29:14 2024 +0200
@@ -632,8 +632,8 @@
 
     CxIterator it1 = cxListIterator(list);
     CxIterator it2 = cxListBackwardsIterator(list);
-    CxMutIterator it3 = cxListMutIterator(list);
-    CxMutIterator it4 = cxListMutBackwardsIterator(list);
+    CxIterator it3 = cxListMutIterator(list);
+    CxIterator it4 = cxListMutBackwardsIterator(list);
 
     CX_TEST_DO {
         CX_TEST_ASSERT(!cxIteratorValid(it1));
@@ -1224,7 +1224,7 @@
     }
     CX_TEST_ASSERT(i == 0);
     i = len / 2;
-    CxMutIterator mut_iter = cxListMutIteratorAt(list, i);
+    CxIterator 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;
@@ -1258,7 +1258,7 @@
     cx_for_n(i, 5) cxListAdd(list, &fivenums[i]);
     int newdata[] = array_init(10, 20, 30, 40, 50);
 
-    CxMutIterator iter = cxListMutIteratorAt(list, 2);
+    CxIterator iter = cxListMutIteratorAt(list, 2);
     CX_TEST_ASSERT(cxIteratorValid(iter));
     CX_TEST_ASSERT(iter.index == 2);
     CX_TEST_ASSERT(*(int *) cxIteratorCurrent(iter) == 2);
@@ -1365,7 +1365,7 @@
     CX_TEST_ASSERT(testdata[48] == destr_last_value + off);
     CX_TEST_ASSERT(testdata_len - destr_test_ctr == cxListSize(list));
 
-    CxMutIterator iter = cxListMutIteratorAt(list, 7);
+    CxIterator iter = cxListMutIteratorAt(list, 7);
     cxIteratorNext(iter);
     CX_TEST_ASSERT(2 == destr_test_ctr);
     CX_TEST_ASSERT(testdata[48] == destr_last_value + off);
--- a/tests/test_tree.c	Thu May 23 18:21:36 2024 +0200
+++ b/tests/test_tree.c	Thu May 23 19:29:14 2024 +0200
@@ -260,8 +260,8 @@
         CX_TEST_ASSERT(!iter.exiting);
         CX_TEST_ASSERT(iter.counter == 1);
         CX_TEST_ASSERT(iter.node == &root);
-        CX_TEST_ASSERT(!iter.base.mutating);
-        CX_TEST_ASSERT(!iter.base.remove);
+        CX_TEST_ASSERT(!iter.mutating);
+        CX_TEST_ASSERT(!iter.remove);
         CX_TEST_ASSERT(iter.stack != NULL);
         CX_TEST_ASSERT(iter.stack_capacity > 0);
         CX_TEST_ASSERT(iter.stack_size == 1);
@@ -517,8 +517,8 @@
         CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);
         CX_TEST_ASSERT(iter.counter == 1);
         CX_TEST_ASSERT(iter.node == &root);
-        CX_TEST_ASSERT(!iter.base.mutating);
-        CX_TEST_ASSERT(!iter.base.remove);
+        CX_TEST_ASSERT(!iter.mutating);
+        CX_TEST_ASSERT(!iter.remove);
         CX_TEST_ASSERT(iter.queue_next != NULL);
         CX_TEST_ASSERT(iter.queue_last != NULL);
         CX_TEST_ASSERT(iter.depth == 1);

mercurial