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