UNIXworkcode

1 # Iterators 2 3 Iterators generalize the iteration over elements of an arbitrary collection. 4 This allows iteration over arrays, lists, maps, trees, etc. in a unified way. 5 6 Creating an iterator is as simple as creating a `CxIterator` struct and setting the fields in a meaningful way. 7 The UCX collections provide various functions to create such iterators. 8 9 If the predefined fields are not enough (or introduce too much bloat) for your use case, 10 you can alternatively create your own iterator structure 11 and place the `CX_ITERATOR_BASE` macro as first member of that structure. 12 13 ```C 14 #include <cx/iterator.h> 15 16 struct my_fancy_iterator_s { 17 CX_ITERATOR_BASE; // the base members used by cx_foreach() 18 // ... custom fields ... 19 }; 20 ``` 21 22 ## Creating an Iterator 23 24 The following functions create iterators over plain C arrays. 25 26 ```C 27 #include <cx/iterator.h> 28 29 CxIterator cxIterator(const void *array, 30 size_t elem_size, size_t elem_count); 31 32 CxIterator cxIteratorPtr(const void *array, 33 size_t elem_count); 34 ``` 35 36 The `cxIterator()` function creates an iterator over the elements of `array` where 37 each element is `elem_size` bytes large and the array contains a total of `elem_count` elements. 38 39 The `cxIteratorPtr()` on the other hand assumes `sizeof(void*)` as the `elem_size` and automatically dereferences the pointers to the array elements. 40 That means, values returned by the iterator created with `cxIteratorPtr()` are the pointers stored in the array, 41 while iterators created `cxIterator()` yield the pointers to the elements in the array. 42 43 Iterators created with the above functions are not allowed to remove elements because they are unable to update the size of the array they are iterating over. 44 45 The UCX collections also define functions for creating iterators over their items. 46 You can read more about them in the respective sections of the documentation. 47 48 ## Using an Iterator 49 50 The following macros work with arbitrary structures using `CX_ITERATOR_BASE` 51 and invoke the respective function pointers `valid`, `current`, or `next`. 52 ```C 53 cxIteratorValid(iter) 54 cxIteratorCurrent(iter) 55 cxIteratorNext(iter) 56 ``` 57 58 You may use them for manual iterator, but usually you do not need them. 59 Every iterator can be used with the `cx_foreach` macro. 60 61 ```C 62 #include <cx/iterator.h> 63 64 // some custom array and its size 65 MyData *array = // ... 66 size_t size = // ... 67 68 CxIterator iter = cxIterator(array, sizeof(MyData), size); 69 cx_foreach(MyData*, elem, iter) { 70 // .. do something with elem .. 71 } 72 ``` 73 74 The macro takes three arguments: 75 1. the pointer-type of a pointer to an element, 76 2. the name of the variable you want to use for accessing the element, 77 3. and the iterator. 78 79 > An iterator does not necessarily need to iterate over the concrete elements of a collection. 80 > Map iterators, for example, can iterator over the key/value pairs, 81 > but they can also iterate over just the values or just the keys. 82 > 83 > You should read the documentation of the function creating the iterator to learn 84 > what exactly the iterator is iterating over. 85 86 ## Removing Elements via Iterators 87 88 Usually an iterator is not mutating the collection it is iterating over. 89 But sometimes it is desirable to remove an element from the collection while iterating over it. 90 91 For this purpose, most collections allow to use `cxIteratorFlagRemoval()`, which instructs the iterator to remove 92 the current element from the collection on the next call to `cxIteratorNext()`. 93 If you are implementing your own iterator, it is up to you to implement this behavior. 94 95 ## Passing Iterators to Functions 96 97 To eliminate the need of memory management for iterators, the structures are usually used by value. 98 This does not come with additional costs because iteration is implemented entirely by using macros. 99 100 However, sometimes it is necessary to pass an iterator to another function. 101 To make that possible in a generalized way, such functions should accept a `CxIteratorBase*` pointer 102 which can be obtained with the `cxIteratorRef()` macro on the calling site. 103 104 In the following example, elements from a list are inserted into a tree: 105 106 ```C 107 CxList *list = // ... 108 CxTree *tree = // ... 109 110 CxIterator iter = cxListIterator(list); 111 cxTreeInsertIter(tree, cxIteratorRef(iter), cxListSize(list)); 112 ``` 113 114 > This is the reason, why `CX_ITERATOR_BASE` must be the first member of any iterator structure. 115 > Otherwise, the address taken by `cxIteratorRef()` would not equal the address of the iterator. 116 {style="note"} 117 118 ## Custom Iterators 119 120 The base structure is defined as follows: 121 ```C 122 struct cx_iterator_base_s { 123 bool (*valid)(const void *); 124 bool (*valid_impl)(const void *); 125 void *(*current)(const void *); 126 void (*next)(void *); 127 void *(*current_impl)(const void *); 128 void (*next_impl)(void *); 129 bool allow_remove; 130 bool remove; 131 }; 132 133 typedef struct cx_iterator_base_s CxIteratorBase; 134 ``` 135 136 The `valid` function indicates whether the iterator is currently pointing to an element in the collection. 137 The `current` function is supposed to return that element, 138 and the `next` function shall advance the iterator to the next element. 139 140 The booleans `allow_remove` and `remove` are used for [removing elements](#removing-elements-via-iterators) as explained above. 141 When an iterator is created, the `allow_remove` field is set to indicate if removal of elements is supported. 142 The `remove` field is set to indicate if the current element should be removed on the next call to `next()` (see `cxIteratorFlagRemoval()`). 143 144 Iterators may be wrapped in which case the original implementation can be stored in the `*_impl` function pointers. 145 They can then be called by a wrapper implementation pointed to by `current` and `next`, respectively. 146 This can be useful when you want to support the `store_pointer` field of the [](collection.h.md) API. 147 148 A specialized, simple, and fast iterator over an array of a certain type 149 that does not support removing elements can be implemented as follows: 150 ```C 151 #include <cx/iterator.h> 152 153 typedef struct my_foo_s { 154 // ... your data ... 155 } MyFoo; 156 157 typedef struct my_foo_iterator_s { 158 CX_ITERATOR_BASE; 159 MyFoo *array; 160 size_t index; 161 size_t elem_count; 162 } MyFooIterator; 163 164 static bool my_foo_iter_valid(const void *it) { 165 const MyFooIterator *iter = it; 166 return iter->index < iter->elem_count; 167 } 168 169 static void *my_foo_iter_current(const void *it) { 170 const MyFooIterator *iter = it; 171 return &iter->array[iter->index]; 172 } 173 174 static void my_foo_iter_next(void *it) { 175 MyFooIterator *iter = it; 176 iter->index++; 177 } 178 179 MyFooIterator myFooIterator(MyFoo *array, size_t elem_count) { 180 MyFooIterator iter; 181 182 // base fields 183 iter.base.valid = my_foo_iter_valid; 184 iter.base.current = my_foo_iter_current; 185 iter.base.next = my_foo_iter_next; 186 iter.base.remove = false; 187 iter.base.allow_remove = false; 188 189 // custom fields 190 iter.index = 0; 191 iter.elem_count = elem_count; 192 193 return iter; 194 } 195 ``` 196 197 > Note, that the behavior of `current` is undefined when `valid` returns `false`. 198 > That means, on the one hand, `current` does not need to check for validity of the iterator, 199 > but on the other hand, it is forbidden to invoke `current` when `valid` would return `false`. 200 {style="note"} 201 202 > If performance matters in your application, it is recommended that you indeed create specialized iterators 203 > for your collections. The default UCX implementations trade some performance for generality. 204 205 <seealso> 206 <category ref="apidoc"> 207 <a href="https://ucx.sourceforge.io/api/iterator_8h.html">iterator.h</a> 208 </category> 209 </seealso> 210