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