utlist.h
Go to the documentation of this file.
1 /*
2 Copyright (c) 2007-2014, Troy D. Hanson http://troydhanson.github.com/uthash/
3 All rights reserved.
4 
5 Redistribution and use in source and binary forms, with or without
6 modification, 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 
11 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
12 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
13 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
14 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
15 OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
16 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
17 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
18 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
19 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
20 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
21 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
22 */
23 
24 #pragma once
25 
40 #define UTLIST_VERSION 1.9.9
41 #include <stddef.h>
42 
43 #include <assert.h>
44 
45 #ifdef __cplusplus
46 extern "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
133 #define LL_SORT(list, cmp) \
134  LL_SORT2(list, cmp, next)
135 
136 #define LL_SORT2(list, cmp, next) \
137 do { \
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) \
199 do { \
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) \
261 do { \
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)
339 #define LL_PREPEND(head,add) \
340  LL_PREPEND2(head,add,next)
341 
343 #define LL_PREPEND2(head,add,next) \
344 do { \
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) \
355 do { \
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) \
372 do { \
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) \
390 do { \
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) \
410 do { \
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) \
425 do { \
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 
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) \
492 do { \
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) \
504 do { \
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) \
512 do { \
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) \
533 do { \
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)
558 #define DL_PREPEND(head,add) \
559  DL_PREPEND2(head,add,prev,next)
560 
562 #define DL_PREPEND2(head,add,prev,next) \
563 do { \
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) \
580 do { \
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) \
599 do { \
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) \
619 do { \
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 
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) \
692 do { \
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) \
719 do { \
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)
739 #define CDL_PREPEND(head,add) \
740  CDL_PREPEND2(head,add,prev,next)
741 
743 #define CDL_PREPEND2(head,add,prev,next) \
744 do { \
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) \
763 do { \
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 
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) \
811 do { \
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) \
823 do { \
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) \
831 do { \
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) \
852 do { \
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)
866 #ifdef __cplusplus
867 }
868 #endif
869 
assert.h
POSIX.1-2008 compliant version of the assert macro.