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