1/* 2 * Copyright (c) 1991, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. All advertising materials mentioning features or use of this software 14 * must display the following acknowledgement: 15 * This product includes software developed by the University of 16 * California, Berkeley and its contributors. 17 * 4. Neither the name of the University nor the names of its contributors 18 * may be used to endorse or promote products derived from this software 19 * without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 * 33 * @(#)queue.h 8.5 (Berkeley) 8/20/94 34 * $FreeBSD: src/sys/sys/queue.h,v 1.54 2002/08/05 05:18:43 alfred Exp $ 35 */ 36 37#ifndef _DB_QUEUE_H_ 38#define _DB_QUEUE_H_ 39 40#if defined(__cplusplus) 41extern "C" { 42#endif 43 44/* 45 * This file defines four types of data structures: singly-linked lists, 46 * singly-linked tail queues, lists and tail queues. 47 * 48 * A singly-linked list is headed by a single forward pointer. The elements 49 * are singly linked for minimum space and pointer manipulation overhead at 50 * the expense of O(n) removal for arbitrary elements. New elements can be 51 * added to the list after an existing element or at the head of the list. 52 * Elements being removed from the head of the list should use the explicit 53 * macro for this purpose for optimum efficiency. A singly-linked list may 54 * only be traversed in the forward direction. Singly-linked lists are ideal 55 * for applications with large datasets and few or no removals or for 56 * implementing a LIFO queue. 57 * 58 * A singly-linked tail queue is headed by a pair of pointers, one to the 59 * head of the list and the other to the tail of the list. The elements are 60 * singly linked for minimum space and pointer manipulation overhead at the 61 * expense of O(n) removal for arbitrary elements. New elements can be added 62 * to the list after an existing element, at the head of the list, or at the 63 * end of the list. Elements being removed from the head of the tail queue 64 * should use the explicit macro for this purpose for optimum efficiency. 65 * A singly-linked tail queue may only be traversed in the forward direction. 66 * Singly-linked tail queues are ideal for applications with large datasets 67 * and few or no removals or for implementing a FIFO queue. 68 * 69 * A list is headed by a single forward pointer (or an array of forward 70 * pointers for a hash table header). The elements are doubly linked 71 * so that an arbitrary element can be removed without a need to 72 * traverse the list. New elements can be added to the list before 73 * or after an existing element or at the head of the list. A list 74 * may only be traversed in the forward direction. 75 * 76 * A tail queue is headed by a pair of pointers, one to the head of the 77 * list and the other to the tail of the list. The elements are doubly 78 * linked so that an arbitrary element can be removed without a need to 79 * traverse the list. New elements can be added to the list before or 80 * after an existing element, at the head of the list, or at the end of 81 * the list. A tail queue may be traversed in either direction. 82 * 83 * For details on the use of these macros, see the queue(3) manual page. 84 * 85 * 86 * SLIST LIST STAILQ TAILQ 87 * _HEAD + + + + 88 * _HEAD_INITIALIZER + + + + 89 * _ENTRY + + + + 90 * _INIT + + + + 91 * _EMPTY + + + + 92 * _FIRST + + + + 93 * _NEXT + + + + 94 * _PREV - - - + 95 * _LAST - - + + 96 * _FOREACH + + + + 97 * _FOREACH_REVERSE - - - + 98 * _INSERT_HEAD + + + + 99 * _INSERT_BEFORE - + - + 100 * _INSERT_AFTER + + + + 101 * _INSERT_TAIL - - + + 102 * _CONCAT - - + + 103 * _REMOVE_HEAD + - + - 104 * _REMOVE + + + + 105 * 106 */ 107 108/* 109 * XXX 110 * We #undef all of the macros because there are incompatible versions of this 111 * file and these macros on various systems. What makes the problem worse is 112 * they are included and/or defined by system include files which we may have 113 * already loaded into Berkeley DB before getting here. For example, FreeBSD's 114 * <rpc/rpc.h> includes its system <sys/queue.h>, and VxWorks UnixLib.h defines 115 * several of the LIST_XXX macros. Visual C.NET 7.0 also defines some of these 116 * same macros in Vc7\PlatformSDK\Include\WinNT.h. Make sure we use ours. 117 */ 118#undef LIST_EMPTY 119#undef LIST_ENTRY 120#undef LIST_FIRST 121#undef LIST_FOREACH 122#undef LIST_HEAD 123#undef LIST_HEAD_INITIALIZER 124#undef LIST_INIT 125#undef LIST_INSERT_AFTER 126#undef LIST_INSERT_BEFORE 127#undef LIST_INSERT_HEAD 128#undef LIST_NEXT 129#undef LIST_REMOVE 130#undef QMD_TRACE_ELEM 131#undef QMD_TRACE_HEAD 132#undef QUEUE_MACRO_DEBUG 133#undef SLIST_EMPTY 134#undef SLIST_ENTRY 135#undef SLIST_FIRST 136#undef SLIST_FOREACH 137#undef SLIST_FOREACH_PREVPTR 138#undef SLIST_HEAD 139#undef SLIST_HEAD_INITIALIZER 140#undef SLIST_INIT 141#undef SLIST_INSERT_AFTER 142#undef SLIST_INSERT_HEAD 143#undef SLIST_NEXT 144#undef SLIST_REMOVE 145#undef SLIST_REMOVE_HEAD 146#undef STAILQ_CONCAT 147#undef STAILQ_EMPTY 148#undef STAILQ_ENTRY 149#undef STAILQ_FIRST 150#undef STAILQ_FOREACH 151#undef STAILQ_HEAD 152#undef STAILQ_HEAD_INITIALIZER 153#undef STAILQ_INIT 154#undef STAILQ_INSERT_AFTER 155#undef STAILQ_INSERT_HEAD 156#undef STAILQ_INSERT_TAIL 157#undef STAILQ_LAST 158#undef STAILQ_NEXT 159#undef STAILQ_REMOVE 160#undef STAILQ_REMOVE_HEAD 161#undef STAILQ_REMOVE_HEAD_UNTIL 162#undef TAILQ_CONCAT 163#undef TAILQ_EMPTY 164#undef TAILQ_ENTRY 165#undef TAILQ_FIRST 166#undef TAILQ_FOREACH 167#undef TAILQ_FOREACH_REVERSE 168#undef TAILQ_HEAD 169#undef TAILQ_HEAD_INITIALIZER 170#undef TAILQ_INIT 171#undef TAILQ_INSERT_AFTER 172#undef TAILQ_INSERT_BEFORE 173#undef TAILQ_INSERT_HEAD 174#undef TAILQ_INSERT_TAIL 175#undef TAILQ_LAST 176#undef TAILQ_NEXT 177#undef TAILQ_PREV 178#undef TAILQ_REMOVE 179#undef TRACEBUF 180#undef TRASHIT 181 182#define QUEUE_MACRO_DEBUG 0 183#if QUEUE_MACRO_DEBUG 184/* Store the last 2 places the queue element or head was altered */ 185struct qm_trace { 186 char * lastfile; 187 int lastline; 188 char * prevfile; 189 int prevline; 190}; 191 192#define TRACEBUF struct qm_trace trace; 193#define TRASHIT(x) do {(x) = (void *)-1;} while (0) 194 195#define QMD_TRACE_HEAD(head) do { \ 196 (head)->trace.prevline = (head)->trace.lastline; \ 197 (head)->trace.prevfile = (head)->trace.lastfile; \ 198 (head)->trace.lastline = __LINE__; \ 199 (head)->trace.lastfile = __FILE__; \ 200} while (0) 201 202#define QMD_TRACE_ELEM(elem) do { \ 203 (elem)->trace.prevline = (elem)->trace.lastline; \ 204 (elem)->trace.prevfile = (elem)->trace.lastfile; \ 205 (elem)->trace.lastline = __LINE__; \ 206 (elem)->trace.lastfile = __FILE__; \ 207} while (0) 208 209#else 210#define QMD_TRACE_ELEM(elem) 211#define QMD_TRACE_HEAD(head) 212#define TRACEBUF 213#define TRASHIT(x) 214#endif /* QUEUE_MACRO_DEBUG */ 215 216/* 217 * Singly-linked List declarations. 218 */ 219#define SLIST_HEAD(name, type) \ 220struct name { \ 221 struct type *slh_first; /* first element */ \ 222} 223 224#define SLIST_HEAD_INITIALIZER(head) \ 225 { NULL } 226 227#define SLIST_ENTRY(type) \ 228struct { \ 229 struct type *sle_next; /* next element */ \ 230} 231 232/* 233 * Singly-linked List functions. 234 */ 235#define SLIST_EMPTY(head) ((head)->slh_first == NULL) 236 237#define SLIST_FIRST(head) ((head)->slh_first) 238 239#define SLIST_FOREACH(var, head, field) \ 240 for ((var) = SLIST_FIRST((head)); \ 241 (var); \ 242 (var) = SLIST_NEXT((var), field)) 243 244#define SLIST_FOREACH_PREVPTR(var, varp, head, field) \ 245 for ((varp) = &SLIST_FIRST((head)); \ 246 ((var) = *(varp)) != NULL; \ 247 (varp) = &SLIST_NEXT((var), field)) 248 249#define SLIST_INIT(head) do { \ 250 SLIST_FIRST((head)) = NULL; \ 251} while (0) 252 253#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 254 SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ 255 SLIST_NEXT((slistelm), field) = (elm); \ 256} while (0) 257 258#define SLIST_INSERT_HEAD(head, elm, field) do { \ 259 SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ 260 SLIST_FIRST((head)) = (elm); \ 261} while (0) 262 263#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 264 265#define SLIST_REMOVE(head, elm, type, field) do { \ 266 if (SLIST_FIRST((head)) == (elm)) { \ 267 SLIST_REMOVE_HEAD((head), field); \ 268 } \ 269 else { \ 270 struct type *curelm = SLIST_FIRST((head)); \ 271 while (SLIST_NEXT(curelm, field) != (elm)) \ 272 curelm = SLIST_NEXT(curelm, field); \ 273 SLIST_NEXT(curelm, field) = \ 274 SLIST_NEXT(SLIST_NEXT(curelm, field), field); \ 275 } \ 276} while (0) 277 278#define SLIST_REMOVE_HEAD(head, field) do { \ 279 SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ 280} while (0) 281 282/* 283 * Singly-linked Tail queue declarations. 284 */ 285#define STAILQ_HEAD(name, type) \ 286struct name { \ 287 struct type *stqh_first;/* first element */ \ 288 struct type **stqh_last;/* addr of last next element */ \ 289} 290 291#define STAILQ_HEAD_INITIALIZER(head) \ 292 { NULL, &(head).stqh_first } 293 294#define STAILQ_ENTRY(type) \ 295struct { \ 296 struct type *stqe_next; /* next element */ \ 297} 298 299/* 300 * Singly-linked Tail queue functions. 301 */ 302#define STAILQ_CONCAT(head1, head2) do { \ 303 if (!STAILQ_EMPTY((head2))) { \ 304 *(head1)->stqh_last = (head2)->stqh_first; \ 305 (head1)->stqh_last = (head2)->stqh_last; \ 306 STAILQ_INIT((head2)); \ 307 } \ 308} while (0) 309 310#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 311 312#define STAILQ_FIRST(head) ((head)->stqh_first) 313 314#define STAILQ_FOREACH(var, head, field) \ 315 for ((var) = STAILQ_FIRST((head)); \ 316 (var); \ 317 (var) = STAILQ_NEXT((var), field)) 318 319#define STAILQ_INIT(head) do { \ 320 STAILQ_FIRST((head)) = NULL; \ 321 (head)->stqh_last = &STAILQ_FIRST((head)); \ 322} while (0) 323 324#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 325 if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ 326 (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 327 STAILQ_NEXT((tqelm), field) = (elm); \ 328} while (0) 329 330#define STAILQ_INSERT_HEAD(head, elm, field) do { \ 331 if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ 332 (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 333 STAILQ_FIRST((head)) = (elm); \ 334} while (0) 335 336#define STAILQ_INSERT_TAIL(head, elm, field) do { \ 337 STAILQ_NEXT((elm), field) = NULL; \ 338 *(head)->stqh_last = (elm); \ 339 (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 340} while (0) 341 342#define STAILQ_LAST(head, type, field) \ 343 (STAILQ_EMPTY((head)) ? \ 344 NULL : \ 345 ((struct type *) \ 346 ((char *)((head)->stqh_last) - __offsetof(struct type, field)))) 347 348#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 349 350#define STAILQ_REMOVE(head, elm, type, field) do { \ 351 if (STAILQ_FIRST((head)) == (elm)) { \ 352 STAILQ_REMOVE_HEAD((head), field); \ 353 } \ 354 else { \ 355 struct type *curelm = STAILQ_FIRST((head)); \ 356 while (STAILQ_NEXT(curelm, field) != (elm)) \ 357 curelm = STAILQ_NEXT(curelm, field); \ 358 if ((STAILQ_NEXT(curelm, field) = \ 359 STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\ 360 (head)->stqh_last = &STAILQ_NEXT((curelm), field);\ 361 } \ 362} while (0) 363 364#define STAILQ_REMOVE_HEAD(head, field) do { \ 365 if ((STAILQ_FIRST((head)) = \ 366 STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ 367 (head)->stqh_last = &STAILQ_FIRST((head)); \ 368} while (0) 369 370#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \ 371 if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \ 372 (head)->stqh_last = &STAILQ_FIRST((head)); \ 373} while (0) 374 375/* 376 * List declarations. 377 */ 378#define LIST_HEAD(name, type) \ 379struct name { \ 380 struct type *lh_first; /* first element */ \ 381} 382 383#define LIST_HEAD_INITIALIZER(head) \ 384 { NULL } 385 386#define LIST_ENTRY(type) \ 387struct { \ 388 struct type *le_next; /* next element */ \ 389 struct type **le_prev; /* address of previous next element */ \ 390} 391 392/* 393 * List functions. 394 */ 395 396#define LIST_EMPTY(head) ((head)->lh_first == NULL) 397 398#define LIST_FIRST(head) ((head)->lh_first) 399 400#define LIST_FOREACH(var, head, field) \ 401 for ((var) = LIST_FIRST((head)); \ 402 (var); \ 403 (var) = LIST_NEXT((var), field)) 404 405#define LIST_INIT(head) do { \ 406 LIST_FIRST((head)) = NULL; \ 407} while (0) 408 409#define LIST_INSERT_AFTER(listelm, elm, field) do { \ 410 if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 411 LIST_NEXT((listelm), field)->field.le_prev = \ 412 &LIST_NEXT((elm), field); \ 413 LIST_NEXT((listelm), field) = (elm); \ 414 (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 415} while (0) 416 417#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 418 (elm)->field.le_prev = (listelm)->field.le_prev; \ 419 LIST_NEXT((elm), field) = (listelm); \ 420 *(listelm)->field.le_prev = (elm); \ 421 (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 422} while (0) 423 424#define LIST_INSERT_HEAD(head, elm, field) do { \ 425 if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 426 LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 427 LIST_FIRST((head)) = (elm); \ 428 (elm)->field.le_prev = &LIST_FIRST((head)); \ 429} while (0) 430 431#define LIST_NEXT(elm, field) ((elm)->field.le_next) 432 433#define LIST_REMOVE(elm, field) do { \ 434 if (LIST_NEXT((elm), field) != NULL) \ 435 LIST_NEXT((elm), field)->field.le_prev = \ 436 (elm)->field.le_prev; \ 437 *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 438} while (0) 439 440/* 441 * Tail queue declarations. 442 */ 443#define TAILQ_HEAD(name, type) \ 444struct name { \ 445 struct type *tqh_first; /* first element */ \ 446 struct type **tqh_last; /* addr of last next element */ \ 447 TRACEBUF \ 448} 449 450#define TAILQ_HEAD_INITIALIZER(head) \ 451 { NULL, &(head).tqh_first } 452 453#define TAILQ_ENTRY(type) \ 454struct { \ 455 struct type *tqe_next; /* next element */ \ 456 struct type **tqe_prev; /* address of previous next element */ \ 457 TRACEBUF \ 458} 459 460/* 461 * Tail queue functions. 462 */ 463#define TAILQ_CONCAT(head1, head2, field) do { \ 464 if (!TAILQ_EMPTY(head2)) { \ 465 *(head1)->tqh_last = (head2)->tqh_first; \ 466 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ 467 (head1)->tqh_last = (head2)->tqh_last; \ 468 TAILQ_INIT((head2)); \ 469 QMD_TRACE_HEAD(head); \ 470 QMD_TRACE_HEAD(head2); \ 471 } \ 472} while (0) 473 474#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 475 476#define TAILQ_FIRST(head) ((head)->tqh_first) 477 478#define TAILQ_FOREACH(var, head, field) \ 479 for ((var) = TAILQ_FIRST((head)); \ 480 (var); \ 481 (var) = TAILQ_NEXT((var), field)) 482 483#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 484 for ((var) = TAILQ_LAST((head), headname); \ 485 (var); \ 486 (var) = TAILQ_PREV((var), headname, field)) 487 488#define TAILQ_INIT(head) do { \ 489 TAILQ_FIRST((head)) = NULL; \ 490 (head)->tqh_last = &TAILQ_FIRST((head)); \ 491 QMD_TRACE_HEAD(head); \ 492} while (0) 493 494#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 495 if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ 496 TAILQ_NEXT((elm), field)->field.tqe_prev = \ 497 &TAILQ_NEXT((elm), field); \ 498 else { \ 499 (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 500 QMD_TRACE_HEAD(head); \ 501 } \ 502 TAILQ_NEXT((listelm), field) = (elm); \ 503 (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ 504 QMD_TRACE_ELEM(&(elm)->field); \ 505 QMD_TRACE_ELEM(&listelm->field); \ 506} while (0) 507 508#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 509 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 510 TAILQ_NEXT((elm), field) = (listelm); \ 511 *(listelm)->field.tqe_prev = (elm); \ 512 (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ 513 QMD_TRACE_ELEM(&(elm)->field); \ 514 QMD_TRACE_ELEM(&listelm->field); \ 515} while (0) 516 517#define TAILQ_INSERT_HEAD(head, elm, field) do { \ 518 if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ 519 TAILQ_FIRST((head))->field.tqe_prev = \ 520 &TAILQ_NEXT((elm), field); \ 521 else \ 522 (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 523 TAILQ_FIRST((head)) = (elm); \ 524 (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ 525 QMD_TRACE_HEAD(head); \ 526 QMD_TRACE_ELEM(&(elm)->field); \ 527} while (0) 528 529#define TAILQ_INSERT_TAIL(head, elm, field) do { \ 530 TAILQ_NEXT((elm), field) = NULL; \ 531 (elm)->field.tqe_prev = (head)->tqh_last; \ 532 *(head)->tqh_last = (elm); \ 533 (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 534 QMD_TRACE_HEAD(head); \ 535 QMD_TRACE_ELEM(&(elm)->field); \ 536} while (0) 537 538#define TAILQ_LAST(head, headname) \ 539 (*(((struct headname *)((head)->tqh_last))->tqh_last)) 540 541#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 542 543#define TAILQ_PREV(elm, headname, field) \ 544 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 545 546#define TAILQ_REMOVE(head, elm, field) do { \ 547 if ((TAILQ_NEXT((elm), field)) != NULL) \ 548 TAILQ_NEXT((elm), field)->field.tqe_prev = \ 549 (elm)->field.tqe_prev; \ 550 else { \ 551 (head)->tqh_last = (elm)->field.tqe_prev; \ 552 QMD_TRACE_HEAD(head); \ 553 } \ 554 *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ 555 TRASHIT((elm)->field.tqe_next); \ 556 TRASHIT((elm)->field.tqe_prev); \ 557 QMD_TRACE_ELEM(&(elm)->field); \ 558} while (0) 559 560#if defined(__cplusplus) 561} 562#endif 563#endif /* !_DB_QUEUE_H_ */ 564