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 { \ 450 CIRCLEQ_END(&head) \ 451 , CIRCLEQ_END(&head) \ 452 } 453 454 #define CIRCLEQ_ENTRY(type) \ 455 struct { \ 456 struct type *cqe_next; /* next element */ \ 457 struct type *cqe_prev; /* previous element */ \ 458 } 459 460 /* 461 * Circular queue access methods 462 */ 463 #define CIRCLEQ_FIRST(head) ((head)->cqh_first) 464 #define CIRCLEQ_LAST(head) ((head)->cqh_last) 465 #define CIRCLEQ_END(head) ((void *)(head)) 466 #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next) 467 #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev) 468 #define CIRCLEQ_EMPTY(head) \ 469 (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head)) 470 471 #define CIRCLEQ_FOREACH(var, head, field) \ 472 for ((var) = CIRCLEQ_FIRST(head); \ 473 (var) != CIRCLEQ_END(head); \ 474 (var) = CIRCLEQ_NEXT(var, field)) 475 476 #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \ 477 for ((var) = CIRCLEQ_LAST(head); \ 478 (var) != CIRCLEQ_END(head); \ 479 (var) = CIRCLEQ_PREV(var, field)) 480 481 /* 482 * Circular queue functions. 483 */ 484 #define CIRCLEQ_INIT(head) \ 485 do { \ 486 (head)->cqh_first = CIRCLEQ_END(head); \ 487 (head)->cqh_last = CIRCLEQ_END(head); \ 488 } while (0) 489 490 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) \ 491 do { \ 492 (elm)->field.cqe_next = (listelm)->field.cqe_next; \ 493 (elm)->field.cqe_prev = (listelm); \ 494 if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \ 495 (head)->cqh_last = (elm); \ 496 else \ 497 (listelm)->field.cqe_next->field.cqe_prev = (elm); \ 498 (listelm)->field.cqe_next = (elm); \ 499 } while (0) 500 501 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) \ 502 do { \ 503 (elm)->field.cqe_next = (listelm); \ 504 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ 505 if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \ 506 (head)->cqh_first = (elm); \ 507 else \ 508 (listelm)->field.cqe_prev->field.cqe_next = (elm); \ 509 (listelm)->field.cqe_prev = (elm); \ 510 } while (0) 511 512 #define CIRCLEQ_INSERT_HEAD(head, elm, field) \ 513 do { \ 514 (elm)->field.cqe_next = (head)->cqh_first; \ 515 (elm)->field.cqe_prev = CIRCLEQ_END(head); \ 516 if ((head)->cqh_last == CIRCLEQ_END(head)) \ 517 (head)->cqh_last = (elm); \ 518 else \ 519 (head)->cqh_first->field.cqe_prev = (elm); \ 520 (head)->cqh_first = (elm); \ 521 } while (0) 522 523 #define CIRCLEQ_INSERT_TAIL(head, elm, field) \ 524 do { \ 525 (elm)->field.cqe_next = CIRCLEQ_END(head); \ 526 (elm)->field.cqe_prev = (head)->cqh_last; \ 527 if ((head)->cqh_first == CIRCLEQ_END(head)) \ 528 (head)->cqh_first = (elm); \ 529 else \ 530 (head)->cqh_last->field.cqe_next = (elm); \ 531 (head)->cqh_last = (elm); \ 532 } while (0) 533 534 #define CIRCLEQ_REMOVE(head, elm, field) \ 535 do { \ 536 if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \ 537 (head)->cqh_last = (elm)->field.cqe_prev; \ 538 else \ 539 (elm)->field.cqe_next->field.cqe_prev = (elm)->field.cqe_prev; \ 540 if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \ 541 (head)->cqh_first = (elm)->field.cqe_next; \ 542 else \ 543 (elm)->field.cqe_prev->field.cqe_next = (elm)->field.cqe_next; \ 544 _Q_INVALIDATE((elm)->field.cqe_prev); \ 545 _Q_INVALIDATE((elm)->field.cqe_next); \ 546 } while (0) 547 548 #define CIRCLEQ_REPLACE(head, elm, elm2, field) \ 549 do { \ 550 if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == CIRCLEQ_END(head)) \ 551 (head)->cqh_last = (elm2); \ 552 else \ 553 (elm2)->field.cqe_next->field.cqe_prev = (elm2); \ 554 if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == CIRCLEQ_END(head)) \ 555 (head)->cqh_first = (elm2); \ 556 else \ 557 (elm2)->field.cqe_prev->field.cqe_next = (elm2); \ 558 _Q_INVALIDATE((elm)->field.cqe_prev); \ 559 _Q_INVALIDATE((elm)->field.cqe_next); \ 560 } while (0) 561