Loading...
Searching...
No Matches
utlist.h
Go to the documentation of this file.
1/*
2 * SPDX-FileCopyrightText: 2007-2014 Troy D. Hanson http://troydhanson.github.io/uthash/
3 * SPDX-License-Identifier: BSD-1-Clause
4 */
5
6#pragma once
7
20
22#define UTLIST_VERSION 1.9.9
23#include <stddef.h>
24
25#include <assert.h>
26
27#ifdef __cplusplus
28extern "C" {
29#endif
30
31/*
32 * This file contains macros to manipulate singly and doubly-linked lists.
33 *
34 * 1. LL_ macros: singly-linked lists.
35 * 2. DL_ macros: doubly-linked lists.
36 * 3. CDL_ macros: circular doubly-linked lists.
37 *
38 * To use singly-linked lists, your structure must have a "next" pointer.
39 * To use doubly-linked lists, your structure must "prev" and "next" pointers.
40 * Either way, the pointer to the head of the list must be initialized to NULL.
41 *
42 * ----------------.EXAMPLE -------------------------
43 * struct item {
44 * int id;
45 * struct item *prev, *next;
46 * }
47 *
48 * struct item *list = NULL:
49 *
50 * int main() {
51 * struct item *item;
52 * ... allocate and populate item ...
53 * DL_APPEND(list, item);
54 * }
55 * --------------------------------------------------
56 *
57 * For doubly-linked lists, the append and delete macros are O(1)
58 * For singly-linked lists, append and delete are O(n) but prepend is O(1)
59 * The sort macro is O(n log(n)) for all types of single/double/circular lists.
60 */
61
75#ifdef _MSC_VER /* MS compiler */
76#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */
77#define LDECLTYPE(x) decltype(x)
78#else /* VS2008 or older (or VS2010 in C mode) */
79#define NO_DECLTYPE
80#define LDECLTYPE(x) char*
81#endif
82#elif defined(__ICCARM__)
83#define NO_DECLTYPE
84#define LDECLTYPE(x) char*
85#else /* GNU, Sun and other compilers */
86#define LDECLTYPE(x) __typeof(x)
87#endif
88
89#ifdef NO_DECLTYPE
90#define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
91#define _NEXT(elt,list,next) ((char*)((list)->next))
92#define _NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }
93/* #define _PREV(elt,list,prev) ((char*)((list)->prev)) */
94#define _PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }
95#define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
96#define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
97#else
98#define _SV(elt,list)
99#define _NEXT(elt,list,next) ((elt)->next)
100#define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to)
101/* #define _PREV(elt,list,prev) ((elt)->prev) */
102#define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to)
103#define _RS(list)
104#define _CASTASGN(a,b) (a)=(b)
105#endif
107
115#define LL_SORT(list, cmp) \
116 LL_SORT2(list, cmp, next)
117
118#define LL_SORT2(list, cmp, next) \
119do { \
120 LDECLTYPE(list) _ls_p; \
121 LDECLTYPE(list) _ls_q; \
122 LDECLTYPE(list) _ls_e; \
123 LDECLTYPE(list) _ls_tail; \
124 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
125 if (list) { \
126 _ls_insize = 1; \
127 _ls_looping = 1; \
128 while (_ls_looping) { \
129 _CASTASGN(_ls_p,list); \
130 list = NULL; \
131 _ls_tail = NULL; \
132 _ls_nmerges = 0; \
133 while (_ls_p) { \
134 _ls_nmerges++; \
135 _ls_q = _ls_p; \
136 _ls_psize = 0; \
137 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
138 _ls_psize++; \
139 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
140 if (!_ls_q) break; \
141 } \
142 _ls_qsize = _ls_insize; \
143 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
144 if (_ls_psize == 0) { \
145 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
146 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
147 } else if (_ls_qsize == 0 || !_ls_q) { \
148 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
149 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
150 } else if (cmp(_ls_p,_ls_q) <= 0) { \
151 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
152 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
153 } else { \
154 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
155 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
156 } \
157 if (_ls_tail) { \
158 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
159 } else { \
160 _CASTASGN(list,_ls_e); \
161 } \
162 _ls_tail = _ls_e; \
163 } \
164 _ls_p = _ls_q; \
165 } \
166 if (_ls_tail) { \
167 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
168 } \
169 if (_ls_nmerges <= 1) { \
170 _ls_looping=0; \
171 } \
172 _ls_insize *= 2; \
173 } \
174 } \
175} while (0)
176
177#define DL_SORT(list, cmp) \
178 DL_SORT2(list, cmp, prev, next)
179
180#define DL_SORT2(list, cmp, prev, next) \
181do { \
182 LDECLTYPE(list) _ls_p; \
183 LDECLTYPE(list) _ls_q; \
184 LDECLTYPE(list) _ls_e; \
185 LDECLTYPE(list) _ls_tail; \
186 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
187 if (list) { \
188 _ls_insize = 1; \
189 _ls_looping = 1; \
190 while (_ls_looping) { \
191 _CASTASGN(_ls_p,list); \
192 list = NULL; \
193 _ls_tail = NULL; \
194 _ls_nmerges = 0; \
195 while (_ls_p) { \
196 _ls_nmerges++; \
197 _ls_q = _ls_p; \
198 _ls_psize = 0; \
199 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
200 _ls_psize++; \
201 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
202 if (!_ls_q) break; \
203 } \
204 _ls_qsize = _ls_insize; \
205 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
206 if (_ls_psize == 0) { \
207 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
208 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
209 } else if (_ls_qsize == 0 || !_ls_q) { \
210 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
211 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
212 } else if (cmp(_ls_p,_ls_q) <= 0) { \
213 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
214 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
215 } else { \
216 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
217 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
218 } \
219 if (_ls_tail) { \
220 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
221 } else { \
222 _CASTASGN(list,_ls_e); \
223 } \
224 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
225 _ls_tail = _ls_e; \
226 } \
227 _ls_p = _ls_q; \
228 } \
229 _CASTASGN(list->prev, _ls_tail); \
230 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
231 if (_ls_nmerges <= 1) { \
232 _ls_looping=0; \
233 } \
234 _ls_insize *= 2; \
235 } \
236 } \
237} while (0)
238
239#define CDL_SORT(list, cmp) \
240 CDL_SORT2(list, cmp, prev, next)
241
242#define CDL_SORT2(list, cmp, prev, next) \
243do { \
244 LDECLTYPE(list) _ls_p; \
245 LDECLTYPE(list) _ls_q; \
246 LDECLTYPE(list) _ls_e; \
247 LDECLTYPE(list) _ls_tail; \
248 LDECLTYPE(list) _ls_oldhead; \
249 LDECLTYPE(list) _tmp; \
250 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
251 if (list) { \
252 _ls_insize = 1; \
253 _ls_looping = 1; \
254 while (_ls_looping) { \
255 _CASTASGN(_ls_p,list); \
256 _CASTASGN(_ls_oldhead,list); \
257 list = NULL; \
258 _ls_tail = NULL; \
259 _ls_nmerges = 0; \
260 while (_ls_p) { \
261 _ls_nmerges++; \
262 _ls_q = _ls_p; \
263 _ls_psize = 0; \
264 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
265 _ls_psize++; \
266 _SV(_ls_q,list); \
267 if (_NEXT(_ls_q,list,next) == _ls_oldhead) { \
268 _ls_q = NULL; \
269 } else { \
270 _ls_q = _NEXT(_ls_q,list,next); \
271 } \
272 _RS(list); \
273 if (!_ls_q) break; \
274 } \
275 _ls_qsize = _ls_insize; \
276 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
277 if (_ls_psize == 0) { \
278 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
279 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
280 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
281 } else if (_ls_qsize == 0 || !_ls_q) { \
282 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
283 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
284 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
285 } else if (cmp(_ls_p,_ls_q) <= 0) { \
286 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
287 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
288 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
289 } else { \
290 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
291 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
292 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
293 } \
294 if (_ls_tail) { \
295 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
296 } else { \
297 _CASTASGN(list,_ls_e); \
298 } \
299 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
300 _ls_tail = _ls_e; \
301 } \
302 _ls_p = _ls_q; \
303 } \
304 _CASTASGN(list->prev,_ls_tail); \
305 _CASTASGN(_tmp,list); \
306 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp,next); _RS(list); \
307 if (_ls_nmerges <= 1) { \
308 _ls_looping=0; \
309 } \
310 _ls_insize *= 2; \
311 } \
312 } \
313} while (0)
315
321#define LL_PREPEND(head,add) \
322 LL_PREPEND2(head,add,next)
323
325#define LL_PREPEND2(head,add,next) \
326do { \
327 (add)->next = head; \
328 head = add; \
329} while (0)
330
332#define LL_CONCAT(head1,head2) \
333 LL_CONCAT2(head1,head2,next)
334
336#define LL_CONCAT2(head1,head2,next) \
337do { \
338 LDECLTYPE(head1) _tmp; \
339 if (head1) { \
340 _tmp = head1; \
341 while (_tmp->next) { _tmp = _tmp->next; } \
342 _tmp->next=(head2); \
343 } else { \
344 (head1)=(head2); \
345 } \
346} while (0)
347
349#define LL_APPEND(head,add) \
350 LL_APPEND2(head,add,next)
351
353#define LL_APPEND2(head,add,next) \
354do { \
355 LDECLTYPE(head) _tmp; \
356 (add)->next=NULL; \
357 if (head) { \
358 _tmp = head; \
359 while (_tmp->next) { _tmp = _tmp->next; } \
360 _tmp->next=(add); \
361 } else { \
362 (head)=(add); \
363 } \
364} while (0)
365
367#define LL_DELETE(head,del) \
368 LL_DELETE2(head,del,next)
369
371#define LL_DELETE2(head,del,next) \
372do { \
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/* Here are VS2008 replacements for LL_APPEND and LL_DELETE */
388#define LL_APPEND_VS2008(head,add) \
389 LL_APPEND2_VS2008(head,add,next)
390
391#define LL_APPEND2_VS2008(head,add,next) \
392do { \
393 if (head) { \
394 (add)->next = head; /* use add->next as a temp variable */ \
395 while ((add)->next->next) { (add)->next = (add)->next->next; } \
396 (add)->next->next=(add); \
397 } else { \
398 (head)=(add); \
399 } \
400 (add)->next=NULL; \
401} while (0)
402
403#define LL_DELETE_VS2008(head,del) \
404 LL_DELETE2_VS2008(head,del,next)
405
406#define LL_DELETE2_VS2008(head,del,next) \
407do { \
408 if ((head) == (del)) { \
409 (head)=(head)->next; \
410 } else { \
411 char *_tmp = (char*)(head); \
412 while ((head)->next && ((head)->next != (del))) { \
413 head = (head)->next; \
414 } \
415 if ((head)->next) { \
416 (head)->next = ((del)->next); \
417 } \
418 { \
419 char **_head_alias = (char**)&(head); \
420 *_head_alias = _tmp; \
421 } \
422 } \
423} while (0)
424#ifdef NO_DECLTYPE
425#undef LL_APPEND
426#define LL_APPEND LL_APPEND_VS2008
427#undef LL_DELETE
428#define LL_DELETE LL_DELETE_VS2008
429#undef LL_DELETE2
430#define LL_DELETE2 LL_DELETE2_VS2008
431#undef LL_APPEND2
432#define LL_APPEND2 LL_APPEND2_VS2008
433#undef LL_CONCAT /* no LL_CONCAT_VS2008 */
434#undef DL_CONCAT /* no DL_CONCAT_VS2008 */
435#endif
436/* end VS2008 replacements */
437
439#define LL_COUNT(head,el,counter) \
440 LL_COUNT2(head,el,counter,next) \
441
442
443#define LL_COUNT2(head,el,counter,next) \
444{ \
445 counter = 0; \
446 LL_FOREACH2(head,el,next){ ++counter; } \
447}
448
450#define LL_FOREACH(head,el) \
451 LL_FOREACH2(head,el,next)
452
454#define LL_FOREACH2(head,el,next) \
455 for(el=head;el;el=(el)->next)
456
461#define LL_FOREACH_SAFE(head,el,tmp) \
462 LL_FOREACH_SAFE2(head,el,tmp,next)
463
465#define LL_FOREACH_SAFE2(head,el,tmp,next) \
466 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
467
469#define LL_SEARCH_SCALAR(head,out,field,val) \
470 LL_SEARCH_SCALAR2(head,out,field,val,next)
471
473#define LL_SEARCH_SCALAR2(head,out,field,val,next) \
474do { \
475 LL_FOREACH2(head,out,next) { \
476 if ((out)->field == (val)) break; \
477 } \
478} while(0)
479
481#define LL_SEARCH(head,out,elt,cmp) \
482 LL_SEARCH2(head,out,elt,cmp,next)
483
485#define LL_SEARCH2(head,out,elt,cmp,next) \
486do { \
487 LL_FOREACH2(head,out,next) { \
488 if ((cmp(out,elt))==0) break; \
489 } \
490} while(0)
491
493#define LL_REPLACE_ELEM(head, el, add) \
494do { \
495 LDECLTYPE(head) _tmp; \
496 assert(head != NULL); \
497 assert(el != NULL); \
498 assert(add != NULL); \
499 (add)->next = (el)->next; \
500 if ((head) == (el)) { \
501 (head) = (add); \
502 } else { \
503 _tmp = head; \
504 while (_tmp->next && (_tmp->next != (el))) { \
505 _tmp = _tmp->next; \
506 } \
507 if (_tmp->next) { \
508 _tmp->next = (add); \
509 } \
510 } \
511} while (0)
512
514#define LL_PREPEND_ELEM(head, el, add) \
515do { \
516 LDECLTYPE(head) _tmp; \
517 assert(head != NULL); \
518 assert(el != NULL); \
519 assert(add != NULL); \
520 (add)->next = (el); \
521 if ((head) == (el)) { \
522 (head) = (add); \
523 } else { \
524 _tmp = head; \
525 while (_tmp->next && (_tmp->next != (el))) { \
526 _tmp = _tmp->next; \
527 } \
528 if (_tmp->next) { \
529 _tmp->next = (add); \
530 } \
531 } \
532} while (0)
533
534
540#define DL_PREPEND(head,add) \
541 DL_PREPEND2(head,add,prev,next)
542
544#define DL_PREPEND2(head,add,prev,next) \
545do { \
546 (add)->next = head; \
547 if (head) { \
548 (add)->prev = (head)->prev; \
549 (head)->prev = (add); \
550 } else { \
551 (add)->prev = (add); \
552 } \
553 (head) = (add); \
554} while (0)
555
557#define DL_APPEND(head,add) \
558 DL_APPEND2(head,add,prev,next)
559
561#define DL_APPEND2(head,add,prev,next) \
562do { \
563 if (head) { \
564 (add)->prev = (head)->prev; \
565 (head)->prev->next = (add); \
566 (head)->prev = (add); \
567 (add)->next = NULL; \
568 } else { \
569 (head)=(add); \
570 (head)->prev = (head); \
571 (head)->next = NULL; \
572 } \
573} while (0)
574
576#define DL_CONCAT(head1,head2) \
577 DL_CONCAT2(head1,head2,prev,next)
578
580#define DL_CONCAT2(head1,head2,prev,next) \
581do { \
582 LDECLTYPE(head1) _tmp; \
583 if (head2) { \
584 if (head1) { \
585 _tmp = (head2)->prev; \
586 (head2)->prev = (head1)->prev; \
587 (head1)->prev->next = (head2); \
588 (head1)->prev = _tmp; \
589 } else { \
590 (head1)=(head2); \
591 } \
592 } \
593} while (0)
594
596#define DL_DELETE(head,del) \
597 DL_DELETE2(head,del,prev,next)
598
600#define DL_DELETE2(head,del,prev,next) \
601do { \
602 assert((del)->prev != NULL); \
603 if ((del)->prev == (del)) { \
604 (head)=NULL; \
605 } else if ((del)==(head)) { \
606 (del)->next->prev = (del)->prev; \
607 (head) = (del)->next; \
608 } else { \
609 (del)->prev->next = (del)->next; \
610 if ((del)->next) { \
611 (del)->next->prev = (del)->prev; \
612 } else { \
613 (head)->prev = (del)->prev; \
614 } \
615 } \
616} while (0)
617
619#define DL_COUNT(head,el,counter) \
620 DL_COUNT2(head,el,counter,next) \
621
622
623#define DL_COUNT2(head,el,counter,next) \
624{ \
625 counter = 0; \
626 DL_FOREACH2(head,el,next){ ++counter; } \
627}
628
630#define DL_FOREACH(head,el) \
631 DL_FOREACH2(head,el,next)
632
634#define DL_FOREACH2(head,el,next) \
635 for(el=head;el;el=(el)->next)
636
641#define DL_FOREACH_SAFE(head,el,tmp) \
642 DL_FOREACH_SAFE2(head,el,tmp,next)
643
645#define DL_FOREACH_SAFE2(head,el,tmp,next) \
646 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
647
652#define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
653
658#define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2
659
664#define DL_SEARCH LL_SEARCH
665
670#define DL_SEARCH2 LL_SEARCH2
671
673#define DL_REPLACE_ELEM(head, el, add) \
674do { \
675 assert(head != NULL); \
676 assert(el != NULL); \
677 assert(add != NULL); \
678 if ((head) == (el)) { \
679 (head) = (add); \
680 (add)->next = (el)->next; \
681 if ((el)->next == NULL) { \
682 (add)->prev = (add); \
683 } else { \
684 (add)->prev = (el)->prev; \
685 (add)->next->prev = (add); \
686 } \
687 } else { \
688 (add)->next = (el)->next; \
689 (add)->prev = (el)->prev; \
690 (add)->prev->next = (add); \
691 if ((el)->next == NULL) { \
692 (head)->prev = (add); \
693 } else { \
694 (add)->next->prev = (add); \
695 } \
696 } \
697} while (0)
698
700#define DL_PREPEND_ELEM(head, el, add) \
701do { \
702 assert(head != NULL); \
703 assert(el != NULL); \
704 assert(add != NULL); \
705 (add)->next = (el); \
706 (add)->prev = (el)->prev; \
707 (el)->prev = (add); \
708 if ((head) == (el)) { \
709 (head) = (add); \
710 } else { \
711 (add)->prev->next = (add); \
712 } \
713} while (0)
714
715
721#define CDL_PREPEND(head,add) \
722 CDL_PREPEND2(head,add,prev,next)
723
725#define CDL_PREPEND2(head,add,prev,next) \
726do { \
727 if (head) { \
728 (add)->prev = (head)->prev; \
729 (add)->next = (head); \
730 (head)->prev = (add); \
731 (add)->prev->next = (add); \
732 } else { \
733 (add)->prev = (add); \
734 (add)->next = (add); \
735 } \
736(head)=(add); \
737} while (0)
738
740#define CDL_DELETE(head,del) \
741 CDL_DELETE2(head,del,prev,next)
742
744#define CDL_DELETE2(head,del,prev,next) \
745do { \
746 if ( ((head)==(del)) && ((head)->next == (head))) { \
747 (head) = 0L; \
748 } else { \
749 (del)->next->prev = (del)->prev; \
750 (del)->prev->next = (del)->next; \
751 if ((del) == (head)) (head)=(del)->next; \
752 } \
753} while (0)
754
756#define CDL_COUNT(head,el,counter) \
757 CDL_COUNT2(head,el,counter,next) \
758
759
760#define CDL_COUNT2(head, el, counter,next) \
761{ \
762 counter = 0; \
763 CDL_FOREACH2(head,el,next){ ++counter; } \
764}
765
767#define CDL_FOREACH(head,el) \
768 CDL_FOREACH2(head,el,next)
769
771#define CDL_FOREACH2(head,el,next) \
772 for(el=head;el;el=((el)->next==head ? 0L : (el)->next))
773
778#define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \
779 CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
780
782#define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \
783 for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \
784 (el) && ((tmp2)=(el)->next, 1); \
785 ((el) = (((el)==(tmp1)) ? 0L : (tmp2))))
786
788#define CDL_SEARCH_SCALAR(head,out,field,val) \
789 CDL_SEARCH_SCALAR2(head,out,field,val,next)
790
792#define CDL_SEARCH_SCALAR2(head,out,field,val,next) \
793do { \
794 CDL_FOREACH2(head,out,next) { \
795 if ((out)->field == (val)) break; \
796 } \
797} while(0)
798
800#define CDL_SEARCH(head,out,elt,cmp) \
801 CDL_SEARCH2(head,out,elt,cmp,next)
802
804#define CDL_SEARCH2(head,out,elt,cmp,next) \
805do { \
806 CDL_FOREACH2(head,out,next) { \
807 if ((cmp(out,elt))==0) break; \
808 } \
809} while(0)
810
812#define CDL_REPLACE_ELEM(head, el, add) \
813do { \
814 assert(head != NULL); \
815 assert(el != NULL); \
816 assert(add != NULL); \
817 if ((el)->next == (el)) { \
818 (add)->next = (add); \
819 (add)->prev = (add); \
820 (head) = (add); \
821 } else { \
822 (add)->next = (el)->next; \
823 (add)->prev = (el)->prev; \
824 (add)->next->prev = (add); \
825 (add)->prev->next = (add); \
826 if ((head) == (el)) { \
827 (head) = (add); \
828 } \
829 } \
830} while (0)
831
833#define CDL_PREPEND_ELEM(head, el, add) \
834do { \
835 assert(head != NULL); \
836 assert(el != NULL); \
837 assert(add != NULL); \
838 (add)->next = (el); \
839 (add)->prev = (el)->prev; \
840 (el)->prev = (add); \
841 (add)->prev->next = (add); \
842 if ((head) == (el)) { \
843 (head) = (add); \
844 } \
845} while (0)
846
847
848#ifdef __cplusplus
849}
850#endif
851
assert.h
POSIX.1-2008 compliant version of the assert macro.