1 /* 2 Copyright (c) 2007-2010, Troy D. Hanson http://uthash.sourceforge.net 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 24 #ifndef _DTLS_UTLIST_H 25 #define _DTLS_UTLIST_H 26 27 #define UTLIST_VERSION 1.9.1 28 29 /* 30 * This file contains macros to manipulate singly and doubly-linked lists. 31 * 32 * 1. LL_ macros: singly-linked lists. 33 * 2. DL_ macros: doubly-linked lists. 34 * 3. CDL_ macros: circular doubly-linked lists. 35 * 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. 39 * 40 * ----------------.EXAMPLE ------------------------- 41 * struct item { 42 * int id; 43 * struct item *prev, *next; 44 * } 45 * 46 * struct item *list = NULL: 47 * 48 * int main() { 49 * struct item *item; 50 * ... allocate and populate item ... 51 * DL_APPEND(list, item); 52 * } 53 * -------------------------------------------------- 54 * 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. 58 */ 59 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 && __cplusplus /* VS2010 and newer in C++ mode */ 66 #define LDECLTYPE(x) decltype(x) 67 #else /* VS2008 or older (or VS2010 in C mode) */ 68 #define NO_DECLTYPE 69 #define LDECLTYPE(x) char* 70 #endif 71 #else /* GNU, Sun and other compilers */ 72 #define LDECLTYPE(x) __typeof(x) 73 #endif 74 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.*/ 78 #ifdef NO_DECLTYPE 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); } 86 #else 87 #define _SV(elt,list) 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) 92 #define _RS(list) 93 #define _CASTASGN(a,b) (a)=(b) 94 #endif 95 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) \ 101 do { \ 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; \ 109 if (list) { \ 110 _ls_insize = 1; \ 111 _ls_looping = 1; \ 112 while (_ls_looping) { \ 113 _CASTASGN(_ls_p,list); \ 114 _CASTASGN(_ls_oldhead,list); \ 115 list = NULL; \ 116 _ls_tail = NULL; \ 117 _ls_nmerges = 0; \ 118 while (_ls_p) { \ 119 _ls_nmerges++; \ 120 _ls_q = _ls_p; \ 121 _ls_psize = 0; \ 122 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 123 _ls_psize++; \ 124 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \ 125 if (!_ls_q) break; \ 126 } \ 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--; \ 135 } else { \ 136 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ 137 } \ 138 if (_ls_tail) { \ 139 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \ 140 } else { \ 141 _CASTASGN(list,_ls_e); \ 142 } \ 143 _ls_tail = _ls_e; \ 144 } \ 145 _ls_p = _ls_q; \ 146 } \ 147 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \ 148 if (_ls_nmerges <= 1) { \ 149 _ls_looping=0; \ 150 } \ 151 _ls_insize *= 2; \ 152 } \ 153 } else _tmp=NULL; /* quiet gcc unused variable warning */ \ 154 } while (0) 155 156 #define DL_SORT(list, cmp) \ 157 do { \ 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; \ 165 if (list) { \ 166 _ls_insize = 1; \ 167 _ls_looping = 1; \ 168 while (_ls_looping) { \ 169 _CASTASGN(_ls_p,list); \ 170 _CASTASGN(_ls_oldhead,list); \ 171 list = NULL; \ 172 _ls_tail = NULL; \ 173 _ls_nmerges = 0; \ 174 while (_ls_p) { \ 175 _ls_nmerges++; \ 176 _ls_q = _ls_p; \ 177 _ls_psize = 0; \ 178 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 179 _ls_psize++; \ 180 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \ 181 if (!_ls_q) break; \ 182 } \ 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--; \ 191 } else { \ 192 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ 193 } \ 194 if (_ls_tail) { \ 195 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \ 196 } else { \ 197 _CASTASGN(list,_ls_e); \ 198 } \ 199 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \ 200 _ls_tail = _ls_e; \ 201 } \ 202 _ls_p = _ls_q; \ 203 } \ 204 _CASTASGN(list->prev, _ls_tail); \ 205 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \ 206 if (_ls_nmerges <= 1) { \ 207 _ls_looping=0; \ 208 } \ 209 _ls_insize *= 2; \ 210 } \ 211 } else _tmp=NULL; /* quiet gcc unused variable warning */ \ 212 } while (0) 213 214 #define CDL_SORT(list, cmp) \ 215 do { \ 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; \ 224 if (list) { \ 225 _ls_insize = 1; \ 226 _ls_looping = 1; \ 227 while (_ls_looping) { \ 228 _CASTASGN(_ls_p,list); \ 229 _CASTASGN(_ls_oldhead,list); \ 230 list = NULL; \ 231 _ls_tail = NULL; \ 232 _ls_nmerges = 0; \ 233 while (_ls_p) { \ 234 _ls_nmerges++; \ 235 _ls_q = _ls_p; \ 236 _ls_psize = 0; \ 237 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 238 _ls_psize++; \ 239 _SV(_ls_q,list); \ 240 if (_NEXT(_ls_q,list) == _ls_oldhead) { \ 241 _ls_q = NULL; \ 242 } else { \ 243 _ls_q = _NEXT(_ls_q,list); \ 244 } \ 245 _RS(list); \ 246 if (!_ls_q) break; \ 247 } \ 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; } \ 259 } else { \ 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; } \ 262 } \ 263 if (_ls_tail) { \ 264 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \ 265 } else { \ 266 _CASTASGN(list,_ls_e); \ 267 } \ 268 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \ 269 _ls_tail = _ls_e; \ 270 } \ 271 _ls_p = _ls_q; \ 272 } \ 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) { \ 277 _ls_looping=0; \ 278 } \ 279 _ls_insize *= 2; \ 280 } \ 281 } else _tmp=NULL; /* quiet gcc unused variable warning */ \ 282 } while (0) 283 284 /****************************************************************************** 285 * singly linked list macros (non-circular) * 286 *****************************************************************************/ 287 #define LL_PREPEND(head,add) \ 288 do { \ 289 (add)->next = head; \ 290 head = add; \ 291 } while (0) 292 293 #define LL_APPEND(head,add) \ 294 do { \ 295 LDECLTYPE(head) _tmp; \ 296 (add)->next=NULL; \ 297 if (head) { \ 298 _tmp = head; \ 299 while (_tmp->next) { _tmp = _tmp->next; } \ 300 _tmp->next=(add); \ 301 } else { \ 302 (head)=(add); \ 303 } \ 304 } while (0) 305 306 #define LL_DELETE(head,del) \ 307 do { \ 308 LDECLTYPE(head) _tmp; \ 309 if ((head) == (del)) { \ 310 (head)=(head)->next; \ 311 } else { \ 312 _tmp = head; \ 313 while (_tmp->next && (_tmp->next != (del))) { \ 314 _tmp = _tmp->next; \ 315 } \ 316 if (_tmp->next) { \ 317 _tmp->next = ((del)->next); \ 318 } \ 319 } \ 320 } while (0) 321 322 /* Here are VS2008 replacements for LL_APPEND and LL_DELETE */ 323 #define LL_APPEND_VS2008(head,add) \ 324 do { \ 325 if (head) { \ 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); \ 329 } else { \ 330 (head)=(add); \ 331 } \ 332 (add)->next=NULL; \ 333 } while (0) 334 335 #define LL_DELETE_VS2008(head,del) \ 336 do { \ 337 if ((head) == (del)) { \ 338 (head)=(head)->next; \ 339 } else { \ 340 char *_tmp = (char*)(head); \ 341 while (head->next && (head->next != (del))) { \ 342 head = head->next; \ 343 } \ 344 if (head->next) { \ 345 head->next = ((del)->next); \ 346 } \ 347 { \ 348 char **_head_alias = (char**)&(head); \ 349 *_head_alias = _tmp; \ 350 } \ 351 } \ 352 } while (0) 353 #ifdef NO_DECLTYPE 354 #undef LL_APPEND 355 #define LL_APPEND LL_APPEND_VS2008 356 #undef LL_DELETE 357 #define LL_DELETE LL_DELETE_VS2008 358 #endif 359 /* end VS2008 replacements */ 360 361 #define LL_FOREACH(head,el) \ 362 for(el=head;el;el=el->next) 363 364 #define LL_FOREACH_SAFE(head,el,tmp) \ 365 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) 366 367 #define LL_SEARCH_SCALAR(head,out,field,val) \ 368 do { \ 369 LL_FOREACH(head,out) { \ 370 if ((out)->field == (val)) break; \ 371 } \ 372 } while(0) 373 374 #define LL_SEARCH(head,out,elt,cmp) \ 375 do { \ 376 LL_FOREACH(head,out) { \ 377 if ((cmp(out,elt))==0) break; \ 378 } \ 379 } while(0) 380 381 /****************************************************************************** 382 * doubly linked list macros (non-circular) * 383 *****************************************************************************/ 384 #define DL_PREPEND(head,add) \ 385 do { \ 386 (add)->next = head; \ 387 if (head) { \ 388 (add)->prev = (head)->prev; \ 389 (head)->prev = (add); \ 390 } else { \ 391 (add)->prev = (add); \ 392 } \ 393 (head) = (add); \ 394 } while (0) 395 396 #define DL_APPEND(head,add) \ 397 do { \ 398 if (head) { \ 399 (add)->prev = (head)->prev; \ 400 (head)->prev->next = (add); \ 401 (head)->prev = (add); \ 402 (add)->next = NULL; \ 403 } else { \ 404 (head)=(add); \ 405 (head)->prev = (head); \ 406 (head)->next = NULL; \ 407 } \ 408 } while (0); 409 410 #define DL_DELETE(head,del) \ 411 do { \ 412 if ((del)->prev == (del)) { \ 413 (head)=NULL; \ 414 } else if ((del)==(head)) { \ 415 (del)->next->prev = (del)->prev; \ 416 (head) = (del)->next; \ 417 } else { \ 418 (del)->prev->next = (del)->next; \ 419 if ((del)->next) { \ 420 (del)->next->prev = (del)->prev; \ 421 } else { \ 422 (head)->prev = (del)->prev; \ 423 } \ 424 } \ 425 } while (0); 426 427 428 #define DL_FOREACH(head,el) \ 429 for(el=head;el;el=el->next) 430 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) 434 435 /* these are identical to their singly-linked list counterparts */ 436 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR 437 #define DL_SEARCH LL_SEARCH 438 439 /****************************************************************************** 440 * circular doubly linked list macros * 441 *****************************************************************************/ 442 #define CDL_PREPEND(head,add) \ 443 do { \ 444 if (head) { \ 445 (add)->prev = (head)->prev; \ 446 (add)->next = (head); \ 447 (head)->prev = (add); \ 448 (add)->prev->next = (add); \ 449 } else { \ 450 (add)->prev = (add); \ 451 (add)->next = (add); \ 452 } \ 453 (head)=(add); \ 454 } while (0) 455 456 #define CDL_DELETE(head,del) \ 457 do { \ 458 if ( ((head)==(del)) && ((head)->next == (head))) { \ 459 (head) = 0L; \ 460 } else { \ 461 (del)->next->prev = (del)->prev; \ 462 (del)->prev->next = (del)->next; \ 463 if ((del) == (head)) (head)=(del)->next; \ 464 } \ 465 } while (0); 466 467 #define CDL_FOREACH(head,el) \ 468 for(el=head;el;el=(el->next==head ? 0L : el->next)) 469 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)))) 474 475 #define CDL_SEARCH_SCALAR(head,out,field,val) \ 476 do { \ 477 CDL_FOREACH(head,out) { \ 478 if ((out)->field == (val)) break; \ 479 } \ 480 } while(0) 481 482 #define CDL_SEARCH(head,out,elt,cmp) \ 483 do { \ 484 CDL_FOREACH(head,out) { \ 485 if ((cmp(out,elt))==0) break; \ 486 } \ 487 } while(0) 488 489 #endif /* _DTLS_UTLIST_H */ 490 491
