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.
 454 Unlike
 455 .Fa SLIST_REMOVE ,
 456 this macro does not traverse the entire list.
 457 .Pp
 458 The macro
 459 .Nm SLIST_REMOVE_HEAD
 460 removes the element
 461 .Fa elm
 462 from the head of the list.
 463 For optimum efficiency,
 464 elements being removed from the head of the list should explicitly use
 465 this macro instead of the generic
 466 .Fa SLIST_REMOVE
 467 macro.
 468 .Pp
 469 The macro
 470 .Nm SLIST_REMOVE
 471 removes the element
 472 .Fa elm
 473 from the list.
 474 .Pp
 475 The macro
 476 .Nm SLIST_SWAP
 477 swaps the contents of
 478 .Fa head1
 479 and
 480 .Fa head2 .
 481 .Sh SINGLY-LINKED LIST EXAMPLE
 482 .Bd -literal
 483 SLIST_HEAD(slisthead, entry) head =
 484     SLIST_HEAD_INITIALIZER(head);
 485 struct slisthead *headp;                /* Singly-linked List head. */
 486 struct entry {
 487         ...
 488         SLIST_ENTRY(entry) entries;     /* Singly-linked List. */
 489         ...
 490 } *n1, *n2, *n3, *np;
 491
 492 SLIST_INIT(&head);                      /* Initialize the list. */
 493
 494 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 495 SLIST_INSERT_HEAD(&head, n1, entries);
 496
 497 n2 = malloc(sizeof(struct entry));      /* Insert after. */
 498 SLIST_INSERT_AFTER(n1, n2, entries);
 499
 500 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
 501 free(n2);
 502
 503 n3 = SLIST_FIRST(&head);
 504 SLIST_REMOVE_HEAD(&head, entries);      /* Deletion from the head. */
 505 free(n3);
 506                                         /* Forward traversal. */
 507 SLIST_FOREACH(np, &head, entries)
 508         np-> ...
 509                                         /* Safe forward traversal. */
 510 SLIST_FOREACH_SAFE(np, &head, entries, np_temp) {
 511         np->do_stuff();
 512         ...
 513         SLIST_REMOVE(&head, np, entry, entries);
 514         free(np);
 515 }
 516
 517 while (!SLIST_EMPTY(&head)) {           /* List Deletion. */
 518         n1 = SLIST_FIRST(&head);
 519         SLIST_REMOVE_HEAD(&head, entries);
 520         free(n1);
 521 }
 522 .Ed
 523 .Sh SINGLY-LINKED TAIL QUEUES
 524 A singly-linked tail queue is headed by a structure defined by the
 525 .Nm STAILQ_HEAD
 526 macro.
 527 This structure contains a pair of pointers,
 528 one to the first element in the tail queue and the other to
 529 the last element in the tail queue.
 530 The elements are singly linked for minimum space and pointer
 531 manipulation overhead at the expense of O(n) removal for arbitrary
 532 elements.
 533 New elements can be added to the tail queue after an existing element,
 534 at the head of the tail queue, or at the end of the tail queue.
 535 A
 536 .Fa STAILQ_HEAD
 537 structure is declared as follows:
 538 .Bd -literal -offset indent
 539 STAILQ_HEAD(HEADNAME, TYPE) head;
 540 .Ed
 541 .Pp
 542 where
 543 .Li HEADNAME
 544 is the name of the structure to be defined, and
 545 .Li TYPE
 546 is the type of the elements to be linked into the tail queue.
 547 A pointer to the head of the tail queue can later be declared as:
 548 .Bd -literal -offset indent
 549 struct HEADNAME *headp;
 550 .Ed
 551 .Pp
 552 (The names
 553 .Li head
 554 and
 555 .Li headp
 556 are user selectable.)
 557 .Pp
 558 The macro
 559 .Nm STAILQ_HEAD_INITIALIZER
 560 evaluates to an initializer for the tail queue
 561 .Fa head .
 562 .Pp
 563 The macro
 564 .Nm STAILQ_CONCAT
 565 concatenates the tail queue headed by
 566 .Fa head2
 567 onto the end of the one headed by
 568 .Fa head1
 569 removing all entries from the former.
 570 .Pp
 571 The macro
 572 .Nm STAILQ_EMPTY
 573 evaluates to true if there are no items on the tail queue.
 574 .Pp
 575 The macro
 576 .Nm STAILQ_ENTRY
 577 declares a structure that connects the elements in
 578 the tail queue.
 579 .Pp
 580 The macro
 581 .Nm STAILQ_FIRST
 582 returns the first item on the tail queue or NULL if the tail queue
 583 is empty.
 584 .Pp
 585 The macro
 586 .Nm STAILQ_FOREACH
 587 traverses the tail queue referenced by
 588 .Fa head
 589 in the forward direction, assigning each element
 590 in turn to
 591 .Fa var .
 592 .Pp
 593 The macro
 594 .Nm STAILQ_FOREACH_FROM
 595 behaves identically to
 596 .Nm STAILQ_FOREACH
 597 when
 598 .Fa var
 599 is NULL, else it treats
 600 .Fa var
 601 as a previously found STAILQ element and begins the loop at
 602 .Fa var
 603 instead of the first element in the STAILQ referenced by
 604 .Fa head .
 605 .Pp
 606 The macro
 607 .Nm STAILQ_FOREACH_SAFE
 608 traverses the tail queue referenced by
 609 .Fa head
 610 in the forward direction, assigning each element
 611 in turn to
 612 .Fa var .
 613 However, unlike
 614 .Fn STAILQ_FOREACH
 615 here it is permitted to both remove
 616 .Fa var
 617 as well as free it from within the loop safely without interfering with the
 618 traversal.
 619 .Pp
 620 The macro
 621 .Nm STAILQ_FOREACH_FROM_SAFE
 622 behaves identically to
 623 .Nm STAILQ_FOREACH_SAFE
 624 when
 625 .Fa var
 626 is NULL, else it treats
 627 .Fa var
 628 as a previously found STAILQ element and begins the loop at
 629 .Fa var
 630 instead of the first element in the STAILQ referenced by
 631 .Fa head .
 632 .Pp
 633 The macro
 634 .Nm STAILQ_INIT
 635 initializes the tail queue referenced by
 636 .Fa head .
 637 .Pp
 638 The macro
 639 .Nm STAILQ_INSERT_HEAD
 640 inserts the new element
 641 .Fa elm
 642 at the head of the tail queue.
 643 .Pp
 644 The macro
 645 .Nm STAILQ_INSERT_TAIL
 646 inserts the new element
 647 .Fa elm
 648 at the end of the tail queue.
 649 .Pp
 650 The macro
 651 .Nm STAILQ_INSERT_AFTER
 652 inserts the new element
 653 .Fa elm
 654 after the element
 655 .Fa listelm .
 656 .Pp
 657 The macro
 658 .Nm STAILQ_LAST
 659 returns the last item on the tail queue.
 660 If the tail queue is empty the return value is
 661 .Dv NULL .
 662 .Pp
 663 The macro
 664 .Nm STAILQ_NEXT
 665 returns the next item on the tail queue, or NULL this item is the last.
 666 .Pp
 667 The macro
 668 .Nm STAILQ_REMOVE_AFTER
 669 removes the element after
 670 .Fa elm
 671 from the tail queue.
 672 Unlike
 673 .Fa STAILQ_REMOVE ,
 674 this macro does not traverse the entire tail queue.
 675 .Pp
 676 The macro
 677 .Nm STAILQ_REMOVE_HEAD
 678 removes the element at the head of the tail queue.
 679 For optimum efficiency,
 680 elements being removed from the head of the tail queue should
 681 use this macro explicitly rather than the generic
 682 .Fa STAILQ_REMOVE
 683 macro.
 684 .Pp
 685 The macro
 686 .Nm STAILQ_REMOVE
 687 removes the element
 688 .Fa elm
 689 from the tail queue.
 690 .Pp
 691 The macro
 692 .Nm STAILQ_SWAP
 693 swaps the contents of
 694 .Fa head1
 695 and
 696 .Fa head2 .
 697 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
 698 .Bd -literal
 699 STAILQ_HEAD(stailhead, entry) head =
 700     STAILQ_HEAD_INITIALIZER(head);
 701 struct stailhead *headp;                /* Singly-linked tail queue head. */
 702 struct entry {
 703         ...
 704         STAILQ_ENTRY(entry) entries;    /* Tail queue. */
 705         ...
 706 } *n1, *n2, *n3, *np;
 707
 708 STAILQ_INIT(&head);                     /* Initialize the queue. */
 709
 710 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 711 STAILQ_INSERT_HEAD(&head, n1, entries);
 712
 713 n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
 714 STAILQ_INSERT_TAIL(&head, n1, entries);
 715
 716 n2 = malloc(sizeof(struct entry));      /* Insert after. */
 717 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
 718                                         /* Deletion. */
 719 STAILQ_REMOVE(&head, n2, entry, entries);
 720 free(n2);
 721                                         /* Deletion from the head. */
 722 n3 = STAILQ_FIRST(&head);
 723 STAILQ_REMOVE_HEAD(&head, entries);
 724 free(n3);
 725                                         /* Forward traversal. */
 726 STAILQ_FOREACH(np, &head, entries)
 727         np-> ...
 728                                         /* Safe forward traversal. */
 729 STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
 730         np->do_stuff();
 731         ...
 732         STAILQ_REMOVE(&head, np, entry, entries);
 733         free(np);
 734 }
 735                                         /* TailQ Deletion. */
 736 while (!STAILQ_EMPTY(&head)) {
 737         n1 = STAILQ_FIRST(&head);
 738         STAILQ_REMOVE_HEAD(&head, entries);
 739         free(n1);
 740 }
 741                                         /* Faster TailQ Deletion. */
 742 n1 = STAILQ_FIRST(&head);
 743 while (n1 != NULL) {
 744         n2 = STAILQ_NEXT(n1, entries);
 745         free(n1);
 746         n1 = n2;
 747 }
 748 STAILQ_INIT(&head);
 749 .Ed
 750 .Sh LISTS
 751 A list is headed by a structure defined by the
 752 .Nm LIST_HEAD
 753 macro.
 754 This structure contains a single pointer to the first element
 755 on the list.
 756 The elements are doubly linked so that an arbitrary element can be
 757 removed without traversing the list.
 758 New elements can be added to the list after an existing element,
 759 before an existing element, or at the head of the list.
 760 A
 761 .Fa LIST_HEAD
 762 structure is declared as follows:
 763 .Bd -literal -offset indent
 764 LIST_HEAD(HEADNAME, TYPE) head;
 765 .Ed
 766 .Pp
 767 where
 768 .Fa HEADNAME
 769 is the name of the structure to be defined, and
 770 .Fa TYPE
 771 is the type of the elements to be linked into the list.
 772 A pointer to the head of the list can later be declared as:
 773 .Bd -literal -offset indent
 774 struct HEADNAME *headp;
 775 .Ed
 776 .Pp
 777 (The names
 778 .Li head
 779 and
 780 .Li headp
 781 are user selectable.)
 782 .Pp
 783 The macro
 784 .Nm LIST_HEAD_INITIALIZER
 785 evaluates to an initializer for the list
 786 .Fa head .
 787 .Pp
 788 The macro
 789 .Nm LIST_EMPTY
 790 evaluates to true if there are no elements in the list.
 791 .Pp
 792 The macro
 793 .Nm LIST_ENTRY
 794 declares a structure that connects the elements in
 795 the list.
 796 .Pp
 797 The macro
 798 .Nm LIST_FIRST
 799 returns the first element in the list or NULL if the list
 800 is empty.
 801 .Pp
 802 The macro
 803 .Nm LIST_FOREACH
 804 traverses the list referenced by
 805 .Fa head
 806 in the forward direction, assigning each element in turn to
 807 .Fa var .
 808 .Pp
 809 The macro
 810 .Nm LIST_FOREACH_FROM
 811 behaves identically to
 812 .Nm LIST_FOREACH
 813 when
 814 .Fa var
 815 is NULL, else it treats
 816 .Fa var
 817 as a previously found LIST element and begins the loop at
 818 .Fa var
 819 instead of the first element in the LIST referenced by
 820 .Fa head .
 821 .Pp
 822 The macro
 823 .Nm LIST_FOREACH_SAFE
 824 traverses the list referenced by
 825 .Fa head
 826 in the forward direction, assigning each element in turn to
 827 .Fa var .
 828 However, unlike
 829 .Fn LIST_FOREACH
 830 here it is permitted to both remove
 831 .Fa var
 832 as well as free it from within the loop safely without interfering with the
 833 traversal.
 834 .Pp
 835 The macro
 836 .Nm LIST_FOREACH_FROM_SAFE
 837 behaves identically to
 838 .Nm LIST_FOREACH_SAFE
 839 when
 840 .Fa var
 841 is NULL, else it treats
 842 .Fa var
 843 as a previously found LIST element and begins the loop at
 844 .Fa var
 845 instead of the first element in the LIST referenced by
 846 .Fa head .
 847 .Pp
 848 The macro
 849 .Nm LIST_INIT
 850 initializes the list referenced by
 851 .Fa head .
 852 .Pp
 853 The macro
 854 .Nm LIST_INSERT_HEAD
 855 inserts the new element
 856 .Fa elm
 857 at the head of the list.
 858 .Pp
 859 The macro
 860 .Nm LIST_INSERT_AFTER
 861 inserts the new element
 862 .Fa elm
 863 after the element
 864 .Fa listelm .
 865 .Pp
 866 The macro
 867 .Nm LIST_INSERT_BEFORE
 868 inserts the new element
 869 .Fa elm
 870 before the element
 871 .Fa listelm .
 872 .Pp
 873 The macro
 874 .Nm LIST_NEXT
 875 returns the next element in the list, or NULL if this is the last.
 876 .Pp
 877 The macro
 878 .Nm LIST_PREV
 879 returns the previous element in the list, or NULL if this is the first.
 880 List
 881 .Fa head
 882 must contain element
 883 .Fa elm .
 884 .Pp
 885 The macro
 886 .Nm LIST_REMOVE
 887 removes the element
 888 .Fa elm
 889 from the list.
 890 .Pp
 891 The macro
 892 .Nm LIST_SWAP
 893 swaps the contents of
 894 .Fa head1
 895 and
 896 .Fa head2 .
 897 .Sh LIST EXAMPLE
 898 .Bd -literal
 899 LIST_HEAD(listhead, entry) head =
 900     LIST_HEAD_INITIALIZER(head);
 901 struct listhead *headp;                 /* List head. */
 902 struct entry {
 903         ...
 904         LIST_ENTRY(entry) entries;      /* List. */
 905         ...
 906 } *n1, *n2, *n3, *np, *np_temp;
 907
 908 LIST_INIT(&head);                       /* Initialize the list. */
 909
 910 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 911 LIST_INSERT_HEAD(&head, n1, entries);
 912
 913 n2 = malloc(sizeof(struct entry));      /* Insert after. */
 914 LIST_INSERT_AFTER(n1, n2, entries);
 915
 916 n3 = malloc(sizeof(struct entry));      /* Insert before. */
 917 LIST_INSERT_BEFORE(n2, n3, entries);
 918
 919 LIST_REMOVE(n2, entries);               /* Deletion. */
 920 free(n2);
 921                                         /* Forward traversal. */
 922 LIST_FOREACH(np, &head, entries)
 923         np-> ...
 924
 925                                         /* Safe forward traversal. */
 926 LIST_FOREACH_SAFE(np, &head, entries, np_temp) {
 927         np->do_stuff();
 928         ...
 929         LIST_REMOVE(np, entries);
 930         free(np);
 931 }
 932
 933 while (!LIST_EMPTY(&head)) {            /* List Deletion. */
 934         n1 = LIST_FIRST(&head);
 935         LIST_REMOVE(n1, entries);
 936         free(n1);
 937 }
 938
 939 n1 = LIST_FIRST(&head);                 /* Faster List Deletion. */
 940 while (n1 != NULL) {
 941         n2 = LIST_NEXT(n1, entries);
 942         free(n1);
 943         n1 = n2;
 944 }
 945 LIST_INIT(&head);
 946 .Ed
 947 .Sh TAIL QUEUES
 948 A tail queue is headed by a structure defined by the
 949 .Nm TAILQ_HEAD
 950 macro.
 951 This structure contains a pair of pointers,
 952 one to the first element in the tail queue and the other to
 953 the last element in the tail queue.
 954 The elements are doubly linked so that an arbitrary element can be
 955 removed without traversing the tail queue.
 956 New elements can be added to the tail queue after an existing element,
 957 before an existing element, at the head of the tail queue,
 958 or at the end of the tail queue.
 959 A
 960 .Fa TAILQ_HEAD
 961 structure is declared as follows:
 962 .Bd -literal -offset indent
 963 TAILQ_HEAD(HEADNAME, TYPE) head;
 964 .Ed
 965 .Pp
 966 where
 967 .Li HEADNAME
 968 is the name of the structure to be defined, and
 969 .Li TYPE
 970 is the type of the elements to be linked into the tail queue.
 971 A pointer to the head of the tail queue can later be declared as:
 972 .Bd -literal -offset indent
 973 struct HEADNAME *headp;
 974 .Ed
 975 .Pp
 976 (The names
 977 .Li head
 978 and
 979 .Li headp
 980 are user selectable.)
 981 .Pp
 982 The macro
 983 .Nm TAILQ_HEAD_INITIALIZER
 984 evaluates to an initializer for the tail queue
 985 .Fa head .
 986 .Pp
 987 The macro
 988 .Nm TAILQ_CONCAT
 989 concatenates the tail queue headed by
 990 .Fa head2
 991 onto the end of the one headed by
 992 .Fa head1
 993 removing all entries from the former.
 994 .Pp
 995 The macro
 996 .Nm TAILQ_EMPTY
 997 evaluates to true if there are no items on the tail queue.
 998 .Pp
 999 The macro
