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