1.1 --- a/src/linked_list.c Wed Feb 08 18:56:58 2023 +0100
1.2 +++ b/src/linked_list.c Wed Feb 08 20:26:09 2023 +0100
1.3 @@ -451,6 +451,8 @@
1.4
1.5 // HIGH LEVEL LINKED LIST IMPLEMENTATION
1.6
1.7 +bool CX_DISABLE_LINKED_LIST_SWAP_SBO = false;
1.8 +
1.9 typedef struct cx_linked_list_node cx_linked_list_node;
1.10 struct cx_linked_list_node {
1.11 cx_linked_list_node *prev;
1.12 @@ -577,6 +579,126 @@
1.13 return 0;
1.14 }
1.15
1.16 +#ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
1.17 +#define CX_LINKED_LIST_SWAP_SBO_SIZE 16
1.18 +#endif
1.19 +
1.20 +static int cx_ll_swap(
1.21 + struct cx_list_s *list,
1.22 + size_t i,
1.23 + size_t j
1.24 +) {
1.25 + if (i >= list->size || j >= list->size) return 1;
1.26 + if (i == j) return 0;
1.27 +
1.28 + // perform an optimized search that finds both elements in one run
1.29 + cx_linked_list *ll = (cx_linked_list *) list;
1.30 + size_t mid = list->size / 2;
1.31 + size_t left, right;
1.32 + if (i < j) {
1.33 + left = i;
1.34 + right = j;
1.35 + } else {
1.36 + left = j;
1.37 + right = i;
1.38 + }
1.39 + cx_linked_list_node *nleft, *nright;
1.40 + if (left < mid && right < mid) {
1.41 + // case 1: both items left from mid
1.42 + nleft = cx_ll_node_at(ll, left);
1.43 + nright = nleft;
1.44 + for (size_t c = left; c < right; c++) {
1.45 + nright = nright->next;
1.46 + }
1.47 + } else if (left >= mid && right >= mid) {
1.48 + // case 2: both items right from mid
1.49 + nright = cx_ll_node_at(ll, right);
1.50 + nleft = nright;
1.51 + for (size_t c = right; c > left; c--) {
1.52 + nleft = nleft->prev;
1.53 + }
1.54 + } else {
1.55 + // case 3: one item left, one item right
1.56 +
1.57 + // chose the closest to begin / end
1.58 + size_t closest;
1.59 + size_t other;
1.60 + size_t diff2boundary = list->size - right - 1;
1.61 + if (left <= diff2boundary) {
1.62 + closest = left;
1.63 + other = right;
1.64 + nleft = cx_ll_node_at(ll, left);
1.65 + } else {
1.66 + closest = right;
1.67 + other = left;
1.68 + diff2boundary = left;
1.69 + nright = cx_ll_node_at(ll, right);
1.70 + }
1.71 +
1.72 + // is other element closer to us or closer to boundary?
1.73 + if (right - left <= diff2boundary) {
1.74 + // search other element starting from already found element
1.75 + if (closest == left) {
1.76 + nright = nleft;
1.77 + for (size_t c = left; c < right; c++) {
1.78 + nright = nright->next;
1.79 + }
1.80 + } else {
1.81 + nleft = nright;
1.82 + for (size_t c = right; c > left; c--) {
1.83 + nleft = nleft->prev;
1.84 + }
1.85 + }
1.86 + } else {
1.87 + // search other element starting at the boundary
1.88 + if (closest == left) {
1.89 + nright = cx_ll_node_at(ll, other);
1.90 + } else {
1.91 + nleft = cx_ll_node_at(ll, other);
1.92 + }
1.93 + }
1.94 + }
1.95 +
1.96 + if (list->itemsize > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) {
1.97 + cx_linked_list_node *prev = nleft->prev;
1.98 + cx_linked_list_node *next = nright->next;
1.99 + cx_linked_list_node *midstart = nleft->next;
1.100 + cx_linked_list_node *midend = nright->prev;
1.101 +
1.102 + if (prev == NULL) {
1.103 + ll->begin = nright;
1.104 + } else {
1.105 + prev->next = nright;
1.106 + }
1.107 + nright->prev = prev;
1.108 + if (midstart == nright) {
1.109 + // special case: both nodes are adjacent
1.110 + nright->next = nleft;
1.111 + nleft->prev = nright;
1.112 + } else {
1.113 + // likely case: a chain is between the two nodes
1.114 + nright->next = midstart;
1.115 + midstart->prev = nright;
1.116 + midend->next = nleft;
1.117 + nleft->prev = midend;
1.118 + }
1.119 + nleft->next = next;
1.120 + if (next == NULL) {
1.121 + ll->end = nleft;
1.122 + } else {
1.123 + next->prev = nleft;
1.124 + }
1.125 + } else {
1.126 + // swap payloads to avoid relinking
1.127 + char buf[CX_LINKED_LIST_SWAP_SBO_SIZE];
1.128 + memcpy(buf, nleft->payload, list->itemsize);
1.129 + memcpy(nleft->payload, nright->payload, list->itemsize);
1.130 + memcpy(nright->payload, buf, list->itemsize);
1.131 + }
1.132 +
1.133 + return 0;
1.134 +}
1.135 +
1.136 static void *cx_ll_at(
1.137 struct cx_list_s const *list,
1.138 size_t index
1.139 @@ -714,6 +836,7 @@
1.140 cx_ll_insert_array,
1.141 cx_ll_insert_iter,
1.142 cx_ll_remove,
1.143 + cx_ll_swap,
1.144 cx_ll_at,
1.145 cx_ll_find,
1.146 cx_ll_sort,
