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. Neither the name of the University nor the names of its contributors 13.\" may be used to endorse or promote products derived from this software 14.\" without specific prior written permission. 15.\" 16.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 17.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 20.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26.\" SUCH DAMAGE. 27.\" 28.Dd April 28, 2025 29.Dt QUEUE 3 30.Os 31.Sh NAME 32.Nm SLIST_CLASS_ENTRY , 33.Nm SLIST_CLASS_HEAD , 34.Nm SLIST_CONCAT , 35.Nm SLIST_EMPTY , 36.Nm SLIST_EMPTY_ATOMIC , 37.Nm SLIST_ENTRY , 38.Nm SLIST_FIRST , 39.Nm SLIST_FOREACH , 40.Nm SLIST_FOREACH_FROM , 41.Nm SLIST_FOREACH_FROM_SAFE , 42.Nm SLIST_FOREACH_SAFE , 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 , 50.Nm SLIST_REMOVE_AFTER , 51.Nm SLIST_REMOVE_HEAD , 52.Nm SLIST_SPLIT_AFTER , 53.Nm SLIST_SWAP , 54.Nm STAILQ_CLASS_ENTRY , 55.Nm STAILQ_CLASS_HEAD , 56.Nm STAILQ_CONCAT , 57.Nm STAILQ_EMPTY , 58.Nm STAILQ_EMPTY_ATOMIC , 59.Nm STAILQ_ENTRY , 60.Nm STAILQ_FIRST , 61.Nm STAILQ_FOREACH , 62.Nm STAILQ_FOREACH_FROM , 63.Nm STAILQ_FOREACH_FROM_SAFE , 64.Nm STAILQ_FOREACH_SAFE , 65.Nm STAILQ_HEAD , 66.Nm STAILQ_HEAD_INITIALIZER , 67.Nm STAILQ_INIT , 68.Nm STAILQ_INSERT_AFTER , 69.Nm STAILQ_INSERT_HEAD , 70.Nm STAILQ_INSERT_TAIL , 71.Nm STAILQ_LAST , 72.Nm STAILQ_NEXT , 73.Nm STAILQ_REMOVE , 74.Nm STAILQ_REMOVE_AFTER , 75.Nm STAILQ_REMOVE_HEAD , 76.Nm STAILQ_SPLIT_AFTER , 77.Nm STAILQ_SWAP , 78.Nm LIST_CLASS_ENTRY , 79.Nm LIST_CLASS_HEAD , 80.Nm LIST_CONCAT , 81.Nm LIST_EMPTY , 82.Nm LIST_EMPTY_ATOMIC , 83.Nm LIST_ENTRY , 84.Nm LIST_FIRST , 85.Nm LIST_FOREACH , 86.Nm LIST_FOREACH_FROM , 87.Nm LIST_FOREACH_FROM_SAFE , 88.Nm LIST_FOREACH_SAFE , 89.Nm LIST_HEAD , 90.Nm LIST_HEAD_INITIALIZER , 91.Nm LIST_INIT , 92.Nm LIST_INSERT_AFTER , 93.Nm LIST_INSERT_BEFORE , 94.Nm LIST_INSERT_HEAD , 95.Nm LIST_NEXT , 96.Nm LIST_PREV , 97.Nm LIST_REMOVE , 98.Nm LIST_REPLACE , 99.Nm LIST_SPLIT_AFTER , 100.Nm LIST_SWAP , 101.Nm TAILQ_CLASS_ENTRY , 102.Nm TAILQ_CLASS_HEAD , 103.Nm TAILQ_CONCAT , 104.Nm TAILQ_EMPTY , 105.Nm TAILQ_EMPTY_ATOMIC , 106.Nm TAILQ_ENTRY , 107.Nm TAILQ_FIRST , 108.Nm TAILQ_FOREACH , 109.Nm TAILQ_FOREACH_FROM , 110.Nm TAILQ_FOREACH_FROM_SAFE , 111.Nm TAILQ_FOREACH_REVERSE , 112.Nm TAILQ_FOREACH_REVERSE_FROM , 113.Nm TAILQ_FOREACH_REVERSE_FROM_SAFE , 114.Nm TAILQ_FOREACH_REVERSE_SAFE , 115.Nm TAILQ_FOREACH_SAFE , 116.Nm TAILQ_HEAD , 117.Nm TAILQ_HEAD_INITIALIZER , 118.Nm TAILQ_INIT , 119.Nm TAILQ_INSERT_AFTER , 120.Nm TAILQ_INSERT_BEFORE , 121.Nm TAILQ_INSERT_HEAD , 122.Nm TAILQ_INSERT_TAIL , 123.Nm TAILQ_LAST , 124.Nm TAILQ_NEXT , 125.Nm TAILQ_PREV , 126.Nm TAILQ_REMOVE , 127.Nm TAILQ_REPLACE , 128.Nm TAILQ_SPLIT_AFTER , 129.Nm TAILQ_SWAP 130.Nd implementations of singly-linked lists, singly-linked tail queues, 131lists and tail queues 132.Sh SYNOPSIS 133.In sys/queue.h 134.\" 135.Fn SLIST_CLASS_ENTRY "CLASSTYPE" 136.Fn SLIST_CLASS_HEAD "HEADNAME" "CLASSTYPE" 137.Fn SLIST_CONCAT "SLIST_HEAD *head1" "SLIST_HEAD *head2" "TYPE" "SLIST_ENTRY NAME" 138.Fn SLIST_EMPTY "SLIST_HEAD *head" 139.Fn SLIST_EMPTY_ATOMIC "SLIST_HEAD *head" 140.Fn SLIST_ENTRY "TYPE" 141.Fn SLIST_FIRST "SLIST_HEAD *head" 142.Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" 143.Fn SLIST_FOREACH_FROM "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" 144.Fn SLIST_FOREACH_FROM_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" 145.Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" 146.Fn SLIST_HEAD "HEADNAME" "TYPE" 147.Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head" 148.Fn SLIST_INIT "SLIST_HEAD *head" 149.Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME" 150.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME" 151.Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME" 152.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME" 153.Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME" 154.Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME" 155.Fn SLIST_SPLIT_AFTER "SLIST_HEAD *head" "TYPE *elm" "SLIST_HEAD *rest" "SLIST_ENTRY NAME" 156.Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "TYPE" 157.\" 158.Fn STAILQ_CLASS_ENTRY "CLASSTYPE" 159.Fn STAILQ_CLASS_HEAD "HEADNAME" "CLASSTYPE" 160.Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" 161.Fn STAILQ_EMPTY "STAILQ_HEAD *head" 162.Fn STAILQ_EMPTY_ATOMIC "STAILQ_HEAD *head" 163.Fn STAILQ_ENTRY "TYPE" 164.Fn STAILQ_FIRST "STAILQ_HEAD *head" 165.Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" 166.Fn STAILQ_FOREACH_FROM "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" 167.Fn STAILQ_FOREACH_FROM_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var" 168.Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var" 169.Fn STAILQ_HEAD "HEADNAME" "TYPE" 170.Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head" 171.Fn STAILQ_INIT "STAILQ_HEAD *head" 172.Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME" 173.Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" 174.Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" 175.Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" 176.Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME" 177.Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME" 178.Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" 179.Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" 180.Fn STAILQ_SPLIT_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_HEAD *rest" "STAILQ_ENTRY NAME" 181.Fn STAILQ_SWAP "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" "TYPE" 182.\" 183.Fn LIST_CLASS_ENTRY "CLASSTYPE" 184.Fn LIST_CLASS_HEAD "HEADNAME" "CLASSTYPE" 185.Fn LIST_CONCAT "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME" 186.Fn LIST_EMPTY "LIST_HEAD *head" 187.Fn LIST_EMPTY_ATOMIC "LIST_HEAD *head" 188.Fn LIST_ENTRY "TYPE" 189.Fn LIST_FIRST "LIST_HEAD *head" 190.Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" 191.Fn LIST_FOREACH_FROM "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" 192.Fn LIST_FOREACH_FROM_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var" 193.Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var" 194.Fn LIST_HEAD "HEADNAME" "TYPE" 195.Fn LIST_HEAD_INITIALIZER "LIST_HEAD head" 196.Fn LIST_INIT "LIST_HEAD *head" 197.Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" 198.Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" 199.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME" 200.Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME" 201.Fn LIST_PREV "TYPE *elm" "LIST_HEAD *head" "TYPE" "LIST_ENTRY NAME" 202.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME" 203.Fn LIST_REPLACE "TYPE *elm" "TYPE *new" "LIST_ENTRY NAME" 204.Fn LIST_SPLIT_AFTER "LIST_HEAD *head" "TYPE *elm" "LIST_HEAD *rest" "LIST_ENTRY NAME" 205.Fn LIST_SWAP "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME" 206.\" 207.Fn TAILQ_CLASS_ENTRY "CLASSTYPE" 208.Fn TAILQ_CLASS_HEAD "HEADNAME" "CLASSTYPE" 209.Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME" 210.Fn TAILQ_EMPTY "TAILQ_HEAD *head" 211.Fn TAILQ_EMPTY_ATOMIC "TAILQ_HEAD *head" 212.Fn TAILQ_ENTRY "TYPE" 213.Fn TAILQ_FIRST "TAILQ_HEAD *head" 214.Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" 215.Fn TAILQ_FOREACH_FROM "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" 216.Fn TAILQ_FOREACH_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var" 217.Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" 218.Fn TAILQ_FOREACH_REVERSE_FROM "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" 219.Fn TAILQ_FOREACH_REVERSE_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var" 220.Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var" 221.Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var" 222.Fn TAILQ_HEAD "HEADNAME" "TYPE" 223.Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head" 224.Fn TAILQ_INIT "TAILQ_HEAD *head" 225.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" 226.Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" 227.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 228.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 229.Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME" 230.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME" 231.Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME" 232.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 233.Fn TAILQ_REPLACE "TAILQ_HEAD *head" "TYPE *elm" "TYPE *new" "TAILQ_ENTRY NAME" 234.Fn TAILQ_SPLIT_AFTER "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_HEAD *rest" "TAILQ_ENTRY NAME" 235.Fn TAILQ_SWAP "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TYPE" "TAILQ_ENTRY NAME" 236.\" 237.Sh DESCRIPTION 238These macros define and operate on four types of data structures which 239can be used in both C and C++ source code: 240.Bl -enum -compact -offset indent 241.It 242Lists 243.It 244Singly-linked lists 245.It 246Singly-linked tail queues 247.It 248Tail queues 249.El 250All four structures support the following functionality: 251.Bl -enum -compact -offset indent 252.It 253Insertion of a new entry at the head of the list. 254.It 255Insertion of a new entry after any element in the list. 256.It 257O(1) removal of an entry from the head of the list. 258.It 259Forward traversal through the list. 260.It 261Splitting a list in two after any element in the list. 262.It 263Swapping the contents of two lists. 264.El 265.Pp 266Singly-linked lists are the simplest of the four data structures 267and support only the above functionality. 268Singly-linked lists are ideal for applications with large datasets 269and few or no removals, 270or for implementing a LIFO queue. 271Singly-linked lists add the following functionality: 272.Bl -enum -compact -offset indent 273.It 274O(n) removal of any entry in the list. 275.It 276O(n) concatenation of two lists. 277.El 278.Pp 279Singly-linked tail queues add the following functionality: 280.Bl -enum -compact -offset indent 281.It 282Entries can be added at the end of a list. 283.It 284O(n) removal of any entry in the list. 285.It 286They may be concatenated. 287.El 288However: 289.Bl -enum -compact -offset indent 290.It 291All list insertions must specify the head of the list. 292.It 293Each head entry requires two pointers rather than one. 294.It 295Code size is about 15% greater and operations run about 20% slower 296than singly-linked lists. 297.El 298.Pp 299Singly-linked tail queues are ideal for applications with large datasets and 300few or no removals, 301or for implementing a FIFO queue. 302.Pp 303All doubly linked types of data structures (lists and tail queues) 304additionally allow: 305.Bl -enum -compact -offset indent 306.It 307Insertion of a new entry before any element in the list. 308.It 309O(1) removal of any entry in the list. 310.El 311However: 312.Bl -enum -compact -offset indent 313.It 314Each element requires two pointers rather than one. 315.It 316Code size and execution time of operations (except for removal) is about 317twice that of the singly-linked data-structures. 318.El 319.Pp 320Linked lists are the simplest of the doubly linked data structures. 321They add the following functionality over the above: 322.Bl -enum -compact -offset indent 323.It 324O(n) concatenation of two lists. 325.It 326They may be traversed backwards. 327.El 328However: 329.Bl -enum -compact -offset indent 330.It 331To traverse backwards, an entry to begin the traversal and the list in 332which it is contained must be specified. 333.El 334.Pp 335Tail queues add the following functionality: 336.Bl -enum -compact -offset indent 337.It 338Entries can be added at the end of a list. 339.It 340They may be traversed backwards, from tail to head. 341.It 342They may be concatenated. 343.El 344However: 345.Bl -enum -compact -offset indent 346.It 347All list insertions and removals must specify the head of the list. 348.It 349Each head entry requires two pointers rather than one. 350.It 351Code size is about 15% greater and operations run about 20% slower 352than singly-linked lists. 353.El 354.Pp 355In the macro definitions, 356.Fa TYPE 357is the name of a user defined structure. 358The structure must contain a field called 359.Fa NAME 360which is of type 361.Li SLIST_ENTRY , 362.Li STAILQ_ENTRY , 363.Li LIST_ENTRY , 364or 365.Li TAILQ_ENTRY . 366In the macro definitions, 367.Fa CLASSTYPE 368is the name of a user defined class. 369The class must contain a field called 370.Fa NAME 371which is of type 372.Li SLIST_CLASS_ENTRY , 373.Li STAILQ_CLASS_ENTRY , 374.Li LIST_CLASS_ENTRY , 375or 376.Li TAILQ_CLASS_ENTRY . 377The argument 378.Fa HEADNAME 379is the name of a user defined structure that must be declared 380using the macros 381.Li SLIST_HEAD , 382.Li SLIST_CLASS_HEAD , 383.Li STAILQ_HEAD , 384.Li STAILQ_CLASS_HEAD , 385.Li LIST_HEAD , 386.Li LIST_CLASS_HEAD , 387.Li TAILQ_HEAD , 388or 389.Li TAILQ_CLASS_HEAD . 390See the examples below for further explanation of how these 391macros are used. 392.Sh SINGLY-LINKED LISTS 393A singly-linked list is headed by a structure defined by the 394.Nm SLIST_HEAD 395macro. 396This structure contains a single pointer to the first element 397on the list. 398The elements are singly linked for minimum space and pointer manipulation 399overhead at the expense of O(n) removal for arbitrary elements. 400New elements can be added to the list after an existing element or 401at the head of the list. 402An 403.Fa SLIST_HEAD 404structure is declared as follows: 405.Bd -literal -offset indent 406SLIST_HEAD(HEADNAME, TYPE) head; 407.Ed 408.Pp 409where 410.Fa HEADNAME 411is the name of the structure to be defined, and 412.Fa TYPE 413is the type of the elements to be linked into the list. 414A pointer to the head of the list can later be declared as: 415.Bd -literal -offset indent 416struct HEADNAME *headp; 417.Ed 418.Pp 419(The names 420.Li head 421and 422.Li headp 423are user selectable.) 424.Pp 425The macro 426.Nm SLIST_HEAD_INITIALIZER 427evaluates to an initializer for the list 428.Fa head . 429.Pp 430The macro 431.Nm SLIST_CONCAT 432concatenates the list headed by 433.Fa head2 434onto the end of the one headed by 435.Fa head1 436removing all entries from the former. 437Use of this macro should be avoided as it traverses the entirety of the 438.Fa head1 439list. 440A singly-linked tail queue should be used if this macro is needed in 441high-usage code paths or to operate on long lists. 442.Pp 443The macro 444.Nm SLIST_EMPTY 445evaluates to true if there are no elements in the list. 446The 447.Nm SLIST_EMPTY_ATOMIC 448variant has the same behavior, but can be safely used in contexts where it is 449possible that a different thread is concurrently updating the list. 450.Pp 451The macro 452.Nm SLIST_ENTRY 453declares a structure that connects the elements in 454the list. 455.Pp 456The macro 457.Nm SLIST_FIRST 458returns the first element in the list or NULL if the list is empty. 459.Pp 460The macro 461.Nm SLIST_FOREACH 462traverses the list referenced by 463.Fa head 464in the forward direction, assigning each element in 465turn to 466.Fa var . 467.Pp 468The macro 469.Nm SLIST_FOREACH_FROM 470behaves identically to 471.Nm SLIST_FOREACH 472when 473.Fa var 474is NULL, else it treats 475.Fa var 476as a previously found SLIST element and begins the loop at 477.Fa var 478instead of the first element in the SLIST referenced by 479.Fa head . 480.Pp 481The macro 482.Nm SLIST_FOREACH_SAFE 483traverses the list referenced by 484.Fa head 485in the forward direction, assigning each element in 486turn to 487.Fa var . 488However, unlike 489.Fn SLIST_FOREACH 490here it is permitted to both remove 491.Fa var 492as well as free it from within the loop safely without interfering with the 493traversal. 494.Pp 495The macro 496.Nm SLIST_FOREACH_FROM_SAFE 497behaves identically to 498.Nm SLIST_FOREACH_SAFE 499when 500.Fa var 501is NULL, else it treats 502.Fa var 503as a previously found SLIST element and begins the loop at 504.Fa var 505instead of the first element in the SLIST referenced by 506.Fa head . 507.Pp 508The macro 509.Nm SLIST_INIT 510initializes the list referenced by 511.Fa head . 512.Pp 513The macro 514.Nm SLIST_INSERT_HEAD 515inserts the new element 516.Fa elm 517at the head of the list. 518.Pp 519The macro 520.Nm SLIST_INSERT_AFTER 521inserts the new element 522.Fa elm 523after the element 524.Fa listelm . 525.Pp 526The macro 527.Nm SLIST_NEXT 528returns the next element in the list. 529.Pp 530The macro 531.Nm SLIST_REMOVE_AFTER 532removes the element after 533.Fa elm 534from the list. 535Unlike 536.Fa SLIST_REMOVE , 537this macro does not traverse the entire list. 538.Pp 539The macro 540.Nm SLIST_REMOVE_HEAD 541removes the element 542.Fa elm 543from the head of the list. 544For optimum efficiency, 545elements being removed from the head of the list should explicitly use 546this macro instead of the generic 547.Fa SLIST_REMOVE 548macro. 549.Pp 550The macro 551.Nm SLIST_REMOVE 552removes the element 553.Fa elm 554from the list. 555Use of this macro should be avoided as it traverses the entire list. 556A doubly-linked list should be used if this macro is needed in 557high-usage code paths or to operate on long lists. 558.Pp 559The macro 560.Nm SLIST_SPLIT_AFTER 561splits the list referenced by 562.Fa head , 563making 564.Fa rest 565reference the list formed by elements after 566.Fa elm 567in 568.Fa head . 569.Pp 570The macro 571.Nm SLIST_SWAP 572swaps the contents of 573.Fa head1 574and 575.Fa head2 . 576.Sh SINGLY-LINKED LIST EXAMPLE 577.Bd -literal 578SLIST_HEAD(slisthead, entry) head = 579 SLIST_HEAD_INITIALIZER(head); 580struct slisthead *headp; /* Singly-linked List head. */ 581struct entry { 582 ... 583 SLIST_ENTRY(entry) entries; /* Singly-linked List. */ 584 ... 585} *n1, *n2, *n3, *np; 586 587SLIST_INIT(&head); /* Initialize the list. */ 588 589n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 590SLIST_INSERT_HEAD(&head, n1, entries); 591 592n2 = malloc(sizeof(struct entry)); /* Insert after. */ 593SLIST_INSERT_AFTER(n1, n2, entries); 594 595SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */ 596free(n2); 597 598n3 = SLIST_FIRST(&head); 599SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */ 600free(n3); 601 /* Forward traversal. */ 602SLIST_FOREACH(np, &head, entries) 603 np-> ... 604 /* Safe forward traversal. */ 605SLIST_FOREACH_SAFE(np, &head, entries, np_temp) { 606 np->do_stuff(); 607 ... 608 SLIST_REMOVE(&head, np, entry, entries); 609 free(np); 610} 611 612while (!SLIST_EMPTY(&head)) { /* List Deletion. */ 613 n1 = SLIST_FIRST(&head); 614 SLIST_REMOVE_HEAD(&head, entries); 615 free(n1); 616} 617.Ed 618.Sh SINGLY-LINKED TAIL QUEUES 619A singly-linked tail queue is headed by a structure defined by the 620.Nm STAILQ_HEAD 621macro. 622This structure contains a pair of pointers, 623one to the first element in the tail queue and the other to 624the last element in the tail queue. 625The elements are singly linked for minimum space and pointer 626manipulation overhead at the expense of O(n) removal for arbitrary 627elements. 628New elements can be added to the tail queue after an existing element, 629at the head of the tail queue, or at the end of the tail queue. 630A 631.Fa STAILQ_HEAD 632structure is declared as follows: 633.Bd -literal -offset indent 634STAILQ_HEAD(HEADNAME, TYPE) head; 635.Ed 636.Pp 637where 638.Li HEADNAME 639is the name of the structure to be defined, and 640.Li TYPE 641is the type of the elements to be linked into the tail queue. 642A pointer to the head of the tail queue can later be declared as: 643.Bd -literal -offset indent 644struct HEADNAME *headp; 645.Ed 646.Pp 647(The names 648.Li head 649and 650.Li headp 651are user selectable.) 652.Pp 653The macro 654.Nm STAILQ_HEAD_INITIALIZER 655evaluates to an initializer for the tail queue 656.Fa head . 657.Pp 658The macro 659.Nm STAILQ_CONCAT 660concatenates the tail queue headed by 661.Fa head2 662onto the end of the one headed by 663.Fa head1 664removing all entries from the former. 665.Pp 666The macro 667.Nm STAILQ_EMPTY 668evaluates to true if there are no items on the tail queue. 669The 670.Nm STAILQ_EMPTY_ATOMIC 671variant has the same behavior, but can be safely used in contexts where it is 672possible that a different thread is concurrently updating the queue. 673.Pp 674The macro 675.Nm STAILQ_ENTRY 676declares a structure that connects the elements in 677the tail queue. 678.Pp 679The macro 680.Nm STAILQ_FIRST 681returns the first item on the tail queue or NULL if the tail queue 682is empty. 683.Pp 684The macro 685.Nm STAILQ_FOREACH 686traverses the tail queue referenced by 687.Fa head 688in the forward direction, assigning each element 689in turn to 690.Fa var . 691.Pp 692The macro 693.Nm STAILQ_FOREACH_FROM 694behaves identically to 695.Nm STAILQ_FOREACH 696when 697.Fa var 698is NULL, else it treats 699.Fa var 700as a previously found STAILQ element and begins the loop at 701.Fa var 702instead of the first element in the STAILQ referenced by 703.Fa head . 704.Pp 705The macro 706.Nm STAILQ_FOREACH_SAFE 707traverses the tail queue referenced by 708.Fa head 709in the forward direction, assigning each element 710in turn to 711.Fa var . 712However, unlike 713.Fn STAILQ_FOREACH 714here it is permitted to both remove 715.Fa var 716as well as free it from within the loop safely without interfering with the 717traversal. 718.Pp 719The macro 720.Nm STAILQ_FOREACH_FROM_SAFE 721behaves identically to 722.Nm STAILQ_FOREACH_SAFE 723when 724.Fa var 725is NULL, else it treats 726.Fa var 727as a previously found STAILQ element and begins the loop at 728.Fa var 729instead of the first element in the STAILQ referenced by 730.Fa head . 731.Pp 732The macro 733.Nm STAILQ_INIT 734initializes the tail queue referenced by 735.Fa head . 736.Pp 737The macro 738.Nm STAILQ_INSERT_HEAD 739inserts the new element 740.Fa elm 741at the head of the tail queue. 742.Pp 743The macro 744.Nm STAILQ_INSERT_TAIL 745inserts the new element 746.Fa elm 747at the end of the tail queue. 748.Pp 749The macro 750.Nm STAILQ_INSERT_AFTER 751inserts the new element 752.Fa elm 753after the element 754.Fa listelm . 755.Pp 756The macro 757.Nm STAILQ_LAST 758returns the last item on the tail queue. 759If the tail queue is empty the return value is 760.Dv NULL . 761.Pp 762The macro 763.Nm STAILQ_NEXT 764returns the next item on the tail queue, or NULL this item is the last. 765.Pp 766The macro 767.Nm STAILQ_REMOVE_AFTER 768removes the element after 769.Fa elm 770from the tail queue. 771Unlike 772.Fa STAILQ_REMOVE , 773this macro does not traverse the entire tail queue. 774.Pp 775The macro 776.Nm STAILQ_REMOVE_HEAD 777removes the element at the head of the tail queue. 778For optimum efficiency, 779elements being removed from the head of the tail queue should 780use this macro explicitly rather than the generic 781.Fa STAILQ_REMOVE 782macro. 783.Pp 784The macro 785.Nm STAILQ_REMOVE 786removes the element 787.Fa elm 788from the tail queue. 789Use of this macro should be avoided as it traverses the entire list. 790A doubly-linked tail queue should be used if this macro is needed in 791high-usage code paths or to operate on long tail queues. 792.Pp 793The macro 794.Nm STAILQ_SPLIT_AFTER 795splits the tail queue referenced by 796.Fa head , 797making 798.Fa rest 799reference the tail queue formed by elements after 800.Fa elm 801in 802.Fa head . 803.Pp 804The macro 805.Nm STAILQ_SWAP 806swaps the contents of 807.Fa head1 808and 809.Fa head2 . 810.Sh SINGLY-LINKED TAIL QUEUE EXAMPLE 811.Bd -literal 812STAILQ_HEAD(stailhead, entry) head = 813 STAILQ_HEAD_INITIALIZER(head); 814struct stailhead *headp; /* Singly-linked tail queue head. */ 815struct entry { 816 ... 817 STAILQ_ENTRY(entry) entries; /* Tail queue. */ 818 ... 819} *n1, *n2, *n3, *np; 820 821STAILQ_INIT(&head); /* Initialize the queue. */ 822 823n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 824STAILQ_INSERT_HEAD(&head, n1, entries); 825 826n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 827STAILQ_INSERT_TAIL(&head, n1, entries); 828 829n2 = malloc(sizeof(struct entry)); /* Insert after. */ 830STAILQ_INSERT_AFTER(&head, n1, n2, entries); 831 /* Deletion. */ 832STAILQ_REMOVE(&head, n2, entry, entries); 833free(n2); 834 /* Deletion from the head. */ 835n3 = STAILQ_FIRST(&head); 836STAILQ_REMOVE_HEAD(&head, entries); 837free(n3); 838 /* Forward traversal. */ 839STAILQ_FOREACH(np, &head, entries) 840 np-> ... 841 /* Safe forward traversal. */ 842STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) { 843 np->do_stuff(); 844 ... 845 STAILQ_REMOVE(&head, np, entry, entries); 846 free(np); 847} 848 /* TailQ Deletion. */ 849while (!STAILQ_EMPTY(&head)) { 850 n1 = STAILQ_FIRST(&head); 851 STAILQ_REMOVE_HEAD(&head, entries); 852 free(n1); 853} 854 /* Faster TailQ Deletion. */ 855n1 = STAILQ_FIRST(&head); 856while (n1 != NULL) { 857 n2 = STAILQ_NEXT(n1, entries); 858 free(n1); 859 n1 = n2; 860} 861STAILQ_INIT(&head); 862.Ed 863.Sh LISTS 864A list is headed by a structure defined by the 865.Nm LIST_HEAD 866macro. 867This structure contains a single pointer to the first element 868on the list. 869The elements are doubly linked so that an arbitrary element can be 870removed without traversing the list. 871New elements can be added to the list after an existing element, 872before an existing element, or at the head of the list. 873A 874.Fa LIST_HEAD 875structure is declared as follows: 876.Bd -literal -offset indent 877LIST_HEAD(HEADNAME, TYPE) head; 878.Ed 879.Pp 880where 881.Fa HEADNAME 882is the name of the structure to be defined, and 883.Fa TYPE 884is the type of the elements to be linked into the list. 885A pointer to the head of the list can later be declared as: 886.Bd -literal -offset indent 887struct HEADNAME *headp; 888.Ed 889.Pp 890(The names 891.Li head 892and 893.Li headp 894are user selectable.) 895.Pp 896The macro 897.Nm LIST_HEAD_INITIALIZER 898evaluates to an initializer for the list 899.Fa head . 900.Pp 901The macro 902.Nm LIST_CONCAT 903concatenates the list headed by 904.Fa head2 905onto the end of the one headed by 906.Fa head1 907removing all entries from the former. 908Use of this macro should be avoided as it traverses the entirety of the 909.Fa head1 910list. 911A tail queue should be used if this macro is needed in 912high-usage code paths or to operate on long lists. 913.Pp 914The macro 915.Nm LIST_EMPTY 916evaluates to true if there are no elements in the list. 917The 918.Nm LIST_EMPTY_ATOMIC 919variant has the same behavior, but can be safely used in contexts where it is 920possible that a different thread is concurrently updating the list. 921.Pp 922The macro 923.Nm LIST_ENTRY 924declares a structure that connects the elements in 925the list. 926.Pp 927The macro 928.Nm LIST_FIRST 929returns the first element in the list or NULL if the list 930is empty. 931.Pp 932The macro 933.Nm LIST_FOREACH 934traverses the list referenced by 935.Fa head 936in the forward direction, assigning each element in turn to 937.Fa var . 938.Pp 939The macro 940.Nm LIST_FOREACH_FROM 941behaves identically to 942.Nm LIST_FOREACH 943when 944.Fa var 945is NULL, else it treats 946.Fa var 947as a previously found LIST element and begins the loop at 948.Fa var 949instead of the first element in the LIST referenced by 950.Fa head . 951.Pp 952The macro 953.Nm LIST_FOREACH_SAFE 954traverses the list referenced by 955.Fa head 956in the forward direction, assigning each element in turn to 957.Fa var . 958However, unlike 959.Fn LIST_FOREACH 960here it is permitted to both remove 961.Fa var 962as well as free it from within the loop safely without interfering with the 963traversal. 964.Pp 965The macro 966.Nm LIST_FOREACH_FROM_SAFE 967behaves identically to 968.Nm LIST_FOREACH_SAFE 969when 970.Fa var 971is NULL, else it treats 972.Fa var 973as a previously found LIST element and begins the loop at 974.Fa var 975instead of the first element in the LIST referenced by 976.Fa head . 977.Pp 978The macro 979.Nm LIST_INIT 980initializes the list referenced by 981.Fa head . 982.Pp 983The macro 984.Nm LIST_INSERT_HEAD 985inserts the new element 986.Fa elm 987at the head of the list. 988.Pp 989The macro 990.Nm LIST_INSERT_AFTER 991inserts the new element 992.Fa elm 993after the element 994.Fa listelm . 995.Pp 996The macro 997.Nm LIST_INSERT_BEFORE 998inserts the new element 999.Fa elm 1000before the element 1001.Fa listelm . 1002.Pp 1003The macro 1004.Nm LIST_NEXT 1005returns the next element in the list, or NULL if this is the last. 1006.Pp 1007The macro 1008.Nm LIST_PREV 1009returns the previous element in the list, or NULL if this is the first. 1010List 1011.Fa head 1012must contain element 1013.Fa elm . 1014.Pp 1015The macro 1016.Nm LIST_REMOVE 1017removes the element 1018.Fa elm 1019from the list. 1020.Pp 1021The macro 1022.Fn LIST_REPLACE 1023replaces the element 1024.Fa elm 1025with 1026.Fa new 1027in the list. 1028The element 1029.Fa new 1030must not already be on a list. 1031.Pp 1032The macro 1033.Nm LIST_SPLIT_AFTER 1034splits the list referenced by 1035.Fa head , 1036making 1037.Fa rest 1038reference the list formed by elements after 1039.Fa elm 1040in 1041.Fa head . 1042.Pp 1043The macro 1044.Nm LIST_SWAP 1045swaps the contents of 1046.Fa head1 1047and 1048.Fa head2 . 1049.Sh LIST EXAMPLE 1050.Bd -literal 1051LIST_HEAD(listhead, entry) head = 1052 LIST_HEAD_INITIALIZER(head); 1053struct listhead *headp; /* List head. */ 1054struct entry { 1055 ... 1056 LIST_ENTRY(entry) entries; /* List. */ 1057 ... 1058} *n1, *n2, *n3, *np, *np_temp; 1059 1060LIST_INIT(&head); /* Initialize the list. */ 1061 1062n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 1063LIST_INSERT_HEAD(&head, n1, entries); 1064 1065n2 = malloc(sizeof(struct entry)); /* Insert after. */ 1066LIST_INSERT_AFTER(n1, n2, entries); 1067 1068n3 = malloc(sizeof(struct entry)); /* Insert before. */ 1069LIST_INSERT_BEFORE(n2, n3, entries); 1070 1071LIST_REMOVE(n2, entries); /* Deletion. */ 1072free(n2); 1073 /* Forward traversal. */ 1074LIST_FOREACH(np, &head, entries) 1075 np-> ... 1076 1077 /* Safe forward traversal. */ 1078LIST_FOREACH_SAFE(np, &head, entries, np_temp) { 1079 np->do_stuff(); 1080 ... 1081 LIST_REMOVE(np, entries); 1082 free(np); 1083} 1084 1085while (!LIST_EMPTY(&head)) { /* List Deletion. */ 1086 n1 = LIST_FIRST(&head); 1087 LIST_REMOVE(n1, entries); 1088 free(n1); 1089} 1090 1091n1 = LIST_FIRST(&head); /* Faster List Deletion. */ 1092while (n1 != NULL) { 1093 n2 = LIST_NEXT(n1, entries); 1094 free(n1); 1095 n1 = n2; 1096} 1097LIST_INIT(&head); 1098.Ed 1099.Sh TAIL QUEUES 1100A tail queue is headed by a structure defined by the 1101.Nm TAILQ_HEAD 1102macro. 1103This structure contains a pair of pointers, 1104one to the first element in the tail queue and the other to 1105the last element in the tail queue. 1106The elements are doubly linked so that an arbitrary element can be 1107removed without traversing the tail queue. 1108New elements can be added to the tail queue after an existing element, 1109before an existing element, at the head of the tail queue, 1110or at the end of the tail queue. 1111A 1112.Fa TAILQ_HEAD 1113structure is declared as follows: 1114.Bd -literal -offset indent 1115TAILQ_HEAD(HEADNAME, TYPE) head; 1116.Ed 1117.Pp 1118where 1119.Li HEADNAME 1120is the name of the structure to be defined, and 1121.Li TYPE 1122is the type of the elements to be linked into the tail queue. 1123A pointer to the head of the tail queue can later be declared as: 1124.Bd -literal -offset indent 1125struct HEADNAME *headp; 1126.Ed 1127.Pp 1128(The names 1129.Li head 1130and 1131.Li headp 1132are user selectable.) 1133.Pp 1134The macro 1135.Nm TAILQ_HEAD_INITIALIZER 1136evaluates to an initializer for the tail queue 1137.Fa head . 1138.Pp 1139The macro 1140.Nm TAILQ_CONCAT 1141concatenates the tail queue headed by 1142.Fa head2 1143onto the end of the one headed by 1144.Fa head1 1145removing all entries from the former. 1146.Pp 1147The macro 1148.Nm TAILQ_EMPTY 1149evaluates to true if there are no items on the tail queue. 1150The 1151.Nm TAILQ_EMPTY_ATOMIC 1152variant has the same behavior, but can be safely used in contexts where it is 1153possible that a different thread is concurrently updating the queue. 1154.Pp 1155The macro 1156.Nm TAILQ_ENTRY 1157declares a structure that connects the elements in 1158the tail queue. 1159.Pp 1160The macro 1161.Nm TAILQ_FIRST 1162returns the first item on the tail queue or NULL if the tail queue 1163is empty. 1164.Pp 1165The macro 1166.Nm TAILQ_FOREACH 1167traverses the tail queue referenced by 1168.Fa head 1169in the forward direction, assigning each element in turn to 1170.Fa var . 1171.Fa var 1172is set to 1173.Dv NULL 1174if the loop completes normally, or if there were no elements. 1175.Pp 1176The macro 1177.Nm TAILQ_FOREACH_FROM 1178behaves identically to 1179.Nm TAILQ_FOREACH 1180when 1181.Fa var 1182is NULL, else it treats 1183.Fa var 1184as a previously found TAILQ element and begins the loop at 1185.Fa var 1186instead of the first element in the TAILQ referenced by 1187.Fa head . 1188.Pp 1189The macro 1190.Nm TAILQ_FOREACH_REVERSE 1191traverses the tail queue referenced by 1192.Fa head 1193in the reverse direction, assigning each element in turn to 1194.Fa var . 1195.Pp 1196The macro 1197.Nm TAILQ_FOREACH_REVERSE_FROM 1198behaves identically to 1199.Nm TAILQ_FOREACH_REVERSE 1200when 1201.Fa var 1202is NULL, else it treats 1203.Fa var 1204as a previously found TAILQ element and begins the reverse loop at 1205.Fa var 1206instead of the last element in the TAILQ referenced by 1207.Fa head . 1208.Pp 1209The macros 1210.Nm TAILQ_FOREACH_SAFE 1211and 1212.Nm TAILQ_FOREACH_REVERSE_SAFE 1213traverse the list referenced by 1214.Fa head 1215in the forward or reverse direction respectively, 1216assigning each element in turn to 1217.Fa var . 1218However, unlike their unsafe counterparts, 1219.Nm TAILQ_FOREACH 1220and 1221.Nm TAILQ_FOREACH_REVERSE 1222permit to both remove 1223.Fa var 1224as well as free it from within the loop safely without interfering with the 1225traversal. 1226.Pp 1227The macro 1228.Nm TAILQ_FOREACH_FROM_SAFE 1229behaves identically to 1230.Nm TAILQ_FOREACH_SAFE 1231when 1232.Fa var 1233is NULL, else it treats 1234.Fa var 1235as a previously found TAILQ element and begins the loop at 1236.Fa var 1237instead of the first element in the TAILQ referenced by 1238.Fa head . 1239.Pp 1240The macro 1241.Nm TAILQ_FOREACH_REVERSE_FROM_SAFE 1242behaves identically to 1243.Nm TAILQ_FOREACH_REVERSE_SAFE 1244when 1245.Fa var 1246is NULL, else it treats 1247.Fa var 1248as a previously found TAILQ element and begins the reverse loop at 1249.Fa var 1250instead of the last element in the TAILQ referenced by 1251.Fa head . 1252.Pp 1253The macro 1254.Nm TAILQ_INIT 1255initializes the tail queue referenced by 1256.Fa head . 1257.Pp 1258The macro 1259.Nm TAILQ_INSERT_HEAD 1260inserts the new element 1261.Fa elm 1262at the head of the tail queue. 1263.Pp 1264The macro 1265.Nm TAILQ_INSERT_TAIL 1266inserts the new element 1267.Fa elm 1268at the end of the tail queue. 1269.Pp 1270The macro 1271.Nm TAILQ_INSERT_AFTER 1272inserts the new element 1273.Fa elm 1274after the element 1275.Fa listelm . 1276.Pp 1277The macro 1278.Nm TAILQ_INSERT_BEFORE 1279inserts the new element 1280.Fa elm 1281before the element 1282.Fa listelm . 1283.Pp 1284The macro 1285.Nm TAILQ_LAST 1286returns the last item on the tail queue. 1287If the tail queue is empty the return value is 1288.Dv NULL . 1289.Pp 1290The macro 1291.Nm TAILQ_NEXT 1292returns the next item on the tail queue, or NULL if this item is the last. 1293.Pp 1294The macro 1295.Nm TAILQ_PREV 1296returns the previous item on the tail queue, or NULL if this item 1297is the first. 1298.Pp 1299The macro 1300.Nm TAILQ_REMOVE 1301removes the element 1302.Fa elm 1303from the tail queue. 1304.Pp 1305The macro 1306.Fn TAILQ_REPLACE 1307replaces the element 1308.Fa elm 1309with 1310.Fa new 1311in the tail queue. 1312The element 1313.Fa new 1314must not already be on a list. 1315.Pp 1316The macro 1317.Nm TAILQ_SPLIT_AFTER 1318splits the tail queue referenced by 1319.Fa head , 1320making 1321.Fa rest 1322reference the tail queue formed by elements after 1323.Fa elm 1324in 1325.Fa head . 1326.Pp 1327The macro 1328.Nm TAILQ_SWAP 1329swaps the contents of 1330.Fa head1 1331and 1332.Fa head2 . 1333.Sh TAIL QUEUE EXAMPLE 1334.Bd -literal 1335TAILQ_HEAD(tailhead, entry) head = 1336 TAILQ_HEAD_INITIALIZER(head); 1337struct tailhead *headp; /* Tail queue head. */ 1338struct entry { 1339 ... 1340 TAILQ_ENTRY(entry) entries; /* Tail queue. */ 1341 ... 1342} *n1, *n2, *n3, *n4, *np; 1343 1344TAILQ_INIT(&head); /* Initialize the queue. */ 1345 1346n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 1347TAILQ_INSERT_HEAD(&head, n1, entries); 1348 1349n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 1350TAILQ_INSERT_TAIL(&head, n1, entries); 1351 1352n2 = malloc(sizeof(struct entry)); /* Insert after. */ 1353TAILQ_INSERT_AFTER(&head, n1, n2, entries); 1354 1355n3 = malloc(sizeof(struct entry)); /* Insert before. */ 1356TAILQ_INSERT_BEFORE(n2, n3, entries); 1357 1358TAILQ_REMOVE(&head, n2, entries); /* Deletion. */ 1359free(n2); 1360 1361n4 = malloc(sizeof(struct entry)); /* Replacement. */ 1362TAILQ_REPLACE(&head, n3, n4, entries); 1363free(n3); 1364 /* Forward traversal. */ 1365TAILQ_FOREACH(np, &head, entries) 1366 np-> ... 1367 /* Safe forward traversal. */ 1368TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) { 1369 np->do_stuff(); 1370 ... 1371 TAILQ_REMOVE(&head, np, entries); 1372 free(np); 1373} 1374 /* Reverse traversal. */ 1375TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries) 1376 np-> ... 1377 /* TailQ Deletion. */ 1378while (!TAILQ_EMPTY(&head)) { 1379 n1 = TAILQ_FIRST(&head); 1380 TAILQ_REMOVE(&head, n1, entries); 1381 free(n1); 1382} 1383 /* Faster TailQ Deletion. */ 1384n1 = TAILQ_FIRST(&head); 1385while (n1 != NULL) { 1386 n2 = TAILQ_NEXT(n1, entries); 1387 free(n1); 1388 n1 = n2; 1389} 1390TAILQ_INIT(&head); 1391.Ed 1392.Sh DIAGNOSTICS 1393.Nm queue(3) 1394provides several diagnostic and debugging facilities. 1395.Pp 1396Check code that performs basic integrity and API conformance checks is 1397automatically inserted when using queue macros in the kernel if compiling it 1398with 1399.Va INVARIANTS . 1400One can request insertion or elision of check code by respectively defining one 1401of the macros 1402.Va QUEUE_MACRO_DEBUG_ASSERTIONS 1403or 1404.Va QUEUE_MACRO_NO_DEBUG_ASSERTIONS 1405before first inclusion of 1406.In sys/queue.h . 1407When check code encounters an anomaly, it panics the kernel or aborts the 1408program. 1409To this end, in the kernel or in 1410.Va _STANDALONE 1411builds, it by default calls 1412.Fn panic , 1413while in userland builds it prints the diagnostic message on 1414.Dv stderr 1415and then calls 1416.Fn abort . 1417These behaviors can be overriden by defining a custom 1418.Fn QMD_PANIC 1419macro before first inclusion of 1420.In sys/queue.h . 1421The diagnostic messages automatically include the source file, line and function 1422where the failing check occured. 1423This behavior can be overriden by defining a custom 1424.Fn QMD_ASSERT 1425macro before first inclusion of 1426.In sys/queue.h . 1427.Pp 1428The 1429.Fn SLIST_REMOVE_PREVPTR 1430macro is available to aid debugging: 1431.Bl -hang -offset indent 1432.It Fn SLIST_REMOVE_PREVPTR "TYPE **prev" "TYPE *elm" "SLIST_ENTRY NAME" 1433.Pp 1434Removes element 1435.Fa elm , 1436which must directly follow the element whose 1437.Va &SLIST_NEXT() 1438is 1439.Fa prev , 1440from the list. 1441This macro may insert, under conditions detailed above, check code that 1442validates that 1443.Fa elm 1444indeed follows 1445.Fa prev 1446in the list 1447.Po 1448through the 1449.Fn QMD_SLIST_CHECK_PREVPTR 1450macro 1451.Pc . 1452.El 1453.Pp 1454When debugging, it can be useful to trace queue changes. 1455To enable tracing, define the macro 1456.Va QUEUE_MACRO_DEBUG_TRACE . 1457Note that, at the moment, only macros for regular tail queues have been 1458instrumented. 1459.Pp 1460It can also be useful to trash pointers that have been unlinked from a queue, 1461to detect use after removal. 1462To enable pointer trashing, define the macro 1463.Va QUEUE_MACRO_DEBUG_TRASH 1464at compile time. 1465Note that, at the moment, only a limited number of macros have been 1466instrumented. 1467The macro 1468.Fn QMD_IS_TRASHED "void *ptr" 1469returns true if 1470.Fa ptr 1471has been trashed by the 1472.Va QUEUE_MACRO_DEBUG_TRASH 1473option. 1474.Sh SEE ALSO 1475.Xr arb 3 , 1476.Xr tree 3 1477.Sh HISTORY 1478The 1479.Nm queue 1480functions first appeared in 1481.Bx 4.4 . 1482