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