contrib/libucl/uthash/utlist.h

   1 /*
   2 Copyright (c) 2007-2013, 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 1.9.8
  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++ code), this code uses whatever method is needed
  65    or, for VS2008 where neither is available, uses casting workarounds. */
  66 #ifdef _MSC_VER            /* MS compiler */
  67 #if _MSC_VER >= 1600 && defined(__cplusplus)  /* VS2010 or newer in C++ mode */
  68 #define LDECLTYPE(x) decltype(x)
  69 #else                     /* VS2008 or older (or VS2010 in C mode) */
  70 #define NO_DECLTYPE
  71 #define LDECLTYPE(x) char*
  72 #endif
  73 #elif defined(__ICCARM__)
  74 #define NO_DECLTYPE
  75 #define LDECLTYPE(x) char*
  76 #else                      /* GNU, Sun and other compilers */
  77 #define LDECLTYPE(x) __typeof(x)
  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 _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
  85 #define _NEXT(elt,list,next) ((char*)((list)->next))
  86 #define _NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }
  87 /* #define _PREV(elt,list,prev) ((char*)((list)->prev)) */
  88 #define _PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }
  89 #define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
  90 #define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
  91 #else
  92 #define _SV(elt,list)
  93 #define _NEXT(elt,list,next) ((elt)->next)
  94 #define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to)
  95 /* #define _PREV(elt,list,prev) ((elt)->prev) */
  96 #define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to)
  97 #define _RS(list)
  98 #define _CASTASGN(a,b) (a)=(b)
  99 #endif
 100
 101 /******************************************************************************
 102  * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort    *
 103  * Unwieldy variable names used here to avoid shadowing passed-in variables.  *
 104  *****************************************************************************/
 105 #define LL_SORT(list, cmp)                                                                     \
 106     LL_SORT2(list, cmp, next)
 107
 108 #define LL_SORT2(list, cmp, next)                                                              \
 109 do {                                                                                           \
 110   LDECLTYPE(list) _ls_p;                                                                       \
 111   LDECLTYPE(list) _ls_q;                                                                       \
 112   LDECLTYPE(list) _ls_e;                                                                       \
 113   LDECLTYPE(list) _ls_tail;                                                                    \
 114   int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping;                       \
 115   if (list) {                                                                                  \
 116     _ls_insize = 1;                                                                            \
 117     _ls_looping = 1;                                                                           \
 118     while (_ls_looping) {                                                                      \
 119       _CASTASGN(_ls_p,list);                                                                   \
 120       list = NULL;                                                                             \
 121       _ls_tail = NULL;                                                                         \
 122       _ls_nmerges = 0;                                                                         \
 123       while (_ls_p) {                                                                          \
 124         _ls_nmerges++;                                                                         \
 125         _ls_q = _ls_p;                                                                         \
 126         _ls_psize = 0;                                                                         \
 127         for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) {                                         \
 128           _ls_psize++;                                                                         \
 129           _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list);                          \
 130           if (!_ls_q) break;                                                                   \
 131         }                                                                                      \
 132         _ls_qsize = _ls_insize;                                                                \
 133         while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) {                                    \
 134           if (_ls_psize == 0) {                                                                \
 135             _ls_e = _ls_q; _SV(_ls_q,list); _ls_q =                                            \
 136               _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--;                                  \
 137           } else if (_ls_qsize == 0 || !_ls_q) {                                               \
 138             _ls_e = _ls_p; _SV(_ls_p,list); _ls_p =                                            \
 139               _NEXT(_ls_p,list,next); _RS(list); _ls_psize--;                                  \
 140           } else if (cmp(_ls_p,_ls_q) <= 0) {                                                  \
 141             _ls_e = _ls_p; _SV(_ls_p,list); _ls_p =                                            \
 142               _NEXT(_ls_p,list,next); _RS(list); _ls_psize--;                                  \
 143           } else {                                                                             \
 144             _ls_e = _ls_q; _SV(_ls_q,list); _ls_q =                                            \
 145               _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--;                                  \
 146           }                                                                                    \
 147           if (_ls_tail) {                                                                      \
 148             _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list);                \
 149           } else {                                                                             \
 150             _CASTASGN(list,_ls_e);                                                             \
 151           }                                                                                    \
 152           _ls_tail = _ls_e;                                                                    \
 153         }                                                                                      \
 154         _ls_p = _ls_q;                                                                         \
 155       }                                                                                        \
 156       if (_ls_tail) {                                                                          \
 157         _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list);                     \
 158       }                                                                                        \
 159       if (_ls_nmerges <= 1) {                                                                  \
 160         _ls_looping=0;                                                                         \
 161       }                                                                                        \
 162       _ls_insize *= 2;                                                                         \
 163     }                                                                                          \
 164   }                                                                                            \
 165 } while (0)
 166
 167
 168 #define DL_SORT(list, cmp)                                                                     \
 169     DL_SORT2(list, cmp, prev, next)
 170
 171 #define DL_SORT2(list, cmp, prev, next)                                                        \
 172 do {                                                                                           \
 173   LDECLTYPE(list) _ls_p;                                                                       \
 174   LDECLTYPE(list) _ls_q;                                                                       \
 175   LDECLTYPE(list) _ls_e;                                                                       \
 176   LDECLTYPE(list) _ls_tail;                                                                    \
 177   int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping;                       \
 178   if (list) {                                                                                  \
 179     _ls_insize = 1;                                                                            \
 180     _ls_looping = 1;                                                                           \
 181     while (_ls_looping) {                                                                      \
 182       _CASTASGN(_ls_p,list);                                                                   \
 183       list = NULL;                                                                             \
 184       _ls_tail = NULL;                                                                         \
 185       _ls_nmerges = 0;                                                                         \
 186       while (_ls_p) {                                                                          \
 187         _ls_nmerges++;                                                                         \
 188         _ls_q = _ls_p;                                                                         \
 189         _ls_psize = 0;                                                                         \
 190         for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) {                                         \
 191           _ls_psize++;                                                                         \
 192           _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list);                          \
 193           if (!_ls_q) break;                                                                   \
 194         }                                                                                      \
 195         _ls_qsize = _ls_insize;                                                                \
 196         while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) {                                    \
 197           if (_ls_psize == 0) {                                                                \
 198             _ls_e = _ls_q; _SV(_ls_q,list); _ls_q =                                            \
 199               _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--;                                  \
 200           } else if (_ls_qsize == 0 || !_ls_q) {                                               \
 201             _ls_e = _ls_p; _SV(_ls_p,list); _ls_p =                                            \
 202               _NEXT(_ls_p,list,next); _RS(list); _ls_psize--;                                  \
 203           } else if (cmp(_ls_p,_ls_q) <= 0) {                                                  \
 204             _ls_e = _ls_p; _SV(_ls_p,list); _ls_p =                                            \
 205               _NEXT(_ls_p,list,next); _RS(list); _ls_psize--;                                  \
 206           } else {                                                                             \
 207             _ls_e = _ls_q; _SV(_ls_q,list); _ls_q =                                            \
 208               _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--;                                  \
 209           }                                                                                    \
 210           if (_ls_tail) {                                                                      \
 211             _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list);                \
 212           } else {                                                                             \
 213             _CASTASGN(list,_ls_e);                                                             \
 214           }                                                                                    \
 215           _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list);                     \
 216           _ls_tail = _ls_e;                                                                    \
 217         }                                                                                      \
 218         _ls_p = _ls_q;                                                                         \
 219       }                                                                                        \
 220       _CASTASGN(list->prev, _ls_tail);                                                         \
 221       _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list);                       \
 222       if (_ls_nmerges <= 1) {                                                                  \
 223         _ls_looping=0;                                                                         \
 224       }                                                                                        \
 225       _ls_insize *= 2;                                                                         \
 226     }                                                                                          \
 227   }                                                                                            \
 228 } while (0)
 229
 230 #define CDL_SORT(list, cmp)                                                                    \
 231     CDL_SORT2(list, cmp, prev, next)
 232
 233 #define CDL_SORT2(list, cmp, prev, next)                                                       \
 234 do {                                                                                           \
 235   LDECLTYPE(list) _ls_p;                                                                       \
 236   LDECLTYPE(list) _ls_q;                                                                       \
 237   LDECLTYPE(list) _ls_e;                                                                       \
 238   LDECLTYPE(list) _ls_tail;                                                                    \
 239   LDECLTYPE(list) _ls_oldhead;                                                                 \
 240   LDECLTYPE(list) _tmp;                                                                        \
 241   int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping;                       \
 242   if (list) {                                                                                  \
 243     _ls_insize = 1;                                                                            \
 244     _ls_looping = 1;                                                                           \
 245     while (_ls_looping) {                                                                      \
 246       _CASTASGN(_ls_p,list);                                                                   \
 247       _CASTASGN(_ls_oldhead,list);                                                             \
 248       list = NULL;                                                                             \
 249       _ls_tail = NULL;                                                                         \
 250       _ls_nmerges = 0;                                                                         \
 251       while (_ls_p) {                                                                          \
 252         _ls_nmerges++;                                                                         \
 253         _ls_q = _ls_p;                                                                         \
 254         _ls_psize = 0;                                                                         \
 255         for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) {                                         \
 256           _ls_psize++;                                                                         \
 257           _SV(_ls_q,list);                                                                     \
 258           if (_NEXT(_ls_q,list,next) == _ls_oldhead) {                                         \
 259             _ls_q = NULL;                                                                      \
 260           } else {                                                                             \
 261             _ls_q = _NEXT(_ls_q,list,next);                                                    \
 262           }                                                                                    \
 263           _RS(list);                                                                           \
 264           if (!_ls_q) break;                                                                   \
 265         }                                                                                      \
 266         _ls_qsize = _ls_insize;                                                                \
 267         while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) {                                    \
 268           if (_ls_psize == 0) {                                                                \
 269             _ls_e = _ls_q; _SV(_ls_q,list); _ls_q =                                            \
 270               _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--;                                  \
 271             if (_ls_q == _ls_oldhead) { _ls_q = NULL; }                                        \
 272           } else if (_ls_qsize == 0 || !_ls_q) {                                               \
 273             _ls_e = _ls_p; _SV(_ls_p,list); _ls_p =                                            \
 274               _NEXT(_ls_p,list,next); _RS(list); _ls_psize--;                                  \
 275             if (_ls_p == _ls_oldhead) { _ls_p = NULL; }                                        \
 276           } else if (cmp(_ls_p,_ls_q) <= 0) {                                                  \
 277             _ls_e = _ls_p; _SV(_ls_p,list); _ls_p =                                            \
 278               _NEXT(_ls_p,list,next); _RS(list); _ls_psize--;                                  \
 279             if (_ls_p == _ls_oldhead) { _ls_p = NULL; }                                        \
 280           } else {                                                                             \
 281             _ls_e = _ls_q; _SV(_ls_q,list); _ls_q =                                            \
 282               _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--;                                  \
 283             if (_ls_q == _ls_oldhead) { _ls_q = NULL; }                                        \
 284           }                                                                                    \
 285           if (_ls_tail) {                                                                      \
 286             _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list);                \
 287           } else {                                                                             \
 288             _CASTASGN(list,_ls_e);                                                             \
 289           }                                                                                    \
 290           _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list);                     \
 291           _ls_tail = _ls_e;                                                                    \
 292         }                                                                                      \
 293         _ls_p = _ls_q;                                                                         \
 294       }                                                                                        \
 295       _CASTASGN(list->prev,_ls_tail);                                                          \
 296       _CASTASGN(_tmp,list);                                                                    \
 297       _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp,next); _RS(list);                       \
 298       if (_ls_nmerges <= 1) {                                                                  \
 299         _ls_looping=0;                                                                         \
 300       }                                                                                        \
 301       _ls_insize *= 2;                                                                         \
 302     }                                                                                          \
 303   }                                                                                            \
 304 } while (0)
 305
 306 /******************************************************************************
 307  * singly linked list macros (non-circular)                                   *
 308  *****************************************************************************/
 309 #define LL_PREPEND(head,add)                                                                   \
 310     LL_PREPEND2(head,add,next)
 311
 312 #define LL_PREPEND2(head,add,next)                                                             \
 313 do {                                                                                           \
 314   (add)->next = head;                                                                          \
 315   head = add;                                                                                  \
 316 } while (0)
 317
 318 #define LL_CONCAT(head1,head2)                                                                 \
 319     LL_CONCAT2(head1,head2,next)
 320
 321 #define LL_CONCAT2(head1,head2,next)                                                           \
 322 do {                                                                                           \
 323   LDECLTYPE(head1) _tmp;                                                                       \
 324   if (head1) {                                                                                 \
 325     _tmp = head1;                                                                              \
 326     while (_tmp->next) { _tmp = _tmp->next; }                                                  \
 327     _tmp->next=(head2);                                                                        \
 328   } else {                                                                                     \
 329     (head1)=(head2);                                                                           \
 330   }                                                                                            \
 331 } while (0)
 332
 333 #define LL_APPEND(head,add)                                                                    \
 334     LL_APPEND2(head,add,next)
 335
 336 #define LL_APPEND2(head,add,next)                                                              \
 337 do {                                                                                           \
 338   LDECLTYPE(head) _tmp;                                                                        \
 339   (add)->next=NULL;                                                                            \
 340   if (head) {                                                                                  \
 341     _tmp = head;                                                                               \
 342     while (_tmp->next) { _tmp = _tmp->next; }                                                  \
 343     _tmp->next=(add);                                                                          \
 344   } else {                                                                                     \
 345     (head)=(add);                                                                              \
 346   }                                                                                            \
 347 } while (0)
 348
 349 #define LL_DELETE(head,del)                                                                    \
 350     LL_DELETE2(head,del,next)
 351
 352 #define LL_DELETE2(head,del,next)                                                              \
 353 do {                                                                                           \
 354   LDECLTYPE(head) _tmp;                                                                        \
 355   if ((head) == (del)) {                                                                       \
 356     (head)=(head)->next;                                                                       \
 357   } else {                                                                                     \
 358     _tmp = head;                                                                               \
 359     while (_tmp->next && (_tmp->next != (del))) {                                              \
 360       _tmp = _tmp->next;                                                                       \
 361     }                                                                                          \
 362     if (_tmp->next) {                                                                          \
 363       _tmp->next = ((del)->next);                                                              \
 364     }                                                                                          \
 365   }                                                                                            \
 366 } while (0)
 367
 368 /* Here are VS2008 replacements for LL_APPEND and LL_DELETE */
 369 #define LL_APPEND_VS2008(head,add)                                                             \
 370     LL_APPEND2_VS2008(head,add,next)
 371
 372 #define LL_APPEND2_VS2008(head,add,next)                                                       \
 373 do {                                                                                           \
 374   if (head) {                                                                                  \
 375     (add)->next = head;     /* use add->next as a temp variable */                             \
 376     while ((add)->next->next) { (add)->next = (add)->next->next; }                             \
 377     (add)->next->next=(add);                                                                   \
 378   } else {                                                                                     \
 379     (head)=(add);                                                                              \
 380   }                                                                                            \
 381   (add)->next=NULL;                                                                            \
 382 } while (0)
 383
 384 #define LL_DELETE_VS2008(head,del)                                                             \
 385     LL_DELETE2_VS2008(head,del,next)
 386
 387 #define LL_DELETE2_VS2008(head,del,next)                                                       \
 388 do {                                                                                           \
 389   if ((head) == (del)) {                                                                       \
 390     (head)=(head)->next;                                                                       \
 391   } else {                                                                                     \
 392     char *_tmp = (char*)(head);                                                                \
 393     while ((head)->next && ((head)->next != (del))) {                                          \
 394       head = (head)->next;                                                                     \
 395     }                                                                                          \
 396     if ((head)->next) {                                                                        \
 397       (head)->next = ((del)->next);                                                            \
 398     }                                                                                          \
 399     {                                                                                          \
 400       char **_head_alias = (char**)&(head);                                                    \
 401       *_head_alias = _tmp;                                                                     \
 402     }                                                                                          \
 403   }                                                                                            \
 404 } while (0)
 405 #ifdef NO_DECLTYPE
 406 #undef LL_APPEND
 407 #define LL_APPEND LL_APPEND_VS2008
 408 #undef LL_DELETE
 409 #define LL_DELETE LL_DELETE_VS2008
 410 #undef LL_DELETE2
 411 #define LL_DELETE2 LL_DELETE2_VS2008
 412 #undef LL_APPEND2
 413 #define LL_APPEND2 LL_APPEND2_VS2008
 414 #undef LL_CONCAT /* no LL_CONCAT_VS2008 */
 415 #undef DL_CONCAT /* no DL_CONCAT_VS2008 */
 416 #endif
 417 /* end VS2008 replacements */
 418
 419 #define LL_COUNT(head,el,counter)                                                              \
 420     LL_COUNT2(head,el,counter,next)                                                            \
 421
 422 #define LL_COUNT2(head,el,counter,next)                                                        \
 423 {                                                                                              \
 424     counter = 0;                                                                               \
 425     LL_FOREACH2(head,el,next){ ++counter; }                                                    \
 426 }
 427
 428 #define LL_FOREACH(head,el)                                                                    \
 429     LL_FOREACH2(head,el,next)
 430
 431 #define LL_FOREACH2(head,el,next)                                                              \
 432     for(el=head;el;el=(el)->next)
 433
 434 #define LL_FOREACH_SAFE(head,el,tmp)                                                           \
 435     LL_FOREACH_SAFE2(head,el,tmp,next)
 436
 437 #define LL_FOREACH_SAFE2(head,el,tmp,next)                                                     \
 438   for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
 439
 440 #define LL_SEARCH_SCALAR(head,out,field,val)                                                   \
 441     LL_SEARCH_SCALAR2(head,out,field,val,next)
 442
 443 #define LL_SEARCH_SCALAR2(head,out,field,val,next)                                             \
 444 do {                                                                                           \
 445     LL_FOREACH2(head,out,next) {                                                               \
 446       if ((out)->field == (val)) break;                                                        \
 447     }                                                                                          \
 448 } while(0)
 449
 450 #define LL_SEARCH(head,out,elt,cmp)                                                            \
 451     LL_SEARCH2(head,out,elt,cmp,next)
 452
 453 #define LL_SEARCH2(head,out,elt,cmp,next)                                                      \
 454 do {                                                                                           \
 455     LL_FOREACH2(head,out,next) {                                                               \
 456       if ((cmp(out,elt))==0) break;                                                            \
 457     }                                                                                          \
 458 } while(0)
 459
 460 #define LL_REPLACE_ELEM(head, el, add)                                                         \
 461 do {                                                                                           \
 462  LDECLTYPE(head) _tmp;                                                                         \
 463  assert(head != NULL);                                                                         \
 464  assert(el != NULL);                                                                           \
 465  assert(add != NULL);                                                                          \
 466  (add)->next = (el)->next;                                                                     \
 467  if ((head) == (el)) {                                                                         \
 468   (head) = (add);                                                                              \
 469  } else {                                                                                      \
 470   _tmp = head;                                                                                 \
 471   while (_tmp->next && (_tmp->next != (el))) {                                                 \
 472    _tmp = _tmp->next;                                                                          \
 473   }                                                                                            \
 474   if (_tmp->next) {                                                                            \
 475     _tmp->next = (add);                                                                        \
 476   }                                                                                            \
 477  }                                                                                             \
 478 } while (0)
 479
 480 #define LL_PREPEND_ELEM(head, el, add)                                                         \
 481 do {                                                                                           \
 482  LDECLTYPE(head) _tmp;                                                                         \
 483  assert(head != NULL);                                                                         \
 484  assert(el != NULL);                                                                           \
 485  assert(add != NULL);                                                                          \
 486  (add)->next = (el);                                                                           \
 487  if ((head) == (el)) {                                                                         \
 488   (head) = (add);                                                                              \
 489  } else {                                                                                      \
 490   _tmp = head;                                                                                 \
 491   while (_tmp->next && (_tmp->next != (el))) {                                                 \
 492    _tmp = _tmp->next;                                                                          \
 493   }                                                                                            \
 494   if (_tmp->next) {                                                                            \
 495     _tmp->next = (add);                                                                        \
 496   }                                                                                            \
 497  }                                                                                             \
 498 } while (0)                                                                                    \
 499
 500
 501 /******************************************************************************
 502  * doubly linked list macros (non-circular)                                   *
 503  *****************************************************************************/
 504 #define DL_PREPEND(head,add)                                                                   \
 505     DL_PREPEND2(head,add,prev,next)
 506
 507 #define DL_PREPEND2(head,add,prev,next)                                                        \
 508 do {                                                                                           \
 509  (add)->next = head;                                                                           \
 510  if (head) {                                                                                   \
 511    (add)->prev = (head)->prev;                                                                 \
 512    (head)->prev = (add);                                                                       \
 513  } else {                                                                                      \
 514    (add)->prev = (add);                                                                        \
 515  }                                                                                             \
 516  (head) = (add);                                                                               \
 517 } while (0)
 518
 519 #define DL_APPEND(head,add)                                                                    \
 520     DL_APPEND2(head,add,prev,next)
 521
 522 #define DL_APPEND2(head,add,prev,next)                                                         \
 523 do {                                                                                           \
 524   if (head) {                                                                                  \
 525       (add)->prev = (head)->prev;                                                              \
 526       (head)->prev->next = (add);                                                              \
 527       (head)->prev = (add);                                                                    \
 528       (add)->next = NULL;                                                                      \
 529   } else {                                                                                     \
 530       (head)=(add);                                                                            \
 531       (head)->prev = (head);                                                                   \
 532       (head)->next = NULL;                                                                     \
 533   }                                                                                            \
 534 } while (0)
 535
 536 #define DL_CONCAT(head1,head2)                                                                 \
 537     DL_CONCAT2(head1,head2,prev,next)
 538
 539 #define DL_CONCAT2(head1,head2,prev,next)                                                      \
 540 do {                                                                                           \
 541   LDECLTYPE(head1) _tmp;                                                                       \
 542   if (head2) {                                                                                 \
 543     if (head1) {                                                                               \
 544         _tmp = (head2)->prev;                                                                  \
 545         (head2)->prev = (head1)->prev;                                                         \
 546         (head1)->prev->next = (head2);                                                         \
 547         (head1)->prev = _tmp;                                                                  \
 548     } else {                                                                                   \
 549         (head1)=(head2);                                                                       \
 550     }                                                                                          \
 551   }                                                                                            \
 552 } while (0)
 553
 554 #define DL_DELETE(head,del)                                                                    \
 555     DL_DELETE2(head,del,prev,next)
 556
 557 #define DL_DELETE2(head,del,prev,next)                                                         \
 558 do {                                                                                           \
 559   assert((del)->prev != NULL);                                                                 \
 560   if ((del)->prev == (del)) {                                                                  \
 561       (head)=NULL;                                                                             \
 562   } else if ((del)==(head)) {                                                                  \
 563       (del)->next->prev = (del)->prev;                                                         \
 564       (head) = (del)->next;                                                                    \
 565   } else {                                                                                     \
 566       (del)->prev->next = (del)->next;                                                         \
 567       if ((del)->next) {                                                                       \
 568           (del)->next->prev = (del)->prev;                                                     \
 569       } else {                                                                                 \
 570           (head)->prev = (del)->prev;                                                          \
 571       }                                                                                        \
 572   }                                                                                            \
 573 } while (0)
 574
 575 #define DL_COUNT(head,el,counter)                                                              \
 576     DL_COUNT2(head,el,counter,next)                                                            \
 577
 578 #define DL_COUNT2(head,el,counter,next)                                                        \
 579 {                                                                                              \
 580     counter = 0;                                                                               \
 581     DL_FOREACH2(head,el,next){ ++counter; }                                                    \
 582 }
 583
 584 #define DL_FOREACH(head,el)                                                                    \
 585     DL_FOREACH2(head,el,next)
 586
 587 #define DL_FOREACH2(head,el,next)                                                              \
 588     for(el=head;el;el=(el)->next)
 589
 590 /* this version is safe for deleting the elements during iteration */
 591 #define DL_FOREACH_SAFE(head,el,tmp)                                                           \
 592     DL_FOREACH_SAFE2(head,el,tmp,next)
 593
 594 #define DL_FOREACH_SAFE2(head,el,tmp,next)                                                     \
 595   for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
 596
 597 /* these are identical to their singly-linked list counterparts */
 598 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
 599 #define DL_SEARCH LL_SEARCH
 600 #define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2
 601 #define DL_SEARCH2 LL_SEARCH2
 602
 603 #define DL_REPLACE_ELEM(head, el, add)                                                         \
 604 do {                                                                                           \
 605  assert(head != NULL);                                                                         \
 606  assert(el != NULL);                                                                           \
 607  assert(add != NULL);                                                                          \
 608  if ((head) == (el)) {                                                                         \
 609   (head) = (add);                                                                              \
 610   (add)->next = (el)->next;                                                                    \
 611   if ((el)->next == NULL) {                                                                    \
 612    (add)->prev = (add);                                                                        \
 613   } else {                                                                                     \
 614    (add)->prev = (el)->prev;                                                                   \
 615    (add)->next->prev = (add);                                                                  \
 616   }                                                                                            \
 617  } else {                                                                                      \
 618   (add)->next = (el)->next;                                                                    \
 619   (add)->prev = (el)->prev;                                                                    \
 620   (add)->prev->next = (add);                                                                   \
 621   if ((el)->next == NULL) {                                                                    \
 622    (head)->prev = (add);                                                                       \
 623   } else {                                                                                     \
 624    (add)->next->prev = (add);                                                                  \
 625   }                                                                                            \
 626  }                                                                                             \
 627 } while (0)
 628
 629 #define DL_PREPEND_ELEM(head, el, add)                                                         \
 630 do {                                                                                           \
 631  assert(head != NULL);                                                                         \
 632  assert(el != NULL);                                                                           \
 633  assert(add != NULL);                                                                          \
 634  (add)->next = (el);                                                                           \
 635  (add)->prev = (el)->prev;                                                                     \
 636  (el)->prev = (add);                                                                           \
 637  if ((head) == (el)) {                                                                         \
 638   (head) = (add);                                                                              \
 639  } else {                                                                                      \
 640   (add)->prev->next = (add);                                                                   \
 641  }                                                                                             \
 642 } while (0)                                                                                    \
 643
 644
 645 /******************************************************************************
 646  * circular doubly linked list macros                                         *
 647  *****************************************************************************/
 648 #define CDL_PREPEND(head,add)                                                                  \
 649     CDL_PREPEND2(head,add,prev,next)
 650
 651 #define CDL_PREPEND2(head,add,prev,next)                                                       \
 652 do {                                                                                           \
 653  if (head) {                                                                                   \
 654    (add)->prev = (head)->prev;                                                                 \
 655    (add)->next = (head);                                                                       \
 656    (head)->prev = (add);                                                                       \
 657    (add)->prev->next = (add);                                                                  \
 658  } else {                                                                                      \
 659    (add)->prev = (add);                                                                        \
 660    (add)->next = (add);                                                                        \
 661  }                                                                                             \
 662 (head)=(add);                                                                                  \
 663 } while (0)
 664
 665 #define CDL_DELETE(head,del)                                                                   \
 666     CDL_DELETE2(head,del,prev,next)
 667
 668 #define CDL_DELETE2(head,del,prev,next)                                                        \
 669 do {                                                                                           \
 670   if ( ((head)==(del)) && ((head)->next == (head))) {                                          \
 671       (head) = 0L;                                                                             \
 672   } else {                                                                                     \
 673      (del)->next->prev = (del)->prev;                                                          \
 674      (del)->prev->next = (del)->next;                                                          \
 675      if ((del) == (head)) (head)=(del)->next;                                                  \
 676   }                                                                                            \
 677 } while (0)
 678
 679 #define CDL_COUNT(head,el,counter)                                                             \
 680     CDL_COUNT2(head,el,counter,next)                                                           \
 681
 682 #define CDL_COUNT2(head, el, counter,next)                                                     \
 683 {                                                                                              \
 684     counter = 0;                                                                               \
 685     CDL_FOREACH2(head,el,next){ ++counter; }                                                   \
 686 }
 687
 688 #define CDL_FOREACH(head,el)                                                                   \
 689     CDL_FOREACH2(head,el,next)
 690
 691 #define CDL_FOREACH2(head,el,next)                                                             \
 692     for(el=head;el;el=((el)->next==head ? 0L : (el)->next))
 693
 694 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2)                                                    \
 695     CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
 696
 697 #define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)                                         \
 698   for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL);                                        \
 699       (el) && ((tmp2)=(el)->next, 1);                                                          \
 700       ((el) = (((el)==(tmp1)) ? 0L : (tmp2))))
 701
 702 #define CDL_SEARCH_SCALAR(head,out,field,val)                                                  \
 703     CDL_SEARCH_SCALAR2(head,out,field,val,next)
 704
 705 #define CDL_SEARCH_SCALAR2(head,out,field,val,next)                                            \
 706 do {                                                                                           \
 707     CDL_FOREACH2(head,out,next) {                                                              \
 708       if ((out)->field == (val)) break;                                                        \
 709     }                                                                                          \
 710 } while(0)
 711
 712 #define CDL_SEARCH(head,out,elt,cmp)                                                           \
 713     CDL_SEARCH2(head,out,elt,cmp,next)
 714
 715 #define CDL_SEARCH2(head,out,elt,cmp,next)                                                     \
 716 do {                                                                                           \
 717     CDL_FOREACH2(head,out,next) {                                                              \
 718       if ((cmp(out,elt))==0) break;                                                            \
 719     }                                                                                          \
 720 } while(0)
 721
 722 #define CDL_REPLACE_ELEM(head, el, add)                                                        \
 723 do {                                                                                           \
 724  assert(head != NULL);                                                                         \
 725  assert(el != NULL);                                                                           \
 726  assert(add != NULL);                                                                          \
 727  if ((el)->next == (el)) {                                                                     \
 728   (add)->next = (add);                                                                         \
 729   (add)->prev = (add);                                                                         \
 730   (head) = (add);                                                                              \
 731  } else {                                                                                      \
 732   (add)->next = (el)->next;                                                                    \
 733   (add)->prev = (el)->prev;                                                                    \
 734   (add)->next->prev = (add);                                                                   \
 735   (add)->prev->next = (add);                                                                   \
 736   if ((head) == (el)) {                                                                        \
 737    (head) = (add);                                                                             \
 738   }                                                                                            \
 739  }                                                                                             \
 740 } while (0)
 741
 742 #define CDL_PREPEND_ELEM(head, el, add)                                                        \
 743 do {                                                                                           \
 744  assert(head != NULL);                                                                         \
 745  assert(el != NULL);                                                                           \
 746  assert(add != NULL);                                                                          \
 747  (add)->next = (el);                                                                           \
 748  (add)->prev = (el)->prev;                                                                     \
 749  (el)->prev = (add);                                                                           \
 750  (add)->prev->next = (add);                                                                    \
 751  if ((head) == (el)) {                                                                         \
 752   (head) = (add);                                                                              \
 753  }                                                                                             \
 754 } while (0)                                                                                    \
 755
 756 #endif /* UTLIST_H */
 757