1 /* 2 Copyright (c) 2007-2022, Troy D. Hanson https://troydhanson.github.io/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.3.0 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(__MCST__) /* Elbrus C Compiler */ 74 #define LDECLTYPE(x) __typeof(x) 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_BOUND2(head, _tmp, add, cmp, next); \ 364 LL_APPEND_ELEM2(head, _tmp, add, next); \ 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,prev,next) 657 658 #define DL_INSERT_INORDER2(head,add,cmp,prev,next) \ 659 do { \ 660 LDECLTYPE(head) _tmp; \ 661 if (head) { \ 662 DL_LOWER_BOUND2(head, _tmp, add, cmp, next); \ 663 DL_APPEND_ELEM2(head, _tmp, add, prev, next); \ 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 assert((del)->next != NULL); \ 716 (del)->next->prev = (del)->prev; \ 717 (head) = (del)->next; \ 718 } else { \ 719 (del)->prev->next = (del)->next; \ 720 if ((del)->next) { \ 721 (del)->next->prev = (del)->prev; \ 722 } else { \ 723 (head)->prev = (del)->prev; \ 724 } \ 725 } \ 726 } while (0) 727 728 #define DL_COUNT(head,el,counter) \ 729 DL_COUNT2(head,el,counter,next) \ 730 731 #define DL_COUNT2(head,el,counter,next) \ 732 do { \ 733 (counter) = 0; \ 734 DL_FOREACH2(head,el,next) { ++(counter); } \ 735 } while (0) 736 737 #define DL_FOREACH(head,el) \ 738 DL_FOREACH2(head,el,next) 739 740 #define DL_FOREACH2(head,el,next) \ 741 for ((el) = (head); el; (el) = (el)->next) 742 743 /* this version is safe for deleting the elements during iteration */ 744 #define DL_FOREACH_SAFE(head,el,tmp) \ 745 DL_FOREACH_SAFE2(head,el,tmp,next) 746 747 #define DL_FOREACH_SAFE2(head,el,tmp,next) \ 748 for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp)) 749 750 /* these are identical to their singly-linked list counterparts */ 751 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR 752 #define DL_SEARCH LL_SEARCH 753 #define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2 754 #define DL_SEARCH2 LL_SEARCH2 755 756 #define DL_REPLACE_ELEM2(head, el, add, prev, next) \ 757 do { \ 758 assert((head) != NULL); \ 759 assert((el) != NULL); \ 760 assert((add) != NULL); \ 761 if ((head) == (el)) { \ 762 (head) = (add); \ 763 (add)->next = (el)->next; \ 764 if ((el)->next == NULL) { \ 765 (add)->prev = (add); \ 766 } else { \ 767 (add)->prev = (el)->prev; \ 768 (add)->next->prev = (add); \ 769 } \ 770 } else { \ 771 (add)->next = (el)->next; \ 772 (add)->prev = (el)->prev; \ 773 (add)->prev->next = (add); \ 774 if ((el)->next == NULL) { \ 775 (head)->prev = (add); \ 776 } else { \ 777 (add)->next->prev = (add); \ 778 } \ 779 } \ 780 } while (0) 781 782 #define DL_REPLACE_ELEM(head, el, add) \ 783 DL_REPLACE_ELEM2(head, el, add, prev, next) 784 785 #define DL_PREPEND_ELEM2(head, el, add, prev, next) \ 786 do { \ 787 if (el) { \ 788 assert((head) != NULL); \ 789 assert((add) != NULL); \ 790 (add)->next = (el); \ 791 (add)->prev = (el)->prev; \ 792 (el)->prev = (add); \ 793 if ((head) == (el)) { \ 794 (head) = (add); \ 795 } else { \ 796 (add)->prev->next = (add); \ 797 } \ 798 } else { \ 799 DL_APPEND2(head, add, prev, next); \ 800 } \ 801 } while (0) \ 802 803 #define DL_PREPEND_ELEM(head, el, add) \ 804 DL_PREPEND_ELEM2(head, el, add, prev, next) 805 806 #define DL_APPEND_ELEM2(head, el, add, prev, next) \ 807 do { \ 808 if (el) { \ 809 assert((head) != NULL); \ 810 assert((add) != NULL); \ 811 (add)->next = (el)->next; \ 812 (add)->prev = (el); \ 813 (el)->next = (add); \ 814 if ((add)->next) { \ 815 (add)->next->prev = (add); \ 816 } else { \ 817 (head)->prev = (add); \ 818 } \ 819 } else { \ 820 DL_PREPEND2(head, add, prev, next); \ 821 } \ 822 } while (0) \ 823 824 #define DL_APPEND_ELEM(head, el, add) \ 825 DL_APPEND_ELEM2(head, el, add, prev, next) 826 827 #ifdef NO_DECLTYPE 828 /* Here are VS2008 / NO_DECLTYPE replacements for a few functions */ 829 830 #undef DL_INSERT_INORDER2 831 #define DL_INSERT_INORDER2(head,add,cmp,prev,next) \ 832 do { \ 833 if ((head) == NULL) { \ 834 (add)->prev = (add); \ 835 (add)->next = NULL; \ 836 (head) = (add); \ 837 } else if ((cmp(head, add)) >= 0) { \ 838 (add)->prev = (head)->prev; \ 839 (add)->next = (head); \ 840 (head)->prev = (add); \ 841 (head) = (add); \ 842 } else { \ 843 char *_tmp = (char*)(head); \ 844 while ((head)->next && (cmp((head)->next, add)) < 0) { \ 845 (head) = (head)->next; \ 846 } \ 847 (add)->prev = (head); \ 848 (add)->next = (head)->next; \ 849 (head)->next = (add); \ 850 UTLIST_RS(head); \ 851 if ((add)->next) { \ 852 (add)->next->prev = (add); \ 853 } else { \ 854 (head)->prev = (add); \ 855 } \ 856 } \ 857 } while (0) 858 #endif /* NO_DECLTYPE */ 859 860 /****************************************************************************** 861 * circular doubly linked list macros * 862 *****************************************************************************/ 863 #define CDL_APPEND(head,add) \ 864 CDL_APPEND2(head,add,prev,next) 865 866 #define CDL_APPEND2(head,add,prev,next) \ 867 do { \ 868 if (head) { \ 869 (add)->prev = (head)->prev; \ 870 (add)->next = (head); \ 871 (head)->prev = (add); \ 872 (add)->prev->next = (add); \ 873 } else { \ 874 (add)->prev = (add); \ 875 (add)->next = (add); \ 876 (head) = (add); \ 877 } \ 878 } while (0) 879 880 #define CDL_PREPEND(head,add) \ 881 CDL_PREPEND2(head,add,prev,next) 882 883 #define CDL_PREPEND2(head,add,prev,next) \ 884 do { \ 885 if (head) { \ 886 (add)->prev = (head)->prev; \ 887 (add)->next = (head); \ 888 (head)->prev = (add); \ 889 (add)->prev->next = (add); \ 890 } else { \ 891 (add)->prev = (add); \ 892 (add)->next = (add); \ 893 } \ 894 (head) = (add); \ 895 } while (0) 896 897 #define CDL_INSERT_INORDER(head,add,cmp) \ 898 CDL_INSERT_INORDER2(head,add,cmp,prev,next) 899 900 #define CDL_INSERT_INORDER2(head,add,cmp,prev,next) \ 901 do { \ 902 LDECLTYPE(head) _tmp; \ 903 if (head) { \ 904 CDL_LOWER_BOUND2(head, _tmp, add, cmp, next); \ 905 CDL_APPEND_ELEM2(head, _tmp, add, prev, next); \ 906 } else { \ 907 (head) = (add); \ 908 (head)->next = (head); \ 909 (head)->prev = (head); \ 910 } \ 911 } while (0) 912 913 #define CDL_LOWER_BOUND(head,elt,like,cmp) \ 914 CDL_LOWER_BOUND2(head,elt,like,cmp,next) 915 916 #define CDL_LOWER_BOUND2(head,elt,like,cmp,next) \ 917 do { \ 918 if ((head) == NULL || (cmp(head, like)) >= 0) { \ 919 (elt) = NULL; \ 920 } else { \ 921 for ((elt) = (head); (elt)->next != (head); (elt) = (elt)->next) { \ 922 if ((cmp((elt)->next, like)) >= 0) { \ 923 break; \ 924 } \ 925 } \ 926 } \ 927 } while (0) 928 929 #define CDL_DELETE(head,del) \ 930 CDL_DELETE2(head,del,prev,next) 931 932 #define CDL_DELETE2(head,del,prev,next) \ 933 do { \ 934 if (((head)==(del)) && ((head)->next == (head))) { \ 935 (head) = NULL; \ 936 } else { \ 937 (del)->next->prev = (del)->prev; \ 938 (del)->prev->next = (del)->next; \ 939 if ((del) == (head)) (head)=(del)->next; \ 940 } \ 941 } while (0) 942 943 #define CDL_COUNT(head,el,counter) \ 944 CDL_COUNT2(head,el,counter,next) \ 945 946 #define CDL_COUNT2(head, el, counter,next) \ 947 do { \ 948 (counter) = 0; \ 949 CDL_FOREACH2(head,el,next) { ++(counter); } \ 950 } while (0) 951 952 #define CDL_FOREACH(head,el) \ 953 CDL_FOREACH2(head,el,next) 954 955 #define CDL_FOREACH2(head,el,next) \ 956 for ((el)=(head);el;(el)=(((el)->next==(head)) ? NULL : (el)->next)) 957 958 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \ 959 CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) 960 961 #define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \ 962 for ((el) = (head), (tmp1) = (head) ? (head)->prev : NULL; \ 963 (el) && ((tmp2) = (el)->next, 1); \ 964 (el) = ((el) == (tmp1) ? NULL : (tmp2))) 965 966 #define CDL_SEARCH_SCALAR(head,out,field,val) \ 967 CDL_SEARCH_SCALAR2(head,out,field,val,next) 968 969 #define CDL_SEARCH_SCALAR2(head,out,field,val,next) \ 970 do { \ 971 CDL_FOREACH2(head,out,next) { \ 972 if ((out)->field == (val)) break; \ 973 } \ 974 } while (0) 975 976 #define CDL_SEARCH(head,out,elt,cmp) \ 977 CDL_SEARCH2(head,out,elt,cmp,next) 978 979 #define CDL_SEARCH2(head,out,elt,cmp,next) \ 980 do { \ 981 CDL_FOREACH2(head,out,next) { \ 982 if ((cmp(out,elt))==0) break; \ 983 } \ 984 } while (0) 985 986 #define CDL_REPLACE_ELEM2(head, el, add, prev, next) \ 987 do { \ 988 assert((head) != NULL); \ 989 assert((el) != NULL); \ 990 assert((add) != NULL); \ 991 if ((el)->next == (el)) { \ 992 (add)->next = (add); \ 993 (add)->prev = (add); \ 994 (head) = (add); \ 995 } else { \ 996 (add)->next = (el)->next; \ 997 (add)->prev = (el)->prev; \ 998 (add)->next->prev = (add); \ 999 (add)->prev->next = (add); \ 1000 if ((head) == (el)) { \ 1001 (head) = (add); \ 1002 } \ 1003 } \ 1004 } while (0) 1005 1006 #define CDL_REPLACE_ELEM(head, el, add) \ 1007 CDL_REPLACE_ELEM2(head, el, add, prev, next) 1008 1009 #define CDL_PREPEND_ELEM2(head, el, add, prev, next) \ 1010 do { \ 1011 if (el) { \ 1012 assert((head) != NULL); \ 1013 assert((add) != NULL); \ 1014 (add)->next = (el); \ 1015 (add)->prev = (el)->prev; \ 1016 (el)->prev = (add); \ 1017 (add)->prev->next = (add); \ 1018 if ((head) == (el)) { \ 1019 (head) = (add); \ 1020 } \ 1021 } else { \ 1022 CDL_APPEND2(head, add, prev, next); \ 1023 } \ 1024 } while (0) 1025 1026 #define CDL_PREPEND_ELEM(head, el, add) \ 1027 CDL_PREPEND_ELEM2(head, el, add, prev, next) 1028 1029 #define CDL_APPEND_ELEM2(head, el, add, prev, next) \ 1030 do { \ 1031 if (el) { \ 1032 assert((head) != NULL); \ 1033 assert((add) != NULL); \ 1034 (add)->next = (el)->next; \ 1035 (add)->prev = (el); \ 1036 (el)->next = (add); \ 1037 (add)->next->prev = (add); \ 1038 } else { \ 1039 CDL_PREPEND2(head, add, prev, next); \ 1040 } \ 1041 } while (0) 1042 1043 #define CDL_APPEND_ELEM(head, el, add) \ 1044 CDL_APPEND_ELEM2(head, el, add, prev, next) 1045 1046 #ifdef NO_DECLTYPE 1047 /* Here are VS2008 / NO_DECLTYPE replacements for a few functions */ 1048 1049 #undef CDL_INSERT_INORDER2 1050 #define CDL_INSERT_INORDER2(head,add,cmp,prev,next) \ 1051 do { \ 1052 if ((head) == NULL) { \ 1053 (add)->prev = (add); \ 1054 (add)->next = (add); \ 1055 (head) = (add); \ 1056 } else if ((cmp(head, add)) >= 0) { \ 1057 (add)->prev = (head)->prev; \ 1058 (add)->next = (head); \ 1059 (add)->prev->next = (add); \ 1060 (head)->prev = (add); \ 1061 (head) = (add); \ 1062 } else { \ 1063 char *_tmp = (char*)(head); \ 1064 while ((char*)(head)->next != _tmp && (cmp((head)->next, add)) < 0) { \ 1065 (head) = (head)->next; \ 1066 } \ 1067 (add)->prev = (head); \ 1068 (add)->next = (head)->next; \ 1069 (add)->next->prev = (add); \ 1070 (head)->next = (add); \ 1071 UTLIST_RS(head); \ 1072 } \ 1073 } while (0) 1074 #endif /* NO_DECLTYPE */ 1075 1076 #endif /* UTLIST_H */ 1077