36 #ifndef UCX_ITERATOR_H |
36 #ifndef UCX_ITERATOR_H |
37 #define UCX_ITERATOR_H |
37 #define UCX_ITERATOR_H |
38 |
38 |
39 #include "common.h" |
39 #include "common.h" |
40 |
40 |
41 /** |
|
42 * The base of mutating and non-mutating iterators. |
|
43 */ |
|
44 struct cx_iterator_base_s { |
41 struct cx_iterator_base_s { |
45 /** |
42 /** |
46 * True iff the iterator points to valid data. |
43 * True iff the iterator points to valid data. |
47 */ |
44 */ |
48 __attribute__ ((__nonnull__)) |
45 __attribute__ ((__nonnull__)) |
49 bool (*valid)(void const *); |
46 bool (*valid)(const void *); |
50 |
47 |
51 /** |
48 /** |
52 * Returns a pointer to the current element. |
49 * Returns a pointer to the current element. |
53 * |
50 * |
54 * When valid returns false, the behavior of this function is undefined. |
51 * When valid returns false, the behavior of this function is undefined. |
55 */ |
52 */ |
56 __attribute__ ((__nonnull__)) |
53 __attribute__ ((__nonnull__)) |
57 void *(*current)(void const *); |
54 void *(*current)(const void *); |
58 |
55 |
59 /** |
56 /** |
60 * Original implementation in case the function needs to be wrapped. |
57 * Original implementation in case the function needs to be wrapped. |
61 */ |
58 */ |
62 __attribute__ ((__nonnull__)) |
59 __attribute__ ((__nonnull__)) |
63 void *(*current_impl)(void const *); |
60 void *(*current_impl)(const void *); |
64 |
61 |
65 /** |
62 /** |
66 * Advances the iterator. |
63 * Advances the iterator. |
67 * |
64 * |
68 * When valid returns false, the behavior of this function is undefined. |
65 * When valid returns false, the behavior of this function is undefined. |
69 */ |
66 */ |
70 __attribute__ ((__nonnull__)) |
67 __attribute__ ((__nonnull__)) |
71 void (*next)(void *); |
68 void (*next)(void *); |
72 |
|
73 /** |
|
74 * Flag current element for removal, if possible. |
|
75 * |
|
76 * When valid returns false, the behavior of this function is undefined. |
|
77 */ |
|
78 __attribute__ ((__nonnull__)) |
|
79 bool (*flag_removal)(void *); |
|
80 |
|
81 /** |
69 /** |
82 * Indicates whether this iterator may remove elements. |
70 * Indicates whether this iterator may remove elements. |
83 */ |
71 */ |
84 bool mutating; |
72 bool mutating; |
85 |
|
86 /** |
73 /** |
87 * Internal flag for removing the current element when advancing. |
74 * Internal flag for removing the current element when advancing. |
88 */ |
75 */ |
89 bool remove; |
76 bool remove; |
90 }; |
77 }; |
91 |
78 |
92 /** |
79 /** |
93 * Internal iterator struct - use CxMutIterator. |
80 * Declares base attributes for an iterator. |
94 */ |
81 * Must be the first member of an iterator structure. |
95 struct cx_mut_iterator_s { |
82 */ |
96 |
83 #define CX_ITERATOR_BASE struct cx_iterator_base_s base |
97 /** |
84 |
98 * The base properties of this iterator. |
85 /** |
99 */ |
86 * Internal iterator struct - use CxIterator. |
100 struct cx_iterator_base_s base; |
87 */ |
101 |
88 struct cx_iterator_s { |
102 /** |
89 CX_ITERATOR_BASE; |
103 * Handle for the current element, if required. |
90 |
|
91 /** |
|
92 * Handle for the current element. |
104 */ |
93 */ |
105 void *elem_handle; |
94 void *elem_handle; |
106 |
95 |
107 /** |
96 /** |
108 * Handle for the source collection, if any. |
97 * Handle for the source collection, if any. |
109 */ |
98 */ |
110 void *src_handle; |
99 union { |
|
100 /** |
|
101 * Access for mutating iterators. |
|
102 */ |
|
103 void *m; |
|
104 /** |
|
105 * Access for normal iterators. |
|
106 */ |
|
107 const void *c; |
|
108 } src_handle; |
111 |
109 |
112 /** |
110 /** |
113 * Field for storing a key-value pair. |
111 * Field for storing a key-value pair. |
114 * May be used by iterators that iterate over k/v-collections. |
112 * May be used by iterators that iterate over k/v-collections. |
115 */ |
113 */ |
116 struct { |
114 struct { |
117 /** |
115 /** |
118 * A pointer to the key. |
116 * A pointer to the key. |
119 */ |
117 */ |
120 void const *key; |
118 const void *key; |
121 /** |
119 /** |
122 * A pointer to the value. |
120 * A pointer to the value. |
123 */ |
121 */ |
124 void *value; |
122 void *value; |
125 } kv_data; |
123 } kv_data; |
133 /** |
131 /** |
134 * If the iterator is position-aware, contains the index of the element in the underlying collection. |
132 * If the iterator is position-aware, contains the index of the element in the underlying collection. |
135 * Otherwise, this field is usually uninitialized. |
133 * Otherwise, this field is usually uninitialized. |
136 */ |
134 */ |
137 size_t index; |
135 size_t index; |
|
136 |
|
137 /** |
|
138 * The size of an individual element. |
|
139 */ |
|
140 size_t elem_size; |
|
141 |
|
142 /** |
|
143 * May contain the total number of elements, if known. |
|
144 * Shall be set to \c SIZE_MAX when the total number is unknown during iteration. |
|
145 */ |
|
146 size_t elem_count; |
138 }; |
147 }; |
139 |
148 |
140 /** |
149 /** |
141 * Mutating iterator value type. |
150 * Iterator type. |
142 * |
151 * |
143 * An iterator points to a certain element in an (possibly unbounded) chain of elements. |
|
144 * Iterators that are based on collections (which have a defined "first" element), are supposed |
|
145 * to be "position-aware", which means that they keep track of the current index within the collection. |
|
146 * |
|
147 * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the |
|
148 * iterator is based on a collection and the underlying collection is mutated by other means than this iterator |
|
149 * (e.g. elements added or removed), the iterator becomes invalid (regardless of what cxIteratorValid() returns) |
|
150 * and MUST be re-obtained from the collection. |
|
151 * |
|
152 * @see CxIterator |
|
153 */ |
|
154 typedef struct cx_mut_iterator_s CxMutIterator; |
|
155 |
|
156 /** |
|
157 * Internal iterator struct - use CxIterator. |
|
158 */ |
|
159 struct cx_iterator_s { |
|
160 |
|
161 /** |
|
162 * The base properties of this iterator. |
|
163 */ |
|
164 struct cx_iterator_base_s base; |
|
165 |
|
166 /** |
|
167 * Handle for the current element, if required. |
|
168 */ |
|
169 void *elem_handle; |
|
170 |
|
171 /** |
|
172 * Handle for the source collection, if any. |
|
173 */ |
|
174 void const *src_handle; |
|
175 |
|
176 /** |
|
177 * Field for storing a key-value pair. |
|
178 * May be used by iterators that iterate over k/v-collections. |
|
179 */ |
|
180 struct { |
|
181 /** |
|
182 * A pointer to the key. |
|
183 */ |
|
184 void const *key; |
|
185 /** |
|
186 * A pointer to the value. |
|
187 */ |
|
188 void *value; |
|
189 } kv_data; |
|
190 |
|
191 /** |
|
192 * Field for storing a slot number. |
|
193 * May be used by iterators that iterate over multi-bucket collections. |
|
194 */ |
|
195 size_t slot; |
|
196 |
|
197 /** |
|
198 * If the iterator is position-aware, contains the index of the element in the underlying collection. |
|
199 * Otherwise, this field is usually uninitialized. |
|
200 */ |
|
201 size_t index; |
|
202 }; |
|
203 |
|
204 /** |
|
205 * Iterator value type. |
|
206 * An iterator points to a certain element in a (possibly unbounded) chain of elements. |
152 * An iterator points to a certain element in a (possibly unbounded) chain of elements. |
207 * Iterators that are based on collections (which have a defined "first" element), are supposed |
153 * Iterators that are based on collections (which have a defined "first" element), are supposed |
208 * to be "position-aware", which means that they keep track of the current index within the collection. |
154 * to be "position-aware", which means that they keep track of the current index within the collection. |
209 * |
155 * |
210 * @note Objects that are pointed to by an iterator are always mutable through that iterator. However, |
156 * @note Objects that are pointed to by an iterator are always mutable through that iterator. However, |
211 * this iterator cannot mutate the collection itself (add or remove elements) and any mutation of the |
157 * any concurrent mutation of the collection other than by this iterator makes this iterator invalid |
212 * collection by other means makes this iterator invalid (regardless of what cxIteratorValid() returns). |
158 * and it must not be used anymore. |
213 * |
|
214 * @see CxMutIterator |
|
215 */ |
159 */ |
216 typedef struct cx_iterator_s CxIterator; |
160 typedef struct cx_iterator_s CxIterator; |
217 |
161 |
218 /** |
162 /** |
219 * Checks if the iterator points to valid data. |
163 * Checks if the iterator points to valid data. |
241 * @param iter the iterator |
185 * @param iter the iterator |
242 */ |
186 */ |
243 #define cxIteratorNext(iter) (iter).base.next(&iter) |
187 #define cxIteratorNext(iter) (iter).base.next(&iter) |
244 |
188 |
245 /** |
189 /** |
246 * Flags the current element for removal. |
190 * Flags the current element for removal, if this iterator is mutating. |
247 * |
191 * |
248 * @param iter the iterator |
192 * @param iter the iterator |
249 * @return false if this iterator cannot remove the element |
193 */ |
250 */ |
194 #define cxIteratorFlagRemoval(iter) (iter).base.remove |= (iter).base.mutating |
251 #define cxIteratorFlagRemoval(iter) (iter).base.flag_removal(&iter) |
195 |
|
196 /** |
|
197 * Obtains a reference to an arbitrary iterator. |
|
198 * |
|
199 * This is useful for APIs that expect some iterator as an argument. |
|
200 * |
|
201 * @param iter the iterator |
|
202 */ |
|
203 #define cxIteratorRef(iter) &((iter).base) |
252 |
204 |
253 /** |
205 /** |
254 * Loops over an iterator. |
206 * Loops over an iterator. |
255 * @param type the type of the elements |
207 * @param type the type of the elements |
256 * @param elem the name of the iteration variable |
208 * @param elem the name of the iteration variable |
257 * @param iter the iterator |
209 * @param iter the iterator |
258 */ |
210 */ |
259 #define cx_foreach(type, elem, iter) \ |
211 #define cx_foreach(type, elem, iter) \ |
260 for (type elem; cxIteratorValid(iter) && (elem = (type)cxIteratorCurrent(iter)) != NULL ; cxIteratorNext(iter)) |
212 for (type elem; cxIteratorValid(iter) && (elem = (type)cxIteratorCurrent(iter)) != NULL ; cxIteratorNext(iter)) |
261 |
213 |
|
214 |
|
215 /** |
|
216 * Creates an iterator for the specified plain array. |
|
217 * |
|
218 * The \p array can be \c NULL in which case the iterator will be immediately |
|
219 * initialized such that #cxIteratorValid() returns \c false. |
|
220 * |
|
221 * |
|
222 * @param array a pointer to the array (can be \c NULL) |
|
223 * @param elem_size the size of one array element |
|
224 * @param elem_count the number of elements in the array |
|
225 * @return an iterator for the specified array |
|
226 */ |
|
227 __attribute__((__warn_unused_result__)) |
|
228 CxIterator cxIterator( |
|
229 const void *array, |
|
230 size_t elem_size, |
|
231 size_t elem_count |
|
232 ); |
|
233 |
|
234 /** |
|
235 * Creates a mutating iterator for the specified plain array. |
|
236 * |
|
237 * While the iterator is in use, the array may only be altered by removing |
|
238 * elements through #cxIteratorFlagRemoval(). Every other change to the array |
|
239 * will bring this iterator to an undefined state. |
|
240 * |
|
241 * When \p remove_keeps_order is set to \c false, removing an element will only |
|
242 * move the last element to the position of the removed element, instead of |
|
243 * moving all subsequent elements by one. Usually, when the order of elements is |
|
244 * not important, this parameter should be set to \c false. |
|
245 * |
|
246 * The \p array can be \c NULL in which case the iterator will be immediately |
|
247 * initialized such that #cxIteratorValid() returns \c false. |
|
248 * |
|
249 * |
|
250 * @param array a pointer to the array (can be \c NULL) |
|
251 * @param elem_size the size of one array element |
|
252 * @param elem_count the number of elements in the array |
|
253 * @param remove_keeps_order \c true if the order of elements must be preserved |
|
254 * when removing an element |
|
255 * @return an iterator for the specified array |
|
256 */ |
|
257 __attribute__((__warn_unused_result__)) |
|
258 CxIterator cxMutIterator( |
|
259 void *array, |
|
260 size_t elem_size, |
|
261 size_t elem_count, |
|
262 bool remove_keeps_order |
|
263 ); |
|
264 |
262 #endif // UCX_ITERATOR_H |
265 #endif // UCX_ITERATOR_H |