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