1.1 --- a/src/linked_list.c Tue Oct 05 13:04:20 2021 +0200
1.2 +++ b/src/linked_list.c Tue Oct 05 16:33:11 2021 +0200
1.3 @@ -33,13 +33,13 @@
1.4
1.5 /* LOW LEVEL LINKED LIST FUNCTIONS */
1.6
1.7 -#define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off))
1.8 +#define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off))
1.9
1.10 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
1.11 size_t i = start_index;
1.12 void *cur = start;
1.13 while (i != index && cur != NULL) {
1.14 - cur = *CX_LL_PTR(cur, loc_advance);
1.15 + cur = CX_LL_PTR(cur, loc_advance);
1.16 i < index ? i++ : i--;
1.17 }
1.18 return cur;
1.19 @@ -53,7 +53,7 @@
1.20 void *last;
1.21 do {
1.22 last = cur;
1.23 - } while ((cur = *CX_LL_PTR(cur, loc_next)) != NULL);
1.24 + } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL);
1.25
1.26 return last;
1.27 }
1.28 @@ -71,8 +71,7 @@
1.29 *begin = new_node;
1.30 } else {
1.31 // if there is a last node, update its next pointer
1.32 - void **next = CX_LL_PTR(last, loc_next);
1.33 - *next = new_node;
1.34 + CX_LL_PTR(last, loc_next) = new_node;
1.35 }
1.36
1.37 // if there is an end pointer, update it
1.38 @@ -82,11 +81,126 @@
1.39
1.40 // if the nodes use a prev pointer, update it
1.41 if (loc_prev >= 0) {
1.42 - void **prev = CX_LL_PTR(new_node, loc_prev);
1.43 - *prev = last;
1.44 + CX_LL_PTR(new_node, loc_prev) = last;
1.45 }
1.46 }
1.47
1.48 +size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
1.49 + size_t size = 0;
1.50 + while (node != NULL) {
1.51 + node = CX_LL_PTR(node, loc_next);
1.52 + size++;
1.53 + }
1.54 + return size;
1.55 +}
1.56 +
1.57 +#define ll_prev(node) CX_LL_PTR(node, loc_prev)
1.58 +#define ll_next(node) CX_LL_PTR(node, loc_next)
1.59 +#define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
1.60 +
1.61 +static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next,
1.62 + ptrdiff_t loc_data, int follow_ptr,
1.63 + size_t length, void *ls, void *le, void *re,
1.64 + CxListComparator cmp_func) {
1.65 + const size_t sbo_len = 1024;
1.66 + void *sbo[sbo_len];
1.67 + void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
1.68 + void *rc, *lc;
1.69 +
1.70 + lc = ls;
1.71 + rc = le;
1.72 + size_t n = 0;
1.73 + while (lc && lc != le && rc != re) {
1.74 + if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
1.75 + sorted[n] = lc;
1.76 + lc = ll_next(lc);
1.77 + } else {
1.78 + sorted[n] = rc;
1.79 + rc = ll_next(rc);
1.80 + }
1.81 + n++;
1.82 + }
1.83 + while (lc && lc != le) {
1.84 + sorted[n] = lc;
1.85 + lc = ll_next(lc);
1.86 + n++;
1.87 + }
1.88 + while (rc && rc != re) {
1.89 + sorted[n] = rc;
1.90 + rc = ll_next(rc);
1.91 + n++;
1.92 + }
1.93 +
1.94 + // Update pointer
1.95 + if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
1.96 + for (size_t i = 0; i < length - 1; i++) {
1.97 + ll_next(sorted[i]) = sorted[i + 1];
1.98 + if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i];
1.99 + }
1.100 + ll_next(sorted[length - 1]) = NULL;
1.101 +
1.102 + void *ret = sorted[0];
1.103 + if (sorted != sbo) {
1.104 + free(sorted);
1.105 + }
1.106 + return ret;
1.107 +}
1.108 +
1.109 +void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
1.110 + ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
1.111 + assert(begin != NULL);
1.112 +
1.113 + void *lc, *ls, *le, *re;
1.114 +
1.115 + // set start node
1.116 + ls = *begin;
1.117 +
1.118 + // check how many elements are already sorted
1.119 + lc = ls;
1.120 + size_t ln = 1;
1.121 + while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
1.122 + lc = ll_next(lc);
1.123 + ln++;
1.124 + }
1.125 + le = ll_next(lc);
1.126 +
1.127 + // if first unsorted node is NULL, the list is already completely sorted
1.128 + if (le != NULL) {
1.129 + void *rc;
1.130 + size_t rn = 1;
1.131 + rc = le;
1.132 + // skip already sorted elements
1.133 + while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
1.134 + rc = ll_next(rc);
1.135 + rn++;
1.136 + }
1.137 + re = ll_next(rc);
1.138 +
1.139 + // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
1.140 + void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
1.141 + ln + rn, ls, le, re, cmp_func);
1.142 +
1.143 + // Something left? Sort it!
1.144 + size_t remainder_length = cx_linked_list_size(re, loc_next);
1.145 + if (remainder_length > 0) {
1.146 + void *remainder = re;
1.147 + cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func);
1.148 +
1.149 + // merge sorted list with (also sorted) remainder
1.150 + *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
1.151 + ln + rn + remainder_length,
1.152 + sorted, remainder, NULL, cmp_func);
1.153 + } else {
1.154 + // no remainder - we've got our sorted list
1.155 + *begin = sorted;
1.156 + }
1.157 + if (end) *end = cx_linked_list_last(sorted, loc_next);
1.158 + }
1.159 +}
1.160 +
1.161 +#undef ll_next
1.162 +#undef ll_data
1.163 +
1.164 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
1.165
1.166 typedef struct cx_linked_list_node cx_linked_list_node;
1.167 @@ -109,7 +223,7 @@
1.168 if (index >= list->base.size) {
1.169 return NULL;
1.170 } else if (index > list->base.size / 2) {
1.171 - return cx_linked_list_at(list->end, list->base.size-1, CX_LL_LOC_PREV, index);
1.172 + return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
1.173 } else {
1.174 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
1.175 }
1.176 @@ -144,7 +258,7 @@
1.177 node->next = NULL;
1.178 ll->end = node;
1.179 }
1.180 - // check if this shall be the new start node
1.181 + // check if this shall be the new start node
1.182 else if (index == 0) {
1.183 ll->begin->prev = node;
1.184 node->next = ll->begin;
1.185 @@ -219,7 +333,7 @@
1.186 static void *cx_pll_at(cx_list_s *list, size_t index) {
1.187 cx_linked_list *ll = (cx_linked_list *) list;
1.188 cx_linked_list_node *node = cx_ll_node_at(ll, index);
1.189 - return node == NULL ? NULL : *(void**)node->payload;
1.190 + return node == NULL ? NULL : *(void **) node->payload;
1.191 }
1.192
1.193 static size_t cx_ll_find(cx_list_s *list, void *elem) {
1.194 @@ -245,7 +359,7 @@
1.195 size_t index;
1.196 cx_linked_list_node *node = ll->begin;
1.197 for (index = 0; index < list->size; index++) {
1.198 - void *current = *(void**)node->payload;
1.199 + void *current = *(void **) node->payload;
1.200 if (cmp(current, elem) == 0) {
1.201 return index;
1.202 }
1.203 @@ -263,7 +377,7 @@
1.204 static void *cx_pll_last(cx_list_s *list) {
1.205 cx_linked_list *ll = (cx_linked_list *) list;
1.206 cx_linked_list_node *last = ll->end;
1.207 - return last == NULL ? NULL : *(void**)last->payload;
1.208 + return last == NULL ? NULL : *(void **) last->payload;
1.209 }
1.210
1.211 static cx_list_class cx_linked_list_class = {
1.212 @@ -310,7 +424,7 @@
1.213 list->base.cl = &cx_pointer_linked_list_class;
1.214 list->base.allocator = allocator;
1.215 list->base.cmpfunc = comparator;
1.216 - list->base.itemsize = sizeof(void*);
1.217 + list->base.itemsize = sizeof(void *);
1.218 list->base.capacity = SIZE_MAX;
1.219 list->base.size = 0;
1.220
