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