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