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