1000 .Nm TAILQ_ENTRY
1001 declares a structure that connects the elements in
1002 the tail queue.
1003 .Pp
1004 The macro
1005 .Nm TAILQ_FIRST
1006 returns the first item on the tail queue or NULL if the tail queue
1007 is empty.
1008 .Pp
1009 The macro
1010 .Nm TAILQ_FOREACH
1011 traverses the tail queue referenced by
1012 .Fa head
1013 in the forward direction, assigning each element in turn to
1014 .Fa var .
1015 .Fa var
1016 is set to
1017 .Dv NULL
1018 if the loop completes normally, or if there were no elements.
1019 .Pp
1020 The macro
1021 .Nm TAILQ_FOREACH_FROM
1022 behaves identically to
1023 .Nm TAILQ_FOREACH
1024 when
1025 .Fa var
1026 is NULL, else it treats
1027 .Fa var
1028 as a previously found TAILQ element and begins the loop at
1029 .Fa var
1030 instead of the first element in the TAILQ referenced by
1031 .Fa head .
1032 .Pp
1033 The macro
1034 .Nm TAILQ_FOREACH_REVERSE
1035 traverses the tail queue referenced by
1036 .Fa head
1037 in the reverse direction, assigning each element in turn to
1038 .Fa var .
1039 .Pp
1040 The macro
1041 .Nm TAILQ_FOREACH_REVERSE_FROM
1042 behaves identically to
1043 .Nm TAILQ_FOREACH_REVERSE
1044 when
1045 .Fa var
1046 is NULL, else it treats
1047 .Fa var
1048 as a previously found TAILQ element and begins the reverse loop at
1049 .Fa var
1050 instead of the last element in the TAILQ referenced by
1051 .Fa head .
1052 .Pp
1053 The macros
1054 .Nm TAILQ_FOREACH_SAFE
1055 and
1056 .Nm TAILQ_FOREACH_REVERSE_SAFE
1057 traverse the list referenced by
1058 .Fa head
1059 in the forward or reverse direction respectively,
1060 assigning each element in turn to
1061 .Fa var .
1062 However, unlike their unsafe counterparts,
1063 .Nm TAILQ_FOREACH
1064 and
1065 .Nm TAILQ_FOREACH_REVERSE
1066 permit to both remove
1067 .Fa var
1068 as well as free it from within the loop safely without interfering with the
1069 traversal.
1070 .Pp
1071 The macro
1072 .Nm TAILQ_FOREACH_FROM_SAFE
1073 behaves identically to
1074 .Nm TAILQ_FOREACH_SAFE
1075 when
1076 .Fa var
1077 is NULL, else it treats
1078 .Fa var
1079 as a previously found TAILQ element and begins the loop at
1080 .Fa var
1081 instead of the first element in the TAILQ referenced by
1082 .Fa head .
1083 .Pp
1084 The macro
1085 .Nm TAILQ_FOREACH_REVERSE_FROM_SAFE
1086 behaves identically to
1087 .Nm TAILQ_FOREACH_REVERSE_SAFE
1088 when
1089 .Fa var
1090 is NULL, else it treats
1091 .Fa var
1092 as a previously found TAILQ element and begins the reverse loop at
1093 .Fa var
1094 instead of the last element in the TAILQ referenced by
1095 .Fa head .
1096 .Pp
1097 The macro
1098 .Nm TAILQ_INIT
1099 initializes the tail queue referenced by
1100 .Fa head .
1101 .Pp
1102 The macro
1103 .Nm TAILQ_INSERT_HEAD
1104 inserts the new element
1105 .Fa elm
1106 at the head of the tail queue.
1107 .Pp
1108 The macro
1109 .Nm TAILQ_INSERT_TAIL
1110 inserts the new element
1111 .Fa elm
1112 at the end of the tail queue.
1113 .Pp
1114 The macro
1115 .Nm TAILQ_INSERT_AFTER
1116 inserts the new element
1117 .Fa elm
1118 after the element
1119 .Fa listelm .
1120 .Pp
1121 The macro
1122 .Nm TAILQ_INSERT_BEFORE
1123 inserts the new element
1124 .Fa elm
1125 before the element
1126 .Fa listelm .
1127 .Pp
1128 The macro
1129 .Nm TAILQ_LAST
1130 returns the last item on the tail queue.
1131 If the tail queue is empty the return value is
1132 .Dv NULL .
1133 .Pp
1134 The macro
1135 .Nm TAILQ_NEXT
1136 returns the next item on the tail queue, or NULL if this item is the last.
1137 .Pp
1138 The macro
1139 .Nm TAILQ_PREV
1140 returns the previous item on the tail queue, or NULL if this item
1141 is the first.
1142 .Pp
1143 The macro
1144 .Nm TAILQ_REMOVE
1145 removes the element
1146 .Fa elm
1147 from the tail queue.
1148 .Pp
1149 The macro
1150 .Nm TAILQ_SWAP
1151 swaps the contents of
1152 .Fa head1
1153 and
1154 .Fa head2 .
1155 .Sh TAIL QUEUE EXAMPLE
1156 .Bd -literal
1157 TAILQ_HEAD(tailhead, entry) head =
1158     TAILQ_HEAD_INITIALIZER(head);
1159 struct tailhead *headp;                 /* Tail queue head. */
1160 struct entry {
1161         ...
1162         TAILQ_ENTRY(entry) entries;     /* Tail queue. */
1163         ...
1164 } *n1, *n2, *n3, *np;
1165
1166 TAILQ_INIT(&head);                      /* Initialize the queue. */
1167
1168 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
1169 TAILQ_INSERT_HEAD(&head, n1, entries);
1170
1171 n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
1172 TAILQ_INSERT_TAIL(&head, n1, entries);
1173
1174 n2 = malloc(sizeof(struct entry));      /* Insert after. */
1175 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
1176
1177 n3 = malloc(sizeof(struct entry));      /* Insert before. */
1178 TAILQ_INSERT_BEFORE(n2, n3, entries);
1179
1180 TAILQ_REMOVE(&head, n2, entries);       /* Deletion. */
1181 free(n2);
1182                                         /* Forward traversal. */
1183 TAILQ_FOREACH(np, &head, entries)
1184         np-> ...
1185                                         /* Safe forward traversal. */
1186 TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
1187         np->do_stuff();
1188         ...
1189         TAILQ_REMOVE(&head, np, entries);
1190         free(np);
1191 }
1192                                         /* Reverse traversal. */
1193 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
1194         np-> ...
1195                                         /* TailQ Deletion. */
1196 while (!TAILQ_EMPTY(&head)) {
1197         n1 = TAILQ_FIRST(&head);
1198         TAILQ_REMOVE(&head, n1, entries);
1199         free(n1);
1200 }
1201                                         /* Faster TailQ Deletion. */
1202 n1 = TAILQ_FIRST(&head);
1203 while (n1 != NULL) {
1204         n2 = TAILQ_NEXT(n1, entries);
1205         free(n1);
1206         n1 = n2;
1207 }
1208 TAILQ_INIT(&head);
1209 .Ed
1210 .Sh SEE ALSO
1211 .Xr tree 3
1212 .Sh HISTORY
1213 The
1214 .Nm queue
1215 functions first appeared in
1216 .Bx 4.4 .