Mercurial > hg > ucx / changeset

     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" */