# HG changeset patch
# User Mike Becker <universe@uap-core.de>
# Date 1669478321 -3600
# Node ID ac5e7f789048d7482c218bef227b5822e05f41ec
# Parent  6c81ee4f11adf73bf4dd9c76fb6d2c694d420fe0
separate iterators and mutating iterators

Trade tons of code duplication for const-correctness.

diff -r 6c81ee4f11ad -r ac5e7f789048 src/array_list.c
--- a/src/array_list.c	Wed Nov 23 22:40:55 2022 +0100
+++ b/src/array_list.c	Sat Nov 26 16:58:41 2022 +0100
@@ -243,7 +243,7 @@
 }
 
 static int cx_arl_insert_iter(
-        struct cx_iterator_s *iter,
+        struct cx_mut_iterator_s *iter,
         void const *elem,
         int prepend
 ) {
@@ -367,20 +367,25 @@
     }
 }
 
-static bool cx_arl_iter_valid(struct cx_iterator_s const *iter) {
+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;
     return iter->index < list->size;
 }
 
-static void *cx_arl_iter_current(struct cx_iterator_s const *iter) {
+static void *cx_arl_iter_current(void const *it) {
+    struct cx_iterator_s const *iter = it;
     return iter->elem_handle;
 }
 
-static void cx_arl_iter_next(struct cx_iterator_s *iter) {
-    if (iter->remove) {
-        iter->remove = false;
+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);
     } else {
+        struct cx_iterator_s *iter = it;
         iter->index++;
         iter->elem_handle =
                 ((char *) iter->elem_handle)
@@ -388,8 +393,18 @@
     }
 }
 
+static bool cx_arl_iter_flag_rm(void *it) {
+    struct cx_iterator_base_s *iter = it;
+    if (iter->mutating) {
+        iter->remove = true;
+        return true;
+    } else {
+        return false;
+    }
+}
+
 static struct cx_iterator_s cx_arl_iterator(
-        struct cx_list_s *list,
+        struct cx_list_s const *list,
         size_t index
 ) {
     struct cx_iterator_s iter;
@@ -397,11 +412,26 @@
     iter.index = index;
     iter.src_handle = list;
     iter.elem_handle = cx_arl_at(list, index);
-    iter.valid = cx_arl_iter_valid;
-    iter.current = cx_arl_iter_current;
-    iter.next = cx_arl_iter_next;
-    iter.remove = false;
+    iter.base.valid = cx_arl_iter_valid;
+    iter.base.current = cx_arl_iter_current;
+    iter.base.next = cx_arl_iter_next;
+    iter.base.flag_removal = cx_arl_iter_flag_rm;
+    iter.base.remove = false;
+    iter.base.mutating = false;
+
+    return iter;
+}
 
+static struct cx_mut_iterator_s cx_arl_mut_iterator(
+        struct cx_list_s *list,
+        size_t index
+) {
+    CxIterator it = cx_arl_iterator(list, index);
+    it.base.mutating = true;
+
+    // we know the iterators share the same memory layout
+    CxMutIterator iter;
+    memcpy(&iter, &it, sizeof(CxMutIterator));
     return iter;
 }
 
@@ -418,6 +448,7 @@
         cx_arl_compare,
         cx_arl_reverse,
         cx_arl_iterator,
