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