1262395Sbapt/* 2262395SbaptCopyright (c) 2007-2013, Troy D. Hanson http://troydhanson.github.com/uthash/ 3262395SbaptAll rights reserved. 4262395Sbapt 5262395SbaptRedistribution and use in source and binary forms, with or without 6262395Sbaptmodification, are permitted provided that the following conditions are met: 7262395Sbapt 8262395Sbapt * Redistributions of source code must retain the above copyright 9262395Sbapt notice, this list of conditions and the following disclaimer. 10262395Sbapt 11262395SbaptTHIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 12262395SbaptIS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 13262395SbaptTO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 14262395SbaptPARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 15262395SbaptOR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 16262395SbaptEXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 17262395SbaptPROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 18262395SbaptPROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 19262395SbaptLIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 20262395SbaptNEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 21262395SbaptSOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 22262395Sbapt*/ 23262395Sbapt 24262395Sbapt#ifndef UTLIST_H 25262395Sbapt#define UTLIST_H 26262395Sbapt 27262395Sbapt#define UTLIST_VERSION 1.9.8 28262395Sbapt 29262395Sbapt#include <assert.h> 30262395Sbapt 31262395Sbapt/* 32262395Sbapt * This file contains macros to manipulate singly and doubly-linked lists. 33262395Sbapt * 34262395Sbapt * 1. LL_ macros: singly-linked lists. 35262395Sbapt * 2. DL_ macros: doubly-linked lists. 36262395Sbapt * 3. CDL_ macros: circular doubly-linked lists. 37262395Sbapt * 38262395Sbapt * To use singly-linked lists, your structure must have a "next" pointer. 39262395Sbapt * To use doubly-linked lists, your structure must "prev" and "next" pointers. 40262395Sbapt * Either way, the pointer to the head of the list must be initialized to NULL. 41262395Sbapt * 42262395Sbapt * ----------------.EXAMPLE ------------------------- 43262395Sbapt * struct item { 44262395Sbapt * int id; 45262395Sbapt * struct item *prev, *next; 46262395Sbapt * } 47262395Sbapt * 48262395Sbapt * struct item *list = NULL: 49262395Sbapt * 50262395Sbapt * int main() { 51262395Sbapt * struct item *item; 52262395Sbapt * ... allocate and populate item ... 53262395Sbapt * DL_APPEND(list, item); 54262395Sbapt * } 55262395Sbapt * -------------------------------------------------- 56262395Sbapt * 57262395Sbapt * For doubly-linked lists, the append and delete macros are O(1) 58262395Sbapt * For singly-linked lists, append and delete are O(n) but prepend is O(1) 59262395Sbapt * The sort macro is O(n log(n)) for all types of single/double/circular lists. 60262395Sbapt */ 61262395Sbapt 62262395Sbapt/* These macros use decltype or the earlier __typeof GNU extension. 63262395Sbapt As decltype is only available in newer compilers (VS2010 or gcc 4.3+ 64262395Sbapt when compiling c++ code), this code uses whatever method is needed 65262395Sbapt or, for VS2008 where neither is available, uses casting workarounds. */ 66262395Sbapt#ifdef _MSC_VER /* MS compiler */ 67262395Sbapt#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ 68262395Sbapt#define LDECLTYPE(x) decltype(x) 69262395Sbapt#else /* VS2008 or older (or VS2010 in C mode) */ 70262395Sbapt#define NO_DECLTYPE 71262395Sbapt#define LDECLTYPE(x) char* 72262395Sbapt#endif 73262395Sbapt#elif defined(__ICCARM__) 74262395Sbapt#define NO_DECLTYPE 75262395Sbapt#define LDECLTYPE(x) char* 76262395Sbapt#else /* GNU, Sun and other compilers */ 77262395Sbapt#define LDECLTYPE(x) __typeof(x) 78262395Sbapt#endif 79262395Sbapt 80262395Sbapt/* for VS2008 we use some workarounds to get around the lack of decltype, 81262395Sbapt * namely, we always reassign our tmp variable to the list head if we need 82262395Sbapt * to dereference its prev/next pointers, and save/restore the real head.*/ 83262395Sbapt#ifdef NO_DECLTYPE 84262395Sbapt#define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); } 85262395Sbapt#define _NEXT(elt,list,next) ((char*)((list)->next)) 86262395Sbapt#define _NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); } 87262395Sbapt/* #define _PREV(elt,list,prev) ((char*)((list)->prev)) */ 88262395Sbapt#define _PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); } 89262395Sbapt#define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; } 90262395Sbapt#define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); } 91262395Sbapt#else 92262395Sbapt#define _SV(elt,list) 93262395Sbapt#define _NEXT(elt,list,next) ((elt)->next) 94262395Sbapt#define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to) 95262395Sbapt/* #define _PREV(elt,list,prev) ((elt)->prev) */ 96262395Sbapt#define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to) 97262395Sbapt#define _RS(list) 98262395Sbapt#define _CASTASGN(a,b) (a)=(b) 99262395Sbapt#endif 100262395Sbapt 101262395Sbapt/****************************************************************************** 102262395Sbapt * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort * 103262395Sbapt * Unwieldy variable names used here to avoid shadowing passed-in variables. * 104262395Sbapt *****************************************************************************/ 105262395Sbapt#define LL_SORT(list, cmp) \ 106262395Sbapt LL_SORT2(list, cmp, next) 107262395Sbapt 108262395Sbapt#define LL_SORT2(list, cmp, next) \ 109262395Sbaptdo { \ 110262395Sbapt LDECLTYPE(list) _ls_p; \ 111262395Sbapt LDECLTYPE(list) _ls_q; \ 112262395Sbapt LDECLTYPE(list) _ls_e; \ 113262395Sbapt LDECLTYPE(list) _ls_tail; \ 114262395Sbapt int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 115262395Sbapt if (list) { \ 116262395Sbapt _ls_insize = 1; \ 117262395Sbapt _ls_looping = 1; \ 118262395Sbapt while (_ls_looping) { \ 119262395Sbapt _CASTASGN(_ls_p,list); \ 120262395Sbapt list = NULL; \ 121262395Sbapt _ls_tail = NULL; \ 122262395Sbapt _ls_nmerges = 0; \ 123262395Sbapt while (_ls_p) { \ 124262395Sbapt _ls_nmerges++; \ 125262395Sbapt _ls_q = _ls_p; \ 126262395Sbapt _ls_psize = 0; \ 127262395Sbapt for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 128262395Sbapt _ls_psize++; \ 129262395Sbapt _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \ 130262395Sbapt if (!_ls_q) break; \ 131262395Sbapt } \ 132262395Sbapt _ls_qsize = _ls_insize; \ 133262395Sbapt while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ 134262395Sbapt if (_ls_psize == 0) { \ 135262395Sbapt _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 136262395Sbapt _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 137262395Sbapt } else if (_ls_qsize == 0 || !_ls_q) { \ 138262395Sbapt _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 139262395Sbapt _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 140262395Sbapt } else if (cmp(_ls_p,_ls_q) <= 0) { \ 141262395Sbapt _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 142262395Sbapt _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 143262395Sbapt } else { \ 144262395Sbapt _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 145262395Sbapt _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 146262395Sbapt } \ 147262395Sbapt if (_ls_tail) { \ 148262395Sbapt _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ 149262395Sbapt } else { \ 150262395Sbapt _CASTASGN(list,_ls_e); \ 151262395Sbapt } \ 152262395Sbapt _ls_tail = _ls_e; \ 153262395Sbapt } \ 154262395Sbapt _ls_p = _ls_q; \ 155262395Sbapt } \ 156262395Sbapt if (_ls_tail) { \ 157262395Sbapt _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \ 158262395Sbapt } \ 159262395Sbapt if (_ls_nmerges <= 1) { \ 160262395Sbapt _ls_looping=0; \ 161262395Sbapt } \ 162262395Sbapt _ls_insize *= 2; \ 163262395Sbapt } \ 164262395Sbapt } \ 165262395Sbapt} while (0) 166262395Sbapt 167262395Sbapt 168262395Sbapt#define DL_SORT(list, cmp) \ 169262395Sbapt DL_SORT2(list, cmp, prev, next) 170262395Sbapt 171262395Sbapt#define DL_SORT2(list, cmp, prev, next) \ 172262395Sbaptdo { \ 173262395Sbapt LDECLTYPE(list) _ls_p; \ 174262395Sbapt LDECLTYPE(list) _ls_q; \ 175262395Sbapt LDECLTYPE(list) _ls_e; \ 176262395Sbapt LDECLTYPE(list) _ls_tail; \ 177262395Sbapt int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 178262395Sbapt if (list) { \ 179262395Sbapt _ls_insize = 1; \ 180262395Sbapt _ls_looping = 1; \ 181262395Sbapt while (_ls_looping) { \ 182262395Sbapt _CASTASGN(_ls_p,list); \ 183262395Sbapt list = NULL; \ 184262395Sbapt _ls_tail = NULL; \ 185262395Sbapt _ls_nmerges = 0; \ 186262395Sbapt while (_ls_p) { \ 187262395Sbapt _ls_nmerges++; \ 188262395Sbapt _ls_q = _ls_p; \ 189262395Sbapt _ls_psize = 0; \ 190262395Sbapt for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 191262395Sbapt _ls_psize++; \ 192262395Sbapt _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \ 193262395Sbapt if (!_ls_q) break; \ 194262395Sbapt } \ 195262395Sbapt _ls_qsize = _ls_insize; \ 196262395Sbapt while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ 197262395Sbapt if (_ls_psize == 0) { \ 198262395Sbapt _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 199262395Sbapt _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 200262395Sbapt } else if (_ls_qsize == 0 || !_ls_q) { \ 201262395Sbapt _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 202262395Sbapt _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 203262395Sbapt } else if (cmp(_ls_p,_ls_q) <= 0) { \ 204262395Sbapt _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 205262395Sbapt _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 206262395Sbapt } else { \ 207262395Sbapt _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 208262395Sbapt _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 209262395Sbapt } \ 210262395Sbapt if (_ls_tail) { \ 211262395Sbapt _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ 212262395Sbapt } else { \ 213262395Sbapt _CASTASGN(list,_ls_e); \ 214262395Sbapt } \ 215262395Sbapt _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \ 216262395Sbapt _ls_tail = _ls_e; \ 217262395Sbapt } \ 218262395Sbapt _ls_p = _ls_q; \ 219262395Sbapt } \ 220262395Sbapt _CASTASGN(list->prev, _ls_tail); \ 221262395Sbapt _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \ 222262395Sbapt if (_ls_nmerges <= 1) { \ 223262395Sbapt _ls_looping=0; \ 224262395Sbapt } \ 225262395Sbapt _ls_insize *= 2; \ 226262395Sbapt } \ 227262395Sbapt } \ 228262395Sbapt} while (0) 229262395Sbapt 230262395Sbapt#define CDL_SORT(list, cmp) \ 231262395Sbapt CDL_SORT2(list, cmp, prev, next) 232262395Sbapt 233262395Sbapt#define CDL_SORT2(list, cmp, prev, next) \ 234262395Sbaptdo { \ 235262395Sbapt LDECLTYPE(list) _ls_p; \ 236262395Sbapt LDECLTYPE(list) _ls_q; \ 237262395Sbapt LDECLTYPE(list) _ls_e; \ 238262395Sbapt LDECLTYPE(list) _ls_tail; \ 239262395Sbapt LDECLTYPE(list) _ls_oldhead; \ 240262395Sbapt LDECLTYPE(list) _tmp; \ 241262395Sbapt int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 242262395Sbapt if (list) { \ 243262395Sbapt _ls_insize = 1; \ 244262395Sbapt _ls_looping = 1; \ 245262395Sbapt while (_ls_looping) { \ 246262395Sbapt _CASTASGN(_ls_p,list); \ 247262395Sbapt _CASTASGN(_ls_oldhead,list); \ 248262395Sbapt list = NULL; \ 249262395Sbapt _ls_tail = NULL; \ 250262395Sbapt _ls_nmerges = 0; \ 251262395Sbapt while (_ls_p) { \ 252262395Sbapt _ls_nmerges++; \ 253262395Sbapt _ls_q = _ls_p; \ 254262395Sbapt _ls_psize = 0; \ 255262395Sbapt for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 256262395Sbapt _ls_psize++; \ 257262395Sbapt _SV(_ls_q,list); \ 258262395Sbapt if (_NEXT(_ls_q,list,next) == _ls_oldhead) { \ 259262395Sbapt _ls_q = NULL; \ 260262395Sbapt } else { \ 261262395Sbapt _ls_q = _NEXT(_ls_q,list,next); \ 262262395Sbapt } \ 263262395Sbapt _RS(list); \ 264262395Sbapt if (!_ls_q) break; \ 265262395Sbapt } \ 266262395Sbapt _ls_qsize = _ls_insize; \ 267262395Sbapt while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ 268262395Sbapt if (_ls_psize == 0) { \ 269262395Sbapt _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 270262395Sbapt _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 271262395Sbapt if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ 272262395Sbapt } else if (_ls_qsize == 0 || !_ls_q) { \ 273262395Sbapt _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 274262395Sbapt _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 275262395Sbapt if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ 276262395Sbapt } else if (cmp(_ls_p,_ls_q) <= 0) { \ 277262395Sbapt _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 278262395Sbapt _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 279262395Sbapt if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ 280262395Sbapt } else { \ 281262395Sbapt _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 282262395Sbapt _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 283262395Sbapt if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ 284262395Sbapt } \ 285262395Sbapt if (_ls_tail) { \ 286262395Sbapt _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ 287262395Sbapt } else { \ 288262395Sbapt _CASTASGN(list,_ls_e); \ 289262395Sbapt } \ 290262395Sbapt _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \ 291262395Sbapt _ls_tail = _ls_e; \ 292262395Sbapt } \ 293262395Sbapt _ls_p = _ls_q; \ 294262395Sbapt } \ 295262395Sbapt _CASTASGN(list->prev,_ls_tail); \ 296262395Sbapt _CASTASGN(_tmp,list); \ 297262395Sbapt _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp,next); _RS(list); \ 298262395Sbapt if (_ls_nmerges <= 1) { \ 299262395Sbapt _ls_looping=0; \ 300262395Sbapt } \ 301262395Sbapt _ls_insize *= 2; \ 302262395Sbapt } \ 303262395Sbapt } \ 304262395Sbapt} while (0) 305262395Sbapt 306262395Sbapt/****************************************************************************** 307262395Sbapt * singly linked list macros (non-circular) * 308262395Sbapt *****************************************************************************/ 309262395Sbapt#define LL_PREPEND(head,add) \ 310262395Sbapt LL_PREPEND2(head,add,next) 311262395Sbapt 312262395Sbapt#define LL_PREPEND2(head,add,next) \ 313262395Sbaptdo { \ 314262395Sbapt (add)->next = head; \ 315262395Sbapt head = add; \ 316262395Sbapt} while (0) 317262395Sbapt 318262395Sbapt#define LL_CONCAT(head1,head2) \ 319262395Sbapt LL_CONCAT2(head1,head2,next) 320262395Sbapt 321262395Sbapt#define LL_CONCAT2(head1,head2,next) \ 322262395Sbaptdo { \ 323262395Sbapt LDECLTYPE(head1) _tmp; \ 324262395Sbapt if (head1) { \ 325262395Sbapt _tmp = head1; \ 326262395Sbapt while (_tmp->next) { _tmp = _tmp->next; } \ 327262395Sbapt _tmp->next=(head2); \ 328262395Sbapt } else { \ 329262395Sbapt (head1)=(head2); \ 330262395Sbapt } \ 331262395Sbapt} while (0) 332262395Sbapt 333262395Sbapt#define LL_APPEND(head,add) \ 334262395Sbapt LL_APPEND2(head,add,next) 335262395Sbapt 336262395Sbapt#define LL_APPEND2(head,add,next) \ 337262395Sbaptdo { \ 338262395Sbapt LDECLTYPE(head) _tmp; \ 339262395Sbapt (add)->next=NULL; \ 340262395Sbapt if (head) { \ 341262395Sbapt _tmp = head; \ 342262395Sbapt while (_tmp->next) { _tmp = _tmp->next; } \ 343262395Sbapt _tmp->next=(add); \ 344262395Sbapt } else { \ 345262395Sbapt (head)=(add); \ 346262395Sbapt } \ 347262395Sbapt} while (0) 348262395Sbapt 349262395Sbapt#define LL_DELETE(head,del) \ 350262395Sbapt LL_DELETE2(head,del,next) 351262395Sbapt 352262395Sbapt#define LL_DELETE2(head,del,next) \ 353262395Sbaptdo { \ 354262395Sbapt LDECLTYPE(head) _tmp; \ 355262395Sbapt if ((head) == (del)) { \ 356262395Sbapt (head)=(head)->next; \ 357262395Sbapt } else { \ 358262395Sbapt _tmp = head; \ 359262395Sbapt while (_tmp->next && (_tmp->next != (del))) { \ 360262395Sbapt _tmp = _tmp->next; \ 361262395Sbapt } \ 362262395Sbapt if (_tmp->next) { \ 363262395Sbapt _tmp->next = ((del)->next); \ 364262395Sbapt } \ 365262395Sbapt } \ 366262395Sbapt} while (0) 367262395Sbapt 368262395Sbapt/* Here are VS2008 replacements for LL_APPEND and LL_DELETE */ 369262395Sbapt#define LL_APPEND_VS2008(head,add) \ 370262395Sbapt LL_APPEND2_VS2008(head,add,next) 371262395Sbapt 372262395Sbapt#define LL_APPEND2_VS2008(head,add,next) \ 373262395Sbaptdo { \ 374262395Sbapt if (head) { \ 375262395Sbapt (add)->next = head; /* use add->next as a temp variable */ \ 376262395Sbapt while ((add)->next->next) { (add)->next = (add)->next->next; } \ 377262395Sbapt (add)->next->next=(add); \ 378262395Sbapt } else { \ 379262395Sbapt (head)=(add); \ 380262395Sbapt } \ 381262395Sbapt (add)->next=NULL; \ 382262395Sbapt} while (0) 383262395Sbapt 384262395Sbapt#define LL_DELETE_VS2008(head,del) \ 385262395Sbapt LL_DELETE2_VS2008(head,del,next) 386262395Sbapt 387262395Sbapt#define LL_DELETE2_VS2008(head,del,next) \ 388262395Sbaptdo { \ 389262395Sbapt if ((head) == (del)) { \ 390262395Sbapt (head)=(head)->next; \ 391262395Sbapt } else { \ 392262395Sbapt char *_tmp = (char*)(head); \ 393262395Sbapt while ((head)->next && ((head)->next != (del))) { \ 394262395Sbapt head = (head)->next; \ 395262395Sbapt } \ 396262395Sbapt if ((head)->next) { \ 397262395Sbapt (head)->next = ((del)->next); \ 398262395Sbapt } \ 399262395Sbapt { \ 400262395Sbapt char **_head_alias = (char**)&(head); \ 401262395Sbapt *_head_alias = _tmp; \ 402262395Sbapt } \ 403262395Sbapt } \ 404262395Sbapt} while (0) 405262395Sbapt#ifdef NO_DECLTYPE 406262395Sbapt#undef LL_APPEND 407262395Sbapt#define LL_APPEND LL_APPEND_VS2008 408262395Sbapt#undef LL_DELETE 409262395Sbapt#define LL_DELETE LL_DELETE_VS2008 410262395Sbapt#undef LL_DELETE2 411262395Sbapt#define LL_DELETE2 LL_DELETE2_VS2008 412262395Sbapt#undef LL_APPEND2 413262395Sbapt#define LL_APPEND2 LL_APPEND2_VS2008 414262395Sbapt#undef LL_CONCAT /* no LL_CONCAT_VS2008 */ 415262395Sbapt#undef DL_CONCAT /* no DL_CONCAT_VS2008 */ 416262395Sbapt#endif 417262395Sbapt/* end VS2008 replacements */ 418262395Sbapt 419262395Sbapt#define LL_COUNT(head,el,counter) \ 420262395Sbapt LL_COUNT2(head,el,counter,next) \ 421262395Sbapt 422262395Sbapt#define LL_COUNT2(head,el,counter,next) \ 423262395Sbapt{ \ 424262395Sbapt counter = 0; \ 425262395Sbapt LL_FOREACH2(head,el,next){ ++counter; } \ 426262395Sbapt} 427262395Sbapt 428262395Sbapt#define LL_FOREACH(head,el) \ 429262395Sbapt LL_FOREACH2(head,el,next) 430262395Sbapt 431262395Sbapt#define LL_FOREACH2(head,el,next) \ 432262395Sbapt for(el=head;el;el=(el)->next) 433262395Sbapt 434262395Sbapt#define LL_FOREACH_SAFE(head,el,tmp) \ 435262395Sbapt LL_FOREACH_SAFE2(head,el,tmp,next) 436262395Sbapt 437262395Sbapt#define LL_FOREACH_SAFE2(head,el,tmp,next) \ 438262395Sbapt for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) 439262395Sbapt 440262395Sbapt#define LL_SEARCH_SCALAR(head,out,field,val) \ 441262395Sbapt LL_SEARCH_SCALAR2(head,out,field,val,next) 442262395Sbapt 443262395Sbapt#define LL_SEARCH_SCALAR2(head,out,field,val,next) \ 444262395Sbaptdo { \ 445262395Sbapt LL_FOREACH2(head,out,next) { \ 446262395Sbapt if ((out)->field == (val)) break; \ 447262395Sbapt } \ 448262395Sbapt} while(0) 449262395Sbapt 450262395Sbapt#define LL_SEARCH(head,out,elt,cmp) \ 451262395Sbapt LL_SEARCH2(head,out,elt,cmp,next) 452262395Sbapt 453262395Sbapt#define LL_SEARCH2(head,out,elt,cmp,next) \ 454262395Sbaptdo { \ 455262395Sbapt LL_FOREACH2(head,out,next) { \ 456262395Sbapt if ((cmp(out,elt))==0) break; \ 457262395Sbapt } \ 458262395Sbapt} while(0) 459262395Sbapt 460262395Sbapt#define LL_REPLACE_ELEM(head, el, add) \ 461262395Sbaptdo { \ 462262395Sbapt LDECLTYPE(head) _tmp; \ 463262395Sbapt assert(head != NULL); \ 464262395Sbapt assert(el != NULL); \ 465262395Sbapt assert(add != NULL); \ 466262395Sbapt (add)->next = (el)->next; \ 467262395Sbapt if ((head) == (el)) { \ 468262395Sbapt (head) = (add); \ 469262395Sbapt } else { \ 470262395Sbapt _tmp = head; \ 471262395Sbapt while (_tmp->next && (_tmp->next != (el))) { \ 472262395Sbapt _tmp = _tmp->next; \ 473262395Sbapt } \ 474262395Sbapt if (_tmp->next) { \ 475262395Sbapt _tmp->next = (add); \ 476262395Sbapt } \ 477262395Sbapt } \ 478262395Sbapt} while (0) 479262395Sbapt 480262395Sbapt#define LL_PREPEND_ELEM(head, el, add) \ 481262395Sbaptdo { \ 482262395Sbapt LDECLTYPE(head) _tmp; \ 483262395Sbapt assert(head != NULL); \ 484262395Sbapt assert(el != NULL); \ 485262395Sbapt assert(add != NULL); \ 486262395Sbapt (add)->next = (el); \ 487262395Sbapt if ((head) == (el)) { \ 488262395Sbapt (head) = (add); \ 489262395Sbapt } else { \ 490262395Sbapt _tmp = head; \ 491262395Sbapt while (_tmp->next && (_tmp->next != (el))) { \ 492262395Sbapt _tmp = _tmp->next; \ 493262395Sbapt } \ 494262395Sbapt if (_tmp->next) { \ 495262395Sbapt _tmp->next = (add); \ 496262395Sbapt } \ 497262395Sbapt } \ 498262395Sbapt} while (0) \ 499262395Sbapt 500262395Sbapt 501262395Sbapt/****************************************************************************** 502262395Sbapt * doubly linked list macros (non-circular) * 503262395Sbapt *****************************************************************************/ 504262395Sbapt#define DL_PREPEND(head,add) \ 505262395Sbapt DL_PREPEND2(head,add,prev,next) 506262395Sbapt 507262395Sbapt#define DL_PREPEND2(head,add,prev,next) \ 508262395Sbaptdo { \ 509262395Sbapt (add)->next = head; \ 510262395Sbapt if (head) { \ 511262395Sbapt (add)->prev = (head)->prev; \ 512262395Sbapt (head)->prev = (add); \ 513262395Sbapt } else { \ 514262395Sbapt (add)->prev = (add); \ 515262395Sbapt } \ 516262395Sbapt (head) = (add); \ 517262395Sbapt} while (0) 518262395Sbapt 519262395Sbapt#define DL_APPEND(head,add) \ 520262395Sbapt DL_APPEND2(head,add,prev,next) 521262395Sbapt 522262395Sbapt#define DL_APPEND2(head,add,prev,next) \ 523262395Sbaptdo { \ 524262395Sbapt if (head) { \ 525262395Sbapt (add)->prev = (head)->prev; \ 526262395Sbapt (head)->prev->next = (add); \ 527262395Sbapt (head)->prev = (add); \ 528262395Sbapt (add)->next = NULL; \ 529262395Sbapt } else { \ 530262395Sbapt (head)=(add); \ 531262395Sbapt (head)->prev = (head); \ 532262395Sbapt (head)->next = NULL; \ 533262395Sbapt } \ 534262395Sbapt} while (0) 535262395Sbapt 536262395Sbapt#define DL_CONCAT(head1,head2) \ 537262395Sbapt DL_CONCAT2(head1,head2,prev,next) 538262395Sbapt 539262395Sbapt#define DL_CONCAT2(head1,head2,prev,next) \ 540262395Sbaptdo { \ 541262395Sbapt LDECLTYPE(head1) _tmp; \ 542262395Sbapt if (head2) { \ 543262395Sbapt if (head1) { \ 544262395Sbapt _tmp = (head2)->prev; \ 545262395Sbapt (head2)->prev = (head1)->prev; \ 546262395Sbapt (head1)->prev->next = (head2); \ 547262395Sbapt (head1)->prev = _tmp; \ 548262395Sbapt } else { \ 549262395Sbapt (head1)=(head2); \ 550262395Sbapt } \ 551262395Sbapt } \ 552262395Sbapt} while (0) 553262395Sbapt 554262395Sbapt#define DL_DELETE(head,del) \ 555262395Sbapt DL_DELETE2(head,del,prev,next) 556262395Sbapt 557262395Sbapt#define DL_DELETE2(head,del,prev,next) \ 558262395Sbaptdo { \ 559262395Sbapt assert((del)->prev != NULL); \ 560262395Sbapt if ((del)->prev == (del)) { \ 561262395Sbapt (head)=NULL; \ 562262395Sbapt } else if ((del)==(head)) { \ 563262395Sbapt (del)->next->prev = (del)->prev; \ 564262395Sbapt (head) = (del)->next; \ 565262395Sbapt } else { \ 566262395Sbapt (del)->prev->next = (del)->next; \ 567262395Sbapt if ((del)->next) { \ 568262395Sbapt (del)->next->prev = (del)->prev; \ 569262395Sbapt } else { \ 570262395Sbapt (head)->prev = (del)->prev; \ 571262395Sbapt } \ 572262395Sbapt } \ 573262395Sbapt} while (0) 574262395Sbapt 575262395Sbapt#define DL_COUNT(head,el,counter) \ 576262395Sbapt DL_COUNT2(head,el,counter,next) \ 577262395Sbapt 578262395Sbapt#define DL_COUNT2(head,el,counter,next) \ 579262395Sbapt{ \ 580262395Sbapt counter = 0; \ 581262395Sbapt DL_FOREACH2(head,el,next){ ++counter; } \ 582262395Sbapt} 583262395Sbapt 584262395Sbapt#define DL_FOREACH(head,el) \ 585262395Sbapt DL_FOREACH2(head,el,next) 586262395Sbapt 587262395Sbapt#define DL_FOREACH2(head,el,next) \ 588262395Sbapt for(el=head;el;el=(el)->next) 589262395Sbapt 590262395Sbapt/* this version is safe for deleting the elements during iteration */ 591262395Sbapt#define DL_FOREACH_SAFE(head,el,tmp) \ 592262395Sbapt DL_FOREACH_SAFE2(head,el,tmp,next) 593262395Sbapt 594262395Sbapt#define DL_FOREACH_SAFE2(head,el,tmp,next) \ 595262395Sbapt for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) 596262395Sbapt 597262395Sbapt/* these are identical to their singly-linked list counterparts */ 598262395Sbapt#define DL_SEARCH_SCALAR LL_SEARCH_SCALAR 599262395Sbapt#define DL_SEARCH LL_SEARCH 600262395Sbapt#define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2 601262395Sbapt#define DL_SEARCH2 LL_SEARCH2 602262395Sbapt 603262395Sbapt#define DL_REPLACE_ELEM(head, el, add) \ 604262395Sbaptdo { \ 605262395Sbapt assert(head != NULL); \ 606262395Sbapt assert(el != NULL); \ 607262395Sbapt assert(add != NULL); \ 608262395Sbapt if ((head) == (el)) { \ 609262395Sbapt (head) = (add); \ 610262395Sbapt (add)->next = (el)->next; \ 611262395Sbapt if ((el)->next == NULL) { \ 612262395Sbapt (add)->prev = (add); \ 613262395Sbapt } else { \ 614262395Sbapt (add)->prev = (el)->prev; \ 615262395Sbapt (add)->next->prev = (add); \ 616262395Sbapt } \ 617262395Sbapt } else { \ 618262395Sbapt (add)->next = (el)->next; \ 619262395Sbapt (add)->prev = (el)->prev; \ 620262395Sbapt (add)->prev->next = (add); \ 621262395Sbapt if ((el)->next == NULL) { \ 622262395Sbapt (head)->prev = (add); \ 623262395Sbapt } else { \ 624262395Sbapt (add)->next->prev = (add); \ 625262395Sbapt } \ 626262395Sbapt } \ 627262395Sbapt} while (0) 628262395Sbapt 629262395Sbapt#define DL_PREPEND_ELEM(head, el, add) \ 630262395Sbaptdo { \ 631262395Sbapt assert(head != NULL); \ 632262395Sbapt assert(el != NULL); \ 633262395Sbapt assert(add != NULL); \ 634262395Sbapt (add)->next = (el); \ 635262395Sbapt (add)->prev = (el)->prev; \ 636262395Sbapt (el)->prev = (add); \ 637262395Sbapt if ((head) == (el)) { \ 638262395Sbapt (head) = (add); \ 639262395Sbapt } else { \ 640262395Sbapt (add)->prev->next = (add); \ 641262395Sbapt } \ 642262395Sbapt} while (0) \ 643262395Sbapt 644262395Sbapt 645262395Sbapt/****************************************************************************** 646262395Sbapt * circular doubly linked list macros * 647262395Sbapt *****************************************************************************/ 648262395Sbapt#define CDL_PREPEND(head,add) \ 649262395Sbapt CDL_PREPEND2(head,add,prev,next) 650262395Sbapt 651262395Sbapt#define CDL_PREPEND2(head,add,prev,next) \ 652262395Sbaptdo { \ 653262395Sbapt if (head) { \ 654262395Sbapt (add)->prev = (head)->prev; \ 655262395Sbapt (add)->next = (head); \ 656262395Sbapt (head)->prev = (add); \ 657262395Sbapt (add)->prev->next = (add); \ 658262395Sbapt } else { \ 659262395Sbapt (add)->prev = (add); \ 660262395Sbapt (add)->next = (add); \ 661262395Sbapt } \ 662262395Sbapt(head)=(add); \ 663262395Sbapt} while (0) 664262395Sbapt 665262395Sbapt#define CDL_DELETE(head,del) \ 666262395Sbapt CDL_DELETE2(head,del,prev,next) 667262395Sbapt 668262395Sbapt#define CDL_DELETE2(head,del,prev,next) \ 669262395Sbaptdo { \ 670262395Sbapt if ( ((head)==(del)) && ((head)->next == (head))) { \ 671262395Sbapt (head) = 0L; \ 672262395Sbapt } else { \ 673262395Sbapt (del)->next->prev = (del)->prev; \ 674262395Sbapt (del)->prev->next = (del)->next; \ 675262395Sbapt if ((del) == (head)) (head)=(del)->next; \ 676262395Sbapt } \ 677262395Sbapt} while (0) 678262395Sbapt 679262395Sbapt#define CDL_COUNT(head,el,counter) \ 680262395Sbapt CDL_COUNT2(head,el,counter,next) \ 681262395Sbapt 682262395Sbapt#define CDL_COUNT2(head, el, counter,next) \ 683262395Sbapt{ \ 684262395Sbapt counter = 0; \ 685262395Sbapt CDL_FOREACH2(head,el,next){ ++counter; } \ 686262395Sbapt} 687262395Sbapt 688262395Sbapt#define CDL_FOREACH(head,el) \ 689262395Sbapt CDL_FOREACH2(head,el,next) 690262395Sbapt 691262395Sbapt#define CDL_FOREACH2(head,el,next) \ 692262395Sbapt for(el=head;el;el=((el)->next==head ? 0L : (el)->next)) 693262395Sbapt 694262395Sbapt#define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \ 695262395Sbapt CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) 696262395Sbapt 697262395Sbapt#define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \ 698262395Sbapt for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \ 699262395Sbapt (el) && ((tmp2)=(el)->next, 1); \ 700262395Sbapt ((el) = (((el)==(tmp1)) ? 0L : (tmp2)))) 701262395Sbapt 702262395Sbapt#define CDL_SEARCH_SCALAR(head,out,field,val) \ 703262395Sbapt CDL_SEARCH_SCALAR2(head,out,field,val,next) 704262395Sbapt 705262395Sbapt#define CDL_SEARCH_SCALAR2(head,out,field,val,next) \ 706262395Sbaptdo { \ 707262395Sbapt CDL_FOREACH2(head,out,next) { \ 708262395Sbapt if ((out)->field == (val)) break; \ 709262395Sbapt } \ 710262395Sbapt} while(0) 711262395Sbapt 712262395Sbapt#define CDL_SEARCH(head,out,elt,cmp) \ 713262395Sbapt CDL_SEARCH2(head,out,elt,cmp,next) 714262395Sbapt 715262395Sbapt#define CDL_SEARCH2(head,out,elt,cmp,next) \ 716262395Sbaptdo { \ 717262395Sbapt CDL_FOREACH2(head,out,next) { \ 718262395Sbapt if ((cmp(out,elt))==0) break; \ 719262395Sbapt } \ 720262395Sbapt} while(0) 721262395Sbapt 722262395Sbapt#define CDL_REPLACE_ELEM(head, el, add) \ 723262395Sbaptdo { \ 724262395Sbapt assert(head != NULL); \ 725262395Sbapt assert(el != NULL); \ 726262395Sbapt assert(add != NULL); \ 727262395Sbapt if ((el)->next == (el)) { \ 728262395Sbapt (add)->next = (add); \ 729262395Sbapt (add)->prev = (add); \ 730262395Sbapt (head) = (add); \ 731262395Sbapt } else { \ 732262395Sbapt (add)->next = (el)->next; \ 733262395Sbapt (add)->prev = (el)->prev; \ 734262395Sbapt (add)->next->prev = (add); \ 735262395Sbapt (add)->prev->next = (add); \ 736262395Sbapt if ((head) == (el)) { \ 737262395Sbapt (head) = (add); \ 738262395Sbapt } \ 739262395Sbapt } \ 740262395Sbapt} while (0) 741262395Sbapt 742262395Sbapt#define CDL_PREPEND_ELEM(head, el, add) \ 743262395Sbaptdo { \ 744262395Sbapt assert(head != NULL); \ 745262395Sbapt assert(el != NULL); \ 746262395Sbapt assert(add != NULL); \ 747262395Sbapt (add)->next = (el); \ 748262395Sbapt (add)->prev = (el)->prev; \ 749262395Sbapt (el)->prev = (add); \ 750262395Sbapt (add)->prev->next = (add); \ 751262395Sbapt if ((head) == (el)) { \ 752262395Sbapt (head) = (add); \ 753262395Sbapt } \ 754262395Sbapt} while (0) \ 755262395Sbapt 756262395Sbapt#endif /* UTLIST_H */ 757262395Sbapt 758