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 
37 #ifndef UTLIST_H
38 #define UTLIST_H
39 
41 #define UTLIST_VERSION 1.9.9
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
124 
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 
196 #define DL_SORT(list, cmp) \
197  DL_SORT2(list, cmp, prev, next)
198 
199 #define DL_SORT2(list, cmp, prev, next) \
200 do { \
201  LDECLTYPE(list) _ls_p; \
202  LDECLTYPE(list) _ls_q; \
203  LDECLTYPE(list) _ls_e; \
204  LDECLTYPE(list) _ls_tail; \
205  int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
206  if (list) { \
207  _ls_insize = 1; \
208  _ls_looping = 1; \
209  while (_ls_looping) { \
210  _CASTASGN(_ls_p,list); \
211  list = NULL; \
212  _ls_tail = NULL; \
213  _ls_nmerges = 0; \
214  while (_ls_p) { \
215  _ls_nmerges++; \
216  _ls_q = _ls_p; \
217  _ls_psize = 0; \
218  for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
219  _ls_psize++; \
220  _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
221  if (!_ls_q) break; \
222  } \
223  _ls_qsize = _ls_insize; \
224  while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
225  if (_ls_psize == 0) { \
226  _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
227  _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
228  } else if (_ls_qsize == 0 || !_ls_q) { \
229  _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
230  _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
231  } else if (cmp(_ls_p,_ls_q) <= 0) { \
232  _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
233  _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
234  } else { \
235  _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
236  _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
237  } \
238  if (_ls_tail) { \
239  _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
240  } else { \
241  _CASTASGN(list,_ls_e); \
242  } \
243  _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
244  _ls_tail = _ls_e; \
245  } \
246  _ls_p = _ls_q; \
247  } \
248  _CASTASGN(list->prev, _ls_tail); \
249  _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
250  if (_ls_nmerges <= 1) { \
251  _ls_looping=0; \
252  } \
253  _ls_insize *= 2; \
254  } \
255  } \
256 } while (0)
257 
258 #define CDL_SORT(list, cmp) \
259  CDL_SORT2(list, cmp, prev, next)
260 
261 #define CDL_SORT2(list, cmp, prev, next) \
262 do { \
263  LDECLTYPE(list) _ls_p; \
264  LDECLTYPE(list) _ls_q; \
265  LDECLTYPE(list) _ls_e; \
266  LDECLTYPE(list) _ls_tail; \
267  LDECLTYPE(list) _ls_oldhead; \
268  LDECLTYPE(list) _tmp; \
269  int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
270  if (list) { \
271  _ls_insize = 1; \
272  _ls_looping = 1; \
273  while (_ls_looping) { \
274  _CASTASGN(_ls_p,list); \
275  _CASTASGN(_ls_oldhead,list); \
276  list = NULL; \
277  _ls_tail = NULL; \
278  _ls_nmerges = 0; \
279  while (_ls_p) { \
280  _ls_nmerges++; \
281  _ls_q = _ls_p; \
282  _ls_psize = 0; \
283  for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
284  _ls_psize++; \
285  _SV(_ls_q,list); \
286  if (_NEXT(_ls_q,list,next) == _ls_oldhead) { \
287  _ls_q = NULL; \
288  } else { \
289  _ls_q = _NEXT(_ls_q,list,next); \
290  } \
291  _RS(list); \
292  if (!_ls_q) break; \
293  } \
294  _ls_qsize = _ls_insize; \
295  while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
296  if (_ls_psize == 0) { \
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  } else if (_ls_qsize == 0 || !_ls_q) { \
301  _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
302  _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
303  if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
304  } else if (cmp(_ls_p,_ls_q) <= 0) { \
305  _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
306  _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
307  if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
308  } else { \
309  _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
310  _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
311  if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
312  } \
313  if (_ls_tail) { \
314  _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
315  } else { \
316  _CASTASGN(list,_ls_e); \
317  } \
318  _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
319  _ls_tail = _ls_e; \
320  } \
321  _ls_p = _ls_q; \
322  } \
323  _CASTASGN(list->prev,_ls_tail); \
324  _CASTASGN(_tmp,list); \
325  _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp,next); _RS(list); \
326  if (_ls_nmerges <= 1) { \
327  _ls_looping=0; \
328  } \
329  _ls_insize *= 2; \
330  } \
331  } \
332 } while (0)
333 
340 #define LL_PREPEND(head,add) \
341  LL_PREPEND2(head,add,next)
342 
344 #define LL_PREPEND2(head,add,next) \
345 do { \
346  (add)->next = head; \
347  head = add; \
348 } while (0)
349 
351 #define LL_CONCAT(head1,head2) \
352  LL_CONCAT2(head1,head2,next)
353 
355 #define LL_CONCAT2(head1,head2,next) \
356 do { \
357  LDECLTYPE(head1) _tmp; \
358  if (head1) { \
359  _tmp = head1; \
360  while (_tmp->next) { _tmp = _tmp->next; } \
361  _tmp->next=(head2); \
362  } else { \
363  (head1)=(head2); \
364  } \
365 } while (0)
366 
368 #define LL_APPEND(head,add) \
369  LL_APPEND2(head,add,next)
370 
372 #define LL_APPEND2(head,add,next) \
373 do { \
374  LDECLTYPE(head) _tmp; \
375  (add)->next=NULL; \
376  if (head) { \
377  _tmp = head; \
378  while (_tmp->next) { _tmp = _tmp->next; } \
379  _tmp->next=(add); \
380  } else { \
381  (head)=(add); \
382  } \
383 } while (0)
384 
386 #define LL_DELETE(head,del) \
387  LL_DELETE2(head,del,next)
388 
390 #define LL_DELETE2(head,del,next) \
391 do { \
392  LDECLTYPE(head) _tmp; \
393  if ((head) == (del)) { \
394  (head)=(head)->next; \
395  } else { \
396  _tmp = head; \
397  while (_tmp->next && (_tmp->next != (del))) { \
398  _tmp = _tmp->next; \
399  } \
400  if (_tmp->next) { \
401  _tmp->next = ((del)->next); \
402  } \
403  } \
404 } while (0)
405 
406 /* Here are VS2008 replacements for LL_APPEND and LL_DELETE */
407 #define LL_APPEND_VS2008(head,add) \
408  LL_APPEND2_VS2008(head,add,next)
409 
410 #define LL_APPEND2_VS2008(head,add,next) \
411 do { \
412  if (head) { \
413  (add)->next = head; /* use add->next as a temp variable */ \
414  while ((add)->next->next) { (add)->next = (add)->next->next; } \
415  (add)->next->next=(add); \
416  } else { \
417  (head)=(add); \
418  } \
419  (add)->next=NULL; \
420 } while (0)
421 
422 #define LL_DELETE_VS2008(head,del) \
423  LL_DELETE2_VS2008(head,del,next)
424 
425 #define LL_DELETE2_VS2008(head,del,next) \
426 do { \
427  if ((head) == (del)) { \
428  (head)=(head)->next; \
429  } else { \
430  char *_tmp = (char*)(head); \
431  while ((head)->next && ((head)->next != (del))) { \
432  head = (head)->next; \
433  } \
434  if ((head)->next) { \
435  (head)->next = ((del)->next); \
436  } \
437  { \
438  char **_head_alias = (char**)&(head); \
439  *_head_alias = _tmp; \
440  } \
441  } \
442 } while (0)
443 #ifdef NO_DECLTYPE
444 #undef LL_APPEND
445 #define LL_APPEND LL_APPEND_VS2008
446 #undef LL_DELETE
447 #define LL_DELETE LL_DELETE_VS2008
448 #undef LL_DELETE2
449 #define LL_DELETE2 LL_DELETE2_VS2008
450 #undef LL_APPEND2
451 #define LL_APPEND2 LL_APPEND2_VS2008
452 #undef LL_CONCAT /* no LL_CONCAT_VS2008 */
453 #undef DL_CONCAT /* no DL_CONCAT_VS2008 */
454 #endif
455 /* end VS2008 replacements */
456 
458 #define LL_COUNT(head,el,counter) \
459  LL_COUNT2(head,el,counter,next) \
460 
461 
462 #define LL_COUNT2(head,el,counter,next) \
463 { \
464  counter = 0; \
465  LL_FOREACH2(head,el,next){ ++counter; } \
466 }
467 
469 #define LL_FOREACH(head,el) \
470  LL_FOREACH2(head,el,next)
471 
473 #define LL_FOREACH2(head,el,next) \
474  for(el=head;el;el=(el)->next)
475 
480 #define LL_FOREACH_SAFE(head,el,tmp) \
481  LL_FOREACH_SAFE2(head,el,tmp,next)
482 
484 #define LL_FOREACH_SAFE2(head,el,tmp,next) \
485  for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
486 
488 #define LL_SEARCH_SCALAR(head,out,field,val) \
489  LL_SEARCH_SCALAR2(head,out,field,val,next)
490 
492 #define LL_SEARCH_SCALAR2(head,out,field,val,next) \
493 do { \
494  LL_FOREACH2(head,out,next) { \
495  if ((out)->field == (val)) break; \
496  } \
497 } while(0)
498 
500 #define LL_SEARCH(head,out,elt,cmp) \
501  LL_SEARCH2(head,out,elt,cmp,next)
502 
504 #define LL_SEARCH2(head,out,elt,cmp,next) \
505 do { \
506  LL_FOREACH2(head,out,next) { \
507  if ((cmp(out,elt))==0) break; \
508  } \
509 } while(0)
510 
512 #define LL_REPLACE_ELEM(head, el, add) \
513 do { \
514  LDECLTYPE(head) _tmp; \
515  assert(head != NULL); \
516  assert(el != NULL); \
517  assert(add != NULL); \
518  (add)->next = (el)->next; \
519  if ((head) == (el)) { \
520  (head) = (add); \
521  } else { \
522  _tmp = head; \
523  while (_tmp->next && (_tmp->next != (el))) { \
524  _tmp = _tmp->next; \
525  } \
526  if (_tmp->next) { \
527  _tmp->next = (add); \
528  } \
529  } \
530 } while (0)
531 
533 #define LL_PREPEND_ELEM(head, el, add) \
534 do { \
535  LDECLTYPE(head) _tmp; \
536  assert(head != NULL); \
537  assert(el != NULL); \
538  assert(add != NULL); \
539  (add)->next = (el); \
540  if ((head) == (el)) { \
541  (head) = (add); \
542  } else { \
543  _tmp = head; \
544  while (_tmp->next && (_tmp->next != (el))) { \
545  _tmp = _tmp->next; \
546  } \
547  if (_tmp->next) { \
548  _tmp->next = (add); \
549  } \
550  } \
551 } while (0)
552 
559 #define DL_PREPEND(head,add) \
560  DL_PREPEND2(head,add,prev,next)
561 
563 #define DL_PREPEND2(head,add,prev,next) \
564 do { \
565  (add)->next = head; \
566  if (head) { \
567  (add)->prev = (head)->prev; \
568  (head)->prev = (add); \
569  } else { \
570  (add)->prev = (add); \
571  } \
572  (head) = (add); \
573 } while (0)
574 
576 #define DL_APPEND(head,add) \
577  DL_APPEND2(head,add,prev,next)
578 
580 #define DL_APPEND2(head,add,prev,next) \
581 do { \
582  if (head) { \
583  (add)->prev = (head)->prev; \
584  (head)->prev->next = (add); \
585  (head)->prev = (add); \
586  (add)->next = NULL; \
587  } else { \
588  (head)=(add); \
589  (head)->prev = (head); \
590  (head)->next = NULL; \
591  } \
592 } while (0)
593 
595 #define DL_CONCAT(head1,head2) \
596  DL_CONCAT2(head1,head2,prev,next)
597 
599 #define DL_CONCAT2(head1,head2,prev,next) \
600 do { \
601  LDECLTYPE(head1) _tmp; \
602  if (head2) { \
603  if (head1) { \
604  _tmp = (head2)->prev; \
605  (head2)->prev = (head1)->prev; \
606  (head1)->prev->next = (head2); \
607  (head1)->prev = _tmp; \
608  } else { \
609  (head1)=(head2); \
610  } \
611  } \
612 } while (0)
613 
615 #define DL_DELETE(head,del) \
616  DL_DELETE2(head,del,prev,next)
617 
619 #define DL_DELETE2(head,del,prev,next) \
620 do { \
621  assert((del)->prev != NULL); \
622  if ((del)->prev == (del)) { \
623  (head)=NULL; \
624  } else if ((del)==(head)) { \
625  (del)->next->prev = (del)->prev; \
626  (head) = (del)->next; \
627  } else { \
628  (del)->prev->next = (del)->next; \
629  if ((del)->next) { \
630  (del)->next->prev = (del)->prev; \
631  } else { \
632  (head)->prev = (del)->prev; \
633  } \
634  } \
635 } while (0)
636 
638 #define DL_COUNT(head,el,counter) \
639  DL_COUNT2(head,el,counter,next) \
640 
641 
642 #define DL_COUNT2(head,el,counter,next) \
643 { \
644  counter = 0; \
645  DL_FOREACH2(head,el,next){ ++counter; } \
646 }
647 
649 #define DL_FOREACH(head,el) \
650  DL_FOREACH2(head,el,next)
651 
653 #define DL_FOREACH2(head,el,next) \
654  for(el=head;el;el=(el)->next)
655 
660 #define DL_FOREACH_SAFE(head,el,tmp) \
661  DL_FOREACH_SAFE2(head,el,tmp,next)
662 
664 #define DL_FOREACH_SAFE2(head,el,tmp,next) \
665  for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
666 
671 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
672 
677 #define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2
678 
683 #define DL_SEARCH LL_SEARCH
684 
689 #define DL_SEARCH2 LL_SEARCH2
690 
692 #define DL_REPLACE_ELEM(head, el, add) \
693 do { \
694  assert(head != NULL); \
695  assert(el != NULL); \
696  assert(add != NULL); \
697  if ((head) == (el)) { \
698  (head) = (add); \
699  (add)->next = (el)->next; \
700  if ((el)->next == NULL) { \
701  (add)->prev = (add); \
702  } else { \
703  (add)->prev = (el)->prev; \
704  (add)->next->prev = (add); \
705  } \
706  } else { \
707  (add)->next = (el)->next; \
708  (add)->prev = (el)->prev; \
709  (add)->prev->next = (add); \
710  if ((el)->next == NULL) { \
711  (head)->prev = (add); \
712  } else { \
713  (add)->next->prev = (add); \
714  } \
715  } \
716 } while (0)
717 
719 #define DL_PREPEND_ELEM(head, el, add) \
720 do { \
721  assert(head != NULL); \
722  assert(el != NULL); \
723  assert(add != NULL); \
724  (add)->next = (el); \
725  (add)->prev = (el)->prev; \
726  (el)->prev = (add); \
727  if ((head) == (el)) { \
728  (head) = (add); \
729  } else { \
730  (add)->prev->next = (add); \
731  } \
732 } while (0)
733 
741 #define CDL_PREPEND(head,add) \
742  CDL_PREPEND2(head,add,prev,next)
743 
745 #define CDL_PREPEND2(head,add,prev,next) \
746 do { \
747  if (head) { \
748  (add)->prev = (head)->prev; \
749  (add)->next = (head); \
750  (head)->prev = (add); \
751  (add)->prev->next = (add); \
752  } else { \
753  (add)->prev = (add); \
754  (add)->next = (add); \
755  } \
756 (head)=(add); \
757 } while (0)
758 
760 #define CDL_DELETE(head,del) \
761  CDL_DELETE2(head,del,prev,next)
762 
764 #define CDL_DELETE2(head,del,prev,next) \
765 do { \
766  if ( ((head)==(del)) && ((head)->next == (head))) { \
767  (head) = 0L; \
768  } else { \
769  (del)->next->prev = (del)->prev; \
770  (del)->prev->next = (del)->next; \
771  if ((del) == (head)) (head)=(del)->next; \
772  } \
773 } while (0)
774 
776 #define CDL_COUNT(head,el,counter) \
777  CDL_COUNT2(head,el,counter,next) \
778 
779 
780 #define CDL_COUNT2(head, el, counter,next) \
781 { \
782  counter = 0; \
783  CDL_FOREACH2(head,el,next){ ++counter; } \
784 }
785 
787 #define CDL_FOREACH(head,el) \
788  CDL_FOREACH2(head,el,next)
789 
791 #define CDL_FOREACH2(head,el,next) \
792  for(el=head;el;el=((el)->next==head ? 0L : (el)->next))
793 
798 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \
799  CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
800 
802 #define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \
803  for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \
804  (el) && ((tmp2)=(el)->next, 1); \
805  ((el) = (((el)==(tmp1)) ? 0L : (tmp2))))
806 
808 #define CDL_SEARCH_SCALAR(head,out,field,val) \
809  CDL_SEARCH_SCALAR2(head,out,field,val,next)
810 
812 #define CDL_SEARCH_SCALAR2(head,out,field,val,next) \
813 do { \
814  CDL_FOREACH2(head,out,next) { \
815  if ((out)->field == (val)) break; \
816  } \
817 } while(0)
818 
820 #define CDL_SEARCH(head,out,elt,cmp) \
821  CDL_SEARCH2(head,out,elt,cmp,next)
822 
824 #define CDL_SEARCH2(head,out,elt,cmp,next) \
825 do { \
826  CDL_FOREACH2(head,out,next) { \
827  if ((cmp(out,elt))==0) break; \
828  } \
829 } while(0)
830 
832 #define CDL_REPLACE_ELEM(head, el, add) \
833 do { \
834  assert(head != NULL); \
835  assert(el != NULL); \
836  assert(add != NULL); \
837  if ((el)->next == (el)) { \
838  (add)->next = (add); \
839  (add)->prev = (add); \
840  (head) = (add); \
841  } else { \
842  (add)->next = (el)->next; \
843  (add)->prev = (el)->prev; \
844  (add)->next->prev = (add); \
845  (add)->prev->next = (add); \
846  if ((head) == (el)) { \
847  (head) = (add); \
848  } \
849  } \
850 } while (0)
851 
853 #define CDL_PREPEND_ELEM(head, el, add) \
854 do { \
855  assert(head != NULL); \
856  assert(el != NULL); \
857  assert(add != NULL); \
858  (add)->next = (el); \
859  (add)->prev = (el)->prev; \
860  (el)->prev = (add); \
861  (add)->prev->next = (add); \
862  if ((head) == (el)) { \
863  (head) = (add); \
864  } \
865 } while (0)
866 
868 #ifdef __cplusplus
869 }
870 #endif
871 
872 #endif /* UTLIST_H */
873 
assert.h
POSIX.1-2008 compliant version of the assert macro.