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 June 17, 2013
  36 .Dt QUEUE 3
  37 .Os
  38 .Sh NAME
  39 .Nm SLIST_EMPTY ,
  40 .Nm SLIST_ENTRY ,
  41 .Nm SLIST_FIRST ,
  42 .Nm SLIST_FOREACH ,
  43 .Nm SLIST_FOREACH_FROM ,
  44 .Nm SLIST_FOREACH_SAFE ,
  45 .Nm SLIST_FOREACH_FROM_SAFE ,
  46 .Nm SLIST_HEAD ,
  47 .Nm SLIST_HEAD_INITIALIZER ,
  48 .Nm SLIST_INIT ,
  49 .Nm SLIST_INSERT_AFTER ,
  50 .Nm SLIST_INSERT_HEAD ,
  51 .Nm SLIST_NEXT ,
  52 .Nm SLIST_REMOVE_AFTER ,
  53 .Nm SLIST_REMOVE_HEAD ,
  54 .Nm SLIST_REMOVE ,
  55 .Nm SLIST_SWAP ,
  56 .Nm STAILQ_CONCAT ,
  57 .Nm STAILQ_EMPTY ,
  58 .Nm STAILQ_ENTRY ,
  59 .Nm STAILQ_FIRST ,
  60 .Nm STAILQ_FOREACH ,
  61 .Nm STAILQ_FOREACH_FROM ,
  62 .Nm STAILQ_FOREACH_SAFE ,
  63 .Nm STAILQ_FOREACH_FROM_SAFE ,
  64 .Nm STAILQ_HEAD ,
  65 .Nm STAILQ_HEAD_INITIALIZER ,
  66 .Nm STAILQ_INIT ,
  67 .Nm STAILQ_INSERT_AFTER ,
  68 .Nm STAILQ_INSERT_HEAD ,
  69 .Nm STAILQ_INSERT_TAIL ,
  70 .Nm STAILQ_LAST ,
  71 .Nm STAILQ_NEXT ,
  72 .Nm STAILQ_REMOVE_AFTER ,
  73 .Nm STAILQ_REMOVE_HEAD ,
  74 .Nm STAILQ_REMOVE ,
  75 .Nm STAILQ_SWAP ,
  76 .Nm LIST_EMPTY ,
  77 .Nm LIST_ENTRY ,
  78 .Nm LIST_FIRST ,
  79 .Nm LIST_FOREACH ,
  80 .Nm LIST_FOREACH_FROM ,
  81 .Nm LIST_FOREACH_SAFE ,
  82 .Nm LIST_FOREACH_FROM_SAFE ,
  83 .Nm LIST_HEAD ,
  84 .Nm LIST_HEAD_INITIALIZER ,
  85 .Nm LIST_INIT ,
  86 .Nm LIST_INSERT_AFTER ,
  87 .Nm LIST_INSERT_BEFORE ,
  88 .Nm LIST_INSERT_HEAD ,
  89 .Nm LIST_NEXT ,
  90 .Nm LIST_PREV ,
  91 .Nm LIST_REMOVE ,
  92 .Nm LIST_SWAP ,
  93 .Nm TAILQ_CONCAT ,
  94 .Nm TAILQ_EMPTY ,
  95 .Nm TAILQ_ENTRY ,
  96 .Nm TAILQ_FIRST ,
  97 .Nm TAILQ_FOREACH ,
  98 .Nm TAILQ_FOREACH_FROM ,
  99 .Nm TAILQ_FOREACH_SAFE ,
 100 .Nm TAILQ_FOREACH_FROM_SAFE ,
 101 .Nm TAILQ_FOREACH_REVERSE ,
 102 .Nm TAILQ_FOREACH_REVERSE_FROM ,
 103 .Nm TAILQ_FOREACH_REVERSE_SAFE ,
 104 .Nm TAILQ_FOREACH_REVERSE_FROM_SAFE ,
 105 .Nm TAILQ_HEAD ,
 106 .Nm TAILQ_HEAD_INITIALIZER ,
 107 .Nm TAILQ_INIT ,
 108 .Nm TAILQ_INSERT_AFTER ,
 109 .Nm TAILQ_INSERT_BEFORE ,
 110 .Nm TAILQ_INSERT_HEAD ,
 111 .Nm TAILQ_INSERT_TAIL ,
 112 .Nm TAILQ_LAST ,
 113 .Nm TAILQ_NEXT ,
 114 .Nm TAILQ_PREV ,
 115 .Nm TAILQ_REMOVE ,
 116 .Nm TAILQ_SWAP
 117 .Nd implementations of singly-linked lists, singly-linked tail queues,
 118 lists and tail queues
 119 .Sh SYNOPSIS
 120 .In sys/queue.h
 121 .\"
 122 .Fn SLIST_EMPTY "SLIST_HEAD *head"
 123 .Fn SLIST_ENTRY "TYPE"
 124 .Fn SLIST_FIRST "SLIST_HEAD *head"
 125 .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
 126 .Fn SLIST_FOREACH_FROM "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
 127 .Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
 128 .Fn SLIST_FOREACH_FROM_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
 129 .Fn SLIST_HEAD "HEADNAME" "TYPE"
 130 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
 131 .Fn SLIST_INIT "SLIST_HEAD *head"
 132 .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
 133 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
 134 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
 135 .Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME"
 136 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
 137 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
 138 .Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "SLIST_ENTRY NAME"
 139 .\"
 140 .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
 141 .Fn STAILQ_EMPTY "STAILQ_HEAD *head"
 142 .Fn STAILQ_ENTRY "TYPE"
 143 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
 144 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
 145 .Fn STAILQ_FOREACH_FROM "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
 146 .Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
 147 .Fn STAILQ_FOREACH_FROM_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
 148 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
 149 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
 150 .Fn STAILQ_INIT "STAILQ_HEAD *head"
 151 .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
 152 .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
 153 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
 154 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
 155 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
 156 .Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
 157 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
 158 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
 159 .Fn STAILQ_SWAP "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" "STAILQ_ENTRY NAME"
 160 .\"
 161 .Fn LIST_EMPTY "LIST_HEAD *head"
 162 .Fn LIST_ENTRY "TYPE"
 163 .Fn LIST_FIRST "LIST_HEAD *head"
 164 .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
 165 .Fn LIST_FOREACH_FROM "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
 166 .Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
 167 .Fn LIST_FOREACH_FROM_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
 168 .Fn LIST_HEAD "HEADNAME" "TYPE"
 169 .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
 170 .Fn LIST_INIT "LIST_HEAD *head"
 171 .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
 172 .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
 173 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
 174 .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
 175 .Fn LIST_PREV "TYPE *elm" "LIST_HEAD *head" "TYPE" "LIST_ENTRY NAME"
 176 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
 177 .Fn LIST_SWAP "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME"
 178 .\"
 179 .Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME"
 180 .Fn TAILQ_EMPTY "TAILQ_HEAD *head"
 181 .Fn TAILQ_ENTRY "TYPE"
 182 .Fn TAILQ_FIRST "TAILQ_HEAD *head"
 183 .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
 184 .Fn TAILQ_FOREACH_FROM "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
 185 .Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
 186 .Fn TAILQ_FOREACH_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
 187 .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
 188 .Fn TAILQ_FOREACH_REVERSE_FROM "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
 189 .Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
 190 .Fn TAILQ_FOREACH_REVERSE_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
 191 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
 192 .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
 193 .Fn TAILQ_INIT "TAILQ_HEAD *head"
 194 .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
 195 .Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
 196 .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
 197 .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
 198 .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
 199 .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
 200 .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
 201 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
 202 .Fn TAILQ_SWAP "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TYPE" "TAILQ_ENTRY NAME"
 203 .\"
 204 .Sh DESCRIPTION
 205 These macros define and operate on four types of data structures:
 206 singly-linked lists, singly-linked tail queues, lists, and tail queues.
 207 All four structures support the following functionality:
 208 .Bl -enum -compact -offset indent
 209 .It
 210 Insertion of a new entry at the head of the list.
 211 .It
 212 Insertion of a new entry after any element in the list.
 213 .It
 214 O(1) removal of an entry from the head of the list.
 215 .It
 216 Forward traversal through the list.
 217 .It
 218 Swapping the contents of two lists.
 219 .El
 220 .Pp
 221 Singly-linked lists are the simplest of the four data structures
 222 and support only the above functionality.
 223 Singly-linked lists are ideal for applications with large datasets
 224 and few or no removals,
 225 or for implementing a LIFO queue.
 226 Singly-linked lists add the following functionality:
 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 .Bl -enum -compact -offset indent
 234 .It
 235 Entries can be added at the end of a list.
 236 .It
 237 O(n) removal of any entry in the list.
 238 .It
 239 They may be concatenated.
 240 .El
 241 However:
 242 .Bl -enum -compact -offset indent
 243 .It
 244 All list insertions must specify the head of the list.
 245 .It
 246 Each head entry requires two pointers rather than one.
 247 .It
 248 Code size is about 15% greater and operations run about 20% slower
 249 than singly-linked lists.
 250 .El
 251 .Pp
 252 Singly-linked tail queues are ideal for applications with large datasets and
 253 few or no removals,
 254 or for implementing a FIFO queue.
 255 .Pp
 256 All doubly linked types of data structures (lists and tail queues)
 257 additionally allow:
 258 .Bl -enum -compact -offset indent
 259 .It
 260 Insertion of a new entry before any element in the list.
 261 .It
 262 O(1) removal of any entry in the list.
 263 .El
 264 However:
 265 .Bl -enum -compact -offset indent
 266 .It
 267 Each element requires two pointers rather than one.
 268 .It
 269 Code size and execution time of operations (except for removal) is about
 270 twice that of the singly-linked data-structures.
 271 .El
 272 .Pp
 273 Linked lists are the simplest of the doubly linked data structures.
 274 They add the following functionality over the above:
 275 .Bl -enum -compact -offset indent
 276 .It
 277 They may be traversed backwards.
 278 .El
 279 However:
 280 .Bl -enum -compact -offset indent
 281 .It
 282 To traverse backwards, an entry to begin the traversal and the list in
 283 which it is contained must be specified.
 284 .El
 285 .Pp
 286 Tail queues add the following functionality:
 287 .Bl -enum -compact -offset indent
 288 .It
 289 Entries can be added at the end of a list.
 290 .It
 291 They may be traversed backwards, from tail to head.
 292 .It
 293 They may be concatenated.
 294 .El
 295 However:
 296 .Bl -enum -compact -offset indent
 297 .It
 298 All list insertions and removals must specify the head of the list.
 299 .It
 300 Each head entry requires two pointers rather than one.
 301 .It
 302 Code size is about 15% greater and operations run about 20% slower
 303 than singly-linked lists.
 304 .El
 305 .Pp
 306 In the macro definitions,
 307 .Fa TYPE
 308 is the name of a user defined structure,
 309 that must contain a field of type
 310 .Li SLIST_ENTRY ,
 311 .Li STAILQ_ENTRY ,
 312 .Li LIST_ENTRY ,
 313 or
 314 .Li TAILQ_ENTRY ,
 315 named
 316 .Fa NAME .
 317 The argument
 318 .Fa HEADNAME
 319 is the name of a user defined structure that must be declared
 320 using the macros
 321 .Li SLIST_HEAD ,
 322 .Li STAILQ_HEAD ,
 323 .Li LIST_HEAD ,
 324 or
 325 .Li TAILQ_HEAD .
 326 See the examples below for further explanation of how these
 327 macros are used.
 328 .Sh SINGLY-LINKED LISTS
 329 A singly-linked list is headed by a structure defined by the
 330 .Nm SLIST_HEAD
 331 macro.
 332 This structure contains a single pointer to the first element
 333 on the list.
 334 The elements are singly linked for minimum space and pointer manipulation
 335 overhead at the expense of O(n) removal for arbitrary elements.
 336 New elements can be added to the list after an existing element or
 337 at the head of the list.
 338 An
 339 .Fa SLIST_HEAD
 340 structure is declared as follows:
 341 .Bd -literal -offset indent
 342 SLIST_HEAD(HEADNAME, TYPE) head;
 343 .Ed
 344 .Pp
 345 where
 346 .Fa HEADNAME
 347 is the name of the structure to be defined, and
 348 .Fa TYPE
 349 is the type of the elements to be linked into the list.
 350 A pointer to the head of the list can later be declared as:
 351 .Bd -literal -offset indent
 352 struct HEADNAME *headp;
 353 .Ed
 354 .Pp
 355 (The names
 356 .Li head
 357 and
 358 .Li headp
 359 are user selectable.)
 360 .Pp
 361 The macro
 362 .Nm SLIST_HEAD_INITIALIZER
 363 evaluates to an initializer for the list
 364 .Fa head .
 365 .Pp
 366 The macro
 367 .Nm SLIST_EMPTY
 368 evaluates to true if there are no elements in the list.
 369 .Pp
 370 The macro
 371 .Nm SLIST_ENTRY
 372 declares a structure that connects the elements in
 373 the list.
 374 .Pp
 375 The macro
 376 .Nm SLIST_FIRST
 377 returns the first element in the list or NULL if the list is empty.
 378 .Pp
 379 The macro
 380 .Nm SLIST_FOREACH
 381 traverses the list referenced by
 382 .Fa head
 383 in the forward direction, assigning each element in
 384 turn to
 385 .Fa var .
 386 .Pp
 387 The macro
 388 .Nm SLIST_FOREACH_FROM
 389 behaves identically to
 390 .Nm SLIST_FOREACH
 391 when
 392 .Fa var
 393 is NULL, else it treats
 394 .Fa var
 395 as a previously found SLIST element and begins the loop at
 396 .Fa var
 397 instead of the first element in the SLIST referenced by
 398 .Fa head .
 399 .Pp
 400 The macro
 401 .Nm SLIST_FOREACH_SAFE
 402 traverses the list referenced by
 403 .Fa head
 404 in the forward direction, assigning each element in
 405 turn to
 406 .Fa var .
 407 However, unlike
 408 .Fn SLIST_FOREACH
 409 here it is permitted to both remove
 410 .Fa var
 411 as well as free it from within the loop safely without interfering with the
 412 traversal.
 413 .Pp
 414 The macro
 415 .Nm SLIST_FOREACH_FROM_SAFE
 416 behaves identically to
 417 .Nm SLIST_FOREACH_SAFE
 418 when
 419 .Fa var
 420 is NULL, else it treats
 421 .Fa var
 422 as a previously found SLIST element and begins the loop at
 423 .Fa var
 424 instead of the first element in the SLIST referenced by
 425 .Fa head .
 426 .Pp
 427 The macro
 428 .Nm SLIST_INIT
 429 initializes the list referenced by
 430 .Fa head .
 431 .Pp
 432 The macro
 433 .Nm SLIST_INSERT_HEAD
 434 inserts the new element
 435 .Fa elm
 436 at the head of the list.
 437 .Pp
 438 The macro
 439 .Nm SLIST_INSERT_AFTER
 440 inserts the new element
 441 .Fa elm
 442 after the element
 443 .Fa listelm .
 444 .Pp
 445 The macro
 446 .Nm SLIST_NEXT
 447 returns the next element in the list.
 448 .Pp
 449 The macro
 450 .Nm SLIST_REMOVE_AFTER
 451 removes the element after
 452 .Fa elm
 453 from the list. Unlike
 454 .Fa SLIST_REMOVE ,
 455 this macro does not traverse the entire list.
 456 .Pp
 457 The macro
 458 .Nm SLIST_REMOVE_HEAD
 459 removes the element
 460 .Fa elm
 461 from the head of the list.
 462 For optimum efficiency,
 463 elements being removed from the head of the list should explicitly use
 464 this macro instead of the generic
 465 .Fa SLIST_REMOVE
 466 macro.
 467 .Pp
 468 The macro
 469 .Nm SLIST_REMOVE
 470 removes the element
 471 .Fa elm
 472 from the list.
 473 .Pp
 474 The macro
 475 .Nm SLIST_SWAP
 476 swaps the contents of
 477 .Fa head1
 478 and
 479 .Fa head2 .
 480 .Sh SINGLY-LINKED LIST EXAMPLE
 481 .Bd -literal
 482 SLIST_HEAD(slisthead, entry) head =
 483     SLIST_HEAD_INITIALIZER(head);
 484 struct slisthead *headp;                /* Singly-linked List head. */
 485 struct entry {
 486         ...
 487         SLIST_ENTRY(entry) entries;     /* Singly-linked List. */
 488         ...
 489 } *n1, *n2, *n3, *np;
 490
 491 SLIST_INIT(&head);                      /* Initialize the list. */
 492
 493 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 494 SLIST_INSERT_HEAD(&head, n1, entries);
 495
 496 n2 = malloc(sizeof(struct entry));      /* Insert after. */
 497 SLIST_INSERT_AFTER(n1, n2, entries);
 498
 499 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
 500 free(n2);
 501
 502 n3 = SLIST_FIRST(&head);
 503 SLIST_REMOVE_HEAD(&head, entries);      /* Deletion from the head. */
 504 free(n3);
 505                                         /* Forward traversal. */
 506 SLIST_FOREACH(np, &head, entries)
 507         np-> ...
 508                                         /* Safe forward traversal. */
 509 SLIST_FOREACH_SAFE(np, &head, entries, np_temp) {
 510         np->do_stuff();
 511         ...
 512         SLIST_REMOVE(&head, np, entry, entries);
 513         free(np);
 514 }
 515
 516 while (!SLIST_EMPTY(&head)) {           /* List Deletion. */
 517         n1 = SLIST_FIRST(&head);
 518         SLIST_REMOVE_HEAD(&head, entries);
 519         free(n1);
 520 }
 521 .Ed
 522 .Sh SINGLY-LINKED TAIL QUEUES
 523 A singly-linked tail queue is headed by a structure defined by the
 524 .Nm STAILQ_HEAD
 525 macro.
 526 This structure contains a pair of pointers,
 527 one to the first element in the tail queue and the other to
 528 the last element in the tail queue.
 529 The elements are singly linked for minimum space and pointer
 530 manipulation overhead at the expense of O(n) removal for arbitrary
 531 elements.
 532 New elements can be added to the tail queue after an existing element,
 533 at the head of the tail queue, or at the end of the tail queue.
 534 A
 535 .Fa STAILQ_HEAD
 536 structure is declared as follows:
 537 .Bd -literal -offset indent
 538 STAILQ_HEAD(HEADNAME, TYPE) head;
 539 .Ed
 540 .Pp
 541 where
 542 .Li HEADNAME
 543 is the name of the structure to be defined, and
 544 .Li TYPE
 545 is the type of the elements to be linked into the tail queue.
 546 A pointer to the head of the tail queue can later be declared as:
 547 .Bd -literal -offset indent
 548 struct HEADNAME *headp;
 549 .Ed
 550 .Pp
 551 (The names
 552 .Li head
 553 and
 554 .Li headp
 555 are user selectable.)
 556 .Pp
 557 The macro
 558 .Nm STAILQ_HEAD_INITIALIZER
 559 evaluates to an initializer for the tail queue
 560 .Fa head .
 561 .Pp
 562 The macro
 563 .Nm STAILQ_CONCAT
 564 concatenates the tail queue headed by
 565 .Fa head2
 566 onto the end of the one headed by
 567 .Fa head1
 568 removing all entries from the former.
 569 .Pp
 570 The macro
 571 .Nm STAILQ_EMPTY
 572 evaluates to true if there are no items on the tail queue.
 573 .Pp
 574 The macro
 575 .Nm STAILQ_ENTRY
 576 declares a structure that connects the elements in
 577 the tail queue.
 578 .Pp
 579 The macro
 580 .Nm STAILQ_FIRST
 581 returns the first item on the tail queue or NULL if the tail queue
 582 is empty.
 583 .Pp
 584 The macro
 585 .Nm STAILQ_FOREACH
 586 traverses the tail queue referenced by
 587 .Fa head
 588 in the forward direction, assigning each element
 589 in turn to
 590 .Fa var .
 591 .Pp
 592 The macro
 593 .Nm STAILQ_FOREACH_FROM
 594 behaves identically to
 595 .Nm STAILQ_FOREACH
 596 when
 597 .Fa var
 598 is NULL, else it treats
 599 .Fa var
 600 as a previously found STAILQ element and begins the loop at
 601 .Fa var
 602 instead of the first element in the STAILQ referenced by
 603 .Fa head .
 604 .Pp
 605 The macro
 606 .Nm STAILQ_FOREACH_SAFE
 607 traverses the tail queue referenced by
 608 .Fa head
 609 in the forward direction, assigning each element
 610 in turn to
 611 .Fa var .
 612 However, unlike
 613 .Fn STAILQ_FOREACH
 614 here it is permitted to both remove
 615 .Fa var
 616 as well as free it from within the loop safely without interfering with the
 617 traversal.
 618 .Pp
 619 The macro
 620 .Nm STAILQ_FOREACH_FROM_SAFE
 621 behaves identically to
 622 .Nm STAILQ_FOREACH_SAFE
 623 when
 624 .Fa var
 625 is NULL, else it treats
 626 .Fa var
 627 as a previously found STAILQ element and begins the loop at
 628 .Fa var
 629 instead of the first element in the STAILQ referenced by
 630 .Fa head .
 631 .Pp
 632 The macro
 633 .Nm STAILQ_INIT
 634 initializes the tail queue referenced by
 635 .Fa head .
 636 .Pp
 637 The macro
 638 .Nm STAILQ_INSERT_HEAD
 639 inserts the new element
 640 .Fa elm
 641 at the head of the tail queue.
 642 .Pp
 643 The macro
 644 .Nm STAILQ_INSERT_TAIL
 645 inserts the new element
 646 .Fa elm
 647 at the end of the tail queue.
 648 .Pp
 649 The macro
 650 .Nm STAILQ_INSERT_AFTER
 651 inserts the new element
 652 .Fa elm
 653 after the element
 654 .Fa listelm .
 655 .Pp
 656 The macro
 657 .Nm STAILQ_LAST
 658 returns the last item on the tail queue.
 659 If the tail queue is empty the return value is
 660 .Dv NULL .
 661 .Pp
 662 The macro
 663 .Nm STAILQ_NEXT
 664 returns the next item on the tail queue, or NULL this item is the last.
 665 .Pp
 666 The macro
 667 .Nm STAILQ_REMOVE_AFTER
 668 removes the element after
 669 .Fa elm
 670 from the tail queue. 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 .Sh 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 .Sh 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 .Sh 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 .Sh 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 .Sh 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 TAILQ_INIT(&head);
1207 .Ed
1208 .Sh SEE ALSO
1209 .Xr tree 3
1210 .Sh HISTORY
1211 The
1212 .Nm queue
1213 functions first appeared in
1214 .Bx 4.4 .