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