share/man/man3/queue.3

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