ucx: src/linked_list.c@8d506ed6c1c0

     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 <stddef.h>

    32 /* LOW LEVEL LINKED LIST FUNCTIONS */

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

    36 void *cx_linked_list_last(void **begin, void **end, off_t loc_next) {

    37     if (end != NULL) {

    38         return *end;

    39     } else {

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

    41             return NULL;

    43         void *cur = *begin;

    44         void *last;

    45         do {

    46             last = cur;

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

    49         return last;

    50     }

    51 }

    53 int cx_linked_list_add(void **begin, void **end, off_t loc_next, off_t loc_prev, void *newnode) {

    54     // TODO: how do we report error messages?

    55     if (loc_next < 0 || (begin == NULL && end == NULL)) {

    56         return 1;

    57     }

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

    60     if (last == NULL) {

    61         if (begin == NULL) {

    62             return 1;

    63         } else {

    64             *begin = newnode;

    65             return 0;

    66         }

    67     }

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

    70     *next = newnode;

    71     if (loc_prev >= 0) {

    72         void **prev = CX_LL_PTR(newnode, loc_prev);

    73         *prev = last;

    74     }

    76     return 0;

    77 }

    79 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */

    81 typedef struct cx_list_node_s cx_list_node;

    83 struct cx_list_node_s {

    84     cx_list_node *next;

    85     cx_list_node *prev;

    86     void *data;

    87 };

    89 typedef struct {

    90     cx_list_node *begin;

    91     cx_list_node *end;

    92     size_t size;

    93 } cx_linked_list;

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

    96     cx_linked_list *listdata = list->listdata;

    97     CxAllocator allocator = list->allocator;

    99     struct cx_list_node_s *node = cxMalloc(allocator, sizeof(struct cx_list_node_s));

   100     if (node == NULL)

   101         return 1;

   103     int ret = cx_linked_list_add(

   104             (void **) &listdata->begin,

   105             (void **) &listdata->end,

   106             offsetof(struct cx_list_node_s, next),

   107             offsetof(struct cx_list_node_s, prev),

   108             node

   109     );

   110     if (ret == 0) {

   111         listdata->size++;

   112         return 0;

   113     } else {

   114         return ret;

   115     }

   116 }

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

   119     cx_linked_list *listdata = list->listdata;

   120     // TODO: implement using low level API

   121     return 1;

   122 }

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

   125     cx_linked_list *listdata = list->listdata;

   126     // TODO: implement using low level API

   127     return NULL;

   128 }

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

   131     cx_linked_list *listdata = list->listdata;

   132     // TODO: implement using low level API

   133     return 0;

   134 }

   136 size_t cx_ll_size(cx_list *list) {

   137     cx_linked_list *listdata = list->listdata;

   138     return listdata->size;

   139 }

   141 cx_list_class cx_linked_list_class = {

   142         cx_ll_add,

   143         cx_ll_insert,

   144         cx_ll_remove,

   145         cx_ll_find,

   146         cx_ll_size

   147 };

   149 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator) {

   150     CxList list = cxMalloc(allocator, sizeof(list));

   151     if (list == NULL)

   152         return NULL;

   154     list->cl = &cx_linked_list_class;

   155     list->data.allocator = allocator;

   156     list->data.cmpfunc = comparator;

   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 > hg > ucx / file revision