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