1.\" $OpenBSD: queue.3,v 1.65 2017/01/12 16:28:49 mpi 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: January 12 2017 $ 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 TAILQ_ENTRY , 81.Nm TAILQ_HEAD , 82.Nm TAILQ_HEAD_INITIALIZER , 83.Nm TAILQ_FIRST , 84.Nm TAILQ_NEXT , 85.Nm TAILQ_LAST , 86.Nm TAILQ_PREV , 87.Nm TAILQ_EMPTY , 88.Nm TAILQ_FOREACH , 89.Nm TAILQ_FOREACH_SAFE , 90.Nm TAILQ_FOREACH_REVERSE , 91.Nm TAILQ_FOREACH_REVERSE_SAFE , 92.Nm TAILQ_INIT , 93.Nm TAILQ_INSERT_AFTER , 94.Nm TAILQ_INSERT_BEFORE , 95.Nm TAILQ_INSERT_HEAD , 96.Nm TAILQ_INSERT_TAIL , 97.Nm TAILQ_REMOVE , 98.Nm TAILQ_REPLACE , 99.Nm TAILQ_CONCAT 100.Nd implementations of singly-linked lists, doubly-linked lists, simple queues, and tail queues 101.Sh SYNOPSIS 102.In sys/queue.h 103.Pp 104.Fn SLIST_ENTRY "TYPE" 105.Fn SLIST_HEAD "HEADNAME" "TYPE" 106.Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head" 107.Ft "struct TYPE *" 108.Fn SLIST_FIRST "SLIST_HEAD *head" 109.Ft "struct TYPE *" 110.Fn SLIST_NEXT "struct TYPE *listelm" "FIELDNAME" 111.Ft int 112.Fn SLIST_EMPTY "SLIST_HEAD *head" 113.Fn SLIST_FOREACH "VARNAME" "SLIST_HEAD *head" "FIELDNAME" 114.Fn SLIST_FOREACH_SAFE "VARNAME" "SLIST_HEAD *head" "FIELDNAME" "TEMP_VARNAME" 115.Ft void 116.Fn SLIST_INIT "SLIST_HEAD *head" 117.Ft void 118.Fn SLIST_INSERT_AFTER "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME" 119.Ft void 120.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "struct TYPE *elm" "FIELDNAME" 121.Ft void 122.Fn SLIST_REMOVE_AFTER "struct TYPE *elm" "FIELDNAME" 123.Ft void 124.Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "FIELDNAME" 125.Ft void 126.Fn SLIST_REMOVE "SLIST_HEAD *head" "struct TYPE *elm" "TYPE" "FIELDNAME" 127.Pp 128.Fn LIST_ENTRY "TYPE" 129.Fn LIST_HEAD "HEADNAME" "TYPE" 130.Fn LIST_HEAD_INITIALIZER "LIST_HEAD head" 131.Ft "struct TYPE *" 132.Fn LIST_FIRST "LIST_HEAD *head" 133.Ft "struct TYPE *" 134.Fn LIST_NEXT "struct TYPE *listelm" "FIELDNAME" 135.Ft int 136.Fn LIST_EMPTY "LIST_HEAD *head" 137.Fn LIST_FOREACH "VARNAME" "LIST_HEAD *head" "FIELDNAME" 138.Fn LIST_FOREACH_SAFE "VARNAME" "LIST_HEAD *head" "FIELDNAME" "TEMP_VARNAME" 139.Ft void 140.Fn LIST_INIT "LIST_HEAD *head" 141.Ft void 142.Fn LIST_INSERT_AFTER "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME" 143.Ft void 144.Fn LIST_INSERT_BEFORE "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME" 145.Ft void 146.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "struct TYPE *elm" "FIELDNAME" 147.Ft void 148.Fn LIST_REMOVE "struct TYPE *elm" "FIELDNAME" 149.Ft void 150.Fn LIST_REPLACE "struct TYPE *elm" "struct TYPE *elm2" "FIELDNAME" 151.Pp 152.Fn SIMPLEQ_ENTRY "TYPE" 153.Fn SIMPLEQ_HEAD "HEADNAME" "TYPE" 154.Fn SIMPLEQ_HEAD_INITIALIZER "SIMPLEQ_HEAD head" 155.Ft "struct TYPE *" 156.Fn SIMPLEQ_FIRST "SIMPLEQ_HEAD *head" 157.Ft "struct TYPE *" 158.Fn SIMPLEQ_NEXT "struct TYPE *listelm" "FIELDNAME" 159.Ft int 160.Fn SIMPLEQ_EMPTY "SIMPLEQ_HEAD *head" 161.Fn SIMPLEQ_FOREACH "VARNAME" "SIMPLEQ_HEAD *head" "FIELDNAME" 162.Fn SIMPLEQ_FOREACH_SAFE "VARNAME" "SIMPLEQ_HEAD *head" "FIELDNAME" "TEMP_VARNAME" 163.Ft void 164.Fn SIMPLEQ_INIT "SIMPLEQ_HEAD *head" 165.Ft void 166.Fn SIMPLEQ_INSERT_AFTER "SIMPLEQ_HEAD *head" "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME" 167.Ft void 168.Fn SIMPLEQ_INSERT_HEAD "SIMPLEQ_HEAD *head" "struct TYPE *elm" "FIELDNAME" 169.Ft void 170.Fn SIMPLEQ_INSERT_TAIL "SIMPLEQ_HEAD *head" "struct TYPE *elm" "FIELDNAME" 171.Ft void 172.Fn SIMPLEQ_REMOVE_AFTER "SIMPLEQ_HEAD *head" "struct TYPE *elm" "FIELDNAME" 173.Ft void 174.Fn SIMPLEQ_REMOVE_HEAD "SIMPLEQ_HEAD *head" "FIELDNAME" 175.Fn SIMPLEQ_CONCAT "SIMPLEQ_HEAD *head1" "SIMPLEQ_HEAD *head2" 176.Pp 177.Fn TAILQ_ENTRY "TYPE" 178.Fn TAILQ_HEAD "HEADNAME" "TYPE" 179.Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head" 180.Ft "struct TYPE *" 181.Fn TAILQ_FIRST "TAILQ_HEAD *head" 182.Ft "struct TYPE *" 183.Fn TAILQ_NEXT "struct TYPE *listelm" "FIELDNAME" 184.Ft "struct TYPE *" 185.Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME" 186.Ft "struct TYPE *" 187.Fn TAILQ_PREV "struct TYPE *listelm" "HEADNAME" "FIELDNAME" 188.Ft int 189.Fn TAILQ_EMPTY "TAILQ_HEAD *head" 190.Fn TAILQ_FOREACH "VARNAME" "TAILQ_HEAD *head" "FIELDNAME" 191.Fn TAILQ_FOREACH_SAFE "VARNAME" "TAILQ_HEAD *head" "FIELDNAME" "TEMP_VARNAME" 192.Fn TAILQ_FOREACH_REVERSE "VARNAME" "TAILQ_HEAD *head" "HEADNAME" "FIELDNAME" 193.Fn TAILQ_FOREACH_REVERSE_SAFE "VARNAME" "TAILQ_HEAD *head" "HEADNAME" "FIELDNAME" "TEMP_VARNAME" 194.Ft void 195.Fn TAILQ_INIT "TAILQ_HEAD *head" 196.Ft void 197.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME" 198.Ft void 199.Fn TAILQ_INSERT_BEFORE "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME" 200.Ft void 201.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "struct TYPE *elm" "FIELDNAME" 202.Ft void 203.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "struct TYPE *elm" "FIELDNAME" 204.Ft void 205.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "struct TYPE *elm" "FIELDNAME" 206.Ft void 207.Fn TAILQ_REPLACE "TAILQ_HEAD *head" "struct TYPE *elm" "struct TYPE *elm2" "FIELDNAME" 208.Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "FIELDNAME" 209.Sh DESCRIPTION 210These macros define and operate on four types of data structures: 211singly-linked lists, simple queues, lists, and tail queues. 212All four structures support the following functionality: 213.Pp 214.Bl -enum -compact -offset indent 215.It 216Insertion of a new entry at the head of the list. 217.It 218Insertion of a new entry after any element in the list. 219.It 220Removal of an entry from the head of the list. 221.It 222Forward traversal through the list. 223.El 224.Pp 225Singly-linked lists are the simplest of the four data structures 226and support only the above functionality. 227Singly-linked lists are ideal for applications with large datasets 228and few or no removals, or for implementing a LIFO queue. 229.Pp 230Simple queues add the following functionality: 231.Pp 232.Bl -enum -compact -offset indent 233.It 234Entries can be added at the end of a list. 235.El 236.Pp 237However: 238.Pp 239.Bl -enum -compact -offset indent 240.It 241All list insertions must specify the head of the list. 242.It 243Each head entry requires two pointers rather than one. 244.It 245Code size is about 15% greater and operations run about 20% slower 246than singly-linked lists. 247.El 248.Pp 249Simple queues are ideal for applications with large datasets and 250few or no removals, or for implementing a FIFO queue. 251.Pp 252All doubly linked types of data structures (lists and tail queues) 253additionally allow: 254.Pp 255.Bl -enum -compact -offset indent 256.It 257Insertion of a new entry before any element in the list. 258.It 259Removal of any entry in the list. 260.El 261.Pp 262However: 263.Pp 264.Bl -enum -compact -offset indent 265.It 266Each element requires two pointers rather than one. 267.It 268Code size and execution time of operations (except for removal) is about 269twice that of the singly-linked data-structures. 270.El 271.Pp 272Lists are the simplest of the doubly linked data structures and support 273only the above functionality over singly-linked lists. 274.Pp 275Tail queues add the following functionality: 276.Pp 277.Bl -enum -compact -offset indent 278.It 279Entries can be added at the end of a list. 280.It 281They may be traversed backwards, at a cost. 282.El 283.Pp 284However: 285.Pp 286.Bl -enum -compact -offset indent 287.It 288All list insertions and removals must specify the head of the list. 289.It 290Each head entry requires two pointers rather than one. 291.It 292Code size is about 15% greater and operations run about 20% slower 293than singly-linked lists. 294.El 295.Pp 296An additional type of data structure, circular queues, violated the C 297language aliasing rules and were miscompiled as a result. 298All code using them should be converted to another structure; 299tail queues are usually the easiest to convert to. 300.Pp 301In the macro definitions, 302.Fa TYPE 303is the name tag of a user defined structure that must contain a field of type 304.Li SLIST_ENTRY , 305.Li LIST_ENTRY , 306.Li SIMPLEQ_ENTRY , 307or 308.Li TAILQ_ENTRY , 309named 310.Fa FIELDNAME . 311The argument 312.Fa HEADNAME 313is the name tag of a user defined structure that must be declared 314using the macros 315.Fn SLIST_HEAD , 316.Fn LIST_HEAD , 317.Fn SIMPLEQ_HEAD , 318or 319.Fn TAILQ_HEAD . 320See the examples below for further explanation of how these macros are used. 321.Sh SINGLY-LINKED LISTS 322A singly-linked list is headed by a structure defined by the 323.Fn SLIST_HEAD 324macro. 325This structure contains a single pointer to the first element on the list. 326The elements are singly linked for minimum space and pointer manipulation 327overhead at the expense of O(n) removal for arbitrary elements. 328New elements can be added to the list after an existing element or 329at the head of the list. 330A 331.Fa SLIST_HEAD 332structure is declared as follows: 333.Bd -literal -offset indent 334SLIST_HEAD(HEADNAME, TYPE) head; 335.Ed 336.Pp 337where 338.Fa HEADNAME 339is the name of the structure to be defined, and struct 340.Fa TYPE 341is the type of the elements to be linked into the list. 342A pointer to the head of the list can later be declared as: 343.Bd -literal -offset indent 344struct HEADNAME *headp; 345.Ed 346.Pp 347(The names 348.Li head 349and 350.Li headp 351are user selectable.) 352.Pp 353The 354.Fa HEADNAME 355facility is often not used, leading to the following bizarre code: 356.Bd -literal -offset indent 357SLIST_HEAD(, TYPE) head, *headp; 358.Ed 359.Pp 360The 361.Fn SLIST_ENTRY 362macro declares a structure that connects the elements in the list. 363.Pp 364The 365.Fn SLIST_INIT 366macro initializes the list referenced by 367.Fa head . 368.Pp 369The list can also be initialized statically by using the 370.Fn SLIST_HEAD_INITIALIZER 371macro like this: 372.Bd -literal -offset indent 373SLIST_HEAD(HEADNAME, TYPE) head = SLIST_HEAD_INITIALIZER(head); 374.Ed 375.Pp 376The 377.Fn SLIST_INSERT_HEAD 378macro inserts the new element 379.Fa elm 380at the head of the list. 381.Pp 382The 383.Fn SLIST_INSERT_AFTER 384macro inserts the new element 385.Fa elm 386after the element 387.Fa listelm . 388.Pp 389The 390.Fn SLIST_REMOVE_HEAD 391macro removes the first element of the list pointed by 392.Fa head . 393.Pp 394The 395.Fn SLIST_REMOVE_AFTER 396macro removes the list element immediately following 397.Fa elm . 398.Pp 399The 400.Fn SLIST_REMOVE 401macro removes the element 402.Fa elm 403of the list pointed by 404.Fa head . 405.Pp 406The 407.Fn SLIST_FIRST 408and 409.Fn SLIST_NEXT 410macros can be used to traverse the list: 411.Bd -literal -offset indent 412for (np = SLIST_FIRST(&head); np != NULL; np = SLIST_NEXT(np, FIELDNAME)) 413.Ed 414.Pp 415Or, for simplicity, one can use the 416.Fn SLIST_FOREACH 417macro: 418.Bd -literal -offset indent 419SLIST_FOREACH(np, head, FIELDNAME) 420.Ed 421.Pp 422The macro 423.Fn SLIST_FOREACH_SAFE 424traverses the list referenced by head in a 425forward direction, assigning each element in turn to var. 426However, unlike 427.Fn SLIST_FOREACH 428it is permitted to remove var as well 429as free it from within the loop safely without interfering with the traversal. 430.Pp 431The 432.Fn SLIST_EMPTY 433macro should be used to check whether a simple list is empty. 434.Sh SINGLY-LINKED LIST EXAMPLE 435.Bd -literal 436SLIST_HEAD(listhead, entry) head; 437struct entry { 438 ... 439 SLIST_ENTRY(entry) entries; /* Simple list. */ 440 ... 441} *n1, *n2, *np; 442 443SLIST_INIT(&head); /* Initialize simple list. */ 444 445n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 446SLIST_INSERT_HEAD(&head, n1, entries); 447 448n2 = malloc(sizeof(struct entry)); /* Insert after. */ 449SLIST_INSERT_AFTER(n1, n2, entries); 450 451SLIST_FOREACH(np, &head, entries) /* Forward traversal. */ 452 np-> ... 453 454while (!SLIST_EMPTY(&head)) { /* Delete. */ 455 n1 = SLIST_FIRST(&head); 456 SLIST_REMOVE_HEAD(&head, entries); 457 free(n1); 458} 459 460.Ed 461.Sh LISTS 462A list is headed by a structure defined by the 463.Fn LIST_HEAD 464macro. 465This structure contains a single pointer to the first element on the list. 466The elements are doubly linked so that an arbitrary element can be 467removed without traversing the list. 468New elements can be added to the list after an existing element, 469before an existing element, or at the head of the list. 470A 471.Fa LIST_HEAD 472structure is declared as follows: 473.Bd -literal -offset indent 474LIST_HEAD(HEADNAME, TYPE) head; 475.Ed 476.Pp 477where 478.Fa HEADNAME 479is the name of the structure to be defined, and struct 480.Fa TYPE 481is the type of the elements to be linked into the list. 482A pointer to the head of the list can later be declared as: 483.Bd -literal -offset indent 484struct HEADNAME *headp; 485.Ed 486.Pp 487(The names 488.Li head 489and 490.Li headp 491are user selectable.) 492.Pp 493The 494.Fa HEADNAME 495facility is often not used, leading to the following bizarre code: 496.Bd -literal -offset indent 497LIST_HEAD(, TYPE) head, *headp; 498.Ed 499.Pp 500The 501.Fn LIST_ENTRY 502macro declares a structure that connects the elements in the list. 503.Pp 504The 505.Fn LIST_INIT 506macro initializes the list referenced by 507.Fa head . 508.Pp 509The list can also be initialized statically by using the 510.Fn LIST_HEAD_INITIALIZER 511macro like this: 512.Bd -literal -offset indent 513LIST_HEAD(HEADNAME, TYPE) head = LIST_HEAD_INITIALIZER(head); 514.Ed 515.Pp 516The 517.Fn LIST_INSERT_HEAD 518macro inserts the new element 519.Fa elm 520at the head of the list. 521.Pp 522The 523.Fn LIST_INSERT_AFTER 524macro inserts the new element 525.Fa elm 526after the element 527.Fa listelm . 528.Pp 529The 530.Fn LIST_INSERT_BEFORE 531macro inserts the new element 532.Fa elm 533before the element 534.Fa listelm . 535.Pp 536The 537.Fn LIST_REMOVE 538macro removes the element 539.Fa elm 540from the list. 541.Pp 542The 543.Fn LIST_REPLACE 544macro replaces the list element 545.Fa elm 546with the new element 547.Fa elm2 . 548.Pp 549The 550.Fn LIST_FIRST 551and 552.Fn LIST_NEXT 553macros can be used to traverse the list: 554.Bd -literal -offset indent 555for (np = LIST_FIRST(&head); np != NULL; np = LIST_NEXT(np, FIELDNAME)) 556.Ed 557.Pp 558Or, for simplicity, one can use the 559.Fn LIST_FOREACH 560macro: 561.Bd -literal -offset indent 562LIST_FOREACH(np, head, FIELDNAME) 563.Ed 564.Pp 565The macro 566.Fn LIST_FOREACH_SAFE 567traverses the list referenced by head in a 568forward direction, assigning each element in turn to var. 569However, unlike 570.Fn LIST_FOREACH 571it is permitted to remove var as well 572as free it from within the loop safely without interfering with the traversal. 573.Pp 574The 575.Fn LIST_EMPTY 576macro should be used to check whether a list is empty. 577.Sh LIST EXAMPLE 578.Bd -literal 579LIST_HEAD(listhead, entry) head; 580struct entry { 581 ... 582 LIST_ENTRY(entry) entries; /* List. */ 583 ... 584} *n1, *n2, *np; 585 586LIST_INIT(&head); /* Initialize list. */ 587 588n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 589LIST_INSERT_HEAD(&head, n1, entries); 590 591n2 = malloc(sizeof(struct entry)); /* Insert after. */ 592LIST_INSERT_AFTER(n1, n2, entries); 593 594n2 = malloc(sizeof(struct entry)); /* Insert before. */ 595LIST_INSERT_BEFORE(n1, n2, entries); 596 /* Forward traversal. */ 597LIST_FOREACH(np, &head, entries) 598 np-> ... 599 600while (!LIST_EMPTY(&head)) { /* Delete. */ 601 n1 = LIST_FIRST(&head); 602 LIST_REMOVE(n1, entries); 603 free(n1); 604} 605.Ed 606.Sh SIMPLE QUEUES 607A simple queue is headed by a structure defined by the 608.Fn SIMPLEQ_HEAD 609macro. 610This structure contains a pair of pointers, one to the first element in the 611simple queue and the other to the last element in the simple queue. 612The elements are singly linked. 613New elements can be added to the queue after an existing element, 614at the head of the queue or at the tail of the queue. 615A 616.Fa SIMPLEQ_HEAD 617structure is declared as follows: 618.Bd -literal -offset indent 619SIMPLEQ_HEAD(HEADNAME, TYPE) head; 620.Ed 621.Pp 622where 623.Fa HEADNAME 624is the name of the structure to be defined, and struct 625.Fa TYPE 626is the type of the elements to be linked into the queue. 627A pointer to the head of the queue can later be declared as: 628.Bd -literal -offset indent 629struct HEADNAME *headp; 630.Ed 631.Pp 632(The names 633.Li head 634and 635.Li headp 636are user selectable.) 637.Pp 638The 639.Fn SIMPLEQ_ENTRY 640macro declares a structure that connects the elements in 641the queue. 642.Pp 643The 644.Fn SIMPLEQ_INIT 645macro initializes the queue referenced by 646.Fa head . 647.Pp 648The queue can also be initialized statically by using the 649.Fn SIMPLEQ_HEAD_INITIALIZER 650macro like this: 651.Bd -literal -offset indent 652SIMPLEQ_HEAD(HEADNAME, TYPE) head = SIMPLEQ_HEAD_INITIALIZER(head); 653.Ed 654.Pp 655The 656.Fn SIMPLEQ_INSERT_AFTER 657macro inserts the new element 658.Fa elm 659after the element 660.Fa listelm . 661.Pp 662The 663.Fn SIMPLEQ_INSERT_HEAD 664macro inserts the new element 665.Fa elm 666at the head of the queue. 667.Pp 668The 669.Fn SIMPLEQ_INSERT_TAIL 670macro inserts the new element 671.Fa elm 672at the end of the queue. 673.Pp 674The 675.Fn SIMPLEQ_REMOVE_AFTER 676macro removes the queue element immediately following 677.Fa elm . 678.Pp 679The 680.Fn SIMPLEQ_REMOVE_HEAD 681macro removes the first element 682from the queue. 683.Pp 684The 685.Fn SIMPLEQ_CONCAT 686macro concatenates all the elements of the queue referenced by 687.Fa head2 688to the end of the queue referenced by 689.Fa head1 , 690emptying 691.Fa head2 692in the process. 693This is more efficient than removing and inserting the individual elements 694as it does not actually traverse 695.Fa head2 . 696.Pp 697The 698.Fn SIMPLEQ_FIRST 699and 700.Fn SIMPLEQ_NEXT 701macros can be used to traverse the queue. 702The 703.Fn SIMPLEQ_FOREACH 704is used for queue traversal: 705.Bd -literal -offset indent 706SIMPLEQ_FOREACH(np, head, FIELDNAME) 707.Ed 708.Pp 709The macro 710.Fn SIMPLEQ_FOREACH_SAFE 711traverses the queue referenced by head in a 712forward direction, assigning each element in turn to var. 713However, unlike 714.Fn SIMPLEQ_FOREACH 715it is permitted to remove var as well 716as free it from within the loop safely without interfering with the traversal. 717.Pp 718The 719.Fn SIMPLEQ_EMPTY 720macro should be used to check whether a list is empty. 721.Sh SIMPLE QUEUE EXAMPLE 722.Bd -literal 723SIMPLEQ_HEAD(listhead, entry) head = SIMPLEQ_HEAD_INITIALIZER(head); 724struct entry { 725 ... 726 SIMPLEQ_ENTRY(entry) entries; /* Simple queue. */ 727 ... 728} *n1, *n2, *np; 729 730n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 731SIMPLEQ_INSERT_HEAD(&head, n1, entries); 732 733n2 = malloc(sizeof(struct entry)); /* Insert after. */ 734SIMPLEQ_INSERT_AFTER(&head, n1, n2, entries); 735 736n2 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 737SIMPLEQ_INSERT_TAIL(&head, n2, entries); 738 /* Forward traversal. */ 739SIMPLEQ_FOREACH(np, &head, entries) 740 np-> ... 741 /* Delete. */ 742while (!SIMPLEQ_EMPTY(&head)) { 743 n1 = SIMPLEQ_FIRST(&head); 744 SIMPLEQ_REMOVE_HEAD(&head, entries); 745 free(n1); 746} 747.Ed 748.Sh TAIL QUEUES 749A tail queue is headed by a structure defined by the 750.Fn TAILQ_HEAD 751macro. 752This structure contains a pair of pointers, 753one to the first element in the tail queue and the other to 754the last element in the tail queue. 755The elements are doubly linked so that an arbitrary element can be 756removed without traversing the tail queue. 757New elements can be added to the queue after an existing element, 758before an existing element, at the head of the queue, or at the end 759of the queue. 760A 761.Fa TAILQ_HEAD 762structure is declared as follows: 763.Bd -literal -offset indent 764TAILQ_HEAD(HEADNAME, TYPE) head; 765.Ed 766.Pp 767where 768.Fa HEADNAME 769is the name of the structure to be defined, and struct 770.Fa TYPE 771is the type of the elements to be linked into the tail queue. 772A pointer to the head of the tail queue can later be declared as: 773.Bd -literal -offset indent 774struct HEADNAME *headp; 775.Ed 776.Pp 777(The names 778.Li head 779and 780.Li headp 781are user selectable.) 782.Pp 783The 784.Fn TAILQ_ENTRY 785macro declares a structure that connects the elements in 786the tail queue. 787.Pp 788The 789.Fn TAILQ_INIT 790macro initializes the tail queue referenced by 791.Fa head . 792.Pp 793The tail queue can also be initialized statically by using the 794.Fn TAILQ_HEAD_INITIALIZER 795macro. 796.Pp 797The 798.Fn TAILQ_INSERT_HEAD 799macro inserts the new element 800.Fa elm 801at the head of the tail queue. 802.Pp 803The 804.Fn TAILQ_INSERT_TAIL 805macro inserts the new element 806.Fa elm 807at the end of the tail queue. 808.Pp 809The 810.Fn TAILQ_INSERT_AFTER 811macro inserts the new element 812.Fa elm 813after the element 814.Fa listelm . 815.Pp 816The 817.Fn TAILQ_INSERT_BEFORE 818macro inserts the new element 819.Fa elm 820before the element 821.Fa listelm . 822.Pp 823The 824.Fn TAILQ_REMOVE 825macro removes the element 826.Fa elm 827from the tail queue. 828.Pp 829The 830.Fn TAILQ_REPLACE 831macro replaces the list element 832.Fa elm 833with the new element 834.Fa elm2 . 835.Pp 836The 837.Fn TAILQ_CONCAT 838macro concatenates all the elements of the tail queue referenced by 839.Fa head2 840to the end of the tail queue referenced by 841.Fa head1 , 842emptying 843.Fa head2 844in the process. 845This is more efficient than removing and inserting the individual elements 846as it does not actually traverse 847.Fa head2 . 848.Pp 849.Fn TAILQ_FOREACH 850and 851.Fn TAILQ_FOREACH_REVERSE 852are used for traversing a tail queue. 853.Fn TAILQ_FOREACH 854starts at the first element and proceeds towards the last. 855.Fn TAILQ_FOREACH_REVERSE 856starts at the last element and proceeds towards the first. 857.Bd -literal -offset indent 858TAILQ_FOREACH(np, &head, FIELDNAME) 859TAILQ_FOREACH_REVERSE(np, &head, HEADNAME, FIELDNAME) 860.Ed 861.Pp 862The macros 863.Fn TAILQ_FOREACH_SAFE 864and 865.Fn TAILQ_FOREACH_REVERSE_SAFE 866traverse the list referenced by head 867in a forward or reverse direction respectively, 868assigning each element in turn to var. 869However, unlike their unsafe counterparts, 870they permit both the removal of var 871as well as freeing it from within the loop safely 872without interfering with the traversal. 873.Pp 874The 875.Fn TAILQ_FIRST , 876.Fn TAILQ_NEXT , 877.Fn TAILQ_LAST 878and 879.Fn TAILQ_PREV 880macros can be used to manually traverse a tail queue or an arbitrary part of 881one. 882.Pp 883The 884.Fn TAILQ_EMPTY 885macro should be used to check whether a tail queue is empty. 886.Sh TAIL QUEUE EXAMPLE 887.Bd -literal 888TAILQ_HEAD(tailhead, entry) head; 889struct entry { 890 ... 891 TAILQ_ENTRY(entry) entries; /* Tail queue. */ 892 ... 893} *n1, *n2, *np; 894 895TAILQ_INIT(&head); /* Initialize queue. */ 896 897n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 898TAILQ_INSERT_HEAD(&head, n1, entries); 899 900n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 901TAILQ_INSERT_TAIL(&head, n1, entries); 902 903n2 = malloc(sizeof(struct entry)); /* Insert after. */ 904TAILQ_INSERT_AFTER(&head, n1, n2, entries); 905 906n2 = malloc(sizeof(struct entry)); /* Insert before. */ 907TAILQ_INSERT_BEFORE(n1, n2, entries); 908 /* Forward traversal. */ 909TAILQ_FOREACH(np, &head, entries) 910 np-> ... 911 /* Manual forward traversal. */ 912for (np = n2; np != NULL; np = TAILQ_NEXT(np, entries)) 913 np-> ... 914 /* Delete. */ 915while ((np = TAILQ_FIRST(&head))) { 916 TAILQ_REMOVE(&head, np, entries); 917 free(np); 918} 919 920.Ed 921.Sh SEE ALSO 922.Xr tree 3 923.Sh NOTES 924It is an error to assume the next and previous fields are preserved 925after an element has been removed from a list or queue. 926Using any macro (except the various forms of insertion) on an element 927removed from a list or queue is incorrect. 928An example of erroneous usage is removing the same element twice. 929.Pp 930The 931.Fn SLIST_END , 932.Fn LIST_END , 933.Fn SIMPLEQ_END 934and 935.Fn TAILQ_END 936macros are deprecated; they provided symmetry with the historical 937.Fn CIRCLEQ_END 938and just expand to 939.Dv NULL . 940.Pp 941Trying to free a list in the following way is a common error: 942.Bd -literal -offset indent 943LIST_FOREACH(var, head, entry) 944 free(var); 945free(head); 946.Ed 947.Pp 948Since 949.Va var 950is free'd, the FOREACH macros refer to a pointer that may have been 951reallocated already. 952A similar situation occurs when the current element is deleted 953from the list. 954In cases like these the data structure's FOREACH_SAFE macros should be used 955instead. 956.Sh HISTORY 957The 958.Nm queue 959functions first appeared in 960.Bx 4.4 . 961The historical circle queue macros were deprecated in 962.Ox 5.5 . 963