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