Loading...
Searching...
No Matches
utlist.h
Go to the documentation of this file.
1/*
2Copyright (c) 2007-2014, Troy D. Hanson http://troydhanson.github.com/uthash/
3All rights reserved.
4
5Redistribution and use in source and binary forms, with or without
6modification, are permitted provided that the following conditions are met:
7
8 * Redistributions of source code must retain the above copyright
9 notice, this list of conditions and the following disclaimer.
10
11THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
12IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
13TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
14PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
15OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
16EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
17PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
18PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
19LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
20NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
21SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
22*/
23
24#pragma once
25
38
40#define UTLIST_VERSION 1.9.9
41#include <stddef.h>
42
43#include <assert.h>
44
45#ifdef __cplusplus
46extern "C" {
47#endif
48
49/*
50 * This file contains macros to manipulate singly and doubly-linked lists.
51 *
52 * 1. LL_ macros: singly-linked lists.
53 * 2. DL_ macros: doubly-linked lists.
54 * 3. CDL_ macros: circular doubly-linked lists.
55 *
56 * To use singly-linked lists, your structure must have a "next" pointer.
57 * To use doubly-linked lists, your structure must "prev" and "next" pointers.
58 * Either way, the pointer to the head of the list must be initialized to NULL.
59 *
60 * ----------------.EXAMPLE -------------------------
61 * struct item {
62 * int id;
63 * struct item *prev, *next;
64 * }
65 *
66 * struct item *list = NULL:
67 *
68 * int main() {
69 * struct item *item;
70 * ... allocate and populate item ...
71 * DL_APPEND(list, item);
72 * }
73 * --------------------------------------------------
74 *
75 * For doubly-linked lists, the append and delete macros are O(1)
76 * For singly-linked lists, append and delete are O(n) but prepend is O(1)
77 * The sort macro is O(n log(n)) for all types of single/double/circular lists.
78 */
79
93#ifdef _MSC_VER /* MS compiler */
94#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */
95#define LDECLTYPE(x) decltype(x)
96#else /* VS2008 or older (or VS2010 in C mode) */
97#define NO_DECLTYPE
98#define LDECLTYPE(x) char*
99#endif
100#elif defined(__ICCARM__)
101#define NO_DECLTYPE
102#define LDECLTYPE(x) char*
103#else /* GNU, Sun and other compilers */
104#define LDECLTYPE(x) __typeof(x)
105#endif
106
107#ifdef NO_DECLTYPE
108#define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
109#define _NEXT(elt,list,next) ((char*)((list)->next))
110#define _NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }
111/* #define _PREV(elt,list,prev) ((char*)((list)->prev)) */
112#define _PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }
113#define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
114#define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
115#else
116#define _SV(elt,list)
117#define _NEXT(elt,list,next) ((elt)->next)
118#define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to)
119/* #define _PREV(elt,list,prev) ((elt)->prev) */
120#define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to)
121#define _RS(list)
122#define _CASTASGN(a,b) (a)=(b)
123#endif
125
133#define LL_SORT(list, cmp) \
134 LL_SORT2(list, cmp, next)
135
136#define LL_SORT2(list, cmp, next) \
137do { \
138 LDECLTYPE(list) _ls_p; \
139 LDECLTYPE(list) _ls_q; \
140 LDECLTYPE(list) _ls_e; \
141 LDECLTYPE(list) _ls_tail; \
142 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
143 if (list) { \
144 _ls_insize = 1; \
145 _ls_looping = 1; \
146 while (_ls_looping) { \
147 _CASTASGN(_ls_p,list); \
148 list = NULL; \
149 _ls_tail = NULL; \
150 _ls_nmerges = 0; \
151 while (_ls_p) { \
152 _ls_nmerges++; \
153 _ls_q = _ls_p; \
154 _ls_psize = 0; \
155 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
156 _ls_psize++; \
157 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
158 if (!_ls_q) break; \
159 } \
160 _ls_qsize = _ls_insize; \
161 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
162 if (_ls_psize == 0) { \
163 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
164 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
165 } else if (_ls_qsize == 0 || !_ls_q) { \
166 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
167 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
168 } else if (cmp(_ls_p,_ls_q) <= 0) { \
169 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
170 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
171 } else { \
172 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
173 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
174 } \
175 if (_ls_tail) { \
176 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
177 } else { \
178 _CASTASGN(list,_ls_e); \
179 } \
180 _ls_tail = _ls_e; \
181 } \
182 _ls_p = _ls_q; \
183 } \
184 if (_ls_tail) { \
185 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
186 } \
187 if (_ls_nmerges <= 1) { \
188 _ls_looping=0; \
189 } \
190 _ls_insize *= 2; \
191 } \
192 } \
193} while (0)
194
195#define DL_SORT(list, cmp) \
196 DL_SORT2(list, cmp, prev, next)
197
198#define DL_SORT2(list, cmp, prev, next) \
199do { \
200 LDECLTYPE(list) _ls_p; \
201 LDECLTYPE(list) _ls_q; \
202 LDECLTYPE(list) _ls_e; \
203 LDECLTYPE(list) _ls_tail; \
204 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
205 if (list) { \
206 _ls_insize = 1; \
207 _ls_looping = 1; \
208 while (_ls_looping) { \
209 _CASTASGN(_ls_p,list); \
210 list = NULL; \
211 _ls_tail = NULL; \
212 _ls_nmerges = 0; \
213 while (_ls_p) { \
214 _ls_nmerges++; \
215 _ls_q = _ls_p; \
216 _ls_psize = 0; \
217 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
218 _ls_psize++; \
219 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
220 if (!_ls_q) break; \
221 } \
222 _ls_qsize = _ls_insize; \
223 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
224 if (_ls_psize == 0) { \
225 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
226 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
227 } else if (_ls_qsize == 0 || !_ls_q) { \
228 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
229 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
230 } else if (cmp(_ls_p,_ls_q) <= 0) { \
231 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
232 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
233 } else { \
234 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
235 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
236 } \
237 if (_ls_tail) { \
238 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
239 } else { \
240 _CASTASGN(list,_ls_e); \
241 } \
242 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
243 _ls_tail = _ls_e; \
244 } \
245 _ls_p = _ls_q; \
246 } \
247 _CASTASGN(list->prev, _ls_tail); \
248 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
249 if (_ls_nmerges <= 1) { \
250 _ls_looping=0; \
251 } \
252 _ls_insize *= 2; \
253 } \
254 } \
255} while (0)
256
257#define CDL_SORT(list, cmp) \
258 CDL_SORT2(list, cmp, prev, next)
259
260#define CDL_SORT2(list, cmp, prev, next) \
261do { \
262 LDECLTYPE(list) _ls_p; \
263 LDECLTYPE(list) _ls_q; \
264 LDECLTYPE(list) _ls_e; \
265 LDECLTYPE(list) _ls_tail; \
266 LDECLTYPE(list) _ls_oldhead; \
267 LDECLTYPE(list) _tmp; \
268 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
269 if (list) { \
270 _ls_insize = 1; \
271 _ls_looping = 1; \
272 while (_ls_looping) { \
273 _CASTASGN(_ls_p,list); \
274 _CASTASGN(_ls_oldhead,list); \
275 list = NULL; \
276 _ls_tail = NULL; \
277 _ls_nmerges = 0; \
278 while (_ls_p) { \
279 _ls_nmerges++; \
280 _ls_q = _ls_p; \
281 _ls_psize = 0; \
282 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
283 _ls_psize++; \
284 _SV(_ls_q,list); \
285 if (_NEXT(_ls_q,list,next) == _ls_oldhead) { \
286 _ls_q = NULL; \
287 } else { \
288 _ls_q = _NEXT(_ls_q,list,next); \
289 } \
290 _RS(list); \
291 if (!_ls_q) break; \
292 } \
293 _ls_qsize = _ls_insize; \
294 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
295 if (_ls_psize == 0) { \
296 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
297 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
298 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
299 } else if (_ls_qsize == 0 || !_ls_q) { \
300 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
301 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
302 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
303 } else if (cmp(_ls_p,_ls_q) <= 0) { \
304 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
305 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
306 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
307 } else { \
308 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
309 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
310 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
311 } \
312 if (_ls_tail) { \
313 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
314 } else { \
315 _CASTASGN(list,_ls_e); \
316 } \
317 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
318 _ls_tail = _ls_e; \
319 } \
320 _ls_p = _ls_q; \
321 } \
322 _CASTASGN(list->prev,_ls_tail); \
323 _CASTASGN(_tmp,list); \
324 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp,next); _RS(list); \
325 if (_ls_nmerges <= 1) { \
326 _ls_looping=0; \
327 } \
328 _ls_insize *= 2; \
329 } \
330 } \
331} while (0)
333
339#define LL_PREPEND(head,add) \
340 LL_PREPEND2(head,add,next)
341
343#define LL_PREPEND2(head,add,next) \
344do { \
345 (add)->next = head; \
346 head = add; \
347} while (0)
348
350#define LL_CONCAT(head1,head2) \
351 LL_CONCAT2(head1,head2,next)
352
354#define LL_CONCAT2(head1,head2,next) \
355do { \
356 LDECLTYPE(head1) _tmp; \
357 if (head1) { \
358 _tmp = head1; \
359 while (_tmp->next) { _tmp = _tmp->next; } \
360 _tmp->next=(head2); \
361 } else { \
362 (head1)=(head2); \
363 } \
364} while (0)
365
367#define LL_APPEND(head,add) \
368 LL_APPEND2(head,add,next)
369
371#define LL_APPEND2(head,add,next) \
372do { \
373 LDECLTYPE(head) _tmp; \
374 (add)->next=NULL; \
375 if (head) { \
376 _tmp = head; \
377 while (_tmp->next) { _tmp = _tmp->next; } \
378 _tmp->next=(add); \
379 } else { \
380 (head)=(add); \
381 } \
382} while (0)
383
385#define LL_DELETE(head,del) \
386 LL_DELETE2(head,del,next)
387
389#define LL_DELETE2(head,del,next) \
390do { \
391 LDECLTYPE(head) _tmp; \
392 if ((head) == (del)) { \
393 (head)=(head)->next; \
394 } else { \
395 _tmp = head; \
396 while (_tmp->next && (_tmp->next != (del))) { \
397 _tmp = _tmp->next; \
398 } \
399 if (_tmp->next) { \
400 _tmp->next = ((del)->next); \
401 } \
402 } \
403} while (0)
404
405/* Here are VS2008 replacements for LL_APPEND and LL_DELETE */
406#define LL_APPEND_VS2008(head,add) \
407 LL_APPEND2_VS2008(head,add,next)
408
409#define LL_APPEND2_VS2008(head,add,next) \
410do { \
411 if (head) { \
412 (add)->next = head; /* use add->next as a temp variable */ \
413 while ((add)->next->next) { (add)->next = (add)->next->next; } \
414 (add)->next->next=(add); \
415 } else { \
416 (head)=(add); \
417 } \
418 (add)->next=NULL; \
419} while (0)
420
421#define LL_DELETE_VS2008(head,del) \
422 LL_DELETE2_VS2008(head,del,next)
423
424#define LL_DELETE2_VS2008(head,del,next) \
425do { \
426 if ((head) == (del)) { \
427 (head)=(head)->next; \
428 } else { \
429 char *_tmp = (char*)(head); \
430 while ((head)->next && ((head)->next != (del))) { \
431 head = (head)->next; \
432 } \
433 if ((head)->next) { \
434 (head)->next = ((del)->next); \
435 } \
436 { \
437 char **_head_alias = (char**)&(head); \
438 *_head_alias = _tmp; \
439 } \
440 } \
441} while (0)
442#ifdef NO_DECLTYPE
443#undef LL_APPEND
444#define LL_APPEND LL_APPEND_VS2008
445#undef LL_DELETE
446#define LL_DELETE LL_DELETE_VS2008
447#undef LL_DELETE2
448#define LL_DELETE2 LL_DELETE2_VS2008
449#undef LL_APPEND2
450#define LL_APPEND2 LL_APPEND2_VS2008
451#undef LL_CONCAT /* no LL_CONCAT_VS2008 */
452#undef DL_CONCAT /* no DL_CONCAT_VS2008 */
453#endif
454/* end VS2008 replacements */
455
457#define LL_COUNT(head,el,counter) \
458 LL_COUNT2(head,el,counter,next) \
459
460
461#define LL_COUNT2(head,el,counter,next) \
462{ \
463 counter = 0; \
464 LL_FOREACH2(head,el,next){ ++counter; } \
465}
466
468#define LL_FOREACH(head,el) \
469 LL_FOREACH2(head,el,next)
470
472#define LL_FOREACH2(head,el,next) \
473 for(el=head;el;el=(el)->next)
474
479#define LL_FOREACH_SAFE(head,el,tmp) \
480 LL_FOREACH_SAFE2(head,el,tmp,next)
481
483#define LL_FOREACH_SAFE2(head,el,tmp,next) \
484 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
485
487#define LL_SEARCH_SCALAR(head,out,field,val) \
488 LL_SEARCH_SCALAR2(head,out,field,val,next)
489
491#define LL_SEARCH_SCALAR2(head,out,field,val,next) \
492do { \
493 LL_FOREACH2(head,out,next) { \
494 if ((out)->field == (val)) break; \
495 } \
496} while(0)
497
499#define LL_SEARCH(head,out,elt,cmp) \
500 LL_SEARCH2(head,out,elt,cmp,next)
501
503#define LL_SEARCH2(head,out,elt,cmp,next) \
504do { \
505 LL_FOREACH2(head,out,next) { \
506 if ((cmp(out,elt))==0) break; \
507 } \
508} while(0)
509
511#define LL_REPLACE_ELEM(head, el, add) \
512do { \
513 LDECLTYPE(head) _tmp; \
514 assert(head != NULL); \
515 assert(el != NULL); \
516 assert(add != NULL); \
517 (add)->next = (el)->next; \
518 if ((head) == (el)) { \
519 (head) = (add); \
520 } else { \
521 _tmp = head; \
522 while (_tmp->next && (_tmp->next != (el))) { \
523 _tmp = _tmp->next; \
524 } \
525 if (_tmp->next) { \
526 _tmp->next = (add); \
527 } \
528 } \
529} while (0)
530
532#define LL_PREPEND_ELEM(head, el, add) \
533do { \
534 LDECLTYPE(head) _tmp; \
535 assert(head != NULL); \
536 assert(el != NULL); \
537 assert(add != NULL); \
538 (add)->next = (el); \
539 if ((head) == (el)) { \
540 (head) = (add); \
541 } else { \
542 _tmp = head; \
543 while (_tmp->next && (_tmp->next != (el))) { \
544 _tmp = _tmp->next; \
545 } \
546 if (_tmp->next) { \
547 _tmp->next = (add); \
548 } \
549 } \
550} while (0)
551
552
558#define DL_PREPEND(head,add) \
559 DL_PREPEND2(head,add,prev,next)
560
562#define DL_PREPEND2(head,add,prev,next) \
563do { \
564 (add)->next = head; \
565 if (head) { \
566 (add)->prev = (head)->prev; \
567 (head)->prev = (add); \
568 } else { \
569 (add)->prev = (add); \
570 } \
571 (head) = (add); \
572} while (0)
573
575#define DL_APPEND(head,add) \
576 DL_APPEND2(head,add,prev,next)
577
579#define DL_APPEND2(head,add,prev,next) \
580do { \
581 if (head) { \
582 (add)->prev = (head)->prev; \
583 (head)->prev->next = (add); \
584 (head)->prev = (add); \
585 (add)->next = NULL; \
586 } else { \
587 (head)=(add); \
588 (head)->prev = (head); \
589 (head)->next = NULL; \
590 } \
591} while (0)
592
594#define DL_CONCAT(head1,head2) \
595 DL_CONCAT2(head1,head2,prev,next)
596
598#define DL_CONCAT2(head1,head2,prev,next) \
599do { \
600 LDECLTYPE(head1) _tmp; \
601 if (head2) { \
602 if (head1) { \
603 _tmp = (head2)->prev; \
604 (head2)->prev = (head1)->prev; \
605 (head1)->prev->next = (head2); \
606 (head1)->prev = _tmp; \
607 } else { \
608 (head1)=(head2); \
609 } \
610 } \
611} while (0)
612
614#define DL_DELETE(head,del) \
615 DL_DELETE2(head,del,prev,next)
616
618#define DL_DELETE2(head,del,prev,next) \
619do { \
620 assert((del)->prev != NULL); \
621 if ((del)->prev == (del)) { \
622 (head)=NULL; \
623 } else if ((del)==(head)) { \
624 (del)->next->prev = (del)->prev; \
625 (head) = (del)->next; \
626 } else { \
627 (del)->prev->next = (del)->next; \
628 if ((del)->next) { \
629 (del)->next->prev = (del)->prev; \
630 } else { \
631 (head)->prev = (del)->prev; \
632 } \
633 } \
634} while (0)
635
637#define DL_COUNT(head,el,counter) \
638 DL_COUNT2(head,el,counter,next) \
639
640
641#define DL_COUNT2(head,el,counter,next) \
642{ \
643 counter = 0; \
644 DL_FOREACH2(head,el,next){ ++counter; } \
645}
646
648#define DL_FOREACH(head,el) \
649 DL_FOREACH2(head,el,next)
650
652#define DL_FOREACH2(head,el,next) \
653 for(el=head;el;el=(el)->next)
654
659#define DL_FOREACH_SAFE(head,el,tmp) \
660 DL_FOREACH_SAFE2(head,el,tmp,next)
661
663#define DL_FOREACH_SAFE2(head,el,tmp,next) \
664 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
665
670#define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
671
676#define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2
677
682#define DL_SEARCH LL_SEARCH
683
688#define DL_SEARCH2 LL_SEARCH2
689
691#define DL_REPLACE_ELEM(head, el, add) \
692do { \
693 assert(head != NULL); \
694 assert(el != NULL); \
695 assert(add != NULL); \
696 if ((head) == (el)) { \
697 (head) = (add); \
698 (add)->next = (el)->next; \
699 if ((el)->next == NULL) { \
700 (add)->prev = (add); \
701 } else { \
702 (add)->prev = (el)->prev; \
703 (add)->next->prev = (add); \
704 } \
705 } else { \
706 (add)->next = (el)->next; \
707 (add)->prev = (el)->prev; \
708 (add)->prev->next = (add); \
709 if ((el)->next == NULL) { \
710 (head)->prev = (add); \
711 } else { \
712 (add)->next->prev = (add); \
713 } \
714 } \
715} while (0)
716
718#define DL_PREPEND_ELEM(head, el, add) \
719do { \
720 assert(head != NULL); \
721 assert(el != NULL); \
722 assert(add != NULL); \
723 (add)->next = (el); \
724 (add)->prev = (el)->prev; \
725 (el)->prev = (add); \
726 if ((head) == (el)) { \
727 (head) = (add); \
728 } else { \
729 (add)->prev->next = (add); \
730 } \
731} while (0)
732
733
739#define CDL_PREPEND(head,add) \
740 CDL_PREPEND2(head,add,prev,next)
741
743#define CDL_PREPEND2(head,add,prev,next) \
744do { \
745 if (head) { \
746 (add)->prev = (head)->prev; \
747 (add)->next = (head); \
748 (head)->prev = (add); \
749 (add)->prev->next = (add); \
750 } else { \
751 (add)->prev = (add); \
752 (add)->next = (add); \
753 } \
754(head)=(add); \
755} while (0)
756
758#define CDL_DELETE(head,del) \
759 CDL_DELETE2(head,del,prev,next)
760
762#define CDL_DELETE2(head,del,prev,next) \
763do { \
764 if ( ((head)==(del)) && ((head)->next == (head))) { \
765 (head) = 0L; \
766 } else { \
767 (del)->next->prev = (del)->prev; \
768 (del)->prev->next = (del)->next; \
769 if ((del) == (head)) (head)=(del)->next; \
770 } \
771} while (0)
772
774#define CDL_COUNT(head,el,counter) \
775 CDL_COUNT2(head,el,counter,next) \
776
777
778#define CDL_COUNT2(head, el, counter,next) \
779{ \
780 counter = 0; \
781 CDL_FOREACH2(head,el,next){ ++counter; } \
782}
783
785#define CDL_FOREACH(head,el) \
786 CDL_FOREACH2(head,el,next)
787
789#define CDL_FOREACH2(head,el,next) \
790 for(el=head;el;el=((el)->next==head ? 0L : (el)->next))
791
796#define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \
797 CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
798
800#define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \
801 for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \
802 (el) && ((tmp2)=(el)->next, 1); \
803 ((el) = (((el)==(tmp1)) ? 0L : (tmp2))))
804
806#define CDL_SEARCH_SCALAR(head,out,field,val) \
807 CDL_SEARCH_SCALAR2(head,out,field,val,next)
808
810#define CDL_SEARCH_SCALAR2(head,out,field,val,next) \
811do { \
812 CDL_FOREACH2(head,out,next) { \
813 if ((out)->field == (val)) break; \
814 } \
815} while(0)
816
818#define CDL_SEARCH(head,out,elt,cmp) \
819 CDL_SEARCH2(head,out,elt,cmp,next)
820
822#define CDL_SEARCH2(head,out,elt,cmp,next) \
823do { \
824 CDL_FOREACH2(head,out,next) { \
825 if ((cmp(out,elt))==0) break; \
826 } \
827} while(0)
828
830#define CDL_REPLACE_ELEM(head, el, add) \
831do { \
832 assert(head != NULL); \
833 assert(el != NULL); \
834 assert(add != NULL); \
835 if ((el)->next == (el)) { \
836 (add)->next = (add); \
837 (add)->prev = (add); \
838 (head) = (add); \
839 } else { \
840 (add)->next = (el)->next; \
841 (add)->prev = (el)->prev; \
842 (add)->next->prev = (add); \
843 (add)->prev->next = (add); \
844 if ((head) == (el)) { \
845 (head) = (add); \
846 } \
847 } \
848} while (0)
849
851#define CDL_PREPEND_ELEM(head, el, add) \
852do { \
853 assert(head != NULL); \
854 assert(el != NULL); \
855 assert(add != NULL); \
856 (add)->next = (el); \
857 (add)->prev = (el)->prev; \
858 (el)->prev = (add); \
859 (add)->prev->next = (add); \
860 if ((head) == (el)) { \
861 (head) = (add); \
862 } \
863} while (0)
864
865
866#ifdef __cplusplus
867}
868#endif
869
assert.h
POSIX.1-2008 compliant version of the assert macro.