src/utlist.h

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