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