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