# HG changeset patch # User Mike Becker # Date 1632760410 -7200 # Node ID cd3069757010b8ef41e13110bb20dbb826a94bd2 # Parent 9d4971ea062534928a4020f334ce110e1a7d48b1 add function cx_linked_list_at() This commit also makes glue functions static. diff -r 9d4971ea0625 -r cd3069757010 src/cx/linked_list.h --- 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); diff -r 9d4971ea0625 -r cd3069757010 src/cx/list.h --- 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); diff -r 9d4971ea0625 -r cd3069757010 src/linked_list.c --- 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)); diff -r 9d4971ea0625 -r cd3069757010 src/list.c --- 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); } diff -r 9d4971ea0625 -r cd3069757010 test/test_list.c --- 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();