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