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