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 <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) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))

 void *cx_linked_list_at(

         void *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 *cur = start;

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

         cur = ll_advance(cur);

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

     }

     return cur;

 }

 size_t cx_linked_list_find(

         void *start,

         ptrdiff_t loc_advance,

         ptrdiff_t loc_data,

         int follow_ptr,

         CxListComparator cmp_func,

         void *elem

 ) {

     assert(start != NULL);

     assert(loc_advance >= 0);

     assert(loc_data >= 0);

     assert(cmp_func);

     void *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 *node,

         ptrdiff_t loc_prev

 ) {

     return cx_linked_list_last(node, loc_prev);

 }

 void *cx_linked_list_last(

         void *node,

         ptrdiff_t loc_next

 ) {

     assert(node != NULL);

     assert(loc_next >= 0);

     void *cur = node;

     void *last;

     do {

         last = cur;

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

     return last;

 }

 void *cx_linked_list_prev(

         void *begin,

         ptrdiff_t loc_next,

         void *node

 ) {

     assert(begin != NULL);

     assert(node != NULL);

     assert(loc_next >= 0);

     if (begin == node) return NULL;

     void *cur = begin;

     void *next;

     while (1) {

         next = ll_next(cur);

         if (next == node) return 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 *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,

         int follow_ptr,

         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;

     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;

     for (size_t i = 0; i < length - 1; i++) {

         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,

         int follow_ptr,

         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, follow_ptr,

                                                  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, follow_ptr, cmp_func);

             // merge sorted list with (also sorted) remainder

             *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,

                                                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);

     }

 }

 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 {

     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 *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(

         cx_list_s *list,

         size_t index,

         void *elem

 ) {

     // out-of bounds check

     if (index > list->size) return 1;

     // cast a linked list pointer

     cx_linked_list *ll = (cx_linked_list *) list;

     // 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);

     // find position efficiently

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

     // insert

     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 int cx_ll_add(

         cx_list_s *list,

         void *elem

 ) {

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

 }

 static int cx_pll_insert(

         cx_list_s *list,

         size_t index,

         void *elem

 ) {

     return cx_ll_insert(list, index, &elem);

 }

 static int cx_pll_add(

         cx_list_s *list,

         void *elem

 ) {

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

 }

 static int cx_ll_remove(

         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(

         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);

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

 }

 static void *cx_pll_at(

         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);

     return node == NULL ? NULL : *(void **) node->payload;

 }

 static size_t cx_ll_find(

         cx_list_s *list,

         void *elem

 ) {

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

                                CX_LL_LOC_NEXT, CX_LL_LOC_DATA,

                                0, list->cmpfunc, elem);

 }

 static size_t cx_pll_find(

         cx_list_s *list,

         void *elem

 ) {

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

                                CX_LL_LOC_NEXT, CX_LL_LOC_DATA,

                                1, list->cmpfunc, elem);

 }

 static void cx_ll_sort(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,

                         0, list->cmpfunc);

 }

 static void cx_pll_sort(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,

                         1, list->cmpfunc);

 }

 static cx_list_class cx_linked_list_class = {

         cx_ll_add,

         cx_ll_insert,

         cx_ll_remove,

         cx_ll_at,

         cx_ll_find,

         cx_ll_sort

 };

 static cx_list_class cx_pointer_linked_list_class = {

         cx_pll_add,

         cx_pll_insert,

         cx_ll_remove,

         cx_pll_at,

         cx_pll_find,

         cx_pll_sort

 };

 CxList cxLinkedListCreate(

         CxAllocator allocator,

         CxListComparator comparator,

         size_t item_size

 ) {

     cx_linked_list *list = cxMalloc(allocator, 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;

     list->base.size = 0;

     list->begin = NULL;

     list->end = NULL;

     return (CxList) list;

 }

 CxList cxPointerLinkedListCreate(

         CxAllocator allocator,

         CxListComparator comparator

 ) {

     cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));

     if (list == NULL)

         return NULL;

     list->base.cl = &cx_pointer_linked_list_class;

     list->base.allocator = allocator;

     list->base.cmpfunc = comparator;

     list->base.itemsize = sizeof(void *);

     list->base.capacity = SIZE_MAX;

     list->base.size = 0;

     list->begin = NULL;

     list->end = NULL;

     return (CxList) list;

 }

 void cxLinkedListDestroy(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;

     }

     cxFree(list->allocator, list);

 }