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