ucx: src/linked_list.c@75ae1dccd101 (annotated)

src/linked_list.c@75ae1dccd101 (annotated)

src/linked_list.c

Tue, 05 Oct 2021 16:33:11 +0200

author: Mike Becker <universe@uap-core.de>
date: Tue, 05 Oct 2021 16:33:11 +0200
changeset 468: 75ae1dccd101
parent 467: 95e42a963520
child 469: 0458bff0b1cd
permissions: -rw-r--r--

add cx_linked_list_sort()

 /*
  * 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))
 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
     size_t i = start_index;
     void *cur = start;
     while (i != index && cur != NULL) {
         cur = CX_LL_PTR(cur, loc_advance);
         i < index ? i++ : i--;
     }
     return cur;
 }
 void *cx_linked_list_last(void *begin, ptrdiff_t loc_next) {
     if (begin == NULL)
         return NULL;
     void *cur = begin;
     void *last;
     do {
         last = cur;
     } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL);
     return last;
 }
 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 = cx_linked_list_last(*begin, loc_next);
     } else {
         last = *end;
     }
     if (last == NULL) {
         assert(begin != NULL);
         *begin = new_node;
     } else {
         // if there is a last node, update its next pointer
         CX_LL_PTR(last, loc_next) = new_node;
     }
     // if there is an end pointer, update it
     if (end != NULL) {
         *end = cx_linked_list_last(new_node, loc_next);
     }
     // if the nodes use a prev pointer, update it
     if (loc_prev >= 0) {
         CX_LL_PTR(new_node, loc_prev) = last;
     }
 }
 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
     size_t size = 0;
     while (node != NULL) {
         node = CX_LL_PTR(node, loc_next);
         size++;
     }
     return size;
 }
 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
 #define ll_next(node) CX_LL_PTR(node, loc_next)
 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
 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++) {
         ll_next(sorted[i]) = sorted[i + 1];
         if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i];
     }
     ll_next(sorted[length - 1]) = NULL;
     void *ret = sorted[0];
     if (sorted != sbo) {
         free(sorted);
     }
     return ret;
 }
 void cx_linked_list_sort(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);
     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);
     }
 }
 #undef ll_next
 #undef ll_data
 /* 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)
 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 node
     cx_linked_list_node *node = cxMalloc(list->allocator,
                                          sizeof(cx_linked_list_node) + list->itemsize);
     // sortir if failed
     if (node == NULL) return 1;
     // copy payload to the new node
     memcpy(node->payload, elem, list->itemsize);
     // check if this is the first node
     if (ll->begin == NULL) {
         node->prev = node->next = NULL;
         ll->begin = ll->end = node;
     } else {
         // check if this shall be the new end node
         if (index == list->size) {
             ll->end->next = node;
             node->prev = ll->end;
             node->next = NULL;
             ll->end = node;
         }
             // check if this shall be the new start node
         else if (index == 0) {
             ll->begin->prev = node;
             node->next = ll->begin;
             node->prev = NULL;
             ll->begin = node;
         } else {
             // find the node at the current index
             cx_linked_list_node *cur = cx_ll_node_at(ll, index);
             // insert before that node
             // (we know all ptr are non-null because we handled all other cases before)
             node->next = cur;
             node->prev = cur->prev;
             cur->prev = node;
             node->prev->next = 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;
     // change left side connection
     if (node->prev == NULL) {
         ll->begin = node->next;
     } else {
         node->prev->next = node->next;
     }
     // change right side connection
     if (node->next == NULL) {
         ll->end = node->prev;
     } else {
         node->next->prev = node->prev;
     }
     // 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) {
     CxListComparator cmp = list->cmpfunc;
     cx_linked_list *ll = (cx_linked_list *) list;
     size_t index;
     cx_linked_list_node *node = ll->begin;
     for (index = 0; index < list->size; index++) {
         void *current = node->payload;
         if (cmp(current, elem) == 0) {
             return index;
         }
         node = node->next;
     }
     return index;
 }
 static size_t cx_pll_find(cx_list_s *list, void *elem) {
     CxListComparator cmp = list->cmpfunc;
     cx_linked_list *ll = (cx_linked_list *) list;
     size_t index;
     cx_linked_list_node *node = ll->begin;
     for (index = 0; index < list->size; index++) {
         void *current = *(void **) node->payload;
         if (cmp(current, elem) == 0) {
             return index;
         }
         node = node->next;
     }
     return index;
 }
 static void *cx_ll_last(cx_list_s *list) {
     cx_linked_list *ll = (cx_linked_list *) list;
     cx_linked_list_node *last = ll->end;
     return last == NULL ? NULL : last->payload;
 }
 static void *cx_pll_last(cx_list_s *list) {
     cx_linked_list *ll = (cx_linked_list *) list;
     cx_linked_list_node *last = ll->end;
     return last == NULL ? NULL : *(void **) last->payload;
 }
 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_last
 };
 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_last
 };
 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);
 }

Mercurial > hg > ucx / annotate

src/linked_list.c@75ae1dccd101 (annotated)

src/linked_list.c