--- a/ucx/cx/iterator.h Sat Apr 20 13:01:58 2024 +0200
+++ b/ucx/cx/iterator.h Thu May 23 22:35:45 2024 +0200
@@ -30,7 +30,6 @@
* \brief Interface for iterator implementations.
* \author Mike Becker
* \author Olaf Wintermann
- * \version 3.0
* \copyright 2-Clause BSD License
*/
@@ -39,9 +38,6 @@
#include "common.h"
-/**
- * The base of mutating and non-mutating iterators.
- */
struct cx_iterator_base_s {
/**
* True iff the iterator points to valid data.
@@ -70,20 +66,10 @@
*/
__attribute__ ((__nonnull__))
void (*next)(void *);
-
- /**
- * Flag current element for removal, if possible.
- *
- * When valid returns false, the behavior of this function is undefined.
- */
- __attribute__ ((__nonnull__))
- bool (*flag_removal)(void *);
-
/**
* Indicates whether this iterator may remove elements.
*/
bool mutating;
-
/**
* Internal flag for removing the current element when advancing.
*/
@@ -91,24 +77,34 @@
};
/**
- * Internal iterator struct - use CxMutIterator.
+ * Declares base attributes for an iterator.
*/
-struct cx_mut_iterator_s {
+#define CX_ITERATOR_BASE struct cx_iterator_base_s base
+
+/**
+ * Internal iterator struct - use CxIterator.
+ */
+struct cx_iterator_s {
+ CX_ITERATOR_BASE;
/**
- * 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.
@@ -136,83 +132,29 @@
* 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;
};
/**
- * 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;
-};
-
-/**
- * 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;
@@ -244,12 +186,11 @@
#define cxIteratorNext(iter) (iter).base.next(&iter)
/**
- * Flags the current element for removal.
+ * Flags the current element for removal, if this iterator is mutating.
*
* @param iter the iterator
- * @return false if this iterator cannot remove the element
*/
-#define cxIteratorFlagRemoval(iter) (iter).base.flag_removal(&iter)
+#define cxIteratorFlagRemoval(iter) (iter).base.remove |= (iter).base.mutating
/**
* Loops over an iterator.
@@ -260,4 +201,55 @@
#define cx_foreach(type, elem, iter) \
for (type elem; cxIteratorValid(iter) && (elem = (type)cxIteratorCurrent(iter)) != NULL ; cxIteratorNext(iter))
+
+/**
+ * Creates an iterator for the specified plain array.
+ *
+ * The \p array can be \c NULL in which case the iterator will be immediately
+ * initialized such that #cxIteratorValid() returns \c false.
+ *
+ *
+ * @param array a pointer to the array (can be \c NULL)
+ * @param elem_size the size of one array element
+ * @param elem_count the number of elements in the array
+ * @return an iterator for the specified array
+ */
+__attribute__((__warn_unused_result__))
+CxIterator cxIterator(
+ void const *array,
+ size_t elem_size,
+ size_t elem_count
+);
+
+/**
+ * Creates a mutating iterator for the specified plain array.
+ *
+ * While the iterator is in use, the array may only be altered by removing
+ * elements through #cxIteratorFlagRemoval(). Every other change to the array
+ * will bring this iterator to an undefined state.
+ *
+ * When \p remove_keeps_order is set to \c false, removing an element will only
+ * move the last element to the position of the removed element, instead of
+ * moving all subsequent elements by one. Usually, when the order of elements is
+ * not important, this parameter should be set to \c false.
+ *
+ * The \p array can be \c NULL in which case the iterator will be immediately
+ * initialized such that #cxIteratorValid() returns \c false.
+ *
+ *
+ * @param array a pointer to the array (can be \c NULL)
+ * @param elem_size the size of one array element
+ * @param elem_count the number of elements in the array
+ * @param remove_keeps_order \c true if the order of elements must be preserved
+ * when removing an element
+ * @return an iterator for the specified array
+ */
+__attribute__((__warn_unused_result__))
+CxIterator cxMutIterator(
+ void *array,
+ size_t elem_size,
+ size_t elem_count,
+ bool remove_keeps_order
+);
+
#endif // UCX_ITERATOR_H