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