ucx: src/linked_list.c@95e42a963520

remove unused cxLinkedListRecalculateSize()

It is not clear what this function was ever supposed to do.

     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         void **next = CX_LL_PTR(last, loc_next);

    75         *next = new_node;

    76     }

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

    79     if (end != NULL) {

    80         *end = cx_linked_list_last(new_node, loc_next);

    81     }

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

    84     if (loc_prev >= 0) {

    85         void **prev = CX_LL_PTR(new_node, loc_prev);

    86         *prev = last;

    87     }

    88 }

    90 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */

    92 typedef struct cx_linked_list_node cx_linked_list_node;

    93 struct cx_linked_list_node {

    94     cx_linked_list_node *prev;

    95     cx_linked_list_node *next;

    96     char payload[];

    97 };

    99 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)

   100 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)

   102 typedef struct {

   103     cx_list_s base;

   104     cx_linked_list_node *begin;

   105     cx_linked_list_node *end;

   106 } cx_linked_list;

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

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

   110         return NULL;

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

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

   113     } else {

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

   115     }

   116 }

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

   119     // out-of bounds check

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

   122     // cast a linked list pointer

   123     cx_linked_list *ll = (cx_linked_list *) list;

   125     // create the new node

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

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

   129     // sortir if failed

   130     if (node == NULL) return 1;

   132     // copy payload to the new node

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

   135     // check if this is the first node

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

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

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

   139     } else {

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

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

   142             ll->end->next = node;

   143             node->prev = ll->end;

   144             node->next = NULL;

   145             ll->end = node;

   146         }

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

   148         else if (index == 0) {

   149             ll->begin->prev = node;

   150             node->next = ll->begin;

   151             node->prev = NULL;

   152             ll->begin = node;

   153         } else {

   154             // find the node at the current index

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

   157             // insert before that node

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

   159             node->next = cur;

   160             node->prev = cur->prev;

   161             cur->prev = node;

   162             node->prev->next = node;

   163         }

   164     }

   166     // increase the size and return

   167     list->size++;

   168     return 0;

   169 }

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

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

   173 }

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

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

   177 }

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

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

   181 }

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

   184     cx_linked_list *ll = (cx_linked_list *) list;

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

   187     // out-of-bounds check

   188     if (node == NULL) return 1;

   190     // change left side connection

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

   192         ll->begin = node->next;

   193     } else {

   194         node->prev->next = node->next;

   195     }

   197     // change right side connection

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

   199         ll->end = node->prev;

   200     } else {

   201         node->next->prev = node->prev;

   202     }

   204     // adjust size

   205     list->size--;

   207     // free and return

   208     cxFree(list->allocator, node);

   210     return 0;

   211 }

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

   214     cx_linked_list *ll = (cx_linked_list *) list;

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

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

   217 }

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

   220     cx_linked_list *ll = (cx_linked_list *) list;

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

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

   223 }

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

   226     CxListComparator cmp = list->cmpfunc;

   227     cx_linked_list *ll = (cx_linked_list *) list;

   229     size_t index;

   230     cx_linked_list_node *node = ll->begin;

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

   232         void *current = node->payload;

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

   234             return index;

   235         }

   236         node = node->next;

   237     }

   238     return index;

   239 }

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

   242     CxListComparator cmp = list->cmpfunc;

   243     cx_linked_list *ll = (cx_linked_list *) list;

   245     size_t index;

   246     cx_linked_list_node *node = ll->begin;

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

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

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

   250             return index;

   251         }

   252         node = node->next;

   253     }

   254     return index;

   255 }

   257 static void *cx_ll_last(cx_list_s *list) {

   258     cx_linked_list *ll = (cx_linked_list *) list;

   259     cx_linked_list_node *last = ll->end;

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

   261 }

   263 static void *cx_pll_last(cx_list_s *list) {

   264     cx_linked_list *ll = (cx_linked_list *) list;

   265     cx_linked_list_node *last = ll->end;

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

   267 }

   269 static cx_list_class cx_linked_list_class = {

   270         cx_ll_add,

   271         cx_ll_insert,

   272         cx_ll_remove,

   273         cx_ll_at,

   274         cx_ll_find,

   275         cx_ll_last

   276 };

   278 static cx_list_class cx_pointer_linked_list_class = {

   279         cx_pll_add,

   280         cx_pll_insert,

   281         cx_ll_remove,

   282         cx_pll_at,

   283         cx_pll_find,

   284         cx_pll_last

   285 };

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

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

   289     if (list == NULL)

   290         return NULL;

   292     list->base.cl = &cx_linked_list_class;

   293     list->base.allocator = allocator;

   294     list->base.cmpfunc = comparator;

   295     list->base.itemsize = item_size;

   296     list->base.capacity = SIZE_MAX;

   297     list->base.size = 0;

   299     list->begin = NULL;

   300     list->end = NULL;

   302     return (CxList) list;

   303 }

   305 CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator) {

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

   307     if (list == NULL)

   308         return NULL;

   310     list->base.cl = &cx_pointer_linked_list_class;

   311     list->base.allocator = allocator;

   312     list->base.cmpfunc = comparator;

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

   314     list->base.capacity = SIZE_MAX;

   315     list->base.size = 0;

   317     list->begin = NULL;

   318     list->end = NULL;

   320     return (CxList) list;

   321 }

   323 void cxLinkedListDestroy(CxList list) {

   324     cx_linked_list *ll = (cx_linked_list *) list;

   326     cx_linked_list_node *node = ll->begin;

   327     while (node) {

   328         void *next = node->next;

   329         cxFree(list->allocator, node);

   330         node = next;

   331     }

   333     cxFree(list->allocator, list);

   334 }

Mercurial > hg > ucx / file revision

src/linked_list.c@95e42a963520

src/linked_list.c