ucx: src/linked_list.c@87b2cdd668ed

     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>

    33 /* LOW LEVEL LINKED LIST FUNCTIONS */

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

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

    38     size_t i = start_index;

    39     void *cur = start;

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

    41         cur = *CX_LL_PTR(cur, loc_advance);

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

    43     }

    44     return cur;

    45 }

    47 void *cx_linked_list_last(void **begin, void **end, ptrdiff_t loc_next) {

    48     if (end != NULL) {

    49         return *end;

    50     } else {

    51         if (begin == NULL || *begin == NULL)

    52             return NULL;

    54         void *cur = *begin;

    55         void *last;

    56         do {

    57             last = cur;

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

    60         return last;

    61     }

    62 }

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

    65     void *last = cx_linked_list_last(begin, end, loc_next);

    66     if (last == NULL) {

    67         if (begin == NULL) {

    68             // no current list and no begin ptr to write to - we don't find something to append to

    69             return 1;

    70         } else {

    71             // start fresh list

    72             *begin = new_node;

    73         }

    74     } else {

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

    76         void **next = CX_LL_PTR(last, loc_next);

    77         *next = new_node;

    78     }

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

    81     if (end != NULL) {

    82         *end = cx_linked_list_last(&new_node, NULL, loc_next);

    83     }

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

    86     if (loc_prev >= 0) {

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

    88         *prev = last;

    89     }

    91     return 0;

    92 }

    94 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */

    96 typedef struct cx_linked_list_node cx_linked_list_node;

    97 struct cx_linked_list_node {

    98     cx_linked_list_node *prev;

    99     cx_linked_list_node *next;

   100     char payload[];

   101 };

   103 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)

   104 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)

   106 typedef struct {

   107     cx_list_s base;

   108     cx_linked_list_node *begin;

   109     cx_linked_list_node *end;

   110 } cx_linked_list;

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

   113     cx_linked_list *ll = (cx_linked_list *) list;

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

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

   117     if (node == NULL)

   118         return 1;

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

   121     node->next = NULL;

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

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

   125     } else {

   126         // per contract of this linked list we know that end must be non-null

   127         ll->end->next = node;

   128         ll->end = node;

   129     }

   130     list->size++;

   132     return 0;

   133 }

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

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

   137         return NULL;

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

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

   140     } else {

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

   142     }

   143 }

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

   146     cx_linked_list *ll = (cx_linked_list *) list;

   147     // TODO: implement using low level API

   148     return 1;

   149 }

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

   152     cx_linked_list *ll = (cx_linked_list *) list;

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

   155     // out-of-bounds check

   156     if (node == NULL) return 1;

   158     // change left side connection

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

   160         ll->begin = node->next;

   161     } else {

   162         node->prev->next = node->next;

   163     }

   165     // change right side connection

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

   167         ll->end = node->prev;

   168     } else {

   169         node->next->prev = node->prev;

   170     }

   172     // adjust size

   173     list->size--;

   175     // free and return

   176     cxFree(list->allocator, node);

   178     return 0;

   179 }

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

   182     cx_linked_list *ll = (cx_linked_list *) list;

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

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

   185 }

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

   188     CxListComparator cmp = list->cmpfunc;

   189     cx_linked_list *ll = (cx_linked_list *) list;

   191     size_t index;

   192     cx_linked_list_node *node = ll->begin;

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

   194         void *current = node->payload;

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

   196             return index;

   197         }

   198         node = node->next;

   199     }

   200     return index;

   201 }

   203 static void *cx_ll_last(cx_list_s *list) {

   204     cx_linked_list *ll = (cx_linked_list *) list;

   205     cx_linked_list_node *last = cx_linked_list_last(NULL, (void **) &ll->end, CX_LL_LOC_NEXT);

   206     return &last->payload;

   207 }

   209 cx_list_class cx_linked_list_class = {

   210         cx_ll_add,

   211         cx_ll_insert,

   212         cx_ll_remove,

   213         cx_ll_at,

   214         cx_ll_find,

   215         cx_ll_last

   216 };

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

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

   220     if (list == NULL)

   221         return NULL;

   223     list->base.cl = &cx_linked_list_class;

   224     list->base.allocator = allocator;

   225     list->base.cmpfunc = comparator;

   226     list->base.itemsize = item_size;

   227     list->base.capacity = SIZE_MAX;

   228     list->base.size = 0;

   230     list->begin = NULL;

   231     list->end = NULL;

   233     return (CxList) list;

   234 }

   236 void cxLinkedListDestroy(CxList list) {

   237     cx_linked_list *ll = (cx_linked_list *) list;

   239     cx_linked_list_node *node = ll->begin;

   240     while (node) {

   241         void *next = node->next;

   242         cxFree(list->allocator, node);

   243         node = next;

   244     }

   246     cxFree(list->allocator, list);

   247 }

   249 size_t cxLinkedListRecalculateSize(CxList list) {

   250     cx_linked_list *ll = (cx_linked_list *) list;

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

   253         ll->base.size = 0;

   254         ll->end = NULL;

   255         return 0;

   256     } else {

   257         cx_linked_list_node *cur = ll->begin;

   258         cx_linked_list_node *last;

   259         size_t size = 0;

   260         do {

   261             last = cur;

   262             size++;

   263         } while ((cur = cur->next) != NULL);

   264         ll->end = last;

   265         ll->base.size = size;

   266         return size;

   267     }

   268 }

Mercurial > hg > ucx / file revision

src/linked_list.c@87b2cdd668ed

src/linked_list.c