1.1 --- a/src/linked_list.c Mon Dec 20 13:01:38 2021 +0100
1.2 +++ b/src/linked_list.c Thu Dec 23 15:20:50 2021 +0100
1.3 @@ -39,7 +39,12 @@
1.4 #define ll_advance(node) CX_LL_PTR(node, loc_advance)
1.5 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
1.6
1.7 -void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
1.8 +void *cx_linked_list_at(
1.9 + void *start,
1.10 + size_t start_index,
1.11 + ptrdiff_t loc_advance,
1.12 + size_t index
1.13 +) {
1.14 assert(start != NULL);
1.15 assert(loc_advance >= 0);
1.16 size_t i = start_index;
1.17 @@ -51,8 +56,14 @@
1.18 return cur;
1.19 }
1.20
1.21 -size_t cx_linked_list_find(void *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, int follow_ptr,
1.22 - CxListComparator cmp_func, void *elem) {
1.23 +size_t cx_linked_list_find(
1.24 + void *start,
1.25 + ptrdiff_t loc_advance,
1.26 + ptrdiff_t loc_data,
1.27 + int follow_ptr,
1.28 + CxListComparator cmp_func,
1.29 + void *elem
1.30 +) {
1.31 assert(start != NULL);
1.32 assert(loc_advance >= 0);
1.33 assert(loc_data >= 0);
1.34 @@ -71,11 +82,17 @@
1.35 return index;
1.36 }
1.37
1.38 -void *cx_linked_list_first(void *node, ptrdiff_t loc_prev) {
1.39 +void *cx_linked_list_first(
1.40 + void *node,
1.41 + ptrdiff_t loc_prev
1.42 +) {
1.43 return cx_linked_list_last(node, loc_prev);
1.44 }
1.45
1.46 -void *cx_linked_list_last(void *node, ptrdiff_t loc_next) {
1.47 +void *cx_linked_list_last(
1.48 + void *node,
1.49 + ptrdiff_t loc_next
1.50 +) {
1.51 assert(node != NULL);
1.52 assert(loc_next >= 0);
1.53
1.54 @@ -88,7 +105,11 @@
1.55 return last;
1.56 }
1.57
1.58 -void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node) {
1.59 +void *cx_linked_list_prev(
1.60 + void *begin,
1.61 + ptrdiff_t loc_next,
1.62 + void *node
1.63 +) {
1.64 assert(begin != NULL);
1.65 assert(node != NULL);
1.66 assert(loc_next >= 0);
1.67 @@ -102,10 +123,41 @@
1.68 }
1.69 }
1.70
1.71 -void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
1.72 - assert(new_node != NULL);
1.73 +void cx_linked_list_link(
1.74 + void *left,
1.75 + void *right,
1.76 + ptrdiff_t loc_prev,
1.77 + ptrdiff_t loc_next
1.78 +) {
1.79 assert(loc_next >= 0);
1.80 - assert(ll_next(new_node) == NULL);
1.81 + ll_next(left) = right;
1.82 + if (loc_prev >= 0) {
1.83 + ll_prev(right) = left;
1.84 + }
1.85 +}
1.86 +
1.87 +void cx_linked_list_unlink(
1.88 + void *left,
1.89 + void *right,
1.90 + ptrdiff_t loc_prev,
1.91 + ptrdiff_t loc_next
1.92 +) {
1.93 + assert (loc_next >= 0);
1.94 + assert(ll_next(left) == right);
1.95 + ll_next(left) = NULL;
1.96 + if (loc_prev >= 0) {
1.97 + assert(ll_prev(right) == left);
1.98 + ll_prev(right) = NULL;
1.99 + }
1.100 +}
1.101 +
1.102 +void cx_linked_list_add(
1.103 + void **begin,
1.104 + void **end,
1.105 + ptrdiff_t loc_prev,
1.106 + ptrdiff_t loc_next,
1.107 + void *new_node
1.108 +) {
1.109 void *last;
1.110 if (end == NULL) {
1.111 assert(begin != NULL);
1.112 @@ -113,57 +165,76 @@
1.113 } else {
1.114 last = *end;
1.115 }
1.116 - if (last == NULL) {
1.117 + cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, last, new_node, new_node);
1.118 +}
1.119 +
1.120 +void cx_linked_list_prepend(
1.121 + void **begin,
1.122 + void **end,
1.123 + ptrdiff_t loc_prev,
1.124 + ptrdiff_t loc_next,
1.125 + void *new_node
1.126 +) {
1.127 + cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, NULL, new_node, new_node);
1.128 +}
1.129 +
1.130 +void cx_linked_list_insert(
1.131 + void **begin,
1.132 + void **end,
1.133 + ptrdiff_t loc_prev,
1.134 + ptrdiff_t loc_next,
1.135 + void *node,
1.136 + void *new_node
1.137 +) {
1.138 + cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, node, new_node, new_node);
1.139 +}
1.140 +
1.141 +void cx_linked_list_insert_chain(
1.142 + void **begin,
1.143 + void **end,
1.144 + ptrdiff_t loc_prev,
1.145 + ptrdiff_t loc_next,
1.146 + void *node,
1.147 + void *insert_begin,
1.148 + void *insert_end
1.149 +) {
1.150 + // find the end of the chain, if not specified
1.151 + if (insert_end == NULL) {
1.152 + insert_end = cx_linked_list_last(insert_begin, loc_next);
1.153 + }
1.154 +
1.155 + // determine the successor
1.156 + void *successor;
1.157 + if (node == NULL) {
1.158 + assert(begin != NULL || (end != NULL && loc_prev >= 0));
1.159 if (begin != NULL) {
1.160 - *begin = new_node;
1.161 + successor = *begin;
1.162 + *begin = insert_begin;
1.163 + } else {
1.164 + successor = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);
1.165 }
1.166 } else {
1.167 - // if there is a last node, update its next pointer
1.168 - ll_next(last) = new_node;
1.169 + successor = ll_next(node);
1.170 + cx_linked_list_link(node, insert_begin, loc_prev, loc_next);
1.171 }
1.172
1.173 - // if there is an end pointer, update it
1.174 - if (end != NULL) {
1.175 - *end = new_node;
1.176 - }
1.177 -
1.178 - // if the nodes use a prev pointer, update it
1.179 - if (loc_prev >= 0) {
1.180 - assert(ll_prev(new_node) == NULL);
1.181 - ll_prev(new_node) = last;
1.182 + if (successor == NULL) {
1.183 + // the list ends with the new chain
1.184 + if (end != NULL) {
1.185 + *end = insert_end;
1.186 + }
1.187 + } else {
1.188 + cx_linked_list_link(insert_end, successor, loc_prev, loc_next);
1.189 }
1.190 }
1.191
1.192 -void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
1.193 - assert(new_node != NULL);
1.194 - assert(loc_next >= 0);
1.195 - assert(ll_next(new_node) == NULL);
1.196 - void *first;
1.197 - if (begin == NULL) {
1.198 - assert(end != NULL);
1.199 - assert(loc_prev >= 0);
1.200 - first = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);
1.201 - } else {
1.202 - first = *begin;
1.203 - }
1.204 - if (first == NULL) {
1.205 - if (end != NULL) {
1.206 - *end = new_node;
1.207 - }
1.208 - } else {
1.209 - ll_next(new_node) = first;
1.210 - if (loc_prev >= 0) {
1.211 - ll_prev(first) = new_node;
1.212 - }
1.213 - }
1.214 -
1.215 - if (begin != NULL) {
1.216 - assert(loc_prev < 0 || ll_prev(new_node) == NULL);
1.217 - *begin = new_node;
1.218 - }
1.219 -}
1.220 -
1.221 -void cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) {
1.222 +void cx_linked_list_remove(
1.223 + void **begin,
1.224 + void **end,
1.225 + ptrdiff_t loc_prev,
1.226 + ptrdiff_t loc_next,
1.227 + void *node
1.228 +) {
1.229 assert(node != NULL);
1.230 assert(loc_next >= 0);
1.231 assert(loc_prev >= 0 || begin != NULL);
1.232 @@ -196,7 +267,10 @@
1.233 }
1.234 }
1.235
1.236 -size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
1.237 +size_t cx_linked_list_size(
1.238 + void *node,
1.239 + ptrdiff_t loc_next
1.240 +) {
1.241 assert(loc_next >= 0);
1.242 size_t size = 0;
1.243 while (node != NULL) {
1.244 @@ -206,10 +280,17 @@
1.245 return size;
1.246 }
1.247
1.248 -static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next,
1.249 - ptrdiff_t loc_data, int follow_ptr,
1.250 - size_t length, void *ls, void *le, void *re,
1.251 - CxListComparator cmp_func) {
1.252 +static void *cx_linked_list_sort_merge(
1.253 + ptrdiff_t loc_prev,
1.254 + ptrdiff_t loc_next,
1.255 + ptrdiff_t loc_data,
1.256 + int follow_ptr,
1.257 + size_t length,
1.258 + void *ls,
1.259 + void *le,
1.260 + void *re,
1.261 + CxListComparator cmp_func
1.262 +) {
1.263 const size_t sbo_len = 1024;
1.264 void *sbo[sbo_len];
1.265 void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
1.266 @@ -242,8 +323,7 @@
1.267 // Update pointer
1.268 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
1.269 for (size_t i = 0; i < length - 1; i++) {
1.270 - ll_next(sorted[i]) = sorted[i + 1];
1.271 - if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i];
1.272 + cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next);
1.273 }
1.274 ll_next(sorted[length - 1]) = NULL;
1.275
1.276 @@ -255,8 +335,14 @@
1.277 }
1.278
1.279 void cx_linked_list_sort( /* NOLINT(misc-no-recursion) - purposely recursive function */
1.280 - void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
1.281 - ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
1.282 + void **begin,
1.283 + void **end,
1.284 + ptrdiff_t loc_prev,
1.285 + ptrdiff_t loc_next,
1.286 + ptrdiff_t loc_data,
1.287 + int follow_ptr,
1.288 + CxListComparator cmp_func
1.289 +) {
1.290 assert(begin != NULL);
1.291 assert(loc_next >= 0);
1.292 assert(loc_data >= 0);
1.293 @@ -310,7 +396,12 @@
1.294 }
1.295 }
1.296
1.297 -void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) {
1.298 +void cx_linked_list_reverse(
1.299 + void **begin,
1.300 + void **end,
1.301 + ptrdiff_t loc_prev,
1.302 + ptrdiff_t loc_next
1.303 +) {
1.304 assert(begin != NULL);
1.305 assert(loc_next >= 0);
1.306
1.307 @@ -355,7 +446,10 @@
1.308 cx_linked_list_node *end;
1.309 } cx_linked_list;
1.310
1.311 -static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) {
1.312 +static cx_linked_list_node *cx_ll_node_at(
1.313 + cx_linked_list *list,
1.314 + size_t index
1.315 +) {
1.316 if (index >= list->base.size) {
1.317 return NULL;
1.318 } else if (index > list->base.size / 2) {
1.319 @@ -365,72 +459,69 @@
1.320 }
1.321 }
1.322
1.323 -static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
1.324 +static int cx_ll_insert(
1.325 + cx_list_s *list,
1.326 + size_t index,
1.327 + void *elem
1.328 +) {
1.329 // out-of bounds check
1.330 if (index > list->size) return 1;
1.331
1.332 // cast a linked list pointer
1.333 cx_linked_list *ll = (cx_linked_list *) list;
1.334
1.335 - // create the new node
1.336 - cx_linked_list_node *node = cxMalloc(list->allocator,
1.337 - sizeof(cx_linked_list_node) + list->itemsize);
1.338 + // create the new new_node
1.339 + cx_linked_list_node *new_node = cxMalloc(list->allocator,
1.340 + sizeof(cx_linked_list_node) + list->itemsize);
1.341
1.342 // sortir if failed
1.343 - if (node == NULL) return 1;
1.344 + if (new_node == NULL) return 1;
1.345
1.346 - // copy payload to the new node
1.347 - memcpy(node->payload, elem, list->itemsize);
1.348 + // initialize new new_node
1.349 + new_node->prev = new_node->next = NULL;
1.350 + memcpy(new_node->payload, elem, list->itemsize);
1.351
1.352 - // check if this is the first node
1.353 - if (ll->begin == NULL) {
1.354 - node->prev = node->next = NULL;
1.355 - ll->begin = ll->end = node;
1.356 - } else {
1.357 - // check if this shall be the new end node
1.358 - if (index == list->size) {
1.359 - ll->end->next = node;
1.360 - node->prev = ll->end;
1.361 - node->next = NULL;
1.362 - ll->end = node;
1.363 - }
1.364 - // check if this shall be the new start node
1.365 - else if (index == 0) {
1.366 - ll->begin->prev = node;
1.367 - node->next = ll->begin;
1.368 - node->prev = NULL;
1.369 - ll->begin = node;
1.370 - } else {
1.371 - // find the node at the current index
1.372 - cx_linked_list_node *cur = cx_ll_node_at(ll, index);
1.373 + // find position efficiently
1.374 + cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at(ll, index - 1);
1.375
1.376 - // insert before that node
1.377 - // (we know all ptr are non-null because we handled all other cases before)
1.378 - node->next = cur;
1.379 - node->prev = cur->prev;
1.380 - cur->prev = node;
1.381 - node->prev->next = node;
1.382 - }
1.383 - }
1.384 + // insert
1.385 + cx_linked_list_insert_chain(
1.386 + (void **) &ll->begin, (void **) &ll->end,
1.387 + CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
1.388 + node, new_node, new_node
1.389 + );
1.390
1.391 // increase the size and return
1.392 list->size++;
1.393 return 0;
1.394 }
1.395
1.396 -static int cx_ll_add(cx_list_s *list, void *elem) {
1.397 +static int cx_ll_add(
1.398 + cx_list_s *list,
1.399 + void *elem
1.400 +) {
1.401 return cx_ll_insert(list, list->size, elem);
1.402 }
1.403
1.404 -static int cx_pll_insert(cx_list_s *list, size_t index, void *elem) {
1.405 +static int cx_pll_insert(
1.406 + cx_list_s *list,
1.407 + size_t index,
1.408 + void *elem
1.409 +) {
1.410 return cx_ll_insert(list, index, &elem);
1.411 }
1.412
1.413 -static int cx_pll_add(cx_list_s *list, void *elem) {
1.414 +static int cx_pll_add(
1.415 + cx_list_s *list,
1.416 + void *elem
1.417 +) {
1.418 return cx_ll_insert(list, list->size, &elem);
1.419 }
1.420
1.421 -static int cx_ll_remove(cx_list_s *list, size_t index) {
1.422 +static int cx_ll_remove(
1.423 + cx_list_s *list,
1.424 + size_t index
1.425 +) {
1.426 cx_linked_list *ll = (cx_linked_list *) list;
1.427 cx_linked_list_node *node = cx_ll_node_at(ll, index);
1.428
1.429 @@ -450,25 +541,37 @@
1.430 return 0;
1.431 }
1.432
1.433 -static void *cx_ll_at(cx_list_s *list, size_t index) {
1.434 +static void *cx_ll_at(
1.435 + cx_list_s *list,
1.436 + size_t index
1.437 +) {
1.438 cx_linked_list *ll = (cx_linked_list *) list;
1.439 cx_linked_list_node *node = cx_ll_node_at(ll, index);
1.440 return node == NULL ? NULL : node->payload;
1.441 }
1.442
1.443 -static void *cx_pll_at(cx_list_s *list, size_t index) {
1.444 +static void *cx_pll_at(
1.445 + cx_list_s *list,
1.446 + size_t index
1.447 +) {
1.448 cx_linked_list *ll = (cx_linked_list *) list;
1.449 cx_linked_list_node *node = cx_ll_node_at(ll, index);
1.450 return node == NULL ? NULL : *(void **) node->payload;
1.451 }
1.452
1.453 -static size_t cx_ll_find(cx_list_s *list, void *elem) {
1.454 +static size_t cx_ll_find(
1.455 + cx_list_s *list,
1.456 + void *elem
1.457 +) {
1.458 return cx_linked_list_find(((cx_linked_list *) list)->begin,
1.459 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
1.460 0, list->cmpfunc, elem);
1.461 }
1.462
1.463 -static size_t cx_pll_find(cx_list_s *list, void *elem) {
1.464 +static size_t cx_pll_find(
1.465 + cx_list_s *list,
1.466 + void *elem
1.467 +) {
1.468 return cx_linked_list_find(((cx_linked_list *) list)->begin,
1.469 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
1.470 1, list->cmpfunc, elem);
1.471 @@ -506,7 +609,11 @@
1.472 cx_pll_sort
1.473 };
1.474
1.475 -CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {
1.476 +CxList cxLinkedListCreate(
1.477 + CxAllocator allocator,
1.478 + CxListComparator comparator,
1.479 + size_t item_size
1.480 +) {
1.481 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
1.482 if (list == NULL)
1.483 return NULL;
1.484 @@ -524,7 +631,10 @@
1.485 return (CxList) list;
1.486 }
1.487
1.488 -CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator) {
1.489 +CxList cxPointerLinkedListCreate(
1.490 + CxAllocator allocator,
1.491 + CxListComparator comparator
1.492 +) {
1.493 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
1.494 if (list == NULL)
1.495 return NULL;
