utlist.h
Go to the documentation of this file.
1 /*
2  * SPDX-FileCopyrightText: 2007-2014 Troy D. Hanson http://troydhanson.github.com/uthash/
3  * SPDX-License-Identifier: BSD-1-Clause
4  */
5 
6 #pragma once
7 
22 #define UTLIST_VERSION 1.9.9
23 #include <stddef.h>
24 
25 #include <assert.h>
26 
27 #ifdef __cplusplus
28 extern "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
115 #define LL_SORT(list, cmp) \
116  LL_SORT2(list, cmp, next)
117 
118 #define LL_SORT2(list, cmp, next) \
119 do { \
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) \
181 do { \
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) \
243 do { \
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)
321 #define LL_PREPEND(head,add) \
322  LL_PREPEND2(head,add,next)
323 
325 #define LL_PREPEND2(head,add,next) \
326 do { \
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) \
337 do { \
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) \
354 do { \
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) \
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 /* 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) \
392 do { \
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) \
407 do { \
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 
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) \
474 do { \
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) \
486 do { \
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) \
494 do { \
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) \
515 do { \
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)
540 #define DL_PREPEND(head,add) \
541  DL_PREPEND2(head,add,prev,next)
542 
544 #define DL_PREPEND2(head,add,prev,next) \
545 do { \
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) \
562 do { \
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) \
581 do { \
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) \
601 do { \
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 
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) \
674 do { \
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) \
701 do { \
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)
721 #define CDL_PREPEND(head,add) \
722  CDL_PREPEND2(head,add,prev,next)
723 
725 #define CDL_PREPEND2(head,add,prev,next) \
726 do { \
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) \
745 do { \
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 
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) \
793 do { \
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) \
805 do { \
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) \
813 do { \
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) \
834 do { \
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)
848 #ifdef __cplusplus
849 }
850 #endif
851 
assert.h
POSIX.1-2008 compliant version of the assert macro.