Sun, 21 May 2023 14:03:21 +0200
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 +}