Mon, 27 Sep 2021 18:33:30 +0200
add function cx_linked_list_at()
This commit also makes glue functions static.
src/cx/linked_list.h | file | annotate | diff | comparison | revisions | |
src/cx/list.h | file | annotate | diff | comparison | revisions | |
src/linked_list.c | file | annotate | diff | comparison | revisions | |
src/list.c | file | annotate | diff | comparison | revisions | |
test/test_list.c | file | annotate | diff | comparison | revisions |
1.1 --- a/src/cx/linked_list.h Mon Sep 27 17:49:23 2021 +0200 1.2 +++ b/src/cx/linked_list.h Mon Sep 27 18:33:30 2021 +0200 1.3 @@ -36,6 +36,25 @@ 1.4 extern "C" { 1.5 #endif 1.6 1.7 +/** 1.8 + * Finds the node at a certain index. 1.9 + * 1.10 + * This function can be used to start at an arbitrary position within the list. 1.11 + * If the search index is large than the start index, \p loc_advance must denote 1.12 + * the location of some sort of \c next pointer (i.e. a pointer to the next node). 1.13 + * But it is also possible that the search index is smaller than the start index 1.14 + * (e.g. in cases where traversing a list backwards is faster) in which case 1.15 + * \p loc_advance must denote the location of some sort of \c prev pointer 1.16 + * (i.e. a pointer to the previous node). 1.17 + * 1.18 + * @param start a pointer to the start node 1.19 + * @param start_index the start index 1.20 + * @param loc_advance the location of the pointer to advance 1.21 + * @param index the search index 1.22 + * @return the node found at the specified index 1.23 + */ 1.24 +void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index); 1.25 + 1.26 void *cx_linked_list_last(void **begin, void **end, ptrdiff_t loc_next); 1.27 1.28 int cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
2.1 --- a/src/cx/list.h Mon Sep 27 17:49:23 2021 +0200 2.2 +++ b/src/cx/list.h Mon Sep 27 18:33:30 2021 +0200 2.3 @@ -45,7 +45,7 @@ 2.4 2.5 int (*insert)(cx_list_s *list, size_t index, void *elem); 2.6 2.7 - void *(*remove)(cx_list_s *list, size_t index); 2.8 + int (*remove)(cx_list_s *list, size_t index); 2.9 2.10 size_t (*find)(cx_list_s *list, void *elem); 2.11 2.12 @@ -67,7 +67,7 @@ 2.13 2.14 int cxListInsert(CxList list, size_t index, void *elem); 2.15 2.16 -void *cxListRemove(CxList list, size_t index); 2.17 +int cxListRemove(CxList list, size_t index); 2.18 2.19 size_t cxListFind(CxList list, void *elem); 2.20
3.1 --- a/src/linked_list.c Mon Sep 27 17:49:23 2021 +0200 3.2 +++ b/src/linked_list.c Mon Sep 27 18:33:30 2021 +0200 3.3 @@ -34,6 +34,16 @@ 3.4 3.5 #define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off)) 3.6 3.7 +void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) { 3.8 + size_t i = start_index; 3.9 + void* cur = start; 3.10 + while (i != index && cur != NULL) { 3.11 + cur = *CX_LL_PTR(cur, loc_advance); 3.12 + i < index ? i++ : i--; 3.13 + } 3.14 + return cur; 3.15 +} 3.16 + 3.17 void *cx_linked_list_last(void **begin, void **end, ptrdiff_t loc_next) { 3.18 if (end != NULL) { 3.19 return *end; 3.20 @@ -97,7 +107,7 @@ 3.21 ptrdiff_t loc_next; 3.22 } cx_linked_list; 3.23 3.24 -int cx_ll_add(cx_list_s *list, void *elem) { 3.25 +static int cx_ll_add(cx_list_s *list, void *elem) { 3.26 cx_linked_list *ll = (cx_linked_list *) list; 3.27 3.28 struct cx_linked_list_node *node = cxMalloc(list->allocator, 3.29 @@ -122,19 +132,22 @@ 3.30 } 3.31 } 3.32 3.33 -int cx_ll_insert(cx_list_s *list, size_t index, void *elem) { 3.34 +static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) { 3.35 cx_linked_list *ll = (cx_linked_list *) list; 3.36 // TODO: implement using low level API 3.37 return 1; 3.38 } 3.39 3.40 -void *cx_ll_remove(cx_list_s *list, size_t index) { 3.41 +static int cx_ll_remove(cx_list_s *list, size_t index) { 3.42 + if (index >= list->size) { 3.43 + return 1; 3.44 + } 3.45 cx_linked_list *ll = (cx_linked_list *) list; 3.46 // TODO: implement using low level API 3.47 - return NULL; 3.48 + return 0; 3.49 } 3.50 3.51 -size_t cx_ll_find(cx_list_s *list, void *elem) { 3.52 +static size_t cx_ll_find(cx_list_s *list, void *elem) { 3.53 CxListComparator cmp = list->cmpfunc; 3.54 cx_linked_list *ll = (cx_linked_list *) list; 3.55 3.56 @@ -150,7 +163,7 @@ 3.57 return index; 3.58 } 3.59 3.60 -void *cx_ll_last(cx_list_s *list) { 3.61 +static void *cx_ll_last(cx_list_s *list) { 3.62 cx_linked_list *linkedList = (cx_linked_list *) list; 3.63 struct cx_linked_list_node *last = cx_linked_list_last( 3.64 NULL, &linkedList->end, offsetof(struct cx_linked_list_node, next));
4.1 --- a/src/list.c Mon Sep 27 17:49:23 2021 +0200 4.2 +++ b/src/list.c Mon Sep 27 18:33:30 2021 +0200 4.3 @@ -36,7 +36,7 @@ 4.4 return list->cl->insert(list, index, elem); 4.5 } 4.6 4.7 -void *cxListRemove(CxList list, size_t index) { 4.8 +int cxListRemove(CxList list, size_t index) { 4.9 return list->cl->remove(list, index); 4.10 } 4.11
5.1 --- a/test/test_list.c Mon Sep 27 17:49:23 2021 +0200 5.2 +++ b/test/test_list.c Mon Sep 27 18:33:30 2021 +0200 5.3 @@ -35,7 +35,7 @@ 5.4 return left == right ? 0 : (left < right ? -1 : 1); 5.5 } 5.6 5.7 -void test_linked_list_create() { 5.8 +void test_linked_list_create(void) { 5.9 cxTestingAllocatorReset(); 5.10 5.11 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int)); 5.12 @@ -66,6 +66,40 @@ 5.13 CU_ASSERT_TRUE(cxTestingAllocatorVerify()) 5.14 } 5.15 5.16 +void test_linked_list_at(void) { 5.17 + struct node { 5.18 + void *next; 5.19 + void *prev; 5.20 + }; 5.21 + const ptrdiff_t loc_prev = offsetof(struct node, prev); 5.22 + const ptrdiff_t loc_next = offsetof(struct node, next); 5.23 + 5.24 + struct node a, b, c, d; 5.25 + a.prev = NULL; 5.26 + a.next = &b; 5.27 + b.prev = &a; 5.28 + b.next = &c; 5.29 + c.prev = &b; 5.30 + c.next = &d; 5.31 + d.prev = &c; 5.32 + d.next = NULL; 5.33 + 5.34 + CU_ASSERT_PTR_EQUAL(&a, cx_linked_list_at(&a, 0, loc_next, 0)); 5.35 + CU_ASSERT_PTR_EQUAL(&b, cx_linked_list_at(&a, 0, loc_next, 1)); 5.36 + CU_ASSERT_PTR_EQUAL(&c, cx_linked_list_at(&a, 0, loc_next, 2)); 5.37 + CU_ASSERT_PTR_EQUAL(&d, cx_linked_list_at(&a, 0, loc_next, 3)); 5.38 + CU_ASSERT_PTR_NULL(cx_linked_list_at(&a, 0, loc_next, 4)); 5.39 + 5.40 + CU_ASSERT_PTR_EQUAL(&a, cx_linked_list_at(&b, 1, loc_prev, 0)); 5.41 + CU_ASSERT_PTR_EQUAL(&b, cx_linked_list_at(&b, 1, loc_next, 1)); 5.42 + CU_ASSERT_PTR_EQUAL(&c, cx_linked_list_at(&b, 1, loc_next, 2)); 5.43 + CU_ASSERT_PTR_EQUAL(&d, cx_linked_list_at(&b, 1, loc_next, 3)); 5.44 + CU_ASSERT_PTR_NULL(cx_linked_list_at(&b, 1, loc_next, 4)); 5.45 + 5.46 + CU_ASSERT_PTR_EQUAL(&a, cx_linked_list_at(&d, 3, loc_prev, 0)); 5.47 + CU_ASSERT_PTR_EQUAL(&b, cx_linked_list_at(&d, 3, loc_prev, 1)); 5.48 +} 5.49 + 5.50 int main() { 5.51 CU_pSuite suite = NULL; 5.52 5.53 @@ -80,7 +114,8 @@ 5.54 } 5.55 5.56 if ( 5.57 - !CU_add_test(suite, "create and destroy linked list", test_linked_list_create) 5.58 + !CU_add_test(suite, "linked list: create and destroy", test_linked_list_create) || 5.59 + !CU_add_test(suite, "linked list: get node at index", test_linked_list_at) 5.60 ) { 5.61 CU_cleanup_registry(); 5.62 return CU_get_error();