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