src/linked_list.c

Sun, 07 Feb 2021 21:03:30 +0100

author
Mike Becker <universe@uap-core.de>
date
Sun, 07 Feb 2021 21:03:30 +0100
changeset 402
a34b93911956
parent 401
e6a8f7fb0c45
child 403
8fa43b732980
permissions
-rw-r--r--

use named fields to access node memory

     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 *newnode) {
    55     // TODO: how do we report error messages?
    56     if (loc_next < 0 || (begin == NULL && end == NULL)) {
    57         return 1;
    58     }
    60     void *last = cx_linked_list_last(begin, end, loc_next);
    61     if (last == NULL) {
    62         if (begin == NULL) {
    63             return 1;
    64         } else {
    65             *begin = newnode;
    66             return 0;
    67         }
    68     }
    70     void **next = CX_LL_PTR(last, loc_next);
    71     *next = newnode;
    72     if (loc_prev >= 0) {
    73         void **prev = CX_LL_PTR(newnode, loc_prev);
    74         *prev = last;
    75     }
    77     return 0;
    78 }
    80 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
    82 struct cx_linked_list_node {
    83     void *prev;
    84     void *next;
    85     int payload;
    86 };
    88 typedef struct {
    89     void *begin;
    90     void *end;
    91 } cx_linked_list;
    93 int cx_ll_add(cx_list *list, void *elem) {
    94     cx_linked_list *listdata = list->listdata;
    95     CxAllocator allocator = list->allocator;
    97     struct cx_linked_list_node *node = cxMalloc(allocator,
    98             sizeof(struct cx_linked_list_node) - sizeof(int) + list->itemsize);
    99     if (node == NULL)
   100         return 1;
   102     node->next = NULL;
   103     memcpy(&node->payload, elem, list->itemsize);
   105     int ret = cx_linked_list_add(
   106             &listdata->begin,
   107             &listdata->end,
   108             offsetof(struct cx_linked_list_node, prev),
   109             offsetof(struct cx_linked_list_node, next),
   110             node
   111     );
   112     if (ret == 0) {
   113         list->size++;
   114         return 0;
   115     } else {
   116         return ret;
   117     }
   118 }
   120 int cx_ll_insert(cx_list *list, size_t index, void *elem) {
   121     cx_linked_list *listdata = list->listdata;
   122     // TODO: implement using low level API
   123     return 1;
   124 }
   126 void *cx_ll_remove(cx_list *list, size_t index) {
   127     cx_linked_list *listdata = list->listdata;
   128     // TODO: implement using low level API
   129     return NULL;
   130 }
   132 size_t cx_ll_find(cx_list *list, void *elem) {
   133     cx_linked_list *listdata = list->listdata;
   134     // TODO: implement using low level API
   135     return 0;
   136 }
   139 cx_list_class cx_linked_list_class = {
   140         cx_ll_add,
   141         cx_ll_insert,
   142         cx_ll_remove,
   143         cx_ll_find
   144 };
   146 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t itemsize) {
   147     CxList list = cxMalloc(allocator, sizeof(list));
   148     if (list == NULL)
   149         return NULL;
   151     list->cl = &cx_linked_list_class;
   152     list->data.allocator = allocator;
   153     list->data.cmpfunc = comparator;
   154     list->data.size = 0;
   155     list->data.itemsize = itemsize;
   156     list->data.capacity = SIZE_MAX;
   157     list->data.listdata = cxCalloc(allocator, 1, sizeof(cx_linked_list));
   158     if (list->data.listdata == NULL) {
   159         cxFree(allocator, list);
   160         return NULL;
   161     }
   162 }

mercurial