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