diff -r fe49cff3c571 -r bb7da585debc ucx/cx/iterator.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ucx/cx/iterator.h Sat Jan 04 16:38:48 2025 +0100 @@ -0,0 +1,265 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +/** + * \file iterator.h + * \brief Interface for iterator implementations. + * \author Mike Becker + * \author Olaf Wintermann + * \copyright 2-Clause BSD License + */ + +#ifndef UCX_ITERATOR_H +#define UCX_ITERATOR_H + +#include "common.h" + +struct cx_iterator_base_s { + /** + * True iff the iterator points to valid data. + */ + __attribute__ ((__nonnull__)) + bool (*valid)(const void *); + + /** + * Returns a pointer to the current element. + * + * When valid returns false, the behavior of this function is undefined. + */ + __attribute__ ((__nonnull__)) + void *(*current)(const void *); + + /** + * Original implementation in case the function needs to be wrapped. + */ + __attribute__ ((__nonnull__)) + void *(*current_impl)(const void *); + + /** + * Advances the iterator. + * + * When valid returns false, the behavior of this function is undefined. + */ + __attribute__ ((__nonnull__)) + void (*next)(void *); + /** + * Indicates whether this iterator may remove elements. + */ + bool mutating; + /** + * Internal flag for removing the current element when advancing. + */ + bool remove; +}; + +/** + * Declares base attributes for an iterator. + * Must be the first member of an iterator structure. + */ +#define CX_ITERATOR_BASE struct cx_iterator_base_s base + +/** + * Internal iterator struct - use CxIterator. + */ +struct cx_iterator_s { + CX_ITERATOR_BASE; + + /** + * Handle for the current element. + */ + void *elem_handle; + + /** + * Handle for the source collection, if any. + */ + union { + /** + * Access for mutating iterators. + */ + void *m; + /** + * Access for normal iterators. + */ + const void *c; + } src_handle; + + /** + * Field for storing a key-value pair. + * May be used by iterators that iterate over k/v-collections. + */ + struct { + /** + * A pointer to the key. + */ + const void *key; + /** + * A pointer to the value. + */ + void *value; + } kv_data; + + /** + * Field for storing a slot number. + * May be used by iterators that iterate over multi-bucket collections. + */ + size_t slot; + + /** + * If the iterator is position-aware, contains the index of the element in the underlying collection. + * Otherwise, this field is usually uninitialized. + */ + size_t index; + + /** + * The size of an individual element. + */ + size_t elem_size; + + /** + * May contain the total number of elements, if known. + * Shall be set to \c SIZE_MAX when the total number is unknown during iteration. + */ + size_t elem_count; +}; + +/** + * Iterator type. + * + * An iterator points to a certain element in a (possibly unbounded) chain of elements. + * Iterators that are based on collections (which have a defined "first" element), are supposed + * to be "position-aware", which means that they keep track of the current index within the collection. + * + * @note Objects that are pointed to by an iterator are always mutable through that iterator. However, + * any concurrent mutation of the collection other than by this iterator makes this iterator invalid + * and it must not be used anymore. + */ +typedef struct cx_iterator_s CxIterator; + +/** + * Checks if the iterator points to valid data. + * + * This is especially false for past-the-end iterators. + * + * @param iter the iterator + * @return true iff the iterator points to valid data + */ +#define cxIteratorValid(iter) (iter).base.valid(&(iter)) + +/** + * Returns a pointer to the current element. + * + * The behavior is undefined if this iterator is invalid. + * + * @param iter the iterator + * @return a pointer to the current element + */ +#define cxIteratorCurrent(iter) (iter).base.current(&iter) + +/** + * Advances the iterator to the next element. + * + * @param iter the iterator + */ +#define cxIteratorNext(iter) (iter).base.next(&iter) + +/** + * Flags the current element for removal, if this iterator is mutating. + * + * @param iter the iterator + */ +#define cxIteratorFlagRemoval(iter) (iter).base.remove |= (iter).base.mutating + +/** + * Obtains a reference to an arbitrary iterator. + * + * This is useful for APIs that expect some iterator as an argument. + * + * @param iter the iterator + */ +#define cxIteratorRef(iter) &((iter).base) + +/** + * Loops over an iterator. + * @param type the type of the elements + * @param elem the name of the iteration variable + * @param iter the iterator + */ +#define cx_foreach(type, elem, iter) \ +for (type elem; cxIteratorValid(iter) && (elem = (type)cxIteratorCurrent(iter)) != NULL ; cxIteratorNext(iter)) + + +/** + * Creates an iterator for the specified plain array. + * + * The \p array can be \c NULL in which case the iterator will be immediately + * initialized such that #cxIteratorValid() returns \c false. + * + * + * @param array a pointer to the array (can be \c NULL) + * @param elem_size the size of one array element + * @param elem_count the number of elements in the array + * @return an iterator for the specified array + */ +__attribute__((__warn_unused_result__)) +CxIterator cxIterator( + const void *array, + size_t elem_size, + size_t elem_count +); + +/** + * Creates a mutating iterator for the specified plain array. + * + * While the iterator is in use, the array may only be altered by removing + * elements through #cxIteratorFlagRemoval(). Every other change to the array + * will bring this iterator to an undefined state. + * + * When \p remove_keeps_order is set to \c false, removing an element will only + * move the last element to the position of the removed element, instead of + * moving all subsequent elements by one. Usually, when the order of elements is + * not important, this parameter should be set to \c false. + * + * The \p array can be \c NULL in which case the iterator will be immediately + * initialized such that #cxIteratorValid() returns \c false. + * + * + * @param array a pointer to the array (can be \c NULL) + * @param elem_size the size of one array element + * @param elem_count the number of elements in the array + * @param remove_keeps_order \c true if the order of elements must be preserved + * when removing an element + * @return an iterator for the specified array + */ +__attribute__((__warn_unused_result__)) +CxIterator cxMutIterator( + void *array, + size_t elem_size, + size_t elem_count, + bool remove_keeps_order +); + +#endif // UCX_ITERATOR_H