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