2 Copyright (c) 2007-2013, Troy D. Hanson http://troydhanson.github.com/uthash/
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions are met:
8 * Redistributions of source code must retain the above copyright
9 notice, this list of conditions and the following disclaimer.
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.
27 #define UTLIST_VERSION 1.9.8
32 * This file contains macros to manipulate singly and doubly-linked lists.
34 * 1. LL_ macros: singly-linked lists.
35 * 2. DL_ macros: doubly-linked lists.
36 * 3. CDL_ macros: circular doubly-linked lists.
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.
42 * ----------------.EXAMPLE -------------------------
45 * struct item *prev, *next;
48 * struct item *list = NULL:
52 * ... allocate and populate item ...
53 * DL_APPEND(list, item);
55 * --------------------------------------------------
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.
62 /* These macros use decltype or the earlier __typeof GNU extension.
63 As decltype is only available in newer compilers (VS2010 or gcc 4.3+
64 when compiling c++ code), this code uses whatever method is needed
65 or, for VS2008 where neither is available, uses casting workarounds. */
66 #ifdef _MSC_VER /* MS compiler */
67 #if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */
68 #define LDECLTYPE(x) decltype(x)
69 #else /* VS2008 or older (or VS2010 in C mode) */
71 #define LDECLTYPE(x) char*
73 #elif defined(__ICCARM__)
75 #define LDECLTYPE(x) char*
76 #else /* GNU, Sun and other compilers */
77 #define LDECLTYPE(x) __typeof(x)
80 /* for VS2008 we use some workarounds to get around the lack of decltype,
81 * namely, we always reassign our tmp variable to the list head if we need
82 * to dereference its prev/next pointers, and save/restore the real head.*/
84 #define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
85 #define _NEXT(elt,list,next) ((char*)((list)->next))
86 #define _NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }
87 /* #define _PREV(elt,list,prev) ((char*)((list)->prev)) */
88 #define _PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }
89 #define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
90 #define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
93 #define _NEXT(elt,list,next) ((elt)->next)
94 #define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to)
95 /* #define _PREV(elt,list,prev) ((elt)->prev) */
96 #define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to)
98 #define _CASTASGN(a,b) (a)=(b)
101 /******************************************************************************
102 * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort *
103 * Unwieldy variable names used here to avoid shadowing passed-in variables. *
104 *****************************************************************************/
105 #define LL_SORT(list, cmp) \
106 LL_SORT2(list, cmp, next)
108 #define LL_SORT2(list, cmp, next) \
110 LDECLTYPE(list) _ls_p; \
111 LDECLTYPE(list) _ls_q; \
112 LDECLTYPE(list) _ls_e; \
113 LDECLTYPE(list) _ls_tail; \
114 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
118 while (_ls_looping) { \
119 _CASTASGN(_ls_p,list); \
127 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
129 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
132 _ls_qsize = _ls_insize; \
133 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
134 if (_ls_psize == 0) { \
135 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
136 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
137 } else if (_ls_qsize == 0 || !_ls_q) { \
138 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
139 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
140 } else if (cmp(_ls_p,_ls_q) <= 0) { \
141 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
142 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
144 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
145 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
148 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
150 _CASTASGN(list,_ls_e); \
157 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
159 if (_ls_nmerges <= 1) { \
168 #define DL_SORT(list, cmp) \
169 DL_SORT2(list, cmp, prev, next)
171 #define DL_SORT2(list, cmp, prev, next) \
173 LDECLTYPE(list) _ls_p; \
174 LDECLTYPE(list) _ls_q; \
175 LDECLTYPE(list) _ls_e; \
176 LDECLTYPE(list) _ls_tail; \
177 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
181 while (_ls_looping) { \
182 _CASTASGN(_ls_p,list); \
190 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
192 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
195 _ls_qsize = _ls_insize; \
196 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
197 if (_ls_psize == 0) { \
198 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
199 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
200 } else if (_ls_qsize == 0 || !_ls_q) { \
201 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
202 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
203 } else if (cmp(_ls_p,_ls_q) <= 0) { \
204 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
205 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
207 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
208 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
211 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
213 _CASTASGN(list,_ls_e); \
215 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
220 _CASTASGN(list->prev, _ls_tail); \
221 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
222 if (_ls_nmerges <= 1) { \
230 #define CDL_SORT(list, cmp) \
231 CDL_SORT2(list, cmp, prev, next)
233 #define CDL_SORT2(list, cmp, prev, next) \
235 LDECLTYPE(list) _ls_p; \
236 LDECLTYPE(list) _ls_q; \
237 LDECLTYPE(list) _ls_e; \
238 LDECLTYPE(list) _ls_tail; \
239 LDECLTYPE(list) _ls_oldhead; \
240 LDECLTYPE(list) _tmp; \
241 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
245 while (_ls_looping) { \
246 _CASTASGN(_ls_p,list); \
247 _CASTASGN(_ls_oldhead,list); \
255 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
258 if (_NEXT(_ls_q,list,next) == _ls_oldhead) { \
261 _ls_q = _NEXT(_ls_q,list,next); \
266 _ls_qsize = _ls_insize; \
267 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
268 if (_ls_psize == 0) { \
269 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
270 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
271 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
272 } else if (_ls_qsize == 0 || !_ls_q) { \
273 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
274 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
275 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
276 } else if (cmp(_ls_p,_ls_q) <= 0) { \
277 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
278 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
279 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
281 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
282 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
283 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
286 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
288 _CASTASGN(list,_ls_e); \
290 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
295 _CASTASGN(list->prev,_ls_tail); \
296 _CASTASGN(_tmp,list); \
297 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp,next); _RS(list); \
298 if (_ls_nmerges <= 1) { \
306 /******************************************************************************
307 * singly linked list macros (non-circular) *
308 *****************************************************************************/
309 #define LL_PREPEND(head,add) \
310 LL_PREPEND2(head,add,next)
312 #define LL_PREPEND2(head,add,next) \
314 (add)->next = head; \
318 #define LL_CONCAT(head1,head2) \
319 LL_CONCAT2(head1,head2,next)
321 #define LL_CONCAT2(head1,head2,next) \
323 LDECLTYPE(head1) _tmp; \
326 while (_tmp->next) { _tmp = _tmp->next; } \
327 _tmp->next=(head2); \
333 #define LL_APPEND(head,add) \
334 LL_APPEND2(head,add,next)
336 #define LL_APPEND2(head,add,next) \
338 LDECLTYPE(head) _tmp; \
342 while (_tmp->next) { _tmp = _tmp->next; } \
349 #define LL_DELETE(head,del) \
350 LL_DELETE2(head,del,next)
352 #define LL_DELETE2(head,del,next) \
354 LDECLTYPE(head) _tmp; \
355 if ((head) == (del)) { \
356 (head)=(head)->next; \
359 while (_tmp->next && (_tmp->next != (del))) { \
363 _tmp->next = ((del)->next); \
368 /* Here are VS2008 replacements for LL_APPEND and LL_DELETE */
369 #define LL_APPEND_VS2008(head,add) \
370 LL_APPEND2_VS2008(head,add,next)
372 #define LL_APPEND2_VS2008(head,add,next) \
375 (add)->next = head; /* use add->next as a temp variable */ \
376 while ((add)->next->next) { (add)->next = (add)->next->next; } \
377 (add)->next->next=(add); \
384 #define LL_DELETE_VS2008(head,del) \
385 LL_DELETE2_VS2008(head,del,next)
387 #define LL_DELETE2_VS2008(head,del,next) \
389 if ((head) == (del)) { \
390 (head)=(head)->next; \
392 char *_tmp = (char*)(head); \
393 while ((head)->next && ((head)->next != (del))) { \
394 head = (head)->next; \
396 if ((head)->next) { \
397 (head)->next = ((del)->next); \
400 char **_head_alias = (char**)&(head); \
401 *_head_alias = _tmp; \
407 #define LL_APPEND LL_APPEND_VS2008
409 #define LL_DELETE LL_DELETE_VS2008
411 #define LL_DELETE2 LL_DELETE2_VS2008
413 #define LL_APPEND2 LL_APPEND2_VS2008
414 #undef LL_CONCAT /* no LL_CONCAT_VS2008 */
415 #undef DL_CONCAT /* no DL_CONCAT_VS2008 */
417 /* end VS2008 replacements */
419 #define LL_COUNT(head,el,counter) \
420 LL_COUNT2(head,el,counter,next) \
422 #define LL_COUNT2(head,el,counter,next) \
425 LL_FOREACH2(head,el,next){ ++counter; } \
428 #define LL_FOREACH(head,el) \
429 LL_FOREACH2(head,el,next)
431 #define LL_FOREACH2(head,el,next) \
432 for(el=head;el;el=(el)->next)
434 #define LL_FOREACH_SAFE(head,el,tmp) \
435 LL_FOREACH_SAFE2(head,el,tmp,next)
437 #define LL_FOREACH_SAFE2(head,el,tmp,next) \
438 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
440 #define LL_SEARCH_SCALAR(head,out,field,val) \
441 LL_SEARCH_SCALAR2(head,out,field,val,next)
443 #define LL_SEARCH_SCALAR2(head,out,field,val,next) \
445 LL_FOREACH2(head,out,next) { \
446 if ((out)->field == (val)) break; \
450 #define LL_SEARCH(head,out,elt,cmp) \
451 LL_SEARCH2(head,out,elt,cmp,next)
453 #define LL_SEARCH2(head,out,elt,cmp,next) \
455 LL_FOREACH2(head,out,next) { \
456 if ((cmp(out,elt))==0) break; \
460 #define LL_REPLACE_ELEM(head, el, add) \
462 LDECLTYPE(head) _tmp; \
463 assert(head != NULL); \
464 assert(el != NULL); \
465 assert(add != NULL); \
466 (add)->next = (el)->next; \
467 if ((head) == (el)) { \
471 while (_tmp->next && (_tmp->next != (el))) { \
475 _tmp->next = (add); \
480 #define LL_PREPEND_ELEM(head, el, add) \
482 LDECLTYPE(head) _tmp; \
483 assert(head != NULL); \
484 assert(el != NULL); \
485 assert(add != NULL); \
486 (add)->next = (el); \
487 if ((head) == (el)) { \
491 while (_tmp->next && (_tmp->next != (el))) { \
495 _tmp->next = (add); \
501 /******************************************************************************
502 * doubly linked list macros (non-circular) *
503 *****************************************************************************/
504 #define DL_PREPEND(head,add) \
505 DL_PREPEND2(head,add,prev,next)
507 #define DL_PREPEND2(head,add,prev,next) \
509 (add)->next = head; \
511 (add)->prev = (head)->prev; \
512 (head)->prev = (add); \
514 (add)->prev = (add); \
519 #define DL_APPEND(head,add) \
520 DL_APPEND2(head,add,prev,next)
522 #define DL_APPEND2(head,add,prev,next) \
525 (add)->prev = (head)->prev; \
526 (head)->prev->next = (add); \
527 (head)->prev = (add); \
528 (add)->next = NULL; \
531 (head)->prev = (head); \
532 (head)->next = NULL; \
536 #define DL_CONCAT(head1,head2) \
537 DL_CONCAT2(head1,head2,prev,next)
539 #define DL_CONCAT2(head1,head2,prev,next) \
541 LDECLTYPE(head1) _tmp; \
544 _tmp = (head2)->prev; \
545 (head2)->prev = (head1)->prev; \
546 (head1)->prev->next = (head2); \
547 (head1)->prev = _tmp; \
554 #define DL_DELETE(head,del) \
555 DL_DELETE2(head,del,prev,next)
557 #define DL_DELETE2(head,del,prev,next) \
559 assert((del)->prev != NULL); \
560 if ((del)->prev == (del)) { \
562 } else if ((del)==(head)) { \
563 (del)->next->prev = (del)->prev; \
564 (head) = (del)->next; \
566 (del)->prev->next = (del)->next; \
568 (del)->next->prev = (del)->prev; \
570 (head)->prev = (del)->prev; \
575 #define DL_COUNT(head,el,counter) \
576 DL_COUNT2(head,el,counter,next) \
578 #define DL_COUNT2(head,el,counter,next) \
581 DL_FOREACH2(head,el,next){ ++counter; } \
584 #define DL_FOREACH(head,el) \
585 DL_FOREACH2(head,el,next)
587 #define DL_FOREACH2(head,el,next) \
588 for(el=head;el;el=(el)->next)
590 /* this version is safe for deleting the elements during iteration */
591 #define DL_FOREACH_SAFE(head,el,tmp) \
592 DL_FOREACH_SAFE2(head,el,tmp,next)
594 #define DL_FOREACH_SAFE2(head,el,tmp,next) \
595 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
597 /* these are identical to their singly-linked list counterparts */
598 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
599 #define DL_SEARCH LL_SEARCH
600 #define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2
601 #define DL_SEARCH2 LL_SEARCH2
603 #define DL_REPLACE_ELEM(head, el, add) \
605 assert(head != NULL); \
606 assert(el != NULL); \
607 assert(add != NULL); \
608 if ((head) == (el)) { \
610 (add)->next = (el)->next; \
611 if ((el)->next == NULL) { \
612 (add)->prev = (add); \
614 (add)->prev = (el)->prev; \
615 (add)->next->prev = (add); \
618 (add)->next = (el)->next; \
619 (add)->prev = (el)->prev; \
620 (add)->prev->next = (add); \
621 if ((el)->next == NULL) { \
622 (head)->prev = (add); \
624 (add)->next->prev = (add); \
629 #define DL_PREPEND_ELEM(head, el, add) \
631 assert(head != NULL); \
632 assert(el != NULL); \
633 assert(add != NULL); \
634 (add)->next = (el); \
635 (add)->prev = (el)->prev; \
636 (el)->prev = (add); \
637 if ((head) == (el)) { \
640 (add)->prev->next = (add); \
645 /******************************************************************************
646 * circular doubly linked list macros *
647 *****************************************************************************/
648 #define CDL_PREPEND(head,add) \
649 CDL_PREPEND2(head,add,prev,next)
651 #define CDL_PREPEND2(head,add,prev,next) \
654 (add)->prev = (head)->prev; \
655 (add)->next = (head); \
656 (head)->prev = (add); \
657 (add)->prev->next = (add); \
659 (add)->prev = (add); \
660 (add)->next = (add); \
665 #define CDL_DELETE(head,del) \
666 CDL_DELETE2(head,del,prev,next)
668 #define CDL_DELETE2(head,del,prev,next) \
670 if ( ((head)==(del)) && ((head)->next == (head))) { \
673 (del)->next->prev = (del)->prev; \
674 (del)->prev->next = (del)->next; \
675 if ((del) == (head)) (head)=(del)->next; \
679 #define CDL_COUNT(head,el,counter) \
680 CDL_COUNT2(head,el,counter,next) \
682 #define CDL_COUNT2(head, el, counter,next) \
685 CDL_FOREACH2(head,el,next){ ++counter; } \
688 #define CDL_FOREACH(head,el) \
689 CDL_FOREACH2(head,el,next)
691 #define CDL_FOREACH2(head,el,next) \
692 for(el=head;el;el=((el)->next==head ? 0L : (el)->next))
694 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \
695 CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
697 #define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \
698 for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \
699 (el) && ((tmp2)=(el)->next, 1); \
700 ((el) = (((el)==(tmp1)) ? 0L : (tmp2))))
702 #define CDL_SEARCH_SCALAR(head,out,field,val) \
703 CDL_SEARCH_SCALAR2(head,out,field,val,next)
705 #define CDL_SEARCH_SCALAR2(head,out,field,val,next) \
707 CDL_FOREACH2(head,out,next) { \
708 if ((out)->field == (val)) break; \
712 #define CDL_SEARCH(head,out,elt,cmp) \
713 CDL_SEARCH2(head,out,elt,cmp,next)
715 #define CDL_SEARCH2(head,out,elt,cmp,next) \
717 CDL_FOREACH2(head,out,next) { \
718 if ((cmp(out,elt))==0) break; \
722 #define CDL_REPLACE_ELEM(head, el, add) \
724 assert(head != NULL); \
725 assert(el != NULL); \
726 assert(add != NULL); \
727 if ((el)->next == (el)) { \
728 (add)->next = (add); \
729 (add)->prev = (add); \
732 (add)->next = (el)->next; \
733 (add)->prev = (el)->prev; \
734 (add)->next->prev = (add); \
735 (add)->prev->next = (add); \
736 if ((head) == (el)) { \
742 #define CDL_PREPEND_ELEM(head, el, add) \
744 assert(head != NULL); \
745 assert(el != NULL); \
746 assert(add != NULL); \
747 (add)->next = (el); \
748 (add)->prev = (el)->prev; \
749 (el)->prev = (add); \
750 (add)->prev->next = (add); \
751 if ((head) == (el)) { \
756 #endif /* UTLIST_H */