src/linked_list.c

Wed, 08 Feb 2023 20:26:09 +0100

author
Mike Becker <universe@uap-core.de>
date
Wed, 08 Feb 2023 20:26:09 +0100
changeset 647
2e6e9d9f2159
parent 641
d402fead3386
child 654
c9d008861178
permissions
-rw-r--r--

implement swap function for list elements - fixes #218

     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  */
    29 #include "cx/linked_list.h"
    30 #include "cx/utils.h"
    31 #include <stdint.h>
    32 #include <string.h>
    33 #include <assert.h>
    35 // LOW LEVEL LINKED LIST FUNCTIONS
    37 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
    38 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
    39 #define ll_next(node) CX_LL_PTR(node, loc_next)
    40 #define ll_advance(node) CX_LL_PTR(node, loc_advance)
    41 #define ll_data(node) (((char*)(node))+loc_data)
    43 void *cx_linked_list_at(
    44         void const *start,
    45         size_t start_index,
    46         ptrdiff_t loc_advance,
    47         size_t index
    48 ) {
    49     assert(start != NULL);
    50     assert(loc_advance >= 0);
    51     size_t i = start_index;
    52     void const *cur = start;
    53     while (i != index && cur != NULL) {
    54         cur = ll_advance(cur);
    55         i < index ? i++ : i--;
    56     }
    57     return (void *) cur;
    58 }
    60 size_t cx_linked_list_find(
    61         void const *start,
    62         ptrdiff_t loc_advance,
    63         ptrdiff_t loc_data,
    64         CxListComparator cmp_func,
    65         void const *elem
    66 ) {
    67     assert(start != NULL);
    68     assert(loc_advance >= 0);
    69     assert(loc_data >= 0);
    70     assert(cmp_func);
    72     void const *node = start;
    73     size_t index = 0;
    74     do {
    75         void *current = ll_data(node);
    76         if (cmp_func(current, elem) == 0) {
    77             return index;
    78         }
    79         node = ll_advance(node);
    80         index++;
    81     } while (node != NULL);
    82     return index;
    83 }
    85 void *cx_linked_list_first(
    86         void const *node,
    87         ptrdiff_t loc_prev
    88 ) {
    89     return cx_linked_list_last(node, loc_prev);
    90 }
    92 void *cx_linked_list_last(
    93         void const *node,
    94         ptrdiff_t loc_next
    95 ) {
    96     assert(node != NULL);
    97     assert(loc_next >= 0);
    99     void const *cur = node;
   100     void const *last;
   101     do {
   102         last = cur;
   103     } while ((cur = ll_next(cur)) != NULL);
   105     return (void *) last;
   106 }
   108 void *cx_linked_list_prev(
   109         void const *begin,
   110         ptrdiff_t loc_next,
   111         void const *node
   112 ) {
   113     assert(begin != NULL);
   114     assert(node != NULL);
   115     assert(loc_next >= 0);
   116     if (begin == node) return NULL;
   117     void const *cur = begin;
   118     void const *next;
   119     while (1) {
   120         next = ll_next(cur);
   121         if (next == node) return (void *) cur;
   122         cur = next;
   123     }
   124 }
   126 void cx_linked_list_link(
   127         void *left,
   128         void *right,
   129         ptrdiff_t loc_prev,
   130         ptrdiff_t loc_next
   131 ) {
   132     assert(loc_next >= 0);
   133     ll_next(left) = right;
   134     if (loc_prev >= 0) {
   135         ll_prev(right) = left;
   136     }
   137 }
   139 void cx_linked_list_unlink(
   140         void *left,
   141         void *right,
   142         ptrdiff_t loc_prev,
   143         ptrdiff_t loc_next
   144 ) {
   145     assert (loc_next >= 0);
   146     assert(ll_next(left) == right);
   147     ll_next(left) = NULL;
   148     if (loc_prev >= 0) {
   149         assert(ll_prev(right) == left);
   150         ll_prev(right) = NULL;
   151     }
   152 }
   154 void cx_linked_list_add(
   155         void **begin,
   156         void **end,
   157         ptrdiff_t loc_prev,
   158         ptrdiff_t loc_next,
   159         void *new_node
   160 ) {
   161     void *last;
   162     if (end == NULL) {
   163         assert(begin != NULL);
   164         last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next);
   165     } else {
   166         last = *end;
   167     }
   168     cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, last, new_node, new_node);
   169 }
   171 void cx_linked_list_prepend(
   172         void **begin,
   173         void **end,
   174         ptrdiff_t loc_prev,
   175         ptrdiff_t loc_next,
   176         void *new_node
   177 ) {
   178     cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, NULL, new_node, new_node);
   179 }
   181 void cx_linked_list_insert(
   182         void **begin,
   183         void **end,
   184         ptrdiff_t loc_prev,
   185         ptrdiff_t loc_next,
   186         void *node,
   187         void *new_node
   188 ) {
   189     cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, node, new_node, new_node);
   190 }
   192 void cx_linked_list_insert_chain(
   193         void **begin,
   194         void **end,
   195         ptrdiff_t loc_prev,
   196         ptrdiff_t loc_next,
   197         void *node,
   198         void *insert_begin,
   199         void *insert_end
   200 ) {
   201     // find the end of the chain, if not specified
   202     if (insert_end == NULL) {
   203         insert_end = cx_linked_list_last(insert_begin, loc_next);
   204     }
   206     // determine the successor
   207     void *successor;
   208     if (node == NULL) {
   209         assert(begin != NULL || (end != NULL && loc_prev >= 0));
   210         if (begin != NULL) {
   211             successor = *begin;
   212             *begin = insert_begin;
   213         } else {
   214             successor = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);
   215         }
   216     } else {
   217         successor = ll_next(node);
   218         cx_linked_list_link(node, insert_begin, loc_prev, loc_next);
   219     }
   221     if (successor == NULL) {
   222         // the list ends with the new chain
   223         if (end != NULL) {
   224             *end = insert_end;
   225         }
   226     } else {
   227         cx_linked_list_link(insert_end, successor, loc_prev, loc_next);
   228     }
   229 }
   231 void cx_linked_list_remove(
   232         void **begin,
   233         void **end,
   234         ptrdiff_t loc_prev,
   235         ptrdiff_t loc_next,
   236         void *node
   237 ) {
   238     assert(node != NULL);
   239     assert(loc_next >= 0);
   240     assert(loc_prev >= 0 || begin != NULL);
   242     // find adjacent nodes
   243     void *next = ll_next(node);
   244     void *prev;
   245     if (loc_prev >= 0) {
   246         prev = ll_prev(node);
   247     } else {
   248         prev = cx_linked_list_prev(*begin, loc_next, node);
   249     }
   251     // update next pointer of prev node, or set begin
   252     if (prev == NULL) {
   253         if (begin != NULL) {
   254             *begin = next;
   255         }
   256     } else {
   257         ll_next(prev) = next;
   258     }
   260     // update prev pointer of next node, or set end
   261     if (next == NULL) {
   262         if (end != NULL) {
   263             *end = prev;
   264         }
   265     } else if (loc_prev >= 0) {
   266         ll_prev(next) = prev;
   267     }
   268 }
   270 size_t cx_linked_list_size(
   271         void const *node,
   272         ptrdiff_t loc_next
   273 ) {
   274     assert(loc_next >= 0);
   275     size_t size = 0;
   276     while (node != NULL) {
   277         node = ll_next(node);
   278         size++;
   279     }
   280     return size;
   281 }
   283 static void *cx_linked_list_sort_merge(
   284         ptrdiff_t loc_prev,
   285         ptrdiff_t loc_next,
   286         ptrdiff_t loc_data,
   287         size_t length,
   288         void *ls,
   289         void *le,
   290         void *re,
   291         CxListComparator cmp_func
   292 ) {
   293     const size_t sbo_len = 1024;
   294     void *sbo[sbo_len];
   295     void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
   296     if (sorted == NULL) abort();
   297     void *rc, *lc;
   299     lc = ls;
   300     rc = le;
   301     size_t n = 0;
   302     while (lc && lc != le && rc != re) {
   303         if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
   304             sorted[n] = lc;
   305             lc = ll_next(lc);
   306         } else {
   307             sorted[n] = rc;
   308             rc = ll_next(rc);
   309         }
   310         n++;
   311     }
   312     while (lc && lc != le) {
   313         sorted[n] = lc;
   314         lc = ll_next(lc);
   315         n++;
   316     }
   317     while (rc && rc != re) {
   318         sorted[n] = rc;
   319         rc = ll_next(rc);
   320         n++;
   321     }
   323     // Update pointer
   324     if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
   325     cx_for_n (i, length - 1) {
   326         cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next);
   327     }
   328     ll_next(sorted[length - 1]) = NULL;
   330     void *ret = sorted[0];
   331     if (sorted != sbo) {
   332         free(sorted);
   333     }
   334     return ret;
   335 }
   337 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function
   338         void **begin,
   339         void **end,
   340         ptrdiff_t loc_prev,
   341         ptrdiff_t loc_next,
   342         ptrdiff_t loc_data,
   343         CxListComparator cmp_func
   344 ) {
   345     assert(begin != NULL);
   346     assert(loc_next >= 0);
   347     assert(loc_data >= 0);
   348     assert(cmp_func);
   350     void *lc, *ls, *le, *re;
   352     // set start node
   353     ls = *begin;
   355     // check how many elements are already sorted
   356     lc = ls;
   357     size_t ln = 1;
   358     while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
   359         lc = ll_next(lc);
   360         ln++;
   361     }
   362     le = ll_next(lc);
   364     // if first unsorted node is NULL, the list is already completely sorted
   365     if (le != NULL) {
   366         void *rc;
   367         size_t rn = 1;
   368         rc = le;
   369         // skip already sorted elements
   370         while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
   371             rc = ll_next(rc);
   372             rn++;
   373         }
   374         re = ll_next(rc);
   376         // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
   377         void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
   378                                                  ln + rn, ls, le, re, cmp_func);
   380         // Something left? Sort it!
   381         size_t remainder_length = cx_linked_list_size(re, loc_next);
   382         if (remainder_length > 0) {
   383             void *remainder = re;
   384             cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func);
   386             // merge sorted list with (also sorted) remainder
   387             *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
   388                                                ln + rn + remainder_length,
   389                                                sorted, remainder, NULL, cmp_func);
   390         } else {
   391             // no remainder - we've got our sorted list
   392             *begin = sorted;
   393         }
   394         if (end) *end = cx_linked_list_last(sorted, loc_next);
   395     }
   396 }
   398 int cx_linked_list_compare(
   399         void const *begin_left,
   400         void const *begin_right,
   401         ptrdiff_t loc_advance,
   402         ptrdiff_t loc_data,
   403         CxListComparator cmp_func
   404 ) {
   405     void const *left = begin_left, *right = begin_right;
   407     while (left != NULL && right != NULL) {
   408         void const *left_data = ll_data(left);
   409         void const *right_data = ll_data(right);
   410         int result = cmp_func(left_data, right_data);
   411         if (result != 0) return result;
   412         left = ll_advance(left);
   413         right = ll_advance(right);
   414     }
   416     if (left != NULL) { return 1; }
   417     else if (right != NULL) { return -1; }
   418     else { return 0; }
   419 }
   421 void cx_linked_list_reverse(
   422         void **begin,
   423         void **end,
   424         ptrdiff_t loc_prev,
   425         ptrdiff_t loc_next
   426 ) {
   427     assert(begin != NULL);
   428     assert(loc_next >= 0);
   430     // swap all links
   431     void *prev = NULL;
   432     void *cur = *begin;
   433     while (cur != NULL) {
   434         void *next = ll_next(cur);
   436         ll_next(cur) = prev;
   437         if (loc_prev >= 0) {
   438             ll_prev(cur) = next;
   439         }
   441         prev = cur;
   442         cur = next;
   443     }
   445     // update begin and end
   446     if (end != NULL) {
   447         *end = *begin;
   448     }
   449     *begin = prev;
   450 }
   452 // HIGH LEVEL LINKED LIST IMPLEMENTATION
   454 bool CX_DISABLE_LINKED_LIST_SWAP_SBO = false;
   456 typedef struct cx_linked_list_node cx_linked_list_node;
   457 struct cx_linked_list_node {
   458     cx_linked_list_node *prev;
   459     cx_linked_list_node *next;
   460     char payload[];
   461 };
   463 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
   464 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
   465 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
   467 typedef struct {
   468     struct cx_list_s base;
   469     cx_linked_list_node *begin;
   470     cx_linked_list_node *end;
   471 } cx_linked_list;
   473 static cx_linked_list_node *cx_ll_node_at(
   474         cx_linked_list const *list,
   475         size_t index
   476 ) {
   477     if (index >= list->base.size) {
   478         return NULL;
   479     } else if (index > list->base.size / 2) {
   480         return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
   481     } else {
   482         return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
   483     }
   484 }
   486 static int cx_ll_insert_at(
   487         struct cx_list_s *list,
   488         cx_linked_list_node *node,
   489         void const *elem
   490 ) {
   492     // create the new new_node
   493     cx_linked_list_node *new_node = cxMalloc(list->allocator,
   494                                              sizeof(cx_linked_list_node) + list->itemsize);
   496     // sortir if failed
   497     if (new_node == NULL) return 1;
   499     // initialize new new_node
   500     new_node->prev = new_node->next = NULL;
   501     memcpy(new_node->payload, elem, list->itemsize);
   503     // insert
   504     cx_linked_list *ll = (cx_linked_list *) list;
   505     cx_linked_list_insert_chain(
   506             (void **) &ll->begin, (void **) &ll->end,
   507             CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
   508             node, new_node, new_node
   509     );
   511     // increase the size and return
   512     list->size++;
   513     return 0;
   514 }
   516 static size_t cx_ll_insert_array(
   517         struct cx_list_s *list,
   518         size_t index,
   519         void const *array,
   520         size_t n
   521 ) {
   522     // out-of bounds and corner case check
   523     if (index > list->size || n == 0) return 0;
   525     // find position efficiently
   526     cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
   528     // perform first insert
   529     if (0 != cx_ll_insert_at(list, node, array)) {
   530         return 1;
   531     }
   533     // is there more?
   534     if (n == 1) return 1;
   536     // we now know exactly where we are
   537     node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
   539     // we can add the remaining nodes and immedately advance to the inserted node
   540     char const *source = array;
   541     for (size_t i = 1; i < n; i++) {
   542         source += list->itemsize;
   543         if (0 != cx_ll_insert_at(list, node, source)) {
   544             return i;
   545         }
   546         node = node->next;
   547     }
   548     return n;
   549 }
   551 static int cx_ll_insert_element(
   552         struct cx_list_s *list,
   553         size_t index,
   554         void const *element
   555 ) {
   556     return 1 != cx_ll_insert_array(list, index, element, 1);
   557 }
   559 static int cx_ll_remove(
   560         struct cx_list_s *list,
   561         size_t index
   562 ) {
   563     cx_linked_list *ll = (cx_linked_list *) list;
   564     cx_linked_list_node *node = cx_ll_node_at(ll, index);
   566     // out-of-bounds check
   567     if (node == NULL) return 1;
   569     // remove
   570     cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
   571                           CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
   573     // adjust size
   574     list->size--;
   576     // free and return
   577     cxFree(list->allocator, node);
   579     return 0;
   580 }
   582 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
   583 #define CX_LINKED_LIST_SWAP_SBO_SIZE 16
   584 #endif
   586 static int cx_ll_swap(
   587         struct cx_list_s *list,
   588         size_t i,
   589         size_t j
   590 ) {
   591     if (i >= list->size || j >= list->size) return 1;
   592     if (i == j) return 0;
   594     // perform an optimized search that finds both elements in one run
   595     cx_linked_list *ll = (cx_linked_list *) list;
   596     size_t mid = list->size / 2;
   597     size_t left, right;
   598     if (i < j) {
   599         left = i;
   600         right = j;
   601     } else {
   602         left = j;
   603         right = i;
   604     }
   605     cx_linked_list_node *nleft, *nright;
   606     if (left < mid && right < mid) {
   607         // case 1: both items left from mid
   608         nleft = cx_ll_node_at(ll, left);
   609         nright = nleft;
   610         for (size_t c = left; c < right; c++) {
   611             nright = nright->next;
   612         }
   613     } else if (left >= mid && right >= mid) {
   614         // case 2: both items right from mid
   615         nright = cx_ll_node_at(ll, right);
   616         nleft = nright;
   617         for (size_t c = right; c > left; c--) {
   618             nleft = nleft->prev;
   619         }
   620     } else {
   621         // case 3: one item left, one item right
   623         // chose the closest to begin / end
   624         size_t closest;
   625         size_t other;
   626         size_t diff2boundary = list->size - right - 1;
   627         if (left <= diff2boundary) {
   628             closest = left;
   629             other = right;
   630             nleft = cx_ll_node_at(ll, left);
   631         } else {
   632             closest = right;
   633             other = left;
   634             diff2boundary = left;
   635             nright = cx_ll_node_at(ll, right);
   636         }
   638         // is other element closer to us or closer to boundary?
   639         if (right - left <= diff2boundary) {
   640             // search other element starting from already found element
   641             if (closest == left) {
   642                 nright = nleft;
   643                 for (size_t c = left; c < right; c++) {
   644                     nright = nright->next;
   645                 }
   646             } else {
   647                 nleft = nright;
   648                 for (size_t c = right; c > left; c--) {
   649                     nleft = nleft->prev;
   650                 }
   651             }
   652         } else {
   653             // search other element starting at the boundary
   654             if (closest == left) {
   655                 nright = cx_ll_node_at(ll, other);
   656             } else {
   657                 nleft = cx_ll_node_at(ll, other);
   658             }
   659         }
   660     }
   662     if (list->itemsize > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) {
   663         cx_linked_list_node *prev = nleft->prev;
   664         cx_linked_list_node *next = nright->next;
   665         cx_linked_list_node *midstart = nleft->next;
   666         cx_linked_list_node *midend = nright->prev;
   668         if (prev == NULL) {
   669             ll->begin = nright;
   670         } else {
   671             prev->next = nright;
   672         }
   673         nright->prev = prev;
   674         if (midstart == nright) {
   675             // special case: both nodes are adjacent
   676             nright->next = nleft;
   677             nleft->prev = nright;
   678         } else {
   679             // likely case: a chain is between the two nodes
   680             nright->next = midstart;
   681             midstart->prev = nright;
   682             midend->next = nleft;
   683             nleft->prev = midend;
   684         }
   685         nleft->next = next;
   686         if (next == NULL) {
   687             ll->end = nleft;
   688         } else {
   689             next->prev = nleft;
   690         }
   691     } else {
   692         // swap payloads to avoid relinking
   693         char buf[CX_LINKED_LIST_SWAP_SBO_SIZE];
   694         memcpy(buf, nleft->payload, list->itemsize);
   695         memcpy(nleft->payload, nright->payload, list->itemsize);
   696         memcpy(nright->payload, buf, list->itemsize);
   697     }
   699     return 0;
   700 }
   702 static void *cx_ll_at(
   703         struct cx_list_s const *list,
   704         size_t index
   705 ) {
   706     cx_linked_list *ll = (cx_linked_list *) list;
   707     cx_linked_list_node *node = cx_ll_node_at(ll, index);
   708     return node == NULL ? NULL : node->payload;
   709 }
   711 static size_t cx_ll_find(
   712         struct cx_list_s const *list,
   713         void const *elem
   714 ) {
   715     return cx_linked_list_find(((cx_linked_list *) list)->begin,
   716                                CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
   717                                list->cmpfunc, elem);
   718 }
   720 static void cx_ll_sort(struct cx_list_s *list) {
   721     cx_linked_list *ll = (cx_linked_list *) list;
   722     cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
   723                         CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
   724                         list->cmpfunc);
   725 }
   727 static void cx_ll_reverse(struct cx_list_s *list) {
   728     cx_linked_list *ll = (cx_linked_list *) list;
   729     cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT);
   730 }
   732 static int cx_ll_compare(
   733         struct cx_list_s const *list,
   734         struct cx_list_s const *other
   735 ) {
   736     cx_linked_list *left = (cx_linked_list *) list;
   737     cx_linked_list *right = (cx_linked_list *) other;
   738     return cx_linked_list_compare(left->begin, right->begin,
   739                                   CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
   740                                   list->cmpfunc);
   741 }
   743 static bool cx_ll_iter_valid(void const *it) {
   744     struct cx_iterator_s const *iter = it;
   745     return iter->elem_handle != NULL;
   746 }
   748 static void cx_ll_iter_next(void *it) {
   749     struct cx_iterator_base_s *itbase = it;
   750     if (itbase->remove) {
   751         itbase->remove = false;
   752         struct cx_mut_iterator_s *iter = it;
   753         cx_linked_list *ll = iter->src_handle;
   754         cx_linked_list_node *node = iter->elem_handle;
   755         iter->elem_handle = node->next;
   756         cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
   757                               CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
   758         ll->base.size--;
   759         cxFree(ll->base.allocator, node);
   760     } else {
   761         struct cx_iterator_s *iter = it;
   762         iter->index++;
   763         cx_linked_list_node *node = iter->elem_handle;
   764         iter->elem_handle = node->next;
   765     }
   766 }
   768 static void *cx_ll_iter_current(void const *it) {
   769     struct cx_iterator_s const *iter = it;
   770     cx_linked_list_node *node = iter->elem_handle;
   771     return node->payload;
   772 }
   774 static bool cx_ll_iter_flag_rm(void *it) {
   775     struct cx_iterator_base_s *iter = it;
   776     if (iter->mutating) {
   777         iter->remove = true;
   778         return true;
   779     } else {
   780         return false;
   781     }
   782 }
   784 static CxIterator cx_ll_iterator(
   785         struct cx_list_s const *list,
   786         size_t index
   787 ) {
   788     CxIterator iter;
   789     iter.index = index;
   790     iter.src_handle = list;
   791     iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index);
   792     iter.base.valid = cx_ll_iter_valid;
   793     iter.base.current = cx_ll_iter_current;
   794     iter.base.next = cx_ll_iter_next;
   795     iter.base.flag_removal = cx_ll_iter_flag_rm;
   796     iter.base.mutating = false;
   797     iter.base.remove = false;
   798     return iter;
   799 }
   801 static int cx_ll_insert_iter(
   802         CxMutIterator *iter,
   803         void const *elem,
   804         int prepend
   805 ) {
   806     struct cx_list_s *list = iter->src_handle;
   807     cx_linked_list_node *node = iter->elem_handle;
   808     if (node != NULL) {
   809         assert(prepend >= 0 && prepend <= 1);
   810         cx_linked_list_node *choice[2] = {node, node->prev};
   811         int result = cx_ll_insert_at(list, choice[prepend], elem);
   812         iter->index += prepend * (0 == result);
   813         return result;
   814     } else {
   815         int result = cx_ll_insert_element(list, list->size, elem);
   816         iter->index = list->size;
   817         return result;
   818     }
   819 }
   821 static void cx_ll_destructor(CxList *list) {
   822     cx_linked_list *ll = (cx_linked_list *) list;
   824     cx_linked_list_node *node = ll->begin;
   825     while (node) {
   826         void *next = node->next;
   827         cxFree(list->allocator, node);
   828         node = next;
   829     }
   830     // do not free the list pointer, this is just a destructor!
   831 }
   833 static cx_list_class cx_linked_list_class = {
   834         cx_ll_destructor,
   835         cx_ll_insert_element,
   836         cx_ll_insert_array,
   837         cx_ll_insert_iter,
   838         cx_ll_remove,
   839         cx_ll_swap,
   840         cx_ll_at,
   841         cx_ll_find,
   842         cx_ll_sort,
   843         cx_ll_compare,
   844         cx_ll_reverse,
   845         cx_ll_iterator,
   846 };
   848 CxList *cxLinkedListCreate(
   849         CxAllocator const *allocator,
   850         CxListComparator comparator,
   851         size_t item_size
   852 ) {
   853     cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
   854     if (list == NULL) return NULL;
   856     list->base.cl = &cx_linked_list_class;
   857     list->base.allocator = allocator;
   858     list->base.cmpfunc = comparator;
   859     list->base.itemsize = item_size;
   860     list->base.capacity = SIZE_MAX;
   862     return (CxList *) list;
   863 }

mercurial