1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/linked_list.c Sun Feb 07 19:42:12 2021 +0100
1.3 @@ -0,0 +1,162 @@
1.4 +/*
1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 + *
1.7 + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
1.8 + *
1.9 + * Redistribution and use in source and binary forms, with or without
1.10 + * modification, are permitted provided that the following conditions are met:
1.11 + *
1.12 + * 1. Redistributions of source code must retain the above copyright
1.13 + * notice, this list of conditions and the following disclaimer.
1.14 + *
1.15 + * 2. Redistributions in binary form must reproduce the above copyright
1.16 + * notice, this list of conditions and the following disclaimer in the
1.17 + * documentation and/or other materials provided with the distribution.
1.18 + *
1.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
1.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
1.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
1.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
1.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
1.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
1.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
1.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
1.29 + * POSSIBILITY OF SUCH DAMAGE.
1.30 + */
1.31 +
1.32 +#include "cx/linked_list.h"
1.33 +#include <stddef.h>
1.34 +
1.35 +/* LOW LEVEL LINKED LIST FUNCTIONS */
1.36 +
1.37 +#define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off))
1.38 +
1.39 +void *cx_linked_list_last(void **begin, void **end, off_t loc_next) {
1.40 + if (end != NULL) {
1.41 + return *end;
1.42 + } else {
1.43 + if (begin == NULL || *begin == NULL)
1.44 + return NULL;
1.45 +
1.46 + void *cur = *begin;
1.47 + void *last;
1.48 + do {
1.49 + last = cur;
1.50 + } while ((cur = *CX_LL_PTR(cur, loc_next)) != NULL);
1.51 +
1.52 + return last;
1.53 + }
1.54 +}
1.55 +
1.56 +int cx_linked_list_add(void **begin, void **end, off_t loc_next, off_t loc_prev, void *newnode) {
1.57 + // TODO: how do we report error messages?
1.58 + if (loc_next < 0 || (begin == NULL && end == NULL)) {
1.59 + return 1;
1.60 + }
1.61 +
1.62 + void *last = cx_linked_list_last(begin, end, loc_next);
1.63 + if (last == NULL) {
1.64 + if (begin == NULL) {
1.65 + return 1;
1.66 + } else {
1.67 + *begin = newnode;
1.68 + return 0;
1.69 + }
1.70 + }
1.71 +
1.72 + void **next = CX_LL_PTR(last, loc_next);
1.73 + *next = newnode;
1.74 + if (loc_prev >= 0) {
1.75 + void **prev = CX_LL_PTR(newnode, loc_prev);
1.76 + *prev = last;
1.77 + }
1.78 +
1.79 + return 0;
1.80 +}
1.81 +
1.82 +/* HIGH LEVEL LINKED LIST IMPLEMENTATION */
1.83 +
1.84 +typedef struct cx_list_node_s cx_list_node;
1.85 +
1.86 +struct cx_list_node_s {
1.87 + cx_list_node *next;
1.88 + cx_list_node *prev;
1.89 + void *data;
1.90 +};
1.91 +
1.92 +typedef struct {
1.93 + cx_list_node *begin;
1.94 + cx_list_node *end;
1.95 + size_t size;
1.96 +} cx_linked_list;
1.97 +
1.98 +int cx_ll_add(cx_list *list, void *elem) {
1.99 + cx_linked_list *listdata = list->listdata;
1.100 + CxAllocator allocator = list->allocator;
1.101 +
1.102 + struct cx_list_node_s *node = cxMalloc(allocator, sizeof(struct cx_list_node_s));
1.103 + if (node == NULL)
1.104 + return 1;
1.105 +
1.106 + int ret = cx_linked_list_add(
1.107 + (void **) &listdata->begin,
1.108 + (void **) &listdata->end,
1.109 + offsetof(struct cx_list_node_s, next),
1.110 + offsetof(struct cx_list_node_s, prev),
1.111 + node
1.112 + );
1.113 + if (ret == 0) {
1.114 + listdata->size++;
1.115 + return 0;
1.116 + } else {
1.117 + return ret;
1.118 + }
1.119 +}
1.120 +
1.121 +int cx_ll_insert(cx_list *list, size_t index, void *elem) {
1.122 + cx_linked_list *listdata = list->listdata;
1.123 + // TODO: implement using low level API
1.124 + return 1;
1.125 +}
1.126 +
1.127 +void *cx_ll_remove(cx_list *list, size_t index) {
1.128 + cx_linked_list *listdata = list->listdata;
1.129 + // TODO: implement using low level API
1.130 + return NULL;
1.131 +}
1.132 +
1.133 +size_t cx_ll_find(cx_list *list, void *elem) {
1.134 + cx_linked_list *listdata = list->listdata;
1.135 + // TODO: implement using low level API
1.136 + return 0;
1.137 +}
1.138 +
1.139 +size_t cx_ll_size(cx_list *list) {
1.140 + cx_linked_list *listdata = list->listdata;
1.141 + return listdata->size;
1.142 +}
1.143 +
1.144 +cx_list_class cx_linked_list_class = {
1.145 + cx_ll_add,
1.146 + cx_ll_insert,
1.147 + cx_ll_remove,
1.148 + cx_ll_find,
1.149 + cx_ll_size
1.150 +};
1.151 +
1.152 +CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator) {
1.153 + CxList list = cxMalloc(allocator, sizeof(list));
1.154 + if (list == NULL)
1.155 + return NULL;
1.156 +
1.157 + list->cl = &cx_linked_list_class;
1.158 + list->data.allocator = allocator;
1.159 + list->data.cmpfunc = comparator;
1.160 + list->data.listdata = cxCalloc(allocator, 1, sizeof(cx_linked_list));
1.161 + if (list->data.listdata == NULL) {
1.162 + cxFree(allocator, list);
1.163 + return NULL;
1.164 + }
1.165 +}
1.166 \ No newline at end of file
