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 ssize_t cx_linked_list_find(
  60         void const *start,
  61         ptrdiff_t loc_advance,
  62         ptrdiff_t loc_data,
  63         cx_compare_func 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     ssize_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 -1;
  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         cx_compare_func cmp_func,
 295         void **begin,
 296         void **end
 297 ) {
 298     void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE];
 299     void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ?
 300                     malloc(sizeof(void *) * length) : sbo;
 301     if (sorted == NULL) abort();
 302     void *rc, *lc;
 303
 304     lc = ls;
 305     rc = le;
 306     size_t n = 0;
 307     while (lc && lc != le && rc != re) {
 308         if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
 309             sorted[n] = lc;
 310             lc = ll_next(lc);
 311         } else {
 312             sorted[n] = rc;
 313             rc = ll_next(rc);
 314         }
 315         n++;
 316     }
 317     while (lc && lc != le) {
 318         sorted[n] = lc;
 319         lc = ll_next(lc);
 320         n++;
 321     }
 322     while (rc && rc != re) {
 323         sorted[n] = rc;
 324         rc = ll_next(rc);
 325         n++;
 326     }
 327
 328     // Update pointer
 329     if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
 330     cx_for_n (i, length - 1) {
 331         cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next);
 332     }
 333     ll_next(sorted[length - 1]) = NULL;
 334
 335     *begin = sorted[0];
 336     *end = sorted[length-1];
 337     if (sorted != sbo) {
 338         free(sorted);
 339     }
 340 }
 341
 342 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function
 343         void **begin,
 344         void **end,
 345         ptrdiff_t loc_prev,
 346         ptrdiff_t loc_next,
 347         ptrdiff_t loc_data,
 348         cx_compare_func cmp_func
 349 ) {
 350     assert(begin != NULL);
 351     assert(loc_next >= 0);
 352     assert(loc_data >= 0);
 353     assert(cmp_func);
 354
 355     void *lc, *ls, *le, *re;
 356
 357     // set start node
 358     ls = *begin;
 359
 360     // early exit when this list is empty
 361     if (ls == NULL) return;
 362
 363     // check how many elements are already sorted
 364     lc = ls;
 365     size_t ln = 1;
 366     while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
 367         lc = ll_next(lc);
 368         ln++;
 369     }
 370     le = ll_next(lc);
 371
 372     // if first unsorted node is NULL, the list is already completely sorted
 373     if (le != NULL) {
 374         void *rc;
 375         size_t rn = 1;
 376         rc = le;
 377         // skip already sorted elements
 378         while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
 379             rc = ll_next(rc);
 380             rn++;
 381         }
 382         re = ll_next(rc);
 383
 384         // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
 385         void *sorted_begin, *sorted_end;
 386         cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
 387                                   ln + rn, ls, le, re, cmp_func,
 388                                   &sorted_begin, &sorted_end);
 389
 390         // Something left? Sort it!
 391         size_t remainder_length = cx_linked_list_size(re, loc_next);
 392         if (remainder_length > 0) {
 393             void *remainder = re;
 394             cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func);
 395
 396             // merge sorted list with (also sorted) remainder
 397             cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
 398                                       ln + rn + remainder_length,
 399                                       sorted_begin, remainder, NULL, cmp_func,
 400                                       &sorted_begin, &sorted_end);
 401         }
 402         *begin = sorted_begin;
 403         if (end) *end = sorted_end;
 404     }
 405 }
 406
 407 int cx_linked_list_compare(
 408         void const *begin_left,
 409         void const *begin_right,
 410         ptrdiff_t loc_advance,
 411         ptrdiff_t loc_data,
 412         cx_compare_func cmp_func
 413 ) {
 414     void const *left = begin_left, *right = begin_right;
 415
 416     while (left != NULL && right != NULL) {
 417         void const *left_data = ll_data(left);
 418         void const *right_data = ll_data(right);
 419         int result = cmp_func(left_data, right_data);
 420         if (result != 0) return result;
 421         left = ll_advance(left);
 422         right = ll_advance(right);
 423     }
 424
 425     if (left != NULL) { return 1; }
 426     else if (right != NULL) { return -1; }
 427     else { return 0; }
 428 }
 429
 430 void cx_linked_list_reverse(
 431         void **begin,
 432         void **end,
 433         ptrdiff_t loc_prev,
 434         ptrdiff_t loc_next
 435 ) {
 436     assert(begin != NULL);
 437     assert(loc_next >= 0);
 438
 439     // swap all links
 440     void *prev = NULL;
 441     void *cur = *begin;
 442     while (cur != NULL) {
 443         void *next = ll_next(cur);
 444
 445         ll_next(cur) = prev;
 446         if (loc_prev >= 0) {
 447             ll_prev(cur) = next;
 448         }
 449
 450         prev = cur;
 451         cur = next;
 452     }
 453
 454     // update begin and end
 455     if (end != NULL) {
 456         *end = *begin;
 457     }
 458     *begin = prev;
 459 }
 460
 461 // HIGH LEVEL LINKED LIST IMPLEMENTATION
 462
 463 bool CX_DISABLE_LINKED_LIST_SWAP_SBO = false;
 464
 465 typedef struct cx_linked_list_node cx_linked_list_node;
 466 struct cx_linked_list_node {
 467     cx_linked_list_node *prev;
 468     cx_linked_list_node *next;
 469     char payload[];
 470 };
 471
 472 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
 473 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
 474 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
 475
 476 typedef struct {
 477     struct cx_list_s base;
 478     cx_linked_list_node *begin;
 479     cx_linked_list_node *end;
 480 } cx_linked_list;
 481
 482 static cx_linked_list_node *cx_ll_node_at(
 483         cx_linked_list const *list,
 484         size_t index
 485 ) {
 486     if (index >= list->base.size) {
 487         return NULL;
 488     } else if (index > list->base.size / 2) {
 489         return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
 490     } else {
 491         return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
 492     }
 493 }
 494
 495 static int cx_ll_insert_at(
 496         struct cx_list_s *list,
 497         cx_linked_list_node *node,
 498         void const *elem
 499 ) {
 500
 501     // create the new new_node
 502     cx_linked_list_node *new_node = cxMalloc(list->allocator,
 503                                              sizeof(cx_linked_list_node) + list->item_size);
 504
 505     // sortir if failed
 506     if (new_node == NULL) return 1;
 507
 508     // initialize new new_node
 509     new_node->prev = new_node->next = NULL;
 510     memcpy(new_node->payload, elem, list->item_size);
 511
 512     // insert
 513     cx_linked_list *ll = (cx_linked_list *) list;
 514     cx_linked_list_insert_chain(
 515             (void **) &ll->begin, (void **) &ll->end,
 516             CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
 517             node, new_node, new_node
 518     );
 519
 520     // increase the size and return
 521     list->size++;
 522     return 0;
 523 }
 524
 525 static size_t cx_ll_insert_array(
 526         struct cx_list_s *list,
 527         size_t index,
 528         void const *array,
 529         size_t n
 530 ) {
 531     // out-of bounds and corner case check
 532     if (index > list->size || n == 0) return 0;
 533
 534     // find position efficiently
 535     cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
 536
 537     // perform first insert
 538     if (0 != cx_ll_insert_at(list, node, array)) {
 539         return 1;
 540     }
 541
 542     // is there more?
 543     if (n == 1) return 1;
 544
 545     // we now know exactly where we are
 546     node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
 547
 548     // we can add the remaining nodes and immedately advance to the inserted node
 549     char const *source = array;
 550     for (size_t i = 1; i < n; i++) {
 551         source += list->item_size;
 552         if (0 != cx_ll_insert_at(list, node, source)) {
 553             return i;
 554         }
 555         node = node->next;
 556     }
 557     return n;
 558 }
 559
 560 static int cx_ll_insert_element(
 561         struct cx_list_s *list,
 562         size_t index,
 563         void const *element
 564 ) {
 565     return 1 != cx_ll_insert_array(list, index, element, 1);
 566 }
 567
 568 static int cx_ll_remove(
 569         struct cx_list_s *list,
 570         size_t index
 571 ) {
 572     cx_linked_list *ll = (cx_linked_list *) list;
 573     cx_linked_list_node *node = cx_ll_node_at(ll, index);
 574
 575     // out-of-bounds check
 576     if (node == NULL) return 1;
 577
 578     // element destruction
 579     cx_invoke_destructor(list, node->payload);
 580
 581     // remove
 582     cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
 583                           CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
 584
 585     // adjust size
 586     list->size--;
 587
 588     // free and return
 589     cxFree(list->allocator, node);
 590
 591     return 0;
 592 }
 593
 594 static void cx_ll_clear(struct cx_list_s *list) {
 595     if (list->size == 0) return;
 596
 597     cx_linked_list *ll = (cx_linked_list *) list;
 598     cx_linked_list_node *node = ll->begin;
 599     while (node != NULL) {
 600         cx_invoke_destructor(list, node->payload);
 601         cx_linked_list_node *next = node->next;
 602         cxFree(list->allocator, node);
 603         node = next;
 604     }
 605     ll->begin = ll->end = NULL;
 606     list->size = 0;
 607 }
 608
 609 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
 610 #define CX_LINKED_LIST_SWAP_SBO_SIZE 128
 611 #endif
 612
 613 static int cx_ll_swap(
 614         struct cx_list_s *list,
 615         size_t i,
 616         size_t j
 617 ) {
 618     if (i >= list->size || j >= list->size) return 1;
 619     if (i == j) return 0;
 620
 621     // perform an optimized search that finds both elements in one run
 622     cx_linked_list *ll = (cx_linked_list *) list;
 623     size_t mid = list->size / 2;
 624     size_t left, right;
 625     if (i < j) {
 626         left = i;
 627         right = j;
 628     } else {
 629         left = j;
 630         right = i;
 631     }
 632     cx_linked_list_node *nleft, *nright;
 633     if (left < mid && right < mid) {
 634         // case 1: both items left from mid
 635         nleft = cx_ll_node_at(ll, left);
 636         nright = nleft;
 637         for (size_t c = left; c < right; c++) {
 638             nright = nright->next;
 639         }
 640     } else if (left >= mid && right >= mid) {
 641         // case 2: both items right from mid
 642         nright = cx_ll_node_at(ll, right);
 643         nleft = nright;
 644         for (size_t c = right; c > left; c--) {
 645             nleft = nleft->prev;
 646         }
 647     } else {
 648         // case 3: one item left, one item right
 649
 650         // chose the closest to begin / end
 651         size_t closest;
 652         size_t other;
 653         size_t diff2boundary = list->size - right - 1;
 654         if (left <= diff2boundary) {
 655             closest = left;
 656             other = right;
 657             nleft = cx_ll_node_at(ll, left);
 658         } else {
 659             closest = right;
 660             other = left;
 661             diff2boundary = left;
 662             nright = cx_ll_node_at(ll, right);
 663         }
 664
 665         // is other element closer to us or closer to boundary?
 666         if (right - left <= diff2boundary) {
 667             // search other element starting from already found element
 668             if (closest == left) {
 669                 nright = nleft;
 670                 for (size_t c = left; c < right; c++) {
 671                     nright = nright->next;
 672                 }
 673             } else {
 674                 nleft = nright;
 675                 for (size_t c = right; c > left; c--) {
 676                     nleft = nleft->prev;
 677                 }
 678             }
 679         } else {
 680             // search other element starting at the boundary
 681             if (closest == left) {
 682                 nright = cx_ll_node_at(ll, other);
 683             } else {
 684                 nleft = cx_ll_node_at(ll, other);
 685             }
 686         }
 687     }
 688
 689     if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) {
 690         cx_linked_list_node *prev = nleft->prev;
 691         cx_linked_list_node *next = nright->next;
 692         cx_linked_list_node *midstart = nleft->next;
 693         cx_linked_list_node *midend = nright->prev;
 694
 695         if (prev == NULL) {
 696             ll->begin = nright;
 697         } else {
 698             prev->next = nright;
 699         }
 700         nright->prev = prev;
 701         if (midstart == nright) {
 702             // special case: both nodes are adjacent
 703             nright->next = nleft;
 704             nleft->prev = nright;
 705         } else {
 706             // likely case: a chain is between the two nodes
 707             nright->next = midstart;
 708             midstart->prev = nright;
 709             midend->next = nleft;
 710             nleft->prev = midend;
 711         }
 712         nleft->next = next;
 713         if (next == NULL) {
 714             ll->end = nleft;
 715         } else {
 716             next->prev = nleft;
 717         }
 718     } else {
 719         // swap payloads to avoid relinking
 720         char buf[CX_LINKED_LIST_SWAP_SBO_SIZE];
 721         memcpy(buf, nleft->payload, list->item_size);
 722         memcpy(nleft->payload, nright->payload, list->item_size);
 723         memcpy(nright->payload, buf, list->item_size);
 724     }
 725
 726     return 0;
 727 }
 728
 729 static void *cx_ll_at(
 730         struct cx_list_s const *list,
 731         size_t index
 732 ) {
 733     cx_linked_list *ll = (cx_linked_list *) list;
 734     cx_linked_list_node *node = cx_ll_node_at(ll, index);
 735     return node == NULL ? NULL : node->payload;
 736 }
 737
 738 static ssize_t cx_ll_find(
 739         struct cx_list_s const *list,
 740         void const *elem
 741 ) {
 742     return cx_linked_list_find(((cx_linked_list *) list)->begin,
 743                                CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
 744                                list->cmpfunc, elem);
 745 }
 746
 747 static void cx_ll_sort(struct cx_list_s *list) {
 748     cx_linked_list *ll = (cx_linked_list *) list;
 749     cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
 750                         CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
 751                         list->cmpfunc);
 752 }
 753
 754 static void cx_ll_reverse(struct cx_list_s *list) {
 755     cx_linked_list *ll = (cx_linked_list *) list;
 756     cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT);
 757 }
 758
 759 static int cx_ll_compare(
 760         struct cx_list_s const *list,
 761         struct cx_list_s const *other
 762 ) {
 763     cx_linked_list *left = (cx_linked_list *) list;
 764     cx_linked_list *right = (cx_linked_list *) other;
 765     return cx_linked_list_compare(left->begin, right->begin,
 766                                   CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
 767                                   list->cmpfunc);
 768 }
 769
 770 static bool cx_ll_iter_valid(void const *it) {
 771     struct cx_iterator_s const *iter = it;
 772     return iter->elem_handle != NULL;
 773 }
 774
 775 static void cx_ll_iter_next(void *it) {
 776     struct cx_iterator_base_s *itbase = it;
 777     if (itbase->remove) {
 778         itbase->remove = false;
 779         struct cx_mut_iterator_s *iter = it;
 780         struct cx_list_s *list = iter->src_handle;
 781         cx_linked_list *ll = iter->src_handle;
 782         cx_linked_list_node *node = iter->elem_handle;
 783         iter->elem_handle = node->next;
 784         cx_invoke_destructor(list, node->payload);
 785         cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
 786                               CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
 787         list->size--;
 788         cxFree(list->allocator, node);
 789     } else {
 790         struct cx_iterator_s *iter = it;
 791         iter->index++;
 792         cx_linked_list_node *node = iter->elem_handle;
 793         iter->elem_handle = node->next;
 794     }
 795 }
 796
 797 static void cx_ll_iter_prev(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->prev;
 806         iter->index--;
 807         cx_invoke_destructor(list, node->payload);
 808         cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
 809                               CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
 810         list->size--;
 811         cxFree(list->allocator, node);
 812     } else {
 813         struct cx_iterator_s *iter = it;
 814         iter->index--;
 815         cx_linked_list_node *node = iter->elem_handle;
 816         iter->elem_handle = node->prev;
 817     }
 818 }
 819
 820 static void *cx_ll_iter_current(void const *it) {
 821     struct cx_iterator_s const *iter = it;
 822     cx_linked_list_node *node = iter->elem_handle;
 823     return node->payload;
 824 }
 825
 826 static bool cx_ll_iter_flag_rm(void *it) {
 827     struct cx_iterator_base_s *iter = it;
 828     if (iter->mutating) {
 829         iter->remove = true;
 830         return true;
 831     } else {
 832         return false;
 833     }
 834 }
 835
 836 static CxIterator cx_ll_iterator(
 837         struct cx_list_s const *list,
 838         size_t index,
 839         bool backwards
 840 ) {
 841     CxIterator iter;
 842     iter.index = index;
 843     iter.src_handle = list;
 844     iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index);
 845     iter.base.valid = cx_ll_iter_valid;
 846     iter.base.current = cx_ll_iter_current;
 847     iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next;
 848     iter.base.flag_removal = cx_ll_iter_flag_rm;
 849     iter.base.mutating = false;
 850     iter.base.remove = false;
 851     return iter;
 852 }
 853
 854 static int cx_ll_insert_iter(
 855         CxMutIterator *iter,
 856         void const *elem,
 857         int prepend
 858 ) {
 859     struct cx_list_s *list = iter->src_handle;
 860     cx_linked_list_node *node = iter->elem_handle;
 861     if (node != NULL) {
 862         assert(prepend >= 0 && prepend <= 1);
 863         cx_linked_list_node *choice[2] = {node, node->prev};
 864         int result = cx_ll_insert_at(list, choice[prepend], elem);
 865         iter->index += prepend * (0 == result);
 866         return result;
 867     } else {
 868         int result = cx_ll_insert_element(list, list->size, elem);
 869         iter->index = list->size;
 870         return result;
 871     }
 872 }
 873
 874 static void cx_ll_destructor(CxList *list) {
 875     cx_linked_list *ll = (cx_linked_list *) list;
 876
 877     cx_linked_list_node *node = ll->begin;
 878     while (node) {
 879         cx_invoke_destructor(list, node->payload);
 880         void *next = node->next;
 881         cxFree(list->allocator, node);
 882         node = next;
 883     }
 884
 885     cxFree(list->allocator, list);
 886 }
 887
 888 static cx_list_class cx_linked_list_class = {
 889         cx_ll_destructor,
 890         cx_ll_insert_element,
 891         cx_ll_insert_array,
 892         cx_ll_insert_iter,
 893         cx_ll_remove,
 894         cx_ll_clear,
 895         cx_ll_swap,
 896         cx_ll_at,
 897         cx_ll_find,
 898         cx_ll_sort,
 899         cx_ll_compare,
 900         cx_ll_reverse,
 901         cx_ll_iterator,
 902 };
 903
 904 CxList *cxLinkedListCreate(
 905         CxAllocator const *allocator,
 906         cx_compare_func comparator,
 907         size_t item_size
 908 ) {
 909     if (allocator == NULL) {
 910         allocator = cxDefaultAllocator;
 911     }
 912
 913     cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
 914     if (list == NULL) return NULL;
 915
 916     list->base.cl = &cx_linked_list_class;
 917     list->base.allocator = allocator;
 918     list->base.cmpfunc = comparator;
 919
 920     if (item_size > 0) {
 921         list->base.item_size = item_size;
 922     } else {
 923         cxListStorePointers((CxList *) list);
 924     }
 925
 926     return (CxList *) list;
 927 }