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