1.1 --- a/src/linked_list.c Mon Dec 20 12:10:48 2021 +0100
1.2 +++ b/src/linked_list.c Mon Dec 20 13:01:38 2021 +0100
1.3 @@ -34,6 +34,10 @@
1.4 /* LOW LEVEL LINKED LIST FUNCTIONS */
1.5
1.6 #define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off))
1.7 +#define ll_prev(node) CX_LL_PTR(node, loc_prev)
1.8 +#define ll_next(node) CX_LL_PTR(node, loc_next)
1.9 +#define ll_advance(node) CX_LL_PTR(node, loc_advance)
1.10 +#define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
1.11
1.12 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
1.13 assert(start != NULL);
1.14 @@ -41,12 +45,32 @@
1.15 size_t i = start_index;
1.16 void *cur = start;
1.17 while (i != index && cur != NULL) {
1.18 - cur = CX_LL_PTR(cur, loc_advance);
1.19 + cur = ll_advance(cur);
1.20 i < index ? i++ : i--;
1.21 }
1.22 return cur;
1.23 }
1.24
1.25 +size_t cx_linked_list_find(void *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, int follow_ptr,
1.26 + CxListComparator cmp_func, void *elem) {
1.27 + assert(start != NULL);
1.28 + assert(loc_advance >= 0);
1.29 + assert(loc_data >= 0);
1.30 + assert(cmp_func);
1.31 +
1.32 + void *node = start;
1.33 + size_t index = 0;
1.34 + do {
1.35 + void *current = ll_data(node);
1.36 + if (cmp_func(current, elem) == 0) {
1.37 + return index;
1.38 + }
1.39 + node = ll_advance(node);
1.40 + index++;
1.41 + } while (node != NULL);
1.42 + return index;
1.43 +}
1.44 +
1.45 void *cx_linked_list_first(void *node, ptrdiff_t loc_prev) {
1.46 return cx_linked_list_last(node, loc_prev);
1.47 }
1.48 @@ -59,7 +83,7 @@
1.49 void *last;
1.50 do {
1.51 last = cur;
1.52 - } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL);
1.53 + } while ((cur = ll_next(cur)) != NULL);
1.54
1.55 return last;
1.56 }
1.57 @@ -72,7 +96,7 @@
1.58 void *cur = begin;
1.59 void *next;
1.60 while (1) {
1.61 - next = CX_LL_PTR(cur, loc_next);
1.62 + next = ll_next(cur);
1.63 if (next == node) return cur;
1.64 cur = next;
1.65 }
1.66 @@ -81,7 +105,7 @@
1.67 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
1.68 assert(new_node != NULL);
1.69 assert(loc_next >= 0);
1.70 - assert(CX_LL_PTR(new_node, loc_next) == NULL);
1.71 + assert(ll_next(new_node) == NULL);
1.72 void *last;
1.73 if (end == NULL) {
1.74 assert(begin != NULL);
1.75 @@ -95,7 +119,7 @@
1.76 }
1.77 } else {
1.78 // if there is a last node, update its next pointer
1.79 - CX_LL_PTR(last, loc_next) = new_node;
1.80 + ll_next(last) = new_node;
1.81 }
1.82
1.83 // if there is an end pointer, update it
1.84 @@ -105,15 +129,15 @@
1.85
1.86 // if the nodes use a prev pointer, update it
1.87 if (loc_prev >= 0) {
1.88 - assert(CX_LL_PTR(new_node, loc_prev) == NULL);
1.89 - CX_LL_PTR(new_node, loc_prev) = last;
1.90 + assert(ll_prev(new_node) == NULL);
1.91 + ll_prev(new_node) = last;
1.92 }
1.93 }
1.94
1.95 void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
1.96 assert(new_node != NULL);
1.97 assert(loc_next >= 0);
1.98 - assert(CX_LL_PTR(new_node, loc_next) == NULL);
1.99 + assert(ll_next(new_node) == NULL);
1.100 void *first;
1.101 if (begin == NULL) {
1.102 assert(end != NULL);
1.103 @@ -127,14 +151,14 @@
1.104 *end = new_node;
1.105 }
1.106 } else {
1.107 - CX_LL_PTR(new_node, loc_next) = first;
1.108 + ll_next(new_node) = first;
1.109 if (loc_prev >= 0) {
1.110 - CX_LL_PTR(first, loc_prev) = new_node;
1.111 + ll_prev(first) = new_node;
1.112 }
1.113 }
1.114
1.115 if (begin != NULL) {
1.116 - assert(loc_prev < 0 || CX_LL_PTR(new_node, loc_prev) == NULL);
1.117 + assert(loc_prev < 0 || ll_prev(new_node) == NULL);
1.118 *begin = new_node;
1.119 }
1.120 }
1.121 @@ -145,10 +169,10 @@
1.122 assert(loc_prev >= 0 || begin != NULL);
1.123
1.124 // find adjacent nodes
1.125 - void *next = CX_LL_PTR(node, loc_next);
1.126 + void *next = ll_next(node);
1.127 void *prev;
1.128 if (loc_prev >= 0) {
1.129 - prev = CX_LL_PTR(node, loc_prev);
1.130 + prev = ll_prev(node);
1.131 } else {
1.132 prev = cx_linked_list_prev(*begin, loc_next, node);
1.133 }
1.134 @@ -159,7 +183,7 @@
1.135 *begin = next;
1.136 }
1.137 } else {
1.138 - CX_LL_PTR(prev, loc_next) = next;
1.139 + ll_next(prev) = next;
1.140 }
1.141
1.142 // update prev pointer of next node, or set end
1.143 @@ -168,7 +192,7 @@
1.144 *end = prev;
1.145 }
1.146 } else if (loc_prev >= 0) {
1.147 - CX_LL_PTR(next, loc_prev) = prev;
1.148 + ll_prev(next) = prev;
1.149 }
1.150 }
1.151
1.152 @@ -176,16 +200,12 @@
1.153 assert(loc_next >= 0);
1.154 size_t size = 0;
1.155 while (node != NULL) {
1.156 - node = CX_LL_PTR(node, loc_next);
1.157 + node = ll_next(node);
1.158 size++;
1.159 }
1.160 return size;
1.161 }
1.162
1.163 -#define ll_prev(node) CX_LL_PTR(node, loc_prev)
1.164 -#define ll_next(node) CX_LL_PTR(node, loc_next)
1.165 -#define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
1.166 -
1.167 static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next,
1.168 ptrdiff_t loc_data, int follow_ptr,
1.169 size_t length, void *ls, void *le, void *re,
1.170 @@ -290,9 +310,6 @@
1.171 }
1.172 }
1.173
1.174 -#undef ll_next
1.175 -#undef ll_data
1.176 -
1.177 void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) {
1.178 assert(begin != NULL);
1.179 assert(loc_next >= 0);
1.180 @@ -301,11 +318,11 @@
1.181 void *prev = NULL;
1.182 void *cur = *begin;
1.183 while (cur != NULL) {
1.184 - void *next = CX_LL_PTR(cur, loc_next);
1.185 + void *next = ll_next(cur);
1.186
1.187 - CX_LL_PTR(cur, loc_next) = prev;
1.188 + ll_next(cur) = prev;
1.189 if (loc_prev >= 0) {
1.190 - CX_LL_PTR(cur, loc_prev) = next;
1.191 + ll_prev(cur) = next;
1.192 }
1.193
1.194 prev = cur;
1.195 @@ -446,35 +463,15 @@
1.196 }
1.197
1.198 static size_t cx_ll_find(cx_list_s *list, void *elem) {
1.199 - CxListComparator cmp = list->cmpfunc;
1.200 - cx_linked_list *ll = (cx_linked_list *) list;
1.201 -
1.202 - size_t index;
1.203 - cx_linked_list_node *node = ll->begin;
1.204 - for (index = 0; index < list->size; index++) {
1.205 - void *current = node->payload;
1.206 - if (cmp(current, elem) == 0) {
1.207 - return index;
1.208 - }
1.209 - node = node->next;
1.210 - }
1.211 - return index;
1.212 + return cx_linked_list_find(((cx_linked_list *) list)->begin,
1.213 + CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
1.214 + 0, list->cmpfunc, elem);
1.215 }
1.216
1.217 static size_t cx_pll_find(cx_list_s *list, void *elem) {
1.218 - CxListComparator cmp = list->cmpfunc;
1.219 - cx_linked_list *ll = (cx_linked_list *) list;
1.220 -
1.221 - size_t index;
1.222 - cx_linked_list_node *node = ll->begin;
1.223 - for (index = 0; index < list->size; index++) {
1.224 - void *current = *(void **) node->payload;
1.225 - if (cmp(current, elem) == 0) {
1.226 - return index;
1.227 - }
1.228 - node = node->next;
1.229 - }
1.230 - return index;
1.231 + return cx_linked_list_find(((cx_linked_list *) list)->begin,
1.232 + CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
1.233 + 1, list->cmpfunc, elem);
1.234 }
1.235
1.236 static void cx_ll_sort(cx_list_s *list) {
