share/man/man3/queue.3

   1 .\" Copyright (c) 1993
   2 .\"     The Regents of the University of California.  All rights reserved.
   3 .\"
   4 .\" Redistribution and use in source and binary forms, with or without
   5 .\" modification, are permitted provided that the following conditions
   6 .\" are met:
   7 .\" 1. Redistributions of source code must retain the above copyright
   8 .\"    notice, this list of conditions and the following disclaimer.
   9 .\" 2. Redistributions in binary form must reproduce the above copyright
  10 .\"    notice, this list of conditions and the following disclaimer in the
  11 .\"    documentation and/or other materials provided with the distribution.
  12 .\" 3. All advertising materials mentioning features or use of this software
  13 .\"    must display the following acknowledgement:
  14 .\"     This product includes software developed by the University of
  15 .\"     California, Berkeley and its contributors.
  16 .\" 4. 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.3     8.2 (Berkeley) 1/24/94
  33 .\" $FreeBSD: src/share/man/man3/queue.3,v 1.15.2.7 2001/12/18 10:09:02 ru Exp $
  34 .\" $DragonFly: src/share/man/man3/queue.3,v 1.2 2003/06/17 04:36:58 dillon Exp $
  35 .\"
  36 .Dd January 24, 1994
  37 .Dt QUEUE 3
  38 .Os
  39 .Sh NAME
  40 .Nm SLIST_EMPTY ,
  41 .Nm SLIST_ENTRY ,
  42 .Nm SLIST_FIRST ,
  43 .Nm SLIST_FOREACH ,
  44 .Nm SLIST_HEAD ,
  45 .Nm SLIST_HEAD_INITIALIZER ,
  46 .Nm SLIST_INIT ,
  47 .Nm SLIST_INSERT_AFTER ,
  48 .Nm SLIST_INSERT_HEAD ,
  49 .Nm SLIST_NEXT ,
  50 .Nm SLIST_REMOVE_HEAD ,
  51 .Nm SLIST_REMOVE ,
  52 .Nm STAILQ_EMPTY ,
  53 .Nm STAILQ_ENTRY ,
  54 .Nm STAILQ_FIRST ,
  55 .Nm STAILQ_FOREACH ,
  56 .Nm STAILQ_HEAD ,
  57 .Nm STAILQ_HEAD_INITIALIZER ,
  58 .Nm STAILQ_INIT ,
  59 .Nm STAILQ_INSERT_AFTER ,
  60 .Nm STAILQ_INSERT_HEAD ,
  61 .Nm STAILQ_INSERT_TAIL ,
  62 .Nm STAILQ_LAST ,
  63 .Nm STAILQ_NEXT ,
  64 .Nm STAILQ_REMOVE_HEAD ,
  65 .Nm STAILQ_REMOVE ,
  66 .Nm LIST_EMPTY ,
  67 .Nm LIST_ENTRY ,
  68 .Nm LIST_FIRST ,
  69 .Nm LIST_FOREACH ,
  70 .Nm LIST_HEAD ,
  71 .Nm LIST_HEAD_INITIALIZER ,
  72 .Nm LIST_INIT ,
  73 .Nm LIST_INSERT_AFTER ,
  74 .Nm LIST_INSERT_BEFORE ,
  75 .Nm LIST_INSERT_HEAD ,
  76 .Nm LIST_NEXT ,
  77 .Nm LIST_REMOVE ,
  78 .Nm TAILQ_EMPTY ,
  79 .Nm TAILQ_ENTRY ,
  80 .Nm TAILQ_FIRST ,
  81 .Nm TAILQ_FOREACH ,
  82 .Nm TAILQ_FOREACH_REVERSE ,
  83 .Nm TAILQ_HEAD ,
  84 .Nm TAILQ_HEAD_INITIALIZER ,
  85 .Nm TAILQ_INIT ,
  86 .Nm TAILQ_INSERT_AFTER ,
  87 .Nm TAILQ_INSERT_BEFORE ,
  88 .Nm TAILQ_INSERT_HEAD ,
  89 .Nm TAILQ_INSERT_TAIL ,
  90 .Nm TAILQ_LAST ,
  91 .Nm TAILQ_NEXT ,
  92 .Nm TAILQ_PREV ,
  93 .Nm TAILQ_REMOVE ,
  94 .Nm CIRCLEQ_EMPTY ,
  95 .Nm CIRCLEQ_ENTRY ,
  96 .Nm CIRCLEQ_FIRST ,
  97 .Nm CIRCLEQ_FOREACH ,
  98 .Nm CIRCLEQ_FOREACH_REVERSE ,
  99 .Nm CIRCLEQ_HEAD ,
 100 .Nm CIRCLEQ_HEAD_INITIALIZER ,
 101 .Nm CIRCLEQ_INIT ,
 102 .Nm CIRCLEQ_INSERT_AFTER ,
 103 .Nm CIRCLEQ_INSERT_BEFORE ,
 104 .Nm CIRCLEQ_INSERT_HEAD ,
 105 .Nm CIRCLEQ_INSERT_TAIL ,
 106 .Nm CIRCLE_LAST ,
 107 .Nm CIRCLE_NEXT ,
 108 .Nm CIRCLE_PREV ,
 109 .Nm CIRCLEQ_REMOVE
 110 .Nd implementations of singly-linked lists, singly-linked tail queues,
 111 lists, tail queues, and circular queues
 112 .Sh SYNOPSIS
 113 .In sys/queue.h
 114 .\"
 115 .Fn SLIST_EMPTY "SLIST_HEAD *head"
 116 .Fn SLIST_ENTRY "TYPE"
 117 .Fn SLIST_FIRST "SLIST_HEAD *head"
 118 .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
 119 .Fn SLIST_HEAD "HEADNAME" "TYPE"
 120 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
 121 .Fn SLIST_INIT "SLIST_HEAD *head"
 122 .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
 123 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
 124 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
 125 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
 126 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
 127 .\"
 128 .Fn STAILQ_EMPTY "STAILQ_HEAD *head"
 129 .Fn STAILQ_ENTRY "TYPE"
 130 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
 131 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
 132 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
 133 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
 134 .Fn STAILQ_INIT "STAILQ_HEAD *head"
 135 .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
 136 .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
 137 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
 138 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
 139 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
 140 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
 141 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
 142 .\"
 143 .Fn LIST_EMPTY "LIST_HEAD *head"
 144 .Fn LIST_ENTRY "TYPE"
 145 .Fn LIST_FIRST "LIST_HEAD *head"
 146 .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
 147 .Fn LIST_HEAD "HEADNAME" "TYPE"
 148 .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
 149 .Fn LIST_INIT "LIST_HEAD *head"
 150 .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
 151 .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
 152 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
 153 .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
 154 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
 155 .\"
 156 .Fn TAILQ_EMPTY "TAILQ_HEAD *head"
 157 .Fn TAILQ_ENTRY "TYPE"
 158 .Fn TAILQ_FIRST "TAILQ_HEAD *head"
 159 .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
 160 .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
 161 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
 162 .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
 163 .Fn TAILQ_INIT "TAILQ_HEAD *head"
 164 .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
 165 .Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
 166 .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
 167 .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
 168 .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
 169 .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
 170 .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
 171 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
 172 .\"
 173 .Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head"
 174 .Fn CIRCLEQ_ENTRY "TYPE"
 175 .Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head"
 176 .Fn CIRCLEQ_FOREACH "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
 177 .Fn CIRCLEQ_FOREACH_REVERSE "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
 178 .Fn CIRCLEQ_HEAD "HEADNAME" "TYPE"
 179 .Fn CIRCLEQ_HEAD_INITIALIZER "CIRCLEQ_HEAD head"
 180 .Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head"
 181 .Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
 182 .Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
 183 .Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
 184 .Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
 185 .Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head"
 186 .Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME"
 187 .Fn CIRCLE_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME"
 188 .Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
 189 .Sh DESCRIPTION
 190 These macros define and operate on five types of data structures:
 191 singly-linked lists, singly-linked tail queues, lists, tail queues,
 192 and circular queues.
 193 All five structures support the following functionality:
 194 .Bl -enum -compact -offset indent
 195 .It
 196 Insertion of a new entry at the head of the list.
 197 .It
 198 Insertion of a new entry after any element in the list.
 199 .It
 200 O(1) removal of an entry from the head of the list.
 201 .It
 202 O(n) removal of any entry in the list.
 203 .It
 204 Forward traversal through the list.
 205 .El
 206 .Pp
 207 Singly-linked lists are the simplest of the five data structures
 208 and support only the above functionality.
 209 Singly-linked lists are ideal for applications with large datasets
 210 and few or no removals,
 211 or for implementing a LIFO queue.
 212 .Pp
 213 Singly-linked tail queues add the following functionality:
 214 .Bl -enum -compact -offset indent
 215 .It
 216 Entries can be added at the end of a list.
 217 .El
 218 However:
 219 .Bl -enum -compact -offset indent
 220 .It
 221 All list insertions must specify the head of the list.
 222 .It
 223 Each head entry requires two pointers rather than one.
 224 .It
 225 Code size is about 15% greater and operations run about 20% slower
 226 than singly-linked lists.
 227 .El
 228 .Pp
 229 Singly-linked tailqs are ideal for applications with large datasets and
 230 few or no removals,
 231 or for implementing a FIFO queue.
 232 .Pp
 233 All doubly linked types of data structures (lists, tail queues, and circle
 234 queues) additionally allow:
 235 .Bl -enum -compact -offset indent
 236 .It
 237 Insertion of a new entry before any element in the list.
 238 .It
 239 O(1) removal of any entry in the list.
 240 .El
 241 However:
 242 .Bl -enum -compact -offset indent
 243 .It
 244 Each elements requires two pointers rather than one.
 245 .It
 246 Code size and execution time of operations (except for removal) is about
 247 twice that of the singly-linked data-structures.
 248 .El
 249 .Pp
 250 Linked lists are the simplest of the doubly linked data structures and support
 251 only the above functionality over singly-linked lists.
 252 .Pp
 253 Tail queues add the following functionality:
 254 .Bl -enum -compact -offset indent
 255 .It
 256 Entries can be added at the end of a list.
 257 .It
 258 They may be traversed backwards, from tail to head.
 259 .El
 260 However:
 261 .Bl -enum -compact -offset indent
 262 .It
 263 All list insertions and removals must specify the head of the list.
 264 .It
 265 Each head entry requires two pointers rather than one.
 266 .It
 267 Code size is about 15% greater and operations run about 20% slower
 268 than singly-linked lists.
 269 .El
 270 .Pp
 271 Circular queues add the following functionality:
 272 .Bl -enum -compact -offset indent
 273 .It
 274 Entries can be added at the end of a list.
 275 .It
 276 They may be traversed backwards, from tail to head.
 277 .El
 278 However:
 279 .Bl -enum -compact -offset indent
 280 .It
 281 All list insertions and removals must specify the head of the list.
 282 .It
 283 Each head entry requires two pointers rather than one.
 284 .It
 285 The termination condition for traversal is more complex.
 286 .It
 287 Code size is about 40% greater and operations run about 45% slower
 288 than lists.
 289 .El
 290 .Pp
 291 In the macro definitions,
 292 .Fa TYPE
 293 is the name of a user defined structure,
 294 that must contain a field of type
 295 .Li SLIST_ENTRY ,
 296 .Li STAILQ_ENTRY ,
 297 .Li LIST_ENTRY ,
 298 .Li TAILQ_ENTRY ,
 299 or
 300 .Li CIRCLEQ_ENTRY ,
 301 named
 302 .Fa NAME .
 303 The argument
 304 .Fa HEADNAME
 305 is the name of a user defined structure that must be declared
 306 using the macros
 307 .Li SLIST_HEAD ,
 308 .Li STAILQ_HEAD ,
 309 .Li LIST_HEAD ,
 310 .Li TAILQ_HEAD ,
 311 or
 312 .Li CIRCLEQ_HEAD .
 313 See the examples below for further explanation of how these
 314 macros are used.
 315 .Sh SINGLY-LINKED LISTS
 316 A singly-linked list is headed by a structure defined by the
 317 .Nm SLIST_HEAD
 318 macro.
 319 This structure contains a single pointer to the first element
 320 on the list.
 321 The elements are singly linked for minimum space and pointer manipulation
 322 overhead at the expense of O(n) removal for arbitrary elements.
 323 New elements can be added to the list after an existing element or
 324 at the head of the list.
 325 An
 326 .Fa SLIST_HEAD
 327 structure is declared as follows:
 328 .Bd -literal -offset indent
 329 SLIST_HEAD(HEADNAME, TYPE) head;
 330 .Ed
 331 .Pp
 332 where
 333 .Fa HEADNAME
 334 is the name of the structure to be defined, and
 335 .Fa TYPE
 336 is the type of the elements to be linked into the list.
 337 A pointer to the head of the list can later be declared as:
 338 .Bd -literal -offset indent
 339 struct HEADNAME *headp;
 340 .Ed
 341 .Pp
 342 (The names
 343 .Li head
 344 and
 345 .Li headp
 346 are user selectable.)
 347 .Pp
 348 The macro
 349 .Nm SLIST_HEAD_INITIALIZER
 350 evaluates to an initializer for the list
 351 .Fa head .
 352 .Pp
 353 The macro
 354 .Nm SLIST_EMPTY
 355 evaluates to true if there are no elements in the list.
 356 .Pp
 357 The macro
 358 .Nm SLIST_ENTRY
 359 declares a structure that connects the elements in
 360 the list.
 361 .Pp
 362 The macro
 363 .Nm SLIST_FIRST
 364 returns the first element in the list or NULL if the list is empty.
 365 .Pp
 366 The macro
 367 .Nm SLIST_FOREACH
 368 traverses the list referenced by
 369 .Fa head
 370 in the forward direction, assigning each element in
 371 turn to
 372 .Fa var .
 373 .Pp
 374 The macro
 375 .Nm SLIST_INIT
 376 initializes the list referenced by
 377 .Fa head .
 378 .Pp
 379 The macro
 380 .Nm SLIST_INSERT_HEAD
 381 inserts the new element
 382 .Fa elm
 383 at the head of the list.
 384 .Pp
 385 The macro
 386 .Nm SLIST_INSERT_AFTER
 387 inserts the new element
 388 .Fa elm
 389 after the element
 390 .Fa listelm .
 391 .Pp
 392 The macro
 393 .Nm SLIST_NEXT
 394 returns the next element in the list.
 395 .Pp
 396 The macro
 397 .Nm SLIST_REMOVE_HEAD
 398 removes the element
 399 .Fa elm
 400 from the head of the list.
 401 For optimum efficiency,
 402 elements being removed from the head of the list should explicitly use
 403 this macro instead of the generic
 404 .Fa SLIST_REMOVE
 405 macro.
 406 .Pp
 407 The macro
 408 .Nm SLIST_REMOVE
 409 removes the element
 410 .Fa elm
 411 from the list.
 412 .Sh SINGLY-LINKED LIST EXAMPLE
 413 .Bd -literal
 414 SLIST_HEAD(slisthead, entry) head =
 415     SLIST_HEAD_INITIALIZER(head);
 416 struct slisthead *headp;                /* Singly-linked List head. */
 417 struct entry {
 418         ...
 419         SLIST_ENTRY(entry) entries;     /* Singly-linked List. */
 420         ...
 421 } *n1, *n2, *n3, *np;
 422
 423 SLIST_INIT(&head);                      /* Initialize the list. */
 424
 425 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 426 SLIST_INSERT_HEAD(&head, n1, entries);
 427
 428 n2 = malloc(sizeof(struct entry));      /* Insert after. */
 429 SLIST_INSERT_AFTER(n1, n2, entries);
 430
 431 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
 432 free(n2);
 433
 434 n3 = SLIST_FIRST(&head);
 435 SLIST_REMOVE_HEAD(&head, entries);      /* Deletion from the head. */
 436 free(n3);
 437                                         /* Forward traversal. */
 438 SLIST_FOREACH(np, &head, entries)
 439         np-> ...
 440
 441 while (!SLIST_EMPTY(&head)) {           /* List Deletion. */
 442         n1 = SLIST_FIRST(&head);
 443         SLIST_REMOVE_HEAD(&head, entries);
 444         free(n1);
 445 }
 446 .Ed
 447 .Sh SINGLY-LINKED TAIL QUEUES
 448 A singly-linked tail queue is headed by a structure defined by the
 449 .Nm STAILQ_HEAD
 450 macro.
 451 This structure contains a pair of pointers,
 452 one to the first element in the tail queue and the other to
 453 the last element in the tail queue.
 454 The elements are singly linked for minimum space and pointer
 455 manipulation overhead at the expense of O(n) removal for arbitrary
 456 elements.
 457 New elements can be added to the tail queue after an existing element,
 458 at the head of the tail queue, or at the end of the tail queue.
 459 A
 460 .Fa STAILQ_HEAD
 461 structure is declared as follows:
 462 .Bd -literal -offset indent
 463 STAILQ_HEAD(HEADNAME, TYPE) head;
 464 .Ed
 465 .Pp
 466 where
 467 .Li HEADNAME
 468 is the name of the structure to be defined, and
 469 .Li TYPE
 470 is the type of the elements to be linked into the tail queue.
 471 A pointer to the head of the tail queue can later be declared as:
 472 .Bd -literal -offset indent
 473 struct HEADNAME *headp;
 474 .Ed
 475 .Pp
 476 (The names
 477 .Li head
 478 and
 479 .Li headp
 480 are user selectable.)
 481 .Pp
 482 The macro
 483 .Nm STAILQ_HEAD_INITIALIZER
 484 evaluates to an initializer for the tail queue
 485 .Fa head .
 486 .Pp
 487 The macro
 488 .Nm STAILQ_EMPTY
 489 evaluates to true if there are no items on the tail queue.
 490 .Pp
 491 The macro
 492 .Nm STAILQ_ENTRY
 493 declares a structure that connects the elements in
 494 the tail queue.
 495 .Pp
 496 The macro
 497 .Nm STAILQ_FIRST
 498 returns the first item on the tail queue or NULL if the tail queue
 499 is empty.
 500 .Pp
 501 The macro
 502 .Nm STAILQ_FOREACH
 503 traverses the tail queue referenced by
 504 .Fa head
 505 in the forward direction, assigning each element
 506 in turn to
 507 .Fa var .
 508 .Pp
 509 The macro
 510 .Nm STAILQ_INIT
 511 initializes the tail queue referenced by
 512 .Fa head .
 513 .Pp
 514 The macro
 515 .Nm STAILQ_INSERT_HEAD
 516 inserts the new element
 517 .Fa elm
 518 at the head of the tail queue.
 519 .Pp
 520 The macro
 521 .Nm STAILQ_INSERT_TAIL
 522 inserts the new element
 523 .Fa elm
 524 at the end of the tail queue.
 525 .Pp
 526 The macro
 527 .Nm STAILQ_INSERT_AFTER
 528 inserts the new element
 529 .Fa elm
 530 after the element
 531 .Fa listelm .
 532 .Pp
 533 The macro
 534 .Nm STAILQ_LAST
 535 returns the last item on the tail queue.
 536 If the tail queue is empty the return value is undefined.
 537 .Pp
 538 The macro
 539 .Nm STAILQ_NEXT
 540 returns the next item on the tail queue, or NULL this item is the last.
 541 .Pp
 542 The macro
 543 .Nm STAILQ_REMOVE_HEAD
 544 removes the element at the head of the tail queue.
 545 For optimum efficiency,
 546 elements being removed from the head of the tail queue should
 547 use this macro explicitly rather than the generic
 548 .Fa STAILQ_REMOVE
 549 macro.
 550 .Pp
 551 The macro
 552 .Nm STAILQ_REMOVE
 553 removes the element
 554 .Fa elm
 555 from the tail queue.
 556 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
 557 .Bd -literal
 558 STAILQ_HEAD(stailhead, entry) head =
 559     STAILQ_HEAD_INITIALIZER(head);
 560 struct stailhead *headp;                /* Singly-linked tail queue head. */
 561 struct entry {
 562         ...
 563         STAILQ_ENTRY(entry) entries;    /* Tail queue. */
 564         ...
 565 } *n1, *n2, *n3, *np;
 566
 567 STAILQ_INIT(&head);                     /* Initialize the queue. */
 568
 569 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 570 STAILQ_INSERT_HEAD(&head, n1, entries);
 571
 572 n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
 573 STAILQ_INSERT_TAIL(&head, n1, entries);
 574
 575 n2 = malloc(sizeof(struct entry));      /* Insert after. */
 576 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
 577                                         /* Deletion. */
 578 STAILQ_REMOVE(&head, n2, entry, entries);
 579 free(n2);
 580                                         /* Deletion from the head. */
 581 n3 = STAILQ_FIRST(&head);
 582 STAILQ_REMOVE_HEAD(&head, entries);
 583 free(n3);
 584                                         /* Forward traversal. */
 585 STAILQ_FOREACH(np, &head, entries)
 586         np-> ...
 587                                         /* TailQ Deletion. */
 588 while (!STAILQ_EMPTY(&head)) {
 589         n1 = STAILQ_FIRST(&head);
 590         STAILQ_REMOVE_HEAD(&head, entries);
 591         free(n1);
 592 }
 593                                         /* Faster TailQ Deletion. */
 594 n1 = STAILQ_FIRST(&head);
 595 while (n1 != NULL) {
 596         n2 = STAILQ_NEXT(n1, entries);
 597         free(n1);
 598         n1 = n2;
 599 }
 600 STAILQ_INIT(&head);
 601 .Ed
 602 .Sh LISTS
 603 A list is headed by a structure defined by the
 604 .Nm LIST_HEAD
 605 macro.
 606 This structure contains a single pointer to the first element
 607 on the list.
 608 The elements are doubly linked so that an arbitrary element can be
 609 removed without traversing the list.
 610 New elements can be added to the list after an existing element,
 611 before an existing element, or at the head of the list.
 612 A
 613 .Fa LIST_HEAD
 614 structure is declared as follows:
 615 .Bd -literal -offset indent
 616 LIST_HEAD(HEADNAME, TYPE) head;
 617 .Ed
 618 .Pp
 619 where
 620 .Fa HEADNAME
 621 is the name of the structure to be defined, and
 622 .Fa TYPE
 623 is the type of the elements to be linked into the list.
 624 A pointer to the head of the list can later be declared as:
 625 .Bd -literal -offset indent
 626 struct HEADNAME *headp;
 627 .Ed
 628 .Pp
 629 (The names
 630 .Li head
 631 and
 632 .Li headp
 633 are user selectable.)
 634 .Pp
 635 The macro
 636 .Nm LIST_HEAD_INITIALIZER
 637 evaluates to an initializer for the list
 638 .Fa head .
 639 .Pp
 640 The macro
 641 .Nm LIST_EMPTY
 642 evaluates to true if their are no elements in the list.
 643 .Pp
 644 The macro
 645 .Nm LIST_ENTRY
 646 declares a structure that connects the elements in
 647 the list.
 648 .Pp
 649 The macro
 650 .Nm LIST_FIRST
 651 returns the first element in the list or NULL if the list
 652 is empty.
 653 .Pp
 654 The macro
 655 .Nm LIST_FOREACH
 656 traverses the list referenced by
 657 .Fa head
 658 in the forward direction, assigning each element in turn to
 659 .Fa var .
 660 .Pp
 661 The macro
 662 .Nm LIST_INIT
 663 initializes the list referenced by
 664 .Fa head .
 665 .Pp
 666 The macro
 667 .Nm LIST_INSERT_HEAD
 668 inserts the new element
 669 .Fa elm
 670 at the head of the list.
 671 .Pp
 672 The macro
 673 .Nm LIST_INSERT_AFTER
 674 inserts the new element
 675 .Fa elm
 676 after the element
 677 .Fa listelm .
 678 .Pp
 679 The macro
 680 .Nm LIST_INSERT_BEFORE
 681 inserts the new element
 682 .Fa elm
 683 before the element
 684 .Fa listelm .
 685 .Pp
 686 The macro
 687 .Nm LIST_NEXT
 688 returns the next element in the list, or NULL if this is the last.
 689 .Pp
 690 The macro
 691 .Nm LIST_REMOVE
 692 removes the element
 693 .Fa elm
 694 from the list.
 695 .Sh LIST EXAMPLE
 696 .Bd -literal
 697 LIST_HEAD(listhead, entry) head =
 698     LIST_HEAD_INITIALIZER(head);
 699 struct listhead *headp;                 /* List head. */
 700 struct entry {
 701         ...
 702         LIST_ENTRY(entry) entries;      /* List. */
 703         ...
 704 } *n1, *n2, *n3, *np;
 705
 706 LIST_INIT(&head);                       /* Initialize the list. */
 707
 708 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 709 LIST_INSERT_HEAD(&head, n1, entries);
 710
 711 n2 = malloc(sizeof(struct entry));      /* Insert after. */
 712 LIST_INSERT_AFTER(n1, n2, entries);
 713
 714 n3 = malloc(sizeof(struct entry));      /* Insert before. */
 715 LIST_INSERT_BEFORE(n2, n3, entries);
 716
 717 LIST_REMOVE(n2, entries);               /* Deletion. */
 718 free(n2);
 719                                         /* Forward traversal. */
 720 LIST_FOREACH(np, &head, entries)
 721         np-> ...
 722
 723 while (!LIST_EMPTY(&head)) {            /* List Deletion. */
 724         n1 = LIST_FIRST(&head);
 725         LIST_REMOVE(n1, entries);
 726         free(n1);
 727 }
 728
 729 n1 = LIST_FIRST(&head);                 /* Faster List Deletion. */
 730 while (n1 != NULL) {
 731         n2 = LIST_NEXT(n1, entries);
 732         free(n1);
 733         n1 = n2;
 734 }
 735 LIST_INIT(&head);
 736 .Ed
 737 .Sh TAIL QUEUES
 738 A tail queue is headed by a structure defined by the
 739 .Nm TAILQ_HEAD
 740 macro.
 741 This structure contains a pair of pointers,
 742 one to the first element in the tail queue and the other to
 743 the last element in the tail queue.
 744 The elements are doubly linked so that an arbitrary element can be
 745 removed without traversing the tail queue.
 746 New elements can be added to the tail queue after an existing element,
 747 before an existing element, at the head of the tail queue,
 748 or at the end of the tail queue.
 749 A
 750 .Fa TAILQ_HEAD
 751 structure is declared as follows:
 752 .Bd -literal -offset indent
 753 TAILQ_HEAD(HEADNAME, TYPE) head;
 754 .Ed
 755 .Pp
 756 where
 757 .Li HEADNAME
 758 is the name of the structure to be defined, and
 759 .Li TYPE
 760 is the type of the elements to be linked into the tail queue.
 761 A pointer to the head of the tail queue can later be declared as:
 762 .Bd -literal -offset indent
 763 struct HEADNAME *headp;
 764 .Ed
 765 .Pp
 766 (The names
 767 .Li head
 768 and
 769 .Li headp
 770 are user selectable.)
 771 .Pp
 772 The macro
 773 .Nm TAILQ_HEAD_INITIALIZER
 774 evaluates to an initializer for the tail queue
 775 .Fa head .
 776 .Pp
 777 The macro
 778 .Nm TAILQ_EMPTY
 779 evaluates to true if there are no items on the tail queue.
 780 .Pp
 781 The macro
 782 .Nm TAILQ_ENTRY
 783 declares a structure that connects the elements in
 784 the tail queue.
 785 .Pp
 786 The macro
 787 .Nm TAILQ_FIRST
 788 returns the first item on the tail queue or NULL if the tail queue
 789 is empty.
 790 .Pp
 791 The macro
 792 .Nm TAILQ_FOREACH
 793 traverses the tail queue referenced by
 794 .Fa head
 795 in the forward direction, assigning each element in turn to
 796 .Fa var .
 797 .Pp
 798 The macro
 799 .Nm TAILQ_FOREACH_REVERSE
 800 traverses the tail queue referenced by
 801 .Fa head
 802 in the reverse direction, assigning each element in turn to
 803 .Fa var .
 804 .Pp
 805 The macro
 806 .Nm TAILQ_INIT
 807 initializes the tail queue referenced by
 808 .Fa head .
 809 .Pp
 810 The macro
 811 .Nm TAILQ_INSERT_HEAD
 812 inserts the new element
 813 .Fa elm
 814 at the head of the tail queue.
 815 .Pp
 816 The macro
 817 .Nm TAILQ_INSERT_TAIL
 818 inserts the new element
 819 .Fa elm
 820 at the end of the tail queue.
 821 .Pp
 822 The macro
 823 .Nm TAILQ_INSERT_AFTER
 824 inserts the new element
 825 .Fa elm
 826 after the element
 827 .Fa listelm .
 828 .Pp
 829 The macro
 830 .Nm TAILQ_INSERT_BEFORE
 831 inserts the new element
 832 .Fa elm
 833 before the element
 834 .Fa listelm .
 835 .Pp
 836 The macro
 837 .Nm TAILQ_LAST
 838 returns the last item on the tail queue.
 839 If the tail queue is empty the return value is undefined.
 840 .Pp
 841 The macro
 842 .Nm TAILQ_NEXT
 843 returns the next item on the tail queue, or NULL if this item is the last.
 844 .Pp
 845 The macro
 846 .Nm TAILQ_PREV
 847 returns the previous item on the tail queue, or NULL if this item
 848 is the first.
 849 .Pp
 850 The macro
 851 .Nm TAILQ_REMOVE
 852 removes the element
 853 .Fa elm
 854 from the tail queue.
 855 .Sh TAIL QUEUE EXAMPLE
 856 .Bd -literal
 857 TAILQ_HEAD(tailhead, entry) head =
 858     TAILQ_HEAD_INITIALIZER(head);
 859 struct tailhead *headp;                 /* Tail queue head. */
 860 struct entry {
 861         ...
 862         TAILQ_ENTRY(entry) entries;     /* Tail queue. */
 863         ...
 864 } *n1, *n2, *n3, *np;
 865
 866 TAILQ_INIT(&head);                      /* Initialize the queue. */
 867
 868 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 869 TAILQ_INSERT_HEAD(&head, n1, entries);
 870
 871 n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
 872 TAILQ_INSERT_TAIL(&head, n1, entries);
 873
 874 n2 = malloc(sizeof(struct entry));      /* Insert after. */
 875 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
 876
 877 n3 = malloc(sizeof(struct entry));      /* Insert before. */
 878 TAILQ_INSERT_BEFORE(n2, n3, entries);
 879
 880 TAILQ_REMOVE(&head, n2, entries);       /* Deletion. */
 881 free(n2);
 882                                         /* Forward traversal. */
 883 TAILQ_FOREACH(np, &head, entries)
 884         np-> ...
 885                                         /* Reverse traversal. */
 886 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
 887         np-> ...
 888                                         /* TailQ Deletion. */
 889 while (!TAILQ_EMPTY(&head)) {
 890         n1 = TAILQ_FIRST(&head);
 891         TAILQ_REMOVE(&head, n1, entries);
 892         free(n1);
 893 }
 894                                         /* Faster TailQ Deletion. */
 895 n1 = TAILQ_FIRST(&head);
 896 while (n1 != NULL) {
 897         n2 = TAILQ_NEXT(n1, entries);
 898         free(n1);
 899         n1 = n2;
 900 }
 901 TAILQ_INIT(&head);
 902 .Ed
 903 .Sh CIRCULAR QUEUES
 904 A circular queue is headed by a structure defined by the
 905 .Nm CIRCLEQ_HEAD
 906 macro.
 907 This structure contains a pair of pointers,
 908 one to the first element in the circular queue and the other to the
 909 last element in the circular queue.
 910 The elements are doubly linked so that an arbitrary element can be
 911 removed without traversing the queue.
 912 New elements can be added to the queue after an existing element,
 913 before an existing element, at the head of the queue, or at the end
 914 of the queue.
 915 A
 916 .Fa CIRCLEQ_HEAD
 917 structure is declared as follows:
 918 .Bd -literal -offset indent
 919 CIRCLEQ_HEAD(HEADNAME, TYPE) head;
 920 .Ed
 921 .Pp
 922 where
 923 .Li HEADNAME
 924 is the name of the structure to be defined, and
 925 .Li TYPE
 926 is the type of the elements to be linked into the circular queue.
 927 A pointer to the head of the circular queue can later be declared as:
 928 .Bd -literal -offset indent
 929 struct HEADNAME *headp;
 930 .Ed
 931 .Pp
 932 (The names
 933 .Li head
 934 and
 935 .Li headp
 936 are user selectable.)
 937 .Pp
 938 The macro
 939 .Nm CIRCLEQ_HEAD_INITIALIZER
 940 evaluates to an initializer for the circle queue
 941 .Fa head .
 942 .Pp
 943 The macro
 944 .Nm CIRCLEQ_EMPTY
 945 evaluates to true if there are no items on the circle queue.
 946 .Pp
 947 The macro
 948 .Nm CIRCLEQ_ENTRY
 949 declares a structure that connects the elements in
 950 the circular queue.
 951 .Pp
 952 The macro
 953 .Nm CIRCLEQ_FIRST
 954 returns the first item on the circle queue.
 955 .Pp
 956 The macro
 957 .Nm CICRLEQ_FOREACH
 958 traverses the circle queue referenced by
 959 .Fa head
 960 in the forward direction, assigning each element in turn to
 961 .Fa var .
 962 .Pp
 963 The macro
 964 .Nm CICRLEQ_FOREACH_REVERSE
 965 traverses the circle queue referenced by
 966 .Fa head
 967 in the reverse direction, assigning each element in turn to
 968 .Fa var .
 969 .Pp
 970 The macro
 971 .Nm CIRCLEQ_INIT
 972 initializes the circular queue referenced by
 973 .Fa head .
 974 .Pp
 975 The macro
 976 .Nm CIRCLEQ_INSERT_HEAD
 977 inserts the new element
 978 .Fa elm
 979 at the head of the circular queue.
 980 .Pp
 981 The macro
 982 .Nm CIRCLEQ_INSERT_TAIL
 983 inserts the new element
 984 .Fa elm
 985 at the end of the circular queue.
 986 .Pp
 987 The macro
 988 .Nm CIRCLEQ_INSERT_AFTER
 989 inserts the new element
 990 .Fa elm
 991 after the element
 992 .Fa listelm .
 993 .Pp
 994 The macro
 995 .Nm CIRCLEQ_INSERT_BEFORE
 996 inserts the new element
 997 .Fa elm
 998 before the element
 999 .Fa listelm .
