man3/queue.3

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