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