Fri, 08 Oct 2021 19:47:31 +0200
add cx_linked_list_{prev, remove, reverse}
changes assertions for some low level methods (loc_next is now always mandatory)
src/cx/linked_list.h | file | annotate | diff | comparison | revisions | |
src/linked_list.c | file | annotate | diff | comparison | revisions | |
test/test_list.c | file | annotate | diff | comparison | revisions |
1.1 --- a/src/cx/linked_list.h Fri Oct 08 18:58:49 2021 +0200 1.2 +++ b/src/cx/linked_list.h Fri Oct 08 19:47:31 2021 +0200 1.3 @@ -110,6 +110,18 @@ 1.4 void *cx_linked_list_last(void *begin, ptrdiff_t loc_next); 1.5 1.6 /** 1.7 + * Finds the predecessor of a node in case it is not linked. 1.8 + * 1.9 + * \remark If \p node is not contained in the list starting with \p begin, the behavior is undefined. 1.10 + * 1.11 + * @param begin the node where to start the search 1.12 + * @param loc_next the location of the \c next pointer 1.13 + * @param node the successor of the node to find 1.14 + * @return the node or \c NULL if \p node has no predecessor 1.15 + */ 1.16 +void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node); 1.17 + 1.18 +/** 1.19 * Adds a new node to a linked list. 1.20 * 1.21 * \remark One of the pointers \p begin and \p end may be \c NULL, but not both. 1.22 @@ -117,12 +129,38 @@ 1.23 * @param begin a pointer to the begin node pointer (if your list has one) 1.24 * @param end a pointer to the end node pointer (if your list has one) 1.25 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) 1.26 - * @param loc_next the location of a \c next pointer within your node struct (negative if your struct does not have one) 1.27 + * @param loc_next the location of a \c next pointer within your node struct (required) 1.28 * @param new_node a pointer to the node that shall be appended 1.29 */ 1.30 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node); 1.31 1.32 /** 1.33 + * Removes a node from the linked list. 1.34 + * 1.35 + * If the node to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end) 1.36 + * addresses are provided, the pointers are adjusted accordingly. 1.37 + * 1.38 + * The following combinations of arguments are valid (more arguments are optional): 1.39 + * \li \p loc_next and \p loc_prev 1.40 + * \li \p loc_next and \p begin 1.41 + * 1.42 + * This function returns an adjacent node according to the following rules: 1.43 + * \li if the node has only one adjacent node, that one is returned 1.44 + * \li otherwise, the former \c prev node is returned 1.45 + * 1.46 + * \remark The \c next and \c prev pointers of the removed node are cleared by this function. 1.47 + * 1.48 + * @param begin a pointer to the begin node pointer (optional) 1.49 + * @param end a pointer to the end node pointer (optional) 1.50 + * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) 1.51 + * @param loc_next the location of a \c next pointer within your node struct (required) 1.52 + * @param node the node to remove 1.53 + * @return an adjacent node or \c NULL, if this was the last node 1.54 + */ 1.55 +void *cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node); 1.56 + 1.57 + 1.58 +/** 1.59 * Determines the size of a linked list starting with \p node. 1.60 * @param node the first node 1.61 * @param loc_next the location of the \c next pointer within the node struct 1.62 @@ -162,6 +200,17 @@ 1.63 void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, 1.64 ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func); 1.65 1.66 + 1.67 +/** 1.68 + * Reverses the order of the nodes in a linked list. 1.69 + * 1.70 + * @param begin a pointer to the begin node pointer (required) 1.71 + * @param end a pointer to the end node pointer (optional) 1.72 + * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) 1.73 + * @param loc_next the location of a \c next pointer within your node struct (required) 1.74 + */ 1.75 +void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next); 1.76 + 1.77 #ifdef __cplusplus 1.78 } /* extern "C" */ 1.79 #endif
2.1 --- a/src/linked_list.c Fri Oct 08 18:58:49 2021 +0200 2.2 +++ b/src/linked_list.c Fri Oct 08 19:47:31 2021 +0200 2.3 @@ -36,6 +36,8 @@ 2.4 #define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off)) 2.5 2.6 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) { 2.7 + assert(start != NULL); 2.8 + assert(loc_advance >= 0); 2.9 size_t i = start_index; 2.10 void *cur = start; 2.11 while (i != index && cur != NULL) { 2.12 @@ -46,6 +48,7 @@ 2.13 } 2.14 2.15 void *cx_linked_list_last(void *begin, ptrdiff_t loc_next) { 2.16 + assert(loc_next >= 0); 2.17 if (begin == NULL) 2.18 return NULL; 2.19 2.20 @@ -58,7 +61,21 @@ 2.21 return last; 2.22 } 2.23 2.24 +void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node) { 2.25 + assert(begin != NULL); 2.26 + assert(loc_next >= 0); 2.27 + if (begin == node) return NULL; 2.28 + void *cur = begin; 2.29 + void *next; 2.30 + while (1) { 2.31 + next = CX_LL_PTR(cur, loc_next); 2.32 + if (next == node) return cur; 2.33 + cur = next; 2.34 + } 2.35 +} 2.36 + 2.37 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) { 2.38 + assert(loc_next >= 0); 2.39 void *last; 2.40 if (end == NULL) { 2.41 assert(begin != NULL); 2.42 @@ -85,7 +102,48 @@ 2.43 } 2.44 } 2.45 2.46 +void *cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) { 2.47 + assert(loc_next >= 0); 2.48 + assert(loc_prev >= 0 || begin != NULL); 2.49 + 2.50 + // find adjacent nodes 2.51 + void *next = CX_LL_PTR(node, loc_next); 2.52 + void *prev; 2.53 + if (loc_prev >= 0) { 2.54 + prev = CX_LL_PTR(node, loc_prev); 2.55 + } else { 2.56 + prev = cx_linked_list_prev(*begin, loc_next, node); 2.57 + } 2.58 + 2.59 + // update links of adjacent nodes 2.60 + if (prev != NULL) { 2.61 + CX_LL_PTR(prev, loc_next) = next; 2.62 + } 2.63 + if (next != NULL && loc_prev >= 0) { 2.64 + CX_LL_PTR(next, loc_prev) = prev; 2.65 + } 2.66 + 2.67 + // erase links of the target node 2.68 + CX_LL_PTR(node, loc_next) = NULL; 2.69 + if (loc_prev >= 0) { 2.70 + CX_LL_PTR(node, loc_prev) = NULL; 2.71 + } 2.72 + 2.73 + // update begin, if required 2.74 + if (*begin == node) { 2.75 + *begin = next; 2.76 + } 2.77 + 2.78 + // update end, if required 2.79 + if (end != NULL && *end == node) { 2.80 + *end = prev; 2.81 + } 2.82 + 2.83 + return prev == NULL ? next : prev; 2.84 +} 2.85 + 2.86 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) { 2.87 + assert(loc_next >= 0); 2.88 size_t size = 0; 2.89 while (node != NULL) { 2.90 node = CX_LL_PTR(node, loc_next); 2.91 @@ -149,6 +207,9 @@ 2.92 void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, 2.93 ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) { 2.94 assert(begin != NULL); 2.95 + assert(loc_next >= 0); 2.96 + assert(loc_data >= 0); 2.97 + assert(cmp_func); 2.98 2.99 void *lc, *ls, *le, *re; 2.100 2.101 @@ -201,6 +262,32 @@ 2.102 #undef ll_next 2.103 #undef ll_data 2.104 2.105 +void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) { 2.106 + assert(begin != NULL); 2.107 + assert(loc_next >= 0); 2.108 + 2.109 + // swap all links 2.110 + void *prev = NULL; 2.111 + void *cur = *begin; 2.112 + while (cur != NULL) { 2.113 + void *next = CX_LL_PTR(cur, loc_next); 2.114 + 2.115 + CX_LL_PTR(cur, loc_next) = prev; 2.116 + if (loc_prev >= 0) { 2.117 + CX_LL_PTR(cur, loc_prev) = next; 2.118 + } 2.119 + 2.120 + prev = cur; 2.121 + cur = next; 2.122 + } 2.123 + 2.124 + // update begin and end 2.125 + if (end != NULL) { 2.126 + *end = *begin; 2.127 + } 2.128 + *begin = prev; 2.129 +} 2.130 + 2.131 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */ 2.132 2.133 typedef struct cx_linked_list_node cx_linked_list_node;
3.1 --- a/test/test_list.c Fri Oct 08 18:58:49 2021 +0200 3.2 +++ b/test/test_list.c Fri Oct 08 19:47:31 2021 +0200 3.3 @@ -128,7 +128,6 @@ 3.4 } 3.5 3.6 void test_linked_list_last(void) { 3.7 - CU_ASSERT_PTR_NULL(cx_linked_list_last(NULL, -1)) 3.8 CU_ASSERT_PTR_NULL(cx_linked_list_last(NULL, 0)) 3.9 3.10 struct node { 3.11 @@ -146,6 +145,97 @@ 3.12 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&third, loc), &third) 3.13 } 3.14 3.15 +void test_linked_list_prev(void) { 3.16 + struct node { 3.17 + void *next; 3.18 + }; 3.19 + ptrdiff_t loc = offsetof(struct node, next); 3.20 + 3.21 + struct node third = {NULL}; 3.22 + struct node second = {&third}; 3.23 + struct node first = {&second}; 3.24 + 3.25 + CU_ASSERT_PTR_NULL(cx_linked_list_prev(&first, loc, &first)) 3.26 + CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &second), &first) 3.27 + CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &third), &second) 3.28 +} 3.29 + 3.30 +void test_linked_list_remove(void) { 3.31 + struct node { 3.32 + void *next; 3.33 + }; 3.34 + struct dnode { 3.35 + void *next; 3.36 + void *prev; 3.37 + }; 3.38 + ptrdiff_t loc = offsetof(struct node, next); 3.39 + ptrdiff_t ploc = offsetof(struct dnode, prev); 3.40 + 3.41 + void *begin; 3.42 + void *end; 3.43 + void *result; 3.44 + 3.45 + // single linked list 3.46 + struct node third = {NULL}; 3.47 + struct node second = {&third}; 3.48 + struct node first = {&second}; 3.49 + begin = &first; 3.50 + 3.51 + result = cx_linked_list_remove(&begin, NULL, -1, loc, &second); 3.52 + CU_ASSERT_PTR_EQUAL(result, &first) 3.53 + CU_ASSERT_PTR_EQUAL(begin, &first) 3.54 + CU_ASSERT_PTR_EQUAL(first.next, &third) 3.55 + CU_ASSERT_PTR_NULL(second.next) 3.56 + CU_ASSERT_PTR_NULL(third.next) 3.57 + 3.58 + result = cx_linked_list_remove(&begin, NULL, -1, loc, &first); 3.59 + CU_ASSERT_PTR_EQUAL(result, &third) 3.60 + CU_ASSERT_PTR_EQUAL(begin, &third) 3.61 + CU_ASSERT_PTR_NULL(first.next) 3.62 + CU_ASSERT_PTR_NULL(third.next) 3.63 + 3.64 + result = cx_linked_list_remove(&begin, NULL, -1, loc, &third); 3.65 + CU_ASSERT_PTR_NULL(result) 3.66 + CU_ASSERT_PTR_NULL(begin) 3.67 + CU_ASSERT_PTR_NULL(third.next) 3.68 + 3.69 + // doubly linked list 3.70 + struct dnode dthird = {NULL , NULL}; 3.71 + struct dnode dsecond = {&dthird, NULL}; 3.72 + struct dnode dfirst = {&dsecond, NULL}; 3.73 + dthird.prev = &dsecond; 3.74 + dsecond.prev = &dfirst; 3.75 + begin = &dfirst; 3.76 + end = &dthird; 3.77 + 3.78 + result = cx_linked_list_remove(&begin, &end, ploc, loc, &dsecond); 3.79 + CU_ASSERT_PTR_EQUAL(result, &dfirst) 3.80 + CU_ASSERT_PTR_EQUAL(begin, &dfirst) 3.81 + CU_ASSERT_PTR_EQUAL(end, &dthird) 3.82 + CU_ASSERT_PTR_NULL(dfirst.prev) 3.83 + CU_ASSERT_PTR_EQUAL(dfirst.next, &dthird) 3.84 + CU_ASSERT_PTR_NULL(dsecond.prev) 3.85 + CU_ASSERT_PTR_NULL(dsecond.next) 3.86 + CU_ASSERT_PTR_EQUAL(dthird.prev, &dfirst) 3.87 + CU_ASSERT_PTR_NULL(dthird.next) 3.88 + 3.89 + result = cx_linked_list_remove(&begin, &end, ploc, loc, &dthird); 3.90 + CU_ASSERT_PTR_EQUAL(result, &dfirst) 3.91 + CU_ASSERT_PTR_EQUAL(begin, &dfirst) 3.92 + CU_ASSERT_PTR_EQUAL(end, &dfirst) 3.93 + CU_ASSERT_PTR_NULL(dfirst.prev) 3.94 + CU_ASSERT_PTR_NULL(dfirst.next) 3.95 + CU_ASSERT_PTR_NULL(dthird.prev) 3.96 + CU_ASSERT_PTR_NULL(dthird.next) 3.97 + 3.98 + result = cx_linked_list_remove(&begin, &end, ploc, loc, &dfirst); 3.99 + CU_ASSERT_PTR_NULL(result) 3.100 + CU_ASSERT_PTR_NULL(begin) 3.101 + CU_ASSERT_PTR_NULL(end) 3.102 + CU_ASSERT_PTR_NULL(dfirst.next) 3.103 + CU_ASSERT_PTR_NULL(dfirst.prev) 3.104 +} 3.105 + 3.106 void test_linked_list_size(void) { 3.107 struct node { 3.108 void *next; 3.109 @@ -209,7 +299,7 @@ 3.110 CU_ASSERT_EQUAL(begin->data, expected[0]) 3.111 struct node *check = begin; 3.112 struct node *check_last = NULL; 3.113 - for (int i = 0 ; i < 100 ; i++) { 3.114 + for (int i = 0; i < 100; i++) { 3.115 CU_ASSERT_EQUAL(check->data, expected[i]) 3.116 CU_ASSERT_PTR_EQUAL(check->prev, check_last) 3.117 if (i < 99) { 3.118 @@ -222,6 +312,51 @@ 3.119 CU_ASSERT_EQUAL(end->data, expected[99]) 3.120 } 3.121 3.122 +void test_linked_list_reverse(void) { 3.123 + struct node { 3.124 + void *next; 3.125 + }; 3.126 + struct dnode { 3.127 + void *next; 3.128 + void *prev; 3.129 + }; 3.130 + ptrdiff_t loc = offsetof(struct node, next); 3.131 + ptrdiff_t ploc = offsetof(struct dnode, prev); 3.132 + 3.133 + void *begin; 3.134 + void *end; 3.135 + 3.136 + // single linked list 3.137 + struct node third = {NULL}; 3.138 + struct node second = {&third}; 3.139 + struct node first = {&second}; 3.140 + begin = &first; 3.141 + 3.142 + cx_linked_list_reverse(&begin, NULL, -1, loc); 3.143 + CU_ASSERT_PTR_EQUAL(begin, &third) 3.144 + CU_ASSERT_PTR_EQUAL(third.next, &second) 3.145 + CU_ASSERT_PTR_EQUAL(second.next, &first) 3.146 + CU_ASSERT_PTR_NULL(first.next) 3.147 + 3.148 + // doubly linked list 3.149 + struct dnode dthird = {NULL , NULL}; 3.150 + struct dnode dsecond = {&dthird, NULL}; 3.151 + struct dnode dfirst = {&dsecond, NULL}; 3.152 + dthird.prev = &dsecond; 3.153 + dsecond.prev = &dfirst; 3.154 + begin = &dfirst; 3.155 + end = &dthird; 3.156 + 3.157 + cx_linked_list_reverse(&begin, &end, ploc, loc); 3.158 + CU_ASSERT_PTR_EQUAL(begin, &dthird) 3.159 + CU_ASSERT_PTR_EQUAL(end, &dfirst) 3.160 + CU_ASSERT_PTR_EQUAL(dthird.next, &dsecond) 3.161 + CU_ASSERT_PTR_EQUAL(dsecond.next, &dfirst) 3.162 + CU_ASSERT_PTR_NULL(dfirst.next) 3.163 + CU_ASSERT_PTR_NULL(dthird.prev) 3.164 + CU_ASSERT_PTR_EQUAL(dsecond.prev, &dthird) 3.165 + CU_ASSERT_PTR_EQUAL(dfirst.prev, &dsecond) 3.166 +} 3.167 3.168 void test_hl_linked_list_create(void) { 3.169 cxTestingAllocatorReset(); 3.170 @@ -415,14 +550,14 @@ 3.171 3.172 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int)); 3.173 3.174 - for (int i = 0 ; i < 100 ; i++) { 3.175 + for (int i = 0; i < 100; i++) { 3.176 cxListAdd(list, &scrambled[i]); 3.177 } 3.178 3.179 cxListSort(list); 3.180 3.181 - for (int i = 0 ; i < 100 ; i++) { 3.182 - CU_ASSERT_EQUAL(*(int*)cxListAt(list, i), expected[i]) 3.183 + for (int i = 0; i < 100; i++) { 3.184 + CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i]) 3.185 } 3.186 3.187 cxLinkedListDestroy(list); 3.188 @@ -616,14 +751,14 @@ 3.189 3.190 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int); 3.191 3.192 - for (int i = 0 ; i < 100 ; i++) { 3.193 + for (int i = 0; i < 100; i++) { 3.194 cxListAdd(list, &scrambled[i]); 3.195 } 3.196 3.197 cxListSort(list); 3.198 3.199 - for (int i = 0 ; i < 100 ; i++) { 3.200 - CU_ASSERT_EQUAL(*(int*)cxListAt(list, i), expected[i]) 3.201 + for (int i = 0; i < 100; i++) { 3.202 + CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i]) 3.203 } 3.204 3.205 cxLinkedListDestroy(list); 3.206 @@ -642,8 +777,11 @@ 3.207 cu_add_test(suite, test_linked_list_at); 3.208 cu_add_test(suite, test_linked_list_add); 3.209 cu_add_test(suite, test_linked_list_last); 3.210 + cu_add_test(suite, test_linked_list_prev); 3.211 + cu_add_test(suite, test_linked_list_remove); 3.212 cu_add_test(suite, test_linked_list_size); 3.213 cu_add_test(suite, test_linked_list_sort); 3.214 + cu_add_test(suite, test_linked_list_reverse); 3.215 3.216 suite = CU_add_suite("high level linked list", NULL, NULL); 3.217