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