# HG changeset patch
# User Mike Becker <universe@uap-core.de>
# Date 1633431825 -7200
# Node ID 28bc3e10ac280db0e6dbeb873f6ea83b9655c1ca
# Parent  1e3cb39815f8beadc7b3184b8c9cc74a274bf672
add special linked list implementation for storing pointers

diff -r 1e3cb39815f8 -r 28bc3e10ac28 src/cx/linked_list.h
--- a/src/cx/linked_list.h	Tue Oct 05 12:25:23 2021 +0200
+++ b/src/cx/linked_list.h	Tue Oct 05 13:03:45 2021 +0200
@@ -45,8 +45,36 @@
 extern "C" {
 #endif
 
+/**
+ * Allocates a linked list for storing elements with \p item_size bytes each.
+ *
+ * Elements added to the list are copied.
+ *
+ * @param allocator the allocator for allocating the list nodes
+ * @param comparator the comparator for the elements
+ * @param item_size the size of each element in bytes
+ * @return the created list
+ */
 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size);
 
+/**
+ * Allocates a linked list for storing pointers.
+ *
+ * If you want to store the elements directly in this list, use cxLinkedListCreate().
+ *
+ * @param allocator the allocator for allocating the list nodes
+ * @param comparator the comparator for the elements
+ * @return the created list
+ */
+CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator);
+
+/**
+ * Deallocates the memory of the entire list.
+ *
+ * \attention If this is a pointer list, the memory the pointers are referring to is \em not freed.
+ *
+ * @param list the list
+ */
 void cxLinkedListDestroy(CxList list);
 
 size_t cxLinkedListRecalculateSize(CxList list);
diff -r 1e3cb39815f8 -r 28bc3e10ac28 src/linked_list.c
--- a/src/linked_list.c	Tue Oct 05 12:25:23 2021 +0200
+++ b/src/linked_list.c	Tue Oct 05 13:03:45 2021 +0200
@@ -172,6 +172,14 @@
     return cx_ll_insert(list, list->size, elem);
 }
 
+static int cx_pll_insert(cx_list_s *list, size_t index, void *elem) {
+    return cx_ll_insert(list, index, &elem);
+}
+
+static int cx_pll_add(cx_list_s *list, void *elem) {
+    return cx_ll_insert(list, list->size, &elem);
+}
+
 static int cx_ll_remove(cx_list_s *list, size_t index) {
     cx_linked_list *ll = (cx_linked_list *) list;
     cx_linked_list_node *node = cx_ll_node_at(ll, index);
@@ -205,7 +213,13 @@
 static void *cx_ll_at(cx_list_s *list, size_t index) {
     cx_linked_list *ll = (cx_linked_list *) list;
     cx_linked_list_node *node = cx_ll_node_at(ll, index);
-    return node == NULL ? NULL : &node->payload;
+    return node == NULL ? NULL : node->payload;
+}
+
+static void *cx_pll_at(cx_list_s *list, size_t index) {
+    cx_linked_list *ll = (cx_linked_list *) list;
+    cx_linked_list_node *node = cx_ll_node_at(ll, index);
+    return node == NULL ? NULL : *(void**)node->payload;
 }
 
 static size_t cx_ll_find(cx_list_s *list, void *elem) {
@@ -224,10 +238,32 @@
     return index;
 }
 
+static size_t cx_pll_find(cx_list_s *list, void *elem) {
+    CxListComparator cmp = list->cmpfunc;
+    cx_linked_list *ll = (cx_linked_list *) list;
+
+    size_t index;
+    cx_linked_list_node *node = ll->begin;
+    for (index = 0; index < list->size; index++) {
+        void *current = *(void**)node->payload;
+        if (cmp(current, elem) == 0) {
+            return index;
+        }
+        node = node->next;
+    }
+    return index;
+}
+
 static void *cx_ll_last(cx_list_s *list) {
     cx_linked_list *ll = (cx_linked_list *) list;
     cx_linked_list_node *last = ll->end;
-    return last == NULL ? NULL : &last->payload;
+    return last == NULL ? NULL : last->payload;
+}
+
+static void *cx_pll_last(cx_list_s *list) {
+    cx_linked_list *ll = (cx_linked_list *) list;
+    cx_linked_list_node *last = ll->end;
+    return last == NULL ? NULL : *(void**)last->payload;
 }
 
 static cx_list_class cx_linked_list_class = {
@@ -239,6 +275,15 @@
         cx_ll_last
 };
 
+static cx_list_class cx_pointer_linked_list_class = {
+        cx_pll_add,
+        cx_pll_insert,
+        cx_ll_remove,
+        cx_pll_at,
+        cx_pll_find,
+        cx_pll_last
+};
+
 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {
     cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
     if (list == NULL)
@@ -257,6 +302,24 @@
     return (CxList) list;
 }
 
+CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator) {
+    cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
+    if (list == NULL)
+        return NULL;
+
+    list->base.cl = &cx_pointer_linked_list_class;
+    list->base.allocator = allocator;
+    list->base.cmpfunc = comparator;
+    list->base.itemsize = sizeof(void*);
+    list->base.capacity = SIZE_MAX;
+    list->base.size = 0;
+
+    list->begin = NULL;
+    list->end = NULL;
+
+    return (CxList) list;
+}
+
 void cxLinkedListDestroy(CxList list) {
     cx_linked_list *ll = (cx_linked_list *) list;
 
diff -r 1e3cb39815f8 -r 28bc3e10ac28 test/test_list.c
--- a/test/test_list.c	Tue Oct 05 12:25:23 2021 +0200
+++ b/test/test_list.c	Tue Oct 05 13:03:45 2021 +0200
@@ -158,19 +158,7 @@
     CU_ASSERT_EQUAL(list->itemsize, sizeof(int))
     CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
 
-    // assume this structure for a linked list
-    struct ll_check {
-        cx_list_s base;
-        void *begin;
-        void *end;
-    };
-
-    struct ll_check *actual = (struct ll_check *) list;
-    CU_ASSERT_PTR_NULL(actual->begin)
-    CU_ASSERT_PTR_NULL(actual->end)
-
     cxLinkedListDestroy(list);
-
     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
 }
 
