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