ucx: src/linked_list.c@d402fead3386 (annotated)

src/linked_list.c@d402fead3386 (annotated)

src/linked_list.c

Thu, 26 Jan 2023 20:59:36 +0100

author: Mike Becker <universe@uap-core.de>
date: Thu, 26 Jan 2023 20:59:36 +0100
changeset 641: d402fead3386
parent 640: 55cc3b373c5e
child 647: 2e6e9d9f2159
child 650: 77021e06b1a8
permissions: -rw-r--r--

add new pointer list wrapper - resolves #234

since we need a thread local variable, this drops C99 support

 /*
  * 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_element(
         struct cx_list_s *list,
         size_t index,
         void const *element
 ) {
     return 1 != cx_ll_insert_array(list, index, element, 1);
 }
 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 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_element(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_insert_element,
         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,
 };
 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;
 }

Mercurial > hg > ucx / annotate

src/linked_list.c@d402fead3386 (annotated)

src/linked_list.c