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