changeset
add cx_linked_list_sort()
Tue, 05 Oct 2021 16:33:11 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Tue, 05 Oct 2021 16:33:11 +0200
- changeset 468
- 75ae1dccd101
- parent 467
- 95e42a963520
- child 469
- 0458bff0b1cd
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 |
--- a/src/cx/linked_list.h Tue Oct 05 13:04:20 2021 +0200 +++ b/src/cx/linked_list.h Tue Oct 05 16:33:11 2021 +0200 @@ -122,6 +122,46 @@ */ void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_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 + * @return the size of the list or zero if \p node is \c NULL + */ +size_t cx_linked_list_size(void *node, ptrdiff_t loc_next); + +/** + * Sorts a linked list based on a comparison function. + * + * This function can work with linked lists of the following structures: + * \code + * typedef struct node node; + * struct node { + * node* prev; + * node* next; + * my_payload data; // in this case set follow_ptr = 0 + * } + * + * typedef struct ptr_node ptr_node; + * struct ptr_node { + * ptr_node* prev; + * ptr_node* next; + * my_payload* data; // in this case set follow_ptr = 1 + * } + * \endcode + * + * @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 not present) + * @param loc_next the location of a \c next pointer within your node struct (required) + * @param loc_data the location of the \c data pointer within your node struct + * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func. + * If \c true, the data at \p loc_data is dereferenced, assuming to be a pointer, and then passed to \p cmp_func. + * @param cmp_func the compare function defining the sort order + */ +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); + #ifdef __cplusplus } /* extern "C" */ #endif
--- a/src/linked_list.c Tue Oct 05 13:04:20 2021 +0200 +++ b/src/linked_list.c Tue Oct 05 16:33:11 2021 +0200 @@ -33,13 +33,13 @@ /* LOW LEVEL LINKED LIST FUNCTIONS */ -#define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off)) +#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); + cur = CX_LL_PTR(cur, loc_advance); i < index ? i++ : i--; } return cur; @@ -53,7 +53,7 @@ void *last; do { last = cur; - } while ((cur = *CX_LL_PTR(cur, loc_next)) != NULL); + } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL); return last; } @@ -71,8 +71,7 @@ *begin = new_node; } else { // if there is a last node, update its next pointer - void **next = CX_LL_PTR(last, loc_next); - *next = new_node; + CX_LL_PTR(last, loc_next) = new_node; } // if there is an end pointer, update it @@ -82,11 +81,126 @@ // if the nodes use a prev pointer, update it if (loc_prev >= 0) { - void **prev = CX_LL_PTR(new_node, loc_prev); - *prev = last; + CX_LL_PTR(new_node, loc_prev) = last; } } +size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) { + size_t size = 0; + while (node != NULL) { + node = CX_LL_PTR(node, loc_next); + size++; + } + return size; +} + +#define ll_prev(node) CX_LL_PTR(node, loc_prev) +#define ll_next(node) CX_LL_PTR(node, loc_next) +#define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data)) + +static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next, + ptrdiff_t loc_data, int follow_ptr, + size_t length, void *ls, void *le, void *re, + CxListComparator cmp_func) { + const size_t sbo_len = 1024; + void *sbo[sbo_len]; + void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo; + void *rc, *lc; + + lc = ls; + rc = le; + size_t n = 0; + while (lc && lc != le && rc != re) { + if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) { + sorted[n] = lc; + lc = ll_next(lc); + } else { + sorted[n] = rc; + rc = ll_next(rc); + } + n++; + } + while (lc && lc != le) { + sorted[n] = lc; + lc = ll_next(lc); + n++; + } + while (rc && rc != re) { + sorted[n] = rc; + rc = ll_next(rc); + n++; + } + + // Update pointer + if (loc_prev >= 0) ll_prev(sorted[0]) = NULL; + for (size_t i = 0; i < length - 1; i++) { + ll_next(sorted[i]) = sorted[i + 1]; + if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i]; + } + ll_next(sorted[length - 1]) = NULL; + + void *ret = sorted[0]; + if (sorted != sbo) { + free(sorted); + } + return ret; +} + +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); + + void *lc, *ls, *le, *re; + + // set start node + ls = *begin; + + // check how many elements are already sorted + lc = ls; + size_t ln = 1; + while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) { + lc = ll_next(lc); + ln++; + } + le = ll_next(lc); + + // if first unsorted node is NULL, the list is already completely sorted + if (le != NULL) { + void *rc; + size_t rn = 1; + rc = le; + // skip already sorted elements + while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) { + rc = ll_next(rc); + rn++; + } + re = ll_next(rc); + + // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them + void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr, + ln + rn, ls, le, re, cmp_func); + + // Something left? Sort it! + size_t remainder_length = cx_linked_list_size(re, loc_next); + if (remainder_length > 0) { + void *remainder = re; + cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func); + + // merge sorted list with (also sorted) remainder + *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr, + ln + rn + remainder_length, + sorted, remainder, NULL, cmp_func); + } else { + // no remainder - we've got our sorted list + *begin = sorted; + } + if (end) *end = cx_linked_list_last(sorted, loc_next); + } +} + +#undef ll_next +#undef ll_data + /* HIGH LEVEL LINKED LIST IMPLEMENTATION */ typedef struct cx_linked_list_node cx_linked_list_node; @@ -109,7 +223,7 @@ if (index >= list->base.size) { return NULL; } else if (index > list->base.size / 2) { - return cx_linked_list_at(list->end, list->base.size-1, CX_LL_LOC_PREV, index); + return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index); } else { return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); } @@ -144,7 +258,7 @@ node->next = NULL; ll->end = node; } - // check if this shall be the new start node + // check if this shall be the new start node else if (index == 0) { ll->begin->prev = node; node->next = ll->begin; @@ -219,7 +333,7 @@ static void *cx_pll_at(cx_list_s *list, size_t index) { cx_linked_list *ll = (cx_linked_list *) list; cx_linked_list_node *node = cx_ll_node_at(ll, index); - return node == NULL ? NULL : *(void**)node->payload; + return node == NULL ? NULL : *(void **) node->payload; } static size_t cx_ll_find(cx_list_s *list, void *elem) { @@ -245,7 +359,7 @@ size_t index; cx_linked_list_node *node = ll->begin; for (index = 0; index < list->size; index++) { - void *current = *(void**)node->payload; + void *current = *(void **) node->payload; if (cmp(current, elem) == 0) { return index; } @@ -263,7 +377,7 @@ static void *cx_pll_last(cx_list_s *list) { cx_linked_list *ll = (cx_linked_list *) list; cx_linked_list_node *last = ll->end; - return last == NULL ? NULL : *(void**)last->payload; + return last == NULL ? NULL : *(void **) last->payload; } static cx_list_class cx_linked_list_class = { @@ -310,7 +424,7 @@ list->base.cl = &cx_pointer_linked_list_class; list->base.allocator = allocator; list->base.cmpfunc = comparator; - list->base.itemsize = sizeof(void*); + list->base.itemsize = sizeof(void *); list->base.capacity = SIZE_MAX; list->base.size = 0;
--- a/test/test_list.c Tue Oct 05 13:04:20 2021 +0200 +++ b/test/test_list.c Tue Oct 05 16:33:11 2021 +0200 @@ -146,6 +146,82 @@ CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&third, loc), &third) } +void test_linked_list_size(void) { + struct node { + void *next; + }; + ptrdiff_t loc = offsetof(struct node, next); + + struct node first = {NULL}; + struct node second = {NULL}; + struct node third = {NULL}; + + CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc), 0) + CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 1) + first.next = &second; + CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 2) + second.next = &third; + CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 3) + CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&second, loc), 2) +} + +void test_linked_list_sort(void) { + struct node { + void *prev; + void *next; + int data; + }; + + int expected[] = { + 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880, + 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894, + 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797, + 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677, + 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681, + 4785, 4791, 4801, 4859, 4903, 4973 + }; + int scrambled[] = { + 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079, + 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888, + 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300, + 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424, + 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973, + 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681 + }; + + struct node *nodes = calloc(100, sizeof(struct node)); + for (int i = 0; i < 100; i++) { + nodes[i].prev = i == 0 ? NULL : &nodes[i - 1]; + nodes[i].next = i == 99 ? NULL : &nodes[i + 1]; + nodes[i].data = scrambled[i]; + } + + struct node *begin = &nodes[0]; + struct node *end = &nodes[99]; + + cx_linked_list_sort((void **) &begin, (void **) &end, + offsetof(struct node, prev), + offsetof(struct node, next), + offsetof(struct node, data), + 0, (CxListComparator) cmp_int); + + CU_ASSERT_PTR_NULL(begin->prev) + CU_ASSERT_EQUAL(begin->data, expected[0]) + struct node *check = begin; + struct node *check_last = NULL; + 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) { + CU_ASSERT_PTR_NOT_NULL(check->next) + } + check_last = check; + check = check->next; + } + CU_ASSERT_PTR_NULL(check) + CU_ASSERT_EQUAL(end->data, expected[99]) +} + void test_hl_linked_list_create(void) { cxTestingAllocatorReset(); @@ -494,6 +570,8 @@ 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_size); + cu_add_test(suite, test_linked_list_sort); suite = CU_add_suite("high level linked list", NULL, NULL);
