# HG changeset patch
# User Mike Becker <universe@uap-core.de>
# Date 1642868114 -3600
# Node ID 6ce8cfa10a96647d97c79bbbd17d006034c71ae8
# Parent  e3469b497effd3be0785e751197c1bc14e6a73d6
add iterator interface + linked list iterator

diff -r e3469b497eff -r 6ce8cfa10a96 src/CMakeLists.txt
--- a/src/CMakeLists.txt	Sat Jan 22 10:29:48 2022 +0100
+++ b/src/CMakeLists.txt	Sat Jan 22 17:15:14 2022 +0100
@@ -8,6 +8,7 @@
 set(headers
         cx/utils.h
         cx/allocator.h
+        cx/iterator.h
         cx/list.h
         cx/linked_list.h
         cx/tree.h
diff -r e3469b497eff -r 6ce8cfa10a96 src/cx/iterator.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/cx/iterator.h	Sat Jan 22 17:15:14 2022 +0100
@@ -0,0 +1,121 @@
+/*
+ * 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"
+
+/**
+ * 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 (elements added or removed),
+ * the iterator becomes invalid (regardless of what cxIteratorValid() returns) and MUST be re-obtained
+ * from the collection.
+ */
+typedef struct cx_iterator_s CxIterator;
+
+/**
+ * Internal iterator struct - use CxIterator.
+ */
+struct cx_iterator_s {
+    /**
+     * 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;
+    /**
+     * Internal data.
+     */
+    void *data;
+
+    /**
+     * True iff the iterator points to valid data.
+     */
+    bool (*valid)(CxIterator const *) __attribute__ ((__nonnull__));
+
+    /**
+     * Returns a pointer to the current element.
+     */
+    void *(*current)(CxIterator const *) __attribute__ ((__nonnull__));
+
+    /**
+     * Advances the iterator.
+     */
+    void (*next)(CxIterator *) __attribute__ ((__nonnull__));
+};
+
+/**
+ * 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
+ */
+__attribute__ ((__nonnull__))
+static inline bool cxIteratorValid(CxIterator const *iter) {
+    return iter->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
+ */
+__attribute__ ((__nonnull__))
+static inline void *cxIteratorCurrent(CxIterator const *iter) {
+    return iter->current(iter);
+}
+
+/**
+ * Advances the iterator to the next element.
+ *
+ * @param iter the iterator
+ */
+__attribute__ ((__nonnull__))
+static inline void cxIteratorNext(CxIterator *iter) {
+    iter->next(iter);
+}
+
+#endif /* UCX_ITERATOR_H */
diff -r e3469b497eff -r 6ce8cfa10a96 src/cx/list.h
--- a/src/cx/list.h	Sat Jan 22 10:29:48 2022 +0100
+++ b/src/cx/list.h	Sat Jan 22 17:15:14 2022 +0100
@@ -39,6 +39,7 @@
 
 #include "common.h"
 #include "allocator.h"
+#include "iterator.h"
 
 #ifdef __cplusplus
 extern "C" {
@@ -119,6 +120,14 @@
      * Member function for reversing the order of the items.
      */
     void (*reverse)(cx_list_s *list);
+
+    /**
+     * Returns an iterator pointing to the specified index.
+     */
+    CxIterator (*iterator)(
+            cx_list_s const *list,
+            size_t index
+    );
 } cx_list_class;
 
 /**
@@ -227,6 +236,38 @@
 }
 
 /**
+ * Returns an iterator pointing to the item at the specified index.
+ *
+ * The returned iterator is position-aware.
+ *
+ * If the index is out of range, a past-the-end iterator will be returned.
+ *
+ * @param list the list
+ * @param index the index where the iterator shall point at
+ * @return a new iterator
+ */
+static inline CxIterator cxListIterator(
+        CxList list,
+        size_t index
+) {
+    return list->cl->iterator(list, index);
+}
+
+/**
+ * Returns an iterator pointing to the first item of the list.
+ *
+ * The returned iterator is position-aware.
+ *
+ * If the list is empty, a past-the-end iterator will be returned.
+ *
+ * @param list the list
+ * @return a new iterator
+ */
+static inline CxIterator cxListBegin(CxList list) {
+    return list->cl->iterator(list, 0);
+}
+
+/**
  * Returns the index of the first element that equals \p elem.
  *
  * Determining equality is performed by the list's comparator function.
diff -r e3469b497eff -r 6ce8cfa10a96 src/linked_list.c
--- a/src/linked_list.c	Sat Jan 22 10:29:48 2022 +0100
+++ b/src/linked_list.c	Sat Jan 22 17:15:14 2022 +0100
@@ -640,6 +640,48 @@
                                   true, list->cmpfunc);
 }
 
+static bool cx_ll_iter_valid(CxIterator const *iter) {
+    return iter->data != NULL;
+}
+
+static void cx_ll_iter_next(CxIterator *iter) {
+    iter->index++;
+    cx_linked_list_node *node = iter->data;
+    iter->data = node->next;
+}
+
+static void *cx_ll_iter_current(CxIterator const *iter) {
+    cx_linked_list_node *node = iter->data;
+    return node->payload;
+}
+
+static void *cx_pll_iter_current(CxIterator const *iter) {
+    cx_linked_list_node *node = iter->data;
+    return *(void **) node->payload;
+}
+
+static CxIterator cx_ll_iterator(
+        cx_list_s const *list,
+        size_t index
+) {
+    CxIterator iter;
+    iter.index = index;
+    iter.data = cx_ll_node_at((cx_linked_list const *) list, index);
+    iter.valid = cx_ll_iter_valid;
+    iter.current = cx_ll_iter_current;
+    iter.next = cx_ll_iter_next;
+    return iter;
+}
+
+static CxIterator cx_pll_iterator(
+        cx_list_s const *list,
+        size_t index
+) {
+    CxIterator iter = cx_ll_iterator(list, index);
+    iter.current = cx_pll_iter_current;
+    return iter;
+}
+
 static cx_list_class cx_linked_list_class = {
         cx_ll_add,
         cx_ll_insert,
@@ -648,7 +690,8 @@
         cx_ll_find,
         cx_ll_sort,
         cx_ll_compare,
-        cx_ll_reverse
+        cx_ll_reverse,
+        cx_ll_iterator,
 };
 
 static cx_list_class cx_pointer_linked_list_class = {
@@ -659,7 +702,8 @@
         cx_pll_find,
         cx_pll_sort,
         cx_pll_compare,
-        cx_ll_reverse
+        cx_ll_reverse,
+        cx_pll_iterator,
 };
 
 CxList cxLinkedListCreate(
diff -r e3469b497eff -r 6ce8cfa10a96 test/test_list.c
--- a/test/test_list.c	Sat Jan 22 10:29:48 2022 +0100
+++ b/test/test_list.c	Sat Jan 22 17:15:14 2022 +0100
@@ -223,12 +223,12 @@
 
     cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]);
     CU_ASSERT_PTR_EQUAL(end, &nodes[0])
-    cx_linked_list_add(NULL, &end,  loc_prev, loc_next, &nodes[1]);
+    cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]);
     CU_ASSERT_PTR_EQUAL(end, &nodes[1])
     CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
     CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
 
-    cx_linked_list_add(NULL, &end,  loc_prev, loc_next, &nodes[2]);
+    cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]);
     CU_ASSERT_PTR_EQUAL(end, &nodes[2])
     CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
     CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
@@ -759,6 +759,38 @@
     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
 }
 
+void test_hl_linked_list_iterator_impl(CxList list) {
+    int i = 0;
+    for (CxIterator iter = cxListBegin(list); cxIteratorValid(&iter); cxIteratorNext(&iter)) {
+        CU_ASSERT_EQUAL(iter.index, (size_t) i)
+        int *x = cxIteratorCurrent(&iter);
+        CU_ASSERT_EQUAL(*x, i)
+        i++;
+    }
+    CU_ASSERT_EQUAL(i, 10)
+    cxLinkedListDestroy(list);
+    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
+}
+
+void test_hl_linked_list_iterator(void) {
+    cxTestingAllocatorReset();
+    CxList list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
+    for (int i = 0; i < 10; i++) {
+        cxListAdd(list, &i);
+    }
+    test_hl_linked_list_iterator_impl(list);
+}
+
+void test_hl_ptr_linked_list_iterator(void) {
+    cxTestingAllocatorReset();
+    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
+    int data[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+    for (int i = 0; i < 10; i++) {
+        cxListAdd(list, &data[i]);
+    }
+    test_hl_linked_list_iterator_impl(list);
+}
+
 void test_hl_ptr_linked_list_create(void) {
     cxTestingAllocatorReset();
 
@@ -887,9 +919,9 @@
     cxListAdd(list, &b);
     cxListAdd(list, &c);
 
-    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 0), 5)
-    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 1), 47)
-    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 2), 13)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
     CU_ASSERT_PTR_NULL(cxListAt(list, 3))
 
     cxLinkedListDestroy(list);
@@ -997,6 +1029,7 @@
     cu_add_test(suite, test_hl_linked_list_at);
     cu_add_test(suite, test_hl_linked_list_find);
     cu_add_test(suite, test_hl_linked_list_sort);
+    cu_add_test(suite, test_hl_linked_list_iterator);
 
     suite = CU_add_suite("high level pointer linked list", NULL, NULL);
 
@@ -1007,6 +1040,7 @@
     cu_add_test(suite, test_hl_ptr_linked_list_at);
     cu_add_test(suite, test_hl_ptr_linked_list_find);
     cu_add_test(suite, test_hl_ptr_linked_list_sort);
+    cu_add_test(suite, test_hl_ptr_linked_list_iterator);
 
     CU_basic_set_mode(UCX_CU_BRM);
 
diff -r e3469b497eff -r 6ce8cfa10a96 test/util_allocator.c
--- a/test/util_allocator.c	Sat Jan 22 10:29:48 2022 +0100
+++ b/test/util_allocator.c	Sat Jan 22 17:15:14 2022 +0100
@@ -119,7 +119,7 @@
     memset(&cx_testing_allocator_data, 0, sizeof(cx_testing_allocator_s));
 }
 
-int cxTestingAllocatorVerify(void) {
+bool cxTestingAllocatorVerify(void) {
     return cx_testing_allocator_data.live == 0
            && cx_testing_allocator_data.alloc_failed == 0 && cx_testing_allocator_data.free_failed == 0
            && cx_testing_allocator_data.alloc_total == cx_testing_allocator_data.free_total;
diff -r e3469b497eff -r 6ce8cfa10a96 test/util_allocator.h
--- a/test/util_allocator.h	Sat Jan 22 10:29:48 2022 +0100
+++ b/test/util_allocator.h	Sat Jan 22 17:15:14 2022 +0100
@@ -81,7 +81,7 @@
  *
  * @return true on success, false if there was any problem
  */
-int cxTestingAllocatorVerify(void);
+bool cxTestingAllocatorVerify(void);
 
 #ifdef __cplusplus
 }; /* extern "C" */