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