ucx/cx/iterator.h

   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  * \version 3.0
  34  * \copyright 2-Clause BSD License
  35  */
  36
  37 #ifndef UCX_ITERATOR_H
  38 #define UCX_ITERATOR_H
  39
  40 #include "common.h"
  41
  42 /**
  43  * The base of mutating and non-mutating iterators.
  44  */
  45 struct cx_iterator_base_s {
  46     /**
  47      * True iff the iterator points to valid data.
  48      */
  49     __attribute__ ((__nonnull__))
  50     bool (*valid)(void const *);
  51
  52     /**
  53      * Returns a pointer to the current element.
  54      */
  55     __attribute__ ((__nonnull__))
  56     void *(*current)(void const *);
  57
  58     /**
  59      * Original implementation in case the function needs to be wrapped.
  60      */
  61     __attribute__ ((__nonnull__))
  62     void *(*current_impl)(void const *);
  63
  64     /**
  65      * Advances the iterator.
  66      */
  67     __attribute__ ((__nonnull__))
  68     void (*next)(void *);
  69
  70     /**
  71      * Flag current element for removal, if possible.
  72      */
  73     __attribute__ ((__nonnull__))
  74     bool (*flag_removal)(void *);
  75
  76     /**
  77      * Indicates whether this iterator is muting.
  78      */
  79     bool mutating;
  80
  81     /**
  82      * Internal flag for removing the current element when advancing.
  83      */
  84     bool remove;
  85 };
  86
  87 /**
  88  * Internal iterator struct - use CxMutIterator.
  89  */
  90 struct cx_mut_iterator_s {
  91
  92     /**
  93      * The base properties of this iterator.
  94      */
  95     struct cx_iterator_base_s base;
  96
  97     /**
  98      * Handle for the current element, if required.
  99      */
 100     void *elem_handle;
 101
 102     /**
 103      * Handle for the source collection, if any.
 104      */
 105     void *src_handle;
 106
 107     /**
 108      * Field for storing a key-value pair.
 109      * May be used by iterators that iterate over k/v-collections.
 110      */
 111     struct {
 112         /**
 113          * A pointer to the key.
 114          */
 115         void const *key;
 116         /**
 117          * A pointer to the value.
 118          */
 119         void *value;
 120     } kv_data;
 121
 122     /**
 123      * Field for storing a slot number.
 124      * May be used by iterators that iterate over multi-bucket collections.
 125      */
 126     size_t slot;
 127
 128     /**
 129      * If the iterator is position-aware, contains the index of the element in the underlying collection.
 130      * Otherwise, this field is usually uninitialized.
 131      */
 132     size_t index;
 133 };
 134
 135 /**
 136  * Mutating iterator value type.
 137  *
 138  * An iterator points to a certain element in an (possibly unbounded) chain of elements.
 139  * Iterators that are based on collections (which have a defined "first" element), are supposed
 140  * to be "position-aware", which means that they keep track of the current index within the collection.
 141  *
 142  * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the
 143  * iterator is based on a collection and the underlying collection is mutated by other means than this iterator
 144  * (e.g. elements added or removed), the iterator becomes invalid (regardless of what cxIteratorValid() returns)
 145  * and MUST be re-obtained from the collection.
 146  *
 147  * @see CxIterator
 148  */
 149 typedef struct cx_mut_iterator_s CxMutIterator;
 150
 151 /**
 152  * Internal iterator struct - use CxIterator.
 153  */
 154 struct cx_iterator_s {
 155
 156     /**
 157      * The base properties of this iterator.
 158      */
 159     struct cx_iterator_base_s base;
 160
 161     /**
 162      * Handle for the current element, if required.
 163      */
 164     void *elem_handle;
 165
 166     /**
 167      * Handle for the source collection, if any.
 168      */
 169     void const *src_handle;
 170
 171     /**
 172      * Field for storing a key-value pair.
 173      * May be used by iterators that iterate over k/v-collections.
 174      */
 175     struct {
 176         /**
 177          * A pointer to the key.
 178          */
 179         void const *key;
 180         /**
 181          * A pointer to the value.
 182          */
 183         void *value;
 184     } kv_data;
 185
 186     /**
 187      * Field for storing a slot number.
 188      * May be used by iterators that iterate over multi-bucket collections.
 189      */
 190     size_t slot;
 191
 192     /**
 193      * If the iterator is position-aware, contains the index of the element in the underlying collection.
 194      * Otherwise, this field is usually uninitialized.
 195      */
 196     size_t index;
 197 };
 198
 199 /**
 200  * Iterator value type.
 201  * An iterator points to a certain element in an (possibly unbounded) chain of elements.
 202  * Iterators that are based on collections (which have a defined "first" element), are supposed
 203  * to be "position-aware", which means that they keep track of the current index within the collection.
 204  *
 205  * @note Objects that are pointed to by an iterator are always mutable through that iterator. However,
 206  * this iterator cannot mutate the collection itself (add or remove elements) and any mutation of the
 207  * collection by other means make this iterator invalid (regardless of what cxIteratorValid() returns).
 208  *
 209  * @see CxMutIterator
 210  */
 211 typedef struct cx_iterator_s CxIterator;
 212
 213 /**
 214  * Checks if the iterator points to valid data.
 215  *
 216  * This is especially false for past-the-end iterators.
 217  *
 218  * @param iter the iterator
 219  * @return true iff the iterator points to valid data
 220  */
 221 #define cxIteratorValid(iter) (iter).base.valid(&(iter))
 222
 223 /**
 224  * Returns a pointer to the current element.
 225  *
 226  * The behavior is undefined if this iterator is invalid.
 227  *
 228  * @param iter the iterator
 229  * @return a pointer to the current element
 230  */
 231 #define cxIteratorCurrent(iter) (iter).base.current(&iter)
 232
 233 /**
 234  * Advances the iterator to the next element.
 235  *
 236  * @param iter the iterator
 237  */
 238 #define cxIteratorNext(iter) (iter).base.next(&iter)
 239
 240 /**
 241  * Flags the current element for removal.
 242  *
 243  * @param iter the iterator
 244  * @return false if this iterator cannot remove the element
 245  */
 246 #define cxIteratorFlagRemoval(iter) (iter).base.flag_removal(&iter)
 247
 248 /**
 249  * Loops over an iterator.
 250  * @param type the type of the elements
 251  * @param elem the name of the iteration variable
 252  * @param iter the iterator
 253  */
 254 #define cx_foreach(type, elem, iter) \
 255 for (type elem; cxIteratorValid(iter) && (elem = (type)cxIteratorCurrent(iter)) != NULL ; cxIteratorNext(iter))
 256
 257 #endif // UCX_ITERATOR_H