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