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