1 /* 2 * Copyright (c) 2007-2013 Troy D. Hanson 3 * http://troydhanson.github.com/uthash/ 4 * Copyright (c) 2021 The DPS8M Development Team 5 * 6 * All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions are met: 10 * 11 * * Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 15 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 16 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 17 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 18 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 19 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 20 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 21 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 22 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 23 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 24 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25 */ 26 27 #ifndef UTLIST_H 28 # define UTLIST_H 29 30 # define UTLIST_VERSION 1.9.8 31 32 # include <assert.h> 33 34 /* 35 * This file contains macros to manipulate singly and doubly-linked lists. 36 * 37 * 1. LL_ macros: singly-linked lists. 38 * 2. DL_ macros: doubly-linked lists. 39 * 3. CDL_ macros: circular doubly-linked lists. 40 * 41 * To use singly-linked lists, your structure must have a "next" pointer. 42 * To use doubly-linked lists, your structure must "prev" and "next" pointers. 43 * Either way, the pointer to the head of the list must be initialized to NULL. 44 * 45 * ----------------.EXAMPLE ------------------------- 46 * struct item { 47 * int id; 48 * struct item *prev, *next; 49 * } 50 * 51 * struct item *list = NULL: 52 * 53 * int main() { 54 * struct item *item; 55 * ... allocate and populate item ... 56 * DL_APPEND(list, item); 57 * } 58 * -------------------------------------------------- 59 * 60 * For doubly-linked lists, the append and delete macros are O(1) 61 * For singly-linked lists, append and delete are O(n) but prepend is O(1) 62 * The sort macro is O(n log(n)) for all types of single/double/circular lists. 63 */ 64 65 /* 66 * These macros use decltype or the earlier __typeof GNU extension. 67 * As decltype is only available in newer compilers (VS2010 or gcc 4.3+ 68 * when compiling c++ code), this code uses whatever method is needed 69 * or, for VS2008 where neither is available, uses casting workarounds. 70 */ 71 72 # ifdef _MSC_VER /* MS compiler */ 73 # if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ 74 # define LDECLTYPE(x) decltype(x) 75 # else /* VS2008 or older (or VS2010 in C mode) */ 76 # define NO_DECLTYPE 77 # define LDECLTYPE(x) char* 78 # endif 79 # else /* GNU, Sun and other compilers */ 80 # define LDECLTYPE(x) __typeof(x) 81 # endif 82 83 /* 84 * For VS2008 we use some workarounds to get around the lack of decltype, 85 * namely, we always reassign our tmp variable to the list head if we need 86 * to dereference its prev/next pointers, and save/restore the real head. 87 */ 88 89 # ifdef NO_DECLTYPE 90 # define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); } 91 # define _NEXT(elt,list,next) ((char*)((list)->next)) 92 # define _NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); } 93 /* #define _PREV(elt,list,prev) ((char*)((list)->prev)) */ 94 # define _PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); } 95 # define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; } 96 # define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); } 97 # else 98 # define _SV(elt,list) 99 # define _NEXT(elt,list,next) ((elt)->next) 100 # define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to) 101 /* #define _PREV(elt,list,prev) ((elt)->prev) */ 102 # define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to) 103 # define _RS(list) 104 # define _CASTASGN(a,b) (a)=(b) 105 # endif 106 107 /* 108 ****************************************************************************** 109 * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort * 110 * Unwieldy variable names used here to avoid shadowing passed-in variables. * 111 ****************************************************************************** 112 */ 113 114 # define LL_SORT(list, cmp) \ 115 LL_SORT2(list, cmp, next) 116 117 # define LL_SORT2(list, cmp, next) \ 118 do { \ 119 LDECLTYPE(list) _ls_p; \ 120 LDECLTYPE(list) _ls_q; \ 121 LDECLTYPE(list) _ls_e; \ 122 LDECLTYPE(list) _ls_tail; \ 123 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 124 if (list) { \ 125 _ls_insize = 1; \ 126 _ls_looping = 1; \ 127 while (_ls_looping) { \ 128 _CASTASGN(_ls_p,list); \ 129 list = NULL; \ 130 _ls_tail = NULL; \ 131 _ls_nmerges = 0; \ 132 while (_ls_p) { \ 133 _ls_nmerges++; \ 134 _ls_q = _ls_p; \ 135 _ls_psize = 0; \ 136 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 137 _ls_psize++; \ 138 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \ 139 if (!_ls_q) break; \ 140 } \ 141 _ls_qsize = _ls_insize; \ 142 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ 143 if (_ls_psize == 0) { \ 144 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 145 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 146 } else if (_ls_qsize == 0 || !_ls_q) { \ 147 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 148 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 149 } else if (cmp(_ls_p,_ls_q) <= 0) { \ 150 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 151 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 152 } else { \ 153 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 154 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 155 } \ 156 if (_ls_tail) { \ 157 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ 158 } else { \ 159 _CASTASGN(list,_ls_e); \ 160 } \ 161 _ls_tail = _ls_e; \ 162 } \ 163 _ls_p = _ls_q; \ 164 } \ 165 if (_ls_tail) { \ 166 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \ 167 } \ 168 if (_ls_nmerges <= 1) { \ 169 _ls_looping=0; \ 170 } \ 171 _ls_insize *= 2; \ 172 } \ 173 } \ 174 } while (0) 175 176 177 # define DL_SORT(list, cmp) \ 178 DL_SORT2(list, cmp, prev, next) 179 180 # define DL_SORT2(list, cmp, prev, next) \ 181 do { \ 182 LDECLTYPE(list) _ls_p; \ 183 LDECLTYPE(list) _ls_q; \ 184 LDECLTYPE(list) _ls_e; \ 185 LDECLTYPE(list) _ls_tail; \ 186 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 187 if (list) { \ 188 _ls_insize = 1; \ 189 _ls_looping = 1; \ 190 while (_ls_looping) { \ 191 _CASTASGN(_ls_p,list); \ 192 list = NULL; \ 193 _ls_tail = NULL; \ 194 _ls_nmerges = 0; \ 195 while (_ls_p) { \ 196 _ls_nmerges++; \ 197 _ls_q = _ls_p; \ 198 _ls_psize = 0; \ 199 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 200 _ls_psize++; \ 201 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \ 202 if (!_ls_q) break; \ 203 } \ 204 _ls_qsize = _ls_insize; \ 205 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ 206 if (_ls_psize == 0) { \ 207 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 208 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 209 } else if (_ls_qsize == 0 || !_ls_q) { \ 210 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 211 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 212 } else if (cmp(_ls_p,_ls_q) <= 0) { \ 213 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 214 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 215 } else { \ 216 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 217 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 218 } \ 219 if (_ls_tail) { \ 220 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ 221 } else { \ 222 _CASTASGN(list,_ls_e); \ 223 } \ 224 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \ 225 _ls_tail = _ls_e; \ 226 } \ 227 _ls_p = _ls_q; \ 228 } \ 229 _CASTASGN(list->prev, _ls_tail); \ 230 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \ 231 if (_ls_nmerges <= 1) { \ 232 _ls_looping=0; \ 233 } \ 234 _ls_insize *= 2; \ 235 } \ 236 } \ 237 } while (0) 238 239 # define CDL_SORT(list, cmp) \ 240 CDL_SORT2(list, cmp, prev, next) 241 242 # define CDL_SORT2(list, cmp, prev, next) \ 243 do { \ 244 LDECLTYPE(list) _ls_p; \ 245 LDECLTYPE(list) _ls_q; \ 246 LDECLTYPE(list) _ls_e; \ 247 LDECLTYPE(list) _ls_tail; \ 248 LDECLTYPE(list) _ls_oldhead; \ 249 LDECLTYPE(list) _tmp; \ 250 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 251 if (list) { \ 252 _ls_insize = 1; \ 253 _ls_looping = 1; \ 254 while (_ls_looping) { \ 255 _CASTASGN(_ls_p,list); \ 256 _CASTASGN(_ls_oldhead,list); \ 257 list = NULL; \ 258 _ls_tail = NULL; \ 259 _ls_nmerges = 0; \ 260 while (_ls_p) { \ 261 _ls_nmerges++; \ 262 _ls_q = _ls_p; \ 263 _ls_psize = 0; \ 264 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 265 _ls_psize++; \ 266 _SV(_ls_q,list); \ 267 if (_NEXT(_ls_q,list,next) == _ls_oldhead) { \ 268 _ls_q = NULL; \ 269 } else { \ 270 _ls_q = _NEXT(_ls_q,list,next); \ 271 } \ 272 _RS(list); \ 273 if (!_ls_q) break; \ 274 } \ 275 _ls_qsize = _ls_insize; \ 276 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ 277 if (_ls_psize == 0) { \ 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 } else if (_ls_qsize == 0 || !_ls_q) { \ 282 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 283 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 284 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ 285 } else if (cmp(_ls_p,_ls_q) <= 0) { \ 286 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ 287 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ 288 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ 289 } else { \ 290 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ 291 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ 292 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ 293 } \ 294 if (_ls_tail) { \ 295 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ 296 } else { \ 297 _CASTASGN(list,_ls_e); \ 298 } \ 299 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \ 300 _ls_tail = _ls_e; \ 301 } \ 302 _ls_p = _ls_q; \ 303 } \ 304 _CASTASGN(list->prev,_ls_tail); \ 305 _CASTASGN(_tmp,list); \ 306 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp,next); _RS(list); \ 307 if (_ls_nmerges <= 1) { \ 308 _ls_looping=0; \ 309 } \ 310 _ls_insize *= 2; \ 311 } \ 312 } \ 313 } while (0) 314 315 /* 316 ****************************************************************************** 317 * singly linked list macros (non-circular) * 318 ****************************************************************************** 319 */ 320 321 # define LL_PREPEND(head,add) \ 322 LL_PREPEND2(head,add,next) 323 324 # define LL_PREPEND2(head,add,next) \ 325 do { \ 326 (add)->next = head; \ 327 head = add; \ 328 } while (0) 329 330 # define LL_CONCAT(head1,head2) \ 331 LL_CONCAT2(head1,head2,next) 332 333 # define LL_CONCAT2(head1,head2,next) \ 334 do { \ 335 LDECLTYPE(head1) _tmp; \ 336 if (head1) { \ 337 _tmp = head1; \ 338 while (_tmp->next) { _tmp = _tmp->next; } \ 339 _tmp->next=(head2); \ 340 } else { \ 341 (head1)=(head2); \ 342 } \ 343 } while (0) 344 345 # define LL_APPEND(head,add) \ 346 LL_APPEND2(head,add,next) 347 348 # define LL_APPEND2(head,add,next) \ 349 do { \ 350 LDECLTYPE(head) _tmp; \ 351 (add)->next=NULL; \ 352 if (head) { \ 353 _tmp = head; \ 354 while (_tmp->next) { _tmp = _tmp->next; } \ 355 _tmp->next=(add); \ 356 } else { \ 357 (head)=(add); \ 358 } \ 359 } while (0) 360 361 # define LL_DELETE(head,del) \ 362 LL_DELETE2(head,del,next) 363 364 # define LL_DELETE2(head,del,next) \ 365 do { \ 366 LDECLTYPE(head) _tmp; \ 367 if ((head) == (del)) { \ 368 (head)=(head)->next; \ 369 } else { \ 370 _tmp = head; \ 371 while (_tmp->next && (_tmp->next != (del))) { \ 372 _tmp = _tmp->next; \ 373 } \ 374 if (_tmp->next) { \ 375 _tmp->next = ((del)->next); \ 376 } \ 377 } \ 378 } while (0) 379 380 /* 381 * Here are VS2008 replacements 382 * for LL_APPEND and LL_DELETE 383 */ 384 385 # define LL_APPEND_VS2008(head,add) \ 386 LL_APPEND2_VS2008(head,add,next) 387 388 # define LL_APPEND2_VS2008(head,add,next) \ 389 do { \ 390 if (head) { \ 391 (add)->next = head; /* use add->next as a temp variable */ \ 392 while ((add)->next->next) { (add)->next = (add)->next->next; } \ 393 (add)->next->next=(add); \ 394 } else { \ 395 (head)=(add); \ 396 } \ 397 (add)->next=NULL; \ 398 } while (0) 399 400 # define LL_DELETE_VS2008(head,del) \ 401 LL_DELETE2_VS2008(head,del,next) 402 403 # define LL_DELETE2_VS2008(head,del,next) \ 404 do { \ 405 if ((head) == (del)) { \ 406 (head)=(head)->next; \ 407 } else { \ 408 char *_tmp = (char*)(head); \ 409 while ((head)->next && ((head)->next != (del))) { \ 410 head = (head)->next; \ 411 } \ 412 if ((head)->next) { \ 413 (head)->next = ((del)->next); \ 414 } \ 415 { \ 416 char **_head_alias = (char**)&(head); \ 417 *_head_alias = _tmp; \ 418 } \ 419 } \ 420 } while (0) 421 # ifdef NO_DECLTYPE 422 # undef LL_APPEND 423 # define LL_APPEND LL_APPEND_VS2008 424 # undef LL_DELETE 425 # define LL_DELETE LL_DELETE_VS2008 426 # undef LL_DELETE2 427 # define LL_DELETE2_VS2008 428 # undef LL_APPEND2 429 # define LL_APPEND2 LL_APPEND2_VS2008 430 # undef LL_CONCAT /* no LL_CONCAT_VS2008 */ 431 # undef DL_CONCAT /* no DL_CONCAT_VS2008 */ 432 # endif 433 434 /* 435 * End VS2008 436 * replacements 437 */ 438 439 # define LL_FOREACH(head,el) \ 440 LL_FOREACH2(head,el,next) 441 442 # define LL_FOREACH2(head,el,next) \ 443 for(el=head;el;el=(el)->next) 444 445 # define LL_FOREACH_SAFE(head,el,tmp) \ 446 LL_FOREACH_SAFE2(head,el,tmp,next) 447 448 # define LL_FOREACH_SAFE2(head,el,tmp,next) \ 449 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) 450 451 # define LL_SEARCH_SCALAR(head,out,field,val) \ 452 LL_SEARCH_SCALAR2(head,out,field,val,next) 453 454 # define LL_SEARCH_SCALAR2(head,out,field,val,next) \ 455 do { \ 456 LL_FOREACH2(head,out,next) { \ 457 if ((out)->field == (val)) break; \ 458 } \ 459 } while(0) 460 461 # define LL_SEARCH(head,out,elt,cmp) \ 462 LL_SEARCH2(head,out,elt,cmp,next) 463 464 # define LL_SEARCH2(head,out,elt,cmp,next) \ 465 do { \ 466 LL_FOREACH2(head,out,next) { \ 467 if ((cmp(out,elt))==0) break; \ 468 } \ 469 } while(0) 470 471 # define LL_REPLACE_ELEM(head, el, add) \ 472 do { \ 473 LDECLTYPE(head) _tmp; \ 474 assert(head != NULL); \ 475 assert(el != NULL); \ 476 assert(add != NULL); \ 477 (add)->next = (el)->next; \ 478 if ((head) == (el)) { \ 479 (head) = (add); \ 480 } else { \ 481 _tmp = head; \ 482 while (_tmp->next && (_tmp->next != (el))) { \ 483 _tmp = _tmp->next; \ 484 } \ 485 if (_tmp->next) { \ 486 _tmp->next = (add); \ 487 } \ 488 } \ 489 } while (0) 490 491 # define LL_PREPEND_ELEM(head, el, add) \ 492 do { \ 493 LDECLTYPE(head) _tmp; \ 494 assert(head != NULL); \ 495 assert(el != NULL); \ 496 assert(add != NULL); \ 497 (add)->next = (el); \ 498 if ((head) == (el)) { \ 499 (head) = (add); \ 500 } else { \ 501 _tmp = head; \ 502 while (_tmp->next && (_tmp->next != (el))) { \ 503 _tmp = _tmp->next; \ 504 } \ 505 if (_tmp->next) { \ 506 _tmp->next = (add); \ 507 } \ 508 } \ 509 } while (0) \ 510 511 512 /* 513 ****************************************************************************** 514 * doubly linked list macros (non-circular) * 515 ****************************************************************************** 516 */ 517 518 # define DL_PREPEND(head,add) \ 519 DL_PREPEND2(head,add,prev,next) 520 521 # define DL_PREPEND2(head,add,prev,next) \ 522 do { \ 523 (add)->next = head; \ 524 if (head) { \ 525 (add)->prev = (head)->prev; \ 526 (head)->prev = (add); \ 527 } else { \ 528 (add)->prev = (add); \ 529 } \ 530 (head) = (add); \ 531 } while (0) 532 533 # define DL_APPEND(head,add) \ 534 DL_APPEND2(head,add,prev,next) 535 536 # define DL_APPEND2(head,add,prev,next) \ 537 do { \ 538 if (head) { \ 539 (add)->prev = (head)->prev; \ 540 (head)->prev->next = (add); \ 541 (head)->prev = (add); \ 542 (add)->next = NULL; \ 543 } else { \ 544 (head)=(add); \ 545 (head)->prev = (head); \ 546 (head)->next = NULL; \ 547 } \ 548 } while (0) 549 550 # define DL_CONCAT(head1,head2) \ 551 DL_CONCAT2(head1,head2,prev,next) 552 553 # define DL_CONCAT2(head1,head2,prev,next) \ 554 do { \ 555 LDECLTYPE(head1) _tmp; \ 556 if (head2) { \ 557 if (head1) { \ 558 _tmp = (head2)->prev; \ 559 (head2)->prev = (head1)->prev; \ 560 (head1)->prev->next = (head2); \ 561 (head1)->prev = _tmp; \ 562 } else { \ 563 (head1)=(head2); \ 564 } \ 565 } \ 566 } while (0) 567 568 # define DL_DELETE(head,del) \ 569 DL_DELETE2(head,del,prev,next) 570 571 # define DL_DELETE2(head,del,prev,next) \ 572 do { \ 573 assert((del)->prev != NULL); \ 574 if ((del)->prev == (del)) { \ 575 (head)=NULL; \ 576 } else if ((del)==(head)) { \ 577 (del)->next->prev = (del)->prev; \ 578 (head) = (del)->next; \ 579 } else { \ 580 (del)->prev->next = (del)->next; \ 581 if ((del)->next) { \ 582 (del)->next->prev = (del)->prev; \ 583 } else { \ 584 (head)->prev = (del)->prev; \ 585 } \ 586 } \ 587 } while (0) 588 589 590 # define DL_FOREACH(head,el) \ 591 DL_FOREACH2(head,el,next) 592 593 # define DL_FOREACH2(head,el,next) \ 594 for(el=head;el;el=(el)->next) 595 596 /* 597 * this version is safe for deleting 598 * the elements during iteration 599 */ 600 601 # define DL_FOREACH_SAFE(head,el,tmp) \ 602 DL_FOREACH_SAFE2(head,el,tmp,next) 603 604 # define DL_FOREACH_SAFE2(head,el,tmp,next) \ 605 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) 606 607 /* 608 * these are identical to their 609 * singly-linked list counterparts 610 */ 611 612 # define DL_SEARCH_SCALAR LL_SEARCH_SCALAR 613 # define DL_SEARCH LL_SEARCH 614 # define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2 615 # define DL_SEARCH2 LL_SEARCH2 616 617 # define DL_REPLACE_ELEM(head, el, add) \ 618 do { \ 619 assert(head != NULL); \ 620 assert(el != NULL); \ 621 assert(add != NULL); \ 622 if ((head) == (el)) { \ 623 (head) = (add); \ 624 (add)->next = (el)->next; \ 625 if ((el)->next == NULL) { \ 626 (add)->prev = (add); \ 627 } else { \ 628 (add)->prev = (el)->prev; \ 629 (add)->next->prev = (add); \ 630 } \ 631 } else { \ 632 (add)->next = (el)->next; \ 633 (add)->prev = (el)->prev; \ 634 (add)->prev->next = (add); \ 635 if ((el)->next == NULL) { \ 636 (head)->prev = (add); \ 637 } else { \ 638 (add)->next->prev = (add); \ 639 } \ 640 } \ 641 } while (0) 642 643 # define DL_PREPEND_ELEM(head, el, add) \ 644 do { \ 645 assert(head != NULL); \ 646 assert(el != NULL); \ 647 assert(add != NULL); \ 648 (add)->next = (el); \ 649 (add)->prev = (el)->prev; \ 650 (el)->prev = (add); \ 651 if ((head) == (el)) { \ 652 (head) = (add); \ 653 } else { \ 654 (add)->prev->next = (add); \ 655 } \ 656 } while (0) \ 657 658 659 /* 660 ****************************************************************************** 661 * circular doubly linked list macros * 662 ****************************************************************************** 663 */ 664 665 # define CDL_PREPEND(head,add) \ 666 CDL_PREPEND2(head,add,prev,next) 667 668 # define CDL_PREPEND2(head,add,prev,next) \ 669 do { \ 670 if (head) { \ 671 (add)->prev = (head)->prev; \ 672 (add)->next = (head); \ 673 (head)->prev = (add); \ 674 (add)->prev->next = (add); \ 675 } else { \ 676 (add)->prev = (add); \ 677 (add)->next = (add); \ 678 } \ 679 (head)=(add); \ 680 } while (0) 681 682 # define CDL_DELETE(head,del) \ 683 CDL_DELETE2(head,del,prev,next) 684 685 # define CDL_DELETE2(head,del,prev,next) \ 686 do { \ 687 if ( ((head)==(del)) && ((head)->next == (head))) { \ 688 (head) = 0L; \ 689 } else { \ 690 (del)->next->prev = (del)->prev; \ 691 (del)->prev->next = (del)->next; \ 692 if ((del) == (head)) (head)=(del)->next; \ 693 } \ 694 } while (0) 695 696 # define CDL_FOREACH(head,el) \ 697 CDL_FOREACH2(head,el,next) 698 699 # define CDL_FOREACH2(head,el,next) \ 700 for(el=head;el;el=((el)->next==head ? 0L : (el)->next)) 701 702 # define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \ 703 CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) 704 705 # define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \ 706 for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \ 707 (el) && ((tmp2)=(el)->next, 1); \ 708 ((el) = (((el)==(tmp1)) ? 0L : (tmp2)))) 709 710 # define CDL_SEARCH_SCALAR(head,out,field,val) \ 711 CDL_SEARCH_SCALAR2(head,out,field,val,next) 712 713 # define CDL_SEARCH_SCALAR2(head,out,field,val,next) \ 714 do { \ 715 CDL_FOREACH2(head,out,next) { \ 716 if ((out)->field == (val)) break; \ 717 } \ 718 } while(0) 719 720 # define CDL_SEARCH(head,out,elt,cmp) \ 721 CDL_SEARCH2(head,out,elt,cmp,next) 722 723 # define CDL_SEARCH2(head,out,elt,cmp,next) \ 724 do { \ 725 CDL_FOREACH2(head,out,next) { \ 726 if ((cmp(out,elt))==0) break; \ 727 } \ 728 } while(0) 729 730 # define CDL_REPLACE_ELEM(head, el, add) \ 731 do { \ 732 assert(head != NULL); \ 733 assert(el != NULL); \ 734 assert(add != NULL); \ 735 if ((el)->next == (el)) { \ 736 (add)->next = (add); \ 737 (add)->prev = (add); \ 738 (head) = (add); \ 739 } else { \ 740 (add)->next = (el)->next; \ 741 (add)->prev = (el)->prev; \ 742 (add)->next->prev = (add); \ 743 (add)->prev->next = (add); \ 744 if ((head) == (el)) { \ 745 (head) = (add); \ 746 } \ 747 } \ 748 } while (0) 749 750 # define CDL_PREPEND_ELEM(head, el, add) \ 751 do { \ 752 assert(head != NULL); \ 753 assert(el != NULL); \ 754 assert(add != NULL); \ 755 (add)->next = (el); \ 756 (add)->prev = (el)->prev; \ 757 (el)->prev = (add); \ 758 (add)->prev->next = (add); \ 759 if ((head) == (el)) { \ 760 (head) = (add); \ 761 } \ 762 } while (0) \ 763 764 #endif /* UTLIST_H */ 765