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