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