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.
 495 Unlike
 496 .Fa SLIST_REMOVE ,
 497 this macro does not traverse the entire list.
 498 .Pp
 499 The macro
 500 .Nm SLIST_REMOVE_HEAD
 501 removes the element
 502 .Fa elm
 503 from the head of the list.
 504 For optimum efficiency,
 505 elements being removed from the head of the list should explicitly use
 506 this macro instead of the generic
 507 .Fa SLIST_REMOVE
 508 macro.
 509 .Pp
 510 The macro
 511 .Nm SLIST_REMOVE
 512 removes the element
 513 .Fa elm
 514 from the list.
 515 .Pp
 516 The macro
 517 .Nm SLIST_SWAP
 518 swaps the contents of
 519 .Fa head1
 520 and
 521 .Fa head2 .
 522 .Sh SINGLY-LINKED LIST EXAMPLE
 523 .Bd -literal
 524 SLIST_HEAD(slisthead, entry) head =
 525     SLIST_HEAD_INITIALIZER(head);
 526 struct slisthead *headp;                /* Singly-linked List head. */
 527 struct entry {
 528         ...
 529         SLIST_ENTRY(entry) entries;     /* Singly-linked List. */
 530         ...
 531 } *n1, *n2, *n3, *np;
 532
 533 SLIST_INIT(&head);                      /* Initialize the list. */
 534
 535 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 536 SLIST_INSERT_HEAD(&head, n1, entries);
 537
 538 n2 = malloc(sizeof(struct entry));      /* Insert after. */
 539 SLIST_INSERT_AFTER(n1, n2, entries);
 540
 541 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
 542 free(n2);
 543
 544 n3 = SLIST_FIRST(&head);
 545 SLIST_REMOVE_HEAD(&head, entries);      /* Deletion from the head. */
 546 free(n3);
 547                                         /* Forward traversal. */
 548 SLIST_FOREACH(np, &head, entries)
 549         np-> ...
 550                                         /* Safe forward traversal. */
 551 SLIST_FOREACH_SAFE(np, &head, entries, np_temp) {
 552         np->do_stuff();
 553         ...
 554         SLIST_REMOVE(&head, np, entry, entries);
 555         free(np);
 556 }
 557
 558 while (!SLIST_EMPTY(&head)) {           /* List Deletion. */
 559         n1 = SLIST_FIRST(&head);
 560         SLIST_REMOVE_HEAD(&head, entries);
 561         free(n1);
 562 }
 563 .Ed
 564 .Sh SINGLY-LINKED TAIL QUEUES
 565 A singly-linked tail queue is headed by a structure defined by the
 566 .Nm STAILQ_HEAD
 567 macro.
 568 This structure contains a pair of pointers,
 569 one to the first element in the tail queue and the other to
 570 the last element in the tail queue.
 571 The elements are singly linked for minimum space and pointer
 572 manipulation overhead at the expense of O(n) removal for arbitrary
 573 elements.
 574 New elements can be added to the tail queue after an existing element,
 575 at the head of the tail queue, or at the end of the tail queue.
 576 A
 577 .Fa STAILQ_HEAD
 578 structure is declared as follows:
 579 .Bd -literal -offset indent
 580 STAILQ_HEAD(HEADNAME, TYPE) head;
 581 .Ed
 582 .Pp
 583 where
 584 .Li HEADNAME
 585 is the name of the structure to be defined, and
 586 .Li TYPE
 587 is the type of the elements to be linked into the tail queue.
 588 A pointer to the head of the tail queue can later be declared as:
 589 .Bd -literal -offset indent
 590 struct HEADNAME *headp;
 591 .Ed
 592 .Pp
 593 (The names
 594 .Li head
 595 and
 596 .Li headp
 597 are user selectable.)
 598 .Pp
 599 The macro
 600 .Nm STAILQ_HEAD_INITIALIZER
 601 evaluates to an initializer for the tail queue
 602 .Fa head .
 603 .Pp
 604 The macro
 605 .Nm STAILQ_CONCAT
 606 concatenates the tail queue headed by
 607 .Fa head2
 608 onto the end of the one headed by
 609 .Fa head1
 610 removing all entries from the former.
 611 .Pp
 612 The macro
 613 .Nm STAILQ_EMPTY
 614 evaluates to true if there are no items on the tail queue.
 615 .Pp
 616 The macro
 617 .Nm STAILQ_ENTRY
 618 declares a structure that connects the elements in
 619 the tail queue.
 620 .Pp
 621 The macro
 622 .Nm STAILQ_FIRST
 623 returns the first item on the tail queue or NULL if the tail queue
 624 is empty.
 625 .Pp
 626 The macro
 627 .Nm STAILQ_FOREACH
 628 traverses the tail queue referenced by
 629 .Fa head
 630 in the forward direction, assigning each element
 631 in turn to
 632 .Fa var .
 633 .Pp
 634 The macro
 635 .Nm STAILQ_FOREACH_FROM
 636 behaves identically to
 637 .Nm STAILQ_FOREACH
 638 when
 639 .Fa var
 640 is NULL, else it treats
 641 .Fa var
 642 as a previously found STAILQ element and begins the loop at
 643 .Fa var
 644 instead of the first element in the STAILQ referenced by
 645 .Fa head .
 646 .Pp
 647 The macro
 648 .Nm STAILQ_FOREACH_SAFE
 649 traverses the tail queue referenced by
 650 .Fa head
 651 in the forward direction, assigning each element
 652 in turn to
 653 .Fa var .
 654 However, unlike
 655 .Fn STAILQ_FOREACH
 656 here it is permitted to both remove
 657 .Fa var
 658 as well as free it from within the loop safely without interfering with the
 659 traversal.
 660 .Pp
 661 The macro
 662 .Nm STAILQ_FOREACH_FROM_SAFE
 663 behaves identically to
 664 .Nm STAILQ_FOREACH_SAFE
 665 when
 666 .Fa var
 667 is NULL, else it treats
 668 .Fa var
 669 as a previously found STAILQ element and begins the loop at
 670 .Fa var
 671 instead of the first element in the STAILQ referenced by
 672 .Fa head .
 673 .Pp
 674 The macro
 675 .Nm STAILQ_INIT
 676 initializes the tail queue referenced by
 677 .Fa head .
 678 .Pp
 679 The macro
 680 .Nm STAILQ_INSERT_HEAD
 681 inserts the new element
 682 .Fa elm
 683 at the head of the tail queue.
 684 .Pp
 685 The macro
 686 .Nm STAILQ_INSERT_TAIL
 687 inserts the new element
 688 .Fa elm
 689 at the end of the tail queue.
 690 .Pp
 691 The macro
 692 .Nm STAILQ_INSERT_AFTER
 693 inserts the new element
 694 .Fa elm
 695 after the element
 696 .Fa listelm .
 697 .Pp
 698 The macro
 699 .Nm STAILQ_LAST
 700 returns the last item on the tail queue.
 701 If the tail queue is empty the return value is
 702 .Dv NULL .
 703 .Pp
 704 The macro
 705 .Nm STAILQ_NEXT
 706 returns the next item on the tail queue, or NULL this item is the last.
 707 .Pp
 708 The macro
 709 .Nm STAILQ_REMOVE_AFTER
 710 removes the element after
 711 .Fa elm
 712 from the tail queue.
 713 Unlike
 714 .Fa STAILQ_REMOVE ,
 715 this macro does not traverse the entire tail queue.
 716 .Pp
 717 The macro
 718 .Nm STAILQ_REMOVE_HEAD
 719 removes the element at the head of the tail queue.
 720 For optimum efficiency,
 721 elements being removed from the head of the tail queue should
 722 use this macro explicitly rather than the generic
 723 .Fa STAILQ_REMOVE
 724 macro.
 725 .Pp
 726 The macro
 727 .Nm STAILQ_REMOVE
 728 removes the element
 729 .Fa elm
 730 from the tail queue.
 731 .Pp
 732 The macro
 733 .Nm STAILQ_SWAP
 734 swaps the contents of
 735 .Fa head1
 736 and
 737 .Fa head2 .
 738 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
 739 .Bd -literal
 740 STAILQ_HEAD(stailhead, entry) head =
 741     STAILQ_HEAD_INITIALIZER(head);
 742 struct stailhead *headp;                /* Singly-linked tail queue head. */
 743 struct entry {
 744         ...
 745         STAILQ_ENTRY(entry) entries;    /* Tail queue. */
 746         ...
 747 } *n1, *n2, *n3, *np;
 748
 749 STAILQ_INIT(&head);                     /* Initialize the queue. */
 750
 751 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 752 STAILQ_INSERT_HEAD(&head, n1, entries);
 753
 754 n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
 755 STAILQ_INSERT_TAIL(&head, n1, entries);
 756
 757 n2 = malloc(sizeof(struct entry));      /* Insert after. */
 758 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
 759                                         /* Deletion. */
 760 STAILQ_REMOVE(&head, n2, entry, entries);
 761 free(n2);
 762                                         /* Deletion from the head. */
 763 n3 = STAILQ_FIRST(&head);
 764 STAILQ_REMOVE_HEAD(&head, entries);
 765 free(n3);
 766                                         /* Forward traversal. */
 767 STAILQ_FOREACH(np, &head, entries)
 768         np-> ...
 769                                         /* Safe forward traversal. */
 770 STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
 771         np->do_stuff();
 772         ...
 773         STAILQ_REMOVE(&head, np, entry, entries);
 774         free(np);
 775 }
 776                                         /* TailQ Deletion. */
 777 while (!STAILQ_EMPTY(&head)) {
 778         n1 = STAILQ_FIRST(&head);
 779         STAILQ_REMOVE_HEAD(&head, entries);
 780         free(n1);
 781 }
 782                                         /* Faster TailQ Deletion. */
 783 n1 = STAILQ_FIRST(&head);
 784 while (n1 != NULL) {
 785         n2 = STAILQ_NEXT(n1, entries);
 786         free(n1);
 787         n1 = n2;
 788 }
 789 STAILQ_INIT(&head);
 790 .Ed
 791 .Sh LISTS
 792 A list is headed by a structure defined by the
 793 .Nm LIST_HEAD
 794 macro.
 795 This structure contains a single pointer to the first element
 796 on the list.
 797 The elements are doubly linked so that an arbitrary element can be
 798 removed without traversing the list.
 799 New elements can be added to the list after an existing element,
 800 before an existing element, or at the head of the list.
 801 A
 802 .Fa LIST_HEAD
 803 structure is declared as follows:
 804 .Bd -literal -offset indent
 805 LIST_HEAD(HEADNAME, TYPE) head;
 806 .Ed
 807 .Pp
 808 where
 809 .Fa HEADNAME
 810 is the name of the structure to be defined, and
 811 .Fa TYPE
 812 is the type of the elements to be linked into the list.
 813 A pointer to the head of the list can later be declared as:
 814 .Bd -literal -offset indent
 815 struct HEADNAME *headp;
 816 .Ed
 817 .Pp
 818 (The names
 819 .Li head
 820 and
 821 .Li headp
 822 are user selectable.)
 823 .Pp
 824 The macro
 825 .Nm LIST_HEAD_INITIALIZER
 826 evaluates to an initializer for the list
 827 .Fa head .
 828 .Pp
 829 The macro
 830 .Nm LIST_EMPTY
 831 evaluates to true if there are no elements in the list.
 832 .Pp
 833 The macro
 834 .Nm LIST_ENTRY
 835 declares a structure that connects the elements in
 836 the list.
 837 .Pp
 838 The macro
 839 .Nm LIST_FIRST
 840 returns the first element in the list or NULL if the list
 841 is empty.
 842 .Pp
 843 The macro
 844 .Nm LIST_FOREACH
 845 traverses the list referenced by
 846 .Fa head
 847 in the forward direction, assigning each element in turn to
 848 .Fa var .
 849 .Pp
 850 The macro
 851 .Nm LIST_FOREACH_FROM
 852 behaves identically to
 853 .Nm LIST_FOREACH
 854 when
 855 .Fa var
 856 is NULL, else it treats
 857 .Fa var
 858 as a previously found LIST element and begins the loop at
 859 .Fa var
 860 instead of the first element in the LIST referenced by
 861 .Fa head .
 862 .Pp
 863 The macro
 864 .Nm LIST_FOREACH_SAFE
 865 traverses the list referenced by
 866 .Fa head
 867 in the forward direction, assigning each element in turn to
 868 .Fa var .
 869 However, unlike
 870 .Fn LIST_FOREACH
 871 here it is permitted to both remove
 872 .Fa var
 873 as well as free it from within the loop safely without interfering with the
 874 traversal.
 875 .Pp
 876 The macro
 877 .Nm LIST_FOREACH_FROM_SAFE
 878 behaves identically to
 879 .Nm LIST_FOREACH_SAFE
 880 when
 881 .Fa var
 882 is NULL, else it treats
 883 .Fa var
 884 as a previously found LIST element and begins the loop at
 885 .Fa var
 886 instead of the first element in the LIST referenced by
 887 .Fa head .
 888 .Pp
 889 The macro
 890 .Nm LIST_INIT
 891 initializes the list referenced by
 892 .Fa head .
 893 .Pp
 894 The macro
 895 .Nm LIST_INSERT_HEAD
 896 inserts the new element
 897 .Fa elm
 898 at the head of the list.
 899 .Pp
 900 The macro
 901 .Nm LIST_INSERT_AFTER
 902 inserts the new element
 903 .Fa elm
 904 after the element
 905 .Fa listelm .
 906 .Pp
 907 The macro
 908 .Nm LIST_INSERT_BEFORE
 909 inserts the new element
 910 .Fa elm
 911 before the element
 912 .Fa listelm .
 913 .Pp
 914 The macro
 915 .Nm LIST_NEXT
 916 returns the next element in the list, or NULL if this is the last.
 917 .Pp
 918 The macro
 919 .Nm LIST_PREV
 920 returns the previous element in the list, or NULL if this is the first.
 921 List
 922 .Fa head
 923 must contain element
 924 .Fa elm .
 925 .Pp
 926 The macro
 927 .Nm LIST_REMOVE
 928 removes the element
 929 .Fa elm
 930 from the list.
 931 .Pp
 932 The macro
 933 .Nm LIST_SWAP
 934 swaps the contents of
 935 .Fa head1
 936 and
 937 .Fa head2 .
 938 .Sh LIST EXAMPLE
 939 .Bd -literal
 940 LIST_HEAD(listhead, entry) head =
 941     LIST_HEAD_INITIALIZER(head);
 942 struct listhead *headp;                 /* List head. */
 943 struct entry {
 944         ...
 945         LIST_ENTRY(entry) entries;      /* List. */
 946         ...
 947 } *n1, *n2, *n3, *np, *np_temp;
 948
 949 LIST_INIT(&head);                       /* Initialize the list. */
 950
 951 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 952 LIST_INSERT_HEAD(&head, n1, entries);
 953
 954 n2 = malloc(sizeof(struct entry));      /* Insert after. */
 955 LIST_INSERT_AFTER(n1, n2, entries);
 956
 957 n3 = malloc(sizeof(struct entry));      /* Insert before. */
 958 LIST_INSERT_BEFORE(n2, n3, entries);
 959
 960 LIST_REMOVE(n2, entries);               /* Deletion. */
 961 free(n2);
 962                                         /* Forward traversal. */
 963 LIST_FOREACH(np, &head, entries)
 964         np-> ...
 965
 966                                         /* Safe forward traversal. */
 967 LIST_FOREACH_SAFE(np, &head, entries, np_temp) {
 968         np->do_stuff();
 969         ...
 970         LIST_REMOVE(np, entries);
 971         free(np);
 972 }
 973
 974 while (!LIST_EMPTY(&head)) {            /* List Deletion. */
 975         n1 = LIST_FIRST(&head);
 976         LIST_REMOVE(n1, entries);
 977         free(n1);
 978 }
 979
 980 n1 = LIST_FIRST(&head);                 /* Faster List Deletion. */
 981 while (n1 != NULL) {
 982         n2 = LIST_NEXT(n1, entries);
 983         free(n1);
 984         n1 = n2;
 985 }
 986 LIST_INIT(&head);
 987 .Ed
 988 .Sh TAIL QUEUES
 989 A tail queue is headed by a structure defined by the
 990 .Nm TAILQ_HEAD
 991 macro.
 992 This structure contains a pair of pointers,
 993 one to the first element in the tail queue and the other to
 994 the last element in the tail queue.
 995 The elements are doubly linked so that an arbitrary element can be
 996 removed without traversing the tail queue.
 997 New elements can be added to the tail queue after an existing element,
 998 before an existing element, at the head of the tail queue,
 999 or at the end of the tail queue.
1000 A
1001 .Fa TAILQ_HEAD
1002 structure is declared as follows:
1003 .Bd -literal -offset indent
1004 TAILQ_HEAD(HEADNAME, TYPE) head;
1005 .Ed
1006 .Pp
1007 where
1008 .Li HEADNAME
1009 is the name of the structure to be defined, and
1010 .Li TYPE
1011 is the type of the elements to be linked into the tail queue.
1012 A pointer to the head of the tail queue can later be declared as:
1013 .Bd -literal -offset indent
1014 struct HEADNAME *headp;
1015 .Ed
1016 .Pp
1017 (The names
1018 .Li head
1019 and
1020 .Li headp
1021 are user selectable.)
1022 .Pp
1023 The macro
1024 .Nm TAILQ_HEAD_INITIALIZER
1025 evaluates to an initializer for the tail queue
1026 .Fa head .
1027 .Pp
1028 The macro
1029 .Nm TAILQ_CONCAT
1030 concatenates the tail queue headed by
1031 .Fa head2
1032 onto the end of the one headed by
1033 .Fa head1
1034 removing all entries from the former.
1035 .Pp
1036 The macro
1037 .Nm TAILQ_EMPTY
1038 evaluates to true if there are no items on the tail queue.
1039 .Pp
1040 The macro
1041 .Nm TAILQ_ENTRY
1042 declares a structure that connects the elements in
1043 the tail queue.
1044 .Pp
1045 The macro
1046 .Nm TAILQ_FIRST
1047 returns the first item on the tail queue or NULL if the tail queue
1048 is empty.
1049 .Pp
1050 The macro
1051 .Nm TAILQ_FOREACH
1052 traverses the tail queue referenced by
1053 .Fa head
1054 in the forward direction, assigning each element in turn to
1055 .Fa var .
1056 .Fa var
1057 is set to
1058 .Dv NULL
1059 if the loop completes normally, or if there were no elements.
1060 .Pp
1061 The macro
1062 .Nm TAILQ_FOREACH_FROM
1063 behaves identically to
1064 .Nm TAILQ_FOREACH
1065 when
1066 .Fa var
1067 is NULL, else it treats
1068 .Fa var
1069 as a previously found TAILQ element and begins the loop at
1070 .Fa var
1071 instead of the first element in the TAILQ referenced by
1072 .Fa head .
1073 .Pp
1074 The macro
1075 .Nm TAILQ_FOREACH_REVERSE
1076 traverses the tail queue referenced by
1077 .Fa head
1078 in the reverse direction, assigning each element in turn to
1079 .Fa var .
1080 .Pp
1081 The macro
1082 .Nm TAILQ_FOREACH_REVERSE_FROM
1083 behaves identically to
1084 .Nm TAILQ_FOREACH_REVERSE
1085 when
1086 .Fa var
1087 is NULL, else it treats
1088 .Fa var
1089 as a previously found TAILQ element and begins the reverse loop at
1090 .Fa var
1091 instead of the last element in the TAILQ referenced by
1092 .Fa head .
1093 .Pp
1094 The macros
1095 .Nm TAILQ_FOREACH_SAFE
1096 and
1097 .Nm TAILQ_FOREACH_REVERSE_SAFE
1098 traverse the list referenced by
1099 .Fa head
1100 in the forward or reverse direction respectively,
1101 assigning each element in turn to
1102 .Fa var .
1103 However, unlike their unsafe counterparts,
1104 .Nm TAILQ_FOREACH
1105 and
1106 .Nm TAILQ_FOREACH_REVERSE
1107 permit to both remove
1108 .Fa var
1109 as well as free it from within the loop safely without interfering with the
1110 traversal.
1111 .Pp
1112 The macro
1113 .Nm TAILQ_FOREACH_FROM_SAFE
1114 behaves identically to
1115 .Nm TAILQ_FOREACH_SAFE
1116 when
1117 .Fa var
1118 is NULL, else it treats
1119 .Fa var
1120 as a previously found TAILQ element and begins the loop at
1121 .Fa var
1122 instead of the first element in the TAILQ referenced by
1123 .Fa head .
1124 .Pp
1125 The macro
1126 .Nm TAILQ_FOREACH_REVERSE_FROM_SAFE
1127 behaves identically to
1128 .Nm TAILQ_FOREACH_REVERSE_SAFE
1129 when
1130 .Fa var
1131 is NULL, else it treats
1132 .Fa var
1133 as a previously found TAILQ element and begins the reverse loop at
1134 .Fa var
1135 instead of the last element in the TAILQ referenced by
1136 .Fa head .
1137 .Pp
1138 The macro
1139 .Nm TAILQ_INIT
1140 initializes the tail queue referenced by
1141 .Fa head .
1142 .Pp
1143 The macro
1144 .Nm TAILQ_INSERT_HEAD
1145 inserts the new element
1146 .Fa elm
1147 at the head of the tail queue.
1148 .Pp
1149 The macro
1150 .Nm TAILQ_INSERT_TAIL
1151 inserts the new element
1152 .Fa elm
1153 at the end of the tail queue.
1154 .Pp
1155 The macro
1156 .Nm TAILQ_INSERT_AFTER
1157 inserts the new element
1158 .Fa elm
1159 after the element
1160 .Fa listelm .
1161 .Pp
1162 The macro
1163 .Nm TAILQ_INSERT_BEFORE
1164 inserts the new element
1165 .Fa elm
1166 before the element
1167 .Fa listelm .
1168 .Pp
1169 The macro
1170 .Nm TAILQ_LAST
1171 returns the last item on the tail queue.
1172 If the tail queue is empty the return value is
1173 .Dv NULL .
1174 .Pp
1175 The macro
1176 .Nm TAILQ_NEXT
1177 returns the next item on the tail queue, or NULL if this item is the last.
1178 .Pp
1179 The macro
1180 .Nm TAILQ_PREV
1181 returns the previous item on the tail queue, or NULL if this item
1182 is the first.
1183 .Pp
1184 The macro
1185 .Nm TAILQ_REMOVE
1186 removes the element
1187 .Fa elm
1188 from the tail queue.
1189 .Pp
1190 The macro
1191 .Nm TAILQ_SWAP
1192 swaps the contents of
1193 .Fa head1
1194 and
1195 .Fa head2 .
1196 .Sh TAIL QUEUE EXAMPLE
1197 .Bd -literal
1198 TAILQ_HEAD(tailhead, entry) head =
1199     TAILQ_HEAD_INITIALIZER(head);
1200 struct tailhead *headp;                 /* Tail queue head. */
1201 struct entry {
1202         ...
1203         TAILQ_ENTRY(entry) entries;     /* Tail queue. */
1204         ...
1205 } *n1, *n2, *n3, *np;
1206
1207 TAILQ_INIT(&head);                      /* Initialize the queue. */
1208
1209 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
1210 TAILQ_INSERT_HEAD(&head, n1, entries);
1211
1212 n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
1213 TAILQ_INSERT_TAIL(&head, n1, entries);
1214
1215 n2 = malloc(sizeof(struct entry));      /* Insert after. */
1216 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
1217
1218 n3 = malloc(sizeof(struct entry));      /* Insert before. */
1219 TAILQ_INSERT_BEFORE(n2, n3, entries);
1220
1221 TAILQ_REMOVE(&head, n2, entries);       /* Deletion. */
1222 free(n2);
1223                                         /* Forward traversal. */
1224 TAILQ_FOREACH(np, &head, entries)
1225         np-> ...
1226                                         /* Safe forward traversal. */
1227 TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
1228         np->do_stuff();
1229         ...
1230         TAILQ_REMOVE(&head, np, entries);
1231         free(np);
1232 }
1233                                         /* Reverse traversal. */
1234 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
1235         np-> ...
1236                                         /* TailQ Deletion. */
1237 while (!TAILQ_EMPTY(&head)) {
1238         n1 = TAILQ_FIRST(&head);
1239         TAILQ_REMOVE(&head, n1, entries);
1240         free(n1);
1241 }
1242                                         /* Faster TailQ Deletion. */
1243 n1 = TAILQ_FIRST(&head);
1244 while (n1 != NULL) {
1245         n2 = TAILQ_NEXT(n1, entries);
1246         free(n1);
1247         n1 = n2;
1248 }
1249 TAILQ_INIT(&head);
1250 .Ed
1251 .Sh SEE ALSO
1252 .Xr tree 3
1253 .Sh HISTORY
1254 The
1255 .Nm queue
1256 functions first appeared in
1257 .Bx 4.4 .