ucx/linked_list.c

   1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
   3  *
   4  * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions are met:
   8  *
   9  *   1. Redistributions of source code must retain the above copyright
  10  *      notice, this list of conditions and the following disclaimer.
  11  *
  12  *   2. Redistributions in binary form must reproduce the above copyright
  13  *      notice, this list of conditions and the following disclaimer in the
  14  *      documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  26  * POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 #include "cx/linked_list.h"
  30 #include "cx/utils.h"
  31 #include <string.h>
  32 #include <assert.h>
  33
  34 // LOW LEVEL LINKED LIST FUNCTIONS
  35
  36 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
  37 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
  38 #define ll_next(node) CX_LL_PTR(node, loc_next)
  39 #define ll_advance(node) CX_LL_PTR(node, loc_advance)
  40 #define ll_data(node) (((char*)(node))+loc_data)
  41
  42 void *cx_linked_list_at(
  43         void const *start,
  44         size_t start_index,
  45         ptrdiff_t loc_advance,
  46         size_t index
  47 ) {
  48     assert(start != NULL);
  49     assert(loc_advance >= 0);
  50     size_t i = start_index;
  51     void const *cur = start;
  52     while (i != index && cur != NULL) {
  53         cur = ll_advance(cur);
  54         i < index ? i++ : i--;
  55     }
  56     return (void *) cur;
  57 }
  58
  59 size_t cx_linked_list_find(
  60         void const *start,
  61         ptrdiff_t loc_advance,
  62         ptrdiff_t loc_data,
  63         CxListComparator cmp_func,
  64         void const *elem
  65 ) {
  66     assert(start != NULL);
  67     assert(loc_advance >= 0);
  68     assert(loc_data >= 0);
  69     assert(cmp_func);
  70
  71     void const *node = start;
  72     size_t index = 0;
  73     do {
  74         void *current = ll_data(node);
  75         if (cmp_func(current, elem) == 0) {
  76             return index;
  77         }
  78         node = ll_advance(node);
  79         index++;
  80     } while (node != NULL);
  81     return index;
  82 }
  83
  84 void *cx_linked_list_first(
  85         void const *node,
  86         ptrdiff_t loc_prev
  87 ) {
  88     return cx_linked_list_last(node, loc_prev);
  89 }
  90
  91 void *cx_linked_list_last(
  92         void const *node,
  93         ptrdiff_t loc_next
  94 ) {
  95     assert(node != NULL);
  96     assert(loc_next >= 0);
  97
  98     void const *cur = node;
  99     void const *last;
 100     do {
 101         last = cur;
 102     } while ((cur = ll_next(cur)) != NULL);
 103
 104     return (void *) last;
 105 }
 106
 107 void *cx_linked_list_prev(
 108         void const *begin,
 109         ptrdiff_t loc_next,
 110         void const *node
 111 ) {
 112     assert(begin != NULL);
 113     assert(node != NULL);
 114     assert(loc_next >= 0);
 115     if (begin == node) return NULL;
 116     void const *cur = begin;
 117     void const *next;
 118     while (1) {
 119         next = ll_next(cur);
 120         if (next == node) return (void *) cur;
 121         cur = next;
 122     }
 123 }
 124
 125 void cx_linked_list_link(
 126         void *left,
 127         void *right,
 128         ptrdiff_t loc_prev,
 129         ptrdiff_t loc_next
 130 ) {
 131     assert(loc_next >= 0);
 132     ll_next(left) = right;
 133     if (loc_prev >= 0) {
 134         ll_prev(right) = left;
 135     }
 136 }
 137
 138 void cx_linked_list_unlink(
 139         void *left,
 140         void *right,
 141         ptrdiff_t loc_prev,
 142         ptrdiff_t loc_next
 143 ) {
 144     assert (loc_next >= 0);
 145     assert(ll_next(left) == right);
 146     ll_next(left) = NULL;
 147     if (loc_prev >= 0) {
 148         assert(ll_prev(right) == left);
 149         ll_prev(right) = NULL;
 150     }
 151 }
 152
 153 void cx_linked_list_add(
 154         void **begin,
 155         void **end,
 156         ptrdiff_t loc_prev,
 157         ptrdiff_t loc_next,
 158         void *new_node
 159 ) {
 160     void *last;
 161     if (end == NULL) {
 162         assert(begin != NULL);
 163         last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next);
 164     } else {
 165         last = *end;
 166     }
 167     cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, last, new_node, new_node);
 168 }
 169
 170 void cx_linked_list_prepend(
 171         void **begin,
 172         void **end,
 173         ptrdiff_t loc_prev,
 174         ptrdiff_t loc_next,
 175         void *new_node
 176 ) {
 177     cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, NULL, new_node, new_node);
 178 }
 179
 180 void cx_linked_list_insert(
 181         void **begin,
 182         void **end,
 183         ptrdiff_t loc_prev,
 184         ptrdiff_t loc_next,
 185         void *node,
 186         void *new_node
 187 ) {
 188     cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, node, new_node, new_node);
 189 }
 190
 191 void cx_linked_list_insert_chain(
 192         void **begin,
 193         void **end,
 194         ptrdiff_t loc_prev,
 195         ptrdiff_t loc_next,
 196         void *node,
 197         void *insert_begin,
 198         void *insert_end
 199 ) {
 200     // find the end of the chain, if not specified
 201     if (insert_end == NULL) {
 202         insert_end = cx_linked_list_last(insert_begin, loc_next);
 203     }
 204
 205     // determine the successor
 206     void *successor;
 207     if (node == NULL) {
 208         assert(begin != NULL || (end != NULL && loc_prev >= 0));
 209         if (begin != NULL) {
 210             successor = *begin;
 211             *begin = insert_begin;
 212         } else {
 213             successor = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);
 214         }
 215     } else {
 216         successor = ll_next(node);
 217         cx_linked_list_link(node, insert_begin, loc_prev, loc_next);
 218     }
 219
 220     if (successor == NULL) {
 221         // the list ends with the new chain
 222         if (end != NULL) {
 223             *end = insert_end;
 224         }
 225     } else {
 226         cx_linked_list_link(insert_end, successor, loc_prev, loc_next);
 227     }
 228 }
 229
 230 void cx_linked_list_remove(
 231         void **begin,
 232         void **end,
 233         ptrdiff_t loc_prev,
 234         ptrdiff_t loc_next,
 235         void *node
 236 ) {
 237     assert(node != NULL);
 238     assert(loc_next >= 0);
 239     assert(loc_prev >= 0 || begin != NULL);
 240
 241     // find adjacent nodes
 242     void *next = ll_next(node);
 243     void *prev;
 244     if (loc_prev >= 0) {
 245         prev = ll_prev(node);
 246     } else {
 247         prev = cx_linked_list_prev(*begin, loc_next, node);
 248     }
 249
 250     // update next pointer of prev node, or set begin
 251     if (prev == NULL) {
 252         if (begin != NULL) {
 253             *begin = next;
 254         }
 255     } else {
 256         ll_next(prev) = next;
 257     }
 258
 259     // update prev pointer of next node, or set end
 260     if (next == NULL) {
 261         if (end != NULL) {
 262             *end = prev;
 263         }
 264     } else if (loc_prev >= 0) {
 265         ll_prev(next) = prev;
 266     }
 267 }
 268
 269 size_t cx_linked_list_size(
 270         void const *node,
 271         ptrdiff_t loc_next
 272 ) {
 273     assert(loc_next >= 0);
 274     size_t size = 0;
 275     while (node != NULL) {
 276         node = ll_next(node);
 277         size++;
 278     }
 279     return size;
 280 }
 281
 282 #ifndef CX_LINKED_LIST_SORT_SBO_SIZE
 283 #define CX_LINKED_LIST_SORT_SBO_SIZE 1024
 284 #endif
 285
 286 static void *cx_linked_list_sort_merge(
 287         ptrdiff_t loc_prev,
 288         ptrdiff_t loc_next,
 289         ptrdiff_t loc_data,
 290         size_t length,
 291         void *ls,
 292         void *le,
 293         void *re,
 294         CxListComparator cmp_func
 295 ) {
 296     void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE];
 297     void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ?
 298                     malloc(sizeof(void *) * length) : sbo;
 299     if (sorted == NULL) abort();
 300     void *rc, *lc;
 301
 302     lc = ls;
 303     rc = le;
 304     size_t n = 0;
 305     while (lc && lc != le && rc != re) {
 306         if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
 307             sorted[n] = lc;
 308             lc = ll_next(lc);
 309         } else {
 310             sorted[n] = rc;
 311             rc = ll_next(rc);
 312         }
 313         n++;
 314     }
 315     while (lc && lc != le) {
 316         sorted[n] = lc;
 317         lc = ll_next(lc);
 318         n++;
 319     }
 320     while (rc && rc != re) {
 321         sorted[n] = rc;
 322         rc = ll_next(rc);
 323         n++;
 324     }
 325
 326     // Update pointer
 327     if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
 328     cx_for_n (i, length - 1) {
 329         cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next);
 330     }
 331     ll_next(sorted[length - 1]) = NULL;
 332
 333     void *ret = sorted[0];
 334     if (sorted != sbo) {
 335         free(sorted);
 336     }
 337     return ret;
 338 }
 339
 340 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function
 341         void **begin,
 342         void **end,
 343         ptrdiff_t loc_prev,
 344         ptrdiff_t loc_next,
 345         ptrdiff_t loc_data,
 346         CxListComparator cmp_func
 347 ) {
 348     assert(begin != NULL);
 349     assert(loc_next >= 0);
 350     assert(loc_data >= 0);
 351     assert(cmp_func);
 352
 353     void *lc, *ls, *le, *re;
 354
 355     // set start node
 356     ls = *begin;
 357
 358     // check how many elements are already sorted
 359     lc = ls;
 360     size_t ln = 1;
 361     while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
 362         lc = ll_next(lc);
 363         ln++;
 364     }
 365     le = ll_next(lc);
 366
 367     // if first unsorted node is NULL, the list is already completely sorted
 368     if (le != NULL) {
 369         void *rc;
 370         size_t rn = 1;
 371         rc = le;
 372         // skip already sorted elements
 373         while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
 374             rc = ll_next(rc);
 375             rn++;
 376         }
 377         re = ll_next(rc);
 378
 379         // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
 380         void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
 381                                                  ln + rn, ls, le, re, cmp_func);
 382
 383         // Something left? Sort it!
 384         size_t remainder_length = cx_linked_list_size(re, loc_next);
 385         if (remainder_length > 0) {
 386             void *remainder = re;
 387             cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func);
 388
 389             // merge sorted list with (also sorted) remainder
 390             *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
 391                                                ln + rn + remainder_length,
 392                                                sorted, remainder, NULL, cmp_func);
 393         } else {
 394             // no remainder - we've got our sorted list
 395             *begin = sorted;
 396         }
 397         if (end) *end = cx_linked_list_last(sorted, loc_next);
 398     }
 399 }
 400
 401 int cx_linked_list_compare(
 402         void const *begin_left,
 403         void const *begin_right,
 404         ptrdiff_t loc_advance,
 405         ptrdiff_t loc_data,
 406         CxListComparator cmp_func
 407 ) {
 408     void const *left = begin_left, *right = begin_right;
 409
 410     while (left != NULL && right != NULL) {
 411         void const *left_data = ll_data(left);
 412         void const *right_data = ll_data(right);
 413         int result = cmp_func(left_data, right_data);
 414         if (result != 0) return result;
 415         left = ll_advance(left);
 416         right = ll_advance(right);
 417     }
 418
 419     if (left != NULL) { return 1; }
 420     else if (right != NULL) { return -1; }
 421     else { return 0; }
 422 }
 423
 424 void cx_linked_list_reverse(
 425         void **begin,
 426         void **end,
 427         ptrdiff_t loc_prev,
 428         ptrdiff_t loc_next
 429 ) {
 430     assert(begin != NULL);
 431     assert(loc_next >= 0);
 432
 433     // swap all links
 434     void *prev = NULL;
 435     void *cur = *begin;
 436     while (cur != NULL) {
 437         void *next = ll_next(cur);
 438
 439         ll_next(cur) = prev;
 440         if (loc_prev >= 0) {
 441             ll_prev(cur) = next;
 442         }
 443
 444         prev = cur;
 445         cur = next;
 446     }
 447
 448     // update begin and end
 449     if (end != NULL) {
 450         *end = *begin;
 451     }
 452     *begin = prev;
 453 }
 454
 455 // HIGH LEVEL LINKED LIST IMPLEMENTATION
 456
 457 bool CX_DISABLE_LINKED_LIST_SWAP_SBO = false;
 458
 459 typedef struct cx_linked_list_node cx_linked_list_node;
 460 struct cx_linked_list_node {
 461     cx_linked_list_node *prev;
 462     cx_linked_list_node *next;
 463     char payload[];
 464 };
 465
 466 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
 467 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
 468 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
 469
 470 typedef struct {
 471     struct cx_list_s base;
 472     cx_linked_list_node *begin;
 473     cx_linked_list_node *end;
 474 } cx_linked_list;
 475
 476 static cx_linked_list_node *cx_ll_node_at(
 477         cx_linked_list const *list,
 478         size_t index
 479 ) {
 480     if (index >= list->base.size) {
 481         return NULL;
 482     } else if (index > list->base.size / 2) {
 483         return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
 484     } else {
 485         return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
 486     }
 487 }
 488
 489 static int cx_ll_insert_at(
 490         struct cx_list_s *list,
 491         cx_linked_list_node *node,
 492         void const *elem
 493 ) {
 494
 495     // create the new new_node
 496     cx_linked_list_node *new_node = cxMalloc(list->allocator,
 497                                              sizeof(cx_linked_list_node) + list->itemsize);
 498
 499     // sortir if failed
 500     if (new_node == NULL) return 1;
 501
 502     // initialize new new_node
 503     new_node->prev = new_node->next = NULL;
 504     memcpy(new_node->payload, elem, list->itemsize);
 505
 506     // insert
 507     cx_linked_list *ll = (cx_linked_list *) list;
 508     cx_linked_list_insert_chain(
 509             (void **) &ll->begin, (void **) &ll->end,
 510             CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
 511             node, new_node, new_node
 512     );
 513
 514     // increase the size and return
 515     list->size++;
 516     return 0;
 517 }
 518
 519 static size_t cx_ll_insert_array(
 520         struct cx_list_s *list,
 521         size_t index,
 522         void const *array,
 523         size_t n
 524 ) {
 525     // out-of bounds and corner case check
 526     if (index > list->size || n == 0) return 0;
 527
 528     // find position efficiently
 529     cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
 530
 531     // perform first insert
 532     if (0 != cx_ll_insert_at(list, node, array)) {
 533         return 1;
 534     }
 535
 536     // is there more?
 537     if (n == 1) return 1;
 538
 539     // we now know exactly where we are
 540     node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
 541
 542     // we can add the remaining nodes and immedately advance to the inserted node
 543     char const *source = array;
 544     for (size_t i = 1; i < n; i++) {
 545         source += list->itemsize;
 546         if (0 != cx_ll_insert_at(list, node, source)) {
 547             return i;
 548         }
 549         node = node->next;
 550     }
 551     return n;
 552 }
 553
 554 static int cx_ll_insert_element(
 555         struct cx_list_s *list,
 556         size_t index,
 557         void const *element
 558 ) {
 559     return 1 != cx_ll_insert_array(list, index, element, 1);
 560 }
 561
 562 static int cx_ll_remove(
 563         struct cx_list_s *list,
 564         size_t index
 565 ) {
 566     cx_linked_list *ll = (cx_linked_list *) list;
 567     cx_linked_list_node *node = cx_ll_node_at(ll, index);
 568
 569     // out-of-bounds check
 570     if (node == NULL) return 1;
 571
 572     // element destruction
 573     if (list->content_destructor_type != CX_DESTRUCTOR_NONE) {
 574         cx_list_invoke_destructor(list, node->payload);
 575     }
 576
 577     // remove
 578     cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
 579                           CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
 580
 581     // adjust size
 582     list->size--;
 583
 584     // free and return
 585     cxFree(list->allocator, node);
 586
 587     return 0;
 588 }
 589
 590 static void cx_ll_clear(struct cx_list_s *list) {
 591     if (list->size == 0) return;
 592
 593     cx_linked_list *ll = (cx_linked_list *) list;
 594     cx_linked_list_node *node = ll->begin;
 595
 596     // looks super redundant, but avoids repeatedly checking
 597     // the destructor type for each element
 598     switch (list->content_destructor_type) {
 599         case CX_DESTRUCTOR_SIMPLE: {
 600             while (node != NULL) {
 601                 cx_list_invoke_simple_destructor(list, node->payload);
 602                 cx_linked_list_node *next = node->next;
 603                 cxFree(list->allocator, node);
 604                 node = next;
 605             }
 606             break;
 607         }
 608         case CX_DESTRUCTOR_ADVANCED: {
 609             while (node != NULL) {
 610                 cx_list_invoke_advanced_destructor(list, node->payload);
 611                 cx_linked_list_node *next = node->next;
 612                 cxFree(list->allocator, node);
 613                 node = next;
 614             }
 615             break;
 616         }
 617         case CX_DESTRUCTOR_NONE: {
 618             while (node != NULL) {
 619                 cx_linked_list_node *next = node->next;
 620                 cxFree(list->allocator, node);
 621                 node = next;
 622             }
 623             break;
 624         }
 625     }
 626
 627     ll->begin = ll->end = NULL;
 628     list->size = 0;
 629 }
 630
 631 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
 632 #define CX_LINKED_LIST_SWAP_SBO_SIZE 16
 633 #endif
 634
 635 static int cx_ll_swap(
 636         struct cx_list_s *list,
 637         size_t i,
 638         size_t j
 639 ) {
 640     if (i >= list->size || j >= list->size) return 1;
 641     if (i == j) return 0;
 642
 643     // perform an optimized search that finds both elements in one run
 644     cx_linked_list *ll = (cx_linked_list *) list;
 645     size_t mid = list->size / 2;
 646     size_t left, right;
 647     if (i < j) {
 648         left = i;
 649         right = j;
 650     } else {
 651         left = j;
 652         right = i;
 653     }
 654     cx_linked_list_node *nleft, *nright;
 655     if (left < mid && right < mid) {
 656         // case 1: both items left from mid
 657         nleft = cx_ll_node_at(ll, left);
 658         nright = nleft;
 659         for (size_t c = left; c < right; c++) {
 660             nright = nright->next;
 661         }
 662     } else if (left >= mid && right >= mid) {
 663         // case 2: both items right from mid
 664         nright = cx_ll_node_at(ll, right);
 665         nleft = nright;
 666         for (size_t c = right; c > left; c--) {
 667             nleft = nleft->prev;
 668         }
 669     } else {
 670         // case 3: one item left, one item right
 671
 672         // chose the closest to begin / end
 673         size_t closest;
 674         size_t other;
 675         size_t diff2boundary = list->size - right - 1;
 676         if (left <= diff2boundary) {
 677             closest = left;
 678             other = right;
 679             nleft = cx_ll_node_at(ll, left);
 680         } else {
 681             closest = right;
 682             other = left;
 683             diff2boundary = left;
 684             nright = cx_ll_node_at(ll, right);
 685         }
 686
 687         // is other element closer to us or closer to boundary?
 688         if (right - left <= diff2boundary) {
 689             // search other element starting from already found element
 690             if (closest == left) {
 691                 nright = nleft;
 692                 for (size_t c = left; c < right; c++) {
 693                     nright = nright->next;
 694                 }
 695             } else {
 696                 nleft = nright;
 697                 for (size_t c = right; c > left; c--) {
 698                     nleft = nleft->prev;
 699                 }
 700             }
 701         } else {
 702             // search other element starting at the boundary
 703             if (closest == left) {
 704                 nright = cx_ll_node_at(ll, other);
 705             } else {
 706                 nleft = cx_ll_node_at(ll, other);
 707             }
 708         }
 709     }
 710
 711     if (list->itemsize > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) {
 712         cx_linked_list_node *prev = nleft->prev;
 713         cx_linked_list_node *next = nright->next;
 714         cx_linked_list_node *midstart = nleft->next;
 715         cx_linked_list_node *midend = nright->prev;
 716
 717         if (prev == NULL) {
 718             ll->begin = nright;
 719         } else {
 720             prev->next = nright;
 721         }
 722         nright->prev = prev;
 723         if (midstart == nright) {
 724             // special case: both nodes are adjacent
 725             nright->next = nleft;
 726             nleft->prev = nright;
 727         } else {
 728             // likely case: a chain is between the two nodes
 729             nright->next = midstart;
 730             midstart->prev = nright;
 731             midend->next = nleft;
 732             nleft->prev = midend;
 733         }
 734         nleft->next = next;
 735         if (next == NULL) {
 736             ll->end = nleft;
 737         } else {
 738             next->prev = nleft;
 739         }
 740     } else {
 741         // swap payloads to avoid relinking
 742         char buf[CX_LINKED_LIST_SWAP_SBO_SIZE];
 743         memcpy(buf, nleft->payload, list->itemsize);
 744         memcpy(nleft->payload, nright->payload, list->itemsize);
 745         memcpy(nright->payload, buf, list->itemsize);
 746     }
 747
 748     return 0;
 749 }
 750
 751 static void *cx_ll_at(
 752         struct cx_list_s const *list,
 753         size_t index
 754 ) {
 755     cx_linked_list *ll = (cx_linked_list *) list;
 756     cx_linked_list_node *node = cx_ll_node_at(ll, index);
 757     return node == NULL ? NULL : node->payload;
 758 }
 759
 760 static size_t cx_ll_find(
 761         struct cx_list_s const *list,
 762         void const *elem
 763 ) {
 764     return cx_linked_list_find(((cx_linked_list *) list)->begin,
 765                                CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
 766                                list->cmpfunc, elem);
 767 }
 768
 769 static void cx_ll_sort(struct cx_list_s *list) {
 770     cx_linked_list *ll = (cx_linked_list *) list;
 771     cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
 772                         CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
 773                         list->cmpfunc);
 774 }
 775
 776 static void cx_ll_reverse(struct cx_list_s *list) {
 777     cx_linked_list *ll = (cx_linked_list *) list;
 778     cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT);
 779 }
 780
 781 static int cx_ll_compare(
 782         struct cx_list_s const *list,
 783         struct cx_list_s const *other
 784 ) {
 785     cx_linked_list *left = (cx_linked_list *) list;
 786     cx_linked_list *right = (cx_linked_list *) other;
 787     return cx_linked_list_compare(left->begin, right->begin,
 788                                   CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
 789                                   list->cmpfunc);
 790 }
 791
 792 static bool cx_ll_iter_valid(void const *it) {
 793     struct cx_iterator_s const *iter = it;
 794     return iter->elem_handle != NULL;
 795 }
 796
 797 static void cx_ll_iter_next(void *it) {
 798     struct cx_iterator_base_s *itbase = it;
 799     if (itbase->remove) {
 800         itbase->remove = false;
 801         struct cx_mut_iterator_s *iter = it;
 802         struct cx_list_s *list = iter->src_handle;
 803         cx_linked_list *ll = iter->src_handle;
 804         cx_linked_list_node *node = iter->elem_handle;
 805         iter->elem_handle = node->next;
 806         if (list->content_destructor_type != CX_DESTRUCTOR_NONE) {
 807             cx_list_invoke_destructor(list, node->payload);
 808         }
 809         cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
 810                               CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
 811         list->size--;
 812         cxFree(list->allocator, node);
 813     } else {
 814         struct cx_iterator_s *iter = it;
 815         iter->index++;
 816         cx_linked_list_node *node = iter->elem_handle;
 817         iter->elem_handle = node->next;
 818     }
 819 }
 820
 821 static void cx_ll_iter_prev(void *it) {
 822     struct cx_iterator_base_s *itbase = it;
 823     if (itbase->remove) {
 824         itbase->remove = false;
 825         struct cx_mut_iterator_s *iter = it;
 826         struct cx_list_s *list = iter->src_handle;
 827         cx_linked_list *ll = iter->src_handle;
 828         cx_linked_list_node *node = iter->elem_handle;
 829         iter->elem_handle = node->prev;
 830         iter->index--;
 831         if (list->content_destructor_type != CX_DESTRUCTOR_NONE) {
 832             cx_list_invoke_destructor(list, node->payload);
 833         }
 834         cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
 835                               CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
 836         list->size--;
 837         cxFree(list->allocator, node);
 838     } else {
 839         struct cx_iterator_s *iter = it;
 840         iter->index--;
 841         cx_linked_list_node *node = iter->elem_handle;
 842         iter->elem_handle = node->prev;
 843     }
 844 }
 845
 846 static void *cx_ll_iter_current(void const *it) {
 847     struct cx_iterator_s const *iter = it;
 848     cx_linked_list_node *node = iter->elem_handle;
 849     return node->payload;
 850 }
 851
 852 static bool cx_ll_iter_flag_rm(void *it) {
 853     struct cx_iterator_base_s *iter = it;
 854     if (iter->mutating) {
 855         iter->remove = true;
 856         return true;
 857     } else {
 858         return false;
 859     }
 860 }
 861
 862 static CxIterator cx_ll_iterator(
 863         struct cx_list_s const *list,
 864         size_t index,
 865         bool backwards
 866 ) {
 867     CxIterator iter;
 868     iter.index = index;
 869     iter.src_handle = list;
 870     iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index);
 871     iter.base.valid = cx_ll_iter_valid;
 872     iter.base.current = cx_ll_iter_current;
 873     iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next;
 874     iter.base.flag_removal = cx_ll_iter_flag_rm;
 875     iter.base.mutating = false;
 876     iter.base.remove = false;
 877     return iter;
 878 }
 879
 880 static int cx_ll_insert_iter(
 881         CxMutIterator *iter,
 882         void const *elem,
 883         int prepend
 884 ) {
 885     struct cx_list_s *list = iter->src_handle;
 886     cx_linked_list_node *node = iter->elem_handle;
 887     if (node != NULL) {
 888         assert(prepend >= 0 && prepend <= 1);
 889         cx_linked_list_node *choice[2] = {node, node->prev};
 890         int result = cx_ll_insert_at(list, choice[prepend], elem);
 891         iter->index += prepend * (0 == result);
 892         return result;
 893     } else {
 894         int result = cx_ll_insert_element(list, list->size, elem);
 895         iter->index = list->size;
 896         return result;
 897     }
 898 }
 899
 900 static void cx_ll_destructor(CxList *list) {
 901     cx_linked_list *ll = (cx_linked_list *) list;
 902
 903     cx_linked_list_node *node = ll->begin;
 904     while (node) {
 905         void *next = node->next;
 906         cxFree(list->allocator, node);
 907         node = next;
 908     }
 909     // do not free the list pointer, this is just a destructor!
 910 }
 911
 912 static cx_list_class cx_linked_list_class = {
 913         cx_ll_destructor,
 914         cx_ll_insert_element,
 915         cx_ll_insert_array,
 916         cx_ll_insert_iter,
 917         cx_ll_remove,
 918         cx_ll_clear,
 919         cx_ll_swap,
 920         cx_ll_at,
 921         cx_ll_find,
 922         cx_ll_sort,
 923         cx_ll_compare,
 924         cx_ll_reverse,
 925         cx_ll_iterator,
 926 };
 927
 928 CxList *cxLinkedListCreate(
 929         CxAllocator const *allocator,
 930         CxListComparator comparator,
 931         size_t item_size
 932 ) {
 933     if (allocator == NULL) {
 934         allocator = cxDefaultAllocator;
 935     }
 936
 937     cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
 938     if (list == NULL) return NULL;
 939
 940     list->base.cl = &cx_linked_list_class;
 941     list->base.allocator = allocator;
 942     list->base.cmpfunc = comparator;
 943     list->base.capacity = SIZE_MAX;
 944
 945     if (item_size > 0) {
 946         list->base.itemsize = item_size;
 947     } else {
 948         cxListStorePointers((CxList *) list);
 949     }
 950
 951     return (CxList *) list;
 952 }