# HG changeset patch # User Mike Becker # Date 1633715251 -7200 # Node ID 1bd4b8c28722aeda462d3b7761c2655913dacc75 # Parent 18f964adad1b31216ca0791e78c2b56ec063103f add cx_linked_list_{prev, remove, reverse} changes assertions for some low level methods (loc_next is now always mandatory) diff -r 18f964adad1b -r 1bd4b8c28722 src/cx/linked_list.h --- a/src/cx/linked_list.h Fri Oct 08 18:58:49 2021 +0200 +++ b/src/cx/linked_list.h Fri Oct 08 19:47:31 2021 +0200 @@ -110,6 +110,18 @@ void *cx_linked_list_last(void *begin, ptrdiff_t loc_next); /** + * Finds the predecessor of a node in case it is not linked. + * + * \remark If \p node is not contained in the list starting with \p begin, the behavior is undefined. + * + * @param begin the node where to start the search + * @param loc_next the location of the \c next pointer + * @param node the successor of the node to find + * @return the node or \c NULL if \p node has no predecessor + */ +void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node); + +/** * Adds a new node to a linked list. * * \remark One of the pointers \p begin and \p end may be \c NULL, but not both. @@ -117,12 +129,38 @@ * @param begin a pointer to the begin node pointer (if your list has one) * @param end a pointer to the end node pointer (if your list has one) * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) - * @param loc_next the location of a \c next pointer within your node struct (negative if your struct does not have one) + * @param loc_next the location of a \c next pointer within your node struct (required) * @param new_node a pointer to the node that shall be appended */ void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node); /** + * Removes a node from the linked list. + * + * If the node to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end) + * addresses are provided, the pointers are adjusted accordingly. + * + * The following combinations of arguments are valid (more arguments are optional): + * \li \p loc_next and \p loc_prev + * \li \p loc_next and \p begin + * + * This function returns an adjacent node according to the following rules: + * \li if the node has only one adjacent node, that one is returned + * \li otherwise, the former \c prev node is returned + * + * \remark The \c next and \c prev pointers of the removed node are cleared by this function. + * + * @param begin a pointer to the begin node pointer (optional) + * @param end a pointer to the end node pointer (optional) + * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) + * @param loc_next the location of a \c next pointer within your node struct (required) + * @param node the node to remove + * @return an adjacent node or \c NULL, if this was the last node + */ +void *cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node); + + +/** * Determines the size of a linked list starting with \p node. * @param node the first node * @param loc_next the location of the \c next pointer within the node struct @@ -162,6 +200,17 @@ void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func); + +/** + * Reverses the order of the nodes in a linked list. + * + * @param begin a pointer to the begin node pointer (required) + * @param end a pointer to the end node pointer (optional) + * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) + * @param loc_next the location of a \c next pointer within your node struct (required) + */ +void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next); + #ifdef __cplusplus } /* extern "C" */ #endif diff -r 18f964adad1b -r 1bd4b8c28722 src/linked_list.c --- a/src/linked_list.c Fri Oct 08 18:58:49 2021 +0200 +++ b/src/linked_list.c Fri Oct 08 19:47:31 2021 +0200 @@ -36,6 +36,8 @@ #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) { + assert(start != NULL); + assert(loc_advance >= 0); size_t i = start_index; void *cur = start; while (i != index && cur != NULL) { @@ -46,6 +48,7 @@ } void *cx_linked_list_last(void *begin, ptrdiff_t loc_next) { + assert(loc_next >= 0); if (begin == NULL) return NULL; @@ -58,7 +61,21 @@ return last; } +void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node) { + assert(begin != NULL); + assert(loc_next >= 0); + if (begin == node) return NULL; + void *cur = begin; + void *next; + while (1) { + next = CX_LL_PTR(cur, loc_next); + if (next == node) return cur; + cur = next; + } +} + void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) { + assert(loc_next >= 0); void *last; if (end == NULL) { assert(begin != NULL); @@ -85,7 +102,48 @@ } } +void *cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) { + assert(loc_next >= 0); + assert(loc_prev >= 0 || begin != NULL); + + // find adjacent nodes + void *next = CX_LL_PTR(node, loc_next); + void *prev; + if (loc_prev >= 0) { + prev = CX_LL_PTR(node, loc_prev); + } else { + prev = cx_linked_list_prev(*begin, loc_next, node); + } + + // update links of adjacent nodes + if (prev != NULL) { + CX_LL_PTR(prev, loc_next) = next; + } + if (next != NULL && loc_prev >= 0) { + CX_LL_PTR(next, loc_prev) = prev; + } + + // erase links of the target node + CX_LL_PTR(node, loc_next) = NULL; + if (loc_prev >= 0) { + CX_LL_PTR(node, loc_prev) = NULL; + } + + // update begin, if required + if (*begin == node) { + *begin = next; + } + + // update end, if required + if (end != NULL && *end == node) { + *end = prev; + } + + return prev == NULL ? next : prev; +} + size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) { + assert(loc_next >= 0); size_t size = 0; while (node != NULL) { node = CX_LL_PTR(node, loc_next); @@ -149,6 +207,9 @@ void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) { assert(begin != NULL); + assert(loc_next >= 0); + assert(loc_data >= 0); + assert(cmp_func); void *lc, *ls, *le, *re; @@ -201,6 +262,32 @@ #undef ll_next #undef ll_data +void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) { + assert(begin != NULL); + assert(loc_next >= 0); + + // swap all links + void *prev = NULL; + void *cur = *begin; + while (cur != NULL) { + void *next = CX_LL_PTR(cur, loc_next); + + CX_LL_PTR(cur, loc_next) = prev; + if (loc_prev >= 0) { + CX_LL_PTR(cur, loc_prev) = next; + } + + prev = cur; + cur = next; + } + + // update begin and end + if (end != NULL) { + *end = *begin; + } + *begin = prev; +} + /* HIGH LEVEL LINKED LIST IMPLEMENTATION */ typedef struct cx_linked_list_node cx_linked_list_node; diff -r 18f964adad1b -r 1bd4b8c28722 test/test_list.c --- a/test/test_list.c Fri Oct 08 18:58:49 2021 +0200 +++ b/test/test_list.c Fri Oct 08 19:47:31 2021 +0200 @@ -128,7 +128,6 @@ } void test_linked_list_last(void) { - CU_ASSERT_PTR_NULL(cx_linked_list_last(NULL, -1)) CU_ASSERT_PTR_NULL(cx_linked_list_last(NULL, 0)) struct node { @@ -146,6 +145,97 @@ CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&third, loc), &third) } +void test_linked_list_prev(void) { + struct node { + void *next; + }; + ptrdiff_t loc = offsetof(struct node, next); + + struct node third = {NULL}; + struct node second = {&third}; + struct node first = {&second}; + + CU_ASSERT_PTR_NULL(cx_linked_list_prev(&first, loc, &first)) + CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &second), &first) + CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &third), &second) +} + +void test_linked_list_remove(void) { + struct node { + void *next; + }; + struct dnode { + void *next; + void *prev; + }; + ptrdiff_t loc = offsetof(struct node, next); + ptrdiff_t ploc = offsetof(struct dnode, prev); + + void *begin; + void *end; + void *result; + + // single linked list + struct node third = {NULL}; + struct node second = {&third}; + struct node first = {&second}; + begin = &first; + + result = cx_linked_list_remove(&begin, NULL, -1, loc, &second); + CU_ASSERT_PTR_EQUAL(result, &first) + CU_ASSERT_PTR_EQUAL(begin, &first) + CU_ASSERT_PTR_EQUAL(first.next, &third) + CU_ASSERT_PTR_NULL(second.next) + CU_ASSERT_PTR_NULL(third.next) + + result = cx_linked_list_remove(&begin, NULL, -1, loc, &first); + CU_ASSERT_PTR_EQUAL(result, &third) + CU_ASSERT_PTR_EQUAL(begin, &third) + CU_ASSERT_PTR_NULL(first.next) + CU_ASSERT_PTR_NULL(third.next) + + result = cx_linked_list_remove(&begin, NULL, -1, loc, &third); + CU_ASSERT_PTR_NULL(result) + CU_ASSERT_PTR_NULL(begin) + CU_ASSERT_PTR_NULL(third.next) + + // doubly linked list + struct dnode dthird = {NULL , NULL}; + struct dnode dsecond = {&dthird, NULL}; + struct dnode dfirst = {&dsecond, NULL}; + dthird.prev = &dsecond; + dsecond.prev = &dfirst; + begin = &dfirst; + end = &dthird; + + result = cx_linked_list_remove(&begin, &end, ploc, loc, &dsecond); + CU_ASSERT_PTR_EQUAL(result, &dfirst) + CU_ASSERT_PTR_EQUAL(begin, &dfirst) + CU_ASSERT_PTR_EQUAL(end, &dthird) + CU_ASSERT_PTR_NULL(dfirst.prev) + CU_ASSERT_PTR_EQUAL(dfirst.next, &dthird) + CU_ASSERT_PTR_NULL(dsecond.prev) + CU_ASSERT_PTR_NULL(dsecond.next) + CU_ASSERT_PTR_EQUAL(dthird.prev, &dfirst) + CU_ASSERT_PTR_NULL(dthird.next) + + result = cx_linked_list_remove(&begin, &end, ploc, loc, &dthird); + CU_ASSERT_PTR_EQUAL(result, &dfirst) + CU_ASSERT_PTR_EQUAL(begin, &dfirst) + CU_ASSERT_PTR_EQUAL(end, &dfirst) + CU_ASSERT_PTR_NULL(dfirst.prev) + CU_ASSERT_PTR_NULL(dfirst.next) + CU_ASSERT_PTR_NULL(dthird.prev) + CU_ASSERT_PTR_NULL(dthird.next) + + result = cx_linked_list_remove(&begin, &end, ploc, loc, &dfirst); + CU_ASSERT_PTR_NULL(result) + CU_ASSERT_PTR_NULL(begin) + CU_ASSERT_PTR_NULL(end) + CU_ASSERT_PTR_NULL(dfirst.next) + CU_ASSERT_PTR_NULL(dfirst.prev) +} + void test_linked_list_size(void) { struct node { void *next; @@ -209,7 +299,7 @@ CU_ASSERT_EQUAL(begin->data, expected[0]) struct node *check = begin; struct node *check_last = NULL; - for (int i = 0 ; i < 100 ; i++) { + for (int i = 0; i < 100; i++) { CU_ASSERT_EQUAL(check->data, expected[i]) CU_ASSERT_PTR_EQUAL(check->prev, check_last) if (i < 99) { @@ -222,6 +312,51 @@ CU_ASSERT_EQUAL(end->data, expected[99]) } +void test_linked_list_reverse(void) { + struct node { + void *next; + }; + struct dnode { + void *next; + void *prev; + }; + ptrdiff_t loc = offsetof(struct node, next); + ptrdiff_t ploc = offsetof(struct dnode, prev); + + void *begin; + void *end; + + // single linked list + struct node third = {NULL}; + struct node second = {&third}; + struct node first = {&second}; + begin = &first; + + cx_linked_list_reverse(&begin, NULL, -1, loc); + CU_ASSERT_PTR_EQUAL(begin, &third) + CU_ASSERT_PTR_EQUAL(third.next, &second) + CU_ASSERT_PTR_EQUAL(second.next, &first) + CU_ASSERT_PTR_NULL(first.next) + + // doubly linked list + struct dnode dthird = {NULL , NULL}; + struct dnode dsecond = {&dthird, NULL}; + struct dnode dfirst = {&dsecond, NULL}; + dthird.prev = &dsecond; + dsecond.prev = &dfirst; + begin = &dfirst; + end = &dthird; + + cx_linked_list_reverse(&begin, &end, ploc, loc); + CU_ASSERT_PTR_EQUAL(begin, &dthird) + CU_ASSERT_PTR_EQUAL(end, &dfirst) + CU_ASSERT_PTR_EQUAL(dthird.next, &dsecond) + CU_ASSERT_PTR_EQUAL(dsecond.next, &dfirst) + CU_ASSERT_PTR_NULL(dfirst.next) + CU_ASSERT_PTR_NULL(dthird.prev) + CU_ASSERT_PTR_EQUAL(dsecond.prev, &dthird) + CU_ASSERT_PTR_EQUAL(dfirst.prev, &dsecond) +} void test_hl_linked_list_create(void) { cxTestingAllocatorReset(); @@ -415,14 +550,14 @@ CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int)); - for (int i = 0 ; i < 100 ; i++) { + for (int i = 0; i < 100; i++) { cxListAdd(list, &scrambled[i]); } cxListSort(list); - for (int i = 0 ; i < 100 ; i++) { - CU_ASSERT_EQUAL(*(int*)cxListAt(list, i), expected[i]) + for (int i = 0; i < 100; i++) { + CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i]) } cxLinkedListDestroy(list); @@ -616,14 +751,14 @@ CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int); - for (int i = 0 ; i < 100 ; i++) { + for (int i = 0; i < 100; i++) { cxListAdd(list, &scrambled[i]); } cxListSort(list); - for (int i = 0 ; i < 100 ; i++) { - CU_ASSERT_EQUAL(*(int*)cxListAt(list, i), expected[i]) + for (int i = 0; i < 100; i++) { + CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i]) } cxLinkedListDestroy(list); @@ -642,8 +777,11 @@ cu_add_test(suite, test_linked_list_at); cu_add_test(suite, test_linked_list_add); cu_add_test(suite, test_linked_list_last); + cu_add_test(suite, test_linked_list_prev); + cu_add_test(suite, test_linked_list_remove); cu_add_test(suite, test_linked_list_size); cu_add_test(suite, test_linked_list_sort); + cu_add_test(suite, test_linked_list_reverse); suite = CU_add_suite("high level linked list", NULL, NULL);