add empty list implementation - fixes #258

Sun, 21 May 2023 14:03:21 +0200

author
Mike Becker <universe@uap-core.de>
date
Sun, 21 May 2023 14:03:21 +0200
changeset 704
35f06c5eeb0e
parent 703
425d4279856f
child 705
0d5447230044

add empty list implementation - fixes #258

src/cx/iterator.h file | annotate | diff | comparison | revisions
src/cx/list.h file | annotate | diff | comparison | revisions
src/list.c file | annotate | diff | comparison | revisions
tests/test_list.cpp file | annotate | diff | comparison | revisions
     1.1 --- a/src/cx/iterator.h	Sun May 21 11:52:58 2023 +0200
     1.2 +++ b/src/cx/iterator.h	Sun May 21 14:03:21 2023 +0200
     1.3 @@ -51,6 +51,8 @@
     1.4  
     1.5      /**
     1.6       * Returns a pointer to the current element.
     1.7 +     *
     1.8 +     * When valid returns false, the behavior of this function is undefined.
     1.9       */
    1.10      __attribute__ ((__nonnull__))
    1.11      void *(*current)(void const *);
    1.12 @@ -63,12 +65,16 @@
    1.13  
    1.14      /**
    1.15       * Advances the iterator.
    1.16 +     *
    1.17 +     * When valid returns false, the behavior of this function is undefined.
    1.18       */
    1.19      __attribute__ ((__nonnull__))
    1.20      void (*next)(void *);
    1.21  
    1.22      /**
    1.23       * Flag current element for removal, if possible.
    1.24 +     *
    1.25 +     * When valid returns false, the behavior of this function is undefined.
    1.26       */
    1.27      __attribute__ ((__nonnull__))
    1.28      bool (*flag_removal)(void *);
     2.1 --- a/src/cx/list.h	Sun May 21 11:52:58 2023 +0200
     2.2 +++ b/src/cx/list.h	Sun May 21 14:03:21 2023 +0200
     2.3 @@ -632,6 +632,14 @@
     2.4  __attribute__((__nonnull__))
     2.5  void cxListDestroy(CxList *list);
     2.6  
     2.7 +/**
     2.8 + * A shared instance of an empty list.
     2.9 + *
    2.10 + * Writing to that list is undefined.
    2.11 + */
    2.12 +extern CxList * const cxEmptyList;
    2.13 +
    2.14 +
    2.15  #ifdef __cplusplus
    2.16  } // extern "C"
    2.17  #endif
     3.1 --- a/src/list.c	Sun May 21 11:52:58 2023 +0200
     3.2 +++ b/src/list.c	Sun May 21 14:03:21 2023 +0200
     3.3 @@ -195,6 +195,83 @@
     3.4  
     3.5  // </editor-fold>
     3.6  
     3.7 +// <editor-fold desc="empty list implementation">
     3.8 +
     3.9 +static void cx_emptyl_noop(__attribute__((__unused__)) CxList *list) {
    3.10 +    // this is a noop, but MUST be implemented
    3.11 +}
    3.12 +
    3.13 +static void *cx_emptyl_at(
    3.14 +        __attribute__((__unused__)) struct cx_list_s const *list,
    3.15 +        __attribute__((__unused__)) size_t index
    3.16 +) {
    3.17 +    return NULL;
    3.18 +}
    3.19 +
    3.20 +static ssize_t cx_emptyl_find(
    3.21 +        __attribute__((__unused__)) struct cx_list_s const *list,
    3.22 +        __attribute__((__unused__)) void const *elem
    3.23 +) {
    3.24 +    return -1;
    3.25 +}
    3.26 +
    3.27 +static int cx_emptyl_compare(
    3.28 +        __attribute__((__unused__)) struct cx_list_s const *list,
    3.29 +        struct cx_list_s const *other
    3.30 +) {
    3.31 +    if (other->size == 0) return 0;
    3.32 +    return -1;
    3.33 +}
    3.34 +
    3.35 +static bool cx_emptyl_iter_valid(__attribute__((__unused__)) void const *iter) {
    3.36 +    return false;
    3.37 +}
    3.38 +
    3.39 +static CxIterator cx_emptyl_iterator(
    3.40 +        struct cx_list_s const *list,
    3.41 +        size_t index,
    3.42 +        __attribute__((__unused__)) bool backwards
    3.43 +) {
    3.44 +    CxIterator iter = {0};
    3.45 +    iter.src_handle = list;
    3.46 +    iter.index = index;
    3.47 +    iter.base.valid = cx_emptyl_iter_valid;
    3.48 +    return iter;
    3.49 +}
    3.50 +
    3.51 +static cx_list_class cx_empty_list_class = {
    3.52 +        cx_emptyl_noop,
    3.53 +        NULL,
    3.54 +        NULL,
    3.55 +        NULL,
    3.56 +        NULL,
    3.57 +        cx_emptyl_noop,
    3.58 +        NULL,
    3.59 +        cx_emptyl_at,
    3.60 +        cx_emptyl_find,
    3.61 +        cx_emptyl_noop,
    3.62 +        cx_emptyl_compare,
    3.63 +        cx_emptyl_noop,
    3.64 +        cx_emptyl_iterator,
    3.65 +};
    3.66 +
    3.67 +CxList cx_empty_list = {
    3.68 +        NULL,
    3.69 +        NULL,
    3.70 +        0,
    3.71 +        0,
    3.72 +        NULL,
    3.73 +        NULL,
    3.74 +        NULL,
    3.75 +        false,
    3.76 +        &cx_empty_list_class,
    3.77 +        NULL
    3.78 +};
    3.79 +
    3.80 +CxList *const cxEmptyList = &cx_empty_list;
    3.81 +
    3.82 +// </editor-fold>
    3.83 +
    3.84  void cxListDestroy(CxList *list) {
    3.85      if (list->simple_destructor) {
    3.86          CxIterator iter = cxListIterator(list);
    3.87 @@ -212,7 +289,9 @@
    3.88      }
    3.89  
    3.90      list->cl->destructor(list);
    3.91 -    cxFree(list->allocator, list);
    3.92 +    if (list->allocator) {
    3.93 +        cxFree(list->allocator, list);
    3.94 +    }
    3.95  }
    3.96  
    3.97  int cxListCompare(
     4.1 --- a/tests/test_list.cpp	Sun May 21 11:52:58 2023 +0200
     4.2 +++ b/tests/test_list.cpp	Sun May 21 14:03:21 2023 +0200
     4.3 @@ -1477,3 +1477,80 @@
     4.4      EXPECT_TRUE(testingAllocator.verify());
     4.5  }
     4.6  
     4.7 +TEST(EmptyList, Size) {
     4.8 +    auto list = cxEmptyList;
     4.9 +
    4.10 +    EXPECT_EQ(list->size, 0);
    4.11 +    EXPECT_EQ(cxListSize(list), 0);
    4.12 +}
    4.13 +
    4.14 +TEST(EmptyList, Iterator) {
    4.15 +    auto list = cxEmptyList;
    4.16 +
    4.17 +    auto it1 = cxListIterator(list);
    4.18 +    auto it2 = cxListBackwardsIterator(list);
    4.19 +    auto it3 = cxListMutIterator(list);
    4.20 +    auto it4 = cxListMutBackwardsIterator(list);
    4.21 +
    4.22 +    EXPECT_FALSE(cxIteratorValid(it1));
    4.23 +    EXPECT_FALSE(cxIteratorValid(it2));
    4.24 +    EXPECT_FALSE(cxIteratorValid(it3));
    4.25 +    EXPECT_FALSE(cxIteratorValid(it4));
    4.26 +
    4.27 +    int c = 0;
    4.28 +    cx_foreach(void*, data, it1) c++;
    4.29 +    cx_foreach(void*, data, it2) c++;
    4.30 +    cx_foreach(void*, data, it3) c++;
    4.31 +    cx_foreach(void*, data, it4) c++;
    4.32 +    EXPECT_EQ(c, 0);
    4.33 +}
    4.34 +
    4.35 +TEST(EmptyList, NoOps) {
    4.36 +    auto list = cxEmptyList;
    4.37 +
    4.38 +    ASSERT_NO_FATAL_FAILURE(cxListSort(list));
    4.39 +    ASSERT_NO_FATAL_FAILURE(cxListClear(list));
    4.40 +    ASSERT_NO_FATAL_FAILURE(cxListDestroy(list));
    4.41 +}
    4.42 +
    4.43 +TEST(EmptyList, At) {
    4.44 +    auto list = cxEmptyList;
    4.45 +
    4.46 +    EXPECT_EQ(cxListAt(list, 0), nullptr);
    4.47 +    EXPECT_EQ(cxListAt(list, 1), nullptr);
    4.48 +}
    4.49 +
    4.50 +TEST(EmptyList, Find) {
    4.51 +    auto list = cxEmptyList;
    4.52 +
    4.53 +    int x = 42, y = 1337;
    4.54 +
    4.55 +    EXPECT_LT(cxListFind(list, &x), 0);
    4.56 +    EXPECT_LT(cxListFind(list, &y), 0);
    4.57 +}
    4.58 +
    4.59 +TEST(EmptyList, Compare) {
    4.60 +    auto empty = cxEmptyList;
    4.61 +
    4.62 +    auto ll = cxLinkedListCreateSimple(sizeof(int));
    4.63 +    auto al = cxArrayListCreateSimple(sizeof(int), 8);
    4.64 +
    4.65 +    int x = 5;
    4.66 +
    4.67 +    EXPECT_EQ(cxListCompare(empty, cxEmptyList), 0);
    4.68 +    EXPECT_EQ(cxListCompare(ll, cxEmptyList), 0);
    4.69 +    EXPECT_EQ(cxListCompare(al, cxEmptyList), 0);
    4.70 +    EXPECT_EQ(cxListCompare(cxEmptyList, ll), 0);
    4.71 +    EXPECT_EQ(cxListCompare(cxEmptyList, al), 0);
    4.72 +
    4.73 +    cxListAdd(ll, &x);
    4.74 +    cxListAdd(al, &x);
    4.75 +
    4.76 +    EXPECT_GT(cxListCompare(ll, cxEmptyList), 0);
    4.77 +    EXPECT_GT(cxListCompare(al, cxEmptyList), 0);
    4.78 +    EXPECT_LT(cxListCompare(cxEmptyList, ll), 0);
    4.79 +    EXPECT_LT(cxListCompare(cxEmptyList, al), 0);
    4.80 +
    4.81 +    cxListDestroy(ll);
    4.82 +    cxListDestroy(al);
    4.83 +}

mercurial