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 #include <stddef.h>
43 
44 #include <assert.h>
45 
46 #ifdef __cplusplus
47 extern "C" {
48 #endif
49 
50 /*
51  * This file contains macros to manipulate singly and doubly-linked lists.
52  *
53  * 1. LL_ macros: singly-linked lists.
54  * 2. DL_ macros: doubly-linked lists.
55  * 3. CDL_ macros: circular doubly-linked lists.
56  *
57  * To use singly-linked lists, your structure must have a "next" pointer.
58  * To use doubly-linked lists, your structure must "prev" and "next" pointers.
59  * Either way, the pointer to the head of the list must be initialized to NULL.
60  *
61  * ----------------.EXAMPLE -------------------------
62  * struct item {
63  * int id;
64  * struct item *prev, *next;
65  * }
66  *
67  * struct item *list = NULL:
68  *
69  * int main() {
70  * struct item *item;
71  * ... allocate and populate item ...
72  * DL_APPEND(list, item);
73  * }
74  * --------------------------------------------------
75  *
76  * For doubly-linked lists, the append and delete macros are O(1)
77  * For singly-linked lists, append and delete are O(n) but prepend is O(1)
78  * The sort macro is O(n log(n)) for all types of single/double/circular lists.
79  */
80 
94 #ifdef _MSC_VER /* MS compiler */
95 #if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */
96 #define LDECLTYPE(x) decltype(x)
97 #else /* VS2008 or older (or VS2010 in C mode) */
98 #define NO_DECLTYPE
99 #define LDECLTYPE(x) char*
100 #endif
101 #elif defined(__ICCARM__)
102 #define NO_DECLTYPE
103 #define LDECLTYPE(x) char*
104 #else /* GNU, Sun and other compilers */
105 #define LDECLTYPE(x) __typeof(x)
106 #endif
107 
108 #ifdef NO_DECLTYPE
109 #define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
110 #define _NEXT(elt,list,next) ((char*)((list)->next))
111 #define _NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }
112 /* #define _PREV(elt,list,prev) ((char*)((list)->prev)) */
113 #define _PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }
114 #define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
115 #define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
116 #else
117 #define _SV(elt,list)
118 #define _NEXT(elt,list,next) ((elt)->next)
119 #define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to)
120 /* #define _PREV(elt,list,prev) ((elt)->prev) */
121 #define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to)
122 #define _RS(list)
123 #define _CASTASGN(a,b) (a)=(b)
124 #endif
134 #define LL_SORT(list, cmp) \
135  LL_SORT2(list, cmp, next)
136 
137 #define LL_SORT2(list, cmp, next) \
138 do { \
139  LDECLTYPE(list) _ls_p; \
140  LDECLTYPE(list) _ls_q; \
141  LDECLTYPE(list) _ls_e; \
142  LDECLTYPE(list) _ls_tail; \
143  int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
144  if (list) { \
145  _ls_insize = 1; \
146  _ls_looping = 1; \
147  while (_ls_looping) { \
148  _CASTASGN(_ls_p,list); \
149  list = NULL; \
150  _ls_tail = NULL; \
151  _ls_nmerges = 0; \
152  while (_ls_p) { \
153  _ls_nmerges++; \
154  _ls_q = _ls_p; \
155  _ls_psize = 0; \
156  for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
157  _ls_psize++; \
158  _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
159  if (!_ls_q) break; \
160  } \
161  _ls_qsize = _ls_insize; \
162  while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
163  if (_ls_psize == 0) { \
164  _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
165  _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
166  } else if (_ls_qsize == 0 || !_ls_q) { \
167  _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
168  _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
169  } else if (cmp(_ls_p,_ls_q) <= 0) { \
170  _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
171  _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
172  } else { \
173  _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
174  _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
175  } \
176  if (_ls_tail) { \
177  _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
178  } else { \
179  _CASTASGN(list,_ls_e); \
180  } \
181  _ls_tail = _ls_e; \
182  } \
183  _ls_p = _ls_q; \
184  } \
185  if (_ls_tail) { \
186  _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
187  } \
188  if (_ls_nmerges <= 1) { \
189  _ls_looping=0; \
190  } \
191  _ls_insize *= 2; \
192  } \
193  } \
194 } while (0)
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)
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 
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)
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 
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)
740 #define CDL_PREPEND(head,add) \
741  CDL_PREPEND2(head,add,prev,next)
742 
744 #define CDL_PREPEND2(head,add,prev,next) \
745 do { \
746  if (head) { \
747  (add)->prev = (head)->prev; \
748  (add)->next = (head); \
749  (head)->prev = (add); \
750  (add)->prev->next = (add); \
751  } else { \
752  (add)->prev = (add); \
753  (add)->next = (add); \
754  } \
755 (head)=(add); \
756 } while (0)
757 
759 #define CDL_DELETE(head,del) \
760  CDL_DELETE2(head,del,prev,next)
761 
763 #define CDL_DELETE2(head,del,prev,next) \
764 do { \
765  if ( ((head)==(del)) && ((head)->next == (head))) { \
766  (head) = 0L; \
767  } else { \
768  (del)->next->prev = (del)->prev; \
769  (del)->prev->next = (del)->next; \
770  if ((del) == (head)) (head)=(del)->next; \
771  } \
772 } while (0)
773 
775 #define CDL_COUNT(head,el,counter) \
776  CDL_COUNT2(head,el,counter,next) \
777 
779 #define CDL_COUNT2(head, el, counter,next) \
780 { \
781  counter = 0; \
782  CDL_FOREACH2(head,el,next){ ++counter; } \
783 }
784 
786 #define CDL_FOREACH(head,el) \
787  CDL_FOREACH2(head,el,next)
788 
790 #define CDL_FOREACH2(head,el,next) \
791  for(el=head;el;el=((el)->next==head ? 0L : (el)->next))
792 
797 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \
798  CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
799 
801 #define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \
802  for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \
803  (el) && ((tmp2)=(el)->next, 1); \
804  ((el) = (((el)==(tmp1)) ? 0L : (tmp2))))
805 
807 #define CDL_SEARCH_SCALAR(head,out,field,val) \
808  CDL_SEARCH_SCALAR2(head,out,field,val,next)
809 
811 #define CDL_SEARCH_SCALAR2(head,out,field,val,next) \
812 do { \
813  CDL_FOREACH2(head,out,next) { \
814  if ((out)->field == (val)) break; \
815  } \
816 } while(0)
817 
819 #define CDL_SEARCH(head,out,elt,cmp) \
820  CDL_SEARCH2(head,out,elt,cmp,next)
821 
823 #define CDL_SEARCH2(head,out,elt,cmp,next) \
824 do { \
825  CDL_FOREACH2(head,out,next) { \
826  if ((cmp(out,elt))==0) break; \
827  } \
828 } while(0)
829 
831 #define CDL_REPLACE_ELEM(head, el, add) \
832 do { \
833  assert(head != NULL); \
834  assert(el != NULL); \
835  assert(add != NULL); \
836  if ((el)->next == (el)) { \
837  (add)->next = (add); \
838  (add)->prev = (add); \
839  (head) = (add); \
840  } else { \
841  (add)->next = (el)->next; \
842  (add)->prev = (el)->prev; \
843  (add)->next->prev = (add); \
844  (add)->prev->next = (add); \
845  if ((head) == (el)) { \
846  (head) = (add); \
847  } \
848  } \
849 } while (0)
850 
852 #define CDL_PREPEND_ELEM(head, el, add) \
853 do { \
854  assert(head != NULL); \
855  assert(el != NULL); \
856  assert(add != NULL); \
857  (add)->next = (el); \
858  (add)->prev = (el)->prev; \
859  (el)->prev = (add); \
860  (add)->prev->next = (add); \
861  if ((head) == (el)) { \
862  (head) = (add); \
863  } \
864 } while (0)
867 #ifdef __cplusplus
868 }
869 #endif
870 
871 #endif /* UTLIST_H */
assert.h
POSIX.1-2008 compliant version of the assert macro.