resource/c_common/utlist.h

   1 /*
   2 Copyright (c) 2007-2016, 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 2.0.1
  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 #endif
  69 #elif defined(__ICCARM__)
  70 #define NO_DECLTYPE
  71 #else                      /* GNU, Sun and other compilers */
  72 #define LDECLTYPE(x) __typeof(x)
  73 #endif
  74
  75 /* for VS2008 we use some workarounds to get around the lack of decltype,
  76  * namely, we always reassign our tmp variable to the list head if we need
  77  * to dereference its prev/next pointers, and save/restore the real head.*/
  78 #ifdef NO_DECLTYPE
  79 #define IF_NO_DECLTYPE(x) x
  80 #define LDECLTYPE(x) char*
  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 IF_NO_DECLTYPE(x)
  90 #define _SV(elt,list)
  91 #define _NEXT(elt,list,next) ((elt)->next)
  92 #define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to)
  93 /* #define _PREV(elt,list,prev) ((elt)->prev) */
  94 #define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to)
  95 #define _RS(list)
  96 #define _CASTASGN(a,b) (a)=(b)
  97 #endif
  98
  99 /******************************************************************************
 100  * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort    *
 101  * Unwieldy variable names used here to avoid shadowing passed-in variables.  *
 102  *****************************************************************************/
 103 #define LL_SORT(list, cmp)                                                                     \
 104     LL_SORT2(list, cmp, next)
 105
 106 #define LL_SORT2(list, cmp, next)                                                              \
 107 do {                                                                                           \
 108   LDECLTYPE(list) _ls_p;                                                                       \
 109   LDECLTYPE(list) _ls_q;                                                                       \
 110   LDECLTYPE(list) _ls_e;                                                                       \
 111   LDECLTYPE(list) _ls_tail;                                                                    \
 112   IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;)                                                        \
 113   int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping;                       \
 114   if (list) {                                                                                  \
 115     _ls_insize = 1;                                                                            \
 116     _ls_looping = 1;                                                                           \
 117     while (_ls_looping) {                                                                      \
 118       _CASTASGN(_ls_p,list);                                                                   \
 119       (list) = NULL;                                                                           \
 120       _ls_tail = NULL;                                                                         \
 121       _ls_nmerges = 0;                                                                         \
 122       while (_ls_p) {                                                                          \
 123         _ls_nmerges++;                                                                         \
 124         _ls_q = _ls_p;                                                                         \
 125         _ls_psize = 0;                                                                         \
 126         for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) {                                         \
 127           _ls_psize++;                                                                         \
 128           _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list);                          \
 129           if (!_ls_q) break;                                                                   \
 130         }                                                                                      \
 131         _ls_qsize = _ls_insize;                                                                \
 132         while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) {                                    \
 133           if (_ls_psize == 0) {                                                                \
 134             _ls_e = _ls_q; _SV(_ls_q,list); _ls_q =                                            \
 135               _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--;                                  \
 136           } else if (_ls_qsize == 0 || !_ls_q) {                                               \
 137             _ls_e = _ls_p; _SV(_ls_p,list); _ls_p =                                            \
 138               _NEXT(_ls_p,list,next); _RS(list); _ls_psize--;                                  \
 139           } else if (cmp(_ls_p,_ls_q) <= 0) {                                                  \
 140             _ls_e = _ls_p; _SV(_ls_p,list); _ls_p =                                            \
 141               _NEXT(_ls_p,list,next); _RS(list); _ls_psize--;                                  \
 142           } else {                                                                             \
 143             _ls_e = _ls_q; _SV(_ls_q,list); _ls_q =                                            \
 144               _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--;                                  \
 145           }                                                                                    \
 146           if (_ls_tail) {                                                                      \
 147             _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list);                \
 148           } else {                                                                             \
 149             _CASTASGN(list,_ls_e);                                                             \
 150           }                                                                                    \
 151           _ls_tail = _ls_e;                                                                    \
 152         }                                                                                      \
 153         _ls_p = _ls_q;                                                                         \
 154       }                                                                                        \
 155       if (_ls_tail) {                                                                          \
 156         _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list);                     \
 157       }                                                                                        \
 158       if (_ls_nmerges <= 1) {                                                                  \
 159         _ls_looping=0;                                                                         \
 160       }                                                                                        \
 161       _ls_insize *= 2;                                                                         \
 162     }                                                                                          \
 163   }                                                                                            \
 164 } while (0)
 165
 166
 167 #define DL_SORT(list, cmp)                                                                     \
 168     DL_SORT2(list, cmp, prev, next)
 169
 170 #define DL_SORT2(list, cmp, prev, next)                                                        \
 171 do {                                                                                           \
 172   LDECLTYPE(list) _ls_p;                                                                       \
 173   LDECLTYPE(list) _ls_q;                                                                       \
 174   LDECLTYPE(list) _ls_e;                                                                       \
 175   LDECLTYPE(list) _ls_tail;                                                                    \
 176   IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;)                                                        \
 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 #define LL_COUNT(head,el,counter)                                                              \
 369     LL_COUNT2(head,el,counter,next)                                                            \
 370
 371 #define LL_COUNT2(head,el,counter,next)                                                        \
 372 do {                                                                                           \
 373   (counter) = 0;                                                                               \
 374   LL_FOREACH2(head,el,next) { ++(counter); }                                                   \
 375 } while (0)
 376
 377 #define LL_FOREACH(head,el)                                                                    \
 378     LL_FOREACH2(head,el,next)
 379
 380 #define LL_FOREACH2(head,el,next)                                                              \
 381     for ((el) = (head); el; (el) = (el)->next)
 382
 383 #define LL_FOREACH_SAFE(head,el,tmp)                                                           \
 384     LL_FOREACH_SAFE2(head,el,tmp,next)
 385
 386 #define LL_FOREACH_SAFE2(head,el,tmp,next)                                                     \
 387   for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp))
 388
 389 #define LL_SEARCH_SCALAR(head,out,field,val)                                                   \
 390     LL_SEARCH_SCALAR2(head,out,field,val,next)
 391
 392 #define LL_SEARCH_SCALAR2(head,out,field,val,next)                                             \
 393 do {                                                                                           \
 394     LL_FOREACH2(head,out,next) {                                                               \
 395       if ((out)->field == (val)) break;                                                        \
 396     }                                                                                          \
 397 } while (0)
 398
 399 #define LL_SEARCH(head,out,elt,cmp)                                                            \
 400     LL_SEARCH2(head,out,elt,cmp,next)
 401
 402 #define LL_SEARCH2(head,out,elt,cmp,next)                                                      \
 403 do {                                                                                           \
 404     LL_FOREACH2(head,out,next) {                                                               \
 405       if ((cmp(out,elt))==0) break;                                                            \
 406     }                                                                                          \
 407 } while (0)
 408
 409 #define LL_REPLACE_ELEM2(head, el, add, next)                                                  \
 410 do {                                                                                           \
 411  LDECLTYPE(head) _tmp;                                                                         \
 412  assert((head) != NULL);                                                                       \
 413  assert((el) != NULL);                                                                         \
 414  assert((add) != NULL);                                                                        \
 415  (add)->next = (el)->next;                                                                     \
 416  if ((head) == (el)) {                                                                         \
 417   (head) = (add);                                                                              \
 418  } else {                                                                                      \
 419   _tmp = (head);                                                                               \
 420   while (_tmp->next && (_tmp->next != (el))) {                                                 \
 421    _tmp = _tmp->next;                                                                          \
 422   }                                                                                            \
 423   if (_tmp->next) {                                                                            \
 424     _tmp->next = (add);                                                                        \
 425   }                                                                                            \
 426  }                                                                                             \
 427 } while (0)
 428
 429 #define LL_REPLACE_ELEM(head, el, add)                                                         \
 430     LL_REPLACE_ELEM2(head, el, add, next)
 431
 432 #define LL_PREPEND_ELEM2(head, el, add, next)                                                  \
 433 do {                                                                                           \
 434  if (el) {                                                                                     \
 435   LDECLTYPE(head) _tmp;                                                                        \
 436   assert((head) != NULL);                                                                      \
 437   assert((add) != NULL);                                                                       \
 438   (add)->next = (el);                                                                          \
 439   if ((head) == (el)) {                                                                        \
 440    (head) = (add);                                                                             \
 441   } else {                                                                                     \
 442    _tmp = (head);                                                                              \
 443    while (_tmp->next && (_tmp->next != (el))) {                                                \
 444     _tmp = _tmp->next;                                                                         \
 445    }                                                                                           \
 446    if (_tmp->next) {                                                                           \
 447      _tmp->next = (add);                                                                       \
 448    }                                                                                           \
 449   }                                                                                            \
 450  } else {                                                                                      \
 451   LL_APPEND2(head, add, next);                                                                 \
 452  }                                                                                             \
 453 } while (0)                                                                                    \
 454
 455 #define LL_PREPEND_ELEM(head, el, add)                                                         \
 456     LL_PREPEND_ELEM2(head, el, add, next)
 457
 458 #define LL_APPEND_ELEM2(head, el, add, next)                                                   \
 459 do {                                                                                           \
 460  if (el) {                                                                                     \
 461   assert((head) != NULL);                                                                      \
 462   assert((add) != NULL);                                                                       \
 463   (add)->next = (el)->next;                                                                    \
 464   (el)->next = (add);                                                                          \
 465  } else {                                                                                      \
 466   LL_PREPEND2(head, add, next);                                                                \
 467  }                                                                                             \
 468 } while (0)                                                                                    \
 469
 470 #define LL_APPEND_ELEM(head, el, add)                                                          \
 471     LL_APPEND_ELEM2(head, el, add, next)
 472
 473 #ifdef NO_DECLTYPE
 474 /* Here are VS2008 / NO_DECLTYPE replacements for a few functions */
 475
 476 #undef LL_CONCAT2
 477 #define LL_CONCAT2(head1,head2,next)                                                           \
 478 do {                                                                                           \
 479   char *_tmp;                                                                                  \
 480   if (head1) {                                                                                 \
 481     _tmp = (char*)(head1);                                                                     \
 482     while ((head1)->next) { (head1) = (head1)->next; }                                         \
 483     (head1)->next = (head2);                                                                   \
 484     _RS(head1);                                                                                \
 485   } else {                                                                                     \
 486     (head1)=(head2);                                                                           \
 487   }                                                                                            \
 488 } while (0)
 489
 490 #undef LL_APPEND2
 491 #define LL_APPEND2(head,add,next)                                                              \
 492 do {                                                                                           \
 493   if (head) {                                                                                  \
 494     (add)->next = head;     /* use add->next as a temp variable */                             \
 495     while ((add)->next->next) { (add)->next = (add)->next->next; }                             \
 496     (add)->next->next=(add);                                                                   \
 497   } else {                                                                                     \
 498     (head)=(add);                                                                              \
 499   }                                                                                            \
 500   (add)->next=NULL;                                                                            \
 501 } while (0)
 502
 503 #undef LL_DELETE2
 504 #define LL_DELETE2(head,del,next)                                                              \
 505 do {                                                                                           \
 506   if ((head) == (del)) {                                                                       \
 507     (head)=(head)->next;                                                                       \
 508   } else {                                                                                     \
 509     char *_tmp = (char*)(head);                                                                \
 510     while ((head)->next && ((head)->next != (del))) {                                          \
 511       (head) = (head)->next;                                                                   \
 512     }                                                                                          \
 513     if ((head)->next) {                                                                        \
 514       (head)->next = ((del)->next);                                                            \
 515     }                                                                                          \
 516     _RS(head);                                                                                 \
 517   }                                                                                            \
 518 } while (0)
 519
 520 #undef LL_REPLACE_ELEM2
 521 #define LL_REPLACE_ELEM2(head, el, add, next)                                                  \
 522 do {                                                                                           \
 523   assert((head) != NULL);                                                                      \
 524   assert((el) != NULL);                                                                        \
 525   assert((add) != NULL);                                                                       \
 526   if ((head) == (el)) {                                                                        \
 527     (head) = (add);                                                                            \
 528   } else {                                                                                     \
 529     (add)->next = head;                                                                        \
 530     while ((add)->next->next && ((add)->next->next != (el))) {                                 \
 531       (add)->next = (add)->next->next;                                                         \
 532     }                                                                                          \
 533     if ((add)->next->next) {                                                                   \
 534       (add)->next->next = (add);                                                               \
 535     }                                                                                          \
 536   }                                                                                            \
 537   (add)->next = (el)->next;                                                                    \
 538 } while (0)
 539
 540 #undef LL_PREPEND_ELEM2
 541 #define LL_PREPEND_ELEM2(head, el, add, next)                                                  \
 542 do {                                                                                           \
 543   if (el) {                                                                                    \
 544     assert((head) != NULL);                                                                    \
 545     assert((add) != NULL);                                                                     \
 546     if ((head) == (el)) {                                                                      \
 547       (head) = (add);                                                                          \
 548     } else {                                                                                   \
 549       (add)->next = (head);                                                                    \
 550       while ((add)->next->next && ((add)->next->next != (el))) {                               \
 551         (add)->next = (add)->next->next;                                                       \
 552       }                                                                                        \
 553       if ((add)->next->next) {                                                                 \
 554         (add)->next->next = (add);                                                             \
 555       }                                                                                        \
 556     }                                                                                          \
 557     (add)->next = (el);                                                                        \
 558   } else {                                                                                     \
 559     LL_APPEND2(head, add, next);                                                               \
 560   }                                                                                            \
 561 } while (0)                                                                                    \
 562
 563 #endif /* NO_DECLTYPE */
 564
 565 /******************************************************************************
 566  * doubly linked list macros (non-circular)                                   *
 567  *****************************************************************************/
 568 #define DL_PREPEND(head,add)                                                                   \
 569     DL_PREPEND2(head,add,prev,next)
 570
 571 #define DL_PREPEND2(head,add,prev,next)                                                        \
 572 do {                                                                                           \
 573  (add)->next = (head);                                                                         \
 574  if (head) {                                                                                   \
 575    (add)->prev = (head)->prev;                                                                 \
 576    (head)->prev = (add);                                                                       \
 577  } else {                                                                                      \
 578    (add)->prev = (add);                                                                        \
 579  }                                                                                             \
 580  (head) = (add);                                                                               \
 581 } while (0)
 582
 583 #define DL_APPEND(head,add)                                                                    \
 584     DL_APPEND2(head,add,prev,next)
 585
 586 #define DL_APPEND2(head,add,prev,next)                                                         \
 587 do {                                                                                           \
 588   if (head) {                                                                                  \
 589       (add)->prev = (head)->prev;                                                              \
 590       (head)->prev->next = (add);                                                              \
 591       (head)->prev = (add);                                                                    \
 592       (add)->next = NULL;                                                                      \
 593   } else {                                                                                     \
 594       (head)=(add);                                                                            \
 595       (head)->prev = (head);                                                                   \
 596       (head)->next = NULL;                                                                     \
 597   }                                                                                            \
 598 } while (0)
 599
 600 #define DL_CONCAT(head1,head2)                                                                 \
 601     DL_CONCAT2(head1,head2,prev,next)
 602
 603 #define DL_CONCAT2(head1,head2,prev,next)                                                      \
 604 do {                                                                                           \
 605   LDECLTYPE(head1) _tmp;                                                                       \
 606   if (head2) {                                                                                 \
 607     if (head1) {                                                                               \
 608         _CASTASGN(_tmp, (head2)->prev);                                                        \
 609         (head2)->prev = (head1)->prev;                                                         \
 610         (head1)->prev->next = (head2);                                                         \
 611         _CASTASGN((head1)->prev, _tmp);                                                        \
 612     } else {                                                                                   \
 613         (head1)=(head2);                                                                       \
 614     }                                                                                          \
 615   }                                                                                            \
 616 } while (0)
 617
 618 #define DL_DELETE(head,del)                                                                    \
 619     DL_DELETE2(head,del,prev,next)
 620
 621 #define DL_DELETE2(head,del,prev,next)                                                         \
 622 do {                                                                                           \
 623   assert((del)->prev != NULL);                                                                 \
 624   if ((del)->prev == (del)) {                                                                  \
 625       (head)=NULL;                                                                             \
 626   } else if ((del)==(head)) {                                                                  \
 627       (del)->next->prev = (del)->prev;                                                         \
 628       (head) = (del)->next;                                                                    \
 629   } else {                                                                                     \
 630       (del)->prev->next = (del)->next;                                                         \
 631       if ((del)->next) {                                                                       \
 632           (del)->next->prev = (del)->prev;                                                     \
 633       } else {                                                                                 \
 634           (head)->prev = (del)->prev;                                                          \
 635       }                                                                                        \
 636   }                                                                                            \
 637 } while (0)
 638
 639 #define DL_COUNT(head,el,counter)                                                              \
 640     DL_COUNT2(head,el,counter,next)                                                            \
 641
 642 #define DL_COUNT2(head,el,counter,next)                                                        \
 643 do {                                                                                           \
 644   (counter) = 0;                                                                               \
 645   DL_FOREACH2(head,el,next) { ++(counter); }                                                   \
 646 } while (0)
 647
 648 #define DL_FOREACH(head,el)                                                                    \
 649     DL_FOREACH2(head,el,next)
 650
 651 #define DL_FOREACH2(head,el,next)                                                              \
 652     for ((el) = (head); el; (el) = (el)->next)
 653
 654 /* this version is safe for deleting the elements during iteration */
 655 #define DL_FOREACH_SAFE(head,el,tmp)                                                           \
 656     DL_FOREACH_SAFE2(head,el,tmp,next)
 657
 658 #define DL_FOREACH_SAFE2(head,el,tmp,next)                                                     \
 659   for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp))
 660
 661 /* these are identical to their singly-linked list counterparts */
 662 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
 663 #define DL_SEARCH LL_SEARCH
 664 #define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2
 665 #define DL_SEARCH2 LL_SEARCH2
 666
 667 #define DL_REPLACE_ELEM2(head, el, add, prev, next)                                            \
 668 do {                                                                                           \
 669  assert((head) != NULL);                                                                       \
 670  assert((el) != NULL);                                                                         \
 671  assert((add) != NULL);                                                                        \
 672  if ((head) == (el)) {                                                                         \
 673   (head) = (add);                                                                              \
 674   (add)->next = (el)->next;                                                                    \
 675   if ((el)->next == NULL) {                                                                    \
 676    (add)->prev = (add);                                                                        \
 677   } else {                                                                                     \
 678    (add)->prev = (el)->prev;                                                                   \
 679    (add)->next->prev = (add);                                                                  \
 680   }                                                                                            \
 681  } else {                                                                                      \
 682   (add)->next = (el)->next;                                                                    \
 683   (add)->prev = (el)->prev;                                                                    \
 684   (add)->prev->next = (add);                                                                   \
 685   if ((el)->next == NULL) {                                                                    \
 686    (head)->prev = (add);                                                                       \
 687   } else {                                                                                     \
 688    (add)->next->prev = (add);                                                                  \
 689   }                                                                                            \
 690  }                                                                                             \
 691 } while (0)
 692
 693 #define DL_REPLACE_ELEM(head, el, add)                                                         \
 694     DL_REPLACE_ELEM2(head, el, add, prev, next)
 695
 696 #define DL_PREPEND_ELEM2(head, el, add, prev, next)                                            \
 697 do {                                                                                           \
 698  if (el) {                                                                                     \
 699   assert((head) != NULL);                                                                      \
 700   assert((add) != NULL);                                                                       \
 701   (add)->next = (el);                                                                          \
 702   (add)->prev = (el)->prev;                                                                    \
 703   (el)->prev = (add);                                                                          \
 704   if ((head) == (el)) {                                                                        \
 705    (head) = (add);                                                                             \
 706   } else {                                                                                     \
 707    (add)->prev->next = (add);                                                                  \
 708   }                                                                                            \
 709  } else {                                                                                      \
 710   DL_APPEND2(head, add, prev, next);                                                           \
 711  }                                                                                             \
 712 } while (0)                                                                                    \
 713
 714 #define DL_PREPEND_ELEM(head, el, add)                                                         \
 715     DL_PREPEND_ELEM2(head, el, add, prev, next)
 716
 717 #define DL_APPEND_ELEM2(head, el, add, prev, next)                                             \
 718 do {                                                                                           \
 719  if (el) {                                                                                     \
 720   assert((head) != NULL);                                                                      \
 721   assert((add) != NULL);                                                                       \
 722   (add)->next = (el)->next;                                                                    \
 723   (add)->prev = (el);                                                                          \
 724   (el)->next = (add);                                                                          \
 725   if ((add)->next) {                                                                           \
 726    (add)->next->prev = (add);                                                                  \
 727   } else {                                                                                     \
 728    (head)->prev = (add);                                                                       \
 729   }                                                                                            \
 730  } else {                                                                                      \
 731   DL_PREPEND2(head, add, prev, next);                                                          \
 732  }                                                                                             \
 733 } while (0)                                                                                    \
 734
 735 #define DL_APPEND_ELEM(head, el, add)                                                          \
 736    DL_APPEND_ELEM2(head, el, add, prev, next)
 737
 738 /******************************************************************************
 739  * circular doubly linked list macros                                         *
 740  *****************************************************************************/
 741 #define CDL_APPEND(head,add)                                                                   \
 742     CDL_APPEND2(head,add,prev,next)
 743
 744 #define CDL_APPEND2(head,add,prev,next)                                                        \
 745 do {                                                                                           \
 746  if (head) {                                                                                   \
 747    (add)->prev = (head)->prev;                                                                 \
 748    (add)->next = (head);                                                                       \
 749    (head)->prev = (add);                                                                       \
 750    (add)->prev->next = (add);                                                                  \
 751  } else {                                                                                      \
 752    (add)->prev = (add);                                                                        \
 753    (add)->next = (add);                                                                        \
 754    (head) = (add);                                                                             \
 755  }                                                                                             \
 756 } while (0)
 757
 758 #define CDL_PREPEND(head,add)                                                                  \
 759     CDL_PREPEND2(head,add,prev,next)
 760
 761 #define CDL_PREPEND2(head,add,prev,next)                                                       \
 762 do {                                                                                           \
 763  if (head) {                                                                                   \
 764    (add)->prev = (head)->prev;                                                                 \
 765    (add)->next = (head);                                                                       \
 766    (head)->prev = (add);                                                                       \
 767    (add)->prev->next = (add);                                                                  \
 768  } else {                                                                                      \
 769    (add)->prev = (add);                                                                        \
 770    (add)->next = (add);                                                                        \
 771  }                                                                                             \
 772  (head) = (add);                                                                               \
 773 } while (0)
 774
 775 #define CDL_DELETE(head,del)                                                                   \
 776     CDL_DELETE2(head,del,prev,next)
 777
 778 #define CDL_DELETE2(head,del,prev,next)                                                        \
 779 do {                                                                                           \
 780   if (((head)==(del)) && ((head)->next == (head))) {                                           \
 781       (head) = NULL;                                                                           \
 782   } else {                                                                                     \
 783      (del)->next->prev = (del)->prev;                                                          \
 784      (del)->prev->next = (del)->next;                                                          \
 785      if ((del) == (head)) (head)=(del)->next;                                                  \
 786   }                                                                                            \
 787 } while (0)
 788
 789 #define CDL_COUNT(head,el,counter)                                                             \
 790     CDL_COUNT2(head,el,counter,next)                                                           \
 791
 792 #define CDL_COUNT2(head, el, counter,next)                                                     \
 793 do {                                                                                           \
 794   (counter) = 0;                                                                               \
 795   CDL_FOREACH2(head,el,next) { ++(counter); }                                                  \
 796 } while (0)
 797
 798 #define CDL_FOREACH(head,el)                                                                   \
 799     CDL_FOREACH2(head,el,next)
 800
 801 #define CDL_FOREACH2(head,el,next)                                                             \
 802     for ((el)=(head);el;(el)=(((el)->next==(head)) ? NULL : (el)->next))
 803
 804 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2)                                                    \
 805     CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
 806
 807 #define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)                                         \
 808   for ((el) = (head), (tmp1) = (head) ? (head)->prev : NULL;                                   \
 809        (el) && ((tmp2) = (el)->next, 1);                                                       \
 810        (el) = ((el) == (tmp1) ? NULL : (tmp2)))
 811
 812 #define CDL_SEARCH_SCALAR(head,out,field,val)                                                  \
 813     CDL_SEARCH_SCALAR2(head,out,field,val,next)
 814
 815 #define CDL_SEARCH_SCALAR2(head,out,field,val,next)                                            \
 816 do {                                                                                           \
 817     CDL_FOREACH2(head,out,next) {                                                              \
 818       if ((out)->field == (val)) break;                                                        \
 819     }                                                                                          \
 820 } while (0)
 821
 822 #define CDL_SEARCH(head,out,elt,cmp)                                                           \
 823     CDL_SEARCH2(head,out,elt,cmp,next)
 824
 825 #define CDL_SEARCH2(head,out,elt,cmp,next)                                                     \
 826 do {                                                                                           \
 827     CDL_FOREACH2(head,out,next) {                                                              \
 828       if ((cmp(out,elt))==0) break;                                                            \
 829     }                                                                                          \
 830 } while (0)
 831
 832 #define CDL_REPLACE_ELEM2(head, el, add, prev, next)                                           \
 833 do {                                                                                           \
 834  assert((head) != NULL);                                                                       \
 835  assert((el) != NULL);                                                                         \
 836  assert((add) != NULL);                                                                        \
 837  if ((el)->next == (el)) {                                                                     \
 838   (add)->next = (add);                                                                         \
 839   (add)->prev = (add);                                                                         \
 840   (head) = (add);                                                                              \
 841  } else {                                                                                      \
 842   (add)->next = (el)->next;                                                                    \
 843   (add)->prev = (el)->prev;                                                                    \
 844   (add)->next->prev = (add);                                                                   \
 845   (add)->prev->next = (add);                                                                   \
 846   if ((head) == (el)) {                                                                        \
 847    (head) = (add);                                                                             \
 848   }                                                                                            \
 849  }                                                                                             \
 850 } while (0)
 851
 852 #define CDL_REPLACE_ELEM(head, el, add)                                                        \
 853     CDL_REPLACE_ELEM2(head, el, add, prev, next)
 854
 855 #define CDL_PREPEND_ELEM2(head, el, add, prev, next)                                           \
 856 do {                                                                                           \
 857   if (el) {                                                                                    \
 858     assert((head) != NULL);                                                                    \
 859     assert((add) != NULL);                                                                     \
 860     (add)->next = (el);                                                                        \
 861     (add)->prev = (el)->prev;                                                                  \
 862     (el)->prev = (add);                                                                        \
 863     (add)->prev->next = (add);                                                                 \
 864     if ((head) == (el)) {                                                                      \
 865       (head) = (add);                                                                          \
 866     }                                                                                          \
 867   } else {                                                                                     \
 868     CDL_APPEND2(head, add, prev, next);                                                        \
 869   }                                                                                            \
 870 } while (0)
 871
 872 #define CDL_PREPEND_ELEM(head, el, add)                                                        \
 873     CDL_PREPEND_ELEM2(head, el, add, prev, next)
 874
 875 #define CDL_APPEND_ELEM2(head, el, add, prev, next)                                            \
 876 do {                                                                                           \
 877  if (el) {                                                                                     \
 878   assert((head) != NULL);                                                                      \
 879   assert((add) != NULL);                                                                       \
 880   (add)->next = (el)->next;                                                                    \
 881   (add)->prev = (el);                                                                          \
 882   (el)->next = (add);                                                                          \
 883   (add)->next->prev = (add);                                                                   \
 884  } else {                                                                                      \
 885   CDL_PREPEND2(head, add, prev, next);                                                         \
 886  }                                                                                             \
 887 } while (0)
 888
 889 #define CDL_APPEND_ELEM(head, el, add)                                                         \
 890     CDL_APPEND_ELEM2(head, el, add, prev, next)
 891
 892 #endif /* UTLIST_H */