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