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