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