|
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 */ |
|
28 |
|
29 #include "cx/linked_list.h" |
|
30 #include <stddef.h> |
|
31 |
|
32 /* LOW LEVEL LINKED LIST FUNCTIONS */ |
|
33 |
|
34 #define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off)) |
|
35 |
|
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; |
|
42 |
|
43 void *cur = *begin; |
|
44 void *last; |
|
45 do { |
|
46 last = cur; |
|
47 } while ((cur = *CX_LL_PTR(cur, loc_next)) != NULL); |
|
48 |
|
49 return last; |
|
50 } |
|
51 } |
|
52 |
|
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 } |
|
58 |
|
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 } |
|
68 |
|
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 } |
|
75 |
|
76 return 0; |
|
77 } |
|
78 |
|
79 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */ |
|
80 |
|
81 typedef struct cx_list_node_s cx_list_node; |
|
82 |
|
83 struct cx_list_node_s { |
|
84 cx_list_node *next; |
|
85 cx_list_node *prev; |
|
86 void *data; |
|
87 }; |
|
88 |
|
89 typedef struct { |
|
90 cx_list_node *begin; |
|
91 cx_list_node *end; |
|
92 size_t size; |
|
93 } cx_linked_list; |
|
94 |
|
95 int cx_ll_add(cx_list *list, void *elem) { |
|
96 cx_linked_list *listdata = list->listdata; |
|
97 CxAllocator allocator = list->allocator; |
|
98 |
|
99 struct cx_list_node_s *node = cxMalloc(allocator, sizeof(struct cx_list_node_s)); |
|
100 if (node == NULL) |
|
101 return 1; |
|
102 |
|
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 } |
|
117 |
|
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 } |
|
123 |
|
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 } |
|
129 |
|
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 } |
|
135 |
|
136 size_t cx_ll_size(cx_list *list) { |
|
137 cx_linked_list *listdata = list->listdata; |
|
138 return listdata->size; |
|
139 } |
|
140 |
|
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 }; |
|
148 |
|
149 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator) { |
|
150 CxList list = cxMalloc(allocator, sizeof(list)); |
|
151 if (list == NULL) |
|
152 return NULL; |
|
153 |
|
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 } |