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