1.\" $OpenBSD: queue.3,v 1.66 2019/12/30 17:25:39 schwarze 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 2019 $ 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 intrusive singly-linked and 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 301All these lists and queues are intrusive: they link together user 302defined structures containing a field of type 303.Li SLIST_ENTRY , 304.Li LIST_ENTRY , 305.Li SIMPLEQ_ENTRY , 306or 307.Li TAILQ_ENTRY . 308In the macro definitions, 309.Fa TYPE 310is the name tag of the user defined structure and 311.Fa FIELDNAME 312is the name of the 313.Li *_ENTRY 314field. 315If an instance of the user defined structure needs to be a member of 316multiple lists at the same time, the structure requires multiple 317.Li *_ENTRY 318fields, one for each list. 319.Pp 320The argument 321.Fa HEADNAME 322is the name tag of a user defined structure that must be declared 323using the macros 324.Fn SLIST_HEAD , 325.Fn LIST_HEAD , 326.Fn SIMPLEQ_HEAD , 327or 328.Fn TAILQ_HEAD . 329See the examples below for further explanation of how these macros are used. 330.Sh SINGLY-LINKED LISTS 331A singly-linked list is headed by a structure defined by the 332.Fn SLIST_HEAD 333macro. 334This structure contains a single pointer to the first element on the list. 335The elements are singly linked for minimum space and pointer manipulation 336overhead at the expense of O(n) removal for arbitrary elements. 337New elements can be added to the list after an existing element or 338at the head of the list. 339A 340.Fa SLIST_HEAD 341structure is declared as follows: 342.Bd -literal -offset indent 343SLIST_HEAD(HEADNAME, TYPE) head; 344.Ed 345.Pp 346where 347.Fa HEADNAME 348is the name of the structure to be defined, and struct 349.Fa TYPE 350is the type of the elements to be linked into the list. 351A pointer to the head of the list can later be declared as: 352.Bd -literal -offset indent 353struct HEADNAME *headp; 354.Ed 355.Pp 356(The names 357.Li head 358and 359.Li headp 360are user selectable.) 361.Pp 362The 363.Fa HEADNAME 364facility is often not used, leading to the following bizarre code: 365.Bd -literal -offset indent 366SLIST_HEAD(, TYPE) head, *headp; 367.Ed 368.Pp 369The 370.Fn SLIST_ENTRY 371macro declares a structure that connects the elements in the list. 372.Pp 373The 374.Fn SLIST_INIT 375macro initializes the list referenced by 376.Fa head . 377.Pp 378The list can also be initialized statically by using the 379.Fn SLIST_HEAD_INITIALIZER 380macro like this: 381.Bd -literal -offset indent 382SLIST_HEAD(HEADNAME, TYPE) head = SLIST_HEAD_INITIALIZER(head); 383.Ed 384.Pp 385The 386.Fn SLIST_INSERT_HEAD 387macro inserts the new element 388.Fa elm 389at the head of the list. 390.Pp 391The 392.Fn SLIST_INSERT_AFTER 393macro inserts the new element 394.Fa elm 395after the element 396.Fa listelm . 397.Pp 398The 399.Fn SLIST_REMOVE_HEAD 400macro removes the first element of the list pointed by 401.Fa head . 402.Pp 403The 404.Fn SLIST_REMOVE_AFTER 405macro removes the list element immediately following 406.Fa elm . 407.Pp 408The 409.Fn SLIST_REMOVE 410macro removes the element 411.Fa elm 412of the list pointed by 413.Fa head . 414.Pp 415The 416.Fn SLIST_FIRST 417and 418.Fn SLIST_NEXT 419macros can be used to traverse the list: 420.Bd -literal -offset indent 421for (np = SLIST_FIRST(&head); np != NULL; np = SLIST_NEXT(np, FIELDNAME)) 422.Ed 423.Pp 424Or, for simplicity, one can use the 425.Fn SLIST_FOREACH 426macro: 427.Bd -literal -offset indent 428SLIST_FOREACH(np, head, FIELDNAME) 429.Ed 430.Pp 431The macro 432.Fn SLIST_FOREACH_SAFE 433traverses the list referenced by head in a 434forward direction, assigning each element in turn to var. 435However, unlike 436.Fn SLIST_FOREACH 437it is permitted to remove var as well 438as free it from within the loop safely without interfering with the traversal. 439.Pp 440The 441.Fn SLIST_EMPTY 442macro should be used to check whether a simple list is empty. 443.Sh SINGLY-LINKED LIST EXAMPLE 444.Bd -literal 445SLIST_HEAD(listhead, entry) head; 446struct entry { 447 ... 448 SLIST_ENTRY(entry) entries; /* Simple list. */ 449 ... 450} *n1, *n2, *np; 451 452SLIST_INIT(&head); /* Initialize simple list. */ 453 454n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 455SLIST_INSERT_HEAD(&head, n1, entries); 456 457n2 = malloc(sizeof(struct entry)); /* Insert after. */ 458SLIST_INSERT_AFTER(n1, n2, entries); 459 460SLIST_FOREACH(np, &head, entries) /* Forward traversal. */ 461 np-> ... 462 463while (!SLIST_EMPTY(&head)) { /* Delete. */ 464 n1 = SLIST_FIRST(&head); 465 SLIST_REMOVE_HEAD(&head, entries); 466 free(n1); 467} 468 469.Ed 470.Sh LISTS 471A list is headed by a structure defined by the 472.Fn LIST_HEAD 473macro. 474This structure contains a single pointer to the first element on the list. 475The elements are doubly linked so that an arbitrary element can be 476removed without traversing the list. 477New elements can be added to the list after an existing element, 478before an existing element, or at the head of the list. 479A 480.Fa LIST_HEAD 481structure is declared as follows: 482.Bd -literal -offset indent 483LIST_HEAD(HEADNAME, TYPE) head; 484.Ed 485.Pp 486where 487.Fa HEADNAME 488is the name of the structure to be defined, and struct 489.Fa TYPE 490is the type of the elements to be linked into the list. 491A pointer to the head of the list can later be declared as: 492.Bd -literal -offset indent 493struct HEADNAME *headp; 494.Ed 495.Pp 496(The names 497.Li head 498and 499.Li headp 500are user selectable.) 501.Pp 502The 503.Fa HEADNAME 504facility is often not used, leading to the following bizarre code: 505.Bd -literal -offset indent 506LIST_HEAD(, TYPE) head, *headp; 507.Ed 508.Pp 509The 510.Fn LIST_ENTRY 511macro declares a structure that connects the elements in the list. 512.Pp 513The 514.Fn LIST_INIT 515macro initializes the list referenced by 516.Fa head . 517.Pp 518The list can also be initialized statically by using the 519.Fn LIST_HEAD_INITIALIZER 520macro like this: 521.Bd -literal -offset indent 522LIST_HEAD(HEADNAME, TYPE) head = LIST_HEAD_INITIALIZER(head); 523.Ed 524.Pp 525The 526.Fn LIST_INSERT_HEAD 527macro inserts the new element 528.Fa elm 529at the head of the list. 530.Pp 531The 532.Fn LIST_INSERT_AFTER 533macro inserts the new element 534.Fa elm 535after the element 536.Fa listelm . 537.Pp 538The 539.Fn LIST_INSERT_BEFORE 540macro inserts the new element 541.Fa elm 542before the element 543.Fa listelm . 544.Pp 545The 546.Fn LIST_REMOVE 547macro removes the element 548.Fa elm 549from the list. 550.Pp 551The 552.Fn LIST_REPLACE 553macro replaces the list element 554.Fa elm 555with the new element 556.Fa elm2 . 557.Pp 558The 559.Fn LIST_FIRST 560and 561.Fn LIST_NEXT 562macros can be used to traverse the list: 563.Bd -literal -offset indent 564for (np = LIST_FIRST(&head); np != NULL; np = LIST_NEXT(np, FIELDNAME)) 565.Ed 566.Pp 567Or, for simplicity, one can use the 568.Fn LIST_FOREACH 569macro: 570.Bd -literal -offset indent 571LIST_FOREACH(np, head, FIELDNAME) 572.Ed 573.Pp 574The macro 575.Fn LIST_FOREACH_SAFE 576traverses the list referenced by head in a 577forward direction, assigning each element in turn to var. 578However, unlike 579.Fn LIST_FOREACH 580it is permitted to remove var as well 581as free it from within the loop safely without interfering with the traversal. 582.Pp 583The 584.Fn LIST_EMPTY 585macro should be used to check whether a list is empty. 586.Sh LIST EXAMPLE 587.Bd -literal 588LIST_HEAD(listhead, entry) head; 589struct entry { 590 ... 591 LIST_ENTRY(entry) entries; /* List. */ 592 ... 593} *n1, *n2, *np; 594 595LIST_INIT(&head); /* Initialize list. */ 596 597n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 598LIST_INSERT_HEAD(&head, n1, entries); 599 600n2 = malloc(sizeof(struct entry)); /* Insert after. */ 601LIST_INSERT_AFTER(n1, n2, entries); 602 603n2 = malloc(sizeof(struct entry)); /* Insert before. */ 604LIST_INSERT_BEFORE(n1, n2, entries); 605 /* Forward traversal. */ 606LIST_FOREACH(np, &head, entries) 607 np-> ... 608 609while (!LIST_EMPTY(&head)) { /* Delete. */ 610 n1 = LIST_FIRST(&head); 611 LIST_REMOVE(n1, entries); 612 free(n1); 613} 614.Ed 615.Sh SIMPLE QUEUES 616A simple queue is headed by a structure defined by the 617.Fn SIMPLEQ_HEAD 618macro. 619This structure contains a pair of pointers, one to the first element in the 620simple queue and the other to the last element in the simple queue. 621The elements are singly linked. 622New elements can be added to the queue after an existing element, 623at the head of the queue or at the tail of the queue. 624A 625.Fa SIMPLEQ_HEAD 626structure is declared as follows: 627.Bd -literal -offset indent 628SIMPLEQ_HEAD(HEADNAME, TYPE) head; 629.Ed 630.Pp 631where 632.Fa HEADNAME 633is the name of the structure to be defined, and struct 634.Fa TYPE 635is the type of the elements to be linked into the queue. 636A pointer to the head of the queue can later be declared as: 637.Bd -literal -offset indent 638struct HEADNAME *headp; 639.Ed 640.Pp 641(The names 642.Li head 643and 644.Li headp 645are user selectable.) 646.Pp 647The 648.Fn SIMPLEQ_ENTRY 649macro declares a structure that connects the elements in 650the queue. 651.Pp 652The 653.Fn SIMPLEQ_INIT 654macro initializes the queue referenced by 655.Fa head . 656.Pp 657The queue can also be initialized statically by using the 658.Fn SIMPLEQ_HEAD_INITIALIZER 659macro like this: 660.Bd -literal -offset indent 661SIMPLEQ_HEAD(HEADNAME, TYPE) head = SIMPLEQ_HEAD_INITIALIZER(head); 662.Ed 663.Pp 664The 665.Fn SIMPLEQ_INSERT_AFTER 666macro inserts the new element 667.Fa elm 668after the element 669.Fa listelm . 670.Pp 671The 672.Fn SIMPLEQ_INSERT_HEAD 673macro inserts the new element 674.Fa elm 675at the head of the queue. 676.Pp 677The 678.Fn SIMPLEQ_INSERT_TAIL 679macro inserts the new element 680.Fa elm 681at the end of the queue. 682.Pp 683The 684.Fn SIMPLEQ_REMOVE_AFTER 685macro removes the queue element immediately following 686.Fa elm . 687.Pp 688The 689.Fn SIMPLEQ_REMOVE_HEAD 690macro removes the first element 691from the queue. 692.Pp 693The 694.Fn SIMPLEQ_CONCAT 695macro concatenates all the elements of the queue referenced by 696.Fa head2 697to the end of the queue referenced by 698.Fa head1 , 699emptying 700.Fa head2 701in the process. 702This is more efficient than removing and inserting the individual elements 703as it does not actually traverse 704.Fa head2 . 705.Pp 706The 707.Fn SIMPLEQ_FIRST 708and 709.Fn SIMPLEQ_NEXT 710macros can be used to traverse the queue. 711The 712.Fn SIMPLEQ_FOREACH 713is used for queue traversal: 714.Bd -literal -offset indent 715SIMPLEQ_FOREACH(np, head, FIELDNAME) 716.Ed 717.Pp 718The macro 719.Fn SIMPLEQ_FOREACH_SAFE 720traverses the queue referenced by head in a 721forward direction, assigning each element in turn to var. 722However, unlike 723.Fn SIMPLEQ_FOREACH 724it is permitted to remove var as well 725as free it from within the loop safely without interfering with the traversal. 726.Pp 727The 728.Fn SIMPLEQ_EMPTY 729macro should be used to check whether a list is empty. 730.Sh SIMPLE QUEUE EXAMPLE 731.Bd -literal 732SIMPLEQ_HEAD(listhead, entry) head = SIMPLEQ_HEAD_INITIALIZER(head); 733struct entry { 734 ... 735 SIMPLEQ_ENTRY(entry) entries; /* Simple queue. */ 736 ... 737} *n1, *n2, *np; 738 739n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 740SIMPLEQ_INSERT_HEAD(&head, n1, entries); 741 742n2 = malloc(sizeof(struct entry)); /* Insert after. */ 743SIMPLEQ_INSERT_AFTER(&head, n1, n2, entries); 744 745n2 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 746SIMPLEQ_INSERT_TAIL(&head, n2, entries); 747 /* Forward traversal. */ 748SIMPLEQ_FOREACH(np, &head, entries) 749 np-> ... 750 /* Delete. */ 751while (!SIMPLEQ_EMPTY(&head)) { 752 n1 = SIMPLEQ_FIRST(&head); 753 SIMPLEQ_REMOVE_HEAD(&head, entries); 754 free(n1); 755} 756.Ed 757.Sh TAIL QUEUES 758A tail queue is headed by a structure defined by the 759.Fn TAILQ_HEAD 760macro. 761This structure contains a pair of pointers, 762one to the first element in the tail queue and the other to 763the last element in the tail queue. 764The elements are doubly linked so that an arbitrary element can be 765removed without traversing the tail queue. 766New elements can be added to the queue after an existing element, 767before an existing element, at the head of the queue, or at the end 768of the queue. 769A 770.Fa TAILQ_HEAD 771structure is declared as follows: 772.Bd -literal -offset indent 773TAILQ_HEAD(HEADNAME, TYPE) head; 774.Ed 775.Pp 776where 777.Fa HEADNAME 778is the name of the structure to be defined, and struct 779.Fa TYPE 780is the type of the elements to be linked into the tail queue. 781A pointer to the head of the tail queue can later be declared as: 782.Bd -literal -offset indent 783struct HEADNAME *headp; 784.Ed 785.Pp 786(The names 787.Li head 788and 789.Li headp 790are user selectable.) 791.Pp 792The 793.Fn TAILQ_ENTRY 794macro declares a structure that connects the elements in 795the tail queue. 796.Pp 797The 798.Fn TAILQ_INIT 799macro initializes the tail queue referenced by 800.Fa head . 801.Pp 802The tail queue can also be initialized statically by using the 803.Fn TAILQ_HEAD_INITIALIZER 804macro. 805.Pp 806The 807.Fn TAILQ_INSERT_HEAD 808macro inserts the new element 809.Fa elm 810at the head of the tail queue. 811.Pp 812The 813.Fn TAILQ_INSERT_TAIL 814macro inserts the new element 815.Fa elm 816at the end of the tail queue. 817.Pp 818The 819.Fn TAILQ_INSERT_AFTER 820macro inserts the new element 821.Fa elm 822after the element 823.Fa listelm . 824.Pp 825The 826.Fn TAILQ_INSERT_BEFORE 827macro inserts the new element 828.Fa elm 829before the element 830.Fa listelm . 831.Pp 832The 833.Fn TAILQ_REMOVE 834macro removes the element 835.Fa elm 836from the tail queue. 837.Pp 838The 839.Fn TAILQ_REPLACE 840macro replaces the list element 841.Fa elm 842with the new element 843.Fa elm2 . 844.Pp 845The 846.Fn TAILQ_CONCAT 847macro concatenates all the elements of the tail queue referenced by 848.Fa head2 849to the end of the tail queue referenced by 850.Fa head1 , 851emptying 852.Fa head2 853in the process. 854This is more efficient than removing and inserting the individual elements 855as it does not actually traverse 856.Fa head2 . 857.Pp 858.Fn TAILQ_FOREACH 859and 860.Fn TAILQ_FOREACH_REVERSE 861are used for traversing a tail queue. 862.Fn TAILQ_FOREACH 863starts at the first element and proceeds towards the last. 864.Fn TAILQ_FOREACH_REVERSE 865starts at the last element and proceeds towards the first. 866.Bd -literal -offset indent 867TAILQ_FOREACH(np, &head, FIELDNAME) 868TAILQ_FOREACH_REVERSE(np, &head, HEADNAME, FIELDNAME) 869.Ed 870.Pp 871The macros 872.Fn TAILQ_FOREACH_SAFE 873and 874.Fn TAILQ_FOREACH_REVERSE_SAFE 875traverse the list referenced by head 876in a forward or reverse direction respectively, 877assigning each element in turn to var. 878However, unlike their unsafe counterparts, 879they permit both the removal of var 880as well as freeing it from within the loop safely 881without interfering with the traversal. 882.Pp 883The 884.Fn TAILQ_FIRST , 885.Fn TAILQ_NEXT , 886.Fn TAILQ_LAST 887and 888.Fn TAILQ_PREV 889macros can be used to manually traverse a tail queue or an arbitrary part of 890one. 891.Pp 892The 893.Fn TAILQ_EMPTY 894macro should be used to check whether a tail queue is empty. 895.Sh TAIL QUEUE EXAMPLE 896.Bd -literal 897TAILQ_HEAD(tailhead, entry) head; 898struct entry { 899 ... 900 TAILQ_ENTRY(entry) entries; /* Tail queue. */ 901 ... 902} *n1, *n2, *np; 903 904TAILQ_INIT(&head); /* Initialize queue. */ 905 906n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 907TAILQ_INSERT_HEAD(&head, n1, entries); 908 909n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 910TAILQ_INSERT_TAIL(&head, n1, entries); 911 912n2 = malloc(sizeof(struct entry)); /* Insert after. */ 913TAILQ_INSERT_AFTER(&head, n1, n2, entries); 914 915n2 = malloc(sizeof(struct entry)); /* Insert before. */ 916TAILQ_INSERT_BEFORE(n1, n2, entries); 917 /* Forward traversal. */ 918TAILQ_FOREACH(np, &head, entries) 919 np-> ... 920 /* Manual forward traversal. */ 921for (np = n2; np != NULL; np = TAILQ_NEXT(np, entries)) 922 np-> ... 923 /* Delete. */ 924while ((np = TAILQ_FIRST(&head))) { 925 TAILQ_REMOVE(&head, np, entries); 926 free(np); 927} 928 929.Ed 930.Sh SEE ALSO 931.Xr tree 3 932.Sh NOTES 933It is an error to assume the next and previous fields are preserved 934after an element has been removed from a list or queue. 935Using any macro (except the various forms of insertion) on an element 936removed from a list or queue is incorrect. 937An example of erroneous usage is removing the same element twice. 938.Pp 939The 940.Fn SLIST_END , 941.Fn LIST_END , 942.Fn SIMPLEQ_END 943and 944.Fn TAILQ_END 945macros are deprecated; they provided symmetry with the historical 946.Fn CIRCLEQ_END 947and just expand to 948.Dv NULL . 949.Pp 950Trying to free a list in the following way is a common error: 951.Bd -literal -offset indent 952LIST_FOREACH(var, head, entry) 953 free(var); 954free(head); 955.Ed 956.Pp 957Since 958.Va var 959is free'd, the FOREACH macros refer to a pointer that may have been 960reallocated already. 961A similar situation occurs when the current element is deleted 962from the list. 963In cases like these the data structure's FOREACH_SAFE macros should be used 964instead. 965.Sh HISTORY 966The 967.Nm queue 968functions first appeared in 969.Bx 4.4 . 970The historical circle queue macros were deprecated in 971.Ox 5.5 . 972