root/src/dps8/utlist.h

/* [previous][next][first][last][top][bottom][index][help] */

INCLUDED FROM


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

/* [previous][next][first][last][top][bottom][index][help] */