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