ucx: comparison docs/Writerside/topics/iterator.h.md

-:ee4e33284f0c
+:790ff923f375
 # Iterators
-<warning>
+Iterators generalize the iteration over elements of an arbitrary collection.
-Outdated Section - will be updated soon!
+This allows iteration over arrays, lists, maps, trees, etc. in a unified way.
-</warning>
-In UCX 3 a new feature has been introduced to write own iterators, that work with the `cx_foreach` macro.
+Creating an iterator is as simple as creating a `CxIterator` struct and setting the fields in a meaningful way.
-In previous UCX releases there were different hard-coded foreach macros for lists and maps that were not customizable.
+The UCX collections provide various functions to create such iterators.
-Now, creating an iterator is as simple as creating a `CxIterator` struct and setting the fields in a meaningful way.
-You do not always need all fields in the iterator structure, depending on your use case.
+If the predefined fields are insufficient (or introduce too much bloat) for your use case,
-Sometimes you only need the `index` (for example when iterating over simple lists), and other times you will need the
+you can alternatively create your own iterator structure
-`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 as first member of that structure.
+```C
+#include <cx/iterator.h>
+struct my_fancy_iterator_s {
+CX_ITERATOR_BASE; // the base members used by cx_foreach()
+// ... custom fields ...
+};
+```
+## Overview
+## Using an Iterator
+The following macros work with arbitrary structures using `CX_ITERATOR_BASE`
+and invoke the respective function pointers `valid`, `current`, or `next`.
+```C
+cxIteratorValid(iter)
+cxIteratorCurrent(iter)
+cxIteratorNext(iter)
+```
+You may use them for manual iterator, but usually you do not need them.
+Every iterator can be used with the `cx_foreach` macro.
+```C
+#include <cx/iterator.h>
+// some custom array and its size
+MyData *array = // ...
+size_t size = // ...
+CxIterator iter = cxIterator(array, sizeof(MyData), size);
+cx_foreach(MyData*, elem, iter) {
+// .. do something with elem ..
+}
+```
+The macro takes three arguments:
+1. the pointer-type of a pointer to an element,
+2. the name of the variable you want to use for accessing the element,
+3. and the iterator.
+> An iterator does not necessarily need to iterate over the elements of a collections.
+> Map iterators, for example, can iterator over the key/value pairs,
+> but they can also iterate over just the values or just the keys.
+>
+> You should read the documentation of the function creating the iterator to learn
+> what exactly the iterator is iterating over.
+## Mutating Iterators
 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.
 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 the `mutating` flag in the base structure is set to `true`,
-On mutating iterators it is allowed to call the `cxFlagForRemoval()` function, which instructs the iterator to remove
+and 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.
-<!--
+## Passing Iterators to Functions
-## Undocumented Symbols (TODO)
-### cxIterator
+To eliminate the need of memory management for iterators, the structures are usually used by value.
-### cxIteratorPtr
+This does not come with additional costs, because iteration is implemented entirely by macros.
-### cxMutIterator
-### cxMutIteratorPtr
+However, sometimes it is necessary to pass an iterator to another function.
--->
+To make that possible in a generalized way, such functions should accept a `CxIteratorBase*` pointer
+which can be obtained with the `cxIteratorRef()` macro on the calling site.
+In the following example, elements from a list are inserted into a tree:
+```C
+CxList *list = // ...
+CxTree *tree = // ...
+CxIterator iter = cxListIterator(list);
+cxTreeInsertIter(tree, cxIteratorRef(iter), cxListSize(list));
+```
+> This is the reason, why `CX_ITERATOR_BASE` must be the first member of any iterator structure.
+> Otherwise, the address taken by `cxIteratorRef()` would not equal the address of the iterator.
+{style="note"}
+## Custom Iterators
+The base structure is defined as follows:
+```C
+struct cx_iterator_base_s {
+bool (*valid)(const void *);
+void *(*current)(const void *);
+void *(*current_impl)(const void *);
+void (*next)(void *);
+bool mutating;
+bool remove;
+};
+typedef struct cx_iterator_base_s CxIteratorBase;
+```
+The `valid` function indicates whether the iterator is currently pointing to an element in the collection.
+The `current` function is supposed to return that element,
+and the `next` function shall advance the iterator to the next element.
+The booleans `mutating` and `remove` are used for [mutating iterators](#mutating-iterators) as explained above.
+Iterators may be wrapped in which case the original implementation can be stored in `current_impl` and
+called by a wrapper implementation pointed to by `current`.
+This can be useful when you want to support the `store_pointer` field of the [](collection.h.md) API.
+A specialized, simple, and fast iterator over an array of a certain type,
+that does not support mutation, can be implemented as follows:
+```C
+#include <cx/iterator.h>
+typedef struct my_foo_s {
+// ... your data ...
+} MyFoo;
+typedef struct my_foo_iterator_s {
+CX_ITERATOR_BASE;
+MyFoo *array;
+size_t index;
+size_t elem_count;
+} MyFooIterator;
+static bool my_foo_iter_valid(const void *it) {
+const MyFooIterator *iter = it;
+return iter->index < iter->elem_count;
+}
+static void *my_foo_iter_current(const void *it) {
+const MyFooIterator *iter = it;
+return &iter->array[iter->index];
+}
+static void my_foo_iter_next(void *it) {
+MyFooIterator *iter = it;
+iter->index++;
+}
+MyFooIterator myFooIterator(MyFoo *array, size_t elem_count) {
+MyFooIterator iter;
+// base fields
+iter.base.valid = my_foo_iter_valid;
+iter.base.current = my_foo_iter_current;
+iter.base.next = my_foo_iter_next;
+iter.base.remove = false;
+iter.base.mutating = false;
+// custom fields
+iter.index = 0;
+iter.elem_count = elem_count;
+return iter;
+}
+```
+> Note, that the behavior of `current` is undefined when `valid` returns `false`.
+> That means, on the one hand, `current` does not need to check for validity of the iterator,
+> but on the other hand it is forbidden to invoke `current` when `valid` would return `false`.
+{style="note"}
+> If performance matters in your application, it is recommended that you indeed create specialized iterators
+> for your collections. The default UCX implementations trade some of the performance for generality.
 <seealso>
 <category ref="apidoc">
 <a href="https://ucx.sourceforge.io/api/iterator_8h.html">iterator.h</a>
 </category>

Mercurial > hg > ucx / file comparison

comparison: docs/Writerside/topics/iterator.h.md

docs/Writerside/topics/iterator.h.md