Mercurial > hg > ucx / changeset

--- 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)

--- 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,

--- 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__))

--- 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

--- 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,

--- 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 <string.h>
 
+// <editor-fold desc="Store Pointers Functionality">
+
+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;
+}
+
+// </editor-fold>
+
 void cxListDestroy(CxList *list) {
     switch (list->content_destructor_type) {
         case CX_DESTRUCTOR_SIMPLE: {

--- 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());
+}