bsd/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: /repoman/r/ncvs/src/share/man/man3/queue.3,v 1.37 2006/03/22 02:40:38 mckusick Exp $
  34 .\"
  35 .Dd January 24, 1994
  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_SAFE ,
  44 .Nm SLIST_HEAD ,
  45 .Nm SLIST_HEAD_INITIALIZER ,
  46 .Nm SLIST_INIT ,
  47 .Nm SLIST_INSERT_AFTER ,
  48 .Nm SLIST_INSERT_HEAD ,
  49 .Nm SLIST_NEXT ,
  50 .Nm SLIST_REMOVE_HEAD ,
  51 .Nm SLIST_REMOVE ,
  52 .Nm STAILQ_CONCAT ,
  53 .Nm STAILQ_EMPTY ,
  54 .Nm STAILQ_ENTRY ,
  55 .Nm STAILQ_FIRST ,
  56 .Nm STAILQ_FOREACH ,
  57 .Nm STAILQ_FOREACH_SAFE ,
  58 .Nm STAILQ_HEAD ,
  59 .Nm STAILQ_HEAD_INITIALIZER ,
  60 .Nm STAILQ_INIT ,
  61 .Nm STAILQ_INSERT_AFTER ,
  62 .Nm STAILQ_INSERT_HEAD ,
  63 .Nm STAILQ_INSERT_TAIL ,
  64 .Nm STAILQ_LAST ,
  65 .Nm STAILQ_NEXT ,
  66 .Nm STAILQ_REMOVE_HEAD ,
  67 .Nm STAILQ_REMOVE ,
  68 .Nm LIST_EMPTY ,
  69 .Nm LIST_ENTRY ,
  70 .Nm LIST_FIRST ,
  71 .Nm LIST_FOREACH ,
  72 .Nm LIST_FOREACH_SAFE ,
  73 .Nm LIST_HEAD ,
  74 .Nm LIST_HEAD_INITIALIZER ,
  75 .Nm LIST_INIT ,
  76 .Nm LIST_INSERT_AFTER ,
  77 .Nm LIST_INSERT_BEFORE ,
  78 .Nm LIST_INSERT_HEAD ,
  79 .Nm LIST_NEXT ,
  80 .Nm LIST_REMOVE ,
  81 .Nm TAILQ_CONCAT ,
  82 .Nm TAILQ_EMPTY ,
  83 .Nm TAILQ_ENTRY ,
  84 .Nm TAILQ_FIRST ,
  85 .Nm TAILQ_FOREACH ,
  86 .Nm TAILQ_FOREACH_SAFE ,
  87 .Nm TAILQ_FOREACH_REVERSE ,
  88 .Nm TAILQ_FOREACH_REVERSE_SAFE ,
  89 .Nm TAILQ_HEAD ,
  90 .Nm TAILQ_HEAD_INITIALIZER ,
  91 .Nm TAILQ_INIT ,
  92 .Nm TAILQ_INSERT_AFTER ,
  93 .Nm TAILQ_INSERT_BEFORE ,
  94 .Nm TAILQ_INSERT_HEAD ,
  95 .Nm TAILQ_INSERT_TAIL ,
  96 .Nm TAILQ_LAST ,
  97 .Nm TAILQ_NEXT ,
  98 .Nm TAILQ_PREV ,
  99 .Nm TAILQ_REMOVE
 100 .Nd implementations of singly-linked lists, singly-linked tail queues,
 101 lists and tail queues
 102 .Sh SYNOPSIS
 103 .In sys/queue.h
 104 .\"
 105 .Fn SLIST_EMPTY "SLIST_HEAD *head"
 106 .Fn SLIST_ENTRY "TYPE"
 107 .Fn SLIST_FIRST "SLIST_HEAD *head"
 108 .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
 109 .Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
 110 .Fn SLIST_HEAD "HEADNAME" "TYPE"
 111 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
 112 .Fn SLIST_INIT "SLIST_HEAD *head"
 113 .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
 114 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
 115 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
 116 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
 117 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
 118 .\"
 119 .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
 120 .Fn STAILQ_EMPTY "STAILQ_HEAD *head"
 121 .Fn STAILQ_ENTRY "TYPE"
 122 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
 123 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
 124 .Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
 125 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
 126 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
 127 .Fn STAILQ_INIT "STAILQ_HEAD *head"
 128 .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
 129 .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
 130 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
 131 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
 132 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
 133 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
 134 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
 135 .\"
 136 .Fn LIST_EMPTY "LIST_HEAD *head"
 137 .Fn LIST_ENTRY "TYPE"
 138 .Fn LIST_FIRST "LIST_HEAD *head"
 139 .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
 140 .Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
 141 .Fn LIST_HEAD "HEADNAME" "TYPE"
 142 .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
 143 .Fn LIST_INIT "LIST_HEAD *head"
 144 .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
 145 .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
 146 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
 147 .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
 148 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
 149 .\"
 150 .Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME"
 151 .Fn TAILQ_EMPTY "TAILQ_HEAD *head"
 152 .Fn TAILQ_ENTRY "TYPE"
 153 .Fn TAILQ_FIRST "TAILQ_HEAD *head"
 154 .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
 155 .Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
 156 .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
 157 .Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
 158 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
 159 .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
 160 .Fn TAILQ_INIT "TAILQ_HEAD *head"
 161 .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
 162 .Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
 163 .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
 164 .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
 165 .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
 166 .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
 167 .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
 168 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
 169 .\"
 170 .Sh DESCRIPTION
 171 These macros define and operate on four types of data structures:
 172 singly-linked lists, singly-linked tail queues, lists, and tail queues.
 173 All four structures support the following functionality:
 174 .Bl -enum -compact -offset indent
 175 .It
 176 Insertion of a new entry at the head of the list.
 177 .It
 178 Insertion of a new entry after any element in the list.
 179 .It
 180 O(1) removal of an entry from the head of the list.
 181 .It
 182 O(n) removal of any entry in the list.
 183 .It
 184 Forward traversal through the list.
 185 .El
 186 .Pp
 187 Singly-linked lists are the simplest of the five data structures
 188 and support only the above functionality.
 189 Singly-linked lists are ideal for applications with large datasets
 190 and few or no removals,
 191 or for implementing a LIFO queue.
 192 .Pp
 193 Singly-linked tail queues add the following functionality:
 194 .Bl -enum -compact -offset indent
 195 .It
 196 Entries can be added at the end of a list.
 197 .It
 198 They may be concatenated.
 199 .El
 200 However:
 201 .Bl -enum -compact -offset indent
 202 .It
 203 All list insertions must specify the head of the list.
 204 .It
 205 Each head entry requires two pointers rather than one.
 206 .It
 207 Code size is about 15% greater and operations run about 20% slower
 208 than singly-linked lists.
 209 .El
 210 .Pp
 211 Singly-linked tailqs are ideal for applications with large datasets and
 212 few or no removals,
 213 or for implementing a FIFO queue.
 214 .Pp
 215 All doubly linked types of data structures (lists and tail queues)
 216 additionally allow:
 217 .Bl -enum -compact -offset indent
 218 .It
 219 Insertion of a new entry before any element in the list.
 220 .It
 221 O(1) removal of any entry in the list.
 222 .El
 223 However:
 224 .Bl -enum -compact -offset indent
 225 .It
 226 Each elements requires two pointers rather than one.
 227 .It
 228 Code size and execution time of operations (except for removal) is about
 229 twice that of the singly-linked data-structures.
 230 .El
 231 .Pp
 232 Linked lists are the simplest of the doubly linked data structures and support
 233 only the above functionality over singly-linked lists.
 234 .Pp
 235 Tail queues add the following functionality:
 236 .Bl -enum -compact -offset indent
 237 .It
 238 Entries can be added at the end of a list.
 239 .It
 240 They may be traversed backwards, from tail to head.
 241 .It
 242 They may be concatenated.
 243 .El
 244 However:
 245 .Bl -enum -compact -offset indent
 246 .It
 247 All list insertions and removals must specify the head of the list.
 248 .It
 249 Each head entry requires two pointers rather than one.
 250 .It
 251 Code size is about 15% greater and operations run about 20% slower
 252 than singly-linked lists.
 253 .El
 254 .Pp
 255 In the macro definitions,
 256 .Fa TYPE
 257 is the name of a user defined structure,
 258 that must contain a field of type
 259 .Li SLIST_ENTRY ,
 260 .Li STAILQ_ENTRY ,
 261 .Li LIST_ENTRY ,
 262 or
 263 .Li TAILQ_ENTRY ,
 264 named
 265 .Fa NAME .
 266 The argument
 267 .Fa HEADNAME
 268 is the name of a user defined structure that must be declared
 269 using the macros
 270 .Li SLIST_HEAD ,
 271 .Li STAILQ_HEAD ,
 272 .Li LIST_HEAD ,
 273 or
 274 .Li TAILQ_HEAD .
 275 See the examples below for further explanation of how these
 276 macros are used.
 277 .Sh SINGLY-LINKED LISTS
 278 A singly-linked list is headed by a structure defined by the
 279 .Nm SLIST_HEAD
 280 macro.
 281 This structure contains a single pointer to the first element
 282 on the list.
 283 The elements are singly linked for minimum space and pointer manipulation
 284 overhead at the expense of O(n) removal for arbitrary elements.
 285 New elements can be added to the list after an existing element or
 286 at the head of the list.
 287 An
 288 .Fa SLIST_HEAD
 289 structure is declared as follows:
 290 .Bd -literal -offset indent
 291 SLIST_HEAD(HEADNAME, TYPE) head;
 292 .Ed
 293 .Pp
 294 where
 295 .Fa HEADNAME
 296 is the name of the structure to be defined, and
 297 .Fa TYPE
 298 is the type of the elements to be linked into the list.
 299 A pointer to the head of the list can later be declared as:
 300 .Bd -literal -offset indent
 301 struct HEADNAME *headp;
 302 .Ed
 303 .Pp
 304 (The names
 305 .Li head
 306 and
 307 .Li headp
 308 are user selectable.)
 309 .Pp
 310 The macro
 311 .Nm SLIST_HEAD_INITIALIZER
 312 evaluates to an initializer for the list
 313 .Fa head .
 314 .Pp
 315 The macro
 316 .Nm SLIST_EMPTY
 317 evaluates to true if there are no elements in the list.
 318 .Pp
 319 The macro
 320 .Nm SLIST_ENTRY
 321 declares a structure that connects the elements in
 322 the list.
 323 .Pp
 324 The macro
 325 .Nm SLIST_FIRST
 326 returns the first element in the list or NULL if the list is empty.
 327 .Pp
 328 The macro
 329 .Nm SLIST_FOREACH
 330 traverses the list referenced by
 331 .Fa head
 332 in the forward direction, assigning each element in
 333 turn to
 334 .Fa var .
 335 .Pp
 336 The macro
 337 .Nm SLIST_FOREACH_SAFE
 338 traverses the list referenced by
 339 .Fa head
 340 in the forward direction, assigning each element in
 341 turn to
 342 .Fa var .
 343 However, unlike
 344 .Fn SLIST_FOREACH
 345 here it is permitted to both remove
 346 .Fa var
 347 as well as free it from within the loop safely without interfering with the
 348 traversal.
 349 .Pp
 350 The macro
 351 .Nm SLIST_INIT
 352 initializes the list referenced by
 353 .Fa head .
 354 .Pp
 355 The macro
 356 .Nm SLIST_INSERT_HEAD
 357 inserts the new element
 358 .Fa elm
 359 at the head of the list.
 360 .Pp
 361 The macro
 362 .Nm SLIST_INSERT_AFTER
 363 inserts the new element
 364 .Fa elm
 365 after the element
 366 .Fa listelm .
 367 .Pp
 368 The macro
 369 .Nm SLIST_NEXT
 370 returns the next element in the list.
 371 .Pp
 372 The macro
 373 .Nm SLIST_REMOVE_HEAD
 374 removes the element
 375 .Fa elm
 376 from the head of the list.
 377 For optimum efficiency,
 378 elements being removed from the head of the list should explicitly use
 379 this macro instead of the generic
 380 .Fa SLIST_REMOVE
 381 macro.
 382 .Pp
 383 The macro
 384 .Nm SLIST_REMOVE
 385 removes the element
 386 .Fa elm
 387 from the list.
 388 .Sh SINGLY-LINKED LIST EXAMPLE
 389 .Bd -literal
 390 SLIST_HEAD(slisthead, entry) head =
 391     SLIST_HEAD_INITIALIZER(head);
 392 struct slisthead *headp;                /* Singly-linked List head. */
 393 struct entry {
 394         ...
 395         SLIST_ENTRY(entry) entries;     /* Singly-linked List. */
 396         ...
 397 } *n1, *n2, *n3, *np;
 398
 399 SLIST_INIT(&head);                      /* Initialize the list. */
 400
 401 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 402 SLIST_INSERT_HEAD(&head, n1, entries);
 403
 404 n2 = malloc(sizeof(struct entry));      /* Insert after. */
 405 SLIST_INSERT_AFTER(n1, n2, entries);
 406
 407 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
 408 free(n2);
 409
 410 n3 = SLIST_FIRST(&head);
 411 SLIST_REMOVE_HEAD(&head, entries);      /* Deletion from the head. */
 412 free(n3);
 413                                         /* Forward traversal. */
 414 SLIST_FOREACH(np, &head, entries)
 415         np-> ...
 416                                         /* Safe forward traversal. */
 417 SLIST_FOREACH_SAFE(np, &head, entries, np_temp) {
 418         np->do_stuff();
 419         ...
 420         SLIST_REMOVE(&head, np, entry, entries);
 421         free(np);
 422 }
 423
 424 while (!SLIST_EMPTY(&head)) {           /* List Deletion. */
 425         n1 = SLIST_FIRST(&head);
 426         SLIST_REMOVE_HEAD(&head, entries);
 427         free(n1);
 428 }
 429 .Ed
 430 .Sh SINGLY-LINKED TAIL QUEUES
 431 A singly-linked tail queue is headed by a structure defined by the
 432 .Nm STAILQ_HEAD
 433 macro.
 434 This structure contains a pair of pointers,
 435 one to the first element in the tail queue and the other to
 436 the last element in the tail queue.
 437 The elements are singly linked for minimum space and pointer
 438 manipulation overhead at the expense of O(n) removal for arbitrary
 439 elements.
 440 New elements can be added to the tail queue after an existing element,
 441 at the head of the tail queue, or at the end of the tail queue.
 442 A
 443 .Fa STAILQ_HEAD
 444 structure is declared as follows:
 445 .Bd -literal -offset indent
 446 STAILQ_HEAD(HEADNAME, TYPE) head;
 447 .Ed
 448 .Pp
 449 where
 450 .Li HEADNAME
 451 is the name of the structure to be defined, and
 452 .Li TYPE
 453 is the type of the elements to be linked into the tail queue.
 454 A pointer to the head of the tail queue can later be declared as:
 455 .Bd -literal -offset indent
 456 struct HEADNAME *headp;
 457 .Ed
 458 .Pp
 459 (The names
 460 .Li head
 461 and
 462 .Li headp
 463 are user selectable.)
 464 .Pp
 465 The macro
 466 .Nm STAILQ_HEAD_INITIALIZER
 467 evaluates to an initializer for the tail queue
 468 .Fa head .
 469 .Pp
 470 The macro
 471 .Nm STAILQ_CONCAT
 472 concatenates the tail queue headed by
 473 .Fa head2
 474 onto the end of the one headed by
 475 .Fa head1
 476 removing all entries from the former.
 477 .Pp
 478 The macro
 479 .Nm STAILQ_EMPTY
 480 evaluates to true if there are no items on the tail queue.
 481 .Pp
 482 The macro
 483 .Nm STAILQ_ENTRY
 484 declares a structure that connects the elements in
 485 the tail queue.
 486 .Pp
 487 The macro
 488 .Nm STAILQ_FIRST
 489 returns the first item on the tail queue or NULL if the tail queue
 490 is empty.
 491 .Pp
 492 The macro
 493 .Nm STAILQ_FOREACH
 494 traverses the tail queue referenced by
 495 .Fa head
 496 in the forward direction, assigning each element
 497 in turn to
 498 .Fa var .
 499 .Pp
 500 The macro
 501 .Nm STAILQ_FOREACH_SAFE
 502 traverses the tail queue referenced by
 503 .Fa head
 504 in the forward direction, assigning each element
 505 in turn to
 506 .Fa var .
 507 However, unlike
 508 .Fn STAILQ_FOREACH
 509 here it is permitted to both remove
 510 .Fa var
 511 as well as free it from within the loop safely without interfering with the
 512 traversal.
 513 .Pp
 514 The macro
 515 .Nm STAILQ_INIT
 516 initializes the tail queue referenced by
 517 .Fa head .
 518 .Pp
 519 The macro
 520 .Nm STAILQ_INSERT_HEAD
 521 inserts the new element
 522 .Fa elm
 523 at the head of the tail queue.
 524 .Pp
 525 The macro
 526 .Nm STAILQ_INSERT_TAIL
 527 inserts the new element
 528 .Fa elm
 529 at the end of the tail queue.
 530 .Pp
 531 The macro
 532 .Nm STAILQ_INSERT_AFTER
 533 inserts the new element
 534 .Fa elm
 535 after the element
 536 .Fa listelm .
 537 .Pp
 538 The macro
 539 .Nm STAILQ_LAST
 540 returns the last item on the tail queue.
 541 If the tail queue is empty the return value is NULL.
 542 .Pp
 543 The macro
 544 .Nm STAILQ_NEXT
 545 returns the next item on the tail queue, or NULL this item is the last.
 546 .Pp
 547 The macro
 548 .Nm STAILQ_REMOVE_HEAD
 549 removes the element at the head of the tail queue.
 550 For optimum efficiency,
 551 elements being removed from the head of the tail queue should
 552 use this macro explicitly rather than the generic
 553 .Fa STAILQ_REMOVE
 554 macro.
 555 .Pp
 556 The macro
 557 .Nm STAILQ_REMOVE
 558 removes the element
 559 .Fa elm
 560 from the tail queue.
 561 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
 562 .Bd -literal
 563 STAILQ_HEAD(stailhead, entry) head =
 564     STAILQ_HEAD_INITIALIZER(head);
 565 struct stailhead *headp;                /* Singly-linked tail queue head. */
 566 struct entry {
 567         ...
 568         STAILQ_ENTRY(entry) entries;    /* Tail queue. */
 569         ...
 570 } *n1, *n2, *n3, *np;
 571
 572 STAILQ_INIT(&head);                     /* Initialize the queue. */
 573
 574 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 575 STAILQ_INSERT_HEAD(&head, n1, entries);
 576
 577 n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
 578 STAILQ_INSERT_TAIL(&head, n1, entries);
 579
 580 n2 = malloc(sizeof(struct entry));      /* Insert after. */
 581 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
 582                                         /* Deletion. */
 583 STAILQ_REMOVE(&head, n2, entry, entries);
 584 free(n2);
 585                                         /* Deletion from the head. */
 586 n3 = STAILQ_FIRST(&head);
 587 STAILQ_REMOVE_HEAD(&head, entries);
 588 free(n3);
 589                                         /* Forward traversal. */
 590 STAILQ_FOREACH(np, &head, entries)
 591         np-> ...
 592                                         /* Safe forward traversal. */
 593 STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
 594         np->do_stuff();
 595         ...
 596         STAILQ_REMOVE(&head, np, entry, entries);
 597         free(np);
 598 }
 599                                         /* TailQ Deletion. */
 600 while (!STAILQ_EMPTY(&head)) {
 601         n1 = STAILQ_FIRST(&head);
 602         STAILQ_REMOVE_HEAD(&head, entries);
 603         free(n1);
 604 }
 605                                         /* Faster TailQ Deletion. */
 606 n1 = STAILQ_FIRST(&head);
 607 while (n1 != NULL) {
 608         n2 = STAILQ_NEXT(n1, entries);
 609         free(n1);
 610         n1 = n2;
 611 }
 612 STAILQ_INIT(&head);
 613 .Ed
 614 .Sh LISTS
 615 A list is headed by a structure defined by the
 616 .Nm LIST_HEAD
 617 macro.
 618 This structure contains a single pointer to the first element
 619 on the list.
 620 The elements are doubly linked so that an arbitrary element can be
 621 removed without traversing the list.
 622 New elements can be added to the list after an existing element,
 623 before an existing element, or at the head of the list.
 624 A
 625 .Fa LIST_HEAD
 626 structure is declared as follows:
 627 .Bd -literal -offset indent
 628 LIST_HEAD(HEADNAME, TYPE) head;
 629 .Ed
 630 .Pp
 631 where
 632 .Fa HEADNAME
 633 is the name of the structure to be defined, and
 634 .Fa TYPE
 635 is the type of the elements to be linked into the list.
 636 A pointer to the head of the list can later be declared as:
 637 .Bd -literal -offset indent
 638 struct HEADNAME *headp;
 639 .Ed
 640 .Pp
 641 (The names
 642 .Li head
 643 and
 644 .Li headp
 645 are user selectable.)
 646 .Pp
 647 The macro
 648 .Nm LIST_HEAD_INITIALIZER
 649 evaluates to an initializer for the list
 650 .Fa head .
 651 .Pp
 652 The macro
 653 .Nm LIST_EMPTY
 654 evaluates to true if there are no elements in the list.
 655 .Pp
 656 The macro
 657 .Nm LIST_ENTRY
 658 declares a structure that connects the elements in
 659 the list.
 660 .Pp
 661 The macro
 662 .Nm LIST_FIRST
 663 returns the first element in the list or NULL if the list
 664 is empty.
 665 .Pp
 666 The macro
 667 .Nm LIST_FOREACH
 668 traverses the list referenced by
 669 .Fa head
 670 in the forward direction, assigning each element in turn to
 671 .Fa var .
 672 .Pp
 673 The macro
 674 .Nm LIST_FOREACH_SAFE
 675 traverses the list referenced by
 676 .Fa head
 677 in the forward direction, assigning each element in turn to
 678 .Fa var .
 679 However, unlike
 680 .Fn LIST_FOREACH
 681 here it is permitted to both remove
 682 .Fa var
 683 as well as free it from within the loop safely without interfering with the
 684 traversal.
 685 .Pp
 686 The macro
 687 .Nm LIST_INIT
 688 initializes the list referenced by
 689 .Fa head .
 690 .Pp
 691 The macro
 692 .Nm LIST_INSERT_HEAD
 693 inserts the new element
 694 .Fa elm
 695 at the head of the list.
 696 .Pp
 697 The macro
 698 .Nm LIST_INSERT_AFTER
 699 inserts the new element
 700 .Fa elm
 701 after the element
 702 .Fa listelm .
 703 .Pp
 704 The macro
 705 .Nm LIST_INSERT_BEFORE
 706 inserts the new element
 707 .Fa elm
 708 before the element
 709 .Fa listelm .
 710 .Pp
 711 The macro
 712 .Nm LIST_NEXT
 713 returns the next element in the list, or NULL if this is the last.
 714 .Pp
 715 The macro
 716 .Nm LIST_REMOVE
 717 removes the element
 718 .Fa elm
 719 from the list.
 720 .Sh LIST EXAMPLE
 721 .Bd -literal
 722 LIST_HEAD(listhead, entry) head =
 723     LIST_HEAD_INITIALIZER(head);
 724 struct listhead *headp;                 /* List head. */
 725 struct entry {
 726         ...
 727         LIST_ENTRY(entry) entries;      /* List. */
 728         ...
 729 } *n1, *n2, *n3, *np, *np_temp;
 730
 731 LIST_INIT(&head);                       /* Initialize the list. */
 732
 733 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 734 LIST_INSERT_HEAD(&head, n1, entries);
 735
 736 n2 = malloc(sizeof(struct entry));      /* Insert after. */
 737 LIST_INSERT_AFTER(n1, n2, entries);
 738
 739 n3 = malloc(sizeof(struct entry));      /* Insert before. */
 740 LIST_INSERT_BEFORE(n2, n3, entries);
 741
 742 LIST_REMOVE(n2, entries);               /* Deletion. */
 743 free(n2);
 744                                         /* Forward traversal. */
 745 LIST_FOREACH(np, &head, entries)
 746         np-> ...
 747
 748                                         /* Safe forward traversal. */
 749 LIST_FOREACH_SAFE(np, &head, entries, np_temp) {
 750         np->do_stuff();
 751         ...
 752         LIST_REMOVE(np, entries);
 753         free(np);
 754 }
 755
 756 while (!LIST_EMPTY(&head)) {            /* List Deletion. */
 757         n1 = LIST_FIRST(&head);
 758         LIST_REMOVE(n1, entries);
 759         free(n1);
 760 }
 761
 762 n1 = LIST_FIRST(&head);                 /* Faster List Deletion. */
 763 while (n1 != NULL) {
 764         n2 = LIST_NEXT(n1, entries);
 765         free(n1);
 766         n1 = n2;
 767 }
 768 LIST_INIT(&head);
 769 .Ed
 770 .Sh TAIL QUEUES
 771 A tail queue is headed by a structure defined by the
 772 .Nm TAILQ_HEAD
 773 macro.
 774 This structure contains a pair of pointers,
 775 one to the first element in the tail queue and the other to
 776 the last element in the tail queue.
 777 The elements are doubly linked so that an arbitrary element can be
 778 removed without traversing the tail queue.
 779 New elements can be added to the tail queue after an existing element,
 780 before an existing element, at the head of the tail queue,
 781 or at the end of the tail queue.
 782 A
 783 .Fa TAILQ_HEAD
 784 structure is declared as follows:
 785 .Bd -literal -offset indent
 786 TAILQ_HEAD(HEADNAME, TYPE) head;
 787 .Ed
 788 .Pp
 789 where
 790 .Li HEADNAME
 791 is the name of the structure to be defined, and
 792 .Li TYPE
 793 is the type of the elements to be linked into the tail queue.
 794 A pointer to the head of the tail queue can later be declared as:
 795 .Bd -literal -offset indent
 796 struct HEADNAME *headp;
 797 .Ed
 798 .Pp
 799 (The names
 800 .Li head
 801 and
 802 .Li headp
 803 are user selectable.)
 804 .Pp
 805 The macro
 806 .Nm TAILQ_HEAD_INITIALIZER
 807 evaluates to an initializer for the tail queue
 808 .Fa head .
 809 .Pp
 810 The macro
 811 .Nm TAILQ_CONCAT
 812 concatenates the tail queue headed by
 813 .Fa head2
 814 onto the end of the one headed by
 815 .Fa head1
 816 removing all entries from the former.
 817 .Pp
 818 The macro
 819 .Nm TAILQ_EMPTY
 820 evaluates to true if there are no items on the tail queue.
 821 .Pp
 822 The macro
 823 .Nm TAILQ_ENTRY
 824 declares a structure that connects the elements in
 825 the tail queue.
 826 .Pp
 827 The macro
 828 .Nm TAILQ_FIRST
 829 returns the first item on the tail queue or NULL if the tail queue
 830 is empty.
 831 .Pp
 832 The macro
 833 .Nm TAILQ_FOREACH
 834 traverses the tail queue referenced by
 835 .Fa head
 836 in the forward direction, assigning each element in turn to
 837 .Fa var .
 838 .Fa var
 839 is set to
 840 .Dv NULL
 841 if the loop completes normally, or if there were no elements.
 842 .Pp
 843 The macro
 844 .Nm TAILQ_FOREACH_REVERSE
 845 traverses the tail queue referenced by
 846 .Fa head
 847 in the reverse direction, assigning each element in turn to
 848 .Fa var .
 849 .Pp
 850 The macros
 851 .Nm TAILQ_FOREACH_SAFE
 852 and
 853 .Nm TAILQ_FOREACH_REVERSE_SAFE
 854 traverse the list referenced by
 855 .Fa head
 856 in the forward or reverse direction respectively,
 857 assigning each element in turn to
 858 .Fa var .
 859 However, unlike their unsafe counterparts,
 860 .Nm TAILQ_FOREACH
 861 and
 862 .Nm TAILQ_FOREACH_REVERSE
 863 permit to both remove
 864 .Fa var
 865 as well as free it from within the loop safely without interfering with the
 866 traversal.
 867 .Pp
 868 The macro
 869 .Nm TAILQ_INIT
 870 initializes the tail queue referenced by
 871 .Fa head .
 872 .Pp
 873 The macro
 874 .Nm TAILQ_INSERT_HEAD
 875 inserts the new element
 876 .Fa elm
 877 at the head of the tail queue.
 878 .Pp
 879 The macro
 880 .Nm TAILQ_INSERT_TAIL
 881 inserts the new element
 882 .Fa elm
 883 at the end of the tail queue.
 884 .Pp
 885 The macro
 886 .Nm TAILQ_INSERT_AFTER
 887 inserts the new element
 888 .Fa elm
 889 after the element
 890 .Fa listelm .
 891 .Pp
 892 The macro
 893 .Nm TAILQ_INSERT_BEFORE
 894 inserts the new element
 895 .Fa elm
 896 before the element
 897 .Fa listelm .
 898 .Pp
 899 The macro
 900 .Nm TAILQ_LAST
 901 returns the last item on the tail queue.
 902 If the tail queue is empty the return value is NULL.
 903 .Pp
 904 The macro
 905 .Nm TAILQ_NEXT
 906 returns the next item on the tail queue, or NULL if this item is the last.
 907 .Pp
 908 The macro
 909 .Nm TAILQ_PREV
 910 returns the previous item on the tail queue, or NULL if this item
 911 is the first.
 912 .Pp
 913 The macro
 914 .Nm TAILQ_REMOVE
 915 removes the element
 916 .Fa elm
 917 from the tail queue.
 918 .Sh TAIL QUEUE EXAMPLE
 919 .Bd -literal
 920 TAILQ_HEAD(tailhead, entry) head =
 921     TAILQ_HEAD_INITIALIZER(head);
 922 struct tailhead *headp;                 /* Tail queue head. */
 923 struct entry {
 924         ...
 925         TAILQ_ENTRY(entry) entries;     /* Tail queue. */
 926         ...
 927 } *n1, *n2, *n3, *np;
 928
 929 TAILQ_INIT(&head);                      /* Initialize the queue. */
 930
 931 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 932 TAILQ_INSERT_HEAD(&head, n1, entries);
 933
 934 n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
 935 TAILQ_INSERT_TAIL(&head, n1, entries);
 936
 937 n2 = malloc(sizeof(struct entry));      /* Insert after. */
 938 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
 939
 940 n3 = malloc(sizeof(struct entry));      /* Insert before. */
 941 TAILQ_INSERT_BEFORE(n2, n3, entries);
 942
 943 TAILQ_REMOVE(&head, n2, entries);       /* Deletion. */
 944 free(n2);
 945                                         /* Forward traversal. */
 946 TAILQ_FOREACH(np, &head, entries)
 947         np-> ...
 948                                         /* Safe forward traversal. */
 949 TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
 950         np->do_stuff();
 951         ...
 952         TAILQ_REMOVE(&head, np, entries);
 953         free(np);
 954 }
 955                                         /* Reverse traversal. */
 956 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
 957         np-> ...
 958                                         /* TailQ Deletion. */
 959 while (!TAILQ_EMPTY(&head)) {
 960         n1 = TAILQ_FIRST(&head);
 961         TAILQ_REMOVE(&head, n1, entries);
 962         free(n1);
 963 }
 964                                         /* Faster TailQ Deletion. */
 965 n1 = TAILQ_FIRST(&head);
 966 while (n1 != NULL) {
 967         n2 = TAILQ_NEXT(n1, entries);
 968         free(n1);
 969         n1 = n2;
 970 }
 971 TAILQ_INIT(&head);
 972 .Ed
 973 .Sh HISTORY
 974 The
 975 .Nm queue
 976 functions first appeared in
 977 .Bx 4.4 .