1 /* 2 Copyright (c) 2007-2017, 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.2 28 29 #ifdef HAVE_ASSERT_H 30 #include <assert.h> 31 #endif /* HAVE_ASSERT_H */ 32 33 /* 34 * This file contains macros to manipulate singly and doubly-linked lists. 35 * 36 * 1. LL_ macros: singly-linked lists. 37 * 2. DL_ macros: doubly-linked lists. 38 * 3. CDL_ macros: circular doubly-linked lists. 39 * 40 * To use singly-linked lists, your structure must have a "next" pointer. 41 * To use doubly-linked lists, your structure must "prev" and "next" pointers. 42 * Either way, the pointer to the head of the list must be initialized to NULL. 43 * 44 * ----------------.EXAMPLE ------------------------- 45 * struct item { 46 * int id; 47 * struct item *prev, *next; 48 * } 49 * 50 * struct item *list = NULL: 51 * 52 * int main() { 53 * struct item *item; 54 * ... allocate and populate item ... 55 * DL_APPEND(list, item); 56 * } 57 * -------------------------------------------------- 58 * 59 * For doubly-linked lists, the append and delete macros are O(1) 60 * For singly-linked lists, append and delete are O(n) but prepend is O(1) 61 * The sort macro is O(n log(n)) for all types of single/double/circular lists. 62 */ 63 64 /* These macros use decltype or the earlier __typeof GNU extension. 65 As decltype is only available in newer compilers (VS2010 or gcc 4.3+ 66 when compiling c++ source) this code uses whatever method is needed 67 or, for VS2008 where neither is available, uses casting workarounds. */ 68 #if !defined(LDECLTYPE) && !defined(NO_DECLTYPE) 69 #if defined(_MSC_VER) /* MS compiler */ 70 #if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ 71 #define LDECLTYPE(x) decltype(x) 72 #else /* VS2008 or older (or VS2010 in C mode) */ 73 #define NO_DECLTYPE 74 #endif 75 #elif defined(__BORLANDC__) || defined(__ICCARM__) || defined(__LCC__) || defined(__WATCOMC__) 76 #define NO_DECLTYPE 77 #else /* GNU, Sun and other compilers */ 78 #define LDECLTYPE(x) __typeof(x) 79 #endif 80 #endif 81 82 /* for VS2008 we use some workarounds to get around the lack of decltype, 83 * namely, we always reassign our tmp variable to the list head if we need 84 * to dereference its prev/next pointers, and save/restore the real head.*/ 85 #ifdef NO_DECLTYPE 86 #define IF_NO_DECLTYPE(x) x 87 #define LDECLTYPE(x) char* 88 #define UTLIST_SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); } 89 #define UTLIST_NEXT(elt,list,next) ((char*)((list)->next)) 90 #define UTLIST_NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); } 91 /* #define UTLIST_PREV(elt,list,prev) ((char*)((list)->prev)) */ 92 #define UTLIST_PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); } 93 #define UTLIST_RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; } 94 #define UTLIST_CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); } 95 #else 96 #define IF_NO_DECLTYPE(x) 97 #define UTLIST_SV(elt,list) 98 #define UTLIST_NEXT(elt,list,next) ((elt)->next) 99 #define UTLIST_NEXTASGN(elt,list,to,next) ((elt)->next)=(to) 100 /* #define UTLIST_PREV(elt,list,prev) ((elt)->prev) */ 101 #define UTLIST_PREVASGN(elt,list,to,prev) ((elt)->prev)=(to) 102 #define UTLIST_RS(list) 103 #define UTLIST_CASTASGN(a,b) (a)=(b) 104 #endif 105 106 /****************************************************************************** 107 * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort * 108 * Unwieldy variable names used here to avoid shadowing passed-in variables. * 109 *****************************************************************************/ 110 #define LL_SORT(list, cmp) \ 111 LL_SORT2(list, cmp, next) 112 113 #define LL_SORT2(list, cmp, next) \ 114 do { \ 115 LDECLTYPE(list) _ls_p; \ 116 LDECLTYPE(list) _ls_q; \ 117 LDECLTYPE(list) _ls_e; \ 118 LDECLTYPE(list) _ls_tail; \ 119 IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;) \ 120 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 121 if (list) { \ 122 _ls_insize = 1; \ 123 _ls_looping = 1; \ 124 while (_ls_looping) { \ 125 UTLIST_CASTASGN(_ls_p,list); \ 126 (list) = NULL; \ 127 _ls_tail = NULL; \ 128 _ls_nmerges = 0; \ 129 while (_ls_p) { \ 130 _ls_nmerges++; \ 131 _ls_q = _ls_p; \ 132 _ls_psize = 0; \ 133 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 134 _ls_psize++; \ 135 UTLIST_SV(_ls_q,list); _ls_q = UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); \ 136 if (!_ls_q) break; \ 137 } \ 138 _ls_qsize = _ls_insize; \ 139 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ 140 if (_ls_psize == 0) { \ 141 _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ 142 UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ 143 } else if (_ls_qsize == 0 || !_ls_q) { \ 144 _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ 145 UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ 146 } else if (cmp(_ls_p,_ls_q) <= 0) { \ 147 _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ 148 UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ 149 } else { \ 150 _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ 151 UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ 152 } \ 153 if (_ls_tail) { \ 154 UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \ 155 } else { \ 156 UTLIST_CASTASGN(list,_ls_e); \ 157 } \ 158 _ls_tail = _ls_e; \ 159 } \ 160 _ls_p = _ls_q; \ 161 } \ 162 if (_ls_tail) { \ 163 UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,NULL,next); UTLIST_RS(list); \ 164 } \ 165 if (_ls_nmerges <= 1) { \ 166 _ls_looping=0; \ 167 } \ 168 _ls_insize *= 2; \ 169 } \ 170 } \ 171 } while (0) 172 173 174 #define DL_SORT(list, cmp) \ 175 DL_SORT2(list, cmp, prev, next) 176 177 #define DL_SORT2(list, cmp, prev, next) \ 178 do { \ 179 LDECLTYPE(list) _ls_p; \ 180 LDECLTYPE(list) _ls_q; \ 181 LDECLTYPE(list) _ls_e; \ 182 LDECLTYPE(list) _ls_tail; \ 183 IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;) \ 184 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 185 if (list) { \ 186 _ls_insize = 1; \ 187 _ls_looping = 1; \ 188 while (_ls_looping) { \ 189 UTLIST_CASTASGN(_ls_p,list); \ 190 (list) = NULL; \ 191 _ls_tail = NULL; \ 192 _ls_nmerges = 0; \ 193 while (_ls_p) { \ 194 _ls_nmerges++; \ 195 _ls_q = _ls_p; \ 196 _ls_psize = 0; \ 197 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 198 _ls_psize++; \ 199 UTLIST_SV(_ls_q,list); _ls_q = UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); \ 200 if (!_ls_q) break; \ 201 } \ 202 _ls_qsize = _ls_insize; \ 203 while ((_ls_psize > 0) || ((_ls_qsize > 0) && _ls_q)) { \ 204 if (_ls_psize == 0) { \ 205 _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ 206 UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ 207 } else if ((_ls_qsize == 0) || (!_ls_q)) { \ 208 _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ 209 UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ 210 } else if (cmp(_ls_p,_ls_q) <= 0) { \ 211 _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ 212 UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ 213 } else { \ 214 _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ 215 UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ 216 } \ 217 if (_ls_tail) { \ 218 UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \ 219 } else { \ 220 UTLIST_CASTASGN(list,_ls_e); \ 221 } \ 222 UTLIST_SV(_ls_e,list); UTLIST_PREVASGN(_ls_e,list,_ls_tail,prev); UTLIST_RS(list); \ 223 _ls_tail = _ls_e; \ 224 } \ 225 _ls_p = _ls_q; \ 226 } \ 227 UTLIST_CASTASGN((list)->prev, _ls_tail); \ 228 UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,NULL,next); UTLIST_RS(list); \ 229 if (_ls_nmerges <= 1) { \ 230 _ls_looping=0; \ 231 } \ 232 _ls_insize *= 2; \ 233 } \ 234 } \ 235 } while (0) 236 237 #define CDL_SORT(list, cmp) \ 238 CDL_SORT2(list, cmp, prev, next) 239 240 #define CDL_SORT2(list, cmp, prev, next) \ 241 do { \ 242 LDECLTYPE(list) _ls_p; \ 243 LDECLTYPE(list) _ls_q; \ 244 LDECLTYPE(list) _ls_e; \ 245 LDECLTYPE(list) _ls_tail; \ 246 LDECLTYPE(list) _ls_oldhead; \ 247 LDECLTYPE(list) _tmp; \ 248 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 249 if (list) { \ 250 _ls_insize = 1; \ 251 _ls_looping = 1; \ 252 while (_ls_looping) { \ 253 UTLIST_CASTASGN(_ls_p,list); \ 254 UTLIST_CASTASGN(_ls_oldhead,list); \ 255 (list) = NULL; \ 256 _ls_tail = NULL; \ 257 _ls_nmerges = 0; \ 258 while (_ls_p) { \ 259 _ls_nmerges++; \ 260 _ls_q = _ls_p; \ 261 _ls_psize = 0; \ 262 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 263 _ls_psize++; \ 264 UTLIST_SV(_ls_q,list); \ 265 if (UTLIST_NEXT(_ls_q,list,next) == _ls_oldhead) { \ 266 _ls_q = NULL; \ 267 } else { \ 268 _ls_q = UTLIST_NEXT(_ls_q,list,next); \ 269 } \ 270 UTLIST_RS(list); \ 271 if (!_ls_q) break; \ 272 } \ 273 _ls_qsize = _ls_insize; \ 274 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ 275 if (_ls_psize == 0) { \ 276 _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ 277 UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ 278 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ 279 } else if (_ls_qsize == 0 || !_ls_q) { \ 280 _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ 281 UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ 282 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ 283 } else if (cmp(_ls_p,_ls_q) <= 0) { \ 284 _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ 285 UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ 286 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ 287 } else { \ 288 _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ 289 UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ 290 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ 291 } \ 292 if (_ls_tail) { \ 293 UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \ 294 } else { \ 295 UTLIST_CASTASGN(list,_ls_e); \ 296 } \ 297 UTLIST_SV(_ls_e,list); UTLIST_PREVASGN(_ls_e,list,_ls_tail,prev); UTLIST_RS(list); \ 298 _ls_tail = _ls_e; \ 299 } \ 300 _ls_p = _ls_q; \ 301 } \ 302 UTLIST_CASTASGN((list)->prev,_ls_tail); \ 303 UTLIST_CASTASGN(_tmp,list); \ 304 UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_tmp,next); UTLIST_RS(list); \ 305 if (_ls_nmerges <= 1) { \ 306 _ls_looping=0; \ 307 } \ 308 _ls_insize *= 2; \ 309 } \ 310 } \ 311 } while (0) 312 313 /****************************************************************************** 314 * singly linked list macros (non-circular) * 315 *****************************************************************************/ 316 #define LL_PREPEND(head,add) \ 317 LL_PREPEND2(head,add,next) 318 319 #define LL_PREPEND2(head,add,next) \ 320 do { \ 321 (add)->next = (head); \ 322 (head) = (add); \ 323 } while (0) 324 325 #define LL_CONCAT(head1,head2) \ 326 LL_CONCAT2(head1,head2,next) 327 328 #define LL_CONCAT2(head1,head2,next) \ 329 do { \ 330 LDECLTYPE(head1) _tmp; \ 331 if (head1) { \ 332 _tmp = (head1); \ 333 while (_tmp->next) { _tmp = _tmp->next; } \ 334 _tmp->next=(head2); \ 335 } else { \ 336 (head1)=(head2); \ 337 } \ 338 } while (0) 339 340 #define LL_APPEND(head,add) \ 341 LL_APPEND2(head,add,next) 342 343 #define LL_APPEND2(head,add,next) \ 344 do { \ 345 LDECLTYPE(head) _tmp; \ 346 (add)->next=NULL; \ 347 if (head) { \ 348 _tmp = (head); \ 349 while (_tmp->next) { _tmp = _tmp->next; } \ 350 _tmp->next=(add); \ 351 } else { \ 352 (head)=(add); \ 353 } \ 354 } while (0) 355 356 #define LL_INSERT_INORDER(head,add,cmp) \ 357 LL_INSERT_INORDER2(head,add,cmp,next) 358 359 #define LL_INSERT_INORDER2(head,add,cmp,next) \ 360 do { \ 361 LDECLTYPE(head) _tmp; \ 362 if (head) { \ 363 LL_LOWER_BOUND(head, _tmp, add, cmp); \ 364 LL_APPEND_ELEM(head, _tmp, add); \ 365 } else { \ 366 (head) = (add); \ 367 (head)->next = NULL; \ 368 } \ 369 } while (0) 370 371 #define LL_LOWER_BOUND(head,elt,like,cmp) \ 372 LL_LOWER_BOUND2(head,elt,like,cmp,next) 373 374 #define LL_LOWER_BOUND2(head,elt,like,cmp,next) \ 375 do { \ 376 if ((head) == NULL || (cmp(head, like)) >= 0) { \ 377 (elt) = NULL; \ 378 } else { \ 379 for ((elt) = (head); (elt)->next != NULL; (elt) = (elt)->next) { \ 380 if (cmp((elt)->next, like) >= 0) { \ 381 break; \ 382 } \ 383 } \ 384 } \ 385 } while (0) 386 387 #define LL_DELETE(head,del) \ 388 LL_DELETE2(head,del,next) 389 390 #define LL_DELETE2(head,del,next) \ 391 do { \ 392 LDECLTYPE(head) _tmp; \ 393 if ((head) == (del)) { \ 394 (head)=(head)->next; \ 395 } else { \ 396 _tmp = (head); \ 397 while (_tmp->next && (_tmp->next != (del))) { \ 398 _tmp = _tmp->next; \ 399 } \ 400 if (_tmp->next) { \ 401 _tmp->next = (del)->next; \ 402 } \ 403 } \ 404 } while (0) 405 406 #define LL_COUNT(head,el,counter) \ 407 LL_COUNT2(head,el,counter,next) \ 408 409 #define LL_COUNT2(head,el,counter,next) \ 410 do { \ 411 (counter) = 0; \ 412 LL_FOREACH2(head,el,next) { ++(counter); } \ 413 } while (0) 414 415 #define LL_FOREACH(head,el) \ 416 LL_FOREACH2(head,el,next) 417 418 #define LL_FOREACH2(head,el,next) \ 419 for ((el) = (head); el; (el) = (el)->next) 420 421 #define LL_FOREACH_SAFE(head,el,tmp) \ 422 LL_FOREACH_SAFE2(head,el,tmp,next) 423 424 #define LL_FOREACH_SAFE2(head,el,tmp,next) \ 425 for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp)) 426 427 #define LL_SEARCH_SCALAR(head,out,field,val) \ 428 LL_SEARCH_SCALAR2(head,out,field,val,next) 429 430 #define LL_SEARCH_SCALAR2(head,out,field,val,next) \ 431 do { \ 432 LL_FOREACH2(head,out,next) { \ 433 if ((out)->field == (val)) break; \ 434 } \ 435 } while (0) 436 437 #define LL_SEARCH(head,out,elt,cmp) \ 438 LL_SEARCH2(head,out,elt,cmp,next) 439 440 #define LL_SEARCH2(head,out,elt,cmp,next) \ 441 do { \ 442 LL_FOREACH2(head,out,next) { \ 443 if ((cmp(out,elt))==0) break; \ 444 } \ 445 } while (0) 446 447 #define LL_REPLACE_ELEM2(head, el, add, next) \ 448 do { \ 449 LDECLTYPE(head) _tmp; \ 450 assert((head) != NULL); \ 451 assert((el) != NULL); \ 452 assert((add) != NULL); \ 453 (add)->next = (el)->next; \ 454 if ((head) == (el)) { \ 455 (head) = (add); \ 456 } else { \ 457 _tmp = (head); \ 458 while (_tmp->next && (_tmp->next != (el))) { \ 459 _tmp = _tmp->next; \ 460 } \ 461 if (_tmp->next) { \ 462 _tmp->next = (add); \ 463 } \ 464 } \ 465 } while (0) 466 467 #define LL_REPLACE_ELEM(head, el, add) \ 468 LL_REPLACE_ELEM2(head, el, add, next) 469 470 #define LL_PREPEND_ELEM2(head, el, add, next) \ 471 do { \ 472 if (el) { \ 473 LDECLTYPE(head) _tmp; \ 474 assert((head) != NULL); \ 475 assert((add) != NULL); \ 476 (add)->next = (el); \ 477 if ((head) == (el)) { \ 478 (head) = (add); \ 479 } else { \ 480 _tmp = (head); \ 481 while (_tmp->next && (_tmp->next != (el))) { \ 482 _tmp = _tmp->next; \ 483 } \ 484 if (_tmp->next) { \ 485 _tmp->next = (add); \ 486 } \ 487 } \ 488 } else { \ 489 LL_APPEND2(head, add, next); \ 490 } \ 491 } while (0) \ 492 493 #define LL_PREPEND_ELEM(head, el, add) \ 494 LL_PREPEND_ELEM2(head, el, add, next) 495 496 #define LL_APPEND_ELEM2(head, el, add, next) \ 497 do { \ 498 if (el) { \ 499 assert((head) != NULL); \ 500 assert((add) != NULL); \ 501 (add)->next = (el)->next; \ 502 (el)->next = (add); \ 503 } else { \ 504 LL_PREPEND2(head, add, next); \ 505 } \ 506 } while (0) \ 507 508 #define LL_APPEND_ELEM(head, el, add) \ 509 LL_APPEND_ELEM2(head, el, add, next) 510 511 #ifdef NO_DECLTYPE 512 /* Here are VS2008 / NO_DECLTYPE replacements for a few functions */ 513 514 #undef LL_CONCAT2 515 #define LL_CONCAT2(head1,head2,next) \ 516 do { \ 517 char *_tmp; \ 518 if (head1) { \ 519 _tmp = (char*)(head1); \ 520 while ((head1)->next) { (head1) = (head1)->next; } \ 521 (head1)->next = (head2); \ 522 UTLIST_RS(head1); \ 523 } else { \ 524 (head1)=(head2); \ 525 } \ 526 } while (0) 527 528 #undef LL_APPEND2 529 #define LL_APPEND2(head,add,next) \ 530 do { \ 531 if (head) { \ 532 (add)->next = head; /* use add->next as a temp variable */ \ 533 while ((add)->next->next) { (add)->next = (add)->next->next; } \ 534 (add)->next->next=(add); \ 535 } else { \ 536 (head)=(add); \ 537 } \ 538 (add)->next=NULL; \ 539 } while (0) 540 541 #undef LL_INSERT_INORDER2 542 #define LL_INSERT_INORDER2(head,add,cmp,next) \ 543 do { \ 544 if ((head) == NULL || (cmp(head, add)) >= 0) { \ 545 (add)->next = (head); \ 546 (head) = (add); \ 547 } else { \ 548 char *_tmp = (char*)(head); \ 549 while ((head)->next != NULL && (cmp((head)->next, add)) < 0) { \ 550 (head) = (head)->next; \ 551 } \ 552 (add)->next = (head)->next; \ 553 (head)->next = (add); \ 554 UTLIST_RS(head); \ 555 } \ 556 } while (0) 557 558 #undef LL_DELETE2 559 #define LL_DELETE2(head,del,next) \ 560 do { \ 561 if ((head) == (del)) { \ 562 (head)=(head)->next; \ 563 } else { \ 564 char *_tmp = (char*)(head); \ 565 while ((head)->next && ((head)->next != (del))) { \ 566 (head) = (head)->next; \ 567 } \ 568 if ((head)->next) { \ 569 (head)->next = ((del)->next); \ 570 } \ 571 UTLIST_RS(head); \ 572 } \ 573 } while (0) 574 575 #undef LL_REPLACE_ELEM2 576 #define LL_REPLACE_ELEM2(head, el, add, next) \ 577 do { \ 578 assert((head) != NULL); \ 579 assert((el) != NULL); \ 580 assert((add) != NULL); \ 581 if ((head) == (el)) { \ 582 (head) = (add); \ 583 } else { \ 584 (add)->next = head; \ 585 while ((add)->next->next && ((add)->next->next != (el))) { \ 586 (add)->next = (add)->next->next; \ 587 } \ 588 if ((add)->next->next) { \ 589 (add)->next->next = (add); \ 590 } \ 591 } \ 592 (add)->next = (el)->next; \ 593 } while (0) 594 595 #undef LL_PREPEND_ELEM2 596 #define LL_PREPEND_ELEM2(head, el, add, next) \ 597 do { \ 598 if (el) { \ 599 assert((head) != NULL); \ 600 assert((add) != NULL); \ 601 if ((head) == (el)) { \ 602 (head) = (add); \ 603 } else { \ 604 (add)->next = (head); \ 605 while ((add)->next->next && ((add)->next->next != (el))) { \ 606 (add)->next = (add)->next->next; \ 607 } \ 608 if ((add)->next->next) { \ 609 (add)->next->next = (add); \ 610 } \ 611 } \ 612 (add)->next = (el); \ 613 } else { \ 614 LL_APPEND2(head, add, next); \ 615 } \ 616 } while (0) \ 617 618 #endif /* NO_DECLTYPE */ 619 620 /****************************************************************************** 621 * doubly linked list macros (non-circular) * 622 *****************************************************************************/ 623 #define DL_PREPEND(head,add) \ 624 DL_PREPEND2(head,add,prev,next) 625 626 #define DL_PREPEND2(head,add,prev,next) \ 627 do { \ 628 (add)->next = (head); \ 629 if (head) { \ 630 (add)->prev = (head)->prev; \ 631 (head)->prev = (add); \ 632 } else { \ 633 (add)->prev = (add); \ 634 } \ 635 (head) = (add); \ 636 } while (0) 637 638 #define DL_APPEND(head,add) \ 639 DL_APPEND2(head,add,prev,next) 640 641 #define DL_APPEND2(head,add,prev,next) \ 642 do { \ 643 if (head) { \ 644 (add)->prev = (head)->prev; \ 645 (head)->prev->next = (add); \ 646 (head)->prev = (add); \ 647 (add)->next = NULL; \ 648 } else { \ 649 (head)=(add); \ 650 (head)->prev = (head); \ 651 (head)->next = NULL; \ 652 } \ 653 } while (0) 654 655 #define DL_INSERT_INORDER(head,add,cmp) \ 656 DL_INSERT_INORDER2(head,add,cmp,next) 657 658 #define DL_INSERT_INORDER2(head,add,cmp,next) \ 659 do { \ 660 LDECLTYPE(head) _tmp; \ 661 if (head) { \ 662 DL_LOWER_BOUND(head, _tmp, add, cmp); \ 663 DL_APPEND_ELEM(head, _tmp, add); \ 664 } else { \ 665 (head) = (add); \ 666 (head)->prev = (head); \ 667 (head)->next = NULL; \ 668 } \ 669 } while (0) 670 671 #define DL_LOWER_BOUND(head,elt,like,cmp) \ 672 DL_LOWER_BOUND2(head,elt,like,cmp,next) 673 674 #define DL_LOWER_BOUND2(head,elt,like,cmp,next) \ 675 do { \ 676 if ((head) == NULL || (cmp(head, like)) >= 0) { \ 677 (elt) = NULL; \ 678 } else { \ 679 for ((elt) = (head); (elt)->next != NULL; (elt) = (elt)->next) { \ 680 if ((cmp((elt)->next, like)) >= 0) { \ 681 break; \ 682 } \ 683 } \ 684 } \ 685 } while (0) 686 687 #define DL_CONCAT(head1,head2) \ 688 DL_CONCAT2(head1,head2,prev,next) 689 690 #define DL_CONCAT2(head1,head2,prev,next) \ 691 do { \ 692 LDECLTYPE(head1) _tmp; \ 693 if (head2) { \ 694 if (head1) { \ 695 UTLIST_CASTASGN(_tmp, (head2)->prev); \ 696 (head2)->prev = (head1)->prev; \ 697 (head1)->prev->next = (head2); \ 698 UTLIST_CASTASGN((head1)->prev, _tmp); \ 699 } else { \ 700 (head1)=(head2); \ 701 } \ 702 } \ 703 } while (0) 704 705 #define DL_DELETE(head,del) \ 706 DL_DELETE2(head,del,prev,next) 707 708 #define DL_DELETE2(head,del,prev,next) \ 709 do { \ 710 assert((head) != NULL); \ 711 assert((del)->prev != NULL); \ 712 if ((del)->prev == (del)) { \ 713 (head)=NULL; \ 714 } else if ((del)==(head)) { \ 715 (del)->next->prev = (del)->prev; \ 716 (head) = (del)->next; \ 717 } else { \ 718 (del)->prev->next = (del)->next; \ 719 if ((del)->next) { \ 720 (del)->next->prev = (del)->prev; \ 721 } else { \ 722 (head)->prev = (del)->prev; \ 723 } \ 724 } \ 725 } while (0) 726 727 #define DL_COUNT(head,el,counter) \ 728 DL_COUNT2(head,el,counter,next) \ 729 730 #define DL_COUNT2(head,el,counter,next) \ 731 do { \ 732 (counter) = 0; \ 733 DL_FOREACH2(head,el,next) { ++(counter); } \ 734 } while (0) 735 736 #define DL_FOREACH(head,el) \ 737 DL_FOREACH2(head,el,next) 738 739 #define DL_FOREACH2(head,el,next) \ 740 for ((el) = (head); el; (el) = (el)->next) 741 742 /* this version is safe for deleting the elements during iteration */ 743 #define DL_FOREACH_SAFE(head,el,tmp) \ 744 DL_FOREACH_SAFE2(head,el,tmp,next) 745 746 #define DL_FOREACH_SAFE2(head,el,tmp,next) \ 747 for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp)) 748 749 /* these are identical to their singly-linked list counterparts */ 750 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR 751 #define DL_SEARCH LL_SEARCH 752 #define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2 753 #define DL_SEARCH2 LL_SEARCH2 754 755 #define DL_REPLACE_ELEM2(head, el, add, prev, next) \ 756 do { \ 757 assert((head) != NULL); \ 758 assert((el) != NULL); \ 759 assert((add) != NULL); \ 760 if ((head) == (el)) { \ 761 (head) = (add); \ 762 (add)->next = (el)->next; \ 763 if ((el)->next == NULL) { \ 764 (add)->prev = (add); \ 765 } else { \ 766 (add)->prev = (el)->prev; \ 767 (add)->next->prev = (add); \ 768 } \ 769 } else { \ 770 (add)->next = (el)->next; \ 771 (add)->prev = (el)->prev; \ 772 (add)->prev->next = (add); \ 773 if ((el)->next == NULL) { \ 774 (head)->prev = (add); \ 775 } else { \ 776 (add)->next->prev = (add); \ 777 } \ 778 } \ 779 } while (0) 780 781 #define DL_REPLACE_ELEM(head, el, add) \ 782 DL_REPLACE_ELEM2(head, el, add, prev, next) 783 784 #define DL_PREPEND_ELEM2(head, el, add, prev, next) \ 785 do { \ 786 if (el) { \ 787 assert((head) != NULL); \ 788 assert((add) != NULL); \ 789 (add)->next = (el); \ 790 (add)->prev = (el)->prev; \ 791 (el)->prev = (add); \ 792 if ((head) == (el)) { \ 793 (head) = (add); \ 794 } else { \ 795 (add)->prev->next = (add); \ 796 } \ 797 } else { \ 798 DL_APPEND2(head, add, prev, next); \ 799 } \ 800 } while (0) \ 801 802 #define DL_PREPEND_ELEM(head, el, add) \ 803 DL_PREPEND_ELEM2(head, el, add, prev, next) 804 805 #define DL_APPEND_ELEM2(head, el, add, prev, next) \ 806 do { \ 807 if (el) { \ 808 assert((head) != NULL); \ 809 assert((add) != NULL); \ 810 (add)->next = (el)->next; \ 811 (add)->prev = (el); \ 812 (el)->next = (add); \ 813 if ((add)->next) { \ 814 (add)->next->prev = (add); \ 815 } else { \ 816 (head)->prev = (add); \ 817 } \ 818 } else { \ 819 DL_PREPEND2(head, add, prev, next); \ 820 } \ 821 } while (0) \ 822 823 #define DL_APPEND_ELEM(head, el, add) \ 824 DL_APPEND_ELEM2(head, el, add, prev, next) 825 826 #ifdef NO_DECLTYPE 827 /* Here are VS2008 / NO_DECLTYPE replacements for a few functions */ 828 829 #undef DL_INSERT_INORDER2 830 #define DL_INSERT_INORDER2(head,add,cmp,next) \ 831 do { \ 832 if ((head) == NULL) { \ 833 (add)->prev = (add); \ 834 (add)->next = NULL; \ 835 (head) = (add); \ 836 } else if ((cmp(head, add)) >= 0) { \ 837 (add)->prev = (head)->prev; \ 838 (add)->next = (head); \ 839 (head)->prev = (add); \ 840 (head) = (add); \ 841 } else { \ 842 char *_tmp = (char*)(head); \ 843 while ((char*)(head)->next != _tmp && (cmp((head)->next, add)) < 0) { \ 844 (head) = (head)->next; \ 845 } \ 846 (add)->prev = (head); \ 847 (add)->next = (head)->next; \ 848 (head)->next = (add); \ 849 UTLIST_RS(head); \ 850 if ((add)->next) { \ 851 (add)->next->prev = (add); \ 852 } else { \ 853 (head)->prev = (add); \ 854 } \ 855 } \ 856 } while (0) 857 #endif /* NO_DECLTYPE */ 858 859 /****************************************************************************** 860 * circular doubly linked list macros * 861 *****************************************************************************/ 862 #define CDL_APPEND(head,add) \ 863 CDL_APPEND2(head,add,prev,next) 864 865 #define CDL_APPEND2(head,add,prev,next) \ 866 do { \ 867 if (head) { \ 868 (add)->prev = (head)->prev; \ 869 (add)->next = (head); \ 870 (head)->prev = (add); \ 871 (add)->prev->next = (add); \ 872 } else { \ 873 (add)->prev = (add); \ 874 (add)->next = (add); \ 875 (head) = (add); \ 876 } \ 877 } while (0) 878 879 #define CDL_PREPEND(head,add) \ 880 CDL_PREPEND2(head,add,prev,next) 881 882 #define CDL_PREPEND2(head,add,prev,next) \ 883 do { \ 884 if (head) { \ 885 (add)->prev = (head)->prev; \ 886 (add)->next = (head); \ 887 (head)->prev = (add); \ 888 (add)->prev->next = (add); \ 889 } else { \ 890 (add)->prev = (add); \ 891 (add)->next = (add); \ 892 } \ 893 (head) = (add); \ 894 } while (0) 895 896 #define CDL_INSERT_INORDER(head,add,cmp) \ 897 CDL_INSERT_INORDER2(head,add,cmp,next) 898 899 #define CDL_INSERT_INORDER2(head,add,cmp,next) \ 900 do { \ 901 LDECLTYPE(head) _tmp; \ 902 if (head) { \ 903 CDL_LOWER_BOUND(head, _tmp, add, cmp); \ 904 CDL_APPEND_ELEM(head, _tmp, add); \ 905 } else { \ 906 (head) = (add); \ 907 (head)->next = (head); \ 908 (head)->prev = (head); \ 909 } \ 910 } while (0) 911 912 #define CDL_LOWER_BOUND(head,elt,like,cmp) \ 913 CDL_LOWER_BOUND2(head,elt,like,cmp,next) 914 915 #define CDL_LOWER_BOUND2(head,elt,like,cmp,next) \ 916 do { \ 917 if ((head) == NULL || (cmp(head, like)) >= 0) { \ 918 (elt) = NULL; \ 919 } else { \ 920 for ((elt) = (head); (elt)->next != (head); (elt) = (elt)->next) { \ 921 if ((cmp((elt)->next, like)) >= 0) { \ 922 break; \ 923 } \ 924 } \ 925 } \ 926 } while (0) 927 928 #define CDL_DELETE(head,del) \ 929 CDL_DELETE2(head,del,prev,next) 930 931 #define CDL_DELETE2(head,del,prev,next) \ 932 do { \ 933 if (((head)==(del)) && ((head)->next == (head))) { \ 934 (head) = NULL; \ 935 } else { \ 936 (del)->next->prev = (del)->prev; \ 937 (del)->prev->next = (del)->next; \ 938 if ((del) == (head)) (head)=(del)->next; \ 939 } \ 940 } while (0) 941 942 #define CDL_COUNT(head,el,counter) \ 943 CDL_COUNT2(head,el,counter,next) \ 944 945 #define CDL_COUNT2(head, el, counter,next) \ 946 do { \ 947 (counter) = 0; \ 948 CDL_FOREACH2(head,el,next) { ++(counter); } \ 949 } while (0) 950 951 #define CDL_FOREACH(head,el) \ 952 CDL_FOREACH2(head,el,next) 953 954 #define CDL_FOREACH2(head,el,next) \ 955 for ((el)=(head);el;(el)=(((el)->next==(head)) ? NULL : (el)->next)) 956 957 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \ 958 CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) 959 960 #define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \ 961 for ((el) = (head), (tmp1) = (head) ? (head)->prev : NULL; \ 962 (el) && ((tmp2) = (el)->next, 1); \ 963 (el) = ((el) == (tmp1) ? NULL : (tmp2))) 964 965 #define CDL_SEARCH_SCALAR(head,out,field,val) \ 966 CDL_SEARCH_SCALAR2(head,out,field,val,next) 967 968 #define CDL_SEARCH_SCALAR2(head,out,field,val,next) \ 969 do { \ 970 CDL_FOREACH2(head,out,next) { \ 971 if ((out)->field == (val)) break; \ 972 } \ 973 } while (0) 974 975 #define CDL_SEARCH(head,out,elt,cmp) \ 976 CDL_SEARCH2(head,out,elt,cmp,next) 977 978 #define CDL_SEARCH2(head,out,elt,cmp,next) \ 979 do { \ 980 CDL_FOREACH2(head,out,next) { \ 981 if ((cmp(out,elt))==0) break; \ 982 } \ 983 } while (0) 984 985 #define CDL_REPLACE_ELEM2(head, el, add, prev, next) \ 986 do { \ 987 assert((head) != NULL); \ 988 assert((el) != NULL); \ 989 assert((add) != NULL); \ 990 if ((el)->next == (el)) { \ 991 (add)->next = (add); \ 992 (add)->prev = (add); \ 993 (head) = (add); \ 994 } else { \ 995 (add)->next = (el)->next; \ 996 (add)->prev = (el)->prev; \ 997 (add)->next->prev = (add); \ 998 (add)->prev->next = (add); \ 999 if ((head) == (el)) { \ 1000 (head) = (add); \ 1001 } \ 1002 } \ 1003 } while (0) 1004 1005 #define CDL_REPLACE_ELEM(head, el, add) \ 1006 CDL_REPLACE_ELEM2(head, el, add, prev, next) 1007 1008 #define CDL_PREPEND_ELEM2(head, el, add, prev, next) \ 1009 do { \ 1010 if (el) { \ 1011 assert((head) != NULL); \ 1012 assert((add) != NULL); \ 1013 (add)->next = (el); \ 1014 (add)->prev = (el)->prev; \ 1015 (el)->prev = (add); \ 1016 (add)->prev->next = (add); \ 1017 if ((head) == (el)) { \ 1018 (head) = (add); \ 1019 } \ 1020 } else { \ 1021 CDL_APPEND2(head, add, prev, next); \ 1022 } \ 1023 } while (0) 1024 1025 #define CDL_PREPEND_ELEM(head, el, add) \ 1026 CDL_PREPEND_ELEM2(head, el, add, prev, next) 1027 1028 #define CDL_APPEND_ELEM2(head, el, add, prev, next) \ 1029 do { \ 1030 if (el) { \ 1031 assert((head) != NULL); \ 1032 assert((add) != NULL); \ 1033 (add)->next = (el)->next; \ 1034 (add)->prev = (el); \ 1035 (el)->next = (add); \ 1036 (add)->next->prev = (add); \ 1037 } else { \ 1038 CDL_PREPEND2(head, add, prev, next); \ 1039 } \ 1040 } while (0) 1041 1042 #define CDL_APPEND_ELEM(head, el, add) \ 1043 CDL_APPEND_ELEM2(head, el, add, prev, next) 1044 1045 #ifdef NO_DECLTYPE 1046 /* Here are VS2008 / NO_DECLTYPE replacements for a few functions */ 1047 1048 #undef CDL_INSERT_INORDER2 1049 #define CDL_INSERT_INORDER2(head,add,cmp,next) \ 1050 do { \ 1051 if ((head) == NULL) { \ 1052 (add)->prev = (add); \ 1053 (add)->next = (add); \ 1054 (head) = (add); \ 1055 } else if ((cmp(head, add)) >= 0) { \ 1056 (add)->prev = (head)->prev; \ 1057 (add)->next = (head); \ 1058 (add)->prev->next = (add); \ 1059 (head)->prev = (add); \ 1060 (head) = (add); \ 1061 } else { \ 1062 char *_tmp = (char*)(head); \ 1063 while ((char*)(head)->next != _tmp && (cmp((head)->next, add)) < 0) { \ 1064 (head) = (head)->next; \ 1065 } \ 1066 (add)->prev = (head); \ 1067 (add)->next = (head)->next; \ 1068 (add)->next->prev = (add); \ 1069 (head)->next = (add); \ 1070 UTLIST_RS(head); \ 1071 } \ 1072 } while (0) 1073 #endif /* NO_DECLTYPE */ 1074 1075 #endif /* UTLIST_H */ 1076