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