git.sur5r.net Git - i3/i3/blob - include/queue.h

   1 /*      $OpenBSD: queue.h,v 1.1 2007/10/26 03:14:08 niallo Exp $        */
   2 /*      $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $       */
   3
   4 /*
   5  * Copyright (c) 1991, 1993
   6  *      The Regents of the University of California.  All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. Neither the name of the University nor the names of its contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  *
  32  *      @(#)queue.h     8.5 (Berkeley) 8/20/94
  33  */
  34
  35 #pragma once
  36
  37 /*
  38  * This file defines five types of data structures: singly-linked lists,
  39  * lists, simple queues, tail queues, and circular queues.
  40  *
  41  *
  42  * A singly-linked list is headed by a single forward pointer. The elements
  43  * are singly linked for minimum space and pointer manipulation overhead at
  44  * the expense of O(n) removal for arbitrary elements. New elements can be
  45  * added to the list after an existing element or at the head of the list.
  46  * Elements being removed from the head of the list should use the explicit
  47  * macro for this purpose for optimum efficiency. A singly-linked list may
  48  * only be traversed in the forward direction.  Singly-linked lists are ideal
  49  * for applications with large datasets and few or no removals or for
  50  * implementing a LIFO queue.
  51  *
  52  * A list is headed by a single forward pointer (or an array of forward
  53  * pointers for a hash table header). The elements are doubly linked
  54  * so that an arbitrary element can be removed without a need to
  55  * traverse the list. New elements can be added to the list before
  56  * or after an existing element or at the head of the list. A list
  57  * may only be traversed in the forward direction.
  58  *
  59  * A simple queue is headed by a pair of pointers, one the head of the
  60  * list and the other to the tail of the list. The elements are singly
  61  * linked to save space, so elements can only be removed from the
  62  * head of the list. New elements can be added to the list before or after
  63  * an existing element, at the head of the list, or at the end of the
  64  * list. A simple queue may only be traversed in the forward direction.
  65  *
  66  * A tail queue is headed by a pair of pointers, one to the head of the
  67  * list and the other to the tail of the list. The elements are doubly
  68  * linked so that an arbitrary element can be removed without a need to
  69  * traverse the list. New elements can be added to the list before or
  70  * after an existing element, at the head of the list, or at the end of
  71  * the list. A tail queue may be traversed in either direction.
  72  *
  73  * A circle queue is headed by a pair of pointers, one to the head of the
  74  * list and the other to the tail of the list. The elements are doubly
  75  * linked so that an arbitrary element can be removed without a need to
  76  * traverse the list. New elements can be added to the list before or after
  77  * an existing element, at the head of the list, or at the end of the list.
  78  * A circle queue may be traversed in either direction, but has a more
  79  * complex end of list detection.
  80  *
  81  * For details on the use of these macros, see the queue(3) manual page.
  82  */
  83
  84 #if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
  85 #define _Q_INVALIDATE(a) (a) = ((void *)-1)
  86 #else
  87 #define _Q_INVALIDATE(a)
  88 #endif
  89
  90 /*
  91  * Singly-linked List definitions.
  92  */
  93 #define SLIST_HEAD(name, type)                      \
  94     struct name {                                   \
  95         struct type *slh_first; /* first element */ \
  96     }
  97
  98 #define SLIST_HEAD_INITIALIZER(head) \
  99     { NULL }
 100
 101 #define SLIST_ENTRY(type)                         \
 102     struct {                                      \
 103         struct type *sle_next; /* next element */ \
 104     }
 105
 106 /*
 107  * Singly-linked List access methods.
 108  */
 109 #define SLIST_FIRST(head) ((head)->slh_first)
 110 #define SLIST_END(head) NULL
 111 #define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head))
 112 #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
 113
 114 #define SLIST_FOREACH(var, head, field) \
 115     for ((var) = SLIST_FIRST(head);     \
 116          (var) != SLIST_END(head);      \
 117          (var) = SLIST_NEXT(var, field))
 118
 119 #define SLIST_FOREACH_PREVPTR(var, varp, head, field) \
 120     for ((varp) = &SLIST_FIRST((head));               \
 121          ((var) = *(varp)) != SLIST_END(head);        \
 122          (varp) = &SLIST_NEXT((var), field))
 123
 124 /*
 125  * Singly-linked List functions.
 126  */
 127 #define SLIST_INIT(head)                     \
 128     {                                        \
 129         SLIST_FIRST(head) = SLIST_END(head); \
 130     }
 131
 132 #define SLIST_INSERT_AFTER(slistelm, elm, field)            \
 133     do {                                                    \
 134         (elm)->field.sle_next = (slistelm)->field.sle_next; \
 135         (slistelm)->field.sle_next = (elm);                 \
 136     } while (0)
 137
 138 #define SLIST_INSERT_HEAD(head, elm, field)        \
 139     do {                                           \
 140         (elm)->field.sle_next = (head)->slh_first; \
 141         (head)->slh_first = (elm);                 \
 142     } while (0)
 143
 144 #define SLIST_REMOVE_NEXT(head, elm, field)                            \
 145     do {                                                               \
 146         (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \
 147     } while (0)
 148
 149 #define SLIST_REMOVE_HEAD(head, field)                         \
 150     do {                                                       \
 151         (head)->slh_first = (head)->slh_first->field.sle_next; \
 152     } while (0)
 153
 154 #define SLIST_REMOVE(head, elm, type, field)                                 \
 155     do {                                                                     \
 156         if ((head)->slh_first == (elm)) {                                    \
 157             SLIST_REMOVE_HEAD((head), field);                                \
 158         } else {                                                             \
 159             struct type *curelm = (head)->slh_first;                         \
 160                                                                              \
 161             while (curelm->field.sle_next != (elm))                          \
 162                 curelm = curelm->field.sle_next;                             \
 163             curelm->field.sle_next = curelm->field.sle_next->field.sle_next; \
 164             _Q_INVALIDATE((elm)->field.sle_next);                            \
 165         }                                                                    \
 166     } while (0)
 167
 168 /*
 169  * List definitions.
 170  */
 171 #define LIST_HEAD(name, type)                      \
 172     struct name {                                  \
 173         struct type *lh_first; /* first element */ \
 174     }
 175
 176 #define LIST_HEAD_INITIALIZER(head) \
 177     { NULL }
 178
 179 #define LIST_ENTRY(type)                                              \
 180     struct {                                                          \
 181         struct type *le_next;  /* next element */                     \
 182         struct type **le_prev; /* address of previous next element */ \
 183     }
 184
 185 /*
 186  * List access methods
 187  */
 188 #define LIST_FIRST(head) ((head)->lh_first)
 189 #define LIST_END(head) NULL
 190 #define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head))
 191 #define LIST_NEXT(elm, field) ((elm)->field.le_next)
 192
 193 #define LIST_FOREACH(var, head, field) \
 194     for ((var) = LIST_FIRST(head);     \
 195          (var) != LIST_END(head);      \
 196          (var) = LIST_NEXT(var, field))
 197
 198 /*
 199  * List functions.
 200  */
 201 #define LIST_INIT(head)                    \
 202     do {                                   \
 203         LIST_FIRST(head) = LIST_END(head); \
 204     } while (0)
 205
 206 #define LIST_INSERT_AFTER(listelm, elm, field)                               \
 207     do {                                                                     \
 208         if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)       \
 209             (listelm)->field.le_next->field.le_prev = &(elm)->field.le_next; \
 210         (listelm)->field.le_next = (elm);                                    \
 211         (elm)->field.le_prev = &(listelm)->field.le_next;                    \
 212     } while (0)
 213
 214 #define LIST_INSERT_BEFORE(listelm, elm, field)           \
 215     do {                                                  \
 216         (elm)->field.le_prev = (listelm)->field.le_prev;  \
 217         (elm)->field.le_next = (listelm);                 \
 218         *(listelm)->field.le_prev = (elm);                \
 219         (listelm)->field.le_prev = &(elm)->field.le_next; \
 220     } while (0)
 221
 222 #define LIST_INSERT_HEAD(head, elm, field)                           \
 223     do {                                                             \
 224         if (((elm)->field.le_next = (head)->lh_first) != NULL)       \
 225             (head)->lh_first->field.le_prev = &(elm)->field.le_next; \
 226         (head)->lh_first = (elm);                                    \
 227         (elm)->field.le_prev = &(head)->lh_first;                    \
 228     } while (0)
 229
 230 #define LIST_REMOVE(elm, field)                                         \
 231     do {                                                                \
 232         if ((elm)->field.le_next != NULL)                               \
 233             (elm)->field.le_next->field.le_prev = (elm)->field.le_prev; \
 234         *(elm)->field.le_prev = (elm)->field.le_next;                   \
 235         _Q_INVALIDATE((elm)->field.le_prev);                            \
 236         _Q_INVALIDATE((elm)->field.le_next);                            \
 237     } while (0)
 238
 239 #define LIST_REPLACE(elm, elm2, field)                                     \
 240     do {                                                                   \
 241         if (((elm2)->field.le_next = (elm)->field.le_next) != NULL)        \
 242             (elm2)->field.le_next->field.le_prev = &(elm2)->field.le_next; \
 243         (elm2)->field.le_prev = (elm)->field.le_prev;                      \
 244         *(elm2)->field.le_prev = (elm2);                                   \
 245         _Q_INVALIDATE((elm)->field.le_prev);                               \
 246         _Q_INVALIDATE((elm)->field.le_next);                               \
 247     } while (0)
 248
 249 /*
 250  * Simple queue definitions.
 251  */
 252 #define SIMPLEQ_HEAD(name, type)                                \
 253     struct name {                                               \
 254         struct type *sqh_first; /* first element */             \
 255         struct type **sqh_last; /* addr of last next element */ \
 256     }
 257
 258 #define SIMPLEQ_HEAD_INITIALIZER(head) \
 259     { NULL, &(head).sqh_first }
 260
 261 #define SIMPLEQ_ENTRY(type)                       \
 262     struct {                                      \
 263         struct type *sqe_next; /* next element */ \
 264     }
 265
 266 /*
 267  * Simple queue access methods.
 268  */
 269 #define SIMPLEQ_FIRST(head) ((head)->sqh_first)
 270 #define SIMPLEQ_END(head) NULL
 271 #define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
 272 #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
 273
 274 #define SIMPLEQ_FOREACH(var, head, field) \
 275     for ((var) = SIMPLEQ_FIRST(head);     \
 276          (var) != SIMPLEQ_END(head);      \
 277          (var) = SIMPLEQ_NEXT(var, field))
 278
 279 /*
 280  * Simple queue functions.
 281  */
 282 #define SIMPLEQ_INIT(head)                     \
 283     do {                                       \
 284         (head)->sqh_first = NULL;              \
 285         (head)->sqh_last = &(head)->sqh_first; \
 286     } while (0)
 287
 288 #define SIMPLEQ_INSERT_HEAD(head, elm, field)                    \
 289     do {                                                         \
 290         if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
 291             (head)->sqh_last = &(elm)->field.sqe_next;           \
 292         (head)->sqh_first = (elm);                               \
 293     } while (0)
 294
 295 #define SIMPLEQ_INSERT_TAIL(head, elm, field)      \
 296     do {                                           \
 297         (elm)->field.sqe_next = NULL;              \
 298         *(head)->sqh_last = (elm);                 \
 299         (head)->sqh_last = &(elm)->field.sqe_next; \
 300     } while (0)
 301
 302 #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field)                  \
 303     do {                                                                 \
 304         if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL) \
 305             (head)->sqh_last = &(elm)->field.sqe_next;                   \
 306         (listelm)->field.sqe_next = (elm);                               \
 307     } while (0)
 308
 309 #define SIMPLEQ_REMOVE_HEAD(head, field)                                     \
 310     do {                                                                     \
 311         if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
 312             (head)->sqh_last = &(head)->sqh_first;                           \
 313     } while (0)
 314
 315 /*
 316  * Tail queue definitions.
 317  */
 318 #define TAILQ_HEAD(name, type)                                  \
 319     struct name {                                               \
 320         struct type *tqh_first; /* first element */             \
 321         struct type **tqh_last; /* addr of last next element */ \
 322     }
 323
 324 #define TAILQ_HEAD_INITIALIZER(head) \
 325     { NULL, &(head).tqh_first }
 326
 327 #define TAILQ_ENTRY(type)                                              \
 328     struct {                                                           \
 329         struct type *tqe_next;  /* next element */                     \
 330         struct type **tqe_prev; /* address of previous next element */ \
 331     }
 332
 333 /*
 334  * tail queue access methods
 335  */
 336 #define TAILQ_FIRST(head) ((head)->tqh_first)
 337 #define TAILQ_END(head) NULL
 338 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
 339 #define TAILQ_LAST(head, headname) \
 340     (*(((struct headname *)((head)->tqh_last))->tqh_last))
 341 /* XXX */
 342 #define TAILQ_PREV(elm, headname, field) \
 343     (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
 344 #define TAILQ_EMPTY(head) \
 345     (TAILQ_FIRST(head) == TAILQ_END(head))
 346
 347 #define TAILQ_FOREACH(var, head, field) \
 348     for ((var) = TAILQ_FIRST(head);     \
 349          (var) != TAILQ_END(head);      \
 350          (var) = TAILQ_NEXT(var, field))
 351
 352 #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
 353     for ((var) = TAILQ_LAST(head, headname);              \
 354          (var) != TAILQ_END(head);                        \
 355          (var) = TAILQ_PREV(var, headname, field))
 356
 357 /*
 358  * Tail queue functions.
 359  */
 360 #define TAILQ_INIT(head)                       \
 361     do {                                       \
 362         (head)->tqh_first = NULL;              \
 363         (head)->tqh_last = &(head)->tqh_first; \
 364     } while (0)
 365
 366 #define TAILQ_INSERT_HEAD(head, elm, field)                             \
 367     do {                                                                \
 368         if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)        \
 369             (head)->tqh_first->field.tqe_prev = &(elm)->field.tqe_next; \
 370         else                                                            \
 371             (head)->tqh_last = &(elm)->field.tqe_next;                  \
 372         (head)->tqh_first = (elm);                                      \
 373         (elm)->field.tqe_prev = &(head)->tqh_first;                     \
 374     } while (0)
 375
 376 #define TAILQ_INSERT_TAIL(head, elm, field)        \
 377     do {                                           \
 378         (elm)->field.tqe_next = NULL;              \
 379         (elm)->field.tqe_prev = (head)->tqh_last;  \
 380         *(head)->tqh_last = (elm);                 \
 381         (head)->tqh_last = &(elm)->field.tqe_next; \
 382     } while (0)
 383
 384 #define TAILQ_INSERT_AFTER(head, listelm, elm, field)                       \
 385     do {                                                                    \
 386         if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)    \
 387             (elm)->field.tqe_next->field.tqe_prev = &(elm)->field.tqe_next; \
 388         else                                                                \
 389             (head)->tqh_last = &(elm)->field.tqe_next;                      \
 390         (listelm)->field.tqe_next = (elm);                                  \
 391         (elm)->field.tqe_prev = &(listelm)->field.tqe_next;                 \
 392     } while (0)
 393
 394 #define TAILQ_INSERT_BEFORE(listelm, elm, field)            \
 395     do {                                                    \
 396         (elm)->field.tqe_prev = (listelm)->field.tqe_prev;  \
 397         (elm)->field.tqe_next = (listelm);                  \
 398         *(listelm)->field.tqe_prev = (elm);                 \
 399         (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
 400     } while (0)
 401
 402 #define TAILQ_REMOVE(head, elm, field)                                     \
 403     do {                                                                   \
 404         if (((elm)->field.tqe_next) != NULL)                               \
 405             (elm)->field.tqe_next->field.tqe_prev = (elm)->field.tqe_prev; \
 406         else                                                               \
 407             (head)->tqh_last = (elm)->field.tqe_prev;                      \
 408         *(elm)->field.tqe_prev = (elm)->field.tqe_next;                    \
 409         _Q_INVALIDATE((elm)->field.tqe_prev);                              \
 410         _Q_INVALIDATE((elm)->field.tqe_next);                              \
 411     } while (0)
 412
 413 #define TAILQ_REPLACE(head, elm, elm2, field)                                 \
 414     do {                                                                      \
 415         if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL)         \
 416             (elm2)->field.tqe_next->field.tqe_prev = &(elm2)->field.tqe_next; \
 417         else                                                                  \
 418             (head)->tqh_last = &(elm2)->field.tqe_next;                       \
 419         (elm2)->field.tqe_prev = (elm)->field.tqe_prev;                       \
 420         *(elm2)->field.tqe_prev = (elm2);                                     \
 421         _Q_INVALIDATE((elm)->field.tqe_prev);                                 \
 422         _Q_INVALIDATE((elm)->field.tqe_next);                                 \
 423     } while (0)
 424
 425 /* Swaps two consecutive elements. 'second' *MUST* follow 'first' */
 426 #define TAILQ_SWAP(first, second, head, field)                                     \
 427     do {                                                                           \
 428         *((first)->field.tqe_prev) = (second);                                     \
 429         (second)->field.tqe_prev = (first)->field.tqe_prev;                        \
 430         (first)->field.tqe_prev = &((second)->field.tqe_next);                     \
 431         (first)->field.tqe_next = (second)->field.tqe_next;                        \
 432         if ((second)->field.tqe_next)                                              \
 433             (second)->field.tqe_next->field.tqe_prev = &((first)->field.tqe_next); \
 434         (second)->field.tqe_next = first;                                          \
 435         if ((head)->tqh_last == &((second)->field.tqe_next))                       \
 436             (head)->tqh_last = &((first)->field.tqe_next);                         \
 437     } while (0)
 438
 439 /*
 440  * Circular queue definitions.
 441  */
 442 #define CIRCLEQ_HEAD(name, type)                    \
 443     struct name {                                   \
 444         struct type *cqh_first; /* first element */ \
 445         struct type *cqh_last;  /* last element */  \
 446     }
 447
 448 #define CIRCLEQ_HEAD_INITIALIZER(head) \
 449     { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
 450
 451 #define CIRCLEQ_ENTRY(type)                           \
 452     struct {                                          \
 453         struct type *cqe_next; /* next element */     \
 454         struct type *cqe_prev; /* previous element */ \
 455     }
 456
 457 /*
 458  * Circular queue access methods
 459  */
 460 #define CIRCLEQ_FIRST(head) ((head)->cqh_first)
 461 #define CIRCLEQ_LAST(head) ((head)->cqh_last)
 462 #define CIRCLEQ_END(head) ((void *)(head))
 463 #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
 464 #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
 465 #define CIRCLEQ_EMPTY(head) \
 466     (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
 467
 468 #define CIRCLEQ_FOREACH(var, head, field) \
 469     for ((var) = CIRCLEQ_FIRST(head);     \
 470          (var) != CIRCLEQ_END(head);      \
 471          (var) = CIRCLEQ_NEXT(var, field))
 472
 473 #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
 474     for ((var) = CIRCLEQ_LAST(head);              \
 475          (var) != CIRCLEQ_END(head);              \
 476          (var) = CIRCLEQ_PREV(var, field))
 477
 478 /*
 479  * Circular queue functions.
 480  */
 481 #define CIRCLEQ_INIT(head)                     \
 482     do {                                       \
 483         (head)->cqh_first = CIRCLEQ_END(head); \
 484         (head)->cqh_last = CIRCLEQ_END(head);  \
 485     } while (0)
 486
 487 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field)        \
 488     do {                                                       \
 489         (elm)->field.cqe_next = (listelm)->field.cqe_next;     \
 490         (elm)->field.cqe_prev = (listelm);                     \
 491         if ((listelm)->field.cqe_next == CIRCLEQ_END(head))    \
 492             (head)->cqh_last = (elm);                          \
 493         else                                                   \
 494             (listelm)->field.cqe_next->field.cqe_prev = (elm); \
 495         (listelm)->field.cqe_next = (elm);                     \
 496     } while (0)
 497
 498 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field)       \
 499     do {                                                       \
 500         (elm)->field.cqe_next = (listelm);                     \
 501         (elm)->field.cqe_prev = (listelm)->field.cqe_prev;     \
 502         if ((listelm)->field.cqe_prev == CIRCLEQ_END(head))    \
 503             (head)->cqh_first = (elm);                         \
 504         else                                                   \
 505             (listelm)->field.cqe_prev->field.cqe_next = (elm); \
 506         (listelm)->field.cqe_prev = (elm);                     \
 507     } while (0)
 508
 509 #define CIRCLEQ_INSERT_HEAD(head, elm, field)          \
 510     do {                                               \
 511         (elm)->field.cqe_next = (head)->cqh_first;     \
 512         (elm)->field.cqe_prev = CIRCLEQ_END(head);     \
 513         if ((head)->cqh_last == CIRCLEQ_END(head))     \
 514             (head)->cqh_last = (elm);                  \
 515         else                                           \
 516             (head)->cqh_first->field.cqe_prev = (elm); \
 517         (head)->cqh_first = (elm);                     \
 518     } while (0)
 519
 520 #define CIRCLEQ_INSERT_TAIL(head, elm, field)         \
 521     do {                                              \
 522         (elm)->field.cqe_next = CIRCLEQ_END(head);    \
 523         (elm)->field.cqe_prev = (head)->cqh_last;     \
 524         if ((head)->cqh_first == CIRCLEQ_END(head))   \
 525             (head)->cqh_first = (elm);                \
 526         else                                          \
 527             (head)->cqh_last->field.cqe_next = (elm); \
 528         (head)->cqh_last = (elm);                     \
 529     } while (0)
 530
 531 #define CIRCLEQ_REMOVE(head, elm, field)                                   \
 532     do {                                                                   \
 533         if ((elm)->field.cqe_next == CIRCLEQ_END(head))                    \
 534             (head)->cqh_last = (elm)->field.cqe_prev;                      \
 535         else                                                               \
 536             (elm)->field.cqe_next->field.cqe_prev = (elm)->field.cqe_prev; \
 537         if ((elm)->field.cqe_prev == CIRCLEQ_END(head))                    \
 538             (head)->cqh_first = (elm)->field.cqe_next;                     \
 539         else                                                               \
 540             (elm)->field.cqe_prev->field.cqe_next = (elm)->field.cqe_next; \
 541         _Q_INVALIDATE((elm)->field.cqe_prev);                              \
 542         _Q_INVALIDATE((elm)->field.cqe_next);                              \
 543     } while (0)
 544
 545 #define CIRCLEQ_REPLACE(head, elm, elm2, field)                                    \
 546     do {                                                                           \
 547         if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == CIRCLEQ_END(head)) \
 548             (head)->cqh_last = (elm2);                                             \
 549         else                                                                       \
 550             (elm2)->field.cqe_next->field.cqe_prev = (elm2);                       \
 551         if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == CIRCLEQ_END(head)) \
 552             (head)->cqh_first = (elm2);                                            \
 553         else                                                                       \
 554             (elm2)->field.cqe_prev->field.cqe_next = (elm2);                       \
 555         _Q_INVALIDATE((elm)->field.cqe_prev);                                      \
 556         _Q_INVALIDATE((elm)->field.cqe_next);                                      \
 557     } while (0)