1 /* 2 Copyright (c) 2007-2013, 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 UTLIST_H 25 #define UTLIST_H 26 27 #define UTLIST_VERSION 1.9.7 28 29 #include <assert.h> 30 31 /* 32 * This file contains macros to manipulate singly and doubly-linked lists. 33 * 34 * 1. LL_ macros: singly-linked lists. 35 * 2. DL_ macros: doubly-linked lists. 36 * 3. CDL_ macros: circular doubly-linked lists. 37 * 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. 41 * 42 * ----------------.EXAMPLE ------------------------- 43 * struct item { 44 * int id; 45 * struct item *prev, *next; 46 * } 47 * 48 * struct item *list = NULL: 49 * 50 * int main() { 51 * struct item *item; 52 * ... allocate and populate item ... 53 * DL_APPEND(list, item); 54 * } 55 * -------------------------------------------------- 56 * 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. 60 */ 61 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) */ 70 #define NO_DECLTYPE 71 #define LDECLTYPE(x) char* 72 #endif 73 #else /* GNU, Sun and other compilers */ 74 #define LDECLTYPE(x) __typeof(x) 75 #endif 76 77 /* for VS2008 we use some workarounds to get around the lack of decltype, 78 * namely, we always reassign our tmp variable to the list head if we need 79 * to dereference its prev/next pointers, and save/restore the real head.*/ 80 #ifdef NO_DECLTYPE 81 #define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); } 82 #define _NEXT(elt,list,next) ((char*)((list)->next)) 83 #define _NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); } 84 /* #define _PREV(elt,list,prev) ((char*)((list)->prev)) */ 85 #define _PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); } 86 #define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; } 87 #define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); } 88 #else 89 #define _SV(elt,list) 90 #define _NEXT(elt,list,next) ((elt)->next) 91 #define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to) 92 /* #define _PREV(elt,list,prev) ((elt)->prev) */ 93 #define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to) 94 #define _RS(list) 95 #define _CASTASGN(a,b) (a)=(b) 96 #endif 97 98 /****************************************************************************** 99 * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort * 100 * Unwieldy variable names used here to avoid shadowing passed-in variables. * 101 *****************************************************************************/ 102 #define LL_SORT(list, cmp) \ 103 LL_SORT2(list, cmp, next) 104 105 #define LL_SORT2(list, cmp, next) \ 106 do { \ 107 LDECLTYPE(list) _ls_p; \ 108 LDECLTYPE(list) _ls_q; \ 109 LDECLTYPE(list) _ls_e; \ 110 LDECLTYPE(list) _ls_tail; \ 111 LDECLTYPE(list) _ls_oldhead; \ 112 LDECLTYPE(list) _tmp; \ 113 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 114 if (list) { \ 115 _ls_insize = 1; \ 116 _ls_looping = 1; \ 117 while (_ls_looping) { \ 118 _CASTASGN(_ls_p,list); \ 119 _CASTASGN(_ls_oldhead,list); \ 120 list = NULL; \ 121 _ls_tail = NULL; \ 122 _ls_nmerges = 0; \ 123 while (_ls_p) { \ 124 _ls_nmerges++; \ 125 _ls_q = _ls_p; \ 126 _ls_psize = 0; \ 127 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 128 _ls_psize++; \ 129 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \ 130 if (!_ls_q) break; \ 131 } \ 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--; \ 143 } else { \ 144 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 145 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 146 } \ 147 if (_ls_tail) { \ 148 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ 149 } else { \ 150 _CASTASGN(list,_ls_e); \ 151 } \ 152 _ls_tail = _ls_e; \ 153 } \ 154 _ls_p = _ls_q; \ 155 } \ 156 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \ 157 if (_ls_nmerges <= 1) { \ 158 _ls_looping=0; \ 159 } \ 160 _ls_insize *= 2; \ 161 } \ 162 } else _tmp=NULL; /* quiet gcc unused variable warning */ \ 163 } while (0) 164 165 166 #define DL_SORT(list, cmp) \ 167 DL_SORT2(list, cmp, prev, next) 168 169 #define DL_SORT2(list, cmp, prev, next) \ 170 do { \ 171 LDECLTYPE(list) _ls_p; \ 172 LDECLTYPE(list) _ls_q; \ 173 LDECLTYPE(list) _ls_e; \ 174 LDECLTYPE(list) _ls_tail; \ 175 LDECLTYPE(list) _ls_oldhead; \ 176 LDECLTYPE(list) _tmp; \ 177 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 178 if (list) { \ 179 _ls_insize = 1; \ 180 _ls_looping = 1; \ 181 while (_ls_looping) { \ 182 _CASTASGN(_ls_p,list); \ 183 _CASTASGN(_ls_oldhead,list); \ 184 list = NULL; \ 185 _ls_tail = NULL; \ 186 _ls_nmerges = 0; \ 187 while (_ls_p) { \ 188 _ls_nmerges++; \ 189 _ls_q = _ls_p; \ 190 _ls_psize = 0; \ 191 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 192 _ls_psize++; \ 193 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \ 194 if (!_ls_q) break; \ 195 } \ 196 _ls_qsize = _ls_insize; \ 197 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ 198 if (_ls_psize == 0) { \ 199 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 200 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 201 } else if (_ls_qsize == 0 || !_ls_q) { \ 202 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 203 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 204 } else if (cmp(_ls_p,_ls_q) <= 0) { \ 205 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 206 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 207 } else { \ 208 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 209 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 210 } \ 211 if (_ls_tail) { \ 212 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ 213 } else { \ 214 _CASTASGN(list,_ls_e); \ 215 } \ 216 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \ 217 _ls_tail = _ls_e; \ 218 } \ 219 _ls_p = _ls_q; \ 220 } \ 221 _CASTASGN(list->prev, _ls_tail); \ 222 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \ 223 if (_ls_nmerges <= 1) { \ 224 _ls_looping=0; \ 225 } \ 226 _ls_insize *= 2; \ 227 } \ 228 } else _tmp=NULL; /* quiet gcc unused variable warning */ \ 229 } while (0) 230 231 #define CDL_SORT(list, cmp) \ 232 CDL_SORT2(list, cmp, prev, next) 233 234 #define CDL_SORT2(list, cmp, prev, next) \ 235 do { \ 236 LDECLTYPE(list) _ls_p; \ 237 LDECLTYPE(list) _ls_q; \ 238 LDECLTYPE(list) _ls_e; \ 239 LDECLTYPE(list) _ls_tail; \ 240 LDECLTYPE(list) _ls_oldhead; \ 241 LDECLTYPE(list) _tmp; \ 242 LDECLTYPE(list) _tmp2; \ 243 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 244 if (list) { \ 245 _ls_insize = 1; \ 246 _ls_looping = 1; \ 247 while (_ls_looping) { \ 248 _CASTASGN(_ls_p,list); \ 249 _CASTASGN(_ls_oldhead,list); \ 250 list = NULL; \ 251 _ls_tail = NULL; \ 252 _ls_nmerges = 0; \ 253 while (_ls_p) { \ 254 _ls_nmerges++; \ 255 _ls_q = _ls_p; \ 256 _ls_psize = 0; \ 257 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 258 _ls_psize++; \ 259 _SV(_ls_q,list); \ 260 if (_NEXT(_ls_q,list,next) == _ls_oldhead) { \ 261 _ls_q = NULL; \ 262 } else { \ 263 _ls_q = _NEXT(_ls_q,list,next); \ 264 } \ 265 _RS(list); \ 266 if (!_ls_q) break; \ 267 } \ 268 _ls_qsize = _ls_insize; \ 269 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ 270 if (_ls_psize == 0) { \ 271 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 272 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 273 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ 274 } else if (_ls_qsize == 0 || !_ls_q) { \ 275 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 276 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 277 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ 278 } else if (cmp(_ls_p,_ls_q) <= 0) { \ 279 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 280 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 281 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ 282 } else { \ 283 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 284 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 285 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ 286 } \ 287 if (_ls_tail) { \ 288 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ 289 } else { \ 290 _CASTASGN(list,_ls_e); \ 291 } \ 292 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \ 293 _ls_tail = _ls_e; \ 294 } \ 295 _ls_p = _ls_q; \ 296 } \ 297 _CASTASGN(list->prev,_ls_tail); \ 298 _CASTASGN(_tmp2,list); \ 299 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp2,next); _RS(list); \ 300 if (_ls_nmerges <= 1) { \ 301 _ls_looping=0; \ 302 } \ 303 _ls_insize *= 2; \ 304 } \ 305 } else _tmp=NULL; /* quiet gcc unused variable warning */ \ 306 } while (0) 307 308 /****************************************************************************** 309 * singly linked list macros (non-circular) * 310 *****************************************************************************/ 311 #define LL_PREPEND(head,add) \ 312 LL_PREPEND2(head,add,next) 313 314 #define LL_PREPEND2(head,add,next) \ 315 do { \ 316 (add)->next = head; \ 317 head = add; \ 318 } while (0) 319 320 #define LL_CONCAT(head1,head2) \ 321 LL_CONCAT2(head1,head2,next) 322 323 #define LL_CONCAT2(head1,head2,next) \ 324 do { \ 325 LDECLTYPE(head1) _tmp; \ 326 if (head1) { \ 327 _tmp = head1; \ 328 while (_tmp->next) { _tmp = _tmp->next; } \ 329 _tmp->next=(head2); \ 330 } else { \ 331 (head1)=(head2); \ 332 } \ 333 } while (0) 334 335 #define LL_APPEND(head,add) \ 336 LL_APPEND2(head,add,next) 337 338 #define LL_APPEND2(head,add,next) \ 339 do { \ 340 LDECLTYPE(head) _tmp; \ 341 (add)->next=NULL; \ 342 if (head) { \ 343 _tmp = head; \ 344 while (_tmp->next) { _tmp = _tmp->next; } \ 345 _tmp->next=(add); \ 346 } else { \ 347 (head)=(add); \ 348 } \ 349 } while (0) 350 351 #define LL_DELETE(head,del) \ 352 LL_DELETE2(head,del,next) 353 354 #define LL_DELETE2(head,del,next) \ 355 do { \ 356 LDECLTYPE(head) _tmp; \ 357 if ((head) == (del)) { \ 358 (head)=(head)->next; \ 359 } else { \ 360 _tmp = head; \ 361 while (_tmp->next && (_tmp->next != (del))) { \ 362 _tmp = _tmp->next; \ 363 } \ 364 if (_tmp->next) { \ 365 _tmp->next = ((del)->next); \ 366 } \ 367 } \ 368 } while (0) 369 370 /* Here are VS2008 replacements for LL_APPEND and LL_DELETE */ 371 #define LL_APPEND_VS2008(head,add) \ 372 LL_APPEND2_VS2008(head,add,next) 373 374 #define LL_APPEND2_VS2008(head,add,next) \ 375 do { \ 376 if (head) { \ 377 (add)->next = head; /* use add->next as a temp variable */ \ 378 while ((add)->next->next) { (add)->next = (add)->next->next; } \ 379 (add)->next->next=(add); \ 380 } else { \ 381 (head)=(add); \ 382 } \ 383 (add)->next=NULL; \ 384 } while (0) 385 386 #define LL_DELETE_VS2008(head,del) \ 387 LL_DELETE2_VS2008(head,del,next) 388 389 #define LL_DELETE2_VS2008(head,del,next) \ 390 do { \ 391 if ((head) == (del)) { \ 392 (head)=(head)->next; \ 393 } else { \ 394 char *_tmp = (char*)(head); \ 395 while ((head)->next && ((head)->next != (del))) { \ 396 head = (head)->next; \ 397 } \ 398 if ((head)->next) { \ 399 (head)->next = ((del)->next); \ 400 } \ 401 { \ 402 char **_head_alias = (char**)&(head); \ 403 *_head_alias = _tmp; \ 404 } \ 405 } \ 406 } while (0) 407 #ifdef NO_DECLTYPE 408 #undef LL_APPEND 409 #define LL_APPEND LL_APPEND_VS2008 410 #undef LL_DELETE 411 #define LL_DELETE LL_DELETE_VS2008 412 #undef LL_DELETE2 413 #define LL_DELETE2_VS2008 414 #undef LL_APPEND2 415 #define LL_APPEND2 LL_APPEND2_VS2008 416 #undef LL_CONCAT /* no LL_CONCAT_VS2008 */ 417 #undef DL_CONCAT /* no DL_CONCAT_VS2008 */ 418 #endif 419 /* end VS2008 replacements */ 420 421 #define LL_FOREACH(head,el) \ 422 LL_FOREACH2(head,el,next) 423 424 #define LL_FOREACH2(head,el,next) \ 425 for(el=head;el;el=(el)->next) 426 427 #define LL_FOREACH_SAFE(head,el,tmp) \ 428 LL_FOREACH_SAFE2(head,el,tmp,next) 429 430 #define LL_FOREACH_SAFE2(head,el,tmp,next) \ 431 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) 432 433 #define LL_SEARCH_SCALAR(head,out,field,val) \ 434 LL_SEARCH_SCALAR2(head,out,field,val,next) 435 436 #define LL_SEARCH_SCALAR2(head,out,field,val,next) \ 437 do { \ 438 LL_FOREACH2(head,out,next) { \ 439 if ((out)->field == (val)) break; \ 440 } \ 441 } while(0) 442 443 #define LL_SEARCH(head,out,elt,cmp) \ 444 LL_SEARCH2(head,out,elt,cmp,next) 445 446 #define LL_SEARCH2(head,out,elt,cmp,next) \ 447 do { \ 448 LL_FOREACH2(head,out,next) { \ 449 if ((cmp(out,elt))==0) break; \ 450 } \ 451 } while(0) 452 453 #define LL_REPLACE_ELEM(head, el, add) \ 454 do { \ 455 LDECLTYPE(head) _tmp; \ 456 assert(head != NULL); \ 457 assert(el != NULL); \ 458 assert(add != NULL); \ 459 (add)->next = (el)->next; \ 460 if ((head) == (el)) { \ 461 (head) = (add); \ 462 } else { \ 463 _tmp = head; \ 464 while (_tmp->next && (_tmp->next != (el))) { \ 465 _tmp = _tmp->next; \ 466 } \ 467 if (_tmp->next) { \ 468 _tmp->next = (add); \ 469 } \ 470 } \ 471 } while (0) 472 473 #define LL_PREPEND_ELEM(head, el, add) \ 474 do { \ 475 LDECLTYPE(head) _tmp; \ 476 assert(head != NULL); \ 477 assert(el != NULL); \ 478 assert(add != NULL); \ 479 (add)->next = (el); \ 480 if ((head) == (el)) { \ 481 (head) = (add); \ 482 } else { \ 483 _tmp = head; \ 484 while (_tmp->next && (_tmp->next != (el))) { \ 485 _tmp = _tmp->next; \ 486 } \ 487 if (_tmp->next) { \ 488 _tmp->next = (add); \ 489 } \ 490 } \ 491 } while (0) \ 492 493 494 /****************************************************************************** 495 * doubly linked list macros (non-circular) * 496 *****************************************************************************/ 497 #define DL_PREPEND(head,add) \ 498 DL_PREPEND2(head,add,prev,next) 499 500 #define DL_PREPEND2(head,add,prev,next) \ 501 do { \ 502 (add)->next = head; \ 503 if (head) { \ 504 (add)->prev = (head)->prev; \ 505 (head)->prev = (add); \ 506 } else { \ 507 (add)->prev = (add); \ 508 } \ 509 (head) = (add); \ 510 } while (0) 511 512 #define DL_APPEND(head,add) \ 513 DL_APPEND2(head,add,prev,next) 514 515 #define DL_APPEND2(head,add,prev,next) \ 516 do { \ 517 if (head) { \ 518 (add)->prev = (head)->prev; \ 519 (head)->prev->next = (add); \ 520 (head)->prev = (add); \ 521 (add)->next = NULL; \ 522 } else { \ 523 (head)=(add); \ 524 (head)->prev = (head); \ 525 (head)->next = NULL; \ 526 } \ 527 } while (0) 528 529 #define DL_CONCAT(head1,head2) \ 530 DL_CONCAT2(head1,head2,prev,next) 531 532 #define DL_CONCAT2(head1,head2,prev,next) \ 533 do { \ 534 LDECLTYPE(head1) _tmp; \ 535 if (head2) { \ 536 if (head1) { \ 537 _tmp = (head2)->prev; \ 538 (head2)->prev = (head1)->prev; \ 539 (head1)->prev->next = (head2); \ 540 (head1)->prev = _tmp; \ 541 } else { \ 542 (head1)=(head2); \ 543 } \ 544 } \ 545 } while (0) 546 547 #define DL_DELETE(head,del) \ 548 DL_DELETE2(head,del,prev,next) 549 550 #define DL_DELETE2(head,del,prev,next) \ 551 do { \ 552 assert((del)->prev != NULL); \ 553 if ((del)->prev == (del)) { \ 554 (head)=NULL; \ 555 } else if ((del)==(head)) { \ 556 (del)->next->prev = (del)->prev; \ 557 (head) = (del)->next; \ 558 } else { \ 559 (del)->prev->next = (del)->next; \ 560 if ((del)->next) { \ 561 (del)->next->prev = (del)->prev; \ 562 } else { \ 563 (head)->prev = (del)->prev; \ 564 } \ 565 } \ 566 } while (0) 567 568 569 #define DL_FOREACH(head,el) \ 570 DL_FOREACH2(head,el,next) 571 572 #define DL_FOREACH2(head,el,next) \ 573 for(el=head;el;el=(el)->next) 574 575 /* this version is safe for deleting the elements during iteration */ 576 #define DL_FOREACH_SAFE(head,el,tmp) \ 577 DL_FOREACH_SAFE2(head,el,tmp,next) 578 579 #define DL_FOREACH_SAFE2(head,el,tmp,next) \ 580 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) 581 582 /* these are identical to their singly-linked list counterparts */ 583 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR 584 #define DL_SEARCH LL_SEARCH 585 #define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2 586 #define DL_SEARCH2 LL_SEARCH2 587 588 #define DL_REPLACE_ELEM(head, el, add) \ 589 do { \ 590 assert(head != NULL); \ 591 assert(el != NULL); \ 592 assert(add != NULL); \ 593 if ((head) == (el)) { \ 594 (head) = (add); \ 595 (add)->next = (el)->next; \ 596 if ((el)->next == NULL) { \ 597 (add)->prev = (add); \ 598 } else { \ 599 (add)->prev = (el)->prev; \ 600 (add)->next->prev = (add); \ 601 } \ 602 } else { \ 603 (add)->next = (el)->next; \ 604 (add)->prev = (el)->prev; \ 605 (add)->prev->next = (add); \ 606 if ((el)->next == NULL) { \ 607 (head)->prev = (add); \ 608 } else { \ 609 (add)->next->prev = (add); \ 610 } \ 611 } \ 612 } while (0) 613 614 #define DL_PREPEND_ELEM(head, el, add) \ 615 do { \ 616 assert(head != NULL); \ 617 assert(el != NULL); \ 618 assert(add != NULL); \ 619 (add)->next = (el); \ 620 (add)->prev = (el)->prev; \ 621 (el)->prev = (add); \ 622 if ((head) == (el)) { \ 623 (head) = (add); \ 624 } else { \ 625 (add)->prev->next = (add); \ 626 } \ 627 } while (0) \ 628 629 630 /****************************************************************************** 631 * circular doubly linked list macros * 632 *****************************************************************************/ 633 #define CDL_PREPEND(head,add) \ 634 CDL_PREPEND2(head,add,prev,next) 635 636 #define CDL_PREPEND2(head,add,prev,next) \ 637 do { \ 638 if (head) { \ 639 (add)->prev = (head)->prev; \ 640 (add)->next = (head); \ 641 (head)->prev = (add); \ 642 (add)->prev->next = (add); \ 643 } else { \ 644 (add)->prev = (add); \ 645 (add)->next = (add); \ 646 } \ 647 (head)=(add); \ 648 } while (0) 649 650 #define CDL_DELETE(head,del) \ 651 CDL_DELETE2(head,del,prev,next) 652 653 #define CDL_DELETE2(head,del,prev,next) \ 654 do { \ 655 if ( ((head)==(del)) && ((head)->next == (head))) { \ 656 (head) = 0L; \ 657 } else { \ 658 (del)->next->prev = (del)->prev; \ 659 (del)->prev->next = (del)->next; \ 660 if ((del) == (head)) (head)=(del)->next; \ 661 } \ 662 } while (0) 663 664 #define CDL_FOREACH(head,el) \ 665 CDL_FOREACH2(head,el,next) 666 667 #define CDL_FOREACH2(head,el,next) \ 668 for(el=head;el;el=((el)->next==head ? 0L : (el)->next)) 669 670 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \ 671 CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) 672 673 #define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \ 674 for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \ 675 (el) && ((tmp2)=(el)->next, 1); \ 676 ((el) = (((el)==(tmp1)) ? 0L : (tmp2)))) 677 678 #define CDL_SEARCH_SCALAR(head,out,field,val) \ 679 CDL_SEARCH_SCALAR2(head,out,field,val,next) 680 681 #define CDL_SEARCH_SCALAR2(head,out,field,val,next) \ 682 do { \ 683 CDL_FOREACH2(head,out,next) { \ 684 if ((out)->field == (val)) break; \ 685 } \ 686 } while(0) 687 688 #define CDL_SEARCH(head,out,elt,cmp) \ 689 CDL_SEARCH2(head,out,elt,cmp,next) 690 691 #define CDL_SEARCH2(head,out,elt,cmp,next) \ 692 do { \ 693 CDL_FOREACH2(head,out,next) { \ 694 if ((cmp(out,elt))==0) break; \ 695 } \ 696 } while(0) 697 698 #define CDL_REPLACE_ELEM(head, el, add) \ 699 do { \ 700 assert(head != NULL); \ 701 assert(el != NULL); \ 702 assert(add != NULL); \ 703 if ((el)->next == (el)) { \ 704 (add)->next = (add); \ 705 (add)->prev = (add); \ 706 (head) = (add); \ 707 } else { \ 708 (add)->next = (el)->next; \ 709 (add)->prev = (el)->prev; \ 710 (add)->next->prev = (add); \ 711 (add)->prev->next = (add); \ 712 if ((head) == (el)) { \ 713 (head) = (add); \ 714 } \ 715 } \ 716 } while (0) 717 718 #define CDL_PREPEND_ELEM(head, el, add) \ 719 do { \ 720 assert(head != NULL); \ 721 assert(el != NULL); \ 722 assert(add != NULL); \ 723 (add)->next = (el); \ 724 (add)->prev = (el)->prev; \ 725 (el)->prev = (add); \ 726 (add)->prev->next = (add); \ 727 if ((head) == (el)) { \ 728 (head) = (add); \ 729 } \ 730 } while (0) \ 731 732 #endif /* UTLIST_H */ 733 734