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