@@ -190,9 +178,9 @@
     CU_ASSERT_EQUAL(list->size, 3)
     CU_ASSERT_TRUE(list->capacity >= list->size)
 
-    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 0), 5)
-    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 1), 47)
-    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 2), 13)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
 
     cxLinkedListDestroy(list);
     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
@@ -208,11 +196,11 @@
 
     data = 5;
     CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
-    CU_ASSERT_EQUAL(*(int*)cxListLast(list), 5)
+    CU_ASSERT_EQUAL(*(int *) cxListLast(list), 5)
 
     data = 47;
     CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
-    CU_ASSERT_EQUAL(*(int*)cxListLast(list), 47)
+    CU_ASSERT_EQUAL(*(int *) cxListLast(list), 47)
 
     cxLinkedListDestroy(list);
     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
@@ -241,10 +229,10 @@
     CU_ASSERT_EQUAL(list->size, 4)
     CU_ASSERT_TRUE(list->capacity >= list->size)
 
-    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 0), 47)
-    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 1), 13)
-    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 2), 5)
-    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 3), 42)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
 
     cxLinkedListDestroy(list);
     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
@@ -273,20 +261,20 @@
     CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
     CU_ASSERT_EQUAL(list->size, 3)
     CU_ASSERT_TRUE(list->capacity >= list->size)
-    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 0), 5)
-    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 1), 47)
-    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 2), 13)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
 
     CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
     CU_ASSERT_EQUAL(list->size, 2)
     CU_ASSERT_TRUE(list->capacity >= list->size)
-    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 0), 47)
-    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 1), 13)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
 
     CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
     CU_ASSERT_EQUAL(list->size, 1)
     CU_ASSERT_TRUE(list->capacity >= list->size)
-    CU_ASSERT_EQUAL(*(int*)cxListAt(list, 0), 47)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
 
     CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
     CU_ASSERT_EQUAL(list->size, 0)
@@ -329,6 +317,171 @@
     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
 }
 
