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 <string.h>
universe@453: #include <assert.h>
universe@398: 
universe@628: // 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@639: #define ll_data(node) (((char*)(node))+loc_data)
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@699: ssize_t cx_linked_list_find(
universe@489:         void const *start,
universe@481:         ptrdiff_t loc_advance,
universe@481:         ptrdiff_t loc_data,
universe@677:         cx_compare_func 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@699:     ssize_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@699:     return -1;
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@661: #ifndef CX_LINKED_LIST_SORT_SBO_SIZE
universe@661: #define CX_LINKED_LIST_SORT_SBO_SIZE 1024
universe@661: #endif
universe@661: 
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@481:         size_t length,
universe@481:         void *ls,
universe@481:         void *le,
universe@481:         void *re,
universe@677:         cx_compare_func cmp_func
universe@481: ) {
universe@661:     void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE];
universe@661:     void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ?
universe@662:                     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@628: 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@677:         cx_compare_func 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@702:     // early exit when this list is empty
universe@702:     if (ls == NULL) return;
universe@702: 
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@639:         void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
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@639:             cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func);
universe@468: 
universe@468:             // merge sorted list with (also sorted) remainder
universe@639:             *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
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@677:         cx_compare_func cmp_func
universe@486: ) {
universe@489:     void const *left = begin_left, *right = begin_right;
universe@486: 
universe@486:     while (left != NULL && right != NULL) {
universe@639:         void const *left_data = ll_data(left);
universe@639:         void const *right_data = ll_data(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@628: // HIGH LEVEL LINKED LIST IMPLEMENTATION
universe@398: 
universe@647: bool CX_DISABLE_LINKED_LIST_SWAP_SBO = false;
universe@647: 
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@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@677:                                              sizeof(cx_linked_list_node) + list->item_size);
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@677:     memcpy(new_node->payload, elem, list->item_size);
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@638: static size_t cx_ll_insert_array(
universe@638:         struct cx_list_s *list,
universe@638:         size_t index,
universe@638:         void const *array,
universe@638:         size_t n
universe@638: ) {
universe@638:     // out-of bounds and corner case check
universe@638:     if (index > list->size || n == 0) return 0;
universe@638: 
universe@638:     // find position efficiently
universe@638:     cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
universe@638: 
universe@638:     // perform first insert
universe@638:     if (0 != cx_ll_insert_at(list, node, array)) {
universe@638:         return 1;
universe@638:     }
universe@638: 
universe@638:     // is there more?
universe@638:     if (n == 1) return 1;
universe@638: 
universe@638:     // we now know exactly where we are
universe@638:     node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
universe@638: 
universe@638:     // we can add the remaining nodes and immedately advance to the inserted node
universe@638:     char const *source = array;
universe@638:     for (size_t i = 1; i < n; i++) {
universe@677:         source += list->item_size;
universe@638:         if (0 != cx_ll_insert_at(list, node, source)) {
universe@638:             return i;
universe@638:         }
universe@638:         node = node->next;
universe@638:     }
universe@638:     return n;
universe@638: }
universe@638: 
universe@641: static int cx_ll_insert_element(
universe@641:         struct cx_list_s *list,
universe@641:         size_t index,
universe@641:         void const *element
universe@641: ) {
universe@641:     return 1 != cx_ll_insert_array(list, index, element, 1);
universe@641: }
universe@641: 
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@664:     // element destruction
universe@677:     cx_invoke_destructor(list, node->payload);
universe@664: 
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@664: static void cx_ll_clear(struct cx_list_s *list) {
universe@664:     if (list->size == 0) return;
universe@664: 
universe@664:     cx_linked_list *ll = (cx_linked_list *) list;
universe@664:     cx_linked_list_node *node = ll->begin;
universe@677:     while (node != NULL) {
universe@677:         cx_invoke_destructor(list, node->payload);
universe@677:         cx_linked_list_node *next = node->next;
universe@677:         cxFree(list->allocator, node);
universe@677:         node = next;
universe@664:     }
universe@664:     ll->begin = ll->end = NULL;
universe@664:     list->size = 0;
universe@664: }
universe@664: 
universe@647: #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
universe@647: #define CX_LINKED_LIST_SWAP_SBO_SIZE 16
universe@647: #endif
universe@647: 
universe@647: static int cx_ll_swap(
universe@647:         struct cx_list_s *list,
universe@647:         size_t i,
universe@647:         size_t j
universe@647: ) {
universe@647:     if (i >= list->size || j >= list->size) return 1;
universe@647:     if (i == j) return 0;
universe@647: 
universe@647:     // perform an optimized search that finds both elements in one run
universe@647:     cx_linked_list *ll = (cx_linked_list *) list;
universe@647:     size_t mid = list->size / 2;
universe@647:     size_t left, right;
universe@647:     if (i < j) {
universe@647:         left = i;
universe@647:         right = j;
universe@647:     } else {
universe@647:         left = j;
universe@647:         right = i;
universe@647:     }
universe@647:     cx_linked_list_node *nleft, *nright;
universe@647:     if (left < mid && right < mid) {
universe@647:         // case 1: both items left from mid
universe@647:         nleft = cx_ll_node_at(ll, left);
universe@647:         nright = nleft;
universe@647:         for (size_t c = left; c < right; c++) {
universe@647:             nright = nright->next;
universe@647:         }
universe@647:     } else if (left >= mid && right >= mid) {
universe@647:         // case 2: both items right from mid
universe@647:         nright = cx_ll_node_at(ll, right);
universe@647:         nleft = nright;
universe@647:         for (size_t c = right; c > left; c--) {
universe@647:             nleft = nleft->prev;
universe@647:         }
universe@647:     } else {
universe@647:         // case 3: one item left, one item right
universe@647: 
universe@647:         // chose the closest to begin / end
universe@647:         size_t closest;
universe@647:         size_t other;
universe@647:         size_t diff2boundary = list->size - right - 1;
universe@647:         if (left <= diff2boundary) {
universe@647:             closest = left;
universe@647:             other = right;
universe@647:             nleft = cx_ll_node_at(ll, left);
universe@647:         } else {
universe@647:             closest = right;
universe@647:             other = left;
universe@647:             diff2boundary = left;
universe@647:             nright = cx_ll_node_at(ll, right);
universe@647:         }
universe@647: 
universe@647:         // is other element closer to us or closer to boundary?
universe@647:         if (right - left <= diff2boundary) {
universe@647:             // search other element starting from already found element
universe@647:             if (closest == left) {
universe@647:                 nright = nleft;
universe@647:                 for (size_t c = left; c < right; c++) {
universe@647:                     nright = nright->next;
universe@647:                 }
universe@647:             } else {
universe@647:                 nleft = nright;
universe@647:                 for (size_t c = right; c > left; c--) {
universe@647:                     nleft = nleft->prev;
universe@647:                 }
universe@647:             }
universe@647:         } else {
universe@647:             // search other element starting at the boundary
universe@647:             if (closest == left) {
universe@647:                 nright = cx_ll_node_at(ll, other);
universe@647:             } else {
universe@647:                 nleft = cx_ll_node_at(ll, other);
universe@647:             }
universe@647:         }
universe@647:     }
universe@647: 
universe@677:     if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) {
universe@647:         cx_linked_list_node *prev = nleft->prev;
universe@647:         cx_linked_list_node *next = nright->next;
universe@647:         cx_linked_list_node *midstart = nleft->next;
universe@647:         cx_linked_list_node *midend = nright->prev;
universe@647: 
universe@647:         if (prev == NULL) {
universe@647:             ll->begin = nright;
universe@647:         } else {
universe@647:             prev->next = nright;
universe@647:         }
universe@647:         nright->prev = prev;
universe@647:         if (midstart == nright) {
universe@647:             // special case: both nodes are adjacent
universe@647:             nright->next = nleft;
universe@647:             nleft->prev = nright;
universe@647:         } else {
universe@647:             // likely case: a chain is between the two nodes
universe@647:             nright->next = midstart;
universe@647:             midstart->prev = nright;
universe@647:             midend->next = nleft;
universe@647:             nleft->prev = midend;
universe@647:         }
universe@647:         nleft->next = next;
universe@647:         if (next == NULL) {
universe@647:             ll->end = nleft;
universe@647:         } else {
universe@647:             next->prev = nleft;
universe@647:         }
universe@647:     } else {
universe@647:         // swap payloads to avoid relinking
universe@647:         char buf[CX_LINKED_LIST_SWAP_SBO_SIZE];
universe@677:         memcpy(buf, nleft->payload, list->item_size);
universe@677:         memcpy(nleft->payload, nright->payload, list->item_size);
universe@677:         memcpy(nright->payload, buf, list->item_size);
universe@647:     }
universe@647: 
universe@647:     return 0;
universe@647: }
universe@647: 
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@699: static ssize_t cx_ll_find(
universe@500:         struct cx_list_s const *list,
universe@489:         void const *elem
universe@481: ) {
universe@480:     return cx_linked_list_find(((cx_linked_list *) list)->begin,
universe@480:                                CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
universe@639:                                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@639:                         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@639:                                   list->cmpfunc);
universe@488: }
universe@488: 
universe@630: static bool cx_ll_iter_valid(void const *it) {
universe@630:     struct cx_iterator_s const *iter = it;
universe@495:     return iter->elem_handle != NULL;
universe@494: }
universe@494: 
universe@630: static void cx_ll_iter_next(void *it) {
universe@630:     struct cx_iterator_base_s *itbase = it;
universe@630:     if (itbase->remove) {
universe@630:         itbase->remove = false;
universe@630:         struct cx_mut_iterator_s *iter = it;
universe@664:         struct cx_list_s *list = iter->src_handle;
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@677:         cx_invoke_destructor(list, node->payload);
universe@495:         cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
universe@495:                               CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
universe@664:         list->size--;
universe@664:         cxFree(list->allocator, node);
universe@495:     } else {
universe@630:         struct cx_iterator_s *iter = it;
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@655: static void cx_ll_iter_prev(void *it) {
universe@655:     struct cx_iterator_base_s *itbase = it;
universe@655:     if (itbase->remove) {
universe@655:         itbase->remove = false;
universe@655:         struct cx_mut_iterator_s *iter = it;
universe@664:         struct cx_list_s *list = iter->src_handle;
universe@655:         cx_linked_list *ll = iter->src_handle;
universe@655:         cx_linked_list_node *node = iter->elem_handle;
universe@655:         iter->elem_handle = node->prev;
universe@655:         iter->index--;
universe@677:         cx_invoke_destructor(list, node->payload);
universe@655:         cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
universe@655:                               CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
universe@664:         list->size--;
universe@664:         cxFree(list->allocator, node);
universe@655:     } else {
universe@655:         struct cx_iterator_s *iter = it;
universe@655:         iter->index--;
universe@655:         cx_linked_list_node *node = iter->elem_handle;
universe@655:         iter->elem_handle = node->prev;
universe@655:     }
universe@655: }
universe@655: 
universe@630: static void *cx_ll_iter_current(void const *it) {
universe@630:     struct cx_iterator_s const *iter = it;
universe@495:     cx_linked_list_node *node = iter->elem_handle;
universe@494:     return node->payload;
universe@494: }
universe@494: 
universe@630: static bool cx_ll_iter_flag_rm(void *it) {
universe@630:     struct cx_iterator_base_s *iter = it;
universe@630:     if (iter->mutating) {
universe@630:         iter->remove = true;
universe@630:         return true;
universe@630:     } else {
universe@630:         return false;
universe@630:     }
universe@630: }
universe@630: 
universe@494: static CxIterator cx_ll_iterator(
universe@630:         struct cx_list_s const *list,
universe@655:         size_t index,
universe@655:         bool backwards
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@630:     iter.base.valid = cx_ll_iter_valid;
universe@630:     iter.base.current = cx_ll_iter_current;
universe@655:     iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next;
universe@630:     iter.base.flag_removal = cx_ll_iter_flag_rm;
universe@630:     iter.base.mutating = false;
universe@630:     iter.base.remove = false;
universe@494:     return iter;
universe@494: }
universe@494: 
universe@499: static int cx_ll_insert_iter(
universe@630:         CxMutIterator *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@641:         int result = cx_ll_insert_element(list, list->size, elem);
universe@499:         iter->index = list->size;
universe@499:         return result;
universe@499:     }
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@641:         cx_ll_insert_element,
universe@638:         cx_ll_insert_array,
universe@499:         cx_ll_insert_iter,
universe@398:         cx_ll_remove,
universe@664:         cx_ll_clear,
universe@647:         cx_ll_swap,
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@630:         cx_ll_iterator,
universe@398: };
universe@398: 
universe@670: CxList *cxLinkedListCreate(
universe@508:         CxAllocator const *allocator,
universe@677:         cx_compare_func comparator,
universe@481:         size_t item_size
universe@481: ) {
universe@670:     if (allocator == NULL) {
universe@670:         allocator = cxDefaultAllocator;
universe@670:     }
universe@670: 
universe@503:     cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
universe@528:     if (list == NULL) return NULL;
universe@398: 
universe@435:     list->base.cl = &cx_linked_list_class;
universe@435:     list->base.allocator = allocator;
universe@435:     list->base.cmpfunc = comparator;
universe@406: 
universe@667:     if (item_size > 0) {
universe@677:         list->base.item_size = item_size;
universe@667:     } else {
universe@667:         cxListStorePointers((CxList *) list);
universe@667:     }
universe@667: 
universe@500:     return (CxList *) list;
universe@406: }