2 Copyright (c) 2007-2010, Troy D. Hanson http://uthash.sourceforge.net
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.1
30 * This file contains macros to manipulate singly and doubly-linked lists.
32 * 1. LL_ macros: singly-linked lists.
33 * 2. DL_ macros: doubly-linked lists.
34 * 3. CDL_ macros: circular doubly-linked lists.
36 * To use singly-linked lists, your structure must have a "next" pointer.
37 * To use doubly-linked lists, your structure must "prev" and "next" pointers.
38 * Either way, the pointer to the head of the list must be initialized to NULL.
40 * ----------------.EXAMPLE -------------------------
43 * struct item *prev, *next;
46 * struct item *list = NULL:
50 * ... allocate and populate item ...
51 * DL_APPEND(list, item);
53 * --------------------------------------------------
55 * For doubly-linked lists, the append and delete macros are O(1)
56 * For singly-linked lists, append and delete are O(n) but prepend is O(1)
57 * The sort macro is O(n log(n)) for all types of single/double/circular lists.
60 /* These macros use decltype or the earlier __typeof GNU extension.
61 As decltype is only available in newer compilers (VS2010 or gcc 4.3+
62 when compiling c++ code), this code uses whatever method is needed
63 or, for VS2008 where neither is available, uses casting workarounds. */
64 #ifdef _MSC_VER /* MS compiler */
65 #if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */
66 #define LDECLTYPE(x) decltype(x)
67 #else /* VS2008 or older (or VS2010 in C mode) */
69 #define LDECLTYPE(x) char*
71 #else /* GNU, Sun and other compilers */
72 #define LDECLTYPE(x) __typeof(x)
75 /* for VS2008 we use some workarounds to get around the lack of decltype,
76 * namely, we always reassign our tmp variable to the list head if we need
77 * to dereference its prev/next pointers, and save/restore the real head.*/
79 #define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
80 #define _NEXT(elt,list) ((char*)((list)->next))
81 #define _NEXTASGN(elt,list,to) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }
82 #define _PREV(elt,list) ((char*)((list)->prev))
83 #define _PREVASGN(elt,list,to) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }
84 #define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
85 #define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
88 #define _NEXT(elt,list) ((elt)->next)
89 #define _NEXTASGN(elt,list,to) ((elt)->next)=(to)
90 #define _PREV(elt,list) ((elt)->prev)
91 #define _PREVASGN(elt,list,to) ((elt)->prev)=(to)
93 #define _CASTASGN(a,b) (a)=(b)
96 /******************************************************************************
97 * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort *
98 * Unwieldy variable names used here to avoid shadowing passed-in variables. *
99 *****************************************************************************/
100 #define LL_SORT(list, cmp) \
102 LDECLTYPE(list) _ls_p; \
103 LDECLTYPE(list) _ls_q; \
104 LDECLTYPE(list) _ls_e; \
105 LDECLTYPE(list) _ls_tail; \
106 LDECLTYPE(list) _ls_oldhead; \
107 LDECLTYPE(list) _tmp; \
108 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
112 while (_ls_looping) { \
113 _CASTASGN(_ls_p,list); \
114 _CASTASGN(_ls_oldhead,list); \
122 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
124 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \
127 _ls_qsize = _ls_insize; \
128 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
129 if (_ls_psize == 0) { \
130 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
131 } else if (_ls_qsize == 0 || !_ls_q) { \
132 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
133 } else if (cmp(_ls_p,_ls_q) <= 0) { \
134 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
136 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
139 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \
141 _CASTASGN(list,_ls_e); \
147 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \
148 if (_ls_nmerges <= 1) { \
153 } else _tmp=NULL; /* quiet gcc unused variable warning */ \
156 #define DL_SORT(list, cmp) \
158 LDECLTYPE(list) _ls_p; \
159 LDECLTYPE(list) _ls_q; \
160 LDECLTYPE(list) _ls_e; \
161 LDECLTYPE(list) _ls_tail; \
162 LDECLTYPE(list) _ls_oldhead; \
163 LDECLTYPE(list) _tmp; \
164 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
168 while (_ls_looping) { \
169 _CASTASGN(_ls_p,list); \
170 _CASTASGN(_ls_oldhead,list); \
178 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
180 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \
183 _ls_qsize = _ls_insize; \
184 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
185 if (_ls_psize == 0) { \
186 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
187 } else if (_ls_qsize == 0 || !_ls_q) { \
188 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
189 } else if (cmp(_ls_p,_ls_q) <= 0) { \
190 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
192 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
195 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \
197 _CASTASGN(list,_ls_e); \
199 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \
204 _CASTASGN(list->prev, _ls_tail); \
205 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \
206 if (_ls_nmerges <= 1) { \
211 } else _tmp=NULL; /* quiet gcc unused variable warning */ \
214 #define CDL_SORT(list, cmp) \
216 LDECLTYPE(list) _ls_p; \
217 LDECLTYPE(list) _ls_q; \
218 LDECLTYPE(list) _ls_e; \
219 LDECLTYPE(list) _ls_tail; \
220 LDECLTYPE(list) _ls_oldhead; \
221 LDECLTYPE(list) _tmp; \
222 LDECLTYPE(list) _tmp2; \
223 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
227 while (_ls_looping) { \
228 _CASTASGN(_ls_p,list); \
229 _CASTASGN(_ls_oldhead,list); \
237 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
240 if (_NEXT(_ls_q,list) == _ls_oldhead) { \
243 _ls_q = _NEXT(_ls_q,list); \
248 _ls_qsize = _ls_insize; \
249 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
250 if (_ls_psize == 0) { \
251 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
252 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
253 } else if (_ls_qsize == 0 || !_ls_q) { \
254 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
255 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
256 } else if (cmp(_ls_p,_ls_q) <= 0) { \
257 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
258 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
260 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
261 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
264 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \
266 _CASTASGN(list,_ls_e); \
268 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \
273 _CASTASGN(list->prev,_ls_tail); \
274 _CASTASGN(_tmp2,list); \
275 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp2); _RS(list); \
276 if (_ls_nmerges <= 1) { \
281 } else _tmp=NULL; /* quiet gcc unused variable warning */ \
284 /******************************************************************************
285 * singly linked list macros (non-circular) *
286 *****************************************************************************/
287 #define LL_PREPEND(head,add) \
289 (add)->next = head; \
293 #define LL_APPEND(head,add) \
295 LDECLTYPE(head) _tmp; \
299 while (_tmp->next) { _tmp = _tmp->next; } \
306 #define LL_DELETE(head,del) \
308 LDECLTYPE(head) _tmp; \
309 if ((head) == (del)) { \
310 (head)=(head)->next; \
313 while (_tmp->next && (_tmp->next != (del))) { \
317 _tmp->next = ((del)->next); \
322 /* Here are VS2008 replacements for LL_APPEND and LL_DELETE */
323 #define LL_APPEND_VS2008(head,add) \
326 (add)->next = head; /* use add->next as a temp variable */ \
327 while ((add)->next->next) { (add)->next = (add)->next->next; } \
328 (add)->next->next=(add); \
335 #define LL_DELETE_VS2008(head,del) \
337 if ((head) == (del)) { \
338 (head)=(head)->next; \
340 char *_tmp = (char*)(head); \
341 while (head->next && (head->next != (del))) { \
345 head->next = ((del)->next); \
348 char **_head_alias = (char**)&(head); \
349 *_head_alias = _tmp; \
355 #define LL_APPEND LL_APPEND_VS2008
357 #define LL_DELETE LL_DELETE_VS2008
359 /* end VS2008 replacements */
361 #define LL_FOREACH(head,el) \
362 for(el=head;el;el=el->next)
364 #define LL_FOREACH_SAFE(head,el,tmp) \
365 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
367 #define LL_SEARCH_SCALAR(head,out,field,val) \
369 LL_FOREACH(head,out) { \
370 if ((out)->field == (val)) break; \
374 #define LL_SEARCH(head,out,elt,cmp) \
376 LL_FOREACH(head,out) { \
377 if ((cmp(out,elt))==0) break; \
381 /******************************************************************************
382 * doubly linked list macros (non-circular) *
383 *****************************************************************************/
384 #define DL_PREPEND(head,add) \
386 (add)->next = head; \
388 (add)->prev = (head)->prev; \
389 (head)->prev = (add); \
391 (add)->prev = (add); \
396 #define DL_APPEND(head,add) \
399 (add)->prev = (head)->prev; \
400 (head)->prev->next = (add); \
401 (head)->prev = (add); \
402 (add)->next = NULL; \
405 (head)->prev = (head); \
406 (head)->next = NULL; \
410 #define DL_DELETE(head,del) \
412 if ((del)->prev == (del)) { \
414 } else if ((del)==(head)) { \
415 (del)->next->prev = (del)->prev; \
416 (head) = (del)->next; \
418 (del)->prev->next = (del)->next; \
420 (del)->next->prev = (del)->prev; \
422 (head)->prev = (del)->prev; \
428 #define DL_FOREACH(head,el) \
429 for(el=head;el;el=el->next)
431 /* this version is safe for deleting the elements during iteration */
432 #define DL_FOREACH_SAFE(head,el,tmp) \
433 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
435 /* these are identical to their singly-linked list counterparts */
436 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
437 #define DL_SEARCH LL_SEARCH
439 /******************************************************************************
440 * circular doubly linked list macros *
441 *****************************************************************************/
442 #define CDL_PREPEND(head,add) \
445 (add)->prev = (head)->prev; \
446 (add)->next = (head); \
447 (head)->prev = (add); \
448 (add)->prev->next = (add); \
450 (add)->prev = (add); \
451 (add)->next = (add); \
456 #define CDL_DELETE(head,del) \
458 if ( ((head)==(del)) && ((head)->next == (head))) { \
461 (del)->next->prev = (del)->prev; \
462 (del)->prev->next = (del)->next; \
463 if ((del) == (head)) (head)=(del)->next; \
467 #define CDL_FOREACH(head,el) \
468 for(el=head;el;el=(el->next==head ? 0L : el->next))
470 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \
471 for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \
472 (el) && ((tmp2)=(el)->next, 1); \
473 ((el) = (((el)==(tmp1)) ? 0L : (tmp2))))
475 #define CDL_SEARCH_SCALAR(head,out,field,val) \
477 CDL_FOREACH(head,out) { \
478 if ((out)->field == (val)) break; \
482 #define CDL_SEARCH(head,out,elt,cmp) \
484 CDL_FOREACH(head,out) { \
485 if ((cmp(out,elt))==0) break; \
489 #endif /* UTLIST_H */