1.\" $OpenBSD: queue.3,v 1.34 2004/04/08 16:08:21 henning 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 December 13, 1993 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_END , 43.Nm SLIST_EMPTY , 44.Nm SLIST_FOREACH , 45.Nm SLIST_FOREACH_PREVPTR , 46.Nm SLIST_INIT , 47.Nm SLIST_INSERT_AFTER , 48.Nm SLIST_INSERT_HEAD , 49.Nm SLIST_REMOVE_HEAD , 50.Nm SLIST_REMOVE_NEXT , 51.Nm SLIST_REMOVE , 52.Nm LIST_ENTRY , 53.Nm LIST_HEAD , 54.Nm LIST_HEAD_INITIALIZER , 55.Nm LIST_FIRST , 56.Nm LIST_NEXT , 57.Nm LIST_END , 58.Nm LIST_EMPTY , 59.Nm LIST_FOREACH , 60.Nm LIST_INIT , 61.Nm LIST_INSERT_AFTER , 62.Nm LIST_INSERT_BEFORE , 63.Nm LIST_INSERT_HEAD , 64.Nm LIST_REMOVE , 65.Nm LIST_REPLACE , 66.Nm SIMPLEQ_ENTRY , 67.Nm SIMPLEQ_HEAD , 68.Nm SIMPLEQ_HEAD_INITIALIZER , 69.Nm SIMPLEQ_FIRST , 70.Nm SIMPLEQ_NEXT , 71.Nm SIMPLEQ_END , 72.Nm SIMPLEQ_EMPTY , 73.Nm SIMPLEQ_FOREACH , 74.Nm SIMPLEQ_INIT , 75.Nm SIMPLEQ_INSERT_HEAD , 76.Nm SIMPLEQ_INSERT_TAIL , 77.Nm SIMPLEQ_INSERT_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_END , 85.Nm TAILQ_LAST , 86.Nm TAILQ_PREV , 87.Nm TAILQ_EMPTY , 88.Nm TAILQ_FOREACH , 89.Nm TAILQ_FOREACH_REVERSE , 90.Nm TAILQ_INIT , 91.Nm TAILQ_INSERT_AFTER , 92.Nm TAILQ_INSERT_BEFORE , 93.Nm TAILQ_INSERT_HEAD , 94.Nm TAILQ_INSERT_TAIL , 95.Nm TAILQ_REMOVE , 96.Nm CIRCLEQ_ENTRY , 97.Nm CIRCLEQ_HEAD , 98.Nm CIRCLEQ_HEAD_INITIALIZER , 99.Nm CIRCLEQ_FIRST , 100.Nm CIRCLEQ_LAST , 101.Nm CIRCLEQ_END , 102.Nm CIRCLEQ_NEXT , 103.Nm CIRCLEQ_PREV , 104.Nm CIRCLEQ_EMPTY , 105.Nm CIRCLEQ_FOREACH , 106.Nm CIRCLEQ_FOREACH_REVERSE , 107.Nm CIRCLEQ_INIT , 108.Nm CIRCLEQ_INSERT_AFTER , 109.Nm CIRCLEQ_INSERT_BEFORE , 110.Nm CIRCLEQ_INSERT_HEAD , 111.Nm CIRCLEQ_INSERT_TAIL , 112.Nm CIRCLEQ_REMOVE 113.Nd "implementations of singly-linked lists, doubly-linked lists, simple queues, tail queues, and circular queues" 114.Sh SYNOPSIS 115.Fd #include <sys/queue.h> 116.Pp 117.Fn SLIST_ENTRY "TYPE" 118.Fn SLIST_HEAD "HEADNAME" "TYPE" 119.Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head" 120.Ft "struct TYPE *" 121.Fn SLIST_FIRST "SLIST_HEAD *head" 122.Ft "struct TYPE *" 123.Fn SLIST_NEXT "struct TYPE *listelm" "SLIST_ENTRY NAME" 124.Ft "struct TYPE *" 125.Fn SLIST_END "SLIST_HEAD *head" 126.Ft "bool" 127.Fn SLIST_EMPTY "SLIST_HEAD *head" 128.Fn SLIST_FOREACH "VARNAME" "SLIST_HEAD *head" "SLIST_ENTRY NAME" 129.Fn SLIST_FOREACH_PREVPTR "VARNAME" "VARNAMEP" "SLIST_HEAD *head" "SLIST_ENTRY NAME" 130.Ft void 131.Fn SLIST_INIT "SLIST_HEAD *head" 132.Ft void 133.Fn SLIST_INSERT_AFTER "struct TYPE *listelm" "struct TYPE *elm" "SLIST_ENTRY NAME" 134.Ft void 135.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "struct TYPE *elm" "SLIST_ENTRY NAME" 136.Ft void 137.Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME" 138.Ft void 139.Fn SLIST_REMOVE_NEXT "SLIST_HEAD *head" "struct TYPE *elm" "SLIST_ENTRY NAME" 140.Ft void 141.Fn SLIST_REMOVE "SLIST_HEAD *head" "struct TYPE *elm" "TYPE" "SLIST_ENTRY NAME" 142.Pp 143.Fn LIST_ENTRY "TYPE" 144.Fn LIST_HEAD "HEADNAME" "TYPE" 145.Fn LIST_HEAD_INITIALIZER "LIST_HEAD head" 146.Ft "struct TYPE *" 147.Fn LIST_FIRST "LIST_HEAD *head" 148.Ft "struct TYPE *" 149.Fn LIST_NEXT "struct TYPE *listelm" "LIST_ENTRY NAME" 150.Ft "struct TYPE *" 151.Fn LIST_END "LIST_HEAD *head" 152.Ft "bool" 153.Fn LIST_EMPTY "LIST_HEAD *head" 154.Fn LIST_FOREACH "VARNAME" "LIST_HEAD *head" "LIST_ENTRY NAME" 155.Ft void 156.Fn LIST_INIT "LIST_HEAD *head" 157.Ft void 158.Fn LIST_INSERT_AFTER "struct TYPE *listelm" "struct TYPE *elm" "LIST_ENTRY NAME" 159.Ft void 160.Fn LIST_INSERT_BEFORE "struct TYPE *listelm" "struct TYPE *elm" "LIST_ENTRY NAME" 161.Ft void 162.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "struct TYPE *elm" "LIST_ENTRY NAME" 163.Ft void 164.Fn LIST_REMOVE "struct TYPE *elm" "LIST_ENTRY NAME" 165.Ft void 166.Fn LIST_REPLACE "struct TYPE *elm" "struct TYPE *elm2" "LIST_ENTRY NAME" 167.Pp 168.Fn SIMPLEQ_ENTRY "TYPE" 169.Fn SIMPLEQ_HEAD "HEADNAME" "TYPE" 170.Fn SIMPLEQ_HEAD_INITIALIZER "SIMPLEQ_HEAD head" 171.Ft "struct TYPE *" 172.Fn SIMPLEQ_FIRST "SIMPLEQ_HEAD *head" 173.Ft "struct TYPE *" 174.Fn SIMPLEQ_NEXT "struct TYPE *listelm" "SIMPLEQ_ENTRY NAME" 175.Ft "struct TYPE *" 176.Fn SIMPLEQ_END "SIMPLEQ_HEAD *head" 177.Ft void 178.Fn SIMPLEQ_INIT "SIMPLEQ_HEAD *head" 179.Ft void 180.Fn SIMPLEQ_INSERT_HEAD "SIMPLEQ_HEAD *head" "struct TYPE *elm" "SIMPLEQ_ENTRY NAME" 181.Ft void 182.Fn SIMPLEQ_INSERT_TAIL "SIMPLEQ_HEAD *head" "struct TYPE *elm" "SIMPLEQ_ENTRY NAME" 183.Ft void 184.Fn SIMPLEQ_INSERT_AFTER "struct TYPE *listelm" "struct TYPE *elm" "SIMPLEQ_ENTRY NAME" 185.Ft void 186.Fn SIMPLEQ_REMOVE_HEAD "SIMPLEQ_HEAD *head" "struct TYPE *elm" "SIMPLEQ_ENTRY NAME" 187.Pp 188.Fn TAILQ_ENTRY "TYPE" 189.Fn TAILQ_HEAD "HEADNAME" "TYPE" 190.Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head" 191.Ft "struct TYPE *" 192.Fn TAILQ_FIRST "TAILQ_HEAD *head" 193.Ft "struct TYPE *" 194.Fn TAILQ_NEXT "struct TYPE *listelm" "TAILQ_ENTRY NAME" 195.Ft "struct TYPE *" 196.Fn TAILQ_END "TAILQ_HEAD *head" 197.Ft "struct TYPE *" 198.Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME NAME" 199.Fn TAILQ_PREV "struct TYPE *listelm" "HEADNAME NAME" "TAILQ_ENTRY NAME" 200.Ft "bool" 201.Fn TAILQ_EMPTY "TAILQ_HEAD *head" 202.Fn TAILQ_FOREACH "VARNAME" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" 203.Fn TAILQ_FOREACH_REVERSE "VARNAME" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" 204.Ft void 205.Fn TAILQ_INIT "TAILQ_HEAD *head" 206.Ft void 207.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "struct TYPE *listelm" "struct TYPE *elm" "TAILQ_ENTRY NAME" 208.Ft void 209.Fn TAILQ_INSERT_BEFORE "struct TYPE *listelm" "struct TYPE *elm" "TAILQ_ENTRY NAME" 210.Ft void 211.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "struct TYPE *elm" "TAILQ_ENTRY NAME" 212.Ft void 213.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "struct TYPE *elm" "TAILQ_ENTRY NAME" 214.Ft void 215.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "struct TYPE *elm" "TAILQ_ENTRY NAME" 216.Pp 217.Fn CIRCLEQ_ENTRY "TYPE" 218.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE" 219.Fn CIRCLEQ_HEAD_INITIALIZER "CIRCLEQ_HEAD head" 220.Ft "struct TYPE *" 221.Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head" 222.Ft "struct TYPE *" 223.Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head" 224.Ft "struct TYPE *" 225.Fn CIRCLEQ_END "CIRCLEQ_HEAD *head" 226.Ft "struct TYPE *" 227.Fn CIRCLEQ_NEXT "struct TYPE *listelm" "CIRCLEQ_ENTRY NAME" 228.Ft "struct TYPE *" 229.Fn CIRCLEQ_PREV "struct TYPE *listelm" "CIRCLEQ_ENTRY NAME" 230.Ft "bool" 231.Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head" 232.Fn CIRCLEQ_FOREACH "VARNAME" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME" 233.Fn CIRCLEQ_FOREACH_REVERSE "VARNAME" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME" 234.Ft void 235.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head" 236.Ft void 237.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "struct TYPE *listelm" "struct TYPE *elm" "CIRCLEQ_ENTRY NAME" 238.Ft void 239.Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "struct TYPE *listelm" "struct TYPE *elm" "CIRCLEQ_ENTRY NAME" 240.Ft void 241.Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "struct TYPE *elm" "CIRCLEQ_ENTRY NAME" 242.Ft void 243.Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "struct TYPE *elm" "CIRCLEQ_ENTRY NAME" 244.Ft void 245.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "struct TYPE *elm" "CIRCLEQ_ENTRY NAME" 246.Sh DESCRIPTION 247These macros define and operate on five types of data structures: 248singly-linked lists, simple queues, lists, tail queues, and circular queues. 249All five structures support the following functionality: 250.Pp 251.Bl -enum -compact -offset indent 252.It 253Insertion of a new entry at the head of the list. 254.It 255Insertion of a new entry after any element in the list. 256.It 257Removal of an entry from the head of the list. 258.It 259Forward traversal through the list. 260.El 261.Pp 262Singly-linked lists are the simplest of the five data structures 263and support only the above functionality. 264Singly-linked lists are ideal for applications with large datasets 265and few or no removals, or for implementing a LIFO queue. 266.Pp 267Simple queues add the following functionality: 268.Pp 269.Bl -enum -compact -offset indent 270.It 271Entries can be added at the end of a list. 272.El 273.Pp 274However: 275.Pp 276.Bl -enum -compact -offset indent 277.It 278All list insertions must specify the head of the list. 279.It 280Each head entry requires two pointers rather than one. 281.It 282Code size is about 15% greater and operations run about 20% slower 283than singly-linked lists. 284.El 285.Pp 286Simple queues are ideal for applications with large datasets and 287few or no removals, or for implementing a FIFO queue. 288.Pp 289All doubly linked types of data structures (lists, tail queues, and circle 290queues) additionally allow: 291.Pp 292.Bl -enum -compact -offset indent 293.It 294Insertion of a new entry before any element in the list. 295.It 296Removal of any entry in the list. 297.El 298.Pp 299However: 300.Pp 301.Bl -enum -compact -offset indent 302.It 303Each element requires two pointers rather than one. 304.It 305Code size and execution time of operations (except for removal) is about 306twice that of the singly-linked data-structures. 307.El 308.Pp 309Lists are the simplest of the doubly linked data structures and support 310only the above functionality over singly-linked lists. 311.Pp 312Tail queues add the following functionality: 313.Pp 314.Bl -enum -compact -offset indent 315.It 316Entries can be added at the end of a list. 317.It 318They may be traversed backwards, at a cost. 319.El 320.Pp 321However: 322.Pp 323.Bl -enum -compact -offset indent 324.It 325All list insertions and removals must specify the head of the list. 326.It 327Each head entry requires two pointers rather than one. 328.It 329Code size is about 15% greater and operations run about 20% slower 330than singly-linked lists. 331.El 332.Pp 333Circular queues add the following functionality: 334.Pp 335.Bl -enum -compact -offset indent 336.It 337Entries can be added at the end of a list. 338.It 339They may be traversed backwards, from tail to head. 340.El 341.Pp 342However: 343.Pp 344.Bl -enum -compact -offset indent 345.It 346All list insertions and removals must specify the head of the list. 347.It 348Each head entry requires two pointers rather than one. 349.It 350The termination condition for traversal is more complex. 351.It 352Code size is about 40% greater and operations run about 45% slower than lists. 353.El 354.Pp 355In the macro definitions, 356.Fa TYPE 357is the name tag of a user defined structure that must contain a field of type 358.Li SLIST_ENTRY , 359.Li LIST_ENTRY , 360.Li SIMPLEQ_ENTRY , 361.Li TAILQ_ENTRY , 362or 363.Li CIRCLEQ_ENTRY , 364named 365.Fa NAME . 366The argument 367.Fa HEADNAME 368is the name tag of a user defined structure that must be declared 369using the macros 370.Fn SLIST_HEAD , 371.Fn LIST_HEAD , 372.Fn SIMPLEQ_HEAD , 373.Fn TAILQ_HEAD , 374or 375.Fn CIRCLEQ_HEAD . 376See the examples below for further explanation of how these macros are used. 377.Sh SINGLY_LINKED LISTS 378A singly-linked list is headed by a structure defined by the 379.Fn SLIST_HEAD 380macro. 381This structure contains a single pointer to the first element on the list. 382The elements are singly linked for minimum space and pointer manipulation 383overhead at the expense of O(n) removal for arbitrary elements. 384New elements can be added to the list after an existing element or 385at the head of the list. 386A 387.Fa SLIST_HEAD 388structure is declared as follows: 389.Bd -literal -offset indent 390SLIST_HEAD(HEADNAME, TYPE) head; 391.Ed 392.Pp 393where 394.Fa HEADNAME 395is the name of the structure to be defined, and struct 396.Fa TYPE 397is the type of the elements to be linked into the list. 398A pointer to the head of the list can later be declared as: 399.Bd -literal -offset indent 400struct HEADNAME *headp; 401.Ed 402.Pp 403(The names 404.Li head 405and 406.Li headp 407are user selectable.) 408.Pp 409The 410.Fa HEADNAME 411facility is often not used, leading to the following bizarre code: 412.Bd -literal -offset indent 413SLIST_HEAD(, TYPE) head, *headp; 414.Ed 415.Pp 416The 417.Fn SLIST_ENTRY 418macro declares a structure that connects the elements in the list. 419.Pp 420The 421.Fn SLIST_INIT 422macro initializes the list referenced by 423.Fa head . 424.Pp 425The list can also be initialized statically by using the 426.Fn SLIST_HEAD_INITIALIZER 427macro like this: 428.Bd -literal -offset indent 429SLIST_HEAD(HEADNAME, TYPE) head = SLIST_HEAD_INITIALIZER(head); 430.Ed 431.Pp 432The 433.Fn SLIST_INSERT_HEAD 434macro inserts the new element 435.Fa elm 436at the head of the list. 437.Pp 438The 439.Fn SLIST_INSERT_AFTER 440macro inserts the new element 441.Fa elm 442after the element 443.Fa listelm . 444.Pp 445The 446.Fn SLIST_REMOVE_HEAD 447macro removes the first element of the list pointed by 448.Fa head . 449.Pp 450The 451.Fn SLIST_REMOVE_NEXT 452macro removes the list element immediately following 453.Fa elm . 454.Pp 455The 456.Fn SLIST_REMOVE 457macro removes the element 458.Fa elm 459of the list pointed by 460.Fa head . 461.Pp 462The 463.Fn SLIST_FIRST 464and 465.Fn SLIST_NEXT 466macros can be used to traverse the list: 467.Bd -literal -offset indent 468for (np = SLIST_FIRST(&head); np != NULL; np = SLIST_NEXT(np, NAME)) 469.Ed 470.Pp 471Or, for simplicity, one can use the 472.Fn SLIST_FOREACH 473macro: 474.Bd -literal -offset indent 475SLIST_FOREACH(np, head, NAME) 476.Ed 477.Pp 478The 479.Fn SLIST_FOREACH_PREVPTR 480macro is similar to 481.Fn SLIST_FOREACH 482except that it stores a pointer to the previous element in 483.Fa VARNAMEP . 484This provides access to the previous element while traversing the list, 485as one would have with a doubly-linked list. 486.Pp 487The 488.Fn SLIST_EMPTY 489macro should be used to check whether a simple list is empty. 490.Sh LISTS 491A list is headed by a structure defined by the 492.Fn LIST_HEAD 493macro. 494This structure contains a single pointer to the first element on the list. 495The elements are doubly linked so that an arbitrary element can be 496removed without traversing the list. 497New elements can be added to the list after an existing element, 498before an existing element, or at the head of the list. 499A 500.Fa LIST_HEAD 501structure is declared as follows: 502.Bd -literal -offset indent 503LIST_HEAD(HEADNAME, TYPE) head; 504.Ed 505.Pp 506where 507.Fa HEADNAME 508is the name of the structure to be defined, and struct 509.Fa TYPE 510is the type of the elements to be linked into the list. 511A pointer to the head of the list can later be declared as: 512.Bd -literal -offset indent 513struct HEADNAME *headp; 514.Ed 515.Pp 516(The names 517.Li head 518and 519.Li headp 520are user selectable.) 521.Pp 522The 523.Fa HEADNAME 524facility is often not used, leading to the following bizarre code: 525.Bd -literal -offset indent 526LIST_HEAD(, TYPE) head, *headp; 527.Ed 528.Pp 529The 530.Fn LIST_ENTRY 531macro declares a structure that connects the elements in the list. 532.Pp 533The 534.Fn LIST_INIT 535macro initializes the list referenced by 536.Fa head . 537.Pp 538The list can also be initialized statically by using the 539.Fn LIST_HEAD_INITIALIZER 540macro like this: 541.Bd -literal -offset indent 542LIST_HEAD(HEADNAME, TYPE) head = LIST_HEAD_INITIALIZER(head); 543.Ed 544.Pp 545The 546.Fn LIST_INSERT_HEAD 547macro inserts the new element 548.Fa elm 549at the head of the list. 550.Pp 551The 552.Fn LIST_INSERT_AFTER 553macro inserts the new element 554.Fa elm 555after the element 556.Fa listelm . 557.Pp 558The 559.Fn LIST_INSERT_BEFORE 560macro inserts the new element 561.Fa elm 562before the element 563.Fa listelm . 564.Pp 565The 566.Fn LIST_REMOVE 567macro removes the element 568.Fa elm 569from the list. 570.Pp 571The 572.Fn LIST_REPLACE 573macro replaces the list element 574.Fa elm 575with the new element 576.Fa elm2 . 577.Pp 578The 579.Fn LIST_FIRST 580and 581.Fn LIST_NEXT 582macros can be used to traverse the list: 583.Bd -literal -offset indent 584for (np = LIST_FIRST(&head); np != NULL; np = LIST_NEXT(np, NAME)) 585.Ed 586.Pp 587Or, for simplicity, one can use the 588.Fn LIST_FOREACH 589macro: 590.Bd -literal -offset indent 591LIST_FOREACH(np, head, NAME) 592.Ed 593.Pp 594The 595.Fn LIST_EMPTY 596macro should be used to check whether a list is empty. 597.Sh LIST EXAMPLE 598.Bd -literal 599LIST_HEAD(listhead, entry) head; 600struct listhead *headp; /* List head. */ 601struct entry { 602 ... 603 LIST_ENTRY(entry) entries; /* List. */ 604 ... 605} *n1, *n2, *np; 606 607LIST_INIT(&head); /* Initialize list. */ 608 609n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 610LIST_INSERT_HEAD(&head, n1, entries); 611 612n2 = malloc(sizeof(struct entry)); /* Insert after. */ 613LIST_INSERT_AFTER(n1, n2, entries); 614 615n2 = malloc(sizeof(struct entry)); /* Insert before. */ 616LIST_INSERT_BEFORE(n1, n2, entries); 617 /* Forward traversal. */ 618for (np = head.lh_first; np != NULL; np = np->entries.le_next) 619 np-> ... 620 621while (head.lh_first != NULL) /* Delete. */ 622 LIST_REMOVE(head.lh_first, entries); 623.Ed 624.Sh SIMPLE QUEUES 625A simple queue is headed by a structure defined by the 626.Fn SIMPLEQ_HEAD 627macro. 628This structure contains a pair of pointers, one to the first element in the 629simple queue and the other to the last element in the simple queue. 630The elements are singly linked. 631New elements can be added to the queue after an existing element, 632at the head of the queue or at the tail of the queue. 633A 634.Fa SIMPLEQ_HEAD 635structure is declared as follows: 636.Bd -literal -offset indent 637SIMPLEQ_HEAD(HEADNAME, TYPE) head; 638.Ed 639.Pp 640where 641.Fa HEADNAME 642is the name of the structure to be defined, and struct 643.Fa TYPE 644is the type of the elements to be linked into the queue. 645A pointer to the head of the queue can later be declared as: 646.Bd -literal -offset indent 647struct HEADNAME *headp; 648.Ed 649.Pp 650(The names 651.Li head 652and 653.Li headp 654are user selectable.) 655.Pp 656The 657.Fn SIMPLEQ_ENTRY 658macro declares a structure that connects the elements in 659the queue. 660.Pp 661The 662.Fn SIMPLEQ_INIT 663macro initializes the queue referenced by 664.Fa head . 665.Pp 666The queue can also be initialized statically by using the 667.Fn SIMPLEQ_HEAD_INITIALIZER 668macro like this: 669.Bd -literal -offset indent 670SIMPLEQ_HEAD(HEADNAME, TYPE) head = SIMPLEQ_HEAD_INITIALIZER(head); 671.Ed 672.Pp 673The 674.Fn SIMPLEQ_INSERT_HEAD 675macro inserts the new element 676.Fa elm 677at the head of the queue. 678.Pp 679The 680.Fn SIMPLEQ_INSERT_TAIL 681macro inserts the new element 682.Fa elm 683at the end of the queue. 684.Pp 685The 686.Fn SIMPLEQ_INSERT_AFTER 687macro inserts the new element 688.Fa elm 689after the element 690.Fa listelm . 691.Pp 692The 693.Fn SIMPLEQ_REMOVE_HEAD 694macro removes the first element 695from the queue. 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, NAME) 707.Ed 708.Pp 709The 710.Fn SIMPLEQ_EMPTY 711macro should be used to check whether a list is empty. 712.Sh SIMPLE QUEUE EXAMPLE 713.Bd -literal 714SIMPLEQ_HEAD(listhead, entry) head = SIMPLEQ_HEAD_INITIALIZER(head); 715struct entry { 716 ... 717 SIMPLEQ_ENTRY(entry) entries; /* List. */ 718 ... 719} *n1, *n2, *np; 720 721n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 722SIMPLEQ_INSERT_HEAD(&head, n1, entries); 723 724n2 = malloc(sizeof(struct entry)); /* Insert after. */ 725SIMPLEQ_INSERT_AFTER(n1, n2, entries); 726 727n2 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 728SIMPLEQ_INSERT_TAIL(&head, n1, entries); 729 /* Forward traversal. */ 730for (np = SIMPLEQ_FIRST(&head); np != NULL; np = SIMPLEQ_NEXT(np, entries)) 731 np-> ... 732 /* Delete. */ 733while ((n1 = SIMPLEQ_FIRST(&head)) != NULL) 734 SIMPLEQ_REMOVE_HEAD(&head, n1, entries); 735.Ed 736.Sh TAIL QUEUES 737A tail queue is headed by a structure defined by the 738.Fn TAILQ_HEAD 739macro. 740This structure contains a pair of pointers, 741one to the first element in the tail queue and the other to 742the last element in the tail queue. 743The elements are doubly linked so that an arbitrary element can be 744removed without traversing the tail queue. 745New elements can be added to the queue after an existing element, 746before an existing element, at the head of the queue, or at the end 747of the queue. 748A 749.Fa TAILQ_HEAD 750structure is declared as follows: 751.Bd -literal -offset indent 752TAILQ_HEAD(HEADNAME, TYPE) head; 753.Ed 754.Pp 755where 756.Fa HEADNAME 757is the name of the structure to be defined, and struct 758.Fa TYPE 759is the type of the elements to be linked into the tail queue. 760A pointer to the head of the tail queue can later be declared as: 761.Bd -literal -offset indent 762struct HEADNAME *headp; 763.Ed 764.Pp 765(The names 766.Li head 767and 768.Li headp 769are user selectable.) 770.Pp 771The 772.Fn TAILQ_ENTRY 773macro declares a structure that connects the elements in 774the tail queue. 775.Pp 776The 777.Fn TAILQ_INIT 778macro initializes the tail queue referenced by 779.Fa head . 780.Pp 781The tail queue can also be initialized statically by using the 782.Fn TAILQ_HEAD_INITIALIZER 783macro. 784.Pp 785The 786.Fn TAILQ_INSERT_HEAD 787macro inserts the new element 788.Fa elm 789at the head of the tail queue. 790.Pp 791The 792.Fn TAILQ_INSERT_TAIL 793macro inserts the new element 794.Fa elm 795at the end of the tail queue. 796.Pp 797The 798.Fn TAILQ_INSERT_AFTER 799macro inserts the new element 800.Fa elm 801after the element 802.Fa listelm . 803.Pp 804The 805.Fn TAILQ_INSERT_BEFORE 806macro inserts the new element 807.Fa elm 808before the element 809.Fa listelm . 810.Pp 811The 812.Fn TAILQ_REMOVE 813macro removes the element 814.Fa elm 815from the tail queue. 816.Pp 817.Fn TAILQ_FOREACH 818and 819.Fn TAILQ_FOREACH_REVERSE 820are used for traversing a tail queue. 821.Fn TAILQ_FOREACH 822starts at the first element and proceeds towards the last. 823.Fn TAILQ_FOREACH_REVERSE 824starts at the last element and proceeds towards the first. 825.Bd -literal -offset indent 826TAILQ_FOREACH(np, &head, NAME) 827TAILQ_FOREACH_REVERSE(np, &head, HEADNAME, NAME) 828.Ed 829.Pp 830The 831.Fn TAILQ_FIRST , 832.Fn TAILQ_NEXT , 833.Fn TAILQ_LAST 834and 835.Fn TAILQ_PREV 836macros can be used to manually traverse a tail queue or an arbitrary part of 837one. 838.Pp 839The 840.Fn TAILQ_EMPTY 841macro should be used to check whether a tail queue is empty. 842.Sh TAIL QUEUE EXAMPLE 843.Bd -literal 844TAILQ_HEAD(tailhead, entry) head; 845struct tailhead *headp; /* Tail queue head. */ 846struct entry { 847 ... 848 TAILQ_ENTRY(entry) entries; /* Tail queue. */ 849 ... 850} *n1, *n2, *np; 851 852TAILQ_INIT(&head); /* Initialize queue. */ 853 854n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 855TAILQ_INSERT_HEAD(&head, n1, entries); 856 857n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 858TAILQ_INSERT_TAIL(&head, n1, entries); 859 860n2 = malloc(sizeof(struct entry)); /* Insert after. */ 861TAILQ_INSERT_AFTER(&head, n1, n2, entries); 862 863n2 = malloc(sizeof(struct entry)); /* Insert before. */ 864TAILQ_INSERT_BEFORE(n1, n2, entries); 865 /* Forward traversal. */ 866TAILQ_FOREACH(np, &head, entries) 867 np-> ... 868 /* Manual forward traversal */ 869for (np = n2; np != NULL; np = TAILQ_NEXT(np, entries)) 870 np-> ... 871 /* Delete. */ 872while (np = TAILQ_FIRST(&head)) 873 TAILQ_REMOVE(&head, np, entries); 874.Ed 875.Sh CIRCULAR QUEUES 876A circular queue is headed by a structure defined by the 877.Fn CIRCLEQ_HEAD 878macro. 879This structure contains a pair of pointers, 880one to the first element in the circular queue and the other to the 881last element in the circular queue. 882The elements are doubly linked so that an arbitrary element can be 883removed without traversing the queue. 884New elements can be added to the queue after an existing element, 885before an existing element, at the head of the queue, or at the end 886of the queue. 887A 888.Fa CIRCLEQ_HEAD 889structure is declared as follows: 890.Bd -literal -offset indent 891CIRCLEQ_HEAD(HEADNAME, TYPE) head; 892.Ed 893.Pp 894where 895.Fa HEADNAME 896is the name of the structure to be defined, and struct 897.Fa TYPE 898is the type of the elements to be linked into the circular queue. 899A pointer to the head of the circular queue can later be declared as: 900.Bd -literal -offset indent 901struct HEADNAME *headp; 902.Ed 903.Pp 904(The names 905.Li head 906and 907.Li headp 908are user selectable.) 909.Pp 910The 911.Fn CIRCLEQ_ENTRY 912macro declares a structure that connects the elements in the circular queue. 913.Pp 914The 915.Fn CIRCLEQ_INIT 916macro initializes the circular queue referenced by 917.Fa head . 918.Pp 919The circular queue can also be initialized statically by using the 920.Fn CIRCLEQ_HEAD_INITIALIZER 921macro. 922.Pp 923The 924.Fn CIRCLEQ_INSERT_HEAD 925macro inserts the new element 926.Fa elm 927at the head of the circular queue. 928.Pp 929The 930.Fn CIRCLEQ_INSERT_TAIL 931macro inserts the new element 932.Fa elm 933at the end of the circular queue. 934.Pp 935The 936.Fn CIRCLEQ_INSERT_AFTER 937macro inserts the new element 938.Fa elm 939after the element 940.Fa listelm . 941.Pp 942The 943.Fn CIRCLEQ_INSERT_BEFORE 944macro inserts the new element 945.Fa elm 946before the element 947.Fa listelm . 948.Pp 949The 950.Fn CIRCLEQ_REMOVE 951macro removes the element 952.Fa elm 953from the circular queue. 954.Pp 955The 956.Fn CIRCLEQ_FIRST , 957.Fn CIRCLEQ_LAST , 958.Fn CIRCLEQ_END , 959.Fn CIRCLEQ_NEXT 960and 961.Fn CIRCLEQ_PREV 962macros can be used to traverse a circular queue. 963The 964.Fn CIRCLEQ_FOREACH 965is used for circular queue forward traversal: 966.Bd -literal -offset indent 967CIRCLEQ_FOREACH(np, head, NAME) 968.Ed 969.Pp 970The 971.Fn CIRCLEQ_FOREACH_REVERSE 972macro acts like 973.Fn CIRCLEQ_FOREACH 974but traverses the circular queue backwards. 975.Pp 976The 977.Fn CIRCLEQ_EMPTY 978macro should be used to check whether a circular queue is empty. 979.Sh CIRCULAR QUEUE EXAMPLE 980.Bd -literal 981CIRCLEQ_HEAD(circleq, entry) head; 982struct circleq *headp; /* Circular queue head. */ 983struct entry { 984 ... 985 CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */ 986 ... 987} *n1, *n2, *np; 988 989CIRCLEQ_INIT(&head); /* Initialize circular queue. */ 990 991n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 992CIRCLEQ_INSERT_HEAD(&head, n1, entries); 993 994n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 995CIRCLEQ_INSERT_TAIL(&head, n1, entries); 996 997n2 = malloc(sizeof(struct entry)); /* Insert after. */ 998CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries); 999 1000n2 = malloc(sizeof(struct entry)); /* Insert before. */ 1001CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries); 1002 /* Forward traversal. */ 1003for (np = CIRCLEQ_FIRST(&head); np != CIRCLEQ_END(&head); 1004 np = CIRCLEQ_NEXT(np, entries)) 1005 np-> ... 1006 /* Reverse traversal. */ 1007for (np = CIRCLEQ_LAST(&head); np != CIRCLEQ_END(&head); 1008 np = CIRCLEQ_PREV(np, entries)) 1009 np-> ... 1010 /* Delete. */ 1011while (CIRCLEQ_FIRST(&head) != CIRCLEQ_END(&head)) 1012 CIRCLEQ_REMOVE(&head, CIRCLEQ_FIRST(&head), entries); 1013.Ed 1014.Sh NOTES 1015The 1016.Fn SLIST_END , 1017.Fn LIST_END , 1018.Fn SIMPLEQ_END 1019and 1020.Fn TAILQ_END 1021macros are provided for symmetry with 1022.Fn CIRCLEQ_END . 1023They expand to 1024.Dv NULL 1025and don't serve any useful purpose. 1026.Pp 1027Trying to free a list in the following way is a common error: 1028.Bd -literal -offset indent 1029LIST_FOREACH(var, head, entry) 1030 free(var); 1031free(head); 1032.Ed 1033.Pp 1034Since 1035.Va var 1036is free'd, the 1037.Fn FOREACH 1038macro refers to a pointer that may have been reallocated already. 1039Proper code needs a second variable. 1040.Bd -literal -offset indent 1041for (var = LIST_FIRST(head); var != LIST_END(head); var = nxt) { 1042 nxt = LIST_NEXT(var, entry); 1043 free(var); 1044} 1045LIST_INIT(head); /* to put the list back in order */ 1046.Ed 1047.Sh HISTORY 1048The 1049.Nm queue 1050functions first appeared in 1051.Bx 4.4 . 1052