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         SLIST_FIRST(head) = SLIST_END(head);                            \
 129 }
 130
 131 #define SLIST_INSERT_AFTER(slistelm, elm, field) do {                   \
 132         (elm)->field.sle_next = (slistelm)->field.sle_next;             \
 133         (slistelm)->field.sle_next = (elm);                             \
 134 } while (0)
 135
 136 #define SLIST_INSERT_HEAD(head, elm, field) do {                        \
 137         (elm)->field.sle_next = (head)->slh_first;                      \
 138         (head)->slh_first = (elm);                                      \
 139 } while (0)
 140
 141 #define SLIST_REMOVE_NEXT(head, elm, field) do {                        \
 142         (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next;  \
 143 } while (0)
 144
 145 #define SLIST_REMOVE_HEAD(head, field) do {                             \
 146         (head)->slh_first = (head)->slh_first->field.sle_next;          \
 147 } while (0)
 148
 149 #define SLIST_REMOVE(head, elm, type, field) do {                       \
 150         if ((head)->slh_first == (elm)) {                               \
 151                 SLIST_REMOVE_HEAD((head), field);                       \
 152         } else {                                                        \
 153                 struct type *curelm = (head)->slh_first;                \
 154                                                                         \
 155                 while (curelm->field.sle_next != (elm))                 \
 156                         curelm = curelm->field.sle_next;                \
 157                 curelm->field.sle_next =                                \
 158                     curelm->field.sle_next->field.sle_next;             \
 159                 _Q_INVALIDATE((elm)->field.sle_next);                   \
 160         }                                                               \
 161 } while (0)
 162
 163 /*
 164  * List definitions.
 165  */
 166 #define LIST_HEAD(name, type)                                           \
 167 struct name {                                                           \
 168         struct type *lh_first;  /* first element */                     \
 169 }
 170
 171 #define LIST_HEAD_INITIALIZER(head)                                     \
 172         { NULL }
 173
 174 #define LIST_ENTRY(type)                                                \
 175 struct {                                                                \
 176         struct type *le_next;   /* next element */                      \
 177         struct type **le_prev;  /* address of previous next element */  \
 178 }
 179
 180 /*
 181  * List access methods
 182  */
 183 #define LIST_FIRST(head)                ((head)->lh_first)
 184 #define LIST_END(head)                  NULL
 185 #define LIST_EMPTY(head)                (LIST_FIRST(head) == LIST_END(head))
 186 #define LIST_NEXT(elm, field)           ((elm)->field.le_next)
 187
 188 #define LIST_FOREACH(var, head, field)                                  \
 189         for((var) = LIST_FIRST(head);                                   \
 190             (var)!= LIST_END(head);                                     \
 191             (var) = LIST_NEXT(var, field))
 192
 193 /*
 194  * List functions.
 195  */
 196 #define LIST_INIT(head) do {                                            \
 197         LIST_FIRST(head) = LIST_END(head);                              \
 198 } while (0)
 199
 200 #define LIST_INSERT_AFTER(listelm, elm, field) do {                     \
 201         if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)  \
 202                 (listelm)->field.le_next->field.le_prev =               \
 203                     &(elm)->field.le_next;                              \
 204         (listelm)->field.le_next = (elm);                               \
 205         (elm)->field.le_prev = &(listelm)->field.le_next;               \
 206 } while (0)
 207
 208 #define LIST_INSERT_BEFORE(listelm, elm, field) do {                    \
 209         (elm)->field.le_prev = (listelm)->field.le_prev;                \
 210         (elm)->field.le_next = (listelm);                               \
 211         *(listelm)->field.le_prev = (elm);                              \
 212         (listelm)->field.le_prev = &(elm)->field.le_next;               \
 213 } while (0)
 214
 215 #define LIST_INSERT_HEAD(head, elm, field) do {                         \
 216         if (((elm)->field.le_next = (head)->lh_first) != NULL)          \
 217                 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
 218         (head)->lh_first = (elm);                                       \
 219         (elm)->field.le_prev = &(head)->lh_first;                       \
 220 } while (0)
 221
 222 #define LIST_REMOVE(elm, field) do {                                    \
 223         if ((elm)->field.le_next != NULL)                               \
 224                 (elm)->field.le_next->field.le_prev =                   \
 225                     (elm)->field.le_prev;                               \
 226         *(elm)->field.le_prev = (elm)->field.le_next;                   \
 227         _Q_INVALIDATE((elm)->field.le_prev);                            \
 228         _Q_INVALIDATE((elm)->field.le_next);                            \
 229 } while (0)
 230
 231 #define LIST_REPLACE(elm, elm2, field) do {                             \
 232         if (((elm2)->field.le_next = (elm)->field.le_next) != NULL)     \
 233                 (elm2)->field.le_next->field.le_prev =                  \
 234                     &(elm2)->field.le_next;                             \
 235         (elm2)->field.le_prev = (elm)->field.le_prev;                   \
 236         *(elm2)->field.le_prev = (elm2);                                \
 237         _Q_INVALIDATE((elm)->field.le_prev);                            \
 238         _Q_INVALIDATE((elm)->field.le_next);                            \
 239 } while (0)
 240
 241 /*
 242  * Simple queue definitions.
 243  */
 244 #define SIMPLEQ_HEAD(name, type)                                        \
 245 struct name {                                                           \
 246         struct type *sqh_first; /* first element */                     \
 247         struct type **sqh_last; /* addr of last next element */         \
 248 }
 249
 250 #define SIMPLEQ_HEAD_INITIALIZER(head)                                  \
 251         { NULL, &(head).sqh_first }
 252
 253 #define SIMPLEQ_ENTRY(type)                                             \
 254 struct {                                                                \
 255         struct type *sqe_next;  /* next element */                      \
 256 }
 257
 258 /*
 259  * Simple queue access methods.
 260  */
 261 #define SIMPLEQ_FIRST(head)         ((head)->sqh_first)
 262 #define SIMPLEQ_END(head)           NULL
 263 #define SIMPLEQ_EMPTY(head)         (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
 264 #define SIMPLEQ_NEXT(elm, field)    ((elm)->field.sqe_next)
 265
 266 #define SIMPLEQ_FOREACH(var, head, field)                               \
 267         for((var) = SIMPLEQ_FIRST(head);                                \
 268             (var) != SIMPLEQ_END(head);                                 \
 269             (var) = SIMPLEQ_NEXT(var, field))
 270
 271 /*
 272  * Simple queue functions.
 273  */
 274 #define SIMPLEQ_INIT(head) do {                                         \
 275         (head)->sqh_first = NULL;                                       \
 276         (head)->sqh_last = &(head)->sqh_first;                          \
 277 } while (0)
 278
 279 #define SIMPLEQ_INSERT_HEAD(head, elm, field) do {                      \
 280         if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)        \
 281                 (head)->sqh_last = &(elm)->field.sqe_next;              \
 282         (head)->sqh_first = (elm);                                      \
 283 } while (0)
 284
 285 #define SIMPLEQ_INSERT_TAIL(head, elm, field) do {                      \
 286         (elm)->field.sqe_next = NULL;                                   \
 287         *(head)->sqh_last = (elm);                                      \
 288         (head)->sqh_last = &(elm)->field.sqe_next;                      \
 289 } while (0)
 290
 291 #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {            \
 292         if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
 293                 (head)->sqh_last = &(elm)->field.sqe_next;              \
 294         (listelm)->field.sqe_next = (elm);                              \
 295 } while (0)
 296
 297 #define SIMPLEQ_REMOVE_HEAD(head, field) do {                   \
 298         if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
 299                 (head)->sqh_last = &(head)->sqh_first;                  \
 300 } while (0)
 301
 302 /*
 303  * Tail queue definitions.
 304  */
 305 #define TAILQ_HEAD(name, type)                                          \
 306 struct name {                                                           \
 307         struct type *tqh_first; /* first element */                     \
 308         struct type **tqh_last; /* addr of last next element */         \
 309 }
 310
 311 #define TAILQ_HEAD_INITIALIZER(head)                                    \
 312         { NULL, &(head).tqh_first }
 313
 314 #define TAILQ_ENTRY(type)                                               \
 315 struct {                                                                \
 316         struct type *tqe_next;  /* next element */                      \
 317         struct type **tqe_prev; /* address of previous next element */  \
 318 }
 319
 320 /*
 321  * tail queue access methods
 322  */
 323 #define TAILQ_FIRST(head)               ((head)->tqh_first)
 324 #define TAILQ_END(head)                 NULL
 325 #define TAILQ_NEXT(elm, field)          ((elm)->field.tqe_next)
 326 #define TAILQ_LAST(head, headname)                                      \
 327         (*(((struct headname *)((head)->tqh_last))->tqh_last))
 328 /* XXX */
 329 #define TAILQ_PREV(elm, headname, field)                                \
 330         (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
 331 #define TAILQ_EMPTY(head)                                               \
 332         (TAILQ_FIRST(head) == TAILQ_END(head))
 333
 334 #define TAILQ_FOREACH(var, head, field)                                 \
 335         for((var) = TAILQ_FIRST(head);                                  \
 336             (var) != TAILQ_END(head);                                   \
 337             (var) = TAILQ_NEXT(var, field))
 338
 339 #define TAILQ_FOREACH_REVERSE(var, head, headname, field)               \
 340         for((var) = TAILQ_LAST(head, headname);                         \
 341             (var) != TAILQ_END(head);                                   \
 342             (var) = TAILQ_PREV(var, headname, field))
 343
 344 /*
 345  * Tail queue functions.
 346  */
 347 #define TAILQ_INIT(head) do {                                           \
 348         (head)->tqh_first = NULL;                                       \
 349         (head)->tqh_last = &(head)->tqh_first;                          \
 350 } while (0)
 351
 352 #define TAILQ_INSERT_HEAD(head, elm, field) do {                        \
 353         if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)        \
 354                 (head)->tqh_first->field.tqe_prev =                     \
 355                     &(elm)->field.tqe_next;                             \
 356         else                                                            \
 357                 (head)->tqh_last = &(elm)->field.tqe_next;              \
 358         (head)->tqh_first = (elm);                                      \
 359         (elm)->field.tqe_prev = &(head)->tqh_first;                     \
 360 } while (0)
 361
 362 #define TAILQ_INSERT_TAIL(head, elm, field) do {                        \
 363         (elm)->field.tqe_next = NULL;                                   \
 364         (elm)->field.tqe_prev = (head)->tqh_last;                       \
 365         *(head)->tqh_last = (elm);                                      \
 366         (head)->tqh_last = &(elm)->field.tqe_next;                      \
 367 } while (0)
 368
 369 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {              \
 370         if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
 371                 (elm)->field.tqe_next->field.tqe_prev =                 \
 372                     &(elm)->field.tqe_next;                             \
 373         else                                                            \
 374                 (head)->tqh_last = &(elm)->field.tqe_next;              \
 375         (listelm)->field.tqe_next = (elm);                              \
 376         (elm)->field.tqe_prev = &(listelm)->field.tqe_next;             \
 377 } while (0)
 378
 379 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do {                   \
 380         (elm)->field.tqe_prev = (listelm)->field.tqe_prev;              \
 381         (elm)->field.tqe_next = (listelm);                              \
 382         *(listelm)->field.tqe_prev = (elm);                             \
 383         (listelm)->field.tqe_prev = &(elm)->field.tqe_next;             \
 384 } while (0)
 385
 386 #define TAILQ_REMOVE(head, elm, field) do {                             \
 387         if (((elm)->field.tqe_next) != NULL)                            \
 388                 (elm)->field.tqe_next->field.tqe_prev =                 \
 389                     (elm)->field.tqe_prev;                              \
 390         else                                                            \
 391                 (head)->tqh_last = (elm)->field.tqe_prev;               \
 392         *(elm)->field.tqe_prev = (elm)->field.tqe_next;                 \
 393         _Q_INVALIDATE((elm)->field.tqe_prev);                           \
 394         _Q_INVALIDATE((elm)->field.tqe_next);                           \
 395 } while (0)
 396
 397 #define TAILQ_REPLACE(head, elm, elm2, field) do {                      \
 398         if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL)   \
 399                 (elm2)->field.tqe_next->field.tqe_prev =                \
 400                     &(elm2)->field.tqe_next;                            \
 401         else                                                            \
 402                 (head)->tqh_last = &(elm2)->field.tqe_next;             \
 403         (elm2)->field.tqe_prev = (elm)->field.tqe_prev;                 \
 404         *(elm2)->field.tqe_prev = (elm2);                               \
 405         _Q_INVALIDATE((elm)->field.tqe_prev);                           \
 406         _Q_INVALIDATE((elm)->field.tqe_next);                           \
 407 } while (0)
 408
 409 /* Swaps two consecutive elements. 'second' *MUST* follow 'first' */
 410 #define TAILQ_SWAP(first, second, head, field) do {                     \
 411         *((first)->field.tqe_prev) = (second);                          \
 412         (second)->field.tqe_prev = (first)->field.tqe_prev;             \
 413         (first)->field.tqe_prev = &((second)->field.tqe_next);          \
 414         (first)->field.tqe_next = (second)->field.tqe_next;             \
 415         if ((second)->field.tqe_next)                                   \
 416                 (second)->field.tqe_next->field.tqe_prev = &((first)->field.tqe_next); \
 417         (second)->field.tqe_next = first;                               \
 418         if ((head)->tqh_last == &((second)->field.tqe_next))            \
 419                 (head)->tqh_last = &((first)->field.tqe_next);          \
 420 } while (0)
 421
 422 /*
 423  * Circular queue definitions.
 424  */
 425 #define CIRCLEQ_HEAD(name, type)                                        \
 426 struct name {                                                           \
 427         struct type *cqh_first;         /* first element */             \
 428         struct type *cqh_last;          /* last element */              \
 429 }
 430
 431 #define CIRCLEQ_HEAD_INITIALIZER(head)                                  \
 432         { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
 433
 434 #define CIRCLEQ_ENTRY(type)                                             \
 435 struct {                                                                \
 436         struct type *cqe_next;          /* next element */              \
 437         struct type *cqe_prev;          /* previous element */          \
 438 }
 439
 440 /*
 441  * Circular queue access methods
 442  */
 443 #define CIRCLEQ_FIRST(head)             ((head)->cqh_first)
 444 #define CIRCLEQ_LAST(head)              ((head)->cqh_last)
 445 #define CIRCLEQ_END(head)               ((void *)(head))
 446 #define CIRCLEQ_NEXT(elm, field)        ((elm)->field.cqe_next)
 447 #define CIRCLEQ_PREV(elm, field)        ((elm)->field.cqe_prev)
 448 #define CIRCLEQ_EMPTY(head)                                             \
 449         (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
 450
 451 #define CIRCLEQ_FOREACH(var, head, field)                               \
 452         for((var) = CIRCLEQ_FIRST(head);                                \
 453             (var) != CIRCLEQ_END(head);                                 \
 454             (var) = CIRCLEQ_NEXT(var, field))
 455
 456 #define CIRCLEQ_FOREACH_REVERSE(var, head, field)                       \
 457         for((var) = CIRCLEQ_LAST(head);                                 \
 458             (var) != CIRCLEQ_END(head);                                 \
 459             (var) = CIRCLEQ_PREV(var, field))
 460
 461 /*
 462  * Circular queue functions.
 463  */
 464 #define CIRCLEQ_INIT(head) do {                                         \
 465         (head)->cqh_first = CIRCLEQ_END(head);                          \
 466         (head)->cqh_last = CIRCLEQ_END(head);                           \
 467 } while (0)
 468
 469 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {            \
 470         (elm)->field.cqe_next = (listelm)->field.cqe_next;              \
 471         (elm)->field.cqe_prev = (listelm);                              \
 472         if ((listelm)->field.cqe_next == CIRCLEQ_END(head))             \
 473                 (head)->cqh_last = (elm);                               \
 474         else                                                            \
 475                 (listelm)->field.cqe_next->field.cqe_prev = (elm);      \
 476         (listelm)->field.cqe_next = (elm);                              \
 477 } while (0)
 478
 479 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {           \
 480         (elm)->field.cqe_next = (listelm);                              \
 481         (elm)->field.cqe_prev = (listelm)->field.cqe_prev;              \
 482         if ((listelm)->field.cqe_prev == CIRCLEQ_END(head))             \
 483                 (head)->cqh_first = (elm);                              \
 484         else                                                            \
 485                 (listelm)->field.cqe_prev->field.cqe_next = (elm);      \
 486         (listelm)->field.cqe_prev = (elm);                              \
 487 } while (0)
 488
 489 #define CIRCLEQ_INSERT_HEAD(head, elm, field) do {                      \
 490         (elm)->field.cqe_next = (head)->cqh_first;                      \
 491         (elm)->field.cqe_prev = CIRCLEQ_END(head);                      \
 492         if ((head)->cqh_last == CIRCLEQ_END(head))                      \
 493                 (head)->cqh_last = (elm);                               \
 494         else                                                            \
 495                 (head)->cqh_first->field.cqe_prev = (elm);              \
 496         (head)->cqh_first = (elm);                                      \
 497 } while (0)
 498
 499 #define CIRCLEQ_INSERT_TAIL(head, elm, field) do {                      \
 500         (elm)->field.cqe_next = CIRCLEQ_END(head);                      \
 501         (elm)->field.cqe_prev = (head)->cqh_last;                       \
 502         if ((head)->cqh_first == CIRCLEQ_END(head))                     \
 503                 (head)->cqh_first = (elm);                              \
 504         else                                                            \
 505                 (head)->cqh_last->field.cqe_next = (elm);               \
 506         (head)->cqh_last = (elm);                                       \
 507 } while (0)
 508
 509 #define CIRCLEQ_REMOVE(head, elm, field) do {                           \
 510         if ((elm)->field.cqe_next == CIRCLEQ_END(head))                 \
 511                 (head)->cqh_last = (elm)->field.cqe_prev;               \
 512         else                                                            \
 513                 (elm)->field.cqe_next->field.cqe_prev =                 \
 514                     (elm)->field.cqe_prev;                              \
 515         if ((elm)->field.cqe_prev == CIRCLEQ_END(head))                 \
 516                 (head)->cqh_first = (elm)->field.cqe_next;              \
 517         else                                                            \
 518                 (elm)->field.cqe_prev->field.cqe_next =                 \
 519                     (elm)->field.cqe_next;                              \
 520         _Q_INVALIDATE((elm)->field.cqe_prev);                           \
 521         _Q_INVALIDATE((elm)->field.cqe_next);                           \
 522 } while (0)
 523
 524 #define CIRCLEQ_REPLACE(head, elm, elm2, field) do {                    \
 525         if (((elm2)->field.cqe_next = (elm)->field.cqe_next) ==         \
 526             CIRCLEQ_END(head))                                          \
 527                 (head)->cqh_last = (elm2);                              \
 528         else                                                            \
 529                 (elm2)->field.cqe_next->field.cqe_prev = (elm2);        \
 530         if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) ==         \
 531             CIRCLEQ_END(head))                                          \
 532                 (head)->cqh_first = (elm2);                             \
 533         else                                                            \
 534                 (elm2)->field.cqe_prev->field.cqe_next = (elm2);        \
 535         _Q_INVALIDATE((elm)->field.cqe_prev);                           \
 536         _Q_INVALIDATE((elm)->field.cqe_next);                           \
 537 } while (0)