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