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