--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ucx/cx/iterator.h Mon May 22 16:17:26 2023 +0200
@@ -0,0 +1,263 @@
+/*
+ * 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
+ * \version 3.0
+ * \copyright 2-Clause BSD License
+ */
+
+#ifndef UCX_ITERATOR_H
+#define UCX_ITERATOR_H
+
+#include "common.h"
+
+/**
+ * The base of mutating and non-mutating iterators.
+ */
+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 *);
+
+ /**
+ * Flag current element for removal, if possible.
+ *
+ * When valid returns false, the behavior of this function is undefined.
+ */
+ __attribute__ ((__nonnull__))
+ bool (*flag_removal)(void *);
+
+ /**
+ * Indicates whether this iterator may remove elements.
+ */
+ bool mutating;
+
+ /**
+ * Internal flag for removing the current element when advancing.
+ */
+ bool remove;
+};
+
+/**
+ * Internal iterator struct - use CxMutIterator.
+ */
+struct cx_mut_iterator_s {
+
+ /**
+ * The base properties of this iterator.
+ */
+ struct cx_iterator_base_s base;
+
+ /**
+ * Handle for the current element, if required.
+ */
+ void *elem_handle;
+
+ /**
+ * Handle for the source collection, if any.
+ */
+ void *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;
+};
+
+/**
+ * Mutating iterator value type.
+ *
+ * An iterator points to a certain element in an (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 mutable through that iterator. However, if the
+ * iterator is based on a collection and the underlying collection is mutated by other means than this iterator
+ * (e.g. elements added or removed), the iterator becomes invalid (regardless of what cxIteratorValid() returns)
+ * and MUST be re-obtained from the collection.
+ *
+ * @see CxIterator
+ */
+typedef struct cx_mut_iterator_s CxMutIterator;
+
+/**
+ * Internal iterator struct - use CxIterator.
+ */
+struct cx_iterator_s {
+
+ /**
+ * The base properties of this iterator.
+ */
+ struct cx_iterator_base_s base;
+
+ /**
+ * Handle for the current element, if required.
+ */
+ void *elem_handle;
+
+ /**
+ * Handle for the source collection, if any.
+ */
+ void const *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;
+};
+
+/**
+ * Iterator value type.
+ * An iterator points to a certain element in an (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,
+ * this iterator cannot mutate the collection itself (add or remove elements) and any mutation of the
+ * collection by other means make this iterator invalid (regardless of what cxIteratorValid() returns).
+ *
+ * @see CxMutIterator
+ */
+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.
+ *
+ * @param iter the iterator
+ * @return false if this iterator cannot remove the element
+ */
+#define cxIteratorFlagRemoval(iter) (iter).base.flag_removal(&iter)
+
+/**
+ * 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))
+
+#endif // UCX_ITERATOR_H