ucx: src/linked_list.c@75ae1dccd101

     1 /*

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

     3  *

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

     5  *

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

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

     8  *

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

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

    11  *

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

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

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

    15  *

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

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

    18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

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

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

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

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

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

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

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

    26  * POSSIBILITY OF SUCH DAMAGE.

    27  */

    29 #include "cx/linked_list.h"

    30 #include <stdint.h>

    31 #include <string.h>

    32 #include <assert.h>

    34 /* LOW LEVEL LINKED LIST FUNCTIONS */

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

    38 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {

    39     size_t i = start_index;

    40     void *cur = start;

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

    42         cur = CX_LL_PTR(cur, loc_advance);

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

    44     }

    45     return cur;

    46 }

    48 void *cx_linked_list_last(void *begin, ptrdiff_t loc_next) {

    49     if (begin == NULL)

    50         return NULL;

    52     void *cur = begin;

    53     void *last;

    54     do {

    55         last = cur;

    56     } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL);

    58     return last;

    59 }

    61 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {

    62     void *last;

    63     if (end == NULL) {

    64         assert(begin != NULL);

    65         last = cx_linked_list_last(*begin, loc_next);

    66     } else {

    67         last = *end;

    68     }

    69     if (last == NULL) {

    70         assert(begin != NULL);

    71         *begin = new_node;

    72     } else {

    73         // if there is a last node, update its next pointer

    74         CX_LL_PTR(last, loc_next) = new_node;

    75     }

    77     // if there is an end pointer, update it

    78     if (end != NULL) {

    79         *end = cx_linked_list_last(new_node, loc_next);

    80     }

    82     // if the nodes use a prev pointer, update it

    83     if (loc_prev >= 0) {

    84         CX_LL_PTR(new_node, loc_prev) = last;

    85     }

    86 }

    88 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {

    89     size_t size = 0;

    90     while (node != NULL) {

    91         node = CX_LL_PTR(node, loc_next);

    92         size++;

    93     }

    94     return size;

    95 }

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

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

    99 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))

   101 static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next,

   102                                        ptrdiff_t loc_data, int follow_ptr,

   103                                        size_t length, void *ls, void *le, void *re,

   104                                        CxListComparator cmp_func) {

   105     const size_t sbo_len = 1024;

   106     void *sbo[sbo_len];

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

   108     void *rc, *lc;

   110     lc = ls;

   111     rc = le;

   112     size_t n = 0;

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

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

   115             sorted[n] = lc;

   116             lc = ll_next(lc);

   117         } else {

   118             sorted[n] = rc;

   119             rc = ll_next(rc);

   120         }

   121         n++;

   122     }

   123     while (lc && lc != le) {

   124         sorted[n] = lc;

   125         lc = ll_next(lc);

   126         n++;

   127     }

   128     while (rc && rc != re) {

   129         sorted[n] = rc;

   130         rc = ll_next(rc);

   131         n++;

   132     }

   134     // Update pointer

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

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

   137         ll_next(sorted[i]) = sorted[i + 1];

   138         if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i];

   139     }

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

   142     void *ret = sorted[0];

   143     if (sorted != sbo) {

   144         free(sorted);

   145     }

   146     return ret;

   147 }

   149 void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,

   150                          ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {

   151     assert(begin != NULL);

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

   155     // set start node

   156     ls = *begin;

   158     // check how many elements are already sorted

   159     lc = ls;

   160     size_t ln = 1;

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

   162         lc = ll_next(lc);

   163         ln++;

   164     }

   165     le = ll_next(lc);

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

   168     if (le != NULL) {

   169         void *rc;

   170         size_t rn = 1;

   171         rc = le;

   172         // skip already sorted elements

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

   174             rc = ll_next(rc);

   175             rn++;

   176         }

   177         re = ll_next(rc);

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

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

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

   183         // Something left? Sort it!

   184         size_t remainder_length = cx_linked_list_size(re, loc_next);

   185         if (remainder_length > 0) {

   186             void *remainder = re;

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

   189             // merge sorted list with (also sorted) remainder

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

   191                                                ln + rn + remainder_length,

   192                                                sorted, remainder, NULL, cmp_func);

   193         } else {

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

   195             *begin = sorted;

   196         }

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

   198     }

   199 }

   201 #undef ll_next

   202 #undef ll_data

   204 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */

   206 typedef struct cx_linked_list_node cx_linked_list_node;

   207 struct cx_linked_list_node {

   208     cx_linked_list_node *prev;

   209     cx_linked_list_node *next;

   210     char payload[];

   211 };

   213 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)

   214 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)

   216 typedef struct {

   217     cx_list_s base;

   218     cx_linked_list_node *begin;

   219     cx_linked_list_node *end;

   220 } cx_linked_list;

   222 static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) {

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

   224         return NULL;

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

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

   227     } else {

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

   229     }

   230 }

   232 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {

   233     // out-of bounds check

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

   236     // cast a linked list pointer

   237     cx_linked_list *ll = (cx_linked_list *) list;

   239     // create the new node

   240     cx_linked_list_node *node = cxMalloc(list->allocator,

   241                                          sizeof(cx_linked_list_node) + list->itemsize);

   243     // sortir if failed

   244     if (node == NULL) return 1;

   246     // copy payload to the new node

   247     memcpy(node->payload, elem, list->itemsize);

   249     // check if this is the first node

   250     if (ll->begin == NULL) {

   251         node->prev = node->next = NULL;

   252         ll->begin = ll->end = node;

   253     } else {

   254         // check if this shall be the new end node

   255         if (index == list->size) {

   256             ll->end->next = node;

   257             node->prev = ll->end;

   258             node->next = NULL;

   259             ll->end = node;

   260         }

   261             // check if this shall be the new start node

   262         else if (index == 0) {

   263             ll->begin->prev = node;

   264             node->next = ll->begin;

   265             node->prev = NULL;

   266             ll->begin = node;

   267         } else {

   268             // find the node at the current index

   269             cx_linked_list_node *cur = cx_ll_node_at(ll, index);

   271             // insert before that node

   272             // (we know all ptr are non-null because we handled all other cases before)

   273             node->next = cur;

   274             node->prev = cur->prev;

   275             cur->prev = node;

   276             node->prev->next = node;

   277         }

   278     }

   280     // increase the size and return

   281     list->size++;

   282     return 0;

   283 }

   285 static int cx_ll_add(cx_list_s *list, void *elem) {

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

   287 }

   289 static int cx_pll_insert(cx_list_s *list, size_t index, void *elem) {

   290     return cx_ll_insert(list, index, &elem);

   291 }

   293 static int cx_pll_add(cx_list_s *list, void *elem) {

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

   295 }

   297 static int cx_ll_remove(cx_list_s *list, size_t index) {

   298     cx_linked_list *ll = (cx_linked_list *) list;

   299     cx_linked_list_node *node = cx_ll_node_at(ll, index);

   301     // out-of-bounds check

   302     if (node == NULL) return 1;

   304     // change left side connection

   305     if (node->prev == NULL) {

   306         ll->begin = node->next;

   307     } else {

   308         node->prev->next = node->next;

   309     }

   311     // change right side connection

   312     if (node->next == NULL) {

   313         ll->end = node->prev;

   314     } else {

   315         node->next->prev = node->prev;

   316     }

   318     // adjust size

   319     list->size--;

   321     // free and return

   322     cxFree(list->allocator, node);

   324     return 0;

   325 }

   327 static void *cx_ll_at(cx_list_s *list, size_t index) {

   328     cx_linked_list *ll = (cx_linked_list *) list;

   329     cx_linked_list_node *node = cx_ll_node_at(ll, index);

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

   331 }

   333 static void *cx_pll_at(cx_list_s *list, size_t index) {

   334     cx_linked_list *ll = (cx_linked_list *) list;

   335     cx_linked_list_node *node = cx_ll_node_at(ll, index);

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

   337 }

   339 static size_t cx_ll_find(cx_list_s *list, void *elem) {

   340     CxListComparator cmp = list->cmpfunc;

   341     cx_linked_list *ll = (cx_linked_list *) list;

   343     size_t index;

   344     cx_linked_list_node *node = ll->begin;

   345     for (index = 0; index < list->size; index++) {

   346         void *current = node->payload;

   347         if (cmp(current, elem) == 0) {

   348             return index;

   349         }

   350         node = node->next;

   351     }

   352     return index;

   353 }

   355 static size_t cx_pll_find(cx_list_s *list, void *elem) {

   356     CxListComparator cmp = list->cmpfunc;

   357     cx_linked_list *ll = (cx_linked_list *) list;

   359     size_t index;

   360     cx_linked_list_node *node = ll->begin;

   361     for (index = 0; index < list->size; index++) {

   362         void *current = *(void **) node->payload;

   363         if (cmp(current, elem) == 0) {

   364             return index;

   365         }

   366         node = node->next;

   367     }

   368     return index;

   369 }

   371 static void *cx_ll_last(cx_list_s *list) {

   372     cx_linked_list *ll = (cx_linked_list *) list;

   373     cx_linked_list_node *last = ll->end;

   374     return last == NULL ? NULL : last->payload;

   375 }

   377 static void *cx_pll_last(cx_list_s *list) {

   378     cx_linked_list *ll = (cx_linked_list *) list;

   379     cx_linked_list_node *last = ll->end;

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

   381 }

   383 static cx_list_class cx_linked_list_class = {

   384         cx_ll_add,

   385         cx_ll_insert,

   386         cx_ll_remove,

   387         cx_ll_at,

   388         cx_ll_find,

   389         cx_ll_last

   390 };

   392 static cx_list_class cx_pointer_linked_list_class = {

   393         cx_pll_add,

   394         cx_pll_insert,

   395         cx_ll_remove,

   396         cx_pll_at,

   397         cx_pll_find,

   398         cx_pll_last

   399 };

   401 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {

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

   403     if (list == NULL)

   404         return NULL;

   406     list->base.cl = &cx_linked_list_class;

   407     list->base.allocator = allocator;

   408     list->base.cmpfunc = comparator;

   409     list->base.itemsize = item_size;

   410     list->base.capacity = SIZE_MAX;

   411     list->base.size = 0;

   413     list->begin = NULL;

   414     list->end = NULL;

   416     return (CxList) list;

   417 }

   419 CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator) {

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

   421     if (list == NULL)

   422         return NULL;

   424     list->base.cl = &cx_pointer_linked_list_class;

   425     list->base.allocator = allocator;

   426     list->base.cmpfunc = comparator;

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

   428     list->base.capacity = SIZE_MAX;

   429     list->base.size = 0;

   431     list->begin = NULL;

   432     list->end = NULL;

   434     return (CxList) list;

   435 }

   437 void cxLinkedListDestroy(CxList list) {

   438     cx_linked_list *ll = (cx_linked_list *) list;

   440     cx_linked_list_node *node = ll->begin;

   441     while (node) {

   442         void *next = node->next;

   443         cxFree(list->allocator, node);

   444         node = next;

   445     }

   447     cxFree(list->allocator, list);

   448 }

Mercurial > hg > ucx / file revision

src/linked_list.c@75ae1dccd101

src/linked_list.c