Mercurial > hg > ucx / changeset

     1.1 --- a/src/array_list.c	Wed Nov 23 22:40:55 2022 +0100
     1.2 +++ b/src/array_list.c	Sat Nov 26 16:58:41 2022 +0100
     1.3 @@ -243,7 +243,7 @@
     1.4  }
     1.5  
     1.6  static int cx_arl_insert_iter(
     1.7 -        struct cx_iterator_s *iter,
     1.8 +        struct cx_mut_iterator_s *iter,
     1.9          void const *elem,
    1.10          int prepend
    1.11  ) {
    1.12 @@ -367,20 +367,25 @@
    1.13      }
    1.14  }
    1.15  
    1.16 -static bool cx_arl_iter_valid(struct cx_iterator_s const *iter) {
    1.17 +static bool cx_arl_iter_valid(void const *it) {
    1.18 +    struct cx_iterator_s const *iter = it;
    1.19      struct cx_list_s const *list = iter->src_handle;
    1.20      return iter->index < list->size;
    1.21  }
    1.22  
    1.23 -static void *cx_arl_iter_current(struct cx_iterator_s const *iter) {
    1.24 +static void *cx_arl_iter_current(void const *it) {
    1.25 +    struct cx_iterator_s const *iter = it;
    1.26      return iter->elem_handle;
    1.27  }
    1.28  
    1.29 -static void cx_arl_iter_next(struct cx_iterator_s *iter) {
    1.30 -    if (iter->remove) {
    1.31 -        iter->remove = false;
    1.32 +static void cx_arl_iter_next(void *it) {
    1.33 +    struct cx_iterator_base_s *itbase = it;
    1.34 +    if (itbase->remove) {
    1.35 +        struct cx_mut_iterator_s *iter = it;
    1.36 +        itbase->remove = false;
    1.37          cx_arl_remove(iter->src_handle, iter->index);
    1.38      } else {
    1.39 +        struct cx_iterator_s *iter = it;
    1.40          iter->index++;
    1.41          iter->elem_handle =
    1.42                  ((char *) iter->elem_handle)
    1.43 @@ -388,8 +393,18 @@
    1.44      }
    1.45  }
    1.46  
    1.47 +static bool cx_arl_iter_flag_rm(void *it) {
    1.48 +    struct cx_iterator_base_s *iter = it;
    1.49 +    if (iter->mutating) {
    1.50 +        iter->remove = true;
    1.51 +        return true;
    1.52 +    } else {
    1.53 +        return false;
    1.54 +    }
    1.55 +}
    1.56 +
    1.57  static struct cx_iterator_s cx_arl_iterator(
    1.58 -        struct cx_list_s *list,
    1.59 +        struct cx_list_s const *list,
    1.60          size_t index
    1.61  ) {
    1.62      struct cx_iterator_s iter;
    1.63 @@ -397,14 +412,29 @@
    1.64      iter.index = index;
    1.65      iter.src_handle = list;
    1.66      iter.elem_handle = cx_arl_at(list, index);
    1.67 -    iter.valid = cx_arl_iter_valid;
    1.68 -    iter.current = cx_arl_iter_current;
    1.69 -    iter.next = cx_arl_iter_next;
    1.70 -    iter.remove = false;
    1.71 +    iter.base.valid = cx_arl_iter_valid;
    1.72 +    iter.base.current = cx_arl_iter_current;
    1.73 +    iter.base.next = cx_arl_iter_next;
    1.74 +    iter.base.flag_removal = cx_arl_iter_flag_rm;
    1.75 +    iter.base.remove = false;
    1.76 +    iter.base.mutating = false;
    1.77  
    1.78      return iter;
    1.79  }
    1.80  
    1.81 +static struct cx_mut_iterator_s cx_arl_mut_iterator(
    1.82 +        struct cx_list_s *list,
    1.83 +        size_t index
    1.84 +) {
    1.85 +    CxIterator it = cx_arl_iterator(list, index);
    1.86 +    it.base.mutating = true;
    1.87 +
    1.88 +    // we know the iterators share the same memory layout
    1.89 +    CxMutIterator iter;
    1.90 +    memcpy(&iter, &it, sizeof(CxMutIterator));
    1.91 +    return iter;
    1.92 +}
    1.93 +
    1.94  static cx_list_class cx_array_list_class = {
    1.95          cx_arl_destructor,
    1.96          cx_arl_add,
    1.97 @@ -418,6 +448,7 @@
    1.98          cx_arl_compare,
    1.99          cx_arl_reverse,
   1.100          cx_arl_iterator,
   1.101 +        cx_arl_mut_iterator,
   1.102  };
   1.103  
   1.104  CxList *cxArrayListCreate(

     2.1 --- a/src/cx/iterator.h	Wed Nov 23 22:40:55 2022 +0100
     2.2 +++ b/src/cx/iterator.h	Sat Nov 26 16:58:41 2022 +0100
     2.3 @@ -40,26 +40,53 @@
     2.4  #include "common.h"
     2.5  
     2.6  /**
     2.7 - * Internal iterator struct - use CxIterator.
     2.8 + * The base of mutating and non-mutating iterators.
     2.9   */
    2.10 -struct cx_iterator_s {
    2.11 +struct cx_iterator_base_s {
    2.12      /**
    2.13       * True iff the iterator points to valid data.
    2.14       */
    2.15      __attribute__ ((__nonnull__))
    2.16 -    bool (*valid)(struct cx_iterator_s const *);
    2.17 +    bool (*valid)(void const *);
    2.18  
    2.19      /**
    2.20       * Returns a pointer to the current element.
    2.21       */
    2.22      __attribute__ ((__nonnull__))
    2.23 -    void *(*current)(struct cx_iterator_s const *);
    2.24 +    void *(*current)(void const *);
    2.25  
    2.26      /**
    2.27       * Advances the iterator.
    2.28       */
    2.29      __attribute__ ((__nonnull__))
    2.30 -    void (*next)(struct cx_iterator_s *);
    2.31 +    void (*next)(void *);
    2.32 +
    2.33 +    /**
    2.34 +     * Flag current element for removal, if possible.
    2.35 +     */
    2.36 +    __attribute__ ((__nonnull__))
    2.37 +    bool (*flag_removal)(void *);
    2.38 +
    2.39 +    /**
    2.40 +     * Indicates whether this iterator is muting.
    2.41 +     */
    2.42 +    bool mutating;
    2.43 +
    2.44 +    /**
    2.45 +     * Internal flag for removing the current element when advancing.
    2.46 +     */
    2.47 +    bool remove;
    2.48 +};
    2.49 +
    2.50 +/**
    2.51 + * Internal iterator struct - use CxMutIterator.
    2.52 + */
    2.53 +struct cx_mut_iterator_s {
    2.54 +
    2.55 +    /**
    2.56 +     * The base properties of this iterator.
    2.57 +     */
    2.58 +    struct cx_iterator_base_s base;
    2.59  
    2.60      /**
    2.61       * Handle for the current element, if required.
    2.62 @@ -79,7 +106,7 @@
    2.63          /**
    2.64           * A pointer to the key.
    2.65           */
    2.66 -        void *key;
    2.67 +        void const *key;
    2.68          /**
    2.69           * A pointer to the value.
    2.70           */
    2.71 @@ -97,13 +124,70 @@
    2.72       * Otherwise, this field is usually uninitialized.
    2.73       */
    2.74      size_t index;
    2.75 +};
    2.76 +
    2.77 +/**
    2.78 + * Mutating iterator value type.
    2.79 + *
    2.80 + * An iterator points to a certain element in an (possibly unbounded) chain of elements.
    2.81 + * Iterators that are based on collections (which have a defined "first" element), are supposed
    2.82 + * to be "position-aware", which means that they keep track of the current index within the collection.
    2.83 + *
    2.84 + * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the
    2.85 + * iterator is based on a collection and the underlying collection is mutated by other means than this iterator
    2.86 + * (e.g. elements added or removed), the iterator becomes invalid (regardless of what cxIteratorValid() returns)
    2.87 + * and MUST be re-obtained from the collection.
    2.88 + *
    2.89 + * @see CxIterator
    2.90 + */
    2.91 +typedef struct cx_mut_iterator_s CxMutIterator;
    2.92 +
    2.93 +/**
    2.94 + * Internal iterator struct - use CxIterator.
    2.95 + */
    2.96 +struct cx_iterator_s {
    2.97  
    2.98      /**
    2.99 -     * Users may set this to true, if the current element shall be removed from the underlying collection
   2.100 -     * when the iterator advances.
   2.101 -     * Has no effect on iterators that are not based on a collection.
   2.102 +     * The base properties of this iterator.
   2.103       */
   2.104 -    bool remove;
   2.105 +    struct cx_iterator_base_s base;
   2.106 +
   2.107 +    /**
   2.108 +     * Handle for the current element, if required.
   2.109 +     */
   2.110 +    void *elem_handle;
   2.111 +
   2.112 +    /**
   2.113 +     * Handle for the source collection, if any.
   2.114 +     */
   2.115 +    void const *src_handle;
   2.116 +
   2.117 +    /**
   2.118 +     * Field for storing a key-value pair.
   2.119 +     * May be used by iterators that iterate over k/v-collections.
   2.120 +     */
   2.121 +    struct {
   2.122 +        /**
   2.123 +         * A pointer to the key.
   2.124 +         */
   2.125 +        void const *key;
   2.126 +        /**
   2.127 +         * A pointer to the value.
   2.128 +         */
   2.129 +        void *value;
   2.130 +    } kv_data;
   2.131 +
   2.132 +    /**
   2.133 +     * Field for storing a slot number.
   2.134 +     * May be used by iterators that iterate over multi-bucket collections.
   2.135 +     */
   2.136 +    size_t slot;
   2.137 +
   2.138 +    /**
   2.139 +     * If the iterator is position-aware, contains the index of the element in the underlying collection.
   2.140 +     * Otherwise, this field is usually uninitialized.
   2.141 +     */
   2.142 +    size_t index;
   2.143  };
   2.144  
   2.145  /**
   2.146 @@ -112,10 +196,11 @@
   2.147   * Iterators that are based on collections (which have a defined "first" element), are supposed
   2.148   * to be "position-aware", which means that they keep track of the current index within the collection.
   2.149   *
   2.150 - * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the
   2.151 - * iterator is based on a collection and the underlying collection is mutated (elements added or removed),
   2.152 - * the iterator becomes invalid (regardless of what cxIteratorValid() returns) and MUST be re-obtained
   2.153 - * from the collection.
   2.154 + * @note Objects that are pointed to by an iterator are always mutable through that iterator. However,
   2.155 + * this iterator cannot mutate the collection itself (add or remove elements) and any mutation of the
   2.156 + * collection by other means make this iterator invalid (regardless of what cxIteratorValid() returns).
   2.157 + *
   2.158 + * @see CxMutIterator
   2.159   */
   2.160  typedef struct cx_iterator_s CxIterator;
   2.161  
   2.162 @@ -124,36 +209,35 @@
   2.163   *
   2.164   * This is especially false for past-the-end iterators.
   2.165   *
   2.166 - * @param iter a pointer to the iterator
   2.167 + * @param iter the iterator
   2.168   * @return true iff the iterator points to valid data
   2.169   */
   2.170 -__attribute__ ((__nonnull__))
   2.171 -static inline bool cxIteratorValid(CxIterator const *iter) {
   2.172 -    return iter->valid(iter);
   2.173 -}
   2.174 +#define cxIteratorValid(iter) (iter).base.valid(&(iter))
   2.175  
   2.176  /**
   2.177   * Returns a pointer to the current element.
   2.178   *
   2.179   * The behavior is undefined if this iterator is invalid.
   2.180   *
   2.181 - * @param iter a pointer to the iterator
   2.182 + * @param iter the iterator
   2.183   * @return a pointer to the current element
   2.184   */
   2.185 -__attribute__ ((__nonnull__))
   2.186 -static inline void *cxIteratorCurrent(CxIterator const *iter) {
   2.187 -    return iter->current(iter);
   2.188 -}
   2.189 +#define cxIteratorCurrent(iter) (iter).base.current(&iter)
   2.190  
   2.191  /**
   2.192   * Advances the iterator to the next element.
   2.193   *
   2.194 - * @param iter a pointer to the iterator
   2.195 + * @param iter the iterator
   2.196   */
   2.197 -__attribute__ ((__nonnull__))
   2.198 -static inline void cxIteratorNext(CxIterator *iter) {
   2.199 -    iter->next(iter);
   2.200 -}
   2.201 +#define cxIteratorNext(iter) (iter).base.next(&iter)
   2.202 +
   2.203 +/**
   2.204 + * Flags the current element for removal.
   2.205 + *
   2.206 + * @param iter the iterator
   2.207 + * @return false if this iterator cannot remove the element
   2.208 + */
   2.209 +#define cxIteratorFlagRemoval(iter) (iter).base.flag_removal(&iter)
   2.210  
   2.211  /**
   2.212   * Loops over an iterator.
   2.213 @@ -162,6 +246,6 @@
   2.214   * @param iter the iterator
   2.215   */
   2.216  #define cx_foreach(type, elem, iter) \
   2.217 -for (type elem; cxIteratorValid(&iter) && (elem = (type)cxIteratorCurrent(&iter)) != NULL ; cxIteratorNext(&iter)) // NOLINT(bugprone-macro-parentheses)
   2.218 +for (type elem; cxIteratorValid(iter) && (elem = (type)cxIteratorCurrent(iter)) != NULL ; cxIteratorNext(iter))
   2.219  
   2.220  #endif // UCX_ITERATOR_H

     3.1 --- a/src/cx/list.h	Wed Nov 23 22:40:55 2022 +0100
     3.2 +++ b/src/cx/list.h	Sat Nov 26 16:58:41 2022 +0100
     3.3 @@ -151,7 +151,7 @@
     3.4       * Member function for inserting an element relative to an iterator position.
     3.5       */
     3.6      int (*insert_iter)(
     3.7 -            struct cx_iterator_s *iter,
     3.8 +            struct cx_mut_iterator_s *iter,
     3.9              void const *elem,
    3.10              int prepend
    3.11      );
    3.12 @@ -202,6 +202,14 @@
    3.13       * Returns an iterator pointing to the specified index.
    3.14       */
    3.15      struct cx_iterator_s (*iterator)(
    3.16 +            struct cx_list_s const *list,
    3.17 +            size_t index
    3.18 +    );
    3.19 +
    3.20 +    /**
    3.21 +     * Returns a mutating iterator pointing to the specified index.
    3.22 +     */
    3.23 +    struct cx_mut_iterator_s (*mut_iterator)(
    3.24              struct cx_list_s *list,
    3.25              size_t index
    3.26      );
    3.27 @@ -289,7 +297,7 @@
    3.28   */
    3.29  __attribute__((__nonnull__))
    3.30  static inline int cxListInsertAfter(
    3.31 -        CxIterator *iter,
    3.32 +        CxMutIterator *iter,
    3.33          void const *elem
    3.34  ) {
    3.35      return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 0);
    3.36 @@ -312,7 +320,7 @@
    3.37   */
    3.38  __attribute__((__nonnull__))
    3.39  static inline int cxListInsertBefore(
    3.40 -        CxIterator *iter,
    3.41 +        CxMutIterator *iter,
    3.42          void const *elem
    3.43  ) {
    3.44      return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 1);
    3.45 @@ -360,10 +368,29 @@
    3.46   */
    3.47  __attribute__((__nonnull__, __warn_unused_result__))
    3.48  static inline CxIterator cxListIterator(
    3.49 +        CxList const *list,
    3.50 +        size_t index
    3.51 +) {
    3.52 +    return list->cl->iterator(list, index);
    3.53 +}
    3.54 +
    3.55 +/**
    3.56 + * Returns a mutating iterator pointing to the item at the specified index.
    3.57 + *
    3.58 + * The returned iterator is position-aware.
    3.59 + *
    3.60 + * If the index is out of range, a past-the-end iterator will be returned.
    3.61 + *
    3.62 + * @param list the list
    3.63 + * @param index the index where the iterator shall point at
    3.64 + * @return a new iterator
    3.65 + */
    3.66 +__attribute__((__nonnull__, __warn_unused_result__))
    3.67 +static inline CxMutIterator cxListMutIterator(
    3.68          CxList *list,
    3.69          size_t index
    3.70  ) {
    3.71 -    return list->cl->iterator(list, index);
    3.72 +    return list->cl->mut_iterator(list, index);
    3.73  }
    3.74  
    3.75  /**
    3.76 @@ -377,11 +404,26 @@
    3.77   * @return a new iterator
    3.78   */
    3.79  __attribute__((__nonnull__, __warn_unused_result__))
    3.80 -static inline CxIterator cxListBegin(CxList *list) {
    3.81 +static inline CxIterator cxListBegin(CxList const *list) {
    3.82      return list->cl->iterator(list, 0);
    3.83  }
    3.84  
    3.85  /**
    3.86 + * Returns a mutating iterator pointing to the first item of the list.
    3.87 + *
    3.88 + * The returned iterator is position-aware.
    3.89 + *
    3.90 + * If the list is empty, a past-the-end iterator will be returned.
    3.91 + *
    3.92 + * @param list the list
    3.93 + * @return a new iterator
    3.94 + */
    3.95 +__attribute__((__nonnull__, __warn_unused_result__))
    3.96 +static inline CxMutIterator cxListBeginMut(CxList *list) {
    3.97 +    return list->cl->mut_iterator(list, 0);
    3.98 +}
    3.99 +
   3.100 +/**
   3.101   * Returns the index of the first element that equals \p elem.
   3.102   *
   3.103   * Determining equality is performed by the list's comparator function.

     4.1 --- a/src/cx/map.h	Wed Nov 23 22:40:55 2022 +0100
     4.2 +++ b/src/cx/map.h	Sat Nov 26 16:58:41 2022 +0100
     4.3 @@ -114,19 +114,37 @@
     4.4       * Iterator over the key/value pairs.
     4.5       */
     4.6      __attribute__((__nonnull__, __warn_unused_result__))
     4.7 -    CxIterator (*iterator)(CxMap *map);
     4.8 +    CxIterator (*iterator)(CxMap const *map);
     4.9  
    4.10      /**
    4.11       * Iterator over the keys.
    4.12       */
    4.13      __attribute__((__nonnull__, __warn_unused_result__))
    4.14 -    CxIterator (*iterator_keys)(CxMap *map);
    4.15 +    CxIterator (*iterator_keys)(CxMap const *map);
    4.16  
    4.17      /**
    4.18       * Iterator over the values.
    4.19       */
    4.20      __attribute__((__nonnull__, __warn_unused_result__))
    4.21 -    CxIterator (*iterator_values)(CxMap *map);
    4.22 +    CxIterator (*iterator_values)(CxMap const *map);
    4.23 +
    4.24 +    /**
    4.25 +     * Mutating iterator over the key/value pairs.
    4.26 +     */
    4.27 +    __attribute__((__nonnull__, __warn_unused_result__))
    4.28 +    CxMutIterator (*mut_iterator)(CxMap *map);
    4.29 +
    4.30 +    /**
    4.31 +     * Mutating iterator over the keys.
    4.32 +     */
    4.33 +    __attribute__((__nonnull__, __warn_unused_result__))
    4.34 +    CxMutIterator (*mut_iterator_keys)(CxMap *map);
    4.35 +
    4.36 +    /**
    4.37 +     * Mutating iterator over the values.
    4.38 +     */
    4.39 +    __attribute__((__nonnull__, __warn_unused_result__))
    4.40 +    CxMutIterator (*mut_iterator_values)(CxMap *map);
    4.41  };
    4.42  
    4.43  /**
    4.44 @@ -263,6 +281,55 @@
    4.45      return map->cl->iterator(map);
    4.46  }
    4.47  
    4.48 +
    4.49 +/**
    4.50 + * Creates a mutating iterator over the values of a map.
    4.51 + *
    4.52 + * \note An iterator iterates over all elements successively. Therefore the order
    4.53 + * highly depends on the map implementation and may change arbitrarily when the contents change.
    4.54 + *
    4.55 + * @param map the map to create the iterator for
    4.56 + * @return an iterator for the currently stored values
    4.57 + */
    4.58 +__attribute__((__nonnull__, __warn_unused_result__))
    4.59 +static inline CxMutIterator cxMapMutIteratorValues(CxMap *map) {
    4.60 +    return map->cl->mut_iterator_values(map);
    4.61 +}
    4.62 +
    4.63 +/**
    4.64 + * Creates a mutating iterator over the keys of a map.
    4.65 + *
    4.66 + * The elements of the iterator are keys of type CxHashKey.
    4.67 + *
    4.68 + * \note An iterator iterates over all elements successively. Therefore the order
    4.69 + * highly depends on the map implementation and may change arbitrarily when the contents change.
    4.70 + *
    4.71 + * @param map the map to create the iterator for
    4.72 + * @return an iterator for the currently stored keys
    4.73 + */
    4.74 +__attribute__((__nonnull__, __warn_unused_result__))
    4.75 +static inline CxMutIterator cxMapMutIteratorKeys(CxMap *map) {
    4.76 +    return map->cl->mut_iterator_keys(map);
    4.77 +}
    4.78 +
    4.79 +/**
    4.80 + * Creates a mutating iterator for a map.
    4.81 + *
    4.82 + * The elements of the iterator are key/value pairs of type CxMapEntry.
    4.83 + *
    4.84 + * \note An iterator iterates over all elements successively. Therefore the order
    4.85 + * highly depends on the map implementation and may change arbitrarily when the contents change.
    4.86 + *
    4.87 + * @param map the map to create the iterator for
    4.88 + * @return an iterator for the currently stored entries
    4.89 + * @see cxMapMutIteratorKeys()
    4.90 + * @see cxMapMutIteratorValues()
    4.91 + */
    4.92 +__attribute__((__nonnull__, __warn_unused_result__))
    4.93 +static inline CxMutIterator cxMapMutIterator(CxMap *map) {
    4.94 +    return map->cl->mut_iterator(map);
    4.95 +}
    4.96 +
    4.97  #ifdef    __cplusplus
    4.98  }
    4.99  #endif

     5.1 --- a/src/hash_map.c	Wed Nov 23 22:40:55 2022 +0100
     5.2 +++ b/src/hash_map.c	Sat Nov 26 16:58:41 2022 +0100
     5.3 @@ -201,34 +201,42 @@
     5.4      return cx_hash_map_get_remove(map, key, true);
     5.5  }
     5.6  
     5.7 -static void *cx_hash_map_iter_current_entry(CxIterator const *iter) {
     5.8 +static void *cx_hash_map_iter_current_entry(void const *it) {
     5.9 +    struct cx_iterator_s const *iter = it;
    5.10      // struct has to have a compatible signature
    5.11      return (struct cx_map_entry_s *) &(iter->kv_data);
    5.12  }
    5.13  
    5.14 -static void *cx_hash_map_iter_current_key(CxIterator const *iter) {
    5.15 +static void *cx_hash_map_iter_current_key(void const *it) {
    5.16 +    struct cx_iterator_s const *iter = it;
    5.17      struct cx_hash_map_element_s *elm = iter->elem_handle;
    5.18      return &elm->key;
    5.19  }
    5.20  
    5.21 -static void *cx_hash_map_iter_current_value(CxIterator const *iter) {
    5.22 +static void *cx_hash_map_iter_current_value(void const *it) {
    5.23 +    struct cx_iterator_s const *iter = it;
    5.24      struct cx_hash_map_element_s *elm = iter->elem_handle;
    5.25      // TODO: return a pointer to data if this map is storing copies
    5.26      return elm->data;
    5.27  }
    5.28  
    5.29 -static bool cx_hash_map_iter_valid(CxIterator const *iter) {
    5.30 +static bool cx_hash_map_iter_valid(void const *it) {
    5.31 +    struct cx_iterator_s const *iter = it;
    5.32      return iter->elem_handle != NULL;
    5.33  }
    5.34  
    5.35 -static void cx_hash_map_iter_next(CxIterator *iter) {
    5.36 -    struct cx_hash_map_s *map = iter->src_handle;
    5.37 +static void cx_hash_map_iter_next(void *it) {
    5.38 +    struct cx_iterator_s *iter = it;
    5.39      struct cx_hash_map_element_s *elm = iter->elem_handle;
    5.40  
    5.41      // remove current element, if asked
    5.42 -    if (iter->remove) {
    5.43 +    if (iter->base.remove) {
    5.44 +        // obtain mutable pointer to the map
    5.45 +        struct cx_mut_iterator_s *miter = it;
    5.46 +        struct cx_hash_map_s *map = miter->src_handle;
    5.47 +
    5.48          // clear the flag
    5.49 -        iter->remove = false;
    5.50 +        iter->base.remove = false;
    5.51  
    5.52          // determine the next element
    5.53          struct cx_hash_map_element_s *next = elm->next;
    5.54 @@ -254,6 +262,7 @@
    5.55      }
    5.56  
    5.57      // search the next bucket, if required
    5.58 +    struct cx_hash_map_s const *map = iter->src_handle;
    5.59      while (elm == NULL && ++iter->slot < map->bucket_count) {
    5.60          elm = map->buckets[iter->slot];
    5.61      }
    5.62 @@ -270,17 +279,29 @@
    5.63      }
    5.64  }
    5.65  
    5.66 -static CxIterator cx_hash_map_iterator(CxMap *map) {
    5.67 +static bool cx_hash_map_iter_flag_rm(void *it) {
    5.68 +    struct cx_iterator_base_s *iter = it;
    5.69 +    if (iter->mutating) {
    5.70 +        iter->remove = true;
    5.71 +        return true;
    5.72 +    } else {
    5.73 +        return false;
    5.74 +    }
    5.75 +}
    5.76 +
    5.77 +static CxIterator cx_hash_map_iterator(CxMap const *map) {
    5.78      CxIterator iter;
    5.79  
    5.80      iter.src_handle = map;
    5.81 -    iter.valid = cx_hash_map_iter_valid;
    5.82 -    iter.next = cx_hash_map_iter_next;
    5.83 -    iter.current = cx_hash_map_iter_current_entry;
    5.84 +    iter.base.valid = cx_hash_map_iter_valid;
    5.85 +    iter.base.next = cx_hash_map_iter_next;
    5.86 +    iter.base.current = cx_hash_map_iter_current_entry;
    5.87 +    iter.base.flag_removal = cx_hash_map_iter_flag_rm;
    5.88 +    iter.base.remove = false;
    5.89 +    iter.base.mutating = false;
    5.90  
    5.91      iter.slot = 0;
    5.92      iter.index = 0;
    5.93 -    iter.remove = false;
    5.94  
    5.95      if (map->size > 0) {
    5.96          struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
    5.97 @@ -301,15 +322,37 @@
    5.98      return iter;
    5.99  }
   5.100  
   5.101 -static CxIterator cx_hash_map_iterator_keys(CxMap *map) {
   5.102 +static CxIterator cx_hash_map_iterator_keys(CxMap const *map) {
   5.103      CxIterator iter = cx_hash_map_iterator(map);
   5.104 -    iter.current = cx_hash_map_iter_current_key;
   5.105 +    iter.base.current = cx_hash_map_iter_current_key;
   5.106      return iter;
   5.107  }
   5.108  
   5.109 -static CxIterator cx_hash_map_iterator_values(CxMap *map) {
   5.110 +static CxIterator cx_hash_map_iterator_values(CxMap const *map) {
   5.111      CxIterator iter = cx_hash_map_iterator(map);
   5.112 -    iter.current = cx_hash_map_iter_current_value;
   5.113 +    iter.base.current = cx_hash_map_iter_current_value;
   5.114 +    return iter;
   5.115 +}
   5.116 +
   5.117 +static CxMutIterator cx_hash_map_mut_iterator(CxMap *map) {
   5.118 +    CxIterator it = cx_hash_map_iterator(map);
   5.119 +    it.base.mutating = true;
   5.120 +
   5.121 +    // we know the iterators share the same memory layout
   5.122 +    CxMutIterator iter;
   5.123 +    memcpy(&iter, &it, sizeof(CxMutIterator));
   5.124 +    return iter;
   5.125 +}
   5.126 +
   5.127 +static CxMutIterator cx_hash_map_mut_iterator_keys(CxMap *map) {
   5.128 +    CxMutIterator iter = cx_hash_map_mut_iterator(map);
   5.129 +    iter.base.current = cx_hash_map_iter_current_key;
   5.130 +    return iter;
   5.131 +}
   5.132 +
   5.133 +static CxMutIterator cx_hash_map_mut_iterator_values(CxMap *map) {
   5.134 +    CxMutIterator iter = cx_hash_map_mut_iterator(map);
   5.135 +    iter.base.current = cx_hash_map_iter_current_value;
   5.136      return iter;
   5.137  }
   5.138  
   5.139 @@ -322,6 +365,9 @@
   5.140          cx_hash_map_iterator,
   5.141          cx_hash_map_iterator_keys,
   5.142          cx_hash_map_iterator_values,
   5.143 +        cx_hash_map_mut_iterator,
   5.144 +        cx_hash_map_mut_iterator_keys,
   5.145 +        cx_hash_map_mut_iterator_values,
   5.146  };
   5.147  
   5.148  CxMap *cxHashMapCreate(

     6.1 --- a/src/linked_list.c	Wed Nov 23 22:40:55 2022 +0100
     6.2 +++ b/src/linked_list.c	Sat Nov 26 16:58:41 2022 +0100
     6.3 @@ -643,13 +643,16 @@
     6.4                                    left->follow_ptr, right->follow_ptr, list->cmpfunc);
     6.5  }
     6.6  
     6.7 -static bool cx_ll_iter_valid(CxIterator const *iter) {
     6.8 +static bool cx_ll_iter_valid(void const *it) {
     6.9 +    struct cx_iterator_s const *iter = it;
    6.10      return iter->elem_handle != NULL;
    6.11  }
    6.12  
    6.13 -static void cx_ll_iter_next(CxIterator *iter) {
    6.14 -    if (iter->remove) {
    6.15 -        iter->remove = false;
    6.16 +static void cx_ll_iter_next(void *it) {
    6.17 +    struct cx_iterator_base_s *itbase = it;
    6.18 +    if (itbase->remove) {
    6.19 +        itbase->remove = false;
    6.20 +        struct cx_mut_iterator_s *iter = it;
    6.21          cx_linked_list *ll = iter->src_handle;
    6.22          cx_linked_list_node *node = iter->elem_handle;
    6.23          iter->elem_handle = node->next;
    6.24 @@ -658,48 +661,85 @@
    6.25          ll->base.size--;
    6.26          cxFree(ll->base.allocator, node);
    6.27      } else {
    6.28 +        struct cx_iterator_s *iter = it;
    6.29          iter->index++;
    6.30          cx_linked_list_node *node = iter->elem_handle;
    6.31          iter->elem_handle = node->next;
    6.32      }
    6.33  }
    6.34  
    6.35 -static void *cx_ll_iter_current(CxIterator const *iter) {
    6.36 +static void *cx_ll_iter_current(void const *it) {
    6.37 +    struct cx_iterator_s const *iter = it;
    6.38      cx_linked_list_node *node = iter->elem_handle;
    6.39      return node->payload;
    6.40  }
    6.41  
    6.42 -static void *cx_pll_iter_current(CxIterator const *iter) {
    6.43 +static void *cx_pll_iter_current(void const *it) {
    6.44 +    struct cx_iterator_s const *iter = it;
    6.45      cx_linked_list_node *node = iter->elem_handle;
    6.46      return *(void **) node->payload;
    6.47  }
    6.48  
    6.49 +static bool cx_ll_iter_flag_rm(void *it) {
    6.50 +    struct cx_iterator_base_s *iter = it;
    6.51 +    if (iter->mutating) {
    6.52 +        iter->remove = true;
    6.53 +        return true;
    6.54 +    } else {
    6.55 +        return false;
    6.56 +    }
    6.57 +}
    6.58 +
    6.59  static CxIterator cx_ll_iterator(
    6.60 -        struct cx_list_s *list,
    6.61 +        struct cx_list_s const *list,
    6.62          size_t index
    6.63  ) {
    6.64      CxIterator iter;
    6.65      iter.index = index;
    6.66      iter.src_handle = list;
    6.67      iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index);
    6.68 -    iter.valid = cx_ll_iter_valid;
    6.69 -    iter.current = cx_ll_iter_current;
    6.70 -    iter.next = cx_ll_iter_next;
    6.71 -    iter.remove = false;
    6.72 +    iter.base.valid = cx_ll_iter_valid;
    6.73 +    iter.base.current = cx_ll_iter_current;
    6.74 +    iter.base.next = cx_ll_iter_next;
    6.75 +    iter.base.flag_removal = cx_ll_iter_flag_rm;
    6.76 +    iter.base.mutating = false;
    6.77 +    iter.base.remove = false;
    6.78      return iter;
    6.79  }
    6.80  
    6.81  static CxIterator cx_pll_iterator(
    6.82 +        struct cx_list_s const *list,
    6.83 +        size_t index
    6.84 +) {
    6.85 +    CxIterator iter = cx_ll_iterator(list, index);
    6.86 +    iter.base.current = cx_pll_iter_current;
    6.87 +    return iter;
    6.88 +}
    6.89 +
    6.90 +static CxMutIterator cx_ll_mut_iterator(
    6.91          struct cx_list_s *list,
    6.92          size_t index
    6.93  ) {
    6.94 -    CxIterator iter = cx_ll_iterator(list, index);
    6.95 -    iter.current = cx_pll_iter_current;
    6.96 +    CxIterator it = cx_ll_iterator(list, index);
    6.97 +    it.base.mutating = true;
    6.98 +
    6.99 +    // we know the iterators share the same memory layout
   6.100 +    CxMutIterator iter;
   6.101 +    memcpy(&iter, &it, sizeof(CxMutIterator));
   6.102 +    return iter;
   6.103 +}
   6.104 +
   6.105 +static CxMutIterator cx_pll_mut_iterator(
   6.106 +        struct cx_list_s *list,
   6.107 +        size_t index
   6.108 +) {
   6.109 +    CxMutIterator iter = cx_ll_mut_iterator(list, index);
   6.110 +    iter.base.current = cx_pll_iter_current;
   6.111      return iter;
   6.112  }
   6.113  
   6.114  static int cx_ll_insert_iter(
   6.115 -        CxIterator *iter,
   6.116 +        CxMutIterator *iter,
   6.117          void const *elem,
   6.118          int prepend
   6.119  ) {
   6.120 @@ -719,7 +759,7 @@
   6.121  }
   6.122  
   6.123  static int cx_pll_insert_iter(
   6.124 -        CxIterator *iter,
   6.125 +        CxMutIterator *iter,
   6.126          void const *elem,
   6.127          int prepend
   6.128  ) {
   6.129 @@ -750,7 +790,8 @@
   6.130          cx_ll_sort,
   6.131          cx_ll_compare,
   6.132          cx_ll_reverse,
   6.133 -        cx_ll_iterator
   6.134 +        cx_ll_iterator,
   6.135 +        cx_ll_mut_iterator,
   6.136  };
   6.137  
   6.138  static cx_list_class cx_pointer_linked_list_class = {
   6.139 @@ -766,6 +807,7 @@
   6.140          cx_ll_compare,
   6.141          cx_ll_reverse,
   6.142          cx_pll_iterator,
   6.143 +        cx_pll_mut_iterator,
   6.144  };
   6.145  
   6.146  CxList *cxLinkedListCreate(

     7.1 --- a/src/list.c	Wed Nov 23 22:40:55 2022 +0100
     7.2 +++ b/src/list.c	Sat Nov 26 16:58:41 2022 +0100
     7.3 @@ -62,18 +62,17 @@
     7.4      } else {
     7.5          // different compare functions, use iterator
     7.6          if (list->size == other->size) {
     7.7 -            // TODO: we would need a const iterator
     7.8              CxIterator left = cxListBegin(list);
     7.9              CxIterator right = cxListBegin(other);
    7.10              for (size_t i = 0; i < list->size; i++) {
    7.11 -                void *leftValue = cxIteratorCurrent(&left);
    7.12 -                void *rightValue = cxIteratorCurrent(&right);
    7.13 +                void *leftValue = cxIteratorCurrent(left);
    7.14 +                void *rightValue = cxIteratorCurrent(right);
    7.15                  int d = list->cmpfunc(leftValue, rightValue);
    7.16                  if (d != 0) {
    7.17                      return d;
    7.18                  }
    7.19 -                cxIteratorNext(&left);
    7.20 -                cxIteratorNext(&right);
    7.21 +                cxIteratorNext(left);
    7.22 +                cxIteratorNext(right);
    7.23              }
    7.24              return 0;
    7.25          } else {

     8.1 --- a/test/test_list.cpp	Wed Nov 23 22:40:55 2022 +0100
     8.2 +++ b/test/test_list.cpp	Sat Nov 26 16:58:41 2022 +0100
     8.3 @@ -686,11 +686,11 @@
     8.4  
     8.5      void verifyIterator(CxList *list) const {
     8.6          int i = 0;
     8.7 -        CxIterator iter = cxListBegin(list);
     8.8 +        auto iter = cxListBeginMut(list);
     8.9          cx_foreach(int*, x, iter) {
    8.10              ASSERT_EQ(iter.index, (size_t) (i + 1) / 2);
    8.11              ASSERT_EQ(*x, testdata.data[i]);
    8.12 -            if (i % 2 == 1) iter.remove = true;
    8.13 +            if (i % 2 == 1) cxIteratorFlagRemoval(iter);
    8.14              i++;
    8.15          }
    8.16          auto len = testdata_len;
    8.17 @@ -702,31 +702,31 @@
    8.18      static void verifyInsertViaIterator(CxList *list) {
    8.19          int newdata[] = {10, 20, 30, 40, 50};
    8.20  
    8.21 -        CxIterator iter = cxListIterator(list, 2);
    8.22 -        EXPECT_TRUE(cxIteratorValid(&iter));
    8.23 +        auto iter = cxListMutIterator(list, 2);
    8.24 +        EXPECT_TRUE(cxIteratorValid(iter));
    8.25          EXPECT_EQ(iter.index, 2);
    8.26 -        EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2);
    8.27 +        EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2);
    8.28          cxListInsertAfter(&iter, &newdata[0]);
    8.29 -        EXPECT_TRUE(cxIteratorValid(&iter));
    8.30 +        EXPECT_TRUE(cxIteratorValid(iter));
    8.31          EXPECT_EQ(iter.index, 2);
    8.32 -        EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2);
    8.33 +        EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2);
    8.34          cxListInsertBefore(&iter, &newdata[1]);
    8.35 -        EXPECT_TRUE(cxIteratorValid(&iter));
    8.36 +        EXPECT_TRUE(cxIteratorValid(iter));
    8.37          EXPECT_EQ(iter.index, 3);
    8.38 -        EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2);
    8.39 +        EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2);
    8.40  
    8.41 -        iter = cxListBegin(list);
    8.42 +        iter = cxListBeginMut(list);
    8.43          cxListInsertBefore(&iter, &newdata[2]);
    8.44 -        EXPECT_TRUE(cxIteratorValid(&iter));
    8.45 +        EXPECT_TRUE(cxIteratorValid(iter));
    8.46          EXPECT_EQ(iter.index, 1);
    8.47 -        EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 0);
    8.48 -        iter = cxListIterator(list, list->size);
    8.49 +        EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 0);
    8.50 +        iter = cxListMutIterator(list, list->size);
    8.51          cxListInsertBefore(&iter, &newdata[3]);
    8.52 -        EXPECT_FALSE(cxIteratorValid(&iter));
    8.53 +        EXPECT_FALSE(cxIteratorValid(iter));
    8.54          EXPECT_EQ(iter.index, 9);
    8.55 -        iter = cxListIterator(list, list->size);
    8.56 +        iter = cxListMutIterator(list, list->size);
    8.57          cxListInsertAfter(&iter, &newdata[4]);
    8.58 -        EXPECT_FALSE(cxIteratorValid(&iter));
    8.59 +        EXPECT_FALSE(cxIteratorValid(iter));
    8.60          EXPECT_EQ(iter.index, 10);
    8.61  
    8.62          int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50};

     9.1 --- a/test/test_map.cpp	Wed Nov 23 22:40:55 2022 +0100
     9.2 +++ b/test/test_map.cpp	Sat Nov 26 16:58:41 2022 +0100
     9.3 @@ -183,9 +183,9 @@
     9.4      cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5");
     9.5      cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6");
     9.6  
     9.7 -    auto iter = cxMapIterator(map);
     9.8 +    auto iter = cxMapMutIterator(map);
     9.9      cx_foreach(CxMapEntry*, entry, iter) {
    9.10 -        if (entry->key->data.cstr[4] % 2 == 1) iter.remove = true;
    9.11 +        if (entry->key->data.cstr[4] % 2 == 1) cxIteratorFlagRemoval(iter);
    9.12      }
    9.13      EXPECT_EQ(map->size, 3);
    9.14      EXPECT_EQ(iter.index, map->size);