Sat, 22 Jan 2022 17:15:14 +0100
add iterator interface + linked list iterator
src/CMakeLists.txt | file | annotate | diff | comparison | revisions | |
src/cx/iterator.h | file | annotate | diff | comparison | revisions | |
src/cx/list.h | file | annotate | diff | comparison | revisions | |
src/linked_list.c | file | annotate | diff | comparison | revisions | |
test/test_list.c | file | annotate | diff | comparison | revisions | |
test/util_allocator.c | file | annotate | diff | comparison | revisions | |
test/util_allocator.h | file | annotate | diff | comparison | revisions |
1.1 --- a/src/CMakeLists.txt Sat Jan 22 10:29:48 2022 +0100 1.2 +++ b/src/CMakeLists.txt Sat Jan 22 17:15:14 2022 +0100 1.3 @@ -8,6 +8,7 @@ 1.4 set(headers 1.5 cx/utils.h 1.6 cx/allocator.h 1.7 + cx/iterator.h 1.8 cx/list.h 1.9 cx/linked_list.h 1.10 cx/tree.h
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 2.2 +++ b/src/cx/iterator.h Sat Jan 22 17:15:14 2022 +0100 2.3 @@ -0,0 +1,121 @@ 2.4 +/* 2.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 2.6 + * 2.7 + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. 2.8 + * 2.9 + * Redistribution and use in source and binary forms, with or without 2.10 + * modification, are permitted provided that the following conditions are met: 2.11 + * 2.12 + * 1. Redistributions of source code must retain the above copyright 2.13 + * notice, this list of conditions and the following disclaimer. 2.14 + * 2.15 + * 2. Redistributions in binary form must reproduce the above copyright 2.16 + * notice, this list of conditions and the following disclaimer in the 2.17 + * documentation and/or other materials provided with the distribution. 2.18 + * 2.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 2.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 2.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 2.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 2.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 2.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 2.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 2.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 2.29 + * POSSIBILITY OF SUCH DAMAGE. 2.30 + */ 2.31 +/** 2.32 + * \file iterator.h 2.33 + * \brief Interface for iterator implementations. 2.34 + * \author Mike Becker 2.35 + * \author Olaf Wintermann 2.36 + * \version 3.0 2.37 + * \copyright 2-Clause BSD License 2.38 + */ 2.39 + 2.40 +#ifndef UCX_ITERATOR_H 2.41 +#define UCX_ITERATOR_H 2.42 + 2.43 +#include "common.h" 2.44 + 2.45 +/** 2.46 + * Iterator value type. 2.47 + * An iterator points to a certain element in an (possibly unbounded) chain of elements. 2.48 + * Iterators that are based on collections (which have a defined "first" element), are supposed 2.49 + * to be "position-aware", which means that they keep track of the current index within the collection. 2.50 + * 2.51 + * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the 2.52 + * iterator is based on a collection and the underlying collection is mutated (elements added or removed), 2.53 + * the iterator becomes invalid (regardless of what cxIteratorValid() returns) and MUST be re-obtained 2.54 + * from the collection. 2.55 + */ 2.56 +typedef struct cx_iterator_s CxIterator; 2.57 + 2.58 +/** 2.59 + * Internal iterator struct - use CxIterator. 2.60 + */ 2.61 +struct cx_iterator_s { 2.62 + /** 2.63 + * If the iterator is position-aware, contains the index of the element in the underlying collection. 2.64 + * Otherwise, this field is usually uninitialized. 2.65 + */ 2.66 + size_t index; 2.67 + /** 2.68 + * Internal data. 2.69 + */ 2.70 + void *data; 2.71 + 2.72 + /** 2.73 + * True iff the iterator points to valid data. 2.74 + */ 2.75 + bool (*valid)(CxIterator const *) __attribute__ ((__nonnull__)); 2.76 + 2.77 + /** 2.78 + * Returns a pointer to the current element. 2.79 + */ 2.80 + void *(*current)(CxIterator const *) __attribute__ ((__nonnull__)); 2.81 + 2.82 + /** 2.83 + * Advances the iterator. 2.84 + */ 2.85 + void (*next)(CxIterator *) __attribute__ ((__nonnull__)); 2.86 +}; 2.87 + 2.88 +/** 2.89 + * Checks if the iterator points to valid data. 2.90 + * 2.91 + * This is especially false for past-the-end iterators. 2.92 + * 2.93 + * @param iter the iterator 2.94 + * @return true iff the iterator points to valid data 2.95 + */ 2.96 +__attribute__ ((__nonnull__)) 2.97 +static inline bool cxIteratorValid(CxIterator const *iter) { 2.98 + return iter->valid(iter); 2.99 +} 2.100 + 2.101 +/** 2.102 + * Returns a pointer to the current element. 2.103 + * 2.104 + * The behavior is undefined if this iterator is invalid. 2.105 + * 2.106 + * @param iter the iterator 2.107 + * @return a pointer to the current element 2.108 + */ 2.109 +__attribute__ ((__nonnull__)) 2.110 +static inline void *cxIteratorCurrent(CxIterator const *iter) { 2.111 + return iter->current(iter); 2.112 +} 2.113 + 2.114 +/** 2.115 + * Advances the iterator to the next element. 2.116 + * 2.117 + * @param iter the iterator 2.118 + */ 2.119 +__attribute__ ((__nonnull__)) 2.120 +static inline void cxIteratorNext(CxIterator *iter) { 2.121 + iter->next(iter); 2.122 +} 2.123 + 2.124 +#endif /* UCX_ITERATOR_H */
3.1 --- a/src/cx/list.h Sat Jan 22 10:29:48 2022 +0100 3.2 +++ b/src/cx/list.h Sat Jan 22 17:15:14 2022 +0100 3.3 @@ -39,6 +39,7 @@ 3.4 3.5 #include "common.h" 3.6 #include "allocator.h" 3.7 +#include "iterator.h" 3.8 3.9 #ifdef __cplusplus 3.10 extern "C" { 3.11 @@ -119,6 +120,14 @@ 3.12 * Member function for reversing the order of the items. 3.13 */ 3.14 void (*reverse)(cx_list_s *list); 3.15 + 3.16 + /** 3.17 + * Returns an iterator pointing to the specified index. 3.18 + */ 3.19 + CxIterator (*iterator)( 3.20 + cx_list_s const *list, 3.21 + size_t index 3.22 + ); 3.23 } cx_list_class; 3.24 3.25 /** 3.26 @@ -227,6 +236,38 @@ 3.27 } 3.28 3.29 /** 3.30 + * Returns an iterator pointing to the item at the specified index. 3.31 + * 3.32 + * The returned iterator is position-aware. 3.33 + * 3.34 + * If the index is out of range, a past-the-end iterator will be returned. 3.35 + * 3.36 + * @param list the list 3.37 + * @param index the index where the iterator shall point at 3.38 + * @return a new iterator 3.39 + */ 3.40 +static inline CxIterator cxListIterator( 3.41 + CxList list, 3.42 + size_t index 3.43 +) { 3.44 + return list->cl->iterator(list, index); 3.45 +} 3.46 + 3.47 +/** 3.48 + * Returns an iterator pointing to the first item of the list. 3.49 + * 3.50 + * The returned iterator is position-aware. 3.51 + * 3.52 + * If the list is empty, a past-the-end iterator will be returned. 3.53 + * 3.54 + * @param list the list 3.55 + * @return a new iterator 3.56 + */ 3.57 +static inline CxIterator cxListBegin(CxList list) { 3.58 + return list->cl->iterator(list, 0); 3.59 +} 3.60 + 3.61 +/** 3.62 * Returns the index of the first element that equals \p elem. 3.63 * 3.64 * Determining equality is performed by the list's comparator function.
4.1 --- a/src/linked_list.c Sat Jan 22 10:29:48 2022 +0100 4.2 +++ b/src/linked_list.c Sat Jan 22 17:15:14 2022 +0100 4.3 @@ -640,6 +640,48 @@ 4.4 true, list->cmpfunc); 4.5 } 4.6 4.7 +static bool cx_ll_iter_valid(CxIterator const *iter) { 4.8 + return iter->data != NULL; 4.9 +} 4.10 + 4.11 +static void cx_ll_iter_next(CxIterator *iter) { 4.12 + iter->index++; 4.13 + cx_linked_list_node *node = iter->data; 4.14 + iter->data = node->next; 4.15 +} 4.16 + 4.17 +static void *cx_ll_iter_current(CxIterator const *iter) { 4.18 + cx_linked_list_node *node = iter->data; 4.19 + return node->payload; 4.20 +} 4.21 + 4.22 +static void *cx_pll_iter_current(CxIterator const *iter) { 4.23 + cx_linked_list_node *node = iter->data; 4.24 + return *(void **) node->payload; 4.25 +} 4.26 + 4.27 +static CxIterator cx_ll_iterator( 4.28 + cx_list_s const *list, 4.29 + size_t index 4.30 +) { 4.31 + CxIterator iter; 4.32 + iter.index = index; 4.33 + iter.data = cx_ll_node_at((cx_linked_list const *) list, index); 4.34 + iter.valid = cx_ll_iter_valid; 4.35 + iter.current = cx_ll_iter_current; 4.36 + iter.next = cx_ll_iter_next; 4.37 + return iter; 4.38 +} 4.39 + 4.40 +static CxIterator cx_pll_iterator( 4.41 + cx_list_s const *list, 4.42 + size_t index 4.43 +) { 4.44 + CxIterator iter = cx_ll_iterator(list, index); 4.45 + iter.current = cx_pll_iter_current; 4.46 + return iter; 4.47 +} 4.48 + 4.49 static cx_list_class cx_linked_list_class = { 4.50 cx_ll_add, 4.51 cx_ll_insert, 4.52 @@ -648,7 +690,8 @@ 4.53 cx_ll_find, 4.54 cx_ll_sort, 4.55 cx_ll_compare, 4.56 - cx_ll_reverse 4.57 + cx_ll_reverse, 4.58 + cx_ll_iterator, 4.59 }; 4.60 4.61 static cx_list_class cx_pointer_linked_list_class = { 4.62 @@ -659,7 +702,8 @@ 4.63 cx_pll_find, 4.64 cx_pll_sort, 4.65 cx_pll_compare, 4.66 - cx_ll_reverse 4.67 + cx_ll_reverse, 4.68 + cx_pll_iterator, 4.69 }; 4.70 4.71 CxList cxLinkedListCreate(
5.1 --- a/test/test_list.c Sat Jan 22 10:29:48 2022 +0100 5.2 +++ b/test/test_list.c Sat Jan 22 17:15:14 2022 +0100 5.3 @@ -223,12 +223,12 @@ 5.4 5.5 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]); 5.6 CU_ASSERT_PTR_EQUAL(end, &nodes[0]) 5.7 - cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]); 5.8 + cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]); 5.9 CU_ASSERT_PTR_EQUAL(end, &nodes[1]) 5.10 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1]) 5.11 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0]) 5.12 5.13 - cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]); 5.14 + cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]); 5.15 CU_ASSERT_PTR_EQUAL(end, &nodes[2]) 5.16 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2]) 5.17 CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1]) 5.18 @@ -759,6 +759,38 @@ 5.19 CU_ASSERT_TRUE(cxTestingAllocatorVerify()) 5.20 } 5.21 5.22 +void test_hl_linked_list_iterator_impl(CxList list) { 5.23 + int i = 0; 5.24 + for (CxIterator iter = cxListBegin(list); cxIteratorValid(&iter); cxIteratorNext(&iter)) { 5.25 + CU_ASSERT_EQUAL(iter.index, (size_t) i) 5.26 + int *x = cxIteratorCurrent(&iter); 5.27 + CU_ASSERT_EQUAL(*x, i) 5.28 + i++; 5.29 + } 5.30 + CU_ASSERT_EQUAL(i, 10) 5.31 + cxLinkedListDestroy(list); 5.32 + CU_ASSERT_TRUE(cxTestingAllocatorVerify()) 5.33 +} 5.34 + 5.35 +void test_hl_linked_list_iterator(void) { 5.36 + cxTestingAllocatorReset(); 5.37 + CxList list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int)); 5.38 + for (int i = 0; i < 10; i++) { 5.39 + cxListAdd(list, &i); 5.40 + } 5.41 + test_hl_linked_list_iterator_impl(list); 5.42 +} 5.43 + 5.44 +void test_hl_ptr_linked_list_iterator(void) { 5.45 + cxTestingAllocatorReset(); 5.46 + CxList list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int); 5.47 + int data[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 5.48 + for (int i = 0; i < 10; i++) { 5.49 + cxListAdd(list, &data[i]); 5.50 + } 5.51 + test_hl_linked_list_iterator_impl(list); 5.52 +} 5.53 + 5.54 void test_hl_ptr_linked_list_create(void) { 5.55 cxTestingAllocatorReset(); 5.56 5.57 @@ -887,9 +919,9 @@ 5.58 cxListAdd(list, &b); 5.59 cxListAdd(list, &c); 5.60 5.61 - CU_ASSERT_EQUAL(*(int*)cxListAt(list, 0), 5) 5.62 - CU_ASSERT_EQUAL(*(int*)cxListAt(list, 1), 47) 5.63 - CU_ASSERT_EQUAL(*(int*)cxListAt(list, 2), 13) 5.64 + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5) 5.65 + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47) 5.66 + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13) 5.67 CU_ASSERT_PTR_NULL(cxListAt(list, 3)) 5.68 5.69 cxLinkedListDestroy(list); 5.70 @@ -997,6 +1029,7 @@ 5.71 cu_add_test(suite, test_hl_linked_list_at); 5.72 cu_add_test(suite, test_hl_linked_list_find); 5.73 cu_add_test(suite, test_hl_linked_list_sort); 5.74 + cu_add_test(suite, test_hl_linked_list_iterator); 5.75 5.76 suite = CU_add_suite("high level pointer linked list", NULL, NULL); 5.77 5.78 @@ -1007,6 +1040,7 @@ 5.79 cu_add_test(suite, test_hl_ptr_linked_list_at); 5.80 cu_add_test(suite, test_hl_ptr_linked_list_find); 5.81 cu_add_test(suite, test_hl_ptr_linked_list_sort); 5.82 + cu_add_test(suite, test_hl_ptr_linked_list_iterator); 5.83 5.84 CU_basic_set_mode(UCX_CU_BRM); 5.85
6.1 --- a/test/util_allocator.c Sat Jan 22 10:29:48 2022 +0100 6.2 +++ b/test/util_allocator.c Sat Jan 22 17:15:14 2022 +0100 6.3 @@ -119,7 +119,7 @@ 6.4 memset(&cx_testing_allocator_data, 0, sizeof(cx_testing_allocator_s)); 6.5 } 6.6 6.7 -int cxTestingAllocatorVerify(void) { 6.8 +bool cxTestingAllocatorVerify(void) { 6.9 return cx_testing_allocator_data.live == 0 6.10 && cx_testing_allocator_data.alloc_failed == 0 && cx_testing_allocator_data.free_failed == 0 6.11 && cx_testing_allocator_data.alloc_total == cx_testing_allocator_data.free_total;
7.1 --- a/test/util_allocator.h Sat Jan 22 10:29:48 2022 +0100 7.2 +++ b/test/util_allocator.h Sat Jan 22 17:15:14 2022 +0100 7.3 @@ -81,7 +81,7 @@ 7.4 * 7.5 * @return true on success, false if there was any problem 7.6 */ 7.7 -int cxTestingAllocatorVerify(void); 7.8 +bool cxTestingAllocatorVerify(void); 7.9 7.10 #ifdef __cplusplus 7.11 }; /* extern "C" */