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