Tue, 05 Oct 2021 16:33:11 +0200
add cx_linked_list_sort()
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 Tue Oct 05 13:04:20 2021 +0200 1.2 +++ b/src/cx/linked_list.h Tue Oct 05 16:33:11 2021 +0200 1.3 @@ -122,6 +122,46 @@ 1.4 */ 1.5 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node); 1.6 1.7 +/** 1.8 + * Determines the size of a linked list starting with \p node. 1.9 + * @param node the first node 1.10 + * @param loc_next the location of the \c next pointer within the node struct 1.11 + * @return the size of the list or zero if \p node is \c NULL 1.12 + */ 1.13 +size_t cx_linked_list_size(void *node, ptrdiff_t loc_next); 1.14 + 1.15 +/** 1.16 + * Sorts a linked list based on a comparison function. 1.17 + * 1.18 + * This function can work with linked lists of the following structures: 1.19 + * \code 1.20 + * typedef struct node node; 1.21 + * struct node { 1.22 + * node* prev; 1.23 + * node* next; 1.24 + * my_payload data; // in this case set follow_ptr = 0 1.25 + * } 1.26 + * 1.27 + * typedef struct ptr_node ptr_node; 1.28 + * struct ptr_node { 1.29 + * ptr_node* prev; 1.30 + * ptr_node* next; 1.31 + * my_payload* data; // in this case set follow_ptr = 1 1.32 + * } 1.33 + * \endcode 1.34 + * 1.35 + * @param begin a pointer to the begin node pointer (required) 1.36 + * @param end a pointer to the end node pointer (optional) 1.37 + * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present) 1.38 + * @param loc_next the location of a \c next pointer within your node struct (required) 1.39 + * @param loc_data the location of the \c data pointer within your node struct 1.40 + * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func. 1.41 + * If \c true, the data at \p loc_data is dereferenced, assuming to be a pointer, and then passed to \p cmp_func. 1.42 + * @param cmp_func the compare function defining the sort order 1.43 + */ 1.44 +void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, 1.45 + ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func); 1.46 + 1.47 #ifdef __cplusplus 1.48 } /* extern "C" */ 1.49 #endif
2.1 --- a/src/linked_list.c Tue Oct 05 13:04:20 2021 +0200 2.2 +++ b/src/linked_list.c Tue Oct 05 16:33:11 2021 +0200 2.3 @@ -33,13 +33,13 @@ 2.4 2.5 /* LOW LEVEL LINKED LIST FUNCTIONS */ 2.6 2.7 -#define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off)) 2.8 +#define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off)) 2.9 2.10 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) { 2.11 size_t i = start_index; 2.12 void *cur = start; 2.13 while (i != index && cur != NULL) { 2.14 - cur = *CX_LL_PTR(cur, loc_advance); 2.15 + cur = CX_LL_PTR(cur, loc_advance); 2.16 i < index ? i++ : i--; 2.17 } 2.18 return cur; 2.19 @@ -53,7 +53,7 @@ 2.20 void *last; 2.21 do { 2.22 last = cur; 2.23 - } while ((cur = *CX_LL_PTR(cur, loc_next)) != NULL); 2.24 + } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL); 2.25 2.26 return last; 2.27 } 2.28 @@ -71,8 +71,7 @@ 2.29 *begin = new_node; 2.30 } else { 2.31 // if there is a last node, update its next pointer 2.32 - void **next = CX_LL_PTR(last, loc_next); 2.33 - *next = new_node; 2.34 + CX_LL_PTR(last, loc_next) = new_node; 2.35 } 2.36 2.37 // if there is an end pointer, update it 2.38 @@ -82,11 +81,126 @@ 2.39 2.40 // if the nodes use a prev pointer, update it 2.41 if (loc_prev >= 0) { 2.42 - void **prev = CX_LL_PTR(new_node, loc_prev); 2.43 - *prev = last; 2.44 + CX_LL_PTR(new_node, loc_prev) = last; 2.45 } 2.46 } 2.47 2.48 +size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) { 2.49 + size_t size = 0; 2.50 + while (node != NULL) { 2.51 + node = CX_LL_PTR(node, loc_next); 2.52 + size++; 2.53 + } 2.54 + return size; 2.55 +} 2.56 + 2.57 +#define ll_prev(node) CX_LL_PTR(node, loc_prev) 2.58 +#define ll_next(node) CX_LL_PTR(node, loc_next) 2.59 +#define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data)) 2.60 + 2.61 +static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next, 2.62 + ptrdiff_t loc_data, int follow_ptr, 2.63 + size_t length, void *ls, void *le, void *re, 2.64 + CxListComparator cmp_func) { 2.65 + const size_t sbo_len = 1024; 2.66 + void *sbo[sbo_len]; 2.67 + void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo; 2.68 + void *rc, *lc; 2.69 + 2.70 + lc = ls; 2.71 + rc = le; 2.72 + size_t n = 0; 2.73 + while (lc && lc != le && rc != re) { 2.74 + if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) { 2.75 + sorted[n] = lc; 2.76 + lc = ll_next(lc); 2.77 + } else { 2.78 + sorted[n] = rc; 2.79 + rc = ll_next(rc); 2.80 + } 2.81 + n++; 2.82 + } 2.83 + while (lc && lc != le) { 2.84 + sorted[n] = lc; 2.85 + lc = ll_next(lc); 2.86 + n++; 2.87 + } 2.88 + while (rc && rc != re) { 2.89 + sorted[n] = rc; 2.90 + rc = ll_next(rc); 2.91 + n++; 2.92 + } 2.93 + 2.94 + // Update pointer 2.95 + if (loc_prev >= 0) ll_prev(sorted[0]) = NULL; 2.96 + for (size_t i = 0; i < length - 1; i++) { 2.97 + ll_next(sorted[i]) = sorted[i + 1]; 2.98 + if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i]; 2.99 + } 2.100 + ll_next(sorted[length - 1]) = NULL; 2.101 + 2.102 + void *ret = sorted[0]; 2.103 + if (sorted != sbo) { 2.104 + free(sorted); 2.105 + } 2.106 + return ret; 2.107 +} 2.108 + 2.109 +void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, 2.110 + ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) { 2.111 + assert(begin != NULL); 2.112 + 2.113 + void *lc, *ls, *le, *re; 2.114 + 2.115 + // set start node 2.116 + ls = *begin; 2.117 + 2.118 + // check how many elements are already sorted 2.119 + lc = ls; 2.120 + size_t ln = 1; 2.121 + while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) { 2.122 + lc = ll_next(lc); 2.123 + ln++; 2.124 + } 2.125 + le = ll_next(lc); 2.126 + 2.127 + // if first unsorted node is NULL, the list is already completely sorted 2.128 + if (le != NULL) { 2.129 + void *rc; 2.130 + size_t rn = 1; 2.131 + rc = le; 2.132 + // skip already sorted elements 2.133 + while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) { 2.134 + rc = ll_next(rc); 2.135 + rn++; 2.136 + } 2.137 + re = ll_next(rc); 2.138 + 2.139 + // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them 2.140 + void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr, 2.141 + ln + rn, ls, le, re, cmp_func); 2.142 + 2.143 + // Something left? Sort it! 2.144 + size_t remainder_length = cx_linked_list_size(re, loc_next); 2.145 + if (remainder_length > 0) { 2.146 + void *remainder = re; 2.147 + cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func); 2.148 + 2.149 + // merge sorted list with (also sorted) remainder 2.150 + *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr, 2.151 + ln + rn + remainder_length, 2.152 + sorted, remainder, NULL, cmp_func); 2.153 + } else { 2.154 + // no remainder - we've got our sorted list 2.155 + *begin = sorted; 2.156 + } 2.157 + if (end) *end = cx_linked_list_last(sorted, loc_next); 2.158 + } 2.159 +} 2.160 + 2.161 +#undef ll_next 2.162 +#undef ll_data 2.163 + 2.164 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */ 2.165 2.166 typedef struct cx_linked_list_node cx_linked_list_node; 2.167 @@ -109,7 +223,7 @@ 2.168 if (index >= list->base.size) { 2.169 return NULL; 2.170 } else if (index > list->base.size / 2) { 2.171 - return cx_linked_list_at(list->end, list->base.size-1, CX_LL_LOC_PREV, index); 2.172 + return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index); 2.173 } else { 2.174 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); 2.175 } 2.176 @@ -144,7 +258,7 @@ 2.177 node->next = NULL; 2.178 ll->end = node; 2.179 } 2.180 - // check if this shall be the new start node 2.181 + // check if this shall be the new start node 2.182 else if (index == 0) { 2.183 ll->begin->prev = node; 2.184 node->next = ll->begin; 2.185 @@ -219,7 +333,7 @@ 2.186 static void *cx_pll_at(cx_list_s *list, size_t index) { 2.187 cx_linked_list *ll = (cx_linked_list *) list; 2.188 cx_linked_list_node *node = cx_ll_node_at(ll, index); 2.189 - return node == NULL ? NULL : *(void**)node->payload; 2.190 + return node == NULL ? NULL : *(void **) node->payload; 2.191 } 2.192 2.193 static size_t cx_ll_find(cx_list_s *list, void *elem) { 2.194 @@ -245,7 +359,7 @@ 2.195 size_t index; 2.196 cx_linked_list_node *node = ll->begin; 2.197 for (index = 0; index < list->size; index++) { 2.198 - void *current = *(void**)node->payload; 2.199 + void *current = *(void **) node->payload; 2.200 if (cmp(current, elem) == 0) { 2.201 return index; 2.202 } 2.203 @@ -263,7 +377,7 @@ 2.204 static void *cx_pll_last(cx_list_s *list) { 2.205 cx_linked_list *ll = (cx_linked_list *) list; 2.206 cx_linked_list_node *last = ll->end; 2.207 - return last == NULL ? NULL : *(void**)last->payload; 2.208 + return last == NULL ? NULL : *(void **) last->payload; 2.209 } 2.210 2.211 static cx_list_class cx_linked_list_class = { 2.212 @@ -310,7 +424,7 @@ 2.213 list->base.cl = &cx_pointer_linked_list_class; 2.214 list->base.allocator = allocator; 2.215 list->base.cmpfunc = comparator; 2.216 - list->base.itemsize = sizeof(void*); 2.217 + list->base.itemsize = sizeof(void *); 2.218 list->base.capacity = SIZE_MAX; 2.219 list->base.size = 0; 2.220
3.1 --- a/test/test_list.c Tue Oct 05 13:04:20 2021 +0200 3.2 +++ b/test/test_list.c Tue Oct 05 16:33:11 2021 +0200 3.3 @@ -146,6 +146,82 @@ 3.4 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&third, loc), &third) 3.5 } 3.6 3.7 +void test_linked_list_size(void) { 3.8 + struct node { 3.9 + void *next; 3.10 + }; 3.11 + ptrdiff_t loc = offsetof(struct node, next); 3.12 + 3.13 + struct node first = {NULL}; 3.14 + struct node second = {NULL}; 3.15 + struct node third = {NULL}; 3.16 + 3.17 + CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc), 0) 3.18 + CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 1) 3.19 + first.next = &second; 3.20 + CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 2) 3.21 + second.next = &third; 3.22 + CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 3) 3.23 + CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&second, loc), 2) 3.24 +} 3.25 + 3.26 +void test_linked_list_sort(void) { 3.27 + struct node { 3.28 + void *prev; 3.29 + void *next; 3.30 + int data; 3.31 + }; 3.32 + 3.33 + int expected[] = { 3.34 + 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880, 3.35 + 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894, 3.36 + 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797, 3.37 + 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677, 3.38 + 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681, 3.39 + 4785, 4791, 4801, 4859, 4903, 4973 3.40 + }; 3.41 + int scrambled[] = { 3.42 + 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079, 3.43 + 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888, 3.44 + 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300, 3.45 + 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424, 3.46 + 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973, 3.47 + 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681 3.48 + }; 3.49 + 3.50 + struct node *nodes = calloc(100, sizeof(struct node)); 3.51 + for (int i = 0; i < 100; i++) { 3.52 + nodes[i].prev = i == 0 ? NULL : &nodes[i - 1]; 3.53 + nodes[i].next = i == 99 ? NULL : &nodes[i + 1]; 3.54 + nodes[i].data = scrambled[i]; 3.55 + } 3.56 + 3.57 + struct node *begin = &nodes[0]; 3.58 + struct node *end = &nodes[99]; 3.59 + 3.60 + cx_linked_list_sort((void **) &begin, (void **) &end, 3.61 + offsetof(struct node, prev), 3.62 + offsetof(struct node, next), 3.63 + offsetof(struct node, data), 3.64 + 0, (CxListComparator) cmp_int); 3.65 + 3.66 + CU_ASSERT_PTR_NULL(begin->prev) 3.67 + CU_ASSERT_EQUAL(begin->data, expected[0]) 3.68 + struct node *check = begin; 3.69 + struct node *check_last = NULL; 3.70 + for (int i = 0 ; i < 100 ; i++) { 3.71 + CU_ASSERT_EQUAL(check->data, expected[i]) 3.72 + CU_ASSERT_PTR_EQUAL(check->prev, check_last) 3.73 + if (i < 99) { 3.74 + CU_ASSERT_PTR_NOT_NULL(check->next) 3.75 + } 3.76 + check_last = check; 3.77 + check = check->next; 3.78 + } 3.79 + CU_ASSERT_PTR_NULL(check) 3.80 + CU_ASSERT_EQUAL(end->data, expected[99]) 3.81 +} 3.82 + 3.83 3.84 void test_hl_linked_list_create(void) { 3.85 cxTestingAllocatorReset(); 3.86 @@ -494,6 +570,8 @@ 3.87 cu_add_test(suite, test_linked_list_at); 3.88 cu_add_test(suite, test_linked_list_add); 3.89 cu_add_test(suite, test_linked_list_last); 3.90 + cu_add_test(suite, test_linked_list_size); 3.91 + cu_add_test(suite, test_linked_list_sort); 3.92 3.93 suite = CU_add_suite("high level linked list", NULL, NULL); 3.94