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