1 /*
2 * This software is licensed under the terms of the MIT License.
3 * See COPYING for further information.
4 * ---
5 * Copyright (c) 2011-2019, Lukas Weber <laochailan@web.de>.
6 * Copyright (c) 2012-2019, Andrei Alexeyev <akari@taisei-project.org>.
7 */
8
9 #include "taisei.h"
10
11 #include "list.h"
12 #include "global.h"
13
14 #undef list_insert
list_insert(List ** dest,List * elem)15 List* list_insert(List **dest, List *elem) {
16 elem->prev = *dest;
17
18 if(*dest != NULL) {
19 elem->next = (*dest)->next;
20
21 if((*dest)->next) {
22 (*dest)->next->prev = elem;
23 }
24
25 (*dest)->next = elem;
26 } else {
27 elem->next = NULL;
28 *dest = elem;
29 }
30
31 return elem;
32 }
33
34 #undef alist_insert
alist_insert(ListAnchor * list,List * ref,List * elem)35 List* alist_insert(ListAnchor *list, List *ref, List *elem) {
36 elem->prev = ref;
37
38 if(ref != NULL) {
39 elem->next = ref->next;
40
41 if(elem->next != NULL) {
42 elem->next->prev = elem;
43 }
44
45 if(ref == list->last) {
46 list->last = elem;
47 }
48
49 if(list->first == NULL) {
50 // list->first = elem;
51 }
52
53 ref->next = elem;
54 } else {
55 assert(list->first == NULL);
56 assert(list->last == NULL);
57 elem->next = elem->prev = NULL;
58 list->first = list->last = elem;
59 }
60
61 return elem;
62 }
63
64 #undef list_push
list_push(List ** dest,List * elem)65 List* list_push(List **dest, List *elem) {
66 if(*dest) {
67 (*dest)->prev = elem;
68 }
69
70 elem->next = *dest;
71 elem->prev = NULL;
72
73 *dest = elem;
74 return elem;
75 }
76
77 #undef alist_push
alist_push(ListAnchor * list,List * elem)78 List* alist_push(ListAnchor *list, List *elem) {
79 elem->next = list->first;
80 elem->prev = NULL;
81
82 if(list->last == NULL) {
83 assert(list->first == NULL);
84 list->last = elem;
85 } else {
86 assert(list->first != NULL);
87 list->first->prev = elem;
88 }
89
90 list->first = elem;
91 return elem;
92 }
93
94 #undef list_append
list_append(List ** dest,List * elem)95 List* list_append(List **dest, List *elem) {
96 if(*dest == NULL) {
97 return list_insert(dest, elem);
98 }
99
100 List *end = *dest;
101 for(List *e = (*dest)->next; e; e = e->next) {
102 end = e;
103 }
104
105 return list_insert(&end, elem);
106 }
107
108 #undef alist_append
alist_append(ListAnchor * list,List * elem)109 List* alist_append(ListAnchor *list, List *elem) {
110 elem->next = NULL;
111 elem->prev = list->last;
112
113 if(list->last == NULL) {
114 assert(list->first == NULL);
115 list->first = elem;
116 } else {
117 assert(list->first != NULL);
118 list->last->next = elem;
119 }
120
121 list->last = elem;
122 return elem;
123 }
124
125 attr_hot
list_insert_at_priority(List ** list_head,List * elem,int prio,ListPriorityFunc prio_func,bool head)126 static List* list_insert_at_priority(List **list_head, List *elem, int prio, ListPriorityFunc prio_func, bool head) {
127 if(!*list_head) {
128 elem->prev = elem->next = NULL;
129 *list_head = elem;
130 return elem;
131 }
132
133 List *dest = *list_head;
134 int dest_prio = prio_func(dest);
135 int candidate_prio = dest_prio;
136
137 if(head) {
138 for(List *e = dest->next; e && (candidate_prio = prio_func(e)) < prio; e = e->next) {
139 dest = e;
140 dest_prio = candidate_prio;
141 }
142 } else {
143 for(List *e = dest->next; e && (candidate_prio = prio_func(e)) <= prio; e = e->next) {
144 dest = e;
145 dest_prio = candidate_prio;
146 }
147 }
148
149 if(dest == *list_head && dest_prio > prio) {
150 elem->next = dest;
151 elem->prev = dest->prev;
152
153 if(elem->prev) {
154 elem->prev->next = elem;
155 }
156
157 dest->prev = elem;
158 *list_head = elem;
159 } else {
160 elem->prev = dest;
161 elem->next = dest->next;
162
163 if(dest->next) {
164 dest->next->prev = elem;
165 }
166
167 dest->next = elem;
168 }
169
170 return elem;
171 }
172
173 #undef list_insert_at_priority_head
list_insert_at_priority_head(List ** dest,List * elem,int prio,ListPriorityFunc prio_func)174 List* list_insert_at_priority_head(List **dest, List *elem, int prio, ListPriorityFunc prio_func) {
175 return list_insert_at_priority(dest, elem, prio, prio_func, true);
176 }
177
178 #undef alist_insert_at_priority_head
alist_insert_at_priority_head(ListAnchor * list,List * elem,int prio,ListPriorityFunc prio_func)179 List* alist_insert_at_priority_head(ListAnchor *list, List *elem, int prio, ListPriorityFunc prio_func) {
180 if(list->first == NULL) {
181 assert(list->last == NULL);
182 elem->prev = elem->next = NULL;
183 list->first = list->last = elem;
184 return elem;
185 }
186
187 List *dest = list->first;
188 int dest_prio = prio_func(dest);
189 int candidate_prio = dest_prio;
190
191 for(List *e = dest->next; e && (candidate_prio = prio_func(e)) < prio; e = e->next) {
192 dest = e;
193 dest_prio = candidate_prio;
194 }
195
196 if(dest == list->first && dest_prio > prio) {
197 elem->next = dest;
198 elem->prev = dest->prev;
199
200 if(elem->prev) {
201 elem->prev->next = elem;
202 }
203
204 dest->prev = elem;
205 list->first = elem;
206 } else {
207 elem->prev = dest;
208 elem->next = dest->next;
209
210 if(dest->next) {
211 dest->next->prev = elem;
212 } else {
213 assert(dest == list->last);
214 list->last = elem;
215 }
216
217 dest->next = elem;
218 }
219
220 return elem;
221 }
222
223 #undef list_insert_at_priority_tail
list_insert_at_priority_tail(List ** dest,List * elem,int prio,ListPriorityFunc prio_func)224 List* list_insert_at_priority_tail(List **dest, List *elem, int prio, ListPriorityFunc prio_func) {
225 return list_insert_at_priority(dest, elem, prio, prio_func, false);
226 }
227
228 #undef alist_insert_at_priority_tail
alist_insert_at_priority_tail(ListAnchor * list,List * elem,int prio,ListPriorityFunc prio_func)229 List* alist_insert_at_priority_tail(ListAnchor *list, List *elem, int prio, ListPriorityFunc prio_func) {
230 if(list->last == NULL) {
231 assert(list->first == NULL);
232 }
233
234 if(list->first == NULL) {
235 assert(list->last == NULL);
236 elem->prev = elem->next = NULL;
237 list->first = list->last = elem;
238 return elem;
239 }
240
241 List *dest = list->last;
242 int dest_prio = prio_func(dest);
243
244 for(List *e = dest->prev; e && dest_prio > prio; e = e->prev) {
245 dest = e;
246 dest_prio = prio_func(e);
247 }
248
249 if(dest == list->first && dest_prio > prio) {
250 elem->next = dest;
251 elem->prev = dest->prev;
252
253 if(elem->prev) {
254 elem->prev->next = elem;
255 }
256
257 dest->prev = elem;
258 list->first = elem;
259 } else {
260 elem->prev = dest;
261 elem->next = dest->next;
262
263 if(dest->next) {
264 dest->next->prev = elem;
265 } else {
266 assert(dest == list->last);
267 list->last = elem;
268 }
269
270 dest->next = elem;
271 }
272
273 return elem;
274 }
275
276 #undef list_unlink
list_unlink(List ** dest,List * elem)277 List* list_unlink(List **dest, List *elem) {
278 if(elem->prev != NULL) {
279 elem->prev->next = elem->next;
280 }
281
282 if(elem->next != NULL) {
283 elem->next->prev = elem->prev;
284 }
285
286 if(*dest == elem) {
287 *dest = elem->next;
288 }
289
290 return elem;
291 }
292
293 #undef alist_unlink
alist_unlink(ListAnchor * list,List * elem)294 List* alist_unlink(ListAnchor *list, List *elem) {
295 if(list->last == elem) {
296 list->last = list->last->prev;
297 }
298
299 return list_unlink(&list->first, elem);
300 }
301
302 #undef list_pop
list_pop(List ** dest)303 List* list_pop(List **dest) {
304 if(*dest == NULL) {
305 return NULL;
306 }
307
308 return list_unlink(dest, *dest);
309 }
310
311 #undef alist_pop
alist_pop(ListAnchor * list)312 List* alist_pop(ListAnchor *list) {
313 if(list->first == NULL) {
314 return NULL;
315 }
316
317 return alist_unlink(list, list->first);
318 }
319
320 #undef alist_merge_tail
alist_merge_tail(ListAnchor * dest,ListAnchor * src)321 void alist_merge_tail(ListAnchor *dest, ListAnchor *src) {
322 if(src->first) {
323 src->first->prev = dest->last;
324
325 if(dest->last) {
326 assume(dest->first != NULL);
327 dest->last->next = src->first;
328 } else {
329 assume(dest->first == NULL);
330 dest->first = src->first;
331 }
332
333 dest->last = src->last;
334 src->first = NULL;
335 src->last = NULL;
336 }
337 }
338
339 #undef list_foreach
list_foreach(List ** dest,ListForeachCallback callback,void * arg)340 void* list_foreach(List **dest, ListForeachCallback callback, void *arg) {
341 void *ret = NULL;
342
343 for(List *e = *dest, *next; e; e = next) {
344 next = e->next;
345
346 if((ret = callback(dest, e, arg)) != NULL) {
347 return ret;
348 }
349 }
350
351 return ret;
352 }
353
354 #undef alist_foreach
alist_foreach(ListAnchor * list,ListAnchorForeachCallback callback,void * arg)355 void* alist_foreach(ListAnchor *list, ListAnchorForeachCallback callback, void *arg) {
356 void *ret = NULL;
357
358 for(List *e = list->first, *next; e; e = next) {
359 next = e->next;
360
361 if((ret = callback(list, e, arg)) != NULL) {
362 return ret;
363 }
364 }
365
366 return ret;
367 }
368
list_callback_free_element(List ** dest,List * elem,void * arg)369 void* list_callback_free_element(List **dest, List *elem, void *arg) {
370 list_unlink(dest, elem);
371 free(elem);
372 return NULL;
373 }
374
alist_callback_free_element(ListAnchor * list,List * elem,void * arg)375 void* alist_callback_free_element(ListAnchor *list, List *elem, void *arg) {
376 alist_unlink(list, elem);
377 free(elem);
378 return NULL;
379 }
380
381 #undef list_free_all
list_free_all(List ** dest)382 void list_free_all(List **dest) {
383 list_foreach(dest, list_callback_free_element, NULL);
384 }
385
386 #undef alist_free_all
alist_free_all(ListAnchor * list)387 void alist_free_all(ListAnchor *list) {
388 alist_foreach(list, alist_callback_free_element, NULL);
389 }
390
list_wrap_container(void * data)391 ListContainer* list_wrap_container(void *data) {
392 ListContainer *c = calloc(1, sizeof(ListContainer));
393 c->data = data;
394 return c;
395 }
396