src/cx/iterator.h@b2bc48c2b251
src/cx/iterator.h
Thu, 23 May 2024 15:05:24 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Thu, 23 May 2024 15:05:24 +0200
- changeset 850
- b2bc48c2b251
- parent 829
- 7d4e31d295af
- child 851
- adb4e0737c33
- permissions
- -rw-r--r--
add iterator over raw C arrays - closes #389
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28 /**
29 * \file iterator.h
30 * \brief Interface for iterator implementations.
31 * \author Mike Becker
32 * \author Olaf Wintermann
33 * \copyright 2-Clause BSD License
34 */
36 #ifndef UCX_ITERATOR_H
37 #define UCX_ITERATOR_H
39 #include "common.h"
41 /**
42 * The base of mutating and non-mutating iterators.
43 */
44 struct cx_iterator_base_s {
45 /**
46 * True iff the iterator points to valid data.
47 */
48 __attribute__ ((__nonnull__))
49 bool (*valid)(void const *);
51 /**
52 * Returns a pointer to the current element.
53 *
54 * When valid returns false, the behavior of this function is undefined.
55 */
56 __attribute__ ((__nonnull__))
57 void *(*current)(void const *);
59 /**
60 * Original implementation in case the function needs to be wrapped.
61 */
62 __attribute__ ((__nonnull__))
63 void *(*current_impl)(void const *);
65 /**
66 * Advances the iterator.
67 *
68 * When valid returns false, the behavior of this function is undefined.
69 */
70 __attribute__ ((__nonnull__))
71 void (*next)(void *);
73 /**
74 * Indicates whether this iterator may remove elements.
75 */
76 bool mutating;
78 /**
79 * Internal flag for removing the current element when advancing.
80 */
81 bool remove;
82 };
84 /**
85 * Internal iterator struct - use CxMutIterator.
86 */
87 struct cx_mut_iterator_s {
89 /**
90 * The base properties of this iterator.
91 */
92 struct cx_iterator_base_s base;
94 /**
95 * Handle for the current element, if required.
96 */
97 void *elem_handle;
99 /**
100 * Handle for the source collection, if any.
101 */
102 void *src_handle;
104 /**
105 * Field for storing a key-value pair.
106 * May be used by iterators that iterate over k/v-collections.
107 */
108 struct {
109 /**
110 * A pointer to the key.
111 */
112 void const *key;
113 /**
114 * A pointer to the value.
115 */
116 void *value;
117 } kv_data;
119 /**
120 * Field for storing a slot number.
121 * May be used by iterators that iterate over multi-bucket collections.
122 */
123 size_t slot;
125 /**
126 * If the iterator is position-aware, contains the index of the element in the underlying collection.
127 * Otherwise, this field is usually uninitialized.
128 */
129 size_t index;
131 /**
132 * The size of an individual element.
133 */
134 size_t elem_size;
136 /**
137 * May contain the total number of elements, if known.
138 * Shall be set to \c SIZE_MAX when the total number is unknown during iteration.
139 */
140 size_t elem_count;
141 };
143 /**
144 * Mutating iterator value type.
145 *
146 * An iterator points to a certain element in an (possibly unbounded) chain of elements.
147 * Iterators that are based on collections (which have a defined "first" element), are supposed
148 * to be "position-aware", which means that they keep track of the current index within the collection.
149 *
150 * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the
151 * iterator is based on a collection and the underlying collection is mutated by other means than this iterator
152 * (e.g. elements added or removed), the iterator becomes invalid (regardless of what cxIteratorValid() returns)
153 * and MUST be re-obtained from the collection.
154 *
155 * @see CxIterator
156 */
157 typedef struct cx_mut_iterator_s CxMutIterator;
159 /**
160 * Internal iterator struct - use CxIterator.
161 */
162 struct cx_iterator_s {
164 /**
165 * The base properties of this iterator.
166 */
167 struct cx_iterator_base_s base;
169 /**
170 * Handle for the current element, if required.
171 */
172 void *elem_handle;
174 /**
175 * Handle for the source collection, if any.
176 */
177 void const *src_handle;
179 /**
180 * Field for storing a key-value pair.
181 * May be used by iterators that iterate over k/v-collections.
182 */
183 struct {
184 /**
185 * A pointer to the key.
186 */
187 void const *key;
188 /**
189 * A pointer to the value.
190 */
191 void *value;
192 } kv_data;
194 /**
195 * Field for storing a slot number.
196 * May be used by iterators that iterate over multi-bucket collections.
197 */
198 size_t slot;
200 /**
201 * If the iterator is position-aware, contains the index of the element in the underlying collection.
202 * Otherwise, this field is usually uninitialized.
203 */
204 size_t index;
206 /**
207 * The size of an individual element.
208 */
209 size_t elem_size;
211 /**
212 * May contain the total number of elements, if known.
213 * Shall be set to \c SIZE_MAX when the total number is unknown during iteration.
214 */
215 size_t elem_count;
216 };
218 /**
219 * Iterator value type.
220 * An iterator points to a certain element in a (possibly unbounded) chain of elements.
221 * Iterators that are based on collections (which have a defined "first" element), are supposed
222 * to be "position-aware", which means that they keep track of the current index within the collection.
223 *
224 * @note Objects that are pointed to by an iterator are always mutable through that iterator. However,
225 * this iterator cannot mutate the collection itself (add or remove elements) and any mutation of the
226 * collection by other means makes this iterator invalid (regardless of what cxIteratorValid() returns).
227 *
228 * @see CxMutIterator
229 */
230 typedef struct cx_iterator_s CxIterator;
232 /**
233 * Checks if the iterator points to valid data.
234 *
235 * This is especially false for past-the-end iterators.
236 *
237 * @param iter the iterator
238 * @return true iff the iterator points to valid data
239 */
240 #define cxIteratorValid(iter) (iter).base.valid(&(iter))
242 /**
243 * Returns a pointer to the current element.
244 *
245 * The behavior is undefined if this iterator is invalid.
246 *
247 * @param iter the iterator
248 * @return a pointer to the current element
249 */
250 #define cxIteratorCurrent(iter) (iter).base.current(&iter)
252 /**
253 * Advances the iterator to the next element.
254 *
255 * @param iter the iterator
256 */
257 #define cxIteratorNext(iter) (iter).base.next(&iter)
259 /**
260 * Flags the current element for removal, if this iterator is mutating.
261 *
262 * @param iter the iterator
263 */
264 #define cxIteratorFlagRemoval(iter) (iter).base.remove |= (iter).base.mutating
266 /**
267 * Loops over an iterator.
268 * @param type the type of the elements
269 * @param elem the name of the iteration variable
270 * @param iter the iterator
271 */
272 #define cx_foreach(type, elem, iter) \
273 for (type elem; cxIteratorValid(iter) && (elem = (type)cxIteratorCurrent(iter)) != NULL ; cxIteratorNext(iter))
276 /**
277 * Creates an iterator for the specified plain array.
278 *
279 * While the iterator is in use, the array may only be altered by removing
280 * elements through #cxIteratorFlagRemoval(). Every other change to the array
281 * will bring this iterator to an undefined state.
282 *
283 * When \p remove_keeps_order is set to \c false, removing an element will only
284 * move the last element to the position of the removed element, instead of
285 * moving all subsequent elements by one. Usually, when the order of elements is
286 * not important, this parameter should be set to \c false.
287 *
288 * The \p array can be \c NULL in which case the iterator will be immediately
289 * initialized such that #cxIteratorValid() returns \c false.
290 *
291 *
292 * @param array a pointer to the array (can be \c NULL)
293 * @param elem_size the size of one array element
294 * @param elem_count the number of elements in the array
295 * @param remove_keeps_order \c true if the order of elements must be preserved
296 * when removing an element
297 * @return an iterator for the specified array
298 */
299 __attribute__((__warn_unused_result__))
300 CxMutIterator cxIterator( // TODO: unify the iterator types
301 void *array,
302 size_t elem_size,
303 size_t elem_count,
304 bool remove_keeps_order
305 );
307 #endif // UCX_ITERATOR_H
