ucx: src/linked_list.c@da66264af8ad

     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_last(void **begin, void **end, ptrdiff_t loc_next) {

    38     if (end != NULL) {

    39         return *end;

    40     } else {

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

    42             return NULL;

    44         void *cur = *begin;

    45         void *last;

    46         do {

    47             last = cur;

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

    50         return last;

    51     }

    52 }

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

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

    56     if (last == NULL) {

    57         if (begin == NULL) {

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

    59             return 1;

    60         } else {

    61             // start fresh list

    62             *begin = new_node;

    63         }

    64     } else {

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

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

    67         *next = new_node;

    68     }

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

    71     if (end != NULL) {

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

    73     }

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

    76     if (loc_prev >= 0) {

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

    78         *prev = last;

    79     }

    81     return 0;

    82 }

    84 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */

    86 struct cx_linked_list_node {

    87     void *prev;

    88     void *next;

    89     char payload[];

    90 };

    92 typedef struct {

    93     void *begin;

    94     void *end;

    95     ptrdiff_t loc_prev;

    96     ptrdiff_t loc_next;

    97 } cx_linked_list;

    99 int cx_ll_add(cx_list *list, void *elem) {

   100     cx_linked_list *listdata = (cx_linked_list *) list->listdata;

   101     CxAllocator allocator = list->allocator;

   103     struct cx_linked_list_node *node = cxMalloc(allocator,

   104                                                 sizeof(struct cx_linked_list_node) + list->itemsize);

   105     if (node == NULL)

   106         return 1;

   108     node->next = NULL;

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

   111     int ret = cx_linked_list_add(

   112             &listdata->begin,

   113             &listdata->end,

   114             offsetof(struct cx_linked_list_node, prev),

   115             offsetof(struct cx_linked_list_node, next),

   116             node

   117     );

   118     if (ret == 0) {

   119         list->size++;

   120         return 0;

   121     } else {

   122         return ret;

   123     }

   124 }

   126 int cx_ll_insert(cx_list *list, size_t index, void *elem) {

   127     cx_linked_list *listdata = (cx_linked_list *) list->listdata;

   128     // TODO: implement using low level API

   129     return 1;

   130 }

   132 void *cx_ll_remove(cx_list *list, size_t index) {

   133     cx_linked_list *listdata = (cx_linked_list *) list->listdata;

   134     // TODO: implement using low level API

   135     return NULL;

   136 }

   138 size_t cx_ll_find(cx_list *list, void *elem) {

   139     cx_linked_list *listdata = (cx_linked_list *) list->listdata;

   140     // TODO: implement using low level API

   141     return 0;

   142 }

   144 void *cx_ll_last(cx_list *list) {

   145     cx_linked_list *listdata = (cx_linked_list *) list->listdata;

   146     struct cx_linked_list_node *last = cx_linked_list_last(

   147             NULL, &listdata->end, offsetof(struct cx_linked_list_node, next));

   148     return &last->payload;

   149 }

   151 cx_list_class cx_linked_list_class = {

   152         cx_ll_add,

   153         cx_ll_insert,

   154         cx_ll_remove,

   155         cx_ll_find,

   156         cx_ll_last

   157 };

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

   160     CxList list = cxMalloc(allocator, sizeof(cx_list_s) + sizeof(cx_linked_list));

   161     if (list == NULL)

   162         return NULL;

   164     list->cl = &cx_linked_list_class;

   165     list->data.allocator = allocator;

   166     list->data.cmpfunc = comparator;

   167     list->data.itemsize = item_size;

   168     list->data.capacity = SIZE_MAX;

   170     cx_linked_list *ll = (cx_linked_list *) list->data.listdata;

   171     ll->begin = NULL;

   172     ll->loc_prev = offsetof(struct cx_linked_list_node, prev);

   173     ll->loc_next = offsetof(struct cx_linked_list_node, next);

   174     cxLinkedListRecalculateSize(list);

   176     return list;

   177 }

   179 void cxLinkedListDestroy(CxList list) {

   180     // TODO: free contents

   181     cxFree(list->data.allocator, list);

   182 }

   184 size_t cxLinkedListRecalculateSize(CxList list) {

   185     cx_linked_list *ll = (cx_linked_list *) list->data.listdata;

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

   188         list->data.size = 0;

   189         ll->end = NULL;

   190         return 0;

   191     } else {

   192         void *cur = ll->begin;

   193         void *last;

   194         size_t size;

   195         do {

   196             last = cur;

   197             size++;

   198         } while ((cur = *CX_LL_PTR(cur, ll->loc_next)) != NULL);

   199         ll->end = last;

   200         list->data.size = size;

   201         return size;

   202     }

   203 }

Mercurial > hg > ucx / file revision