Mercurial > hg > ucx / file revision

 /*

  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.

  *

  * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.

  *

  * Redistribution and use in source and binary forms, with or without

  * modification, are permitted provided that the following conditions are met:

  *

  *   1. Redistributions of source code must retain the above copyright

  *      notice, this list of conditions and the following disclaimer.

  *

  *   2. Redistributions in binary form must reproduce the above copyright

  *      notice, this list of conditions and the following disclaimer in the

  *      documentation and/or other materials provided with the distribution.

  *

  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE

  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF

  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN

  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

  * POSSIBILITY OF SUCH DAMAGE.

  */

 #include "cx/linked_list.h"

 #include "cx/utils.h"

 #include <stdint.h>

 #include <string.h>

 #include <assert.h>

 // LOW LEVEL LINKED LIST FUNCTIONS

 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))

 #define ll_prev(node) CX_LL_PTR(node, loc_prev)

 #define ll_next(node) CX_LL_PTR(node, loc_next)

 #define ll_advance(node) CX_LL_PTR(node, loc_advance)

 #define ll_data(node) (((char*)(node))+loc_data)

 void *cx_linked_list_at(

         void const *start,

         size_t start_index,

         ptrdiff_t loc_advance,

         size_t index

 ) {

     assert(start != NULL);

     assert(loc_advance >= 0);

     size_t i = start_index;

     void const *cur = start;

     while (i != index && cur != NULL) {

         cur = ll_advance(cur);

         i < index ? i++ : i--;

     }

     return (void *) cur;

 }

 size_t cx_linked_list_find(

         void const *start,

         ptrdiff_t loc_advance,

         ptrdiff_t loc_data,

         CxListComparator cmp_func,

         void const *elem

 ) {

     assert(start != NULL);

     assert(loc_advance >= 0);

     assert(loc_data >= 0);

     assert(cmp_func);

     void const *node = start;

     size_t index = 0;

     do {

         void *current = ll_data(node);

         if (cmp_func(current, elem) == 0) {

             return index;

         }

         node = ll_advance(node);

         index++;

     } while (node != NULL);

     return index;

 }

 void *cx_linked_list_first(

         void const *node,

         ptrdiff_t loc_prev

 ) {

     return cx_linked_list_last(node, loc_prev);

 }

 void *cx_linked_list_last(

         void const *node,

         ptrdiff_t loc_next

 ) {

     assert(node != NULL);

     assert(loc_next >= 0);

     void const *cur = node;

     void const *last;

     do {

         last = cur;

     } while ((cur = ll_next(cur)) != NULL);

     return (void *) last;

 }

 void *cx_linked_list_prev(

         void const *begin,

         ptrdiff_t loc_next,

         void const *node

 ) {

     assert(begin != NULL);

     assert(node != NULL);

     assert(loc_next >= 0);

     if (begin == node) return NULL;

     void const *cur = begin;

     void const *next;

     while (1) {

         next = ll_next(cur);

         if (next == node) return (void *) cur;

         cur = next;

     }

 }

 void cx_linked_list_link(

         void *left,

         void *right,

         ptrdiff_t loc_prev,

         ptrdiff_t loc_next

 ) {

     assert(loc_next >= 0);

     ll_next(left) = right;

     if (loc_prev >= 0) {

         ll_prev(right) = left;

     }

 }

 void cx_linked_list_unlink(

         void *left,

         void *right,

         ptrdiff_t loc_prev,

         ptrdiff_t loc_next

 ) {

     assert (loc_next >= 0);

     assert(ll_next(left) == right);

     ll_next(left) = NULL;

     if (loc_prev >= 0) {

         assert(ll_prev(right) == left);

         ll_prev(right) = NULL;

     }

 }

 void cx_linked_list_add(

         void **begin,

         void **end,

         ptrdiff_t loc_prev,

         ptrdiff_t loc_next,

         void *new_node

 ) {

     void *last;

     if (end == NULL) {

         assert(begin != NULL);

         last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next);

     } else {

         last = *end;

     }

     cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, last, new_node, new_node);

 }

 void cx_linked_list_prepend(

         void **begin,

         void **end,

         ptrdiff_t loc_prev,

         ptrdiff_t loc_next,

         void *new_node

 ) {

     cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, NULL, new_node, new_node);

 }

 void cx_linked_list_insert(

         void **begin,

         void **end,

         ptrdiff_t loc_prev,

         ptrdiff_t loc_next,

         void *node,

         void *new_node

 ) {

     cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, node, new_node, new_node);

 }

 void cx_linked_list_insert_chain(

         void **begin,

         void **end,

         ptrdiff_t loc_prev,

         ptrdiff_t loc_next,

         void *node,

         void *insert_begin,

         void *insert_end

 ) {

     // find the end of the chain, if not specified

     if (insert_end == NULL) {

         insert_end = cx_linked_list_last(insert_begin, loc_next);

     }

     // determine the successor

     void *successor;

     if (node == NULL) {

         assert(begin != NULL || (end != NULL && loc_prev >= 0));

         if (begin != NULL) {

             successor = *begin;

             *begin = insert_begin;

         } else {

             successor = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);

         }

     } else {

         successor = ll_next(node);

         cx_linked_list_link(node, insert_begin, loc_prev, loc_next);

     }

     if (successor == NULL) {

         // the list ends with the new chain

         if (end != NULL) {

             *end = insert_end;

         }

     } else {

         cx_linked_list_link(insert_end, successor, loc_prev, loc_next);

     }

 }

 void cx_linked_list_remove(

         void **begin,

         void **end,

         ptrdiff_t loc_prev,

         ptrdiff_t loc_next,

         void *node

 ) {

     assert(node != NULL);

     assert(loc_next >= 0);

     assert(loc_prev >= 0 || begin != NULL);

     // find adjacent nodes

     void *next = ll_next(node);

     void *prev;

     if (loc_prev >= 0) {

         prev = ll_prev(node);

     } else {

         prev = cx_linked_list_prev(*begin, loc_next, node);

     }

     // update next pointer of prev node, or set begin

     if (prev == NULL) {

         if (begin != NULL) {

             *begin = next;

         }

     } else {

         ll_next(prev) = next;

     }

     // update prev pointer of next node, or set end

     if (next == NULL) {

         if (end != NULL) {

             *end = prev;

         }

     } else if (loc_prev >= 0) {

         ll_prev(next) = prev;

     }

 }

 size_t cx_linked_list_size(

         void const *node,

         ptrdiff_t loc_next

 ) {

     assert(loc_next >= 0);

     size_t size = 0;

     while (node != NULL) {

         node = ll_next(node);

         size++;

     }

     return size;

 }

 static void *cx_linked_list_sort_merge(

         ptrdiff_t loc_prev,

         ptrdiff_t loc_next,

         ptrdiff_t loc_data,

         size_t length,

         void *ls,

         void *le,

         void *re,

         CxListComparator cmp_func

 ) {

     const size_t sbo_len = 1024;

     void *sbo[sbo_len];

     void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;

     if (sorted == NULL) abort();

     void *rc, *lc;

     lc = ls;

     rc = le;

     size_t n = 0;

     while (lc && lc != le && rc != re) {

         if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {

             sorted[n] = lc;

             lc = ll_next(lc);

         } else {

             sorted[n] = rc;

             rc = ll_next(rc);

         }

         n++;

     }

     while (lc && lc != le) {

         sorted[n] = lc;

         lc = ll_next(lc);

         n++;

     }

     while (rc && rc != re) {

         sorted[n] = rc;

         rc = ll_next(rc);

         n++;

     }

     // Update pointer

     if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;

     cx_for_n (i, length - 1) {

         cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next);

     }

     ll_next(sorted[length - 1]) = NULL;

     void *ret = sorted[0];

     if (sorted != sbo) {

         free(sorted);

     }

     return ret;

 }

 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function

         void **begin,

         void **end,

         ptrdiff_t loc_prev,

         ptrdiff_t loc_next,

         ptrdiff_t loc_data,

         CxListComparator cmp_func

 ) {

     assert(begin != NULL);

     assert(loc_next >= 0);

     assert(loc_data >= 0);

     assert(cmp_func);

     void *lc, *ls, *le, *re;

     // set start node

     ls = *begin;

     // check how many elements are already sorted

     lc = ls;

     size_t ln = 1;

     while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {

         lc = ll_next(lc);

         ln++;

     }

     le = ll_next(lc);

     // if first unsorted node is NULL, the list is already completely sorted

     if (le != NULL) {

         void *rc;

         size_t rn = 1;

         rc = le;

         // skip already sorted elements

         while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {

             rc = ll_next(rc);

             rn++;

         }

         re = ll_next(rc);

         // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them

         void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,

                                                  ln + rn, ls, le, re, cmp_func);

         // Something left? Sort it!

         size_t remainder_length = cx_linked_list_size(re, loc_next);

         if (remainder_length > 0) {

             void *remainder = re;

             cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func);

             // merge sorted list with (also sorted) remainder

             *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,

                                                ln + rn + remainder_length,

                                                sorted, remainder, NULL, cmp_func);

         } else {

             // no remainder - we've got our sorted list

             *begin = sorted;

         }

         if (end) *end = cx_linked_list_last(sorted, loc_next);

     }

 }

 int cx_linked_list_compare(

         void const *begin_left,

         void const *begin_right,

         ptrdiff_t loc_advance,

         ptrdiff_t loc_data,

         CxListComparator cmp_func

 ) {

     void const *left = begin_left, *right = begin_right;

     while (left != NULL && right != NULL) {

         void const *left_data = ll_data(left);

         void const *right_data = ll_data(right);

         int result = cmp_func(left_data, right_data);

         if (result != 0) return result;

         left = ll_advance(left);

         right = ll_advance(right);

     }

     if (left != NULL) { return 1; }

     else if (right != NULL) { return -1; }

     else { return 0; }

 }

 void cx_linked_list_reverse(

         void **begin,

         void **end,

         ptrdiff_t loc_prev,

         ptrdiff_t loc_next

 ) {

     assert(begin != NULL);

     assert(loc_next >= 0);

     // swap all links

     void *prev = NULL;

     void *cur = *begin;

     while (cur != NULL) {

         void *next = ll_next(cur);

         ll_next(cur) = prev;

         if (loc_prev >= 0) {

             ll_prev(cur) = next;

         }

         prev = cur;

         cur = next;

     }

     // update begin and end

     if (end != NULL) {

         *end = *begin;

     }

     *begin = prev;

 }

 // HIGH LEVEL LINKED LIST IMPLEMENTATION

 typedef struct cx_linked_list_node cx_linked_list_node;

 struct cx_linked_list_node {

     cx_linked_list_node *prev;

     cx_linked_list_node *next;

     char payload[];

 };

 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)

 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)

 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)

 typedef struct {

     struct cx_list_s base;

     cx_linked_list_node *begin;

     cx_linked_list_node *end;

 } cx_linked_list;

 static cx_linked_list_node *cx_ll_node_at(

         cx_linked_list const *list,

         size_t index

 ) {

     if (index >= list->base.size) {

         return NULL;

     } else if (index > list->base.size / 2) {

         return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);

     } else {

         return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);

     }

 }

 static int cx_ll_insert_at(

         struct cx_list_s *list,

         cx_linked_list_node *node,

         void const *elem

 ) {

     // create the new new_node

     cx_linked_list_node *new_node = cxMalloc(list->allocator,

                                              sizeof(cx_linked_list_node) + list->itemsize);

     // sortir if failed

     if (new_node == NULL) return 1;

     // initialize new new_node

     new_node->prev = new_node->next = NULL;

     memcpy(new_node->payload, elem, list->itemsize);

     // insert

     cx_linked_list *ll = (cx_linked_list *) list;

     cx_linked_list_insert_chain(

             (void **) &ll->begin, (void **) &ll->end,

             CX_LL_LOC_PREV, CX_LL_LOC_NEXT,

             node, new_node, new_node

     );

     // increase the size and return

     list->size++;

     return 0;

 }

 static size_t cx_ll_insert_array(

         struct cx_list_s *list,

         size_t index,

         void const *array,

         size_t n

 ) {

     // out-of bounds and corner case check

     if (index > list->size || n == 0) return 0;

     // find position efficiently

     cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);

     // perform first insert

     if (0 != cx_ll_insert_at(list, node, array)) {

         return 1;

     }

     // is there more?

     if (n == 1) return 1;

     // we now know exactly where we are

     node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;

     // we can add the remaining nodes and immedately advance to the inserted node

     char const *source = array;

     for (size_t i = 1; i < n; i++) {

         source += list->itemsize;

         if (0 != cx_ll_insert_at(list, node, source)) {

             return i;

         }

         node = node->next;

     }

     return n;

 }

 static int cx_ll_insert(

         struct cx_list_s *list,

         size_t index,

         void const *elem

 ) {

     return cx_ll_insert_array(list, index, elem, 1) != 1;

 }

 static int cx_ll_add(

         struct cx_list_s *list,

         void const *elem

 ) {

     return cx_ll_insert(list, list->size, elem);

 }

 static size_t cx_ll_add_array(

         struct cx_list_s *list,

         void const *array,

         size_t n

 ) {

     return cx_ll_insert_array(list, list->size, array, n);

 }

 static int cx_ll_remove(

         struct cx_list_s *list,

         size_t index

 ) {

     cx_linked_list *ll = (cx_linked_list *) list;

     cx_linked_list_node *node = cx_ll_node_at(ll, index);

     // out-of-bounds check

     if (node == NULL) return 1;

     // remove

     cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,

                           CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);

     // adjust size

     list->size--;

     // free and return

     cxFree(list->allocator, node);

     return 0;

 }

 static void *cx_ll_at(

         struct cx_list_s const *list,

         size_t index

 ) {

     cx_linked_list *ll = (cx_linked_list *) list;

     cx_linked_list_node *node = cx_ll_node_at(ll, index);

     return node == NULL ? NULL : node->payload;

 }

 static size_t cx_ll_find(

         struct cx_list_s const *list,

         void const *elem

 ) {

     return cx_linked_list_find(((cx_linked_list *) list)->begin,

                                CX_LL_LOC_NEXT, CX_LL_LOC_DATA,

                                list->cmpfunc, elem);

 }

 static void cx_ll_sort(struct cx_list_s *list) {

     cx_linked_list *ll = (cx_linked_list *) list;

     cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,

                         CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,

                         list->cmpfunc);

 }

 static void cx_ll_reverse(struct cx_list_s *list) {

     cx_linked_list *ll = (cx_linked_list *) list;

     cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT);

 }

 static int cx_ll_compare(

         struct cx_list_s const *list,

         struct cx_list_s const *other

 ) {

     cx_linked_list *left = (cx_linked_list *) list;

     cx_linked_list *right = (cx_linked_list *) other;

     return cx_linked_list_compare(left->begin, right->begin,

                                   CX_LL_LOC_NEXT, CX_LL_LOC_DATA,

                                   list->cmpfunc);

 }

 static bool cx_ll_iter_valid(void const *it) {

     struct cx_iterator_s const *iter = it;

     return iter->elem_handle != NULL;

 }

 static void cx_ll_iter_next(void *it) {

     struct cx_iterator_base_s *itbase = it;

     if (itbase->remove) {

         itbase->remove = false;

         struct cx_mut_iterator_s *iter = it;

         cx_linked_list *ll = iter->src_handle;

         cx_linked_list_node *node = iter->elem_handle;

         iter->elem_handle = node->next;

         cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,

                               CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);

         ll->base.size--;

         cxFree(ll->base.allocator, node);

     } else {

         struct cx_iterator_s *iter = it;

         iter->index++;

         cx_linked_list_node *node = iter->elem_handle;

         iter->elem_handle = node->next;

     }

 }

 static void *cx_ll_iter_current(void const *it) {

     struct cx_iterator_s const *iter = it;

     cx_linked_list_node *node = iter->elem_handle;

     return node->payload;

 }

 static bool cx_ll_iter_flag_rm(void *it) {

     struct cx_iterator_base_s *iter = it;

     if (iter->mutating) {

         iter->remove = true;

         return true;

     } else {

         return false;

     }

 }

 static CxIterator cx_ll_iterator(

         struct cx_list_s const *list,

         size_t index

 ) {

     CxIterator iter;

     iter.index = index;

     iter.src_handle = list;

     iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index);

     iter.base.valid = cx_ll_iter_valid;

     iter.base.current = cx_ll_iter_current;

     iter.base.next = cx_ll_iter_next;

     iter.base.flag_removal = cx_ll_iter_flag_rm;

     iter.base.mutating = false;

     iter.base.remove = false;

     return iter;

 }

 static CxMutIterator cx_ll_mut_iterator(

         struct cx_list_s *list,

         size_t index

 ) {

     CxIterator it = cx_ll_iterator(list, index);

     it.base.mutating = true;

     // we know the iterators share the same memory layout

     CxMutIterator iter;

     memcpy(&iter, &it, sizeof(CxMutIterator));

     return iter;

 }

 static int cx_ll_insert_iter(

         CxMutIterator *iter,

         void const *elem,

         int prepend

 ) {

     struct cx_list_s *list = iter->src_handle;

     cx_linked_list_node *node = iter->elem_handle;

     if (node != NULL) {

         assert(prepend >= 0 && prepend <= 1);

         cx_linked_list_node *choice[2] = {node, node->prev};

         int result = cx_ll_insert_at(list, choice[prepend], elem);

         iter->index += prepend * (0 == result);

         return result;

     } else {

         int result = cx_ll_insert(list, list->size, elem);

         iter->index = list->size;

         return result;

     }

 }

 static void cx_ll_destructor(CxList *list) {

     cx_linked_list *ll = (cx_linked_list *) list;

     cx_linked_list_node *node = ll->begin;

     while (node) {

         void *next = node->next;

         cxFree(list->allocator, node);

         node = next;

     }

     // do not free the list pointer, this is just a destructor!

 }

 static cx_list_class cx_linked_list_class = {

         cx_ll_destructor,

         cx_ll_add,

         cx_ll_add_array,

         cx_ll_insert,

         cx_ll_insert_array,

         cx_ll_insert_iter,

         cx_ll_remove,

         cx_ll_at,

         cx_ll_find,

         cx_ll_sort,

         cx_ll_compare,

         cx_ll_reverse,

         cx_ll_iterator,

         cx_ll_mut_iterator,

 };

 CxList *cxLinkedListCreate(

         CxAllocator const *allocator,

         CxListComparator comparator,

         size_t item_size

 ) {

     cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));

     if (list == NULL) return NULL;

     list->base.cl = &cx_linked_list_class;

     list->base.allocator = allocator;

     list->base.cmpfunc = comparator;

     list->base.itemsize = item_size;

     list->base.capacity = SIZE_MAX;

     return (CxList *) list;

 }