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