Mercurial > hg > ucx / changeset

--- a/src/cx/linked_list.h	Mon Sep 27 17:49:23 2021 +0200
+++ b/src/cx/linked_list.h	Mon Sep 27 18:33:30 2021 +0200
@@ -36,6 +36,25 @@
 extern "C" {
 #endif
 
+/**
+ * Finds the node at a certain index.
+ *
+ * This function can be used to start at an arbitrary position within the list.
+ * If the search index is large than the start index, \p loc_advance must denote
+ * the location of some sort of \c next pointer (i.e. a pointer to the next node).
+ * But it is also possible that the search index is smaller than the start index
+ * (e.g. in cases where traversing a list backwards is faster) in which case
+ * \p loc_advance must denote the location of some sort of \c prev pointer
+ * (i.e. a pointer to the previous node).
+ *
+ * @param start a pointer to the start node
+ * @param start_index the start index
+ * @param loc_advance the location of the pointer to advance
+ * @param index the search index
+ * @return the node found at the specified index
+ */
+void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index);
+
 void *cx_linked_list_last(void **begin, void **end, ptrdiff_t loc_next);
 
 int cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);

--- a/src/cx/list.h	Mon Sep 27 17:49:23 2021 +0200
+++ b/src/cx/list.h	Mon Sep 27 18:33:30 2021 +0200
@@ -45,7 +45,7 @@
 
     int (*insert)(cx_list_s *list, size_t index, void *elem);
 
-    void *(*remove)(cx_list_s *list, size_t index);
+    int (*remove)(cx_list_s *list, size_t index);
 
     size_t (*find)(cx_list_s *list, void *elem);
 
@@ -67,7 +67,7 @@
 
 int cxListInsert(CxList list, size_t index, void *elem);
 
-void *cxListRemove(CxList list, size_t index);
+int cxListRemove(CxList list, size_t index);
 
 size_t cxListFind(CxList list, void *elem);
 

--- a/src/linked_list.c	Mon Sep 27 17:49:23 2021 +0200
+++ b/src/linked_list.c	Mon Sep 27 18:33:30 2021 +0200
@@ -34,6 +34,16 @@
 
 #define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off))
 
+void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
+    size_t i = start_index;
+    void* cur = start;
+    while (i != index && cur != NULL) {
+        cur = *CX_LL_PTR(cur, loc_advance);
+        i < index ? i++ : i--;
+    }
+    return cur;
+}
+
 void *cx_linked_list_last(void **begin, void **end, ptrdiff_t loc_next) {
     if (end != NULL) {
         return *end;
@@ -97,7 +107,7 @@
     ptrdiff_t loc_next;
 } cx_linked_list;
 
-int cx_ll_add(cx_list_s *list, void *elem) {
+static int cx_ll_add(cx_list_s *list, void *elem) {
     cx_linked_list *ll = (cx_linked_list *) list;
 
     struct cx_linked_list_node *node = cxMalloc(list->allocator,
@@ -122,19 +132,22 @@
     }
 }
 
-int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
+static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
     cx_linked_list *ll = (cx_linked_list *) list;
     // TODO: implement using low level API
     return 1;
 }
 
-void *cx_ll_remove(cx_list_s *list, size_t index) {
+static int cx_ll_remove(cx_list_s *list, size_t index) {
+    if (index >= list->size) {
+        return 1;
+    }
     cx_linked_list *ll = (cx_linked_list *) list;
     // TODO: implement using low level API
-    return NULL;
+    return 0;
 }
 
-size_t cx_ll_find(cx_list_s *list, void *elem) {
+static size_t cx_ll_find(cx_list_s *list, void *elem) {
     CxListComparator cmp = list->cmpfunc;
     cx_linked_list *ll = (cx_linked_list *) list;
 
@@ -150,7 +163,7 @@
     return index;
 }
 
-void *cx_ll_last(cx_list_s *list) {
+static void *cx_ll_last(cx_list_s *list) {
     cx_linked_list *linkedList = (cx_linked_list *) list;
     struct cx_linked_list_node *last = cx_linked_list_last(
             NULL, &linkedList->end, offsetof(struct cx_linked_list_node, next));

--- a/src/list.c	Mon Sep 27 17:49:23 2021 +0200
+++ b/src/list.c	Mon Sep 27 18:33:30 2021 +0200
@@ -36,7 +36,7 @@
     return list->cl->insert(list, index, elem);
 }
 
-void *cxListRemove(CxList list, size_t index) {
+int cxListRemove(CxList list, size_t index) {
     return list->cl->remove(list, index);
 }
 

--- a/test/test_list.c	Mon Sep 27 17:49:23 2021 +0200
+++ b/test/test_list.c	Mon Sep 27 18:33:30 2021 +0200
@@ -35,7 +35,7 @@
     return left == right ? 0 : (left < right ? -1 : 1);
 }
 
-void test_linked_list_create() {
+void test_linked_list_create(void) {
     cxTestingAllocatorReset();
 
     CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
@@ -66,6 +66,40 @@
     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
 }
 
+void test_linked_list_at(void) {
+    struct node {
+        void *next;
+        void *prev;
+    };
+    const ptrdiff_t loc_prev = offsetof(struct node, prev);
+    const ptrdiff_t loc_next = offsetof(struct node, next);
+
+    struct node a, b, c, d;
+    a.prev = NULL;
+    a.next = &b;
+    b.prev = &a;
+    b.next = &c;
+    c.prev = &b;
+    c.next = &d;
+    d.prev = &c;
+    d.next = NULL;
+
+    CU_ASSERT_PTR_EQUAL(&a, cx_linked_list_at(&a, 0, loc_next, 0));
+    CU_ASSERT_PTR_EQUAL(&b, cx_linked_list_at(&a, 0, loc_next, 1));
+    CU_ASSERT_PTR_EQUAL(&c, cx_linked_list_at(&a, 0, loc_next, 2));
+    CU_ASSERT_PTR_EQUAL(&d, cx_linked_list_at(&a, 0, loc_next, 3));
+    CU_ASSERT_PTR_NULL(cx_linked_list_at(&a, 0, loc_next, 4));
+
+    CU_ASSERT_PTR_EQUAL(&a, cx_linked_list_at(&b, 1, loc_prev, 0));
+    CU_ASSERT_PTR_EQUAL(&b, cx_linked_list_at(&b, 1, loc_next, 1));
+    CU_ASSERT_PTR_EQUAL(&c, cx_linked_list_at(&b, 1, loc_next, 2));
+    CU_ASSERT_PTR_EQUAL(&d, cx_linked_list_at(&b, 1, loc_next, 3));
+    CU_ASSERT_PTR_NULL(cx_linked_list_at(&b, 1, loc_next, 4));
+
+    CU_ASSERT_PTR_EQUAL(&a, cx_linked_list_at(&d, 3, loc_prev, 0));
+    CU_ASSERT_PTR_EQUAL(&b, cx_linked_list_at(&d, 3, loc_prev, 1));
+}
+
 int main() {
     CU_pSuite suite = NULL;
 
@@ -80,7 +114,8 @@
     }
 
     if (
-            !CU_add_test(suite, "create and destroy linked list", test_linked_list_create)
+            !CU_add_test(suite, "linked list: create and destroy", test_linked_list_create) ||
+            !CU_add_test(suite, "linked list: get node at index", test_linked_list_at)
             ) {
         CU_cleanup_registry();
         return CU_get_error();