lib/openbsd-queue.h

   1 // SPDX-License-Identifier: BSD-3-Clause
   2 /*      $OpenBSD: queue.h,v 1.43 2015/12/28 19:38:40 millert Exp $      */
   3 /*      $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $       */
   4
   5 /*
   6  * Copyright (c) 1991, 1993
   7  *      The Regents of the University of California.  All rights reserved.
   8  *
   9  *      @(#)queue.h     8.5 (Berkeley) 8/20/94
  10  */
  11
  12 #ifndef _SYS_QUEUE_H_
  13 #define _SYS_QUEUE_H_
  14
  15 #ifdef __cplusplus
  16 extern "C" {
  17 #endif
  18
  19 /*
  20  * This file defines five types of data structures: singly-linked lists,
  21  * lists, simple queues, tail queues and XOR simple queues.
  22  *
  23  *
  24  * A singly-linked list is headed by a single forward pointer. The elements
  25  * are singly linked for minimum space and pointer manipulation overhead at
  26  * the expense of O(n) removal for arbitrary elements. New elements can be
  27  * added to the list after an existing element or at the head of the list.
  28  * Elements being removed from the head of the list should use the explicit
  29  * macro for this purpose for optimum efficiency. A singly-linked list may
  30  * only be traversed in the forward direction.  Singly-linked lists are ideal
  31  * for applications with large datasets and few or no removals or for
  32  * implementing a LIFO queue.
  33  *
  34  * A list is headed by a single forward pointer (or an array of forward
  35  * pointers for a hash table header). The elements are doubly linked
  36  * so that an arbitrary element can be removed without a need to
  37  * traverse the list. New elements can be added to the list before
  38  * or after an existing element or at the head of the list. A list
  39  * may only be traversed in the forward direction.
  40  *
  41  * A simple queue is headed by a pair of pointers, one to the head of the
  42  * list and the other to the tail of the list. The elements are singly
  43  * linked to save space, so elements can only be removed from the
  44  * head of the list. New elements can be added to the list before or after
  45  * an existing element, at the head of the list, or at the end of the
  46  * list. A simple queue may only be traversed in the forward direction.
  47  *
  48  * A tail queue is headed by a pair of pointers, one to the head of the
  49  * list and the other to the tail of the list. The elements are doubly
  50  * linked so that an arbitrary element can be removed without a need to
  51  * traverse the list. New elements can be added to the list before or
  52  * after an existing element, at the head of the list, or at the end of
  53  * the list. A tail queue may be traversed in either direction.
  54  *
  55  * An XOR simple queue is used in the same way as a regular simple queue.
  56  * The difference is that the head structure also includes a "cookie" that
  57  * is XOR'd with the queue pointer (first, last or next) to generate the
  58  * real pointer value.
  59  *
  60  * For details on the use of these macros, see the queue(3) manual page.
  61  */
  62
  63 #if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
  64 #define _Q_INVALIDATE(a) (a) = ((void *)-1)
  65 #else
  66 #define _Q_INVALIDATE(a)
  67 #endif
  68
  69 /*
  70  * Singly-linked List definitions.
  71  */
  72 #define SLIST_HEAD(name, type)                                                 \
  73         struct name {                                                          \
  74                 struct type *slh_first; /* first element */                    \
  75         }
  76
  77 #define SLIST_HEAD_INITIALIZER(head)                                           \
  78         {                                                                      \
  79                 NULL                                                           \
  80         }
  81
  82 #define SLIST_ENTRY(type)                                                      \
  83         struct {                                                               \
  84                 struct type *sle_next; /* next element */                      \
  85         }
  86
  87 /*
  88  * Singly-linked List access methods.
  89  */
  90 #define SLIST_FIRST(head)       ((head)->slh_first)
  91 #define SLIST_END(head)         NULL
  92 #define SLIST_EMPTY(head)       (SLIST_FIRST(head) == SLIST_END(head))
  93 #define SLIST_NEXT(elm, field)  ((elm)->field.sle_next)
  94
  95 #define SLIST_FOREACH(var, head, field)                                        \
  96         for ((var) = SLIST_FIRST(head); (var) != SLIST_END(head);              \
  97              (var) = SLIST_NEXT(var, field))
  98
  99 #define SLIST_FOREACH_SAFE(var, head, field, tvar)                             \
 100         for ((var) = SLIST_FIRST(head);                                        \
 101              (var) && ((tvar) = SLIST_NEXT(var, field), 1); (var) = (tvar))
 102
 103 /*
 104  * Singly-linked List functions.
 105  */
 106 #define SLIST_INIT(head)                                                       \
 107         {                                                                      \
 108                 SLIST_FIRST(head) = SLIST_END(head);                           \
 109         }
 110
 111 #define SLIST_INSERT_AFTER(slistelm, elm, field)                               \
 112         do {                                                                   \
 113                 (elm)->field.sle_next = (slistelm)->field.sle_next;            \
 114                 (slistelm)->field.sle_next = (elm);                            \
 115         } while (0)
 116
 117 #define SLIST_INSERT_HEAD(head, elm, field)                                    \
 118         do {                                                                   \
 119                 (elm)->field.sle_next = (head)->slh_first;                     \
 120                 (head)->slh_first = (elm);                                     \
 121         } while (0)
 122
 123 #define SLIST_REMOVE_AFTER(elm, field)                                         \
 124         do {                                                                   \
 125                 (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \
 126         } while (0)
 127
 128 #define SLIST_REMOVE_HEAD(head, field)                                         \
 129         do {                                                                   \
 130                 (head)->slh_first = (head)->slh_first->field.sle_next;         \
 131         } while (0)
 132
 133 #define SLIST_REMOVE(head, elm, type, field)                                   \
 134         do {                                                                   \
 135                 if ((head)->slh_first == (elm)) {                              \
 136                         SLIST_REMOVE_HEAD((head), field);                      \
 137                 } else {                                                       \
 138                         struct type *curelm = (head)->slh_first;               \
 139                                                                                \
 140                         while (curelm->field.sle_next != (elm))                \
 141                                 curelm = curelm->field.sle_next;               \
 142                         curelm->field.sle_next =                               \
 143                                 curelm->field.sle_next->field.sle_next;        \
 144                 }                                                              \
 145                 _Q_INVALIDATE((elm)->field.sle_next);                          \
 146         } while (0)
 147
 148 /*
 149  * List definitions.
 150  */
 151 #define LIST_HEAD(name, type)                                                  \
 152         struct name {                                                          \
 153                 struct type *lh_first; /* first element */                     \
 154         }
 155
 156 #define LIST_HEAD_INITIALIZER(head)                                            \
 157         {                                                                      \
 158                 NULL                                                           \
 159         }
 160
 161 #define LIST_ENTRY(type)                                                       \
 162         struct {                                                               \
 163                 struct type *le_next;  /* next element */                      \
 164                 struct type **le_prev; /* address of previous next element */  \
 165         }
 166
 167 /*
 168  * List access methods.
 169  */
 170 #define LIST_FIRST(head)                ((head)->lh_first)
 171 #define LIST_END(head)                  NULL
 172 #define LIST_EMPTY(head)                (LIST_FIRST(head) == LIST_END(head))
 173 #define LIST_NEXT(elm, field)           ((elm)->field.le_next)
 174
 175 #define LIST_FOREACH(var, head, field)                                         \
 176         for ((var) = LIST_FIRST(head); (var) != LIST_END(head);                \
 177              (var) = LIST_NEXT(var, field))
 178
 179 #define LIST_FOREACH_SAFE(var, head, field, tvar)                              \
 180         for ((var) = LIST_FIRST(head);                                         \
 181              (var) && ((tvar) = LIST_NEXT(var, field), 1); (var) = (tvar))
 182
 183 /*
 184  * List functions.
 185  */
 186 #define LIST_INIT(head)                                                        \
 187         do {                                                                   \
 188                 LIST_FIRST(head) = LIST_END(head);                             \
 189         } while (0)
 190
 191 #define LIST_INSERT_AFTER(listelm, elm, field)                                 \
 192         do {                                                                   \
 193                 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
 194                         (listelm)->field.le_next->field.le_prev =              \
 195                                 &(elm)->field.le_next;                         \
 196                 (listelm)->field.le_next = (elm);                              \
 197                 (elm)->field.le_prev = &(listelm)->field.le_next;              \
 198         } while (0)
 199
 200 #define LIST_INSERT_BEFORE(listelm, elm, field)                                \
 201         do {                                                                   \
 202                 (elm)->field.le_prev = (listelm)->field.le_prev;               \
 203                 (elm)->field.le_next = (listelm);                              \
 204                 *(listelm)->field.le_prev = (elm);                             \
 205                 (listelm)->field.le_prev = &(elm)->field.le_next;              \
 206         } while (0)
 207
 208 #define LIST_INSERT_HEAD(head, elm, field)                                     \
 209         do {                                                                   \
 210                 if (((elm)->field.le_next = (head)->lh_first) != NULL)         \
 211                         (head)->lh_first->field.le_prev =                      \
 212                                 &(elm)->field.le_next;                         \
 213                 (head)->lh_first = (elm);                                      \
 214                 (elm)->field.le_prev = &(head)->lh_first;                      \
 215         } while (0)
 216
 217 #define LIST_REMOVE(elm, field)                                                \
 218         do {                                                                   \
 219                 if ((elm)->field.le_next != NULL)                              \
 220                         (elm)->field.le_next->field.le_prev =                  \
 221                                 (elm)->field.le_prev;                          \
 222                 *(elm)->field.le_prev = (elm)->field.le_next;                  \
 223                 _Q_INVALIDATE((elm)->field.le_prev);                           \
 224                 _Q_INVALIDATE((elm)->field.le_next);                           \
 225         } while (0)
 226
 227 #define LIST_REPLACE(elm, elm2, field)                                         \
 228         do {                                                                   \
 229                 if (((elm2)->field.le_next = (elm)->field.le_next) != NULL)    \
 230                         (elm2)->field.le_next->field.le_prev =                 \
 231                                 &(elm2)->field.le_next;                        \
 232                 (elm2)->field.le_prev = (elm)->field.le_prev;                  \
 233                 *(elm2)->field.le_prev = (elm2);                               \
 234                 _Q_INVALIDATE((elm)->field.le_prev);                           \
 235                 _Q_INVALIDATE((elm)->field.le_next);                           \
 236         } while (0)
 237
 238 /*
 239  * Simple queue definitions.
 240  */
 241 #define SIMPLEQ_HEAD(name, type)                                               \
 242         struct name {                                                          \
 243                 struct type *sqh_first; /* first element */                    \
 244                 struct type **sqh_last; /* addr of last next element */        \
 245         }
 246
 247 #define SIMPLEQ_HEAD_INITIALIZER(head)                                         \
 248         {                                                                      \
 249                 NULL, &(head).sqh_first                                        \
 250         }
 251
 252 #define SIMPLEQ_ENTRY(type)                                                    \
 253         struct {                                                               \
 254                 struct type *sqe_next; /* next element */                      \
 255         }
 256
 257 /*
 258  * Simple queue access methods.
 259  */
 260 #define SIMPLEQ_FIRST(head)         ((head)->sqh_first)
 261 #define SIMPLEQ_END(head)           NULL
 262 #define SIMPLEQ_EMPTY(head)         (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
 263 #define SIMPLEQ_NEXT(elm, field)    ((elm)->field.sqe_next)
 264
 265 #define SIMPLEQ_FOREACH(var, head, field)                                      \
 266         for ((var) = SIMPLEQ_FIRST(head); (var) != SIMPLEQ_END(head);          \
 267              (var) = SIMPLEQ_NEXT(var, field))
 268
 269 #define SIMPLEQ_FOREACH_SAFE(var, head, field, tvar)                           \
 270         for ((var) = SIMPLEQ_FIRST(head);                                      \
 271              (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1); (var) = (tvar))
 272
 273 /*
 274  * Simple queue functions.
 275  */
 276 #define SIMPLEQ_INIT(head)                                                     \
 277         do {                                                                   \
 278                 (head)->sqh_first = NULL;                                      \
 279                 (head)->sqh_last = &(head)->sqh_first;                         \
 280         } while (0)
 281
 282 #define SIMPLEQ_INSERT_HEAD(head, elm, field)                                  \
 283         do {                                                                   \
 284                 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)       \
 285                         (head)->sqh_last = &(elm)->field.sqe_next;             \
 286                 (head)->sqh_first = (elm);                                     \
 287         } while (0)
 288
 289 #define SIMPLEQ_INSERT_TAIL(head, elm, field)                                  \
 290         do {                                                                   \
 291                 (elm)->field.sqe_next = NULL;                                  \
 292                 *(head)->sqh_last = (elm);                                     \
 293                 (head)->sqh_last = &(elm)->field.sqe_next;                     \
 294         } while (0)
 295
 296 #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field)                        \
 297         do {                                                                   \
 298                 if (((elm)->field.sqe_next = (listelm)->field.sqe_next)        \
 299                     == NULL)                                                   \
 300                         (head)->sqh_last = &(elm)->field.sqe_next;             \
 301                 (listelm)->field.sqe_next = (elm);                             \
 302         } while (0)
 303
 304 #define SIMPLEQ_REMOVE_HEAD(head, field)                                       \
 305         do {                                                                   \
 306                 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next)    \
 307                     == NULL)                                                   \
 308                         (head)->sqh_last = &(head)->sqh_first;                 \
 309         } while (0)
 310
 311 #define SIMPLEQ_REMOVE_AFTER(head, elm, field)                                 \
 312         do {                                                                   \
 313                 if (((elm)->field.sqe_next =                                   \
 314                              (elm)->field.sqe_next->field.sqe_next)            \
 315                     == NULL)                                                   \
 316                         (head)->sqh_last = &(elm)->field.sqe_next;             \
 317         } while (0)
 318
 319 #define SIMPLEQ_CONCAT(head1, head2)                                           \
 320         do {                                                                   \
 321                 if (!SIMPLEQ_EMPTY((head2))) {                                 \
 322                         *(head1)->sqh_last = (head2)->sqh_first;               \
 323                         (head1)->sqh_last = (head2)->sqh_last;                 \
 324                         SIMPLEQ_INIT((head2));                                 \
 325                 }                                                              \
 326         } while (0)
 327
 328 /*
 329  * XOR Simple queue definitions.
 330  */
 331 #define XSIMPLEQ_HEAD(name, type)                                              \
 332         struct name {                                                          \
 333                 struct type *sqx_first; /* first element */                    \
 334                 struct type **sqx_last; /* addr of last next element */        \
 335                 unsigned long sqx_cookie;                                      \
 336         }
 337
 338 #define XSIMPLEQ_ENTRY(type)                                                   \
 339         struct {                                                               \
 340                 struct type *sqx_next; /* next element */                      \
 341         }
 342
 343 /*
 344  * XOR Simple queue access methods.
 345  */
 346 #define XSIMPLEQ_XOR(head, ptr)                                                \
 347         ((__typeof(ptr))((head)->sqx_cookie ^ (unsigned long)(ptr)))
 348 #define XSIMPLEQ_FIRST(head)        XSIMPLEQ_XOR(head, ((head)->sqx_first))
 349 #define XSIMPLEQ_END(head)          NULL
 350 #define XSIMPLEQ_EMPTY(head)        (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head))
 351 #define XSIMPLEQ_NEXT(head, elm, field)    XSIMPLEQ_XOR(head, ((elm)->field.sqx_next))
 352
 353 #define XSIMPLEQ_FOREACH(var, head, field)                                     \
 354         for ((var) = XSIMPLEQ_FIRST(head); (var) != XSIMPLEQ_END(head);        \
 355              (var) = XSIMPLEQ_NEXT(head, var, field))
 356
 357 #define XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar)                          \
 358         for ((var) = XSIMPLEQ_FIRST(head);                                     \
 359              (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1);           \
 360              (var) = (tvar))
 361
 362 /*
 363  * XOR Simple queue functions.
 364  */
 365 #define XSIMPLEQ_INIT(head)                                                    \
 366         do {                                                                   \
 367                 arc4random_buf(&(head)->sqx_cookie,                            \
 368                                sizeof((head)->sqx_cookie));                    \
 369                 (head)->sqx_first = XSIMPLEQ_XOR(head, NULL);                  \
 370                 (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first);     \
 371         } while (0)
 372
 373 #define XSIMPLEQ_INSERT_HEAD(head, elm, field)                                 \
 374         do {                                                                   \
 375                 if (((elm)->field.sqx_next = (head)->sqx_first)                \
 376                     == XSIMPLEQ_XOR(head, NULL))                               \
 377                         (head)->sqx_last =                                     \
 378                                 XSIMPLEQ_XOR(head, &(elm)->field.sqx_next);    \
 379                 (head)->sqx_first = XSIMPLEQ_XOR(head, (elm));                 \
 380         } while (0)
 381
 382 #define XSIMPLEQ_INSERT_TAIL(head, elm, field)                                 \
 383         do {                                                                   \
 384                 (elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL);              \
 385                 *(XSIMPLEQ_XOR(head, (head)->sqx_last)) =                      \
 386                         XSIMPLEQ_XOR(head, (elm));                             \
 387                 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
 388         } while (0)
 389
 390 #define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field)                       \
 391         do {                                                                   \
 392                 if (((elm)->field.sqx_next = (listelm)->field.sqx_next)        \
 393                     == XSIMPLEQ_XOR(head, NULL))                               \
 394                         (head)->sqx_last =                                     \
 395                                 XSIMPLEQ_XOR(head, &(elm)->field.sqx_next);    \
 396                 (listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm));         \
 397         } while (0)
 398
 399 #define XSIMPLEQ_REMOVE_HEAD(head, field)                                      \
 400         do {                                                                   \
 401                 if (((head)->sqx_first = XSIMPLEQ_XOR(head, (head)->sqx_first) \
 402                                                  ->field.sqx_next)             \
 403                     == XSIMPLEQ_XOR(head, NULL))                               \
 404                         (head)->sqx_last =                                     \
 405                                 XSIMPLEQ_XOR(head, &(head)->sqx_first);        \
 406         } while (0)
 407
 408 #define XSIMPLEQ_REMOVE_AFTER(head, elm, field)                                \
 409         do {                                                                   \
 410                 if (((elm)->field.sqx_next =                                   \
 411                              XSIMPLEQ_XOR(head, (elm)->field.sqx_next)         \
 412                                      ->field.sqx_next)                         \
 413                     == XSIMPLEQ_XOR(head, NULL))                               \
 414                         (head)->sqx_last =                                     \
 415                                 XSIMPLEQ_XOR(head, &(elm)->field.sqx_next);    \
 416         } while (0)
 417
 418
 419 /*
 420  * Tail queue definitions.
 421  */
 422 #define TAILQ_HEAD(name, type)                                                 \
 423         struct name {                                                          \
 424                 struct type *tqh_first; /* first element */                    \
 425                 struct type **tqh_last; /* addr of last next element */        \
 426         }
 427
 428 #define TAILQ_HEAD_INITIALIZER(head)                                           \
 429         {                                                                      \
 430                 NULL, &(head).tqh_first                                        \
 431         }
 432
 433 #define TAILQ_ENTRY(type)                                                      \
 434         struct {                                                               \
 435                 struct type *tqe_next;  /* next element */                     \
 436                 struct type **tqe_prev; /* address of previous next element */ \
 437         }
 438
 439 /*
 440  * Tail queue access methods.
 441  */
 442 #define TAILQ_FIRST(head)               ((head)->tqh_first)
 443 #define TAILQ_END(head)                 NULL
 444 #define TAILQ_NEXT(elm, field)          ((elm)->field.tqe_next)
 445 #define TAILQ_LAST(head, headname)                                             \
 446         (*(((struct headname *)((head)->tqh_last))->tqh_last))
 447 /* XXX */
 448 #define TAILQ_PREV(elm, headname, field)                                       \
 449         (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
 450 #define TAILQ_EMPTY(head) (TAILQ_FIRST(head) == TAILQ_END(head))
 451
 452 #define TAILQ_FOREACH(var, head, field)                                        \
 453         for ((var) = TAILQ_FIRST(head); (var) != TAILQ_END(head);              \
 454              (var) = TAILQ_NEXT(var, field))
 455
 456 #define TAILQ_FOREACH_SAFE(var, head, field, tvar)                             \
 457         for ((var) = TAILQ_FIRST(head);                                        \
 458              (var) != TAILQ_END(head) && ((tvar) = TAILQ_NEXT(var, field), 1); \
 459              (var) = (tvar))
 460
 461
 462 #define TAILQ_FOREACH_REVERSE(var, head, headname, field)                      \
 463         for ((var) = TAILQ_LAST(head, headname); (var) != TAILQ_END(head);     \
 464              (var) = TAILQ_PREV(var, headname, field))
 465
 466 #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)           \
 467         for ((var) = TAILQ_LAST(head, headname);                               \
 468              (var) != TAILQ_END(head)                                          \
 469              && ((tvar) = TAILQ_PREV(var, headname, field), 1);                \
 470              (var) = (tvar))
 471
 472 /*
 473  * Tail queue functions.
 474  */
 475 #define TAILQ_INIT(head)                                                       \
 476         do {                                                                   \
 477                 (head)->tqh_first = NULL;                                      \
 478                 (head)->tqh_last = &(head)->tqh_first;                         \
 479         } while (0)
 480
 481 #define TAILQ_INSERT_HEAD(head, elm, field)                                    \
 482         do {                                                                   \
 483                 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)       \
 484                         (head)->tqh_first->field.tqe_prev =                    \
 485                                 &(elm)->field.tqe_next;                        \
 486                 else                                                           \
 487                         (head)->tqh_last = &(elm)->field.tqe_next;             \
 488                 (head)->tqh_first = (elm);                                     \
 489                 (elm)->field.tqe_prev = &(head)->tqh_first;                    \
 490         } while (0)
 491
 492 #define TAILQ_INSERT_TAIL(head, elm, field)                                    \
 493         do {                                                                   \
 494                 (elm)->field.tqe_next = NULL;                                  \
 495                 (elm)->field.tqe_prev = (head)->tqh_last;                      \
 496                 *(head)->tqh_last = (elm);                                     \
 497                 (head)->tqh_last = &(elm)->field.tqe_next;                     \
 498         } while (0)
 499
 500 #define TAILQ_INSERT_AFTER(head, listelm, elm, field)                          \
 501         do {                                                                   \
 502                 if (((elm)->field.tqe_next = (listelm)->field.tqe_next)        \
 503                     != NULL)                                                   \
 504                         (elm)->field.tqe_next->field.tqe_prev =                \
 505                                 &(elm)->field.tqe_next;                        \
 506                 else                                                           \
 507                         (head)->tqh_last = &(elm)->field.tqe_next;             \
 508                 (listelm)->field.tqe_next = (elm);                             \
 509                 (elm)->field.tqe_prev = &(listelm)->field.tqe_next;            \
 510         } while (0)
 511
 512 #define TAILQ_INSERT_BEFORE(listelm, elm, field)                               \
 513         do {                                                                   \
 514                 (elm)->field.tqe_prev = (listelm)->field.tqe_prev;             \
 515                 (elm)->field.tqe_next = (listelm);                             \
 516                 *(listelm)->field.tqe_prev = (elm);                            \
 517                 (listelm)->field.tqe_prev = &(elm)->field.tqe_next;            \
 518         } while (0)
 519
 520 #define TAILQ_REMOVE(head, elm, field)                                         \
 521         do {                                                                   \
 522                 if (((elm)->field.tqe_next) != NULL)                           \
 523                         (elm)->field.tqe_next->field.tqe_prev =                \
 524                                 (elm)->field.tqe_prev;                         \
 525                 else                                                           \
 526                         (head)->tqh_last = (elm)->field.tqe_prev;              \
 527                 *(elm)->field.tqe_prev = (elm)->field.tqe_next;                \
 528                 _Q_INVALIDATE((elm)->field.tqe_prev);                          \
 529                 _Q_INVALIDATE((elm)->field.tqe_next);                          \
 530         } while (0)
 531
 532 #define TAILQ_REPLACE(head, elm, elm2, field)                                  \
 533         do {                                                                   \
 534                 if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL)  \
 535                         (elm2)->field.tqe_next->field.tqe_prev =               \
 536                                 &(elm2)->field.tqe_next;                       \
 537                 else                                                           \
 538                         (head)->tqh_last = &(elm2)->field.tqe_next;            \
 539                 (elm2)->field.tqe_prev = (elm)->field.tqe_prev;                \
 540                 *(elm2)->field.tqe_prev = (elm2);                              \
 541                 _Q_INVALIDATE((elm)->field.tqe_prev);                          \
 542                 _Q_INVALIDATE((elm)->field.tqe_next);                          \
 543         } while (0)
 544
 545 #define TAILQ_CONCAT(head1, head2, field)                                      \
 546         do {                                                                   \
 547                 if (!TAILQ_EMPTY(head2)) {                                     \
 548                         *(head1)->tqh_last = (head2)->tqh_first;               \
 549                         (head2)->tqh_first->field.tqe_prev =                   \
 550                                 (head1)->tqh_last;                             \
 551                         (head1)->tqh_last = (head2)->tqh_last;                 \
 552                         TAILQ_INIT((head2));                                   \
 553                 }                                                              \
 554         } while (0)
 555
 556 #ifdef __cplusplus
 557 }
 558 #endif
 559
 560 #endif /* !_SYS_QUEUE_H_ */