# HG changeset patch # User Mike Becker # Date 1674763176 -3600 # Node ID d402fead3386c26ea60a797f6f8a36f699e54ccb # Parent 55cc3b373c5e67cfccae915e4066ebb51b0f0b48 add new pointer list wrapper - resolves #234 since we need a thread local variable, this drops C99 support diff -r 55cc3b373c5e -r d402fead3386 CMakeLists.txt --- a/CMakeLists.txt Wed Jan 25 19:19:29 2023 +0100 +++ b/CMakeLists.txt Thu Jan 26 20:59:36 2023 +0100 @@ -3,7 +3,7 @@ # Configuration set(CMAKE_C_STANDARD 11) -set(CMAKE_C_STANDARD_REQUIRED 99) +set(CMAKE_C_STANDARD_REQUIRED 11) option(GCC_MORE_WARNINGS "Enable -Wall -Wextra -pedantic when using gcc." OFF) if (GCC_MORE_WARNINGS AND CMAKE_COMPILER_IS_GNUCC) diff -r 55cc3b373c5e -r d402fead3386 src/array_list.c --- a/src/array_list.c Wed Jan 25 19:19:29 2023 +0100 +++ b/src/array_list.c Thu Jan 26 20:59:36 2023 +0100 @@ -224,6 +224,14 @@ } } +static int cx_arl_insert_element( + struct cx_list_s *list, + size_t index, + void const *element +) { + return 1 != cx_arl_insert_array(list, index, element, 1); +} + static int cx_arl_insert_iter( struct cx_mut_iterator_s *iter, void const *elem, @@ -231,11 +239,10 @@ ) { struct cx_list_s *list = iter->src_handle; if (iter->index < list->size) { - int result = 1 != cx_arl_insert_array( + int result = cx_arl_insert_element( list, iter->index + 1 - prepend, - elem, - 1 + elem ); if (result == 0 && prepend != 0) { iter->index++; @@ -243,7 +250,7 @@ } return result; } else { - int result = 1 != cx_arl_insert_array(list, list->size, elem, 1); + int result = cx_arl_insert_element(list, list->size, elem); iter->index = list->size; return result; } @@ -407,6 +414,7 @@ static cx_list_class cx_array_list_class = { cx_arl_destructor, + cx_arl_insert_element, cx_arl_insert_array, cx_arl_insert_iter, cx_arl_remove, diff -r 55cc3b373c5e -r d402fead3386 src/cx/iterator.h --- a/src/cx/iterator.h Wed Jan 25 19:19:29 2023 +0100 +++ b/src/cx/iterator.h Thu Jan 26 20:59:36 2023 +0100 @@ -56,6 +56,12 @@ void *(*current)(void const *); /** + * Original implementation in case the function needs to be wrapped. + */ + __attribute__ ((__nonnull__)) + void *(*current_impl)(void const *); + + /** * Advances the iterator. */ __attribute__ ((__nonnull__)) diff -r 55cc3b373c5e -r d402fead3386 src/cx/list.h --- a/src/cx/list.h Wed Jan 25 19:19:29 2023 +0100 +++ b/src/cx/list.h Thu Jan 26 20:59:36 2023 +0100 @@ -65,7 +65,11 @@ /** * The list class definition. */ - cx_list_class *cl; + cx_list_class const *cl; + /** + * The actual implementation in case the list class is delegating. + */ + cx_list_class const *climpl; /** * The allocator to use. */ @@ -122,6 +126,16 @@ void (*destructor)(struct cx_list_s *list); /** + * Member function for inserting a single elements. + * Implementors SHOULD see to performant implementations for corner cases. + */ + int (*insert_element)( + struct cx_list_s *list, + size_t index, + void const *data + ); + + /** * Member function for inserting multiple elements. * Implementors SHOULD see to performant implementations for corner cases. */ @@ -198,6 +212,43 @@ typedef struct cx_list_s CxList; /** + * Advises the list to store copies of the objects (default mode of operation). + * + * Retrieving objects from this list will yield pointers to the copies stored + * within this list. + * + * @param list the list + * @see cxListStorePointers() + */ +__attribute__((__nonnull__)) +void cxListStoreObjects(CxList *list); + +/** + * Advises the list to only store pointers to the objects. + * + * Retrieving objects from this list will yield the original pointers stored. + * + * @note This function forcibly sets the element size to the size of a pointer. + * Invoking this function on a non-empty list that already stores copies of + * objects is undefined. + * + * @param list the list + * @see cxListStoreObjects() + */ +__attribute__((__nonnull__)) +void cxListStorePointers(CxList *list); + +/** + * Returns true, if this list is storing pointers instead of the actual data. + * + * @param list + * @return + * @see cxListStorePointers() + */ +__attribute__((__nonnull__)) +bool cxListIsStoringPointers(CxList *list); + +/** * Adds an item to the end of the list. * * @param list the list @@ -210,7 +261,7 @@ CxList *list, void const *elem ) { - return list->cl->insert_array(list, list->size, elem, 1) != 1; + return list->cl->insert_element(list, list->size, elem); } /** @@ -221,6 +272,9 @@ * If there is not enough memory to add all elements, the returned value is * less than \p n. * + * If this list is storing pointers instead of objects \p array is expected to + * be an array of pointers. + * * @param list the list * @param array a pointer to the elements to add * @param n the number of elements to add @@ -254,7 +308,7 @@ size_t index, void const *elem ) { - return list->cl->insert_array(list, index, elem, 1) != 1; + return list->cl->insert_element(list, index, elem); } /** @@ -267,6 +321,9 @@ * If there is not enough memory to add all elements, the returned value is * less than \p n. * + * If this list is storing pointers instead of objects \p array is expected to + * be an array of pointers. + * * @param list the list * @param index the index where to add the elements * @param array a pointer to the elements to add diff -r 55cc3b373c5e -r d402fead3386 src/linked_list.c --- a/src/linked_list.c Wed Jan 25 19:19:29 2023 +0100 +++ b/src/linked_list.c Thu Jan 26 20:59:36 2023 +0100 @@ -546,6 +546,14 @@ return n; } +static int cx_ll_insert_element( + struct cx_list_s *list, + size_t index, + void const *element +) { + return 1 != cx_ll_insert_array(list, index, element, 1); +} + static int cx_ll_remove( struct cx_list_s *list, size_t index @@ -682,7 +690,7 @@ iter->index += prepend * (0 == result); return result; } else { - int result = cx_ll_insert_array(list, list->size, elem, 1) != 1; + int result = cx_ll_insert_element(list, list->size, elem); iter->index = list->size; return result; } @@ -702,6 +710,7 @@ static cx_list_class cx_linked_list_class = { cx_ll_destructor, + cx_ll_insert_element, cx_ll_insert_array, cx_ll_insert_iter, cx_ll_remove, diff -r 55cc3b373c5e -r d402fead3386 src/list.c --- a/src/list.c Wed Jan 25 19:19:29 2023 +0100 +++ b/src/list.c Thu Jan 26 20:59:36 2023 +0100 @@ -30,6 +30,158 @@ #include +// + +static _Thread_local CxListComparator cx_pl_cmpfunc_impl; + +static int cx_pl_cmpfunc( + void const *l, + void const *r +) { + void *const *lptr = l; + void *const *rptr = r; + void const *left = lptr == NULL ? NULL : *lptr; + void const *right = rptr == NULL ? NULL : *rptr; + return cx_pl_cmpfunc_impl(left, right); +} + +static void cx_pl_hack_cmpfunc(struct cx_list_s const *list) { + // cast away const - this is the hacky thing + struct cx_list_s *l = (struct cx_list_s *) list; + cx_pl_cmpfunc_impl = l->cmpfunc; + l->cmpfunc = cx_pl_cmpfunc; +} + +static void cx_pl_unhack_cmpfunc(struct cx_list_s const *list) { + // cast away const - this is the hacky thing + struct cx_list_s *l = (struct cx_list_s *) list; + l->cmpfunc = cx_pl_cmpfunc_impl; +} + +static void cx_pl_destructor(struct cx_list_s *list) { + list->climpl->destructor(list); +} + +static int cx_pl_insert_element( + struct cx_list_s *list, + size_t index, + void const *element +) { + return list->climpl->insert_element(list, index, &element); +} + +static size_t cx_pl_insert_array( + struct cx_list_s *list, + size_t index, + void const *array, + size_t n +) { + return list->climpl->insert_array(list, index, array, n); +} + +static int cx_pl_insert_iter( + struct cx_mut_iterator_s *iter, + void const *elem, + int prepend +) { + struct cx_list_s *list = iter->src_handle; + return list->climpl->insert_iter(iter, &elem, prepend); +} + +static int cx_pl_remove( + struct cx_list_s *list, + size_t index +) { + return list->climpl->remove(list, index); +} + +static void *cx_pl_at( + struct cx_list_s const *list, + size_t index +) { + void **ptr = list->climpl->at(list, index); + return ptr == NULL ? NULL : *ptr; +} + +static size_t cx_pl_find( + struct cx_list_s const *list, + void const *elem +) { + cx_pl_hack_cmpfunc(list); + size_t ret = list->climpl->find(list, &elem); + cx_pl_unhack_cmpfunc(list); + return ret; +} + +static void cx_pl_sort(struct cx_list_s *list) { + cx_pl_hack_cmpfunc(list); + list->climpl->sort(list); + cx_pl_unhack_cmpfunc(list); +} + +static int cx_pl_compare( + struct cx_list_s const *list, + struct cx_list_s const *other +) { + cx_pl_hack_cmpfunc(list); + int ret = list->climpl->compare(list, other); + cx_pl_unhack_cmpfunc(list); + return ret; +} + +static void cx_pl_reverse(struct cx_list_s *list) { + list->climpl->reverse(list); +} + +static void *cx_pl_iter_current(void const *it) { + struct cx_iterator_s const *iter = it; + void **ptr = iter->base.current_impl(it); + return ptr == NULL ? NULL : *ptr; +} + +static struct cx_iterator_s cx_pl_iterator( + struct cx_list_s const *list, + size_t index +) { + struct cx_iterator_s iter = list->climpl->iterator(list, index); + iter.base.current_impl = iter.base.current; + iter.base.current = cx_pl_iter_current; + return iter; +} + +static cx_list_class cx_pointer_list_class = { + cx_pl_destructor, + cx_pl_insert_element, + cx_pl_insert_array, + cx_pl_insert_iter, + cx_pl_remove, + cx_pl_at, + cx_pl_find, + cx_pl_sort, + cx_pl_compare, + cx_pl_reverse, + cx_pl_iterator, +}; + +void cxListStoreObjects(CxList *list) { + if (list->climpl != NULL) { + list->cl = list->climpl; + list->climpl = NULL; + } +} + +void cxListStorePointers(CxList *list) { + list->itemsize = sizeof(void *); + list->climpl = list->cl; + list->cl = &cx_pointer_list_class; +} + +bool cxListIsStoringPointers(CxList *list) { + return list->climpl != NULL; +} + +// + void cxListDestroy(CxList *list) { switch (list->content_destructor_type) { case CX_DESTRUCTOR_SIMPLE: { diff -r 55cc3b373c5e -r d402fead3386 test/test_list.cpp --- a/test/test_list.cpp Wed Jan 25 19:19:29 2023 +0100 +++ b/test/test_list.cpp Thu Jan 26 20:59:36 2023 +0100 @@ -573,6 +573,14 @@ return list; } + auto pointerLinkedListFromTestData() const -> CxList * { + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *))); + cxListStorePointers(list); + // note: cannot use cxListAddArray() because we don't have a list of pointers + cx_for_n(i, testdata_len) cxListAdd(list, &testdata.data[i]); + return list; + } + auto arrayListFromTestData() const -> CxList * { auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), testdata_len)); cxListAddArray(list, testdata.data.data(), testdata_len); @@ -625,21 +633,37 @@ EXPECT_EQ(*(int *) cxListAt(list, 3), 42); } - static void verifyInsertArray(CxList *list) { + static void verifyInsertArray( + CxList *list, + bool pointers = false + ) { int a[5] = {5, 47, 11, 13, 42}; int b[5] = {9, 18, 72, 50, 7}; + int *aptr[5]; + int *bptr[5]; + cx_for_n(i, 5) { + aptr[i] = &a[i]; + bptr[i] = &b[i]; + } size_t inserted; - inserted = cxListInsertArray(list, 0, a, 5); + if (pointers) { + inserted = cxListInsertArray(list, 0, aptr, 5); + } else { + inserted = cxListInsertArray(list, 0, a, 5); + } EXPECT_EQ(inserted, 5); EXPECT_EQ(*(int *) cxListAt(list, 0), 5); EXPECT_EQ(*(int *) cxListAt(list, 1), 47); EXPECT_EQ(*(int *) cxListAt(list, 2), 11); EXPECT_EQ(*(int *) cxListAt(list, 3), 13); EXPECT_EQ(*(int *) cxListAt(list, 4), 42); - - inserted = cxListInsertArray(list, 3, b, 5); + if (pointers) { + inserted = cxListInsertArray(list, 3, bptr, 5); + } else { + inserted = cxListInsertArray(list, 3, b, 5); + } EXPECT_EQ(inserted, 5); EXPECT_EQ(*(int *) cxListAt(list, 0), 5); EXPECT_EQ(*(int *) cxListAt(list, 1), 47); @@ -787,9 +811,26 @@ class LinkedList : public HighLevelTest { }; +class PointerLinkedList : public HighLevelTest { +}; + class ArrayList : public HighLevelTest { }; +TEST_F(PointerLinkedList, cxListStorePointers) { + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, 47)); + EXPECT_FALSE(cxListIsStoringPointers(list)); + cxListStorePointers(list); + EXPECT_EQ(list->itemsize, sizeof(void *)); + EXPECT_NE(list->cl, nullptr); + EXPECT_NE(list->climpl, nullptr); + EXPECT_TRUE(cxListIsStoringPointers(list)); + cxListStoreObjects(list); + EXPECT_NE(list->cl, nullptr); + EXPECT_EQ(list->climpl, nullptr); + EXPECT_FALSE(cxListIsStoringPointers(list)); +} + TEST_F(LinkedList, cxLinkedListCreate) { CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))); ASSERT_NE(list, nullptr); @@ -807,12 +848,18 @@ } TEST_F(LinkedList, cxListAdd) { - CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))); + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))); verifyAdd(list, false); } +TEST_F(PointerLinkedList, cxListAdd) { + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *))); + cxListStorePointers(list); + verifyAdd(list, true); +} + TEST_F(ArrayList, cxListAdd) { - CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8)); + auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8)); verifyAdd(list, false); } @@ -820,6 +867,12 @@ verifyInsert(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)))); } +TEST_F(PointerLinkedList, cxListInsert) { + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *))); + cxListStorePointers(list); + verifyInsert(list); +} + TEST_F(ArrayList, cxListInsert) { verifyInsert(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 2))); } @@ -828,6 +881,12 @@ verifyInsertArray(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)))); } +TEST_F(PointerLinkedList, cxListInsertArray) { + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *))); + cxListStorePointers(list); + verifyInsertArray(list, true); +} + TEST_F(ArrayList, cxListInsertArray) { verifyInsertArray(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 4))); } @@ -836,6 +895,10 @@ verifyRemove(linkedListFromTestData()); } +TEST_F(PointerLinkedList, cxListRemove) { + verifyRemove(pointerLinkedListFromTestData()); +} + TEST_F(ArrayList, cxListRemove) { verifyRemove(arrayListFromTestData()); } @@ -844,6 +907,10 @@ verifyAt(linkedListFromTestData()); } +TEST_F(PointerLinkedList, cxListAt) { + verifyAt(pointerLinkedListFromTestData()); +} + TEST_F(ArrayList, cxListAt) { verifyAt(arrayListFromTestData()); } @@ -852,6 +919,10 @@ verifyFind(linkedListFromTestData()); } +TEST_F(PointerLinkedList, cxListFind) { + verifyFind(pointerLinkedListFromTestData()); +} + TEST_F(ArrayList, cxListFind) { verifyFind(arrayListFromTestData()); } @@ -860,6 +931,10 @@ verifySort(linkedListFromTestData()); } +TEST_F(PointerLinkedList, cxListSort) { + verifySort(pointerLinkedListFromTestData()); +} + TEST_F(ArrayList, cxListSort) { verifySort(arrayListFromTestData()); } @@ -868,6 +943,10 @@ verifyIterator(linkedListFromTestData()); } +TEST_F(PointerLinkedList, Iterator) { + verifyIterator(pointerLinkedListFromTestData()); +} + TEST_F(ArrayList, Iterator) { verifyIterator(arrayListFromTestData()); } @@ -879,6 +958,15 @@ verifyInsertViaIterator(list); } +TEST_F(PointerLinkedList, InsertViaIterator) { + int fivenums[] = {0, 1, 2, 3, 4, 5}; + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *))); + cxListStorePointers(list); + // note: cannot use cxListAddArray() because we don't have a list of pointers + cx_for_n(i, 5) cxListAdd(list, &fivenums[i]); + verifyInsertViaIterator(list); +} + TEST_F(ArrayList, InsertViaIterator) { int fivenums[] = {0, 1, 2, 3, 4, 5}; CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 4)); @@ -890,6 +978,10 @@ verifyReverse(linkedListFromTestData()); } +TEST_F(PointerLinkedList, cxListReverse) { + verifyReverse(pointerLinkedListFromTestData()); +} + TEST_F(ArrayList, cxListReverse) { verifyReverse(arrayListFromTestData()); } @@ -900,20 +992,86 @@ verifyCompare(left, right); } +TEST_F(LinkedList, cxListCompareWithPtrList) { + auto left = linkedListFromTestData(); + auto right = pointerLinkedListFromTestData(); + verifyCompare(left, right); +} + TEST_F(LinkedList, cxListCompareWithArrayList) { auto left = linkedListFromTestData(); auto right = arrayListFromTestData(); verifyCompare(left, right); } +TEST_F(PointerLinkedList, cxListCompare) { + auto left = pointerLinkedListFromTestData(); + auto right = pointerLinkedListFromTestData(); + verifyCompare(left, right); +} + +TEST_F(PointerLinkedList, cxListCompareWithNormalList) { + auto left = pointerLinkedListFromTestData(); + auto right = linkedListFromTestData(); + verifyCompare(left, right); +} + +TEST_F(PointerLinkedList, cxListCompareWithArrayList) { + auto left = pointerLinkedListFromTestData(); + auto right = arrayListFromTestData(); + verifyCompare(left, right); +} + TEST_F(ArrayList, cxListCompare) { auto left = arrayListFromTestData(); auto right = arrayListFromTestData(); verifyCompare(left, right); } -TEST_F(ArrayList, cxListCompareWithLinkedList) { +TEST_F(ArrayList, cxListCompareWithPtrList) { + auto left = arrayListFromTestData(); + auto right = pointerLinkedListFromTestData(); + verifyCompare(left, right); +} + +TEST_F(ArrayList, cxListCompareWithNormalList) { auto left = arrayListFromTestData(); auto right = linkedListFromTestData(); verifyCompare(left, right); } + +TEST_F(PointerLinkedList, NoDestructor) { + void *item = cxMalloc(&testingAllocator, sizeof(int)); + auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int *)); + cxListStorePointers(list); + cxListAdd(list, item); + ASSERT_FALSE(testingAllocator.verify()); + cxListDestroy(list); + EXPECT_FALSE(testingAllocator.verify()); + cxFree(&testingAllocator, item); + EXPECT_TRUE(testingAllocator.verify()); +} + +TEST_F(PointerLinkedList, SimpleDestructor) { + int item = 0; + auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int *)); + cxListStorePointers(list); + list->content_destructor_type = CX_DESTRUCTOR_SIMPLE; + list->simple_destructor = [](void *elem) { *(int *) elem = 42; }; + cxListAdd(list, &item); + cxListDestroy(list); + EXPECT_EQ(item, 42); +} + +TEST_F(PointerLinkedList, AdvancedDestructor) { + void *item = cxMalloc(&testingAllocator, sizeof(int)); + auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int *)); + cxListStorePointers(list); + list->content_destructor_type = CX_DESTRUCTOR_ADVANCED; + list->advanced_destructor.data = &testingAllocator; + list->advanced_destructor.func = (cx_destructor_func2) cxFree; + cxListAdd(list, item); + ASSERT_FALSE(testingAllocator.verify()); + cxListDestroy(list); + EXPECT_TRUE(testingAllocator.verify()); +}