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