1000 .Pp
1001 The macro
1002 .Nm CIRCLEQ_LAST
1003 returns the last item on the circle queue.
1004 .Pp
1005 The macro
1006 .Nm CIRCLEQ_NEXT
1007 returns the next item on the circle queue.
1008 .Pp
1009 The macro
1010 .Nm CIRCLEQ_PREV
1011 returns the previous item on the circle queue.
1012 .Pp
1013 The macro
1014 .Nm CIRCLEQ_REMOVE
1015 removes the element
1016 .Fa elm
1017 from the circular queue.
1018 .Sh CIRCULAR QUEUE EXAMPLE
1019 .Bd -literal
1020 CIRCLEQ_HEAD(circlehead, entry) head =
1021     CIRCLEQ_HEAD_INITIALIZER(head);
1022 struct circlehead *headp;               /* Circular queue head. */
1023 struct entry {
1024         ...
1025         CIRCLEQ_ENTRY(entry) entries;   /* Circular queue. */
1026         ...
1027 } *n1, *n2, *np;
1028
1029 CIRCLEQ_INIT(&head);                    /* Initialize the circular queue. */
1030
1031 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
1032 CIRCLEQ_INSERT_HEAD(&head, n1, entries);
1033
1034 n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
1035 CIRCLEQ_INSERT_TAIL(&head, n1, entries);
1036
1037 n2 = malloc(sizeof(struct entry));      /* Insert after. */
1038 CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
1039
1040 n2 = malloc(sizeof(struct entry));      /* Insert before. */
1041 CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
1042
1043 CIRCLEQ_REMOVE(&head, n1, entries);     /* Deletion. */
1044 free(n1);
1045                                         /* Forward traversal. */
1046 CIRCLEQ_FOREACH(np, &head, entries)
1047         np-> ...
1048                                         /* Reverse traversal. */
1049 CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
1050         np-> ...
1051                                         /* CircleQ Deletion. */
1052 while (CIRCLEQ_FIRST(&head) != (void *)&head) {
1053         n1 = CIRCLEQ_HEAD(&head);
1054         CIRCLEQ_REMOVE(&head, n1, entries);
1055         free(n1);
1056 }
1057                                         /* Faster CircleQ Deletion. */
1058 n1 = CIRCLEQ_FIRST(&head);
1059 while (n1 != (void *)&head) {
1060         n2 = CIRCLEQ_NEXT(n1, entries);
1061         free(n1);
1062         n1 = n2;
1063 }
1064 CIRCLEQ_INIT(&head);
1065 .Ed
1066 .Sh HISTORY
1067 The
1068 .Nm queue
1069 functions first appeared in
1070 .Bx 4.4 .