--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ucx/cx/iterator.h Sat Dec 07 18:56:37 2024 +0100
@@ -0,0 +1,255 @@
+/*
+ * 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)(void const *);
+
+ /**
+ * Returns a pointer to the current element.
+ *
+ * When valid returns false, the behavior of this function is undefined.
+ */
+ __attribute__ ((__nonnull__))
+ void *(*current)(void const *);
+
+ /**
+ * Original implementation in case the function needs to be wrapped.
+ */
+ __attribute__ ((__nonnull__))
+ void *(*current_impl)(void const *);
+
+ /**
+ * 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.
+ */
+#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.
+ */
+ void const *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.
+ */
+ void const *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
+
+/**
+ * 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(
+ void const *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