utlist.h
1 /* 2 Copyright (c) 2007-2013, Troy D. Hanson http://troydhanson.github.com/uthash/ 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.8 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 #elif defined(__ICCARM__) 74 #define NO_DECLTYPE 75 #define LDECLTYPE(x) char* 76 #else /* GNU, Sun and other compilers */ 77 #define LDECLTYPE(x) __typeof(x) 78 #endif 79 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.*/ 83 #ifdef NO_DECLTYPE 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); } 91 #else 92 #define _SV(elt,list) 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) 97 #define _RS(list) 98 #define _CASTASGN(a,b) (a)=(b) 99 #endif 100 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) 107 108 #define LL_SORT2(list, cmp, next) \ 109 do { \ 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; \ 115 if (list) { \ 116 _ls_insize = 1; \ 117 _ls_looping = 1; \ 118 while (_ls_looping) { \ 119 _CASTASGN(_ls_p,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 if (_ls_tail) { \ 157 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \ 158 } \ 159 if (_ls_nmerges <= 1) { \ 160 _ls_looping=0; \ 161 } \ 162 _ls_insize *= 2; \ 163 } \ 164 } \ 165 } while (0) 166 167 168 #define DL_SORT(list, cmp) \ 169 DL_SORT2(list, cmp, prev, next) 170 171 #define DL_SORT2(list, cmp, prev, next) \ 172 do { \ 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; \ 178 if (list) { \ 179 _ls_insize = 1; \ 180 _ls_looping = 1; \ 181 while (_ls_looping) { \ 182 _CASTASGN(_ls_p,list); \ 183 list = NULL; \ 184 _ls_tail = NULL; \ 185 _ls_nmerges = 0; \ 186 while (_ls_p) { \ 187 _ls_nmerges++; \ 188 _ls_q = _ls_p; \ 189 _ls_psize = 0; \ 190 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 191 _ls_psize++; \ 192 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \ 193 if (!_ls_q) break; \ 194 } \ 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--; \ 206 } else { \ 207 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 208 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 209 } \ 210 if (_ls_tail) { \ 211 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ 212 } else { \ 213 _CASTASGN(list,_ls_e); \ 214 } \ 215 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \ 216 _ls_tail = _ls_e; \ 217 } \ 218 _ls_p = _ls_q; \ 219 } \ 220 _CASTASGN(list->prev, _ls_tail); \ 221 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \ 222 if (_ls_nmerges <= 1) { \ 223 _ls_looping=0; \ 224 } \ 225 _ls_insize *= 2; \ 226 } \ 227 } \ 228 } while (0) 229 230 #define CDL_SORT(list, cmp) \ 231 CDL_SORT2(list, cmp, prev, next) 232 233 #define CDL_SORT2(list, cmp, prev, next) \ 234 do { \ 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; \ 242 if (list) { \ 243 _ls_insize = 1; \ 244 _ls_looping = 1; \ 245 while (_ls_looping) { \ 246 _CASTASGN(_ls_p,list); \ 247 _CASTASGN(_ls_oldhead,list); \ 248 list = NULL; \ 249 _ls_tail = NULL; \ 250 _ls_nmerges = 0; \ 251 while (_ls_p) { \ 252 _ls_nmerges++; \ 253 _ls_q = _ls_p; \ 254 _ls_psize = 0; \ 255 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 256 _ls_psize++; \ 257 _SV(_ls_q,list); \ 258 if (_NEXT(_ls_q,list,next) == _ls_oldhead) { \ 259 _ls_q = NULL; \ 260 } else { \ 261 _ls_q = _NEXT(_ls_q,list,next); \ 262 } \ 263 _RS(list); \ 264 if (!_ls_q) break; \ 265 } \ 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; } \ 280 } else { \ 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; } \ 284 } \ 285 if (_ls_tail) { \ 286 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ 287 } else { \ 288 _CASTASGN(list,_ls_e); \ 289 } \ 290 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \ 291 _ls_tail = _ls_e; \ 292 } \ 293 _ls_p = _ls_q; \ 294 } \ 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) { \ 299 _ls_looping=0; \ 300 } \ 301 _ls_insize *= 2; \ 302 } \ 303 } \ 304 } while (0) 305 306 /****************************************************************************** 307 * singly linked list macros (non-circular) * 308 *****************************************************************************/ 309 #define LL_PREPEND(head,add) \ 310 LL_PREPEND2(head,add,next) 311 312 #define LL_PREPEND2(head,add,next) \ 313 do { \ 314 (add)->next = head; \ 315 head = add; \ 316 } while (0) 317 318 #define LL_CONCAT(head1,head2) \ 319 LL_CONCAT2(head1,head2,next) 320 321 #define LL_CONCAT2(head1,head2,next) \ 322 do { \ 323 LDECLTYPE(head1) _tmp; \ 324 if (head1) { \ 325 _tmp = head1; \ 326 while (_tmp->next) { _tmp = _tmp->next; } \ 327 _tmp->next=(head2); \ 328 } else { \ 329 (head1)=(head2); \ 330 } \ 331 } while (0) 332 333 #define LL_APPEND(head,add) \ 334 LL_APPEND2(head,add,next) 335 336 #define LL_APPEND2(head,add,next) \ 337 do { \ 338 LDECLTYPE(head) _tmp; \ 339 (add)->next=NULL; \ 340 if (head) { \ 341 _tmp = head; \ 342 while (_tmp->next) { _tmp = _tmp->next; } \ 343 _tmp->next=(add); \ 344 } else { \ 345 (head)=(add); \ 346 } \ 347 } while (0) 348 349 #define LL_DELETE(head,del) \ 350 LL_DELETE2(head,del,next) 351 352 #define LL_DELETE2(head,del,next) \ 353 do { \ 354 LDECLTYPE(head) _tmp; \ 355 if ((head) == (del)) { \ 356 (head)=(head)->next; \ 357 } else { \ 358 _tmp = head; \ 359 while (_tmp->next && (_tmp->next != (del))) { \ 360 _tmp = _tmp->next; \ 361 } \ 362 if (_tmp->next) { \ 363 _tmp->next = ((del)->next); \ 364 } \ 365 } \ 366 } while (0) 367 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) 371 372 #define LL_APPEND2_VS2008(head,add,next) \ 373 do { \ 374 if (head) { \ 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); \ 378 } else { \ 379 (head)=(add); \ 380 } \ 381 (add)->next=NULL; \ 382 } while (0) 383 384 #define LL_DELETE_VS2008(head,del) \ 385 LL_DELETE2_VS2008(head,del,next) 386 387 #define LL_DELETE2_VS2008(head,del,next) \ 388 do { \ 389 if ((head) == (del)) { \ 390 (head)=(head)->next; \ 391 } else { \ 392 char *_tmp = (char*)(head); \ 393 while ((head)->next && ((head)->next != (del))) { \ 394 head = (head)->next; \ 395 } \ 396 if ((head)->next) { \ 397 (head)->next = ((del)->next); \ 398 } \ 399 { \ 400 char **_head_alias = (char**)&(head); \ 401 *_head_alias = _tmp; \ 402 } \ 403 } \ 404 } while (0) 405 #ifdef NO_DECLTYPE 406 #undef LL_APPEND 407 #define LL_APPEND LL_APPEND_VS2008 408 #undef LL_DELETE 409 #define LL_DELETE LL_DELETE_VS2008 410 #undef LL_DELETE2 411 #define LL_DELETE2 LL_DELETE2_VS2008 412 #undef LL_APPEND2 413 #define LL_APPEND2 LL_APPEND2_VS2008 414 #undef LL_CONCAT /* no LL_CONCAT_VS2008 */ 415 #undef DL_CONCAT /* no DL_CONCAT_VS2008 */ 416 #endif 417 /* end VS2008 replacements */ 418 419 #define LL_COUNT(head,el,counter) \ 420 LL_COUNT2(head,el,counter,next) \ 421 422 #define LL_COUNT2(head,el,counter,next) \ 423 { \ 424 counter = 0; \ 425 LL_FOREACH2(head,el,next){ ++counter; } \ 426 } 427 428 #define LL_FOREACH(head,el) \ 429 LL_FOREACH2(head,el,next) 430 431 #define LL_FOREACH2(head,el,next) \ 432 for(el=head;el;el=(el)->next) 433 434 #define LL_FOREACH_SAFE(head,el,tmp) \ 435 LL_FOREACH_SAFE2(head,el,tmp,next) 436 437 #define LL_FOREACH_SAFE2(head,el,tmp,next) \ 438 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) 439 440 #define LL_SEARCH_SCALAR(head,out,field,val) \ 441 LL_SEARCH_SCALAR2(head,out,field,val,next) 442 443 #define LL_SEARCH_SCALAR2(head,out,field,val,next) \ 444 do { \ 445 LL_FOREACH2(head,out,next) { \ 446 if ((out)->field == (val)) break; \ 447 } \ 448 } while(0) 449 450 #define LL_SEARCH(head,out,elt,cmp) \ 451 LL_SEARCH2(head,out,elt,cmp,next) 452 453 #define LL_SEARCH2(head,out,elt,cmp,next) \ 454 do { \ 455 LL_FOREACH2(head,out,next) { \ 456 if ((cmp(out,elt))==0) break; \ 457 } \ 458 } while(0) 459 460 #define LL_REPLACE_ELEM(head, el, add) \ 461 do { \ 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)) { \ 468 (head) = (add); \ 469 } else { \ 470 _tmp = head; \ 471 while (_tmp->next && (_tmp->next != (el))) { \ 472 _tmp = _tmp->next; \ 473 } \ 474 if (_tmp->next) { \ 475 _tmp->next = (add); \ 476 } \ 477 } \ 478 } while (0) 479 480 #define LL_PREPEND_ELEM(head, el, add) \ 481 do { \ 482 LDECLTYPE(head) _tmp; \ 483 assert(head != NULL); \ 484 assert(el != NULL); \ 485 assert(add != NULL); \ 486 (add)->next = (el); \ 487 if ((head) == (el)) { \ 488 (head) = (add); \ 489 } else { \ 490 _tmp = head; \ 491 while (_tmp->next && (_tmp->next != (el))) { \ 492 _tmp = _tmp->next; \ 493 } \ 494 if (_tmp->next) { \ 495 _tmp->next = (add); \ 496 } \ 497 } \ 498 } while (0) \ 499 500 501 /****************************************************************************** 502 * doubly linked list macros (non-circular) * 503 *****************************************************************************/ 504 #define DL_PREPEND(head,add) \ 505 DL_PREPEND2(head,add,prev,next) 506 507 #define DL_PREPEND2(head,add,prev,next) \ 508 do { \ 509 (add)->next = head; \ 510 if (head) { \ 511 (add)->prev = (head)->prev; \ 512 (head)->prev = (add); \ 513 } else { \ 514 (add)->prev = (add); \ 515 } \ 516 (head) = (add); \ 517 } while (0) 518 519 #define DL_APPEND(head,add) \ 520 DL_APPEND2(head,add,prev,next) 521 522 #define DL_APPEND2(head,add,prev,next) \ 523 do { \ 524 if (head) { \ 525 (add)->prev = (head)->prev; \ 526 (head)->prev->next = (add); \ 527 (head)->prev = (add); \ 528 (add)->next = NULL; \ 529 } else { \ 530 (head)=(add); \ 531 (head)->prev = (head); \ 532 (head)->next = NULL; \ 533 } \ 534 } while (0) 535 536 #define DL_CONCAT(head1,head2) \ 537 DL_CONCAT2(head1,head2,prev,next) 538 539 #define DL_CONCAT2(head1,head2,prev,next) \ 540 do { \ 541 LDECLTYPE(head1) _tmp; \ 542 if (head2) { \ 543 if (head1) { \ 544 _tmp = (head2)->prev; \ 545 (head2)->prev = (head1)->prev; \ 546 (head1)->prev->next = (head2); \ 547 (head1)->prev = _tmp; \ 548 } else { \ 549 (head1)=(head2); \ 550 } \ 551 } \ 552 } while (0) 553 554 #define DL_DELETE(head,del) \ 555 DL_DELETE2(head,del,prev,next) 556 557 #define DL_DELETE2(head,del,prev,next) \ 558 do { \ 559 assert((del)->prev != NULL); \ 560 if ((del)->prev == (del)) { \ 561 (head)=NULL; \ 562 } else if ((del)==(head)) { \ 563 (del)->next->prev = (del)->prev; \ 564 (head) = (del)->next; \ 565 } else { \ 566 (del)->prev->next = (del)->next; \ 567 if ((del)->next) { \ 568 (del)->next->prev = (del)->prev; \ 569 } else { \ 570 (head)->prev = (del)->prev; \ 571 } \ 572 } \ 573 } while (0) 574 575 #define DL_COUNT(head,el,counter) \ 576 DL_COUNT2(head,el,counter,next) \ 577 578 #define DL_COUNT2(head,el,counter,next) \ 579 { \ 580 counter = 0; \ 581 DL_FOREACH2(head,el,next){ ++counter; } \ 582 } 583 584 #define DL_FOREACH(head,el) \ 585 DL_FOREACH2(head,el,next) 586 587 #define DL_FOREACH2(head,el,next) \ 588 for(el=head;el;el=(el)->next) 589 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) 593 594 #define DL_FOREACH_SAFE2(head,el,tmp,next) \ 595 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) 596 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 602 603 #define DL_REPLACE_ELEM(head, el, add) \ 604 do { \ 605 assert(head != NULL); \ 606 assert(el != NULL); \ 607 assert(add != NULL); \ 608 if ((head) == (el)) { \ 609 (head) = (add); \ 610 (add)->next = (el)->next; \ 611 if ((el)->next == NULL) { \ 612 (add)->prev = (add); \ 613 } else { \ 614 (add)->prev = (el)->prev; \ 615 (add)->next->prev = (add); \ 616 } \ 617 } else { \ 618 (add)->next = (el)->next; \ 619 (add)->prev = (el)->prev; \ 620 (add)->prev->next = (add); \ 621 if ((el)->next == NULL) { \ 622 (head)->prev = (add); \ 623 } else { \ 624 (add)->next->prev = (add); \ 625 } \ 626 } \ 627 } while (0) 628 629 #define DL_PREPEND_ELEM(head, el, add) \ 630 do { \ 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)) { \ 638 (head) = (add); \ 639 } else { \ 640 (add)->prev->next = (add); \ 641 } \ 642 } while (0) \ 643 644 645 /****************************************************************************** 646 * circular doubly linked list macros * 647 *****************************************************************************/ 648 #define CDL_PREPEND(head,add) \ 649 CDL_PREPEND2(head,add,prev,next) 650 651 #define CDL_PREPEND2(head,add,prev,next) \ 652 do { \ 653 if (head) { \ 654 (add)->prev = (head)->prev; \ 655 (add)->next = (head); \ 656 (head)->prev = (add); \ 657 (add)->prev->next = (add); \ 658 } else { \ 659 (add)->prev = (add); \ 660 (add)->next = (add); \ 661 } \ 662 (head)=(add); \ 663 } while (0) 664 665 #define CDL_DELETE(head,del) \ 666 CDL_DELETE2(head,del,prev,next) 667 668 #define CDL_DELETE2(head,del,prev,next) \ 669 do { \ 670 if ( ((head)==(del)) && ((head)->next == (head))) { \ 671 (head) = 0L; \ 672 } else { \ 673 (del)->next->prev = (del)->prev; \ 674 (del)->prev->next = (del)->next; \ 675 if ((del) == (head)) (head)=(del)->next; \ 676 } \ 677 } while (0) 678 679 #define CDL_COUNT(head,el,counter) \ 680 CDL_COUNT2(head,el,counter,next) \ 681 682 #define CDL_COUNT2(head, el, counter,next) \ 683 { \ 684 counter = 0; \ 685 CDL_FOREACH2(head,el,next){ ++counter; } \ 686 } 687 688 #define CDL_FOREACH(head,el) \ 689 CDL_FOREACH2(head,el,next) 690 691 #define CDL_FOREACH2(head,el,next) \ 692 for(el=head;el;el=((el)->next==head ? 0L : (el)->next)) 693 694 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \ 695 CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) 696 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)))) 701 702 #define CDL_SEARCH_SCALAR(head,out,field,val) \ 703 CDL_SEARCH_SCALAR2(head,out,field,val,next) 704 705 #define CDL_SEARCH_SCALAR2(head,out,field,val,next) \ 706 do { \ 707 CDL_FOREACH2(head,out,next) { \ 708 if ((out)->field == (val)) break; \ 709 } \ 710 } while(0) 711 712 #define CDL_SEARCH(head,out,elt,cmp) \ 713 CDL_SEARCH2(head,out,elt,cmp,next) 714 715 #define CDL_SEARCH2(head,out,elt,cmp,next) \ 716 do { \ 717 CDL_FOREACH2(head,out,next) { \ 718 if ((cmp(out,elt))==0) break; \ 719 } \ 720 } while(0) 721 722 #define CDL_REPLACE_ELEM(head, el, add) \ 723 do { \ 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); \ 730 (head) = (add); \ 731 } else { \ 732 (add)->next = (el)->next; \ 733 (add)->prev = (el)->prev; \ 734 (add)->next->prev = (add); \ 735 (add)->prev->next = (add); \ 736 if ((head) == (el)) { \ 737 (head) = (add); \ 738 } \ 739 } \ 740 } while (0) 741 742 #define CDL_PREPEND_ELEM(head, el, add) \ 743 do { \ 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)) { \ 752 (head) = (add); \ 753 } \ 754 } while (0) \ 755 756 #endif /* UTLIST_H */ 757