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