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