universe@398: /*
universe@398:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
universe@398:  *
universe@398:  * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
universe@398:  *
universe@398:  * Redistribution and use in source and binary forms, with or without
universe@398:  * modification, are permitted provided that the following conditions are met:
universe@398:  *
universe@398:  *   1. Redistributions of source code must retain the above copyright
universe@398:  *      notice, this list of conditions and the following disclaimer.
universe@398:  *
universe@398:  *   2. Redistributions in binary form must reproduce the above copyright
universe@398:  *      notice, this list of conditions and the following disclaimer in the
universe@398:  *      documentation and/or other materials provided with the distribution.
universe@398:  *
universe@398:  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
universe@398:  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
universe@398:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
universe@398:  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
universe@398:  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
universe@398:  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
universe@398:  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
universe@398:  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
universe@398:  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
universe@398:  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
universe@398:  * POSSIBILITY OF SUCH DAMAGE.
universe@398:  */
universe@398: 
universe@398: #include "cx/linked_list.h"
universe@509: #include "cx/utils.h"
universe@401: #include <stdint.h>
universe@401: #include <string.h>
universe@453: #include <assert.h>
universe@398: 
universe@398: /* LOW LEVEL LINKED LIST FUNCTIONS */
universe@398: 
universe@592: #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
universe@480: #define ll_prev(node) CX_LL_PTR(node, loc_prev)
universe@480: #define ll_next(node) CX_LL_PTR(node, loc_next)
universe@480: #define ll_advance(node) CX_LL_PTR(node, loc_advance)
universe@592: #define ll_data_f(node, follow_ptr) ((follow_ptr)?CX_LL_PTR(node, loc_data):(((char*)(node))+loc_data))
universe@552: #define ll_data(node) ll_data_f(node,follow_ptr)
universe@398: 
universe@481: void *cx_linked_list_at(
universe@508:         void const *start,
universe@481:         size_t start_index,
universe@481:         ptrdiff_t loc_advance,
universe@481:         size_t index
universe@481: ) {
universe@473:     assert(start != NULL);
universe@473:     assert(loc_advance >= 0);
universe@438:     size_t i = start_index;
universe@508:     void const *cur = start;
universe@438:     while (i != index && cur != NULL) {
universe@480:         cur = ll_advance(cur);
universe@438:         i < index ? i++ : i--;
universe@438:     }
universe@508:     return (void *) cur;
universe@438: }
universe@438: 
universe@481: size_t cx_linked_list_find(
universe@489:         void const *start,
universe@481:         ptrdiff_t loc_advance,
universe@481:         ptrdiff_t loc_data,
universe@487:         bool follow_ptr,
universe@481:         CxListComparator cmp_func,
universe@489:         void const *elem
universe@481: ) {
universe@480:     assert(start != NULL);
universe@480:     assert(loc_advance >= 0);
universe@480:     assert(loc_data >= 0);
universe@480:     assert(cmp_func);
universe@480: 
universe@489:     void const *node = start;
universe@480:     size_t index = 0;
universe@480:     do {
universe@480:         void *current = ll_data(node);
universe@480:         if (cmp_func(current, elem) == 0) {
universe@480:             return index;
universe@480:         }
universe@480:         node = ll_advance(node);
universe@480:         index++;
universe@480:     } while (node != NULL);
universe@480:     return index;
universe@480: }
universe@480: 
universe@481: void *cx_linked_list_first(
universe@508:         void const *node,
universe@481:         ptrdiff_t loc_prev
universe@481: ) {
universe@475:     return cx_linked_list_last(node, loc_prev);
universe@475: }
universe@475: 
universe@481: void *cx_linked_list_last(
universe@508:         void const *node,
universe@481:         ptrdiff_t loc_next
universe@481: ) {
universe@478:     assert(node != NULL);
universe@473:     assert(loc_next >= 0);
universe@398: 
universe@508:     void const *cur = node;
universe@508:     void const *last;
universe@456:     do {
universe@456:         last = cur;
universe@480:     } while ((cur = ll_next(cur)) != NULL);
universe@398: 
universe@508:     return (void *) last;
universe@398: }
universe@398: 
universe@481: void *cx_linked_list_prev(
universe@508:         void const *begin,
universe@481:         ptrdiff_t loc_next,
universe@508:         void const *node
universe@481: ) {
universe@473:     assert(begin != NULL);
universe@478:     assert(node != NULL);
universe@473:     assert(loc_next >= 0);
universe@473:     if (begin == node) return NULL;
universe@508:     void const *cur = begin;
universe@508:     void const *next;
universe@473:     while (1) {
universe@480:         next = ll_next(cur);
universe@508:         if (next == node) return (void *) cur;
universe@473:         cur = next;
universe@473:     }
universe@473: }
universe@473: 
universe@481: void cx_linked_list_link(
universe@481:         void *left,
universe@481:         void *right,
universe@481:         ptrdiff_t loc_prev,
universe@481:         ptrdiff_t loc_next
universe@481: ) {
universe@473:     assert(loc_next >= 0);
universe@481:     ll_next(left) = right;
universe@481:     if (loc_prev >= 0) {
universe@481:         ll_prev(right) = left;
universe@481:     }
universe@481: }
universe@481: 
universe@481: void cx_linked_list_unlink(
universe@481:         void *left,
universe@481:         void *right,
universe@481:         ptrdiff_t loc_prev,
universe@481:         ptrdiff_t loc_next
universe@481: ) {
universe@481:     assert (loc_next >= 0);
universe@481:     assert(ll_next(left) == right);
universe@481:     ll_next(left) = NULL;
universe@481:     if (loc_prev >= 0) {
universe@481:         assert(ll_prev(right) == left);
universe@481:         ll_prev(right) = NULL;
universe@481:     }
universe@481: }
universe@481: 
universe@481: void cx_linked_list_add(
universe@481:         void **begin,
universe@481:         void **end,
universe@481:         ptrdiff_t loc_prev,
universe@481:         ptrdiff_t loc_next,
universe@481:         void *new_node
universe@481: ) {
universe@456:     void *last;
universe@456:     if (end == NULL) {
universe@456:         assert(begin != NULL);
universe@478:         last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next);
universe@456:     } else {
universe@456:         last = *end;
universe@456:     }
universe@481:     cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, last, new_node, new_node);
universe@481: }
universe@481: 
universe@481: void cx_linked_list_prepend(
universe@481:         void **begin,
universe@481:         void **end,
universe@481:         ptrdiff_t loc_prev,
universe@481:         ptrdiff_t loc_next,
universe@481:         void *new_node
universe@481: ) {
universe@481:     cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, NULL, new_node, new_node);
universe@481: }
universe@481: 
universe@481: void cx_linked_list_insert(
universe@481:         void **begin,
universe@481:         void **end,
universe@481:         ptrdiff_t loc_prev,
universe@481:         ptrdiff_t loc_next,
universe@481:         void *node,
universe@481:         void *new_node
universe@481: ) {
universe@481:     cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, node, new_node, new_node);
universe@481: }
universe@481: 
universe@481: void cx_linked_list_insert_chain(
universe@481:         void **begin,
universe@481:         void **end,
universe@481:         ptrdiff_t loc_prev,
universe@481:         ptrdiff_t loc_next,
universe@481:         void *node,
universe@481:         void *insert_begin,
universe@481:         void *insert_end
universe@481: ) {
universe@481:     // find the end of the chain, if not specified
universe@481:     if (insert_end == NULL) {
universe@481:         insert_end = cx_linked_list_last(insert_begin, loc_next);
universe@481:     }
universe@481: 
universe@481:     // determine the successor
universe@481:     void *successor;
universe@481:     if (node == NULL) {
universe@481:         assert(begin != NULL || (end != NULL && loc_prev >= 0));
universe@475:         if (begin != NULL) {
universe@481:             successor = *begin;
universe@481:             *begin = insert_begin;
universe@481:         } else {
universe@481:             successor = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);
universe@475:         }
universe@428:     } else {
universe@481:         successor = ll_next(node);
universe@481:         cx_linked_list_link(node, insert_begin, loc_prev, loc_next);
universe@398:     }
universe@398: 
universe@481:     if (successor == NULL) {
universe@481:         // the list ends with the new chain
universe@481:         if (end != NULL) {
universe@481:             *end = insert_end;
universe@481:         }
universe@481:     } else {
universe@481:         cx_linked_list_link(insert_end, successor, loc_prev, loc_next);
universe@398:     }
universe@398: }
universe@398: 
universe@481: void cx_linked_list_remove(
universe@481:         void **begin,
universe@481:         void **end,
universe@481:         ptrdiff_t loc_prev,
universe@481:         ptrdiff_t loc_next,
universe@481:         void *node
universe@481: ) {
universe@477:     assert(node != NULL);
universe@473:     assert(loc_next >= 0);
universe@473:     assert(loc_prev >= 0 || begin != NULL);
universe@473: 
universe@473:     // find adjacent nodes
universe@480:     void *next = ll_next(node);
universe@473:     void *prev;
universe@473:     if (loc_prev >= 0) {
universe@480:         prev = ll_prev(node);
universe@473:     } else {
universe@473:         prev = cx_linked_list_prev(*begin, loc_next, node);
universe@473:     }
universe@473: 
universe@476:     // update next pointer of prev node, or set begin
universe@476:     if (prev == NULL) {
universe@476:         if (begin != NULL) {
universe@476:             *begin = next;
universe@476:         }
universe@476:     } else {
universe@480:         ll_next(prev) = next;
universe@473:     }
universe@476: 
universe@476:     // update prev pointer of next node, or set end
universe@476:     if (next == NULL) {
universe@476:         if (end != NULL) {
universe@476:             *end = prev;
universe@476:         }
universe@476:     } else if (loc_prev >= 0) {
universe@480:         ll_prev(next) = prev;
universe@473:     }
universe@473: }
universe@473: 
universe@481: size_t cx_linked_list_size(
universe@489:         void const *node,
universe@481:         ptrdiff_t loc_next
universe@481: ) {
universe@473:     assert(loc_next >= 0);
universe@468:     size_t size = 0;
universe@468:     while (node != NULL) {
universe@480:         node = ll_next(node);
universe@468:         size++;
universe@468:     }
universe@468:     return size;
universe@468: }
universe@468: 
universe@481: static void *cx_linked_list_sort_merge(
universe@481:         ptrdiff_t loc_prev,
universe@481:         ptrdiff_t loc_next,
universe@481:         ptrdiff_t loc_data,
universe@487:         bool follow_ptr,
universe@481:         size_t length,
universe@481:         void *ls,
universe@481:         void *le,
universe@481:         void *re,
universe@481:         CxListComparator cmp_func
universe@481: ) {
universe@468:     const size_t sbo_len = 1024;
universe@468:     void *sbo[sbo_len];
universe@468:     void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
universe@508:     if (sorted == NULL) abort();
universe@468:     void *rc, *lc;
universe@468: 
universe@468:     lc = ls;
universe@468:     rc = le;
universe@468:     size_t n = 0;
universe@468:     while (lc && lc != le && rc != re) {
universe@468:         if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
universe@468:             sorted[n] = lc;
universe@468:             lc = ll_next(lc);
universe@468:         } else {
universe@468:             sorted[n] = rc;
universe@468:             rc = ll_next(rc);
universe@468:         }
universe@468:         n++;
universe@468:     }
universe@468:     while (lc && lc != le) {
universe@468:         sorted[n] = lc;
universe@468:         lc = ll_next(lc);
universe@468:         n++;
universe@468:     }
universe@468:     while (rc && rc != re) {
universe@468:         sorted[n] = rc;
universe@468:         rc = ll_next(rc);
universe@468:         n++;
universe@468:     }
universe@468: 
universe@468:     // Update pointer
universe@468:     if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
universe@509:     cx_for_n (i, length - 1) {
universe@481:         cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next);
universe@468:     }
universe@468:     ll_next(sorted[length - 1]) = NULL;
universe@468: 
universe@468:     void *ret = sorted[0];
universe@468:     if (sorted != sbo) {
universe@468:         free(sorted);
universe@468:     }
universe@468:     return ret;
universe@468: }
universe@468: 
universe@476: void cx_linked_list_sort( /* NOLINT(misc-no-recursion) - purposely recursive function */
universe@481:         void **begin,
universe@481:         void **end,
universe@481:         ptrdiff_t loc_prev,
universe@481:         ptrdiff_t loc_next,
universe@481:         ptrdiff_t loc_data,
universe@487:         bool follow_ptr,
universe@481:         CxListComparator cmp_func
universe@481: ) {
universe@468:     assert(begin != NULL);
universe@473:     assert(loc_next >= 0);
universe@473:     assert(loc_data >= 0);
universe@473:     assert(cmp_func);
universe@468: 
universe@468:     void *lc, *ls, *le, *re;
universe@468: 
universe@468:     // set start node
universe@468:     ls = *begin;
universe@468: 
universe@468:     // check how many elements are already sorted
universe@468:     lc = ls;
universe@468:     size_t ln = 1;
universe@468:     while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
universe@468:         lc = ll_next(lc);
universe@468:         ln++;
universe@468:     }
universe@468:     le = ll_next(lc);
universe@468: 
universe@468:     // if first unsorted node is NULL, the list is already completely sorted
universe@468:     if (le != NULL) {
universe@468:         void *rc;
universe@468:         size_t rn = 1;
universe@468:         rc = le;
universe@468:         // skip already sorted elements
universe@468:         while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
universe@468:             rc = ll_next(rc);
universe@468:             rn++;
universe@468:         }
universe@468:         re = ll_next(rc);
universe@468: 
universe@468:         // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
universe@468:         void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
universe@468:                                                  ln + rn, ls, le, re, cmp_func);
universe@468: 
universe@468:         // Something left? Sort it!
universe@468:         size_t remainder_length = cx_linked_list_size(re, loc_next);
universe@468:         if (remainder_length > 0) {
universe@468:             void *remainder = re;
universe@468:             cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func);
universe@468: 
universe@468:             // merge sorted list with (also sorted) remainder
universe@468:             *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
universe@468:                                                ln + rn + remainder_length,
universe@468:                                                sorted, remainder, NULL, cmp_func);
universe@468:         } else {
universe@468:             // no remainder - we've got our sorted list
universe@468:             *begin = sorted;
universe@468:         }
universe@468:         if (end) *end = cx_linked_list_last(sorted, loc_next);
universe@468:     }
universe@468: }
universe@468: 
universe@486: int cx_linked_list_compare(
universe@489:         void const *begin_left,
universe@489:         void const *begin_right,
universe@486:         ptrdiff_t loc_advance,
universe@486:         ptrdiff_t loc_data,
universe@552:         bool follow_ptr_left,
universe@552:         bool follow_ptr_right,
universe@486:         CxListComparator cmp_func
universe@486: ) {
universe@489:     void const *left = begin_left, *right = begin_right;
universe@486: 
universe@486:     while (left != NULL && right != NULL) {
universe@552:         void const *left_data = ll_data_f(left, follow_ptr_left);
universe@552:         void const *right_data = ll_data_f(right, follow_ptr_right);
universe@552:         int result = cmp_func(left_data, right_data);
universe@486:         if (result != 0) return result;
universe@486:         left = ll_advance(left);
universe@486:         right = ll_advance(right);
universe@486:     }
universe@486: 
universe@486:     if (left != NULL) { return 1; }
universe@486:     else if (right != NULL) { return -1; }
universe@486:     else { return 0; }
universe@486: }
universe@486: 
universe@481: void cx_linked_list_reverse(
universe@481:         void **begin,
universe@481:         void **end,
universe@481:         ptrdiff_t loc_prev,
universe@481:         ptrdiff_t loc_next
universe@481: ) {
universe@473:     assert(begin != NULL);
universe@473:     assert(loc_next >= 0);
universe@473: 
universe@473:     // swap all links
universe@473:     void *prev = NULL;
universe@473:     void *cur = *begin;
universe@473:     while (cur != NULL) {
universe@480:         void *next = ll_next(cur);
universe@473: 
universe@480:         ll_next(cur) = prev;
universe@473:         if (loc_prev >= 0) {
universe@480:             ll_prev(cur) = next;
universe@473:         }
universe@473: 
universe@473:         prev = cur;
universe@473:         cur = next;
universe@473:     }
universe@473: 
universe@473:     // update begin and end
universe@473:     if (end != NULL) {
universe@473:         *end = *begin;
universe@473:     }
universe@473:     *begin = prev;
universe@473: }
universe@473: 
universe@398: /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
universe@398: 
universe@447: typedef struct cx_linked_list_node cx_linked_list_node;
universe@447: struct cx_linked_list_node {
universe@447:     cx_linked_list_node *prev;
universe@447:     cx_linked_list_node *next;
universe@403:     char payload[];
universe@447: };
universe@402: 
universe@446: #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
universe@446: #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
universe@469: #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
universe@439: 
universe@398: typedef struct {
universe@500:     struct cx_list_s base;
universe@446:     cx_linked_list_node *begin;
universe@446:     cx_linked_list_node *end;
universe@552:     bool follow_ptr;
universe@398: } cx_linked_list;
universe@398: 
universe@481: static cx_linked_list_node *cx_ll_node_at(
universe@489:         cx_linked_list const *list,
universe@481:         size_t index
universe@481: ) {
universe@447:     if (index >= list->base.size) {
universe@447:         return NULL;
universe@447:     } else if (index > list->base.size / 2) {
universe@468:         return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
universe@447:     } else {
universe@447:         return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
universe@447:     }
universe@447: }
universe@447: 
universe@499: static int cx_ll_insert_at(
universe@500:         struct cx_list_s *list,
universe@499:         cx_linked_list_node *node,
universe@489:         void const *elem
universe@481: ) {
universe@448: 
universe@481:     // create the new new_node
universe@481:     cx_linked_list_node *new_node = cxMalloc(list->allocator,
universe@481:                                              sizeof(cx_linked_list_node) + list->itemsize);
universe@448: 
universe@448:     // sortir if failed
universe@481:     if (new_node == NULL) return 1;
universe@448: 
universe@481:     // initialize new new_node
universe@481:     new_node->prev = new_node->next = NULL;
universe@481:     memcpy(new_node->payload, elem, list->itemsize);
universe@448: 
universe@481:     // insert
universe@499:     cx_linked_list *ll = (cx_linked_list *) list;
universe@481:     cx_linked_list_insert_chain(
universe@481:             (void **) &ll->begin, (void **) &ll->end,
universe@481:             CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
universe@481:             node, new_node, new_node
universe@481:     );
universe@448: 
universe@448:     // increase the size and return
universe@448:     list->size++;
universe@448:     return 0;
universe@448: }
universe@448: 
universe@499: static int cx_ll_insert(
universe@500:         struct cx_list_s *list,
universe@499:         size_t index,
universe@499:         void const *elem
universe@499: ) {
universe@499:     // out-of bounds check
universe@499:     if (index > list->size) return 1;
universe@499: 
universe@499:     // find position efficiently
universe@499:     cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
universe@499: 
universe@499:     // perform insert
universe@499:     return cx_ll_insert_at(list, node, elem);
universe@499: }
universe@499: 
universe@481: static int cx_ll_add(
universe@500:         struct cx_list_s *list,
universe@489:         void const *elem
universe@481: ) {
universe@448:     return cx_ll_insert(list, list->size, elem);
universe@398: }
universe@398: 
universe@481: static int cx_pll_insert(
universe@500:         struct cx_list_s *list,
universe@481:         size_t index,
universe@489:         void const *elem
universe@481: ) {
universe@466:     return cx_ll_insert(list, index, &elem);
universe@466: }
universe@466: 
universe@481: static int cx_pll_add(
universe@500:         struct cx_list_s *list,
universe@489:         void const *elem
universe@481: ) {
universe@466:     return cx_ll_insert(list, list->size, &elem);
universe@466: }
universe@466: 
universe@481: static int cx_ll_remove(
universe@500:         struct cx_list_s *list,
universe@481:         size_t index
universe@481: ) {
universe@447:     cx_linked_list *ll = (cx_linked_list *) list;
universe@447:     cx_linked_list_node *node = cx_ll_node_at(ll, index);
universe@447: 
universe@447:     // out-of-bounds check
universe@447:     if (node == NULL) return 1;
universe@447: 
universe@476:     // remove
universe@476:     cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
universe@476:                           CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
universe@447: 
universe@447:     // adjust size
universe@447:     list->size--;
universe@447: 
universe@447:     // free and return
universe@447:     cxFree(list->allocator, node);
universe@447: 
universe@438:     return 0;
universe@398: }
universe@398: 
universe@481: static void *cx_ll_at(
universe@500:         struct cx_list_s const *list,
universe@481:         size_t index
universe@481: ) {
universe@439:     cx_linked_list *ll = (cx_linked_list *) list;
universe@447:     cx_linked_list_node *node = cx_ll_node_at(ll, index);
universe@466:     return node == NULL ? NULL : node->payload;
universe@466: }
universe@466: 
universe@481: static void *cx_pll_at(
universe@500:         struct cx_list_s const *list,
universe@481:         size_t index
universe@481: ) {
universe@466:     cx_linked_list *ll = (cx_linked_list *) list;
universe@466:     cx_linked_list_node *node = cx_ll_node_at(ll, index);
universe@468:     return node == NULL ? NULL : *(void **) node->payload;
universe@439: }
universe@439: 
universe@481: static size_t cx_ll_find(
universe@500:         struct cx_list_s const *list,
universe@489:         void const *elem
universe@481: ) {
universe@552:     cx_linked_list *ll = (cx_linked_list *) list;
universe@480:     return cx_linked_list_find(((cx_linked_list *) list)->begin,
universe@480:                                CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
universe@552:                                ll->follow_ptr, list->cmpfunc, elem);
universe@466: }
universe@466: 
universe@500: static void cx_ll_sort(struct cx_list_s *list) {
universe@469:     cx_linked_list *ll = (cx_linked_list *) list;
universe@469:     cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
universe@469:                         CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
universe@552:                         ll->follow_ptr, list->cmpfunc);
universe@469: }
universe@469: 
universe@500: static void cx_ll_reverse(struct cx_list_s *list) {
universe@490:     cx_linked_list *ll = (cx_linked_list *) list;
universe@521:     cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT);
universe@490: }
universe@490: 
universe@488: static int cx_ll_compare(
universe@500:         struct cx_list_s const *list,
universe@500:         struct cx_list_s const *other
universe@488: ) {
universe@488:     cx_linked_list *left = (cx_linked_list *) list;
universe@488:     cx_linked_list *right = (cx_linked_list *) other;
universe@488:     return cx_linked_list_compare(left->begin, right->begin,
universe@488:                                   CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
universe@552:                                   left->follow_ptr, right->follow_ptr, list->cmpfunc);
universe@488: }
universe@488: 
universe@494: static bool cx_ll_iter_valid(CxIterator const *iter) {
universe@495:     return iter->elem_handle != NULL;
universe@494: }
universe@494: 
universe@494: static void cx_ll_iter_next(CxIterator *iter) {
universe@495:     if (iter->remove) {
universe@495:         iter->remove = false;
universe@495:         cx_linked_list *ll = iter->src_handle;
universe@495:         cx_linked_list_node *node = iter->elem_handle;
universe@495:         iter->elem_handle = node->next;
universe@495:         cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
universe@495:                               CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
universe@495:         ll->base.size--;
universe@495:         cxFree(ll->base.allocator, node);
universe@495:     } else {
universe@495:         iter->index++;
universe@495:         cx_linked_list_node *node = iter->elem_handle;
universe@495:         iter->elem_handle = node->next;
universe@495:     }
universe@494: }
universe@494: 
universe@494: static void *cx_ll_iter_current(CxIterator const *iter) {
universe@495:     cx_linked_list_node *node = iter->elem_handle;
universe@494:     return node->payload;
universe@494: }
universe@494: 
universe@494: static void *cx_pll_iter_current(CxIterator const *iter) {
universe@495:     cx_linked_list_node *node = iter->elem_handle;
universe@494:     return *(void **) node->payload;
universe@494: }
universe@494: 
universe@494: static CxIterator cx_ll_iterator(
universe@500:         struct cx_list_s *list,
universe@494:         size_t index
universe@494: ) {
universe@494:     CxIterator iter;
universe@494:     iter.index = index;
universe@495:     iter.src_handle = list;
universe@495:     iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index);
universe@494:     iter.valid = cx_ll_iter_valid;
universe@494:     iter.current = cx_ll_iter_current;
universe@494:     iter.next = cx_ll_iter_next;
universe@495:     iter.remove = false;
universe@494:     return iter;
universe@494: }
universe@494: 
universe@494: static CxIterator cx_pll_iterator(
universe@500:         struct cx_list_s *list,
universe@494:         size_t index
universe@494: ) {
universe@494:     CxIterator iter = cx_ll_iterator(list, index);
universe@494:     iter.current = cx_pll_iter_current;
universe@494:     return iter;
universe@494: }
universe@494: 
universe@499: static int cx_ll_insert_iter(
universe@499:         CxIterator *iter,
universe@499:         void const *elem,
universe@499:         int prepend
universe@499: ) {
universe@500:     struct cx_list_s *list = iter->src_handle;
universe@499:     cx_linked_list_node *node = iter->elem_handle;
universe@499:     if (node != NULL) {
universe@499:         assert(prepend >= 0 && prepend <= 1);
universe@499:         cx_linked_list_node *choice[2] = {node, node->prev};
universe@499:         int result = cx_ll_insert_at(list, choice[prepend], elem);
universe@499:         iter->index += prepend * (0 == result);
universe@499:         return result;
universe@499:     } else {
universe@499:         int result = cx_ll_insert(list, list->size, elem);
universe@499:         iter->index = list->size;
universe@499:         return result;
universe@499:     }
universe@499: }
universe@499: 
universe@499: static int cx_pll_insert_iter(
universe@499:         CxIterator *iter,
universe@499:         void const *elem,
universe@499:         int prepend
universe@499: ) {
universe@499:     return cx_ll_insert_iter(iter, &elem, prepend);
universe@499: }
universe@499: 
universe@524: static void cx_ll_destructor(CxList *list) {
universe@524:     cx_linked_list *ll = (cx_linked_list *) list;
universe@524: 
universe@524:     cx_linked_list_node *node = ll->begin;
universe@524:     while (node) {
universe@524:         void *next = node->next;
universe@524:         cxFree(list->allocator, node);
universe@524:         node = next;
universe@524:     }
universe@524:     // do not free the list pointer, this is just a destructor!
universe@524: }
universe@524: 
universe@451: static cx_list_class cx_linked_list_class = {
universe@524:         cx_ll_destructor,
universe@398:         cx_ll_add,
universe@398:         cx_ll_insert,
universe@499:         cx_ll_insert_iter,
universe@398:         cx_ll_remove,
universe@439:         cx_ll_at,
universe@404:         cx_ll_find,
universe@488:         cx_ll_sort,
universe@490:         cx_ll_compare,
universe@494:         cx_ll_reverse,
universe@499:         cx_ll_iterator
universe@398: };
universe@398: 
universe@466: static cx_list_class cx_pointer_linked_list_class = {
universe@524:         cx_ll_destructor,
universe@466:         cx_pll_add,
universe@466:         cx_pll_insert,
universe@499:         cx_pll_insert_iter,
universe@466:         cx_ll_remove,
universe@466:         cx_pll_at,
universe@552:         cx_ll_find,
universe@552:         cx_ll_sort,
universe@552:         cx_ll_compare,
universe@494:         cx_ll_reverse,
universe@494:         cx_pll_iterator,
universe@466: };
universe@466: 
universe@500: CxList *cxLinkedListCreate(
universe@508:         CxAllocator const *allocator,
universe@481:         CxListComparator comparator,
universe@481:         size_t item_size
universe@481: ) {
universe@503:     cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
universe@528:     if (list == NULL) return NULL;
universe@398: 
universe@552:     list->follow_ptr = false;
universe@435:     list->base.cl = &cx_linked_list_class;
universe@435:     list->base.allocator = allocator;
universe@435:     list->base.cmpfunc = comparator;
universe@435:     list->base.itemsize = item_size;
universe@435:     list->base.capacity = SIZE_MAX;
universe@406: 
universe@500:     return (CxList *) list;
universe@406: }
universe@406: 
universe@500: CxList *cxPointerLinkedListCreate(
universe@508:         CxAllocator const *allocator,
universe@481:         CxListComparator comparator
universe@481: ) {
universe@503:     cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
universe@528:     if (list == NULL) return NULL;
universe@466: 
universe@552:     list->follow_ptr = true;
universe@466:     list->base.cl = &cx_pointer_linked_list_class;
universe@466:     list->base.allocator = allocator;
universe@466:     list->base.cmpfunc = comparator;
universe@468:     list->base.itemsize = sizeof(void *);
universe@466:     list->base.capacity = SIZE_MAX;
universe@466: 
universe@500:     return (CxList *) list;
universe@466: }
universe@466: 
universe@500: CxList *cxLinkedListFromArray(
universe@508:         CxAllocator const *allocator,
universe@488:         CxListComparator comparator,
universe@488:         size_t item_size,
universe@488:         size_t num_items,
universe@489:         void const *array
universe@488: ) {
universe@500:     CxList *list = cxLinkedListCreate(allocator, comparator, item_size);
universe@488:     if (list == NULL) return NULL;
universe@509:     cx_for_n (i, num_items) {
universe@488:         if (0 != cxListAdd(list, ((const unsigned char *) array) + i * item_size)) {
universe@524:             cx_ll_destructor(list);
universe@524:             cxFree(allocator, list);
universe@524:             return NULL;
universe@488:         }
universe@488:     }
universe@488:     return list;
universe@488: }