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