1 /* MIT License
2 *
3 * Copyright (c) 2023 Brad House
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a copy
6 * of this software and associated documentation files (the "Software"), to deal
7 * in the Software without restriction, including without limitation the rights
8 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 * copies of the Software, and to permit persons to whom the Software is
10 * furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice (including the next
13 * paragraph) shall be included in all copies or substantial portions of the
14 * Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 * SOFTWARE.
23 *
24 * SPDX-License-Identifier: MIT
25 */
26 #include "ares_setup.h"
27 #include "ares.h"
28 #include "ares_private.h"
29 #include "ares__llist.h"
30
31 struct ares__llist {
32 ares__llist_node_t *head;
33 ares__llist_node_t *tail;
34 ares__llist_destructor_t destruct;
35 size_t cnt;
36 };
37
38 struct ares__llist_node {
39 void *data;
40 ares__llist_node_t *prev;
41 ares__llist_node_t *next;
42 ares__llist_t *parent;
43 };
44
ares__llist_create(ares__llist_destructor_t destruct)45 ares__llist_t *ares__llist_create(ares__llist_destructor_t destruct)
46 {
47 ares__llist_t *list = ares_malloc_zero(sizeof(*list));
48
49 if (list == NULL) {
50 return NULL;
51 }
52
53 list->destruct = destruct;
54
55 return list;
56 }
57
ares__llist_replace_destructor(ares__llist_t * list,ares__llist_destructor_t destruct)58 void ares__llist_replace_destructor(ares__llist_t *list,
59 ares__llist_destructor_t destruct)
60 {
61 if (list == NULL) {
62 return;
63 }
64
65 list->destruct = destruct;
66 }
67
68 typedef enum {
69 ARES__LLIST_INSERT_HEAD,
70 ARES__LLIST_INSERT_TAIL,
71 ARES__LLIST_INSERT_BEFORE
72 } ares__llist_insert_type_t;
73
ares__llist_attach_at(ares__llist_t * list,ares__llist_insert_type_t type,ares__llist_node_t * at,ares__llist_node_t * node)74 static void ares__llist_attach_at(ares__llist_t *list,
75 ares__llist_insert_type_t type,
76 ares__llist_node_t *at,
77 ares__llist_node_t *node)
78 {
79 if (list == NULL || node == NULL) {
80 return;
81 }
82
83 node->parent = list;
84
85 if (type == ARES__LLIST_INSERT_BEFORE && (at == list->head || at == NULL)) {
86 type = ARES__LLIST_INSERT_HEAD;
87 }
88
89 switch (type) {
90 case ARES__LLIST_INSERT_HEAD:
91 node->next = list->head;
92 node->prev = NULL;
93 if (list->head) {
94 list->head->prev = node;
95 }
96 list->head = node;
97 break;
98 case ARES__LLIST_INSERT_TAIL:
99 node->next = NULL;
100 node->prev = list->tail;
101 if (list->tail) {
102 list->tail->next = node;
103 }
104 list->tail = node;
105 break;
106 case ARES__LLIST_INSERT_BEFORE:
107 node->next = at;
108 node->prev = at->prev;
109 at->prev = node;
110 break;
111 }
112 if (list->tail == NULL) {
113 list->tail = node;
114 }
115 if (list->head == NULL) {
116 list->head = node;
117 }
118
119 list->cnt++;
120 }
121
ares__llist_insert_at(ares__llist_t * list,ares__llist_insert_type_t type,ares__llist_node_t * at,void * val)122 static ares__llist_node_t *ares__llist_insert_at(ares__llist_t *list,
123 ares__llist_insert_type_t type,
124 ares__llist_node_t *at,
125 void *val)
126 {
127 ares__llist_node_t *node = NULL;
128
129 if (list == NULL || val == NULL) {
130 return NULL;
131 }
132
133 node = ares_malloc_zero(sizeof(*node));
134
135 if (node == NULL) {
136 return NULL;
137 }
138
139 node->data = val;
140 ares__llist_attach_at(list, type, at, node);
141
142 return node;
143 }
144
ares__llist_insert_first(ares__llist_t * list,void * val)145 ares__llist_node_t *ares__llist_insert_first(ares__llist_t *list, void *val)
146 {
147 return ares__llist_insert_at(list, ARES__LLIST_INSERT_HEAD, NULL, val);
148 }
149
ares__llist_insert_last(ares__llist_t * list,void * val)150 ares__llist_node_t *ares__llist_insert_last(ares__llist_t *list, void *val)
151 {
152 return ares__llist_insert_at(list, ARES__LLIST_INSERT_TAIL, NULL, val);
153 }
154
ares__llist_insert_before(ares__llist_node_t * node,void * val)155 ares__llist_node_t *ares__llist_insert_before(ares__llist_node_t *node,
156 void *val)
157 {
158 if (node == NULL) {
159 return NULL;
160 }
161
162 return ares__llist_insert_at(node->parent, ARES__LLIST_INSERT_BEFORE, node,
163 val);
164 }
165
ares__llist_insert_after(ares__llist_node_t * node,void * val)166 ares__llist_node_t *ares__llist_insert_after(ares__llist_node_t *node,
167 void *val)
168 {
169 if (node == NULL) {
170 return NULL;
171 }
172
173 if (node->next == NULL) {
174 return ares__llist_insert_last(node->parent, val);
175 }
176
177 return ares__llist_insert_at(node->parent, ARES__LLIST_INSERT_BEFORE,
178 node->next, val);
179 }
180
ares__llist_node_first(ares__llist_t * list)181 ares__llist_node_t *ares__llist_node_first(ares__llist_t *list)
182 {
183 if (list == NULL) {
184 return NULL;
185 }
186 return list->head;
187 }
188
ares__llist_node_last(ares__llist_t * list)189 ares__llist_node_t *ares__llist_node_last(ares__llist_t *list)
190 {
191 if (list == NULL) {
192 return NULL;
193 }
194 return list->tail;
195 }
196
ares__llist_node_next(ares__llist_node_t * node)197 ares__llist_node_t *ares__llist_node_next(ares__llist_node_t *node)
198 {
199 if (node == NULL) {
200 return NULL;
201 }
202 return node->next;
203 }
204
ares__llist_node_prev(ares__llist_node_t * node)205 ares__llist_node_t *ares__llist_node_prev(ares__llist_node_t *node)
206 {
207 if (node == NULL) {
208 return NULL;
209 }
210 return node->prev;
211 }
212
ares__llist_node_val(ares__llist_node_t * node)213 void *ares__llist_node_val(ares__llist_node_t *node)
214 {
215 if (node == NULL) {
216 return NULL;
217 }
218
219 return node->data;
220 }
221
ares__llist_len(const ares__llist_t * list)222 size_t ares__llist_len(const ares__llist_t *list)
223 {
224 if (list == NULL) {
225 return 0;
226 }
227 return list->cnt;
228 }
229
ares__llist_node_parent(ares__llist_node_t * node)230 ares__llist_t *ares__llist_node_parent(ares__llist_node_t *node)
231 {
232 if (node == NULL) {
233 return NULL;
234 }
235 return node->parent;
236 }
237
ares__llist_first_val(ares__llist_t * list)238 void *ares__llist_first_val(ares__llist_t *list)
239 {
240 return ares__llist_node_val(ares__llist_node_first(list));
241 }
242
ares__llist_last_val(ares__llist_t * list)243 void *ares__llist_last_val(ares__llist_t *list)
244 {
245 return ares__llist_node_val(ares__llist_node_last(list));
246 }
247
ares__llist_node_detach(ares__llist_node_t * node)248 static void ares__llist_node_detach(ares__llist_node_t *node)
249 {
250 ares__llist_t *list;
251
252 if (node == NULL) {
253 return;
254 }
255
256 list = node->parent;
257
258 if (node->prev) {
259 node->prev->next = node->next;
260 }
261
262 if (node->next) {
263 node->next->prev = node->prev;
264 }
265
266 if (node == list->head) {
267 list->head = node->next;
268 }
269
270 if (node == list->tail) {
271 list->tail = node->prev;
272 }
273
274 node->parent = NULL;
275 list->cnt--;
276 }
277
ares__llist_node_claim(ares__llist_node_t * node)278 void *ares__llist_node_claim(ares__llist_node_t *node)
279 {
280 void *val;
281
282 if (node == NULL) {
283 return NULL;
284 }
285
286 val = node->data;
287 ares__llist_node_detach(node);
288 ares_free(node);
289
290 return val;
291 }
292
ares__llist_node_destroy(ares__llist_node_t * node)293 void ares__llist_node_destroy(ares__llist_node_t *node)
294 {
295 ares__llist_destructor_t destruct;
296 void *val;
297
298 if (node == NULL) {
299 return;
300 }
301
302 destruct = node->parent->destruct;
303
304 val = ares__llist_node_claim(node);
305 if (val != NULL && destruct != NULL) {
306 destruct(val);
307 }
308 }
309
ares__llist_node_replace(ares__llist_node_t * node,void * val)310 void ares__llist_node_replace(ares__llist_node_t *node, void *val)
311 {
312 ares__llist_destructor_t destruct;
313
314 if (node == NULL) {
315 return;
316 }
317
318 destruct = node->parent->destruct;
319 if (destruct != NULL) {
320 destruct(node->data);
321 }
322
323 node->data = val;
324 }
325
ares__llist_destroy(ares__llist_t * list)326 void ares__llist_destroy(ares__llist_t *list)
327 {
328 ares__llist_node_t *node;
329
330 if (list == NULL) {
331 return;
332 }
333
334 while ((node = ares__llist_node_first(list)) != NULL) {
335 ares__llist_node_destroy(node);
336 }
337 ares_free(list);
338 }
339
ares__llist_node_move_parent_last(ares__llist_node_t * node,ares__llist_t * new_parent)340 void ares__llist_node_move_parent_last(ares__llist_node_t *node,
341 ares__llist_t *new_parent)
342 {
343 if (node == NULL || new_parent == NULL) {
344 return;
345 }
346
347 ares__llist_node_detach(node);
348 ares__llist_attach_at(new_parent, ARES__LLIST_INSERT_TAIL, NULL, node);
349 }
350
ares__llist_node_move_parent_first(ares__llist_node_t * node,ares__llist_t * new_parent)351 void ares__llist_node_move_parent_first(ares__llist_node_t *node,
352 ares__llist_t *new_parent)
353 {
354 if (node == NULL || new_parent == NULL) {
355 return;
356 }
357
358 ares__llist_node_detach(node);
359 ares__llist_attach_at(new_parent, ARES__LLIST_INSERT_HEAD, NULL, node);
360 }
361