+void test_hl_ptr_linked_list_create(void) {
+    cxTestingAllocatorReset();
+
+    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
+
+    CU_ASSERT_EQUAL(list->size, 0)
+    CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
+    CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
+    CU_ASSERT_EQUAL(list->itemsize, sizeof(void *))
+    CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
+
+    cxLinkedListDestroy(list);
+    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
+}
+
+void test_hl_ptr_linked_list_add(void) {
+    cxTestingAllocatorReset();
+
+    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
+
+    int a = 5, b = 47, c = 13;
+
+    CU_ASSERT_EQUAL(cxListAdd(list, &a), 0)
+    CU_ASSERT_EQUAL(cxListAdd(list, &b), 0)
+    CU_ASSERT_EQUAL(cxListAdd(list, &c), 0)
+
+    CU_ASSERT_EQUAL(list->size, 3)
+    CU_ASSERT_TRUE(list->capacity >= list->size)
+
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
+
+    a = 9;
+    b = 10;
+    c = 11;
+
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 9)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 10)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 11)
+
+    cxLinkedListDestroy(list);
+    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
+}
+
+void test_hl_ptr_linked_list_last(void) {
+    cxTestingAllocatorReset();
+
+    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
+    CU_ASSERT_PTR_NULL(cxListLast(list))
+
+    int a = 5, b = 47;
+
+    CU_ASSERT_EQUAL(cxListAdd(list, &a), 0)
+    CU_ASSERT_EQUAL(*(int *) cxListLast(list), 5)
+    CU_ASSERT_EQUAL(cxListAdd(list, &b), 0)
+    CU_ASSERT_EQUAL(*(int *) cxListLast(list), 47)
+
+    cxLinkedListDestroy(list);
+    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
+}
+
+void test_hl_ptr_linked_list_insert(void) {
+    cxTestingAllocatorReset();
+
+    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
+
+    int a = 5, b = 47, c = 13, d = 42;
+
+    CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &a), 0)
+    CU_ASSERT_EQUAL(list->size, 0)
+    CU_ASSERT_EQUAL(cxListInsert(list, 0, &a), 0)
+    CU_ASSERT_EQUAL(list->size, 1)
+    CU_ASSERT_EQUAL(cxListInsert(list, 0, &b), 0)
+    CU_ASSERT_EQUAL(list->size, 2)
+    CU_ASSERT_EQUAL(cxListInsert(list, 1, &c), 0)
+    CU_ASSERT_EQUAL(list->size, 3)
+    CU_ASSERT_EQUAL(cxListInsert(list, 3, &d), 0)
+
+    CU_ASSERT_EQUAL(list->size, 4)
+    CU_ASSERT_TRUE(list->capacity >= list->size)
+
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
+
+    cxLinkedListDestroy(list);
+    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
+}
+
+void test_hl_ptr_linked_list_remove(void) {
+    cxTestingAllocatorReset();
+
+    int a = 5, b = 47, c = 42, d = 13;
+    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
+
+    cxListAdd(list, &a);
+    cxListAdd(list, &b);
+    cxListAdd(list, &c);
+    cxListAdd(list, &d);
+
+    CU_ASSERT_EQUAL(list->size, 4)
+    CU_ASSERT_TRUE(list->capacity >= list->size)
+
+    CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
+
+    CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
+    CU_ASSERT_EQUAL(list->size, 3)
+    CU_ASSERT_TRUE(list->capacity >= list->size)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
+
+    CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
+    CU_ASSERT_EQUAL(list->size, 2)
+    CU_ASSERT_TRUE(list->capacity >= list->size)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
+
+    CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
+    CU_ASSERT_EQUAL(list->size, 1)
+    CU_ASSERT_TRUE(list->capacity >= list->size)
+    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
+
+    CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
+    CU_ASSERT_EQUAL(list->size, 0)
+    CU_ASSERT_TRUE(list->capacity >= list->size)
+
+    CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
+
+    cxLinkedListDestroy(list);
+    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
+}
+
+void test_hl_ptr_linked_list_find(void) {
+    cxTestingAllocatorReset();
+
+    int a = 5, b = 47, c = 13, criteria;
+    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
+
+    cxListAdd(list, &a);
+    cxListAdd(list, &b);
+    cxListAdd(list, &c);
+
+    CU_ASSERT_EQUAL(list->size, 3)
+    CU_ASSERT_TRUE(list->capacity >= list->size)
+
+    criteria = 5;
+    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
+    criteria = 47;
+    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
+    criteria = 13;
+    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
+    criteria = 9000;
+    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
+    criteria = -5;
+    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
+    b = -5;
+    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
+
+    cxLinkedListDestroy(list);
+    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
+}
+
 int main() {
     CU_pSuite suite = NULL;
 
@@ -351,6 +504,15 @@
     cu_add_test(suite, test_hl_linked_list_remove);
     cu_add_test(suite, test_hl_linked_list_find);
 
+    suite = CU_add_suite("high level pointer linked list", NULL, NULL);
+
+    cu_add_test(suite, test_hl_ptr_linked_list_create);
+    cu_add_test(suite, test_hl_ptr_linked_list_add);
+    cu_add_test(suite, test_hl_ptr_linked_list_last);
+    cu_add_test(suite, test_hl_ptr_linked_list_insert);
+    cu_add_test(suite, test_hl_ptr_linked_list_remove);
+    cu_add_test(suite, test_hl_ptr_linked_list_find);
+
     CU_basic_set_mode(UCX_CU_BRM);
 
     int exitcode;