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