+        cx_arl_mut_iterator,
 };
 
 CxList *cxArrayListCreate(
diff -r 6c81ee4f11ad -r ac5e7f789048 src/cx/iterator.h
--- a/src/cx/iterator.h	Wed Nov 23 22:40:55 2022 +0100
+++ b/src/cx/iterator.h	Sat Nov 26 16:58:41 2022 +0100
@@ -40,26 +40,53 @@
 #include "common.h"
 
 /**
- * Internal iterator struct - use CxIterator.
+ * The base of mutating and non-mutating iterators.
  */
-struct cx_iterator_s {
+struct cx_iterator_base_s {
     /**
      * True iff the iterator points to valid data.
      */
     __attribute__ ((__nonnull__))
-    bool (*valid)(struct cx_iterator_s const *);
+    bool (*valid)(void const *);
 
     /**
      * Returns a pointer to the current element.
      */
     __attribute__ ((__nonnull__))
-    void *(*current)(struct cx_iterator_s const *);
+    void *(*current)(void const *);
 
     /**
      * Advances the iterator.
      */
     __attribute__ ((__nonnull__))
-    void (*next)(struct cx_iterator_s *);
+    void (*next)(void *);
+
+    /**
+     * Flag current element for removal, if possible.
+     */
+    __attribute__ ((__nonnull__))
+    bool (*flag_removal)(void *);
+
+    /**
+     * Indicates whether this iterator is muting.
+     */
+    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.
@@ -79,7 +106,7 @@
         /**
          * A pointer to the key.
          */
-        void *key;
+        void const *key;
         /**
          * A pointer to the value.
          */
@@ -97,13 +124,70 @@
      * Otherwise, this field is usually uninitialized.
      */
     size_t index;
+};
+
+/**
+ * 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.
+ *
+ * @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;
 
     /**
-     * Users may set this to true, if the current element shall be removed from the underlying collection
-     * when the iterator advances.
-     * Has no effect on iterators that are not based on a collection.
+     * 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.
      */
-    bool remove;
+    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;
 };
 
 /**
@@ -112,10 +196,11 @@
  * 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 (elements added or removed),
- * the iterator becomes invalid (regardless of what cxIteratorValid() returns) and MUST be re-obtained
- * from 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 make this iterator invalid (regardless of what cxIteratorValid() returns).
+ *
+ * @see CxMutIterator
  */
 typedef struct cx_iterator_s CxIterator;
 
@@ -124,36 +209,35 @@
  *
  * This is especially false for past-the-end iterators.
  *
- * @param iter a pointer to the iterator
+ * @param iter the iterator
  * @return true iff the iterator points to valid data
  */
-__attribute__ ((__nonnull__))
-static inline bool cxIteratorValid(CxIterator const *iter) {
-    return iter->valid(iter);
-}
+#define cxIteratorValid(iter) (iter).base.valid(&(iter))
 
 /**
  * Returns a pointer to the current element.
  *
  * The behavior is undefined if this iterator is invalid.
  *
- * @param iter a pointer to the iterator
+ * @param iter the iterator
  * @return a pointer to the current element
  */
-__attribute__ ((__nonnull__))
-static inline void *cxIteratorCurrent(CxIterator const *iter) {
-    return iter->current(iter);
-}
+#define cxIteratorCurrent(iter) (iter).base.current(&iter)
 
 /**
  * Advances the iterator to the next element.
  *
- * @param iter a pointer to the iterator
+ * @param iter the iterator
  */
-__attribute__ ((__nonnull__))
-static inline void cxIteratorNext(CxIterator *iter) {
-    iter->next(iter);
-}
+#define cxIteratorNext(iter) (iter).base.next(&iter)
+
+/**
+ * Flags the current element for removal.
+ *
+ * @param iter the iterator
+ * @return false if this iterator cannot remove the element
+ */
+#define cxIteratorFlagRemoval(iter) (iter).base.flag_removal(&iter)
 
 /**
  * Loops over an iterator.
@@ -162,6 +246,6 @@
  * @param iter the iterator
  */
 #define cx_foreach(type, elem, iter) \
-for (type elem; cxIteratorValid(&iter) && (elem = (type)cxIteratorCurrent(&iter)) != NULL ; cxIteratorNext(&iter)) // NOLINT(bugprone-macro-parentheses)
+for (type elem; cxIteratorValid(iter) && (elem = (type)cxIteratorCurrent(iter)) != NULL ; cxIteratorNext(iter))
 
 #endif // UCX_ITERATOR_H
diff -r 6c81ee4f11ad -r ac5e7f789048 src/cx/list.h
--- a/src/cx/list.h	Wed Nov 23 22:40:55 2022 +0100
+++ b/src/cx/list.h	Sat Nov 26 16:58:41 2022 +0100
@@ -151,7 +151,7 @@
      * Member function for inserting an element relative to an iterator position.
      */
     int (*insert_iter)(
-            struct cx_iterator_s *iter,
+            struct cx_mut_iterator_s *iter,
             void const *elem,
             int prepend
     );
@@ -202,6 +202,14 @@
      * Returns an iterator pointing to the specified index.
      */
     struct cx_iterator_s (*iterator)(
+            struct cx_list_s const *list,
+            size_t index
+    );
+
+    /**
+     * Returns a mutating iterator pointing to the specified index.
+     */
+    struct cx_mut_iterator_s (*mut_iterator)(
             struct cx_list_s *list,
             size_t index
     );
@@ -289,7 +297,7 @@
  */
 __attribute__((__nonnull__))
 static inline int cxListInsertAfter(
-        CxIterator *iter,
+        CxMutIterator *iter,
         void const *elem
 ) {
     return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 0);
@@ -312,7 +320,7 @@
  */
 __attribute__((__nonnull__))
 static inline int cxListInsertBefore(
-        CxIterator *iter,
+        CxMutIterator *iter,
         void const *elem
 ) {
     return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 1);
@@ -360,10 +368,29 @@
  */
 __attribute__((__nonnull__, __warn_unused_result__))
 static inline CxIterator cxListIterator(
+        CxList const *list,
+        size_t index
+) {
+    return list->cl->iterator(list, index);
+}
+
+/**
+ * Returns a mutating iterator pointing to the item at the specified index.
+ *
+ * The returned iterator is position-aware.
+ *
+ * If the index is out of range, a past-the-end iterator will be returned.
+ *
+ * @param list the list
+ * @param index the index where the iterator shall point at
+ * @return a new iterator
+ */
+__attribute__((__nonnull__, __warn_unused_result__))
+static inline CxMutIterator cxListMutIterator(
         CxList *list,
         size_t index
 ) {
-    return list->cl->iterator(list, index);
+    return list->cl->mut_iterator(list, index);
 }
 
 /**
@@ -377,11 +404,26 @@
  * @return a new iterator
  */
 __attribute__((__nonnull__, __warn_unused_result__))
-static inline CxIterator cxListBegin(CxList *list) {
+static inline CxIterator cxListBegin(CxList const *list) {
     return list->cl->iterator(list, 0);
 }
 
 /**
+ * Returns a mutating iterator pointing to the first item of the list.
+ *
+ * The returned iterator is position-aware.
+ *
+ * If the list is empty, a past-the-end iterator will be returned.
+ *
+ * @param list the list
+ * @return a new iterator
+ */
+__attribute__((__nonnull__, __warn_unused_result__))
+static inline CxMutIterator cxListBeginMut(CxList *list) {
+    return list->cl->mut_iterator(list, 0);
+}
+
+/**
  * Returns the index of the first element that equals \p elem.
  *
  * Determining equality is performed by the list's comparator function.
diff -r 6c81ee4f11ad -r ac5e7f789048 src/cx/map.h
--- a/src/cx/map.h	Wed Nov 23 22:40:55 2022 +0100
+++ b/src/cx/map.h	Sat Nov 26 16:58:41 2022 +0100
@@ -114,19 +114,37 @@
      * Iterator over the key/value pairs.
      */
     __attribute__((__nonnull__, __warn_unused_result__))
-    CxIterator (*iterator)(CxMap *map);
+    CxIterator (*iterator)(CxMap const *map);
 
     /**
      * Iterator over the keys.
      */
     __attribute__((__nonnull__, __warn_unused_result__))
-    CxIterator (*iterator_keys)(CxMap *map);
+    CxIterator (*iterator_keys)(CxMap const *map);
 
     /**
      * Iterator over the values.
      */
     __attribute__((__nonnull__, __warn_unused_result__))
-    CxIterator (*iterator_values)(CxMap *map);
+    CxIterator (*iterator_values)(CxMap const *map);
+
+    /**
+     * Mutating iterator over the key/value pairs.
+     */
+    __attribute__((__nonnull__, __warn_unused_result__))
+    CxMutIterator (*mut_iterator)(CxMap *map);
+
+    /**
+     * Mutating iterator over the keys.
+     */
+    __attribute__((__nonnull__, __warn_unused_result__))
+    CxMutIterator (*mut_iterator_keys)(CxMap *map);
+
+    /**
+     * Mutating iterator over the values.
+     */
+    __attribute__((__nonnull__, __warn_unused_result__))
+    CxMutIterator (*mut_iterator_values)(CxMap *map);
 };
 
 /**
@@ -263,6 +281,55 @@
     return map->cl->iterator(map);
 }
 
+
+/**
+ * Creates a mutating iterator over the values of a map.
+ *
+ * \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.
+ *
+ * @param map the map to create the iterator for
+ * @return an iterator for the currently stored values
+ */
+__attribute__((__nonnull__, __warn_unused_result__))
+static inline CxMutIterator cxMapMutIteratorValues(CxMap *map) {
+    return map->cl->mut_iterator_values(map);
+}
+
+/**
+ * Creates a mutating iterator over the keys of a map.
+ *
+ * The elements of the iterator are keys of type 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.
+ *
+ * @param map the map to create the iterator for
+ * @return an iterator for the currently stored keys
+ */
+__attribute__((__nonnull__, __warn_unused_result__))
+static inline CxMutIterator cxMapMutIteratorKeys(CxMap *map) {
+    return map->cl->mut_iterator_keys(map);
+}
+
+/**
+ * Creates a mutating iterator for a map.
+ *
+ * The elements of the iterator are key/value pairs of type 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.
+ *
+ * @param map the map to create the iterator for
+ * @return an iterator for the currently stored entries
+ * @see cxMapMutIteratorKeys()
+ * @see cxMapMutIteratorValues()
+ */
+__attribute__((__nonnull__, __warn_unused_result__))
+static inline CxMutIterator cxMapMutIterator(CxMap *map) {
+    return map->cl->mut_iterator(map);
+}
+
 #ifdef    __cplusplus
 }
 #endif
diff -r 6c81ee4f11ad -r ac5e7f789048 src/hash_map.c
--- a/src/hash_map.c	Wed Nov 23 22:40:55 2022 +0100
+++ b/src/hash_map.c	Sat Nov 26 16:58:41 2022 +0100
@@ -201,34 +201,42 @@
     return cx_hash_map_get_remove(map, key, true);
 }
 
-static void *cx_hash_map_iter_current_entry(CxIterator const *iter) {
+static void *cx_hash_map_iter_current_entry(void const *it) {
+    struct cx_iterator_s const *iter = it;
     // struct has to have a compatible signature
     return (struct cx_map_entry_s *) &(iter->kv_data);
 }
 
-static void *cx_hash_map_iter_current_key(CxIterator const *iter) {
+static void *cx_hash_map_iter_current_key(void const *it) {
+    struct cx_iterator_s const *iter = it;
     struct cx_hash_map_element_s *elm = iter->elem_handle;
     return &elm->key;
 }
 
-static void *cx_hash_map_iter_current_value(CxIterator const *iter) {
+static void *cx_hash_map_iter_current_value(void const *it) {
+    struct cx_iterator_s const *iter = it;
     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) {
+static bool cx_hash_map_iter_valid(void const *it) {
+    struct cx_iterator_s const *iter = it;
     return iter->elem_handle != NULL;
 }
 
-static void cx_hash_map_iter_next(CxIterator *iter) {
-    struct cx_hash_map_s *map = iter->src_handle;
+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;
 
     // remove current element, if asked
-    if (iter->remove) {
+    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;
+
         // clear the flag
-        iter->remove = false;
+        iter->base.remove = false;
 
         // determine the next element
         struct cx_hash_map_element_s *next = elm->next;
@@ -254,6 +262,7 @@
     }
 
     // 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];
     }
@@ -270,17 +279,29 @@
     }
 }
 
-static CxIterator cx_hash_map_iterator(CxMap *map) {
+static bool cx_hash_map_iter_flag_rm(void *it) {
+    struct cx_iterator_base_s *iter = it;
+    if (iter->mutating) {
+        iter->remove = true;
+        return true;
+    } else {
+        return false;
+    }
+}
+
+static CxIterator cx_hash_map_iterator(CxMap const *map) {
     CxIterator 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.base.valid = cx_hash_map_iter_valid;
+    iter.base.next = cx_hash_map_iter_next;
+    iter.base.current = cx_hash_map_iter_current_entry;
+    iter.base.flag_removal = cx_hash_map_iter_flag_rm;
+    iter.base.remove = false;
+    iter.base.mutating = false;
 
     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;
@@ -301,15 +322,37 @@
     return iter;
 }
 
-static CxIterator cx_hash_map_iterator_keys(CxMap *map) {
+static CxIterator cx_hash_map_iterator_keys(CxMap const *map) {
     CxIterator iter = cx_hash_map_iterator(map);
-    iter.current = cx_hash_map_iter_current_key;
+    iter.base.current = cx_hash_map_iter_current_key;
+    return iter;
+}
+
+static CxIterator cx_hash_map_iterator_values(CxMap const *map) {
+    CxIterator iter = cx_hash_map_iterator(map);
+    iter.base.current = cx_hash_map_iter_current_value;
     return 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;
+static CxMutIterator cx_hash_map_mut_iterator(CxMap *map) {
+    CxIterator it = cx_hash_map_iterator(map);
+    it.base.mutating = true;
+
+    // we know the iterators share the same memory layout
+    CxMutIterator iter;
+    memcpy(&iter, &it, sizeof(CxMutIterator));
+    return iter;
+}
+
+static CxMutIterator cx_hash_map_mut_iterator_keys(CxMap *map) {
+    CxMutIterator iter = cx_hash_map_mut_iterator(map);
+    iter.base.current = cx_hash_map_iter_current_key;
+    return iter;
+}
+
+static CxMutIterator cx_hash_map_mut_iterator_values(CxMap *map) {
+    CxMutIterator iter = cx_hash_map_mut_iterator(map);
+    iter.base.current = cx_hash_map_iter_current_value;
     return iter;
 }
 
@@ -322,6 +365,9 @@
         cx_hash_map_iterator,
         cx_hash_map_iterator_keys,
         cx_hash_map_iterator_values,
+        cx_hash_map_mut_iterator,
+        cx_hash_map_mut_iterator_keys,
+        cx_hash_map_mut_iterator_values,
 };
 
 CxMap *cxHashMapCreate(
diff -r 6c81ee4f11ad -r ac5e7f789048 src/linked_list.c
--- a/src/linked_list.c	Wed Nov 23 22:40:55 2022 +0100
+++ b/src/linked_list.c	Sat Nov 26 16:58:41 2022 +0100
@@ -643,13 +643,16 @@
                                   left->follow_ptr, right->follow_ptr, list->cmpfunc);
 }
 
-static bool cx_ll_iter_valid(CxIterator const *iter) {
+static bool cx_ll_iter_valid(void const *it) {
+    struct cx_iterator_s const *iter = it;
     return iter->elem_handle != NULL;
 }
 
-static void cx_ll_iter_next(CxIterator *iter) {
-    if (iter->remove) {
-        iter->remove = false;
+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;
         cx_linked_list *ll = iter->src_handle;
         cx_linked_list_node *node = iter->elem_handle;
         iter->elem_handle = node->next;
@@ -658,48 +661,85 @@
         ll->base.size--;
         cxFree(ll->base.allocator, node);
     } else {
+        struct cx_iterator_s *iter = it;
         iter->index++;
         cx_linked_list_node *node = iter->elem_handle;
         iter->elem_handle = node->next;
     }
 }
 
-static void *cx_ll_iter_current(CxIterator const *iter) {
+static void *cx_ll_iter_current(void const *it) {
+    struct cx_iterator_s const *iter = it;
     cx_linked_list_node *node = iter->elem_handle;
     return node->payload;
 }
 
-static void *cx_pll_iter_current(CxIterator const *iter) {
+static void *cx_pll_iter_current(void const *it) {
+    struct cx_iterator_s const *iter = it;
     cx_linked_list_node *node = iter->elem_handle;
     return *(void **) node->payload;
 }
 
+static bool cx_ll_iter_flag_rm(void *it) {
+    struct cx_iterator_base_s *iter = it;
+    if (iter->mutating) {
+        iter->remove = true;
+        return true;
+    } else {
+        return false;
+    }
+}
+
 static CxIterator cx_ll_iterator(
-        struct cx_list_s *list,
+        struct cx_list_s const *list,
         size_t index
 ) {
     CxIterator iter;
     iter.index = index;
     iter.src_handle = list;
     iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index);
-    iter.valid = cx_ll_iter_valid;
-    iter.current = cx_ll_iter_current;
-    iter.next = cx_ll_iter_next;
-    iter.remove = false;
+    iter.base.valid = cx_ll_iter_valid;
+    iter.base.current = cx_ll_iter_current;
+    iter.base.next = cx_ll_iter_next;
+    iter.base.flag_removal = cx_ll_iter_flag_rm;
+    iter.base.mutating = false;
+    iter.base.remove = false;
     return iter;
 }
 
 static CxIterator cx_pll_iterator(
+        struct cx_list_s const *list,
+        size_t index
+) {
+    CxIterator iter = cx_ll_iterator(list, index);
+    iter.base.current = cx_pll_iter_current;
+    return iter;
+}
+
+static CxMutIterator cx_ll_mut_iterator(
         struct cx_list_s *list,
         size_t index
 ) {
-    CxIterator iter = cx_ll_iterator(list, index);
-    iter.current = cx_pll_iter_current;
+    CxIterator it = cx_ll_iterator(list, index);
+    it.base.mutating = true;
+
+    // we know the iterators share the same memory layout
+    CxMutIterator iter;
+    memcpy(&iter, &it, sizeof(CxMutIterator));
+    return iter;
+}
+
+static CxMutIterator cx_pll_mut_iterator(
+        struct cx_list_s *list,
+        size_t index
+) {
+    CxMutIterator iter = cx_ll_mut_iterator(list, index);
+    iter.base.current = cx_pll_iter_current;
     return iter;
 }
 
 static int cx_ll_insert_iter(
-        CxIterator *iter,
+        CxMutIterator *iter,
         void const *elem,
         int prepend
 ) {
@@ -719,7 +759,7 @@
 }
 
 static int cx_pll_insert_iter(
-        CxIterator *iter,
+        CxMutIterator *iter,
         void const *elem,
         int prepend
 ) {
@@ -750,7 +790,8 @@
         cx_ll_sort,
         cx_ll_compare,
         cx_ll_reverse,
-        cx_ll_iterator
+        cx_ll_iterator,
+        cx_ll_mut_iterator,
 };
 
 static cx_list_class cx_pointer_linked_list_class = {
@@ -766,6 +807,7 @@
         cx_ll_compare,
         cx_ll_reverse,
         cx_pll_iterator,
+        cx_pll_mut_iterator,
 };
 
 CxList *cxLinkedListCreate(
diff -r 6c81ee4f11ad -r ac5e7f789048 src/list.c
--- a/src/list.c	Wed Nov 23 22:40:55 2022 +0100
+++ b/src/list.c	Sat Nov 26 16:58:41 2022 +0100
@@ -62,18 +62,17 @@
     } else {
         // different compare functions, use iterator
         if (list->size == other->size) {
-            // TODO: we would need a const iterator
             CxIterator left = cxListBegin(list);
             CxIterator right = cxListBegin(other);
             for (size_t i = 0; i < list->size; i++) {
-                void *leftValue = cxIteratorCurrent(&left);
-                void *rightValue = cxIteratorCurrent(&right);
+                void *leftValue = cxIteratorCurrent(left);
+                void *rightValue = cxIteratorCurrent(right);
                 int d = list->cmpfunc(leftValue, rightValue);
                 if (d != 0) {
                     return d;
                 }
-                cxIteratorNext(&left);
-                cxIteratorNext(&right);
+                cxIteratorNext(left);
+                cxIteratorNext(right);
             }
             return 0;
         } else {
diff -r 6c81ee4f11ad -r ac5e7f789048 test/test_list.cpp
--- a/test/test_list.cpp	Wed Nov 23 22:40:55 2022 +0100
+++ b/test/test_list.cpp	Sat Nov 26 16:58:41 2022 +0100
@@ -686,11 +686,11 @@
 
     void verifyIterator(CxList *list) const {
         int i = 0;
-        CxIterator iter = cxListBegin(list);
+        auto iter = cxListBeginMut(list);
         cx_foreach(int*, x, iter) {
             ASSERT_EQ(iter.index, (size_t) (i + 1) / 2);
             ASSERT_EQ(*x, testdata.data[i]);
-            if (i % 2 == 1) iter.remove = true;
+            if (i % 2 == 1) cxIteratorFlagRemoval(iter);
             i++;
         }
         auto len = testdata_len;
@@ -702,31 +702,31 @@
     static void verifyInsertViaIterator(CxList *list) {
         int newdata[] = {10, 20, 30, 40, 50};
 
-        CxIterator iter = cxListIterator(list, 2);
-        EXPECT_TRUE(cxIteratorValid(&iter));
+        auto iter = cxListMutIterator(list, 2);
+        EXPECT_TRUE(cxIteratorValid(iter));
         EXPECT_EQ(iter.index, 2);
-        EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2);
+        EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2);
         cxListInsertAfter(&iter, &newdata[0]);
-        EXPECT_TRUE(cxIteratorValid(&iter));
+        EXPECT_TRUE(cxIteratorValid(iter));
         EXPECT_EQ(iter.index, 2);
-        EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2);
+        EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2);
         cxListInsertBefore(&iter, &newdata[1]);
-        EXPECT_TRUE(cxIteratorValid(&iter));
+        EXPECT_TRUE(cxIteratorValid(iter));
         EXPECT_EQ(iter.index, 3);
-        EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2);
+        EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2);
 
-        iter = cxListBegin(list);
+        iter = cxListBeginMut(list);
         cxListInsertBefore(&iter, &newdata[2]);
-        EXPECT_TRUE(cxIteratorValid(&iter));
+        EXPECT_TRUE(cxIteratorValid(iter));
         EXPECT_EQ(iter.index, 1);
-        EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 0);
-        iter = cxListIterator(list, list->size);
+        EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 0);
+        iter = cxListMutIterator(list, list->size);
         cxListInsertBefore(&iter, &newdata[3]);
-        EXPECT_FALSE(cxIteratorValid(&iter));
+        EXPECT_FALSE(cxIteratorValid(iter));
         EXPECT_EQ(iter.index, 9);
-        iter = cxListIterator(list, list->size);
+        iter = cxListMutIterator(list, list->size);
         cxListInsertAfter(&iter, &newdata[4]);
-        EXPECT_FALSE(cxIteratorValid(&iter));
+        EXPECT_FALSE(cxIteratorValid(iter));
         EXPECT_EQ(iter.index, 10);
 
         int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50};
diff -r 6c81ee4f11ad -r ac5e7f789048 test/test_map.cpp
--- a/test/test_map.cpp	Wed Nov 23 22:40:55 2022 +0100
+++ b/test/test_map.cpp	Sat Nov 26 16:58:41 2022 +0100
@@ -183,9 +183,9 @@
     cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5");
     cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6");
 
-    auto iter = cxMapIterator(map);
+    auto iter = cxMapMutIterator(map);
     cx_foreach(CxMapEntry*, entry, iter) {
-        if (entry->key->data.cstr[4] % 2 == 1) iter.remove = true;
+        if (entry->key->data.cstr[4] % 2 == 1) cxIteratorFlagRemoval(iter);
     }
     EXPECT_EQ(map->size, 3);
     EXPECT_EQ(iter.index, map->size);