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