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