![[bottom]](../icons/bottom.png){kind=icon}
![[previous]](../icons/n_left.png){kind=icon}
![[next]](../icons/n_right.png){kind=icon}
![[first]](../icons/n_first.png){kind=icon}
![[last]](../icons/n_last.png){kind=icon}
![[top]](../icons/n_top.png){kind=icon}
![[index]](../icons/index.png){kind=icon}
![[help]](../icons/help.png){kind=icon}
*/
1 /*
2 * vim: filetype=c:tabstop=4:ai:expandtab
3 * SPDX-License-Identifier: BSD-1-Clause
4 * scspell-id: 5c109fb8-f630-11ec-b1f7-80ee73e9b8e7
5 *
6 * ---------------------------------------------------------------------------
7 *
8 * Copyright (c) 2007-2021 Troy D. Hanson
9 * https://troydhanson.github.io/uthash/
10 * Copyright (c) 2021-2022 The DPS8M Development Team
11 *
12 * All rights reserved.
13 *
14 * Redistribution and use in source and binary forms, with or without
15 * modification, are permitted provided that the following conditions are met:
16 *
17 * * Redistributions of source code must retain the above copyright
18 * notice, this list of conditions and the following disclaimer.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
21 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
22 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
23 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
24 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
25 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
26 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
27 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
28 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
29 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
30 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 *
32 * ---------------------------------------------------------------------------
33 */
34
35 #ifndef UTLIST_H
36 # define UTLIST_H
37
38 # define UTLIST_VERSION 21.9.8
39
40 # include <assert.h>
41
42 /*
43 * This file contains macros to manipulate singly and doubly-linked lists.
44 *
45 * 1. LL_ macros: singly-linked lists.
46 * 2. DL_ macros: doubly-linked lists.
47 * 3. CDL_ macros: circular doubly-linked lists.
48 *
49 * To use singly-linked lists, your structure must have a "next" pointer.
50 * To use doubly-linked lists, your structure must "prev" and "next" pointers.
51 * Either way, the pointer to the head of the list must be initialized to NULL.
52 *
53 * ----------------.EXAMPLE -------------------------
54 * struct item {
55 * int id;
56 * struct item *prev, *next;
57 * }
58 *
59 * struct item *list = NULL:
60 *
61 * int main() {
62 * struct item *item;
63 * ... allocate and populate item ...
64 * DL_APPEND(list, item);
65 * }
66 * --------------------------------------------------
67 *
68 * For doubly-linked lists, the append and delete macros are O(1)
69 * For singly-linked lists, append and delete are O(n) but prepend is O(1)
70 * The sort macro is O(n log(n)) for all types of single/double/circular lists.
71 */
72
73 /*
74 * These macros use decltype or the earlier __typeof GNU extension.
75 * As decltype is only available in newer compilers (VS2010 or gcc 4.3+
76 * when compiling c++ code), this code uses whatever method is needed
77 * or, for VS2008 where neither is available, uses casting workarounds.
78 */
79
80 # ifdef _MSC_VER /* MS compiler */
81 # if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */
82 # define LDECLTYPE(x) decltype(x)
83 # else /* VS2008 or older (or VS2010 in C mode) */
84 # define NO_DECLTYPE
85 # define LDECLTYPE(x) char*
86 # endif
87 # else /* GNU, Sun and other compilers */
88 # define LDECLTYPE(x) __typeof(x)
89 # endif
90
91 /*
92 * For VS2008 we use some workarounds to get around the lack of decltype,
93 * namely, we always reassign our tmp variable to the list head if we need
94 * to dereference its prev/next pointers, and save/restore the real head.
95 */
96
97 # ifdef NO_DECLTYPE
98 # define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
99 # define _NEXT(elt,list,next) ((char*)((list)->next))
100 # define _NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }
101 /* #define _PREV(elt,list,prev) ((char*)((list)->prev)) */
102 # define _PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }
103 # define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
104 # define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
105 # else
106 # define _SV(elt,list)
107 # define _NEXT(elt,list,next) ((elt)->next)
108 # define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to)
109 /* #define _PREV(elt,list,prev) ((elt)->prev) */
110 # define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to)
111 # define _RS(list)
112 # define _CASTASGN(a,b) (a)=(b)
113 # endif
114
115 /*
116 *****************************************************************************
117 * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort *
118 * Unwieldy variable names used here to avoid shadowing passed-in variables. *
119 *****************************************************************************
120 */
121
122 # define LL_SORT(list, cmp) \
123 LL_SORT2(list, cmp, next)
124
125 # define LL_SORT2(list, cmp, next) \
126 do { \
127 LDECLTYPE(list) _ls_p; \
128 LDECLTYPE(list) _ls_q; \
129 LDECLTYPE(list) _ls_e; \
130 LDECLTYPE(list) _ls_tail; \
131 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
132 if (list) { \
133 _ls_insize = 1; \
134 _ls_looping = 1; \
135 while (_ls_looping) { \
136 _CASTASGN(_ls_p,list); \
137 list = NULL; \
138 _ls_tail = NULL; \
139 _ls_nmerges = 0; \
140 while (_ls_p) { \
141 _ls_nmerges++; \
142 _ls_q = _ls_p; \
143 _ls_psize = 0; \
144 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
145 _ls_psize++; \
146 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
147 if (!_ls_q) break; \
148 } \
149 _ls_qsize = _ls_insize; \
150 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
151 if (_ls_psize == 0) { \
152 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
153 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
154 } else if (_ls_qsize == 0 || !_ls_q) { \
155 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
156 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
157 } else if (cmp(_ls_p,_ls_q) <= 0) { \
158 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
159 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
160 } else { \
161 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
162 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
163 } \
164 if (_ls_tail) { \
165 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
166 } else { \
167 _CASTASGN(list,_ls_e); \
168 } \
169 _ls_tail = _ls_e; \
170 } \
171 _ls_p = _ls_q; \
172 } \
173 if (_ls_tail) { \
174 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
175 } \
176 if (_ls_nmerges <= 1) { \
177 _ls_looping=0; \
178 } \
179 _ls_insize *= 2; \
180 } \
181 } \
182 } while (0)
183
184 # define DL_SORT(list, cmp) \
185 DL_SORT2(list, cmp, prev, next)
186
187 # define DL_SORT2(list, cmp, prev, next) \
188 do { \
189 LDECLTYPE(list) _ls_p; \
190 LDECLTYPE(list) _ls_q; \
191 LDECLTYPE(list) _ls_e; \
192 LDECLTYPE(list) _ls_tail; \
193 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
194 if (list) { \
195 _ls_insize = 1; \
196 _ls_looping = 1; \
197 while (_ls_looping) { \
198 _CASTASGN(_ls_p,list); \
199 list = NULL; \
200 _ls_tail = NULL; \
201 _ls_nmerges = 0; \
202 while (_ls_p) { \
203 _ls_nmerges++; \
204 _ls_q = _ls_p; \
205 _ls_psize = 0; \
206 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
207 _ls_psize++; \
208 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
209 if (!_ls_q) break; \
210 } \
211 _ls_qsize = _ls_insize; \
212 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
213 if (_ls_psize == 0) { \
214 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
215 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
216 } else if (_ls_qsize == 0 || !_ls_q) { \
217 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
218 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
219 } else if (cmp(_ls_p,_ls_q) <= 0) { \
220 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
221 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
222 } else { \
223 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
224 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
225 } \
226 if (_ls_tail) { \
227 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
228 } else { \
229 _CASTASGN(list,_ls_e); \
230 } \
231 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
232 _ls_tail = _ls_e; \
233 } \
234 _ls_p = _ls_q; \
235 } \
236 _CASTASGN(list->prev, _ls_tail); \
237 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
238 if (_ls_nmerges <= 1) { \
239 _ls_looping=0; \
240 } \
241 _ls_insize *= 2; \
242 } \
243 } \
244 } while (0)
245
246 # define CDL_SORT(list, cmp) \
247 CDL_SORT2(list, cmp, prev, next)
248
249 # define CDL_SORT2(list, cmp, prev, next) \
250 do { \
251 LDECLTYPE(list) _ls_p; \
252 LDECLTYPE(list) _ls_q; \
253 LDECLTYPE(list) _ls_e; \
254 LDECLTYPE(list) _ls_tail; \
255 LDECLTYPE(list) _ls_oldhead; \
256 LDECLTYPE(list) _tmp; \
257 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
258 if (list) { \
259 _ls_insize = 1; \
260 _ls_looping = 1; \
261 while (_ls_looping) { \
262 _CASTASGN(_ls_p,list); \
263 _CASTASGN(_ls_oldhead,list); \
264 list = NULL; \
265 _ls_tail = NULL; \
266 _ls_nmerges = 0; \
267 while (_ls_p) { \
268 _ls_nmerges++; \
269 _ls_q = _ls_p; \
270 _ls_psize = 0; \
271 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
272 _ls_psize++; \
273 _SV(_ls_q,list); \
274 if (_NEXT(_ls_q,list,next) == _ls_oldhead) { \
275 _ls_q = NULL; \
276 } else { \
277 _ls_q = _NEXT(_ls_q,list,next); \
278 } \
279 _RS(list); \
280 if (!_ls_q) break; \
281 } \
282 _ls_qsize = _ls_insize; \
283 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
284 if (_ls_psize == 0) { \
285 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
286 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
287 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
288 } else if (_ls_qsize == 0 || !_ls_q) { \
289 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
290 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
291 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
292 } else if (cmp(_ls_p,_ls_q) <= 0) { \
293 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
294 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
295 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
296 } else { \
297 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
298 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
299 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
300 } \
301 if (_ls_tail) { \
302 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
303 } else { \
304 _CASTASGN(list,_ls_e); \
305 } \
306 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
307 _ls_tail = _ls_e; \
308 } \
309 _ls_p = _ls_q; \
310 } \
311 _CASTASGN(list->prev,_ls_tail); \
312 _CASTASGN(_tmp,list); \
313 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp,next); _RS(list); \
314 if (_ls_nmerges <= 1) { \
315 _ls_looping=0; \
316 } \
317 _ls_insize *= 2; \
318 } \
319 } \
320 } while (0)
321
322 /*
323 ******************************************************************************
324 * singly linked list macros (non-circular) *
325 ******************************************************************************
326 */
327
328 # define LL_PREPEND(head,add) \
329 LL_PREPEND2(head,add,next)
330
331 # define LL_PREPEND2(head,add,next) \
332 do { \
333 (add)->next = head; \
334 head = add; \
335 } while (0)
336
337 # define LL_CONCAT(head1,head2) \
338 LL_CONCAT2(head1,head2,next)
339
340 # define LL_CONCAT2(head1,head2,next) \
341 do { \
342 LDECLTYPE(head1) _tmp; \
343 if (head1) { \
344 _tmp = head1; \
345 while (_tmp->next) { _tmp = _tmp->next; } \
346 _tmp->next=(head2); \
347 } else { \
348 (head1)=(head2); \
349 } \
350 } while (0)
351
352 # define LL_APPEND(head,add) \
353 LL_APPEND2(head,add,next)
354
355 # define LL_APPEND2(head,add,next) \
356 do { \
357 LDECLTYPE(head) _tmp; \
358 (add)->next=NULL; \
359 if (head) { \
360 _tmp = head; \
361 while (_tmp->next) { _tmp = _tmp->next; } \
362 _tmp->next=(add); \
363 } else { \
364 (head)=(add); \
365 } \
366 } while (0)
367
368 # define LL_DELETE(head,del) \
369 LL_DELETE2(head,del,next)
370
371 # define LL_DELETE2(head,del,next) \
372 do { \
373 LDECLTYPE(head) _tmp; \
374 if ((head) == (del)) { \
375 (head)=(head)->next; \
376 } else { \
377 _tmp = head; \
378 while (_tmp->next && (_tmp->next != (del))) { \
379 _tmp = _tmp->next; \
380 } \
381 if (_tmp->next) { \
382 _tmp->next = ((del)->next); \
383 } \
384 } \
385 } while (0)
386
387 /*
388 * Here are VS2008 replacements
389 * for LL_APPEND and LL_DELETE
390 */
391
392 # define LL_APPEND_VS2008(head,add) \
393 LL_APPEND2_VS2008(head,add,next)
394
395 # define LL_APPEND2_VS2008(head,add,next) \
396 do { \
397 if (head) { \
398 (add)->next = head; /* use add->next as a temp variable */ \
399 while ((add)->next->next) { (add)->next = (add)->next->next; } \
400 (add)->next->next=(add); \
401 } else { \
402 (head)=(add); \
403 } \
404 (add)->next=NULL; \
405 } while (0)
406
407 # define LL_DELETE_VS2008(head,del) \
408 LL_DELETE2_VS2008(head,del,next)
409
410 # define LL_DELETE2_VS2008(head,del,next) \
411 do { \
412 if ((head) == (del)) { \
413 (head)=(head)->next; \
414 } else { \
415 char *_tmp = (char*)(head); \
416 while ((head)->next && ((head)->next != (del))) { \
417 head = (head)->next; \
418 } \
419 if ((head)->next) { \
420 (head)->next = ((del)->next); \
421 } \
422 { \
423 char **_head_alias = (char**)&(head); \
424 *_head_alias = _tmp; \
425 } \
426 } \
427 } while (0)
428 # ifdef NO_DECLTYPE
429 # undef LL_APPEND
430 # define LL_APPEND LL_APPEND_VS2008
431 # undef LL_DELETE
432 # define LL_DELETE LL_DELETE_VS2008
433 # undef LL_DELETE2
434 # define LL_DELETE2_VS2008
435 # undef LL_APPEND2
436 # define LL_APPEND2 LL_APPEND2_VS2008
437 # undef LL_CONCAT /* no LL_CONCAT_VS2008 */
438 # undef DL_CONCAT /* no DL_CONCAT_VS2008 */
439 # endif
440
441 /*
442 * End VS2008
443 * replacements
444 */
445
446 # define LL_FOREACH(head,el) \
447 LL_FOREACH2(head,el,next)
448
449 # define LL_FOREACH2(head,el,next) \
450 for(el=head;el;el=(el)->next)
451
452 # define LL_FOREACH_SAFE(head,el,tmp) \
453 LL_FOREACH_SAFE2(head,el,tmp,next)
454
455 # define LL_FOREACH_SAFE2(head,el,tmp,next) \
456 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
457
458 # define LL_SEARCH_SCALAR(head,out,field,val) \
459 LL_SEARCH_SCALAR2(head,out,field,val,next)
460
461 # define LL_SEARCH_SCALAR2(head,out,field,val,next) \
462 do { \
463 LL_FOREACH2(head,out,next) { \
464 if ((out)->field == (val)) break; \
465 } \
466 } while(0)
467
468 # define LL_SEARCH(head,out,elt,cmp) \
469 LL_SEARCH2(head,out,elt,cmp,next)
470
471 # define LL_SEARCH2(head,out,elt,cmp,next) \
472 do { \
473 LL_FOREACH2(head,out,next) { \
474 if ((cmp(out,elt))==0) break; \
475 } \
476 } while(0)
477
478 # define LL_REPLACE_ELEM(head, el, add) \
479 do { \
480 LDECLTYPE(head) _tmp; \
481 assert(head != NULL); \
482 assert(el != NULL); \
483 assert(add != NULL); \
484 (add)->next = (el)->next; \
485 if ((head) == (el)) { \
486 (head) = (add); \
487 } else { \
488 _tmp = head; \
489 while (_tmp->next && (_tmp->next != (el))) { \
490 _tmp = _tmp->next; \
491 } \
492 if (_tmp->next) { \
493 _tmp->next = (add); \
494 } \
495 } \
496 } while (0)
497
498 # define LL_PREPEND_ELEM(head, el, add) \
499 do { \
500 LDECLTYPE(head) _tmp; \
501 assert(head != NULL); \
502 assert(el != NULL); \
503 assert(add != NULL); \
504 (add)->next = (el); \
505 if ((head) == (el)) { \
506 (head) = (add); \
507 } else { \
508 _tmp = head; \
509 while (_tmp->next && (_tmp->next != (el))) { \
510 _tmp = _tmp->next; \
511 } \
512 if (_tmp->next) { \
513 _tmp->next = (add); \
514 } \
515 } \
516 } while (0) \
517
518 /*
519 ******************************************************************************
520 * doubly linked list macros (non-circular) *
521 ******************************************************************************
522 */
523
524 # define DL_PREPEND(head,add) \
525 DL_PREPEND2(head,add,prev,next)
526
527 # define DL_PREPEND2(head,add,prev,next) \
528 do { \
529 (add)->next = head; \
530 if (head) { \
531 (add)->prev = (head)->prev; \
532 (head)->prev = (add); \
533 } else { \
534 (add)->prev = (add); \
535 } \
536 (head) = (add); \
537 } while (0)
538
539 # define DL_APPEND(head,add) \
540 DL_APPEND2(head,add,prev,next)
541
542 # define DL_APPEND2(head,add,prev,next) \
543 do { \
544 if (head) { \
545 (add)->prev = (head)->prev; \
546 (head)->prev->next = (add); \
547 (head)->prev = (add); \
548 (add)->next = NULL; \
549 } else { \
550 (head)=(add); \
551 (head)->prev = (head); \
552 (head)->next = NULL; \
553 } \
554 } while (0)
555
556 # define DL_CONCAT(head1,head2) \
557 DL_CONCAT2(head1,head2,prev,next)
558
559 # define DL_CONCAT2(head1,head2,prev,next) \
560 do { \
561 LDECLTYPE(head1) _tmp; \
562 if (head2) { \
563 if (head1) { \
564 _tmp = (head2)->prev; \
565 (head2)->prev = (head1)->prev; \
566 (head1)->prev->next = (head2); \
567 (head1)->prev = _tmp; \
568 } else { \
569 (head1)=(head2); \
570 } \
571 } \
572 } while (0)
573
574 # define DL_DELETE(head,del) \
575 DL_DELETE2(head,del,prev,next)
576
577 # define DL_DELETE2(head,del,prev,next) \
578 do { \
579 assert((del)->prev != NULL); \
580 if ((del)->prev == (del)) { \
581 (head)=NULL; \
582 } else if ((del)==(head)) { \
583 (del)->next->prev = (del)->prev; \
584 (head) = (del)->next; \
585 } else { \
586 (del)->prev->next = (del)->next; \
587 if ((del)->next) { \
588 (del)->next->prev = (del)->prev; \
589 } else { \
590 (head)->prev = (del)->prev; \
591 } \
592 } \
593 } while (0)
594
595 # define DL_FOREACH(head,el) \
596 DL_FOREACH2(head,el,next)
597
598 # define DL_FOREACH2(head,el,next) \
599 for(el=head;el;el=(el)->next)
600
601 /*
602 * this version is safe for deleting
603 * the elements during iteration
604 */
605
606 # define DL_FOREACH_SAFE(head,el,tmp) \
607 DL_FOREACH_SAFE2(head,el,tmp,next)
608
609 # define DL_FOREACH_SAFE2(head,el,tmp,next) \
610 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
611
612 /*
613 * these are identical to their
614 * singly-linked list counterparts
615 */
616
617 # define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
618 # define DL_SEARCH LL_SEARCH
619 # define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2
620 # define DL_SEARCH2 LL_SEARCH2
621
622 # define DL_REPLACE_ELEM(head, el, add) \
623 do { \
624 assert(head != NULL); \
625 assert(el != NULL); \
626 assert(add != NULL); \
627 if ((head) == (el)) { \
628 (head) = (add); \
629 (add)->next = (el)->next; \
630 if ((el)->next == NULL) { \
631 (add)->prev = (add); \
632 } else { \
633 (add)->prev = (el)->prev; \
634 (add)->next->prev = (add); \
635 } \
636 } else { \
637 (add)->next = (el)->next; \
638 (add)->prev = (el)->prev; \
639 (add)->prev->next = (add); \
640 if ((el)->next == NULL) { \
641 (head)->prev = (add); \
642 } else { \
643 (add)->next->prev = (add); \
644 } \
645 } \
646 } while (0)
647
648 # define DL_PREPEND_ELEM(head, el, add) \
649 do { \
650 assert(head != NULL); \
651 assert(el != NULL); \
652 assert(add != NULL); \
653 (add)->next = (el); \
654 (add)->prev = (el)->prev; \
655 (el)->prev = (add); \
656 if ((head) == (el)) { \
657 (head) = (add); \
658 } else { \
659 (add)->prev->next = (add); \
660 } \
661 } while (0) \
662
663 /*
664 ******************************************************************************
665 * circular doubly linked list macros *
666 ******************************************************************************
667 */
668
669 # define CDL_PREPEND(head,add) \
670 CDL_PREPEND2(head,add,prev,next)
671
672 # define CDL_PREPEND2(head,add,prev,next) \
673 do { \
674 if (head) { \
675 (add)->prev = (head)->prev; \
676 (add)->next = (head); \
677 (head)->prev = (add); \
678 (add)->prev->next = (add); \
679 } else { \
680 (add)->prev = (add); \
681 (add)->next = (add); \
682 } \
683 (head)=(add); \
684 } while (0)
685
686 # define CDL_DELETE(head,del) \
687 CDL_DELETE2(head,del,prev,next)
688
689 # define CDL_DELETE2(head,del,prev,next) \
690 do { \
691 if ( ((head)==(del)) && ((head)->next == (head))) { \
692 (head) = 0L; \
693 } else { \
694 (del)->next->prev = (del)->prev; \
695 (del)->prev->next = (del)->next; \
696 if ((del) == (head)) (head)=(del)->next; \
697 } \
698 } while (0)
699
700 # define CDL_FOREACH(head,el) \
701 CDL_FOREACH2(head,el,next)
702
703 # define CDL_FOREACH2(head,el,next) \
704 for(el=head;el;el=((el)->next==head ? 0L : (el)->next))
705
706 # define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \
707 CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
708
709 # define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \
710 for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \
711 (el) && ((tmp2)=(el)->next, 1); \
712 ((el) = (((el)==(tmp1)) ? 0L : (tmp2))))
713
714 # define CDL_SEARCH_SCALAR(head,out,field,val) \
715 CDL_SEARCH_SCALAR2(head,out,field,val,next)
716
717 # define CDL_SEARCH_SCALAR2(head,out,field,val,next) \
718 do { \
719 CDL_FOREACH2(head,out,next) { \
720 if ((out)->field == (val)) break; \
721 } \
722 } while(0)
723
724 # define CDL_SEARCH(head,out,elt,cmp) \
725 CDL_SEARCH2(head,out,elt,cmp,next)
726
727 # define CDL_SEARCH2(head,out,elt,cmp,next) \
728 do { \
729 CDL_FOREACH2(head,out,next) { \
730 if ((cmp(out,elt))==0) break; \
731 } \
732 } while(0)
733
734 # define CDL_REPLACE_ELEM(head, el, add) \
735 do { \
736 assert(head != NULL); \
737 assert(el != NULL); \
738 assert(add != NULL); \
739 if ((el)->next == (el)) { \
740 (add)->next = (add); \
741 (add)->prev = (add); \
742 (head) = (add); \
743 } else { \
744 (add)->next = (el)->next; \
745 (add)->prev = (el)->prev; \
746 (add)->next->prev = (add); \
747 (add)->prev->next = (add); \
748 if ((head) == (el)) { \
749 (head) = (add); \
750 } \
751 } \
752 } while (0)
753
754 # define CDL_PREPEND_ELEM(head, el, add) \
755 do { \
756 assert(head != NULL); \
757 assert(el != NULL); \
758 assert(add != NULL); \
759 (add)->next = (el); \
760 (add)->prev = (el)->prev; \
761 (el)->prev = (add); \
762 (add)->prev->next = (add); \
763 if ((head) == (el)) { \
764 (head) = (add); \
765 } \
766 } while (0) \
767
768 #endif /* UTLIST_H */
![[top]](../icons/top.png){kind=icon}
![[bottom]](../icons/n_bottom.png){kind=icon}
*/