1 /* 2 Copyright (c) 2007-2016, 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 2.0.1 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 #endif 72 #elif defined(__ICCARM__) 73 #define NO_DECLTYPE 74 #else /* GNU, Sun and other compilers */ 75 #define LDECLTYPE(x) __typeof(x) 76 #endif 77 78 /* for VS2008 we use some workarounds to get around the lack of decltype, 79 * namely, we always reassign our tmp variable to the list head if we need 80 * to dereference its prev/next pointers, and save/restore the real head.*/ 81 #ifdef NO_DECLTYPE 82 #define IF_NO_DECLTYPE(x) x 83 #define LDECLTYPE(x) char* 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 IF_NO_DECLTYPE(x) 93 #define _SV(elt,list) 94 #define _NEXT(elt,list,next) ((elt)->next) 95 #define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to) 96 /* #define _PREV(elt,list,prev) ((elt)->prev) */ 97 #define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to) 98 #define _RS(list) 99 #define _CASTASGN(a,b) (a)=(b) 100 #endif 101 102 /****************************************************************************** 103 * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort * 104 * Unwieldy variable names used here to avoid shadowing passed-in variables. * 105 *****************************************************************************/ 106 #define LL_SORT(list, cmp) \ 107 LL_SORT2(list, cmp, next) 108 109 #define LL_SORT2(list, cmp, next) \ 110 do { \ 111 LDECLTYPE(list) _ls_p; \ 112 LDECLTYPE(list) _ls_q; \ 113 LDECLTYPE(list) _ls_e; \ 114 LDECLTYPE(list) _ls_tail; \ 115 IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;) \ 116 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 117 if (list) { \ 118 _ls_insize = 1; \ 119 _ls_looping = 1; \ 120 while (_ls_looping) { \ 121 _CASTASGN(_ls_p,list); \ 122 (list) = NULL; \ 123 _ls_tail = NULL; \ 124 _ls_nmerges = 0; \ 125 while (_ls_p) { \ 126 _ls_nmerges++; \ 127 _ls_q = _ls_p; \ 128 _ls_psize = 0; \ 129 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 130 _ls_psize++; \ 131 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \ 132 if (!_ls_q) break; \ 133 } \ 134 _ls_qsize = _ls_insize; \ 135 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ 136 if (_ls_psize == 0) { \ 137 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 138 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 139 } else if (_ls_qsize == 0 || !_ls_q) { \ 140 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 141 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 142 } else if (cmp(_ls_p,_ls_q) <= 0) { \ 143 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 144 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 145 } else { \ 146 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 147 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 148 } \ 149 if (_ls_tail) { \ 150 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ 151 } else { \ 152 _CASTASGN(list,_ls_e); \ 153 } \ 154 _ls_tail = _ls_e; \ 155 } \ 156 _ls_p = _ls_q; \ 157 } \ 158 if (_ls_tail) { \ 159 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \ 160 } \ 161 if (_ls_nmerges <= 1) { \ 162 _ls_looping=0; \ 163 } \ 164 _ls_insize *= 2; \ 165 } \ 166 } \ 167 } while (0) 168 169 170 #define DL_SORT(list, cmp) \ 171 DL_SORT2(list, cmp, prev, next) 172 173 #define DL_SORT2(list, cmp, prev, next) \ 174 do { \ 175 LDECLTYPE(list) _ls_p; \ 176 LDECLTYPE(list) _ls_q; \ 177 LDECLTYPE(list) _ls_e; \ 178 LDECLTYPE(list) _ls_tail; \ 179 IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;) \ 180 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 181 if (list) { \ 182 _ls_insize = 1; \ 183 _ls_looping = 1; \ 184 while (_ls_looping) { \ 185 _CASTASGN(_ls_p,list); \ 186 (list) = NULL; \ 187 _ls_tail = NULL; \ 188 _ls_nmerges = 0; \ 189 while (_ls_p) { \ 190 _ls_nmerges++; \ 191 _ls_q = _ls_p; \ 192 _ls_psize = 0; \ 193 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 194 _ls_psize++; \ 195 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \ 196 if (!_ls_q) break; \ 197 } \ 198 _ls_qsize = _ls_insize; \ 199 while ((_ls_psize > 0) || ((_ls_qsize > 0) && _ls_q)) { \ 200 if (_ls_psize == 0) { \ 201 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 202 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 203 } else if ((_ls_qsize == 0) || (!_ls_q)) { \ 204 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 205 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 206 } else if (cmp(_ls_p,_ls_q) <= 0) { \ 207 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 208 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 209 } else { \ 210 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 211 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 212 } \ 213 if (_ls_tail) { \ 214 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ 215 } else { \ 216 _CASTASGN(list,_ls_e); \ 217 } \ 218 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \ 219 _ls_tail = _ls_e; \ 220 } \ 221 _ls_p = _ls_q; \ 222 } \ 223 _CASTASGN((list)->prev, _ls_tail); \ 224 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \ 225 if (_ls_nmerges <= 1) { \ 226 _ls_looping=0; \ 227 } \ 228 _ls_insize *= 2; \ 229 } \ 230 } \ 231 } while (0) 232 233 #define CDL_SORT(list, cmp) \ 234 CDL_SORT2(list, cmp, prev, next) 235 236 #define CDL_SORT2(list, cmp, prev, next) \ 237 do { \ 238 LDECLTYPE(list) _ls_p; \ 239 LDECLTYPE(list) _ls_q; \ 240 LDECLTYPE(list) _ls_e; \ 241 LDECLTYPE(list) _ls_tail; \ 242 LDECLTYPE(list) _ls_oldhead; \ 243 LDECLTYPE(list) _tmp; \ 244 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 245 if (list) { \ 246 _ls_insize = 1; \ 247 _ls_looping = 1; \ 248 while (_ls_looping) { \ 249 _CASTASGN(_ls_p,list); \ 250 _CASTASGN(_ls_oldhead,list); \ 251 (list) = NULL; \ 252 _ls_tail = NULL; \ 253 _ls_nmerges = 0; \ 254 while (_ls_p) { \ 255 _ls_nmerges++; \ 256 _ls_q = _ls_p; \ 257 _ls_psize = 0; \ 258 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 259 _ls_psize++; \ 260 _SV(_ls_q,list); \ 261 if (_NEXT(_ls_q,list,next) == _ls_oldhead) { \ 262 _ls_q = NULL; \ 263 } else { \ 264 _ls_q = _NEXT(_ls_q,list,next); \ 265 } \ 266 _RS(list); \ 267 if (!_ls_q) break; \ 268 } \ 269 _ls_qsize = _ls_insize; \ 270 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ 271 if (_ls_psize == 0) { \ 272 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 273 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 274 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ 275 } else if (_ls_qsize == 0 || !_ls_q) { \ 276 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 277 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 278 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ 279 } else if (cmp(_ls_p,_ls_q) <= 0) { \ 280 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 281 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 282 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ 283 } else { \ 284 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 285 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 286 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ 287 } \ 288 if (_ls_tail) { \ 289 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ 290 } else { \ 291 _CASTASGN(list,_ls_e); \ 292 } \ 293 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \ 294 _ls_tail = _ls_e; \ 295 } \ 296 _ls_p = _ls_q; \ 297 } \ 298 _CASTASGN((list)->prev,_ls_tail); \ 299 _CASTASGN(_tmp,list); \ 300 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp,next); _RS(list); \ 301 if (_ls_nmerges <= 1) { \ 302 _ls_looping=0; \ 303 } \ 304 _ls_insize *= 2; \ 305 } \ 306 } \ 307 } while (0) 308 309 /****************************************************************************** 310 * singly linked list macros (non-circular) * 311 *****************************************************************************/ 312 #define LL_PREPEND(head,add) \ 313 LL_PREPEND2(head,add,next) 314 315 #define LL_PREPEND2(head,add,next) \ 316 do { \ 317 (add)->next = (head); \ 318 (head) = (add); \ 319 } while (0) 320 321 #define LL_CONCAT(head1,head2) \ 322 LL_CONCAT2(head1,head2,next) 323 324 #define LL_CONCAT2(head1,head2,next) \ 325 do { \ 326 LDECLTYPE(head1) _tmp; \ 327 if (head1) { \ 328 _tmp = (head1); \ 329 while (_tmp->next) { _tmp = _tmp->next; } \ 330 _tmp->next=(head2); \ 331 } else { \ 332 (head1)=(head2); \ 333 } \ 334 } while (0) 335 336 #define LL_APPEND(head,add) \ 337 LL_APPEND2(head,add,next) 338 339 #define LL_APPEND2(head,add,next) \ 340 do { \ 341 LDECLTYPE(head) _tmp; \ 342 (add)->next=NULL; \ 343 if (head) { \ 344 _tmp = (head); \ 345 while (_tmp->next) { _tmp = _tmp->next; } \ 346 _tmp->next=(add); \ 347 } else { \ 348 (head)=(add); \ 349 } \ 350 } while (0) 351 352 #define LL_DELETE(head,del) \ 353 LL_DELETE2(head,del,next) 354 355 #define LL_DELETE2(head,del,next) \ 356 do { \ 357 LDECLTYPE(head) _tmp; \ 358 if ((head) == (del)) { \ 359 (head)=(head)->next; \ 360 } else { \ 361 _tmp = (head); \ 362 while (_tmp->next && (_tmp->next != (del))) { \ 363 _tmp = _tmp->next; \ 364 } \ 365 if (_tmp->next) { \ 366 _tmp->next = (del)->next; \ 367 } \ 368 } \ 369 } while (0) 370 371 #define LL_COUNT(head,el,counter) \ 372 LL_COUNT2(head,el,counter,next) \ 373 374 #define LL_COUNT2(head,el,counter,next) \ 375 do { \ 376 (counter) = 0; \ 377 LL_FOREACH2(head,el,next) { ++(counter); } \ 378 } while (0) 379 380 #define LL_FOREACH(head,el) \ 381 LL_FOREACH2(head,el,next) 382 383 #define LL_FOREACH2(head,el,next) \ 384 for ((el) = (head); el; (el) = (el)->next) 385 386 #define LL_FOREACH_SAFE(head,el,tmp) \ 387 LL_FOREACH_SAFE2(head,el,tmp,next) 388 389 #define LL_FOREACH_SAFE2(head,el,tmp,next) \ 390 for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp)) 391 392 #define LL_SEARCH_SCALAR(head,out,field,val) \ 393 LL_SEARCH_SCALAR2(head,out,field,val,next) 394 395 #define LL_SEARCH_SCALAR2(head,out,field,val,next) \ 396 do { \ 397 LL_FOREACH2(head,out,next) { \ 398 if ((out)->field == (val)) break; \ 399 } \ 400 } while (0) 401 402 #define LL_SEARCH(head,out,elt,cmp) \ 403 LL_SEARCH2(head,out,elt,cmp,next) 404 405 #define LL_SEARCH2(head,out,elt,cmp,next) \ 406 do { \ 407 LL_FOREACH2(head,out,next) { \ 408 if ((cmp(out,elt))==0) break; \ 409 } \ 410 } while (0) 411 412 #define LL_REPLACE_ELEM2(head, el, add, next) \ 413 do { \ 414 LDECLTYPE(head) _tmp; \ 415 assert((head) != NULL); \ 416 assert((el) != NULL); \ 417 assert((add) != NULL); \ 418 (add)->next = (el)->next; \ 419 if ((head) == (el)) { \ 420 (head) = (add); \ 421 } else { \ 422 _tmp = (head); \ 423 while (_tmp->next && (_tmp->next != (el))) { \ 424 _tmp = _tmp->next; \ 425 } \ 426 if (_tmp->next) { \ 427 _tmp->next = (add); \ 428 } \ 429 } \ 430 } while (0) 431 432 #define LL_REPLACE_ELEM(head, el, add) \ 433 LL_REPLACE_ELEM2(head, el, add, next) 434 435 #define LL_PREPEND_ELEM2(head, el, add, next) \ 436 do { \ 437 if (el) { \ 438 LDECLTYPE(head) _tmp; \ 439 assert((head) != NULL); \ 440 assert((add) != NULL); \ 441 (add)->next = (el); \ 442 if ((head) == (el)) { \ 443 (head) = (add); \ 444 } else { \ 445 _tmp = (head); \ 446 while (_tmp->next && (_tmp->next != (el))) { \ 447 _tmp = _tmp->next; \ 448 } \ 449 if (_tmp->next) { \ 450 _tmp->next = (add); \ 451 } \ 452 } \ 453 } else { \ 454 LL_APPEND2(head, add, next); \ 455 } \ 456 } while (0) \ 457 458 #define LL_PREPEND_ELEM(head, el, add) \ 459 LL_PREPEND_ELEM2(head, el, add, next) 460 461 #define LL_APPEND_ELEM2(head, el, add, next) \ 462 do { \ 463 if (el) { \ 464 assert((head) != NULL); \ 465 assert((add) != NULL); \ 466 (add)->next = (el)->next; \ 467 (el)->next = (add); \ 468 } else { \ 469 LL_PREPEND2(head, add, next); \ 470 } \ 471 } while (0) \ 472 473 #define LL_APPEND_ELEM(head, el, add) \ 474 LL_APPEND_ELEM2(head, el, add, next) 475 476 #ifdef NO_DECLTYPE 477 /* Here are VS2008 / NO_DECLTYPE replacements for a few functions */ 478 479 #undef LL_CONCAT2 480 #define LL_CONCAT2(head1,head2,next) \ 481 do { \ 482 char *_tmp; \ 483 if (head1) { \ 484 _tmp = (char*)(head1); \ 485 while ((head1)->next) { (head1) = (head1)->next; } \ 486 (head1)->next = (head2); \ 487 _RS(head1); \ 488 } else { \ 489 (head1)=(head2); \ 490 } \ 491 } while (0) 492 493 #undef LL_APPEND2 494 #define LL_APPEND2(head,add,next) \ 495 do { \ 496 if (head) { \ 497 (add)->next = head; /* use add->next as a temp variable */ \ 498 while ((add)->next->next) { (add)->next = (add)->next->next; } \ 499 (add)->next->next=(add); \ 500 } else { \ 501 (head)=(add); \ 502 } \ 503 (add)->next=NULL; \ 504 } while (0) 505 506 #undef LL_DELETE2 507 #define LL_DELETE2(head,del,next) \ 508 do { \ 509 if ((head) == (del)) { \ 510 (head)=(head)->next; \ 511 } else { \ 512 char *_tmp = (char*)(head); \ 513 while ((head)->next && ((head)->next != (del))) { \ 514 (head) = (head)->next; \ 515 } \ 516 if ((head)->next) { \ 517 (head)->next = ((del)->next); \ 518 } \ 519 _RS(head); \ 520 } \ 521 } while (0) 522 523 #undef LL_REPLACE_ELEM2 524 #define LL_REPLACE_ELEM2(head, el, add, next) \ 525 do { \ 526 assert((head) != NULL); \ 527 assert((el) != NULL); \ 528 assert((add) != NULL); \ 529 if ((head) == (el)) { \ 530 (head) = (add); \ 531 } else { \ 532 (add)->next = head; \ 533 while ((add)->next->next && ((add)->next->next != (el))) { \ 534 (add)->next = (add)->next->next; \ 535 } \ 536 if ((add)->next->next) { \ 537 (add)->next->next = (add); \ 538 } \ 539 } \ 540 (add)->next = (el)->next; \ 541 } while (0) 542 543 #undef LL_PREPEND_ELEM2 544 #define LL_PREPEND_ELEM2(head, el, add, next) \ 545 do { \ 546 if (el) { \ 547 assert((head) != NULL); \ 548 assert((add) != NULL); \ 549 if ((head) == (el)) { \ 550 (head) = (add); \ 551 } else { \ 552 (add)->next = (head); \ 553 while ((add)->next->next && ((add)->next->next != (el))) { \ 554 (add)->next = (add)->next->next; \ 555 } \ 556 if ((add)->next->next) { \ 557 (add)->next->next = (add); \ 558 } \ 559 } \ 560 (add)->next = (el); \ 561 } else { \ 562 LL_APPEND2(head, add, next); \ 563 } \ 564 } while (0) \ 565 566 #endif /* NO_DECLTYPE */ 567 568 /****************************************************************************** 569 * doubly linked list macros (non-circular) * 570 *****************************************************************************/ 571 #define DL_PREPEND(head,add) \ 572 DL_PREPEND2(head,add,prev,next) 573 574 #define DL_PREPEND2(head,add,prev,next) \ 575 do { \ 576 (add)->next = (head); \ 577 if (head) { \ 578 (add)->prev = (head)->prev; \ 579 (head)->prev = (add); \ 580 } else { \ 581 (add)->prev = (add); \ 582 } \ 583 (head) = (add); \ 584 } while (0) 585 586 #define DL_APPEND(head,add) \ 587 DL_APPEND2(head,add,prev,next) 588 589 #define DL_APPEND2(head,add,prev,next) \ 590 do { \ 591 if (head) { \ 592 (add)->prev = (head)->prev; \ 593 (head)->prev->next = (add); \ 594 (head)->prev = (add); \ 595 (add)->next = NULL; \ 596 } else { \ 597 (head)=(add); \ 598 (head)->prev = (head); \ 599 (head)->next = NULL; \ 600 } \ 601 } while (0) 602 603 #define DL_CONCAT(head1,head2) \ 604 DL_CONCAT2(head1,head2,prev,next) 605 606 #define DL_CONCAT2(head1,head2,prev,next) \ 607 do { \ 608 LDECLTYPE(head1) _tmp; \ 609 if (head2) { \ 610 if (head1) { \ 611 _CASTASGN(_tmp, (head2)->prev); \ 612 (head2)->prev = (head1)->prev; \ 613 (head1)->prev->next = (head2); \ 614 _CASTASGN((head1)->prev, _tmp); \ 615 } else { \ 616 (head1)=(head2); \ 617 } \ 618 } \ 619 } while (0) 620 621 #define DL_DELETE(head,del) \ 622 DL_DELETE2(head,del,prev,next) 623 624 #define DL_DELETE2(head,del,prev,next) \ 625 do { \ 626 assert((del)->prev != NULL); \ 627 if ((del)->prev == (del)) { \ 628 (head)=NULL; \ 629 } else if ((del)==(head)) { \ 630 (del)->next->prev = (del)->prev; \ 631 (head) = (del)->next; \ 632 } else { \ 633 (del)->prev->next = (del)->next; \ 634 if ((del)->next) { \ 635 (del)->next->prev = (del)->prev; \ 636 } else { \ 637 (head)->prev = (del)->prev; \ 638 } \ 639 } \ 640 } while (0) 641 642 #define DL_COUNT(head,el,counter) \ 643 DL_COUNT2(head,el,counter,next) \ 644 645 #define DL_COUNT2(head,el,counter,next) \ 646 do { \ 647 (counter) = 0; \ 648 DL_FOREACH2(head,el,next) { ++(counter); } \ 649 } while (0) 650 651 #define DL_FOREACH(head,el) \ 652 DL_FOREACH2(head,el,next) 653 654 #define DL_FOREACH2(head,el,next) \ 655 for ((el) = (head); el; (el) = (el)->next) 656 657 /* this version is safe for deleting the elements during iteration */ 658 #define DL_FOREACH_SAFE(head,el,tmp) \ 659 DL_FOREACH_SAFE2(head,el,tmp,next) 660 661 #define DL_FOREACH_SAFE2(head,el,tmp,next) \ 662 for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp)) 663 664 /* these are identical to their singly-linked list counterparts */ 665 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR 666 #define DL_SEARCH LL_SEARCH 667 #define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2 668 #define DL_SEARCH2 LL_SEARCH2 669 670 #define DL_REPLACE_ELEM2(head, el, add, prev, next) \ 671 do { \ 672 assert((head) != NULL); \ 673 assert((el) != NULL); \ 674 assert((add) != NULL); \ 675 if ((head) == (el)) { \ 676 (head) = (add); \ 677 (add)->next = (el)->next; \ 678 if ((el)->next == NULL) { \ 679 (add)->prev = (add); \ 680 } else { \ 681 (add)->prev = (el)->prev; \ 682 (add)->next->prev = (add); \ 683 } \ 684 } else { \ 685 (add)->next = (el)->next; \ 686 (add)->prev = (el)->prev; \ 687 (add)->prev->next = (add); \ 688 if ((el)->next == NULL) { \ 689 (head)->prev = (add); \ 690 } else { \ 691 (add)->next->prev = (add); \ 692 } \ 693 } \ 694 } while (0) 695 696 #define DL_REPLACE_ELEM(head, el, add) \ 697 DL_REPLACE_ELEM2(head, el, add, prev, next) 698 699 #define DL_PREPEND_ELEM2(head, el, add, prev, next) \ 700 do { \ 701 if (el) { \ 702 assert((head) != NULL); \ 703 assert((add) != NULL); \ 704 (add)->next = (el); \ 705 (add)->prev = (el)->prev; \ 706 (el)->prev = (add); \ 707 if ((head) == (el)) { \ 708 (head) = (add); \ 709 } else { \ 710 (add)->prev->next = (add); \ 711 } \ 712 } else { \ 713 DL_APPEND2(head, add, prev, next); \ 714 } \ 715 } while (0) \ 716 717 #define DL_PREPEND_ELEM(head, el, add) \ 718 DL_PREPEND_ELEM2(head, el, add, prev, next) 719 720 #define DL_APPEND_ELEM2(head, el, add, prev, next) \ 721 do { \ 722 if (el) { \ 723 assert((head) != NULL); \ 724 assert((add) != NULL); \ 725 (add)->next = (el)->next; \ 726 (add)->prev = (el); \ 727 (el)->next = (add); \ 728 if ((add)->next) { \ 729 (add)->next->prev = (add); \ 730 } else { \ 731 (head)->prev = (add); \ 732 } \ 733 } else { \ 734 DL_PREPEND2(head, add, prev, next); \ 735 } \ 736 } while (0) \ 737 738 #define DL_APPEND_ELEM(head, el, add) \ 739 DL_APPEND_ELEM2(head, el, add, prev, next) 740 741 /****************************************************************************** 742 * circular doubly linked list macros * 743 *****************************************************************************/ 744 #define CDL_APPEND(head,add) \ 745 CDL_APPEND2(head,add,prev,next) 746 747 #define CDL_APPEND2(head,add,prev,next) \ 748 do { \ 749 if (head) { \ 750 (add)->prev = (head)->prev; \ 751 (add)->next = (head); \ 752 (head)->prev = (add); \ 753 (add)->prev->next = (add); \ 754 } else { \ 755 (add)->prev = (add); \ 756 (add)->next = (add); \ 757 (head) = (add); \ 758 } \ 759 } while (0) 760 761 #define CDL_PREPEND(head,add) \ 762 CDL_PREPEND2(head,add,prev,next) 763 764 #define CDL_PREPEND2(head,add,prev,next) \ 765 do { \ 766 if (head) { \ 767 (add)->prev = (head)->prev; \ 768 (add)->next = (head); \ 769 (head)->prev = (add); \ 770 (add)->prev->next = (add); \ 771 } else { \ 772 (add)->prev = (add); \ 773 (add)->next = (add); \ 774 } \ 775 (head) = (add); \ 776 } while (0) 777 778 #define CDL_DELETE(head,del) \ 779 CDL_DELETE2(head,del,prev,next) 780 781 #define CDL_DELETE2(head,del,prev,next) \ 782 do { \ 783 if (((head)==(del)) && ((head)->next == (head))) { \ 784 (head) = NULL; \ 785 } else { \ 786 (del)->next->prev = (del)->prev; \ 787 (del)->prev->next = (del)->next; \ 788 if ((del) == (head)) (head)=(del)->next; \ 789 } \ 790 } while (0) 791 792 #define CDL_COUNT(head,el,counter) \ 793 CDL_COUNT2(head,el,counter,next) \ 794 795 #define CDL_COUNT2(head, el, counter,next) \ 796 do { \ 797 (counter) = 0; \ 798 CDL_FOREACH2(head,el,next) { ++(counter); } \ 799 } while (0) 800 801 #define CDL_FOREACH(head,el) \ 802 CDL_FOREACH2(head,el,next) 803 804 #define CDL_FOREACH2(head,el,next) \ 805 for ((el)=(head);el;(el)=(((el)->next==(head)) ? NULL : (el)->next)) 806 807 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \ 808 CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) 809 810 #define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \ 811 for ((el) = (head), (tmp1) = (head) ? (head)->prev : NULL; \ 812 (el) && ((tmp2) = (el)->next, 1); \ 813 (el) = ((el) == (tmp1) ? NULL : (tmp2))) 814 815 #define CDL_SEARCH_SCALAR(head,out,field,val) \ 816 CDL_SEARCH_SCALAR2(head,out,field,val,next) 817 818 #define CDL_SEARCH_SCALAR2(head,out,field,val,next) \ 819 do { \ 820 CDL_FOREACH2(head,out,next) { \ 821 if ((out)->field == (val)) break; \ 822 } \ 823 } while (0) 824 825 #define CDL_SEARCH(head,out,elt,cmp) \ 826 CDL_SEARCH2(head,out,elt,cmp,next) 827 828 #define CDL_SEARCH2(head,out,elt,cmp,next) \ 829 do { \ 830 CDL_FOREACH2(head,out,next) { \ 831 if ((cmp(out,elt))==0) break; \ 832 } \ 833 } while (0) 834 835 #define CDL_REPLACE_ELEM2(head, el, add, prev, next) \ 836 do { \ 837 assert((head) != NULL); \ 838 assert((el) != NULL); \ 839 assert((add) != NULL); \ 840 if ((el)->next == (el)) { \ 841 (add)->next = (add); \ 842 (add)->prev = (add); \ 843 (head) = (add); \ 844 } else { \ 845 (add)->next = (el)->next; \ 846 (add)->prev = (el)->prev; \ 847 (add)->next->prev = (add); \ 848 (add)->prev->next = (add); \ 849 if ((head) == (el)) { \ 850 (head) = (add); \ 851 } \ 852 } \ 853 } while (0) 854 855 #define CDL_REPLACE_ELEM(head, el, add) \ 856 CDL_REPLACE_ELEM2(head, el, add, prev, next) 857 858 #define CDL_PREPEND_ELEM2(head, el, add, prev, next) \ 859 do { \ 860 if (el) { \ 861 assert((head) != NULL); \ 862 assert((add) != NULL); \ 863 (add)->next = (el); \ 864 (add)->prev = (el)->prev; \ 865 (el)->prev = (add); \ 866 (add)->prev->next = (add); \ 867 if ((head) == (el)) { \ 868 (head) = (add); \ 869 } \ 870 } else { \ 871 CDL_APPEND2(head, add, prev, next); \ 872 } \ 873 } while (0) 874 875 #define CDL_PREPEND_ELEM(head, el, add) \ 876 CDL_PREPEND_ELEM2(head, el, add, prev, next) 877 878 #define CDL_APPEND_ELEM2(head, el, add, prev, next) \ 879 do { \ 880 if (el) { \ 881 assert((head) != NULL); \ 882 assert((add) != NULL); \ 883 (add)->next = (el)->next; \ 884 (add)->prev = (el); \ 885 (el)->next = (add); \ 886 (add)->next->prev = (add); \ 887 } else { \ 888 CDL_PREPEND2(head, add, prev, next); \ 889 } \ 890 } while (0) 891 892 #define CDL_APPEND_ELEM(head, el, add) \ 893 CDL_APPEND_ELEM2(head, el, add, prev, next) 894 895 #endif /* UTLIST_H */ 896