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