1.\" $NetBSD: queue.3,v 1.46 2013/11/27 16:23:00 christos Exp $ 2.\" 3.\" Copyright (c) 2000, 2002 The NetBSD Foundation, Inc. 4.\" All rights reserved. 5.\" 6.\" Redistribution and use in source and binary forms, with or without 7.\" modification, are permitted provided that the following conditions 8.\" are met: 9.\" 1. Redistributions of source code must retain the above copyright 10.\" notice, this list of conditions and the following disclaimer. 11.\" 2. Redistributions in binary form must reproduce the above copyright 12.\" notice, this list of conditions and the following disclaimer in the 13.\" documentation and/or other materials provided with the distribution. 14.\" 15.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 16.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 17.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 18.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 19.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 20.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 21.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 22.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 23.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 24.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 25.\" POSSIBILITY OF SUCH DAMAGE. 26.\" 27.\" Copyright (c) 1993 The Regents of the University of California. 28.\" All rights reserved. 29.\" 30.\" Redistribution and use in source and binary forms, with or without 31.\" modification, are permitted provided that the following conditions 32.\" are met: 33.\" 1. Redistributions of source code must retain the above copyright 34.\" notice, this list of conditions and the following disclaimer. 35.\" 2. Redistributions in binary form must reproduce the above copyright 36.\" notice, this list of conditions and the following disclaimer in the 37.\" documentation and/or other materials provided with the distribution. 38.\" 3. Neither the name of the University nor the names of its contributors 39.\" may be used to endorse or promote products derived from this software 40.\" without specific prior written permission. 41.\" 42.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 43.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 44.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 45.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 46.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 47.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 48.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 49.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 50.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 51.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 52.\" SUCH DAMAGE. 53.\" 54.\" @(#)queue.3 8.1 (Berkeley) 12/13/93 55.\" 56.Dd November 27, 2013 57.Dt QUEUE 3 58.Os 59.Sh NAME 60.Nm SLIST_HEAD , 61.Nm SLIST_HEAD_INITIALIZER , 62.Nm SLIST_ENTRY , 63.Nm SLIST_FIRST , 64.Nm SLIST_EMPTY , 65.Nm SLIST_NEXT , 66.Nm SLIST_FOREACH , 67.Nm SLIST_FOREACH_SAFE , 68.Nm SLIST_INIT , 69.Nm SLIST_INSERT_HEAD , 70.Nm SLIST_INSERT_AFTER , 71.Nm SLIST_REMOVE_AFTER , 72.Nm SLIST_REMOVE_HEAD , 73.Nm SLIST_REMOVE , 74.Nm LIST_HEAD , 75.Nm LIST_HEAD_INITIALIZER , 76.Nm LIST_ENTRY , 77.Nm LIST_FIRST , 78.Nm LIST_EMPTY , 79.Nm LIST_NEXT , 80.Nm LIST_FOREACH , 81.Nm LIST_FOREACH_SAFE , 82.Nm LIST_INIT , 83.Nm LIST_INSERT_AFTER , 84.Nm LIST_INSERT_BEFORE , 85.Nm LIST_INSERT_HEAD , 86.Nm LIST_REMOVE , 87.Nm LIST_REPLACE , 88.Nm SIMPLEQ_HEAD , 89.Nm SIMPLEQ_HEAD_INITIALIZER , 90.Nm SIMPLEQ_ENTRY , 91.Nm SIMPLEQ_FIRST , 92.Nm SIMPLEQ_EMPTY , 93.Nm SIMPLEQ_NEXT , 94.Nm SIMPLEQ_LAST , 95.Nm SIMPLEQ_FOREACH , 96.Nm SIMPLEQ_FOREACH_SAFE , 97.Nm SIMPLEQ_INIT , 98.Nm SIMPLEQ_INSERT_HEAD , 99.Nm SIMPLEQ_INSERT_TAIL , 100.Nm SIMPLEQ_INSERT_AFTER , 101.Nm SIMPLEQ_REMOVE_HEAD , 102.Nm SIMPLEQ_REMOVE_AFTER , 103.Nm SIMPLEQ_REMOVE , 104.Nm SIMPLEQ_CONCAT , 105.Nm TAILQ_HEAD , 106.Nm TAILQ_HEAD_INITIALIZER , 107.Nm TAILQ_ENTRY , 108.Nm TAILQ_FIRST , 109.Nm TAILQ_NEXT , 110.Nm TAILQ_LAST , 111.Nm TAILQ_PREV , 112.Nm TAILQ_EMPTY , 113.Nm TAILQ_FOREACH , 114.Nm TAILQ_FOREACH_SAFE , 115.Nm TAILQ_FOREACH_REVERSE , 116.Nm TAILQ_FOREACH_REVERSE_SAFE , 117.Nm TAILQ_INIT , 118.Nm TAILQ_INSERT_HEAD , 119.Nm TAILQ_INSERT_TAIL , 120.Nm TAILQ_INSERT_AFTER , 121.Nm TAILQ_INSERT_BEFORE , 122.Nm TAILQ_REMOVE , 123.Nm TAILQ_REPLACE , 124.Nm TAILQ_CONCAT , 125.Nm STAILQ_HEAD , 126.Nm STAILQ_HEAD_INITIALIZER , 127.Nm STAILQ_ENTRY , 128.Nm STAILQ_FIRST , 129.Nm STAILQ_EMPTY , 130.Nm STAILQ_NEXT , 131.Nm STAILQ_LAST , 132.Nm STAILQ_FOREACH , 133.Nm STAILQ_FOREACH_SAFE , 134.Nm STAILQ_INIT , 135.Nm STAILQ_INSERT_HEAD , 136.Nm STAILQ_INSERT_TAIL , 137.Nm STAILQ_INSERT_AFTER , 138.Nm STAILQ_REMOVE_HEAD , 139.Nm STAILQ_REMOVE , 140.Nm STAILQ_CONCAT , 141.Nd "implementations of singly-linked lists, lists, simple queues, tail queues, and singly-linked tail queues. 142.Sh SYNOPSIS 143.In sys/queue.h 144.Pp 145.Fn SLIST_HEAD "HEADNAME" "TYPE" 146.Fn SLIST_HEAD_INITIALIZER "head" 147.Fn SLIST_ENTRY "TYPE" 148.Ft TYPE * 149.Fn SLIST_FIRST "SLIST_HEAD *head" 150.Ft int 151.Fn SLIST_EMPTY "SLIST_HEAD *head" 152.Ft TYPE * 153.Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME" 154.Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" 155.Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *tmp" 156.Fn SLIST_INIT "SLIST_HEAD *head" 157.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME" 158.Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME" 159.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME" 160.Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME" 161.Pp 162.Fn LIST_HEAD "HEADNAME" "TYPE" 163.Fn LIST_HEAD_INITIALIZER "head" 164.Fn LIST_ENTRY "TYPE" 165.Ft TYPE * 166.Fn LIST_FIRST "LIST_HEAD *head" 167.Ft TYPE * 168.Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME" 169.Ft int 170.Fn LIST_EMPTY "LIST_HEAD *head" 171.Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" 172.Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *tmp" 173.Fn LIST_INIT "LIST_HEAD *head" 174.Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" 175.Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" 176.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME" 177.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME" 178.Fn LIST_REPLACE "TYPE *elm" "TYPE *new" "LIST_ENTRY NAME" 179.Pp 180.Fn SIMPLEQ_HEAD "HEADNAME" "TYPE" 181.Fn SIMPLEQ_HEAD_INITIALIZER "head" 182.Fn SIMPLEQ_ENTRY "TYPE" 183.Ft TYPE * 184.Fn SIMPLEQ_FIRST "SIMPLEQ_HEAD *head" 185.Ft int 186.Fn SIMPLEQ_EMPTY "SIMPLEQ_HEAD *head" 187.Ft TYPE * 188.Fn SIMPLEQ_NEXT "TYPE *elm" "SIMPLEQ_ENTRY NAME" 189.Ft TYPE * 190.Fn SIMPLEQ_LAST "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME" 191.Fn SIMPLEQ_FOREACH "TYPE *var" "SIMPLEQ_HEAD *head" "SIMPLEQ_ENTRY NAME" 192.Fn SIMPLEQ_FOREACH_SAFE "TYPE *var" "SIMPLEQ_HEAD *head" "SIMPLEQ_ENTRY NAME" "TYPE *tmp" 193.Fn SIMPLEQ_INIT "SIMPLEQ_HEAD *head" 194.Fn SIMPLEQ_INSERT_HEAD "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME" 195.Fn SIMPLEQ_INSERT_TAIL "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME" 196.Fn SIMPLEQ_INSERT_AFTER "SIMPLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "SIMPLEQ_ENTRY NAME" 197.Fn SIMPLEQ_REMOVE_HEAD "SIMPLEQ_HEAD *head" "SIMPLEQ_ENTRY NAME" 198.Fn SIMPLEQ_REMOVE_AFTER "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME" 199.Fn SIMPLEQ_REMOVE "SIMPLEQ_HEAD *head" "TYPE *elm" "TYPE" "SIMPLEQ_ENTRY NAME" 200.Fn SIMPLEQ_CONCAT "SIMPLEQ_HEAD *head1" "SIMPLEQ_HEAD *head2" 201.Pp 202.Fn TAILQ_HEAD "HEADNAME" "TYPE" 203.Fn TAILQ_HEAD_INITIALIZER "head" 204.Fn TAILQ_ENTRY "TYPE" 205.Ft TYPE * 206.Fn TAILQ_FIRST "TAILQ_HEAD *head" 207.Ft TYPE * 208.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME" 209.Ft TYPE * 210.Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME" 211.Ft TYPE * 212.Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME" 213.Ft int 214.Fn TAILQ_EMPTY "TAILQ_HEAD *head" 215.Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" 216.Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *tmp" 217.Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" 218.Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *tmp" 219.Fn TAILQ_INIT "TAILQ_HEAD *head" 220.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 221.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 222.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" 223.Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" 224.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 225.Fn TAILQ_REPLACE "TAILQ_HEAD *head" "TYPE *elm" "TYPE *new" "TAILQ_ENTRY NAME" 226.Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME" 227.Pp 228.Fn STAILQ_HEAD "HEADNAME" "TYPE" 229.Fn STAILQ_HEAD_INITIALIZER "head" 230.Fn STAILQ_ENTRY "TYPE" 231.Ft TYPE * 232.Fn STAILQ_FIRST "STAILQ_HEAD *head" 233.Ft int 234.Fn STAILQ_EMPTY "STAILQ_HEAD *head" 235.Ft TYPE * 236.Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME" 237.Ft TYPE * 238.Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" 239.Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" 240.Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *tmp" 241.Fn STAILQ_INIT "STAILQ_HEAD *head" 242.Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" 243.Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" 244.Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME" 245.Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" 246.Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME" 247.Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" 248.Sh DESCRIPTION 249These macros define and operate on five types of data structures: 250singly-linked lists, simple queues, lists, tail queues, and signly-linked 251tail queues. 252All five structures support the following functionality: 253.Bl -enum -compact -offset indent 254.It 255Insertion of a new entry at the head of the list. 256.It 257Insertion of a new entry before or after any element in the list. 258.It 259Removal of any entry in the list. 260.It 261Forward traversal through the list. 262.El 263.Pp 264Singly-linked lists are the simplest of the four data structures and 265support only the above functionality. 266Singly-linked lists are ideal for applications with large datasets and 267few or no removals, 268or for implementing a LIFO queue. 269.Pp 270Simple queues add the following functionality: 271.Bl -enum -compact -offset indent 272.It 273Entries can be added at the end of a list. 274.It 275They may be concatenated. 276.El 277However: 278.Bl -enum -compact -offset indent 279.It 280Entries may not be added before any element in the list. 281.It 282All list insertions and removals must specify the head of the list. 283.It 284Each head entry requires two pointers rather than one. 285.El 286.Pp 287Simple queues are ideal for applications with large datasets and few or 288no removals, or for implementing a FIFO queue. 289.Pp 290All doubly linked types of data structures (lists and tail queues) 291additionally allow: 292.Bl -enum -compact -offset indent 293.It 294Insertion of a new entry before any element in the list. 295.It 296O(1) removal of any entry in the list. 297.El 298However: 299.Bl -enum -compact -offset indent 300.It 301Each element requires two pointers rather than one. 302.It 303Code size and execution time of operations (except for removal) is about 304twice that of the singly-linked data-structures. 305.El 306.Pp 307Linked lists are the simplest of the doubly linked data structures and 308support only the above functionality over singly-linked lists. 309.Pp 310Tail queues add the following functionality: 311.Bl -enum -compact -offset indent 312.It 313Entries can be added at the end of a list. 314.It 315They may be concatenated. 316.El 317However: 318.Bl -enum -compact -offset indent 319.It 320All list insertions and removals, except insertion before another element, must 321specify the head of the list. 322.It 323Each head entry requires two pointers rather than one. 324.It 325Code size is about 15% greater and operations run about 20% slower 326than lists. 327.El 328.Pp 329Circular queues add the following functionality: 330.Bl -enum -compact -offset indent 331.It 332Entries can be added at the end of a list. 333.It 334They may be traversed backwards, from tail to head. 335.El 336However: 337.Bl -enum -compact -offset indent 338.It 339All list insertions and removals must specify the head of the list. 340.It 341Each head entry requires two pointers rather than one. 342.It 343The termination condition for traversal is more complex. 344.It 345Code size is about 40% greater and operations run about 45% slower 346than lists. 347.El 348.Pp 349In the macro definitions, 350.Fa TYPE 351is the name of a user defined structure, 352that must contain a field of type 353.Li SLIST_ENTRY , 354.Li LIST_ENTRY , 355.Li SIMPLEQ_ENTRY , 356.Li TAILQ_ENTRY , 357or 358.Li STAILQ_ENTRY , 359named 360.Fa NAME . 361The argument 362.Fa HEADNAME 363is the name of a user defined structure that must be declared 364using the macros 365.Li LIST_HEAD , 366.Li SIMPLEQ_HEAD , 367.Li SLIST_HEAD , 368or 369.Li TAILQ_HEAD , 370See the examples below for further explanation of how these 371macros are used. 372.Ss Summary of Operations 373The following table summarizes the supported macros for each type 374of data structure. 375.Pp 376.TS 377box tab(:); 378l | c | c | c | c | c 379l | c | c | c | c | c 380l | c | c | c | c | c 381l | c | c | c | c | c 382l | c | c | c | c | c 383l | c | c | c | c | c. 384:SLIST:LIST:SIMPLEQ:TAILQ:STAILQ 385_ 386_FIRST:+:+:+:+:+ 387_EMPTY:+:+:+:+:+ 388_NEXT:+:+:+:+:+ 389_PREV:-:-:-:+:- 390_LAST:-:-:+:+:+ 391_FOREACH:+:+:+:+:+ 392_FOREACH_SAFE:+:+:+:+:+ 393_FOREACH_REVERSE:-:-:-:+:- 394_FOREACH_REVERSE_SAFE:-:-:-:+:- 395_INSERT_HEAD:+:+:+:+:+ 396_INSERT_AFTER:+:+:+:+:+ 397_INSERT_BEFORE:-:+:-:+:- 398_INSERT_TAIL:-:-:+:+:+ 399_REMOVE:+:+:+:+:+ 400_REMOVE_HEAD:+:-:+:-:+ 401_REMOVE_AFTER:-:-:+:-:+ 402_REPLACE:-:+:-:+:- 403_CONCAT:-:-:+:+:+ 404.TE 405.Sh SINGLY-LINKED LISTS 406A singly-linked list is headed by a structure defined by the 407.Nm SLIST_HEAD 408macro. 409This structure contains a single pointer to the first element 410on the list. 411The elements are singly linked for minimum space and pointer manipulation 412overhead at the expense of O(n) removal for arbitrary elements. 413New elements can be added to the list after an existing element or 414at the head of the list. 415An 416.Fa SLIST_HEAD 417structure is declared as follows: 418.Bd -literal -offset indent 419SLIST_HEAD(HEADNAME, TYPE) head; 420.Ed 421.Pp 422where 423.Fa HEADNAME 424is the name of the structure to be defined, and 425.Fa TYPE 426is the type of the elements to be linked into the list. 427A pointer to the head of the list can later be declared as: 428.Bd -literal -offset indent 429struct HEADNAME *headp; 430.Ed 431.Pp 432(The names 433.Li head 434and 435.Li headp 436are user selectable.) 437.Pp 438The macro 439.Nm SLIST_HEAD_INITIALIZER 440evaluates to an initializer for the list 441.Fa head . 442.Pp 443The macro 444.Nm SLIST_ENTRY 445declares a structure that connects the elements in 446the list. 447.Pp 448The macro 449.Nm SLIST_FIRST 450returns the first element in the list or NULL if the list is empty. 451.Pp 452The macro 453.Pp 454The macro 455.Nm SLIST_EMPTY 456evaluates to true if there are no elements in the list. 457.Pp 458The macro 459.Nm SLIST_NEXT 460returns the next element in the list. 461.Pp 462.Nm SLIST_FOREACH 463traverses the list referenced by 464.Fa head 465in the forward direction, assigning each element in 466turn to 467.Fa var . 468.Pp 469The SAFE version uses 470.Fa tmp 471to hold the next element, so 472.Fa var 473may be freed or removed from the list. 474.Pp 475The macro 476.Nm SLIST_INIT 477initializes the list referenced by 478.Fa head . 479.Pp 480The macro 481.Nm SLIST_INSERT_HEAD 482inserts the new element 483.Fa elm 484at the head of the list. 485.Pp 486The macro 487.Nm SLIST_INSERT_AFTER 488inserts the new element 489.Fa elm 490after the element 491.Fa listelm . 492.Pp 493The macro 494.Nm SLIST_REMOVE 495removes the element 496.Fa elm 497from the list. 498.Pp 499The macro 500.Nm SLIST_REMOVE_HEAD 501removes the first element from the head of the list. 502For optimum efficiency, 503elements being removed from the head of the list should explicitly use 504this macro instead of the generic 505.Nm SLIST_REMOVE 506macro. 507.Pp 508The macros 509.Nm SLIST_REMOVE_AFTER 510removes the element after the one specified. 511For optimum efficiency, 512elements being removed after a specified one should explicitly use 513this macro instead of the generic 514.Nm SLIST_REMOVE 515.Sh SINGLY-LINKED LIST EXAMPLE 516.Bd -literal 517SLIST_HEAD(slisthead, entry) head = 518 SLIST_HEAD_INITIALIZER(head); 519struct slisthead *headp; /* Singly-linked List head. */ 520struct entry { 521 ... 522 SLIST_ENTRY(entry) entries; /* Singly-linked List. */ 523 ... 524} *n1, *n2, *n3, *np; 525 526SLIST_INIT(\*[Am]head); /* Initialize the list. */ 527 528n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 529SLIST_INSERT_HEAD(\*[Am]head, n1, entries); 530 531n2 = malloc(sizeof(struct entry)); /* Insert after. */ 532SLIST_INSERT_AFTER(n1, n2, entries); 533 534SLIST_REMOVE(\*[Am]head, n2, entry, entries);/* Deletion. */ 535free(n2); 536 537n3 = SLIST_FIRST(\*[Am]head); 538SLIST_REMOVE_HEAD(\*[Am]head, entries); /* Deletion from the head. */ 539free(n3); 540 /* Forward traversal. */ 541SLIST_FOREACH(np, \*[Am]head, entries) 542 np-\*[Gt] ... 543 544while (!SLIST_EMPTY(\*[Am]head)) { /* List Deletion. */ 545 n1 = SLIST_FIRST(\*[Am]head); 546 SLIST_REMOVE_HEAD(\*[Am]head, entries); 547 free(n1); 548} 549.Ed 550.Sh LISTS 551A list is headed by a structure defined by the 552.Nm LIST_HEAD 553macro. 554This structure contains a single pointer to the first element 555on the list. 556The elements are doubly linked so that an arbitrary element can be 557removed without traversing the list. 558New elements can be added to the list after an existing element, 559before an existing element, or at the head of the list. 560A 561.Fa LIST_HEAD 562structure is declared as follows: 563.Bd -literal -offset indent 564LIST_HEAD(HEADNAME, TYPE) head; 565.Ed 566.Pp 567where 568.Fa HEADNAME 569is the name of the structure to be defined, and 570.Fa TYPE 571is the type of the elements to be linked into the list. 572A pointer to the head of the list can later be declared as: 573.Bd -literal -offset indent 574struct HEADNAME *headp; 575.Ed 576.Pp 577(The names 578.Li head 579and 580.Li headp 581are user selectable.) 582.Pp 583The macro 584.Nm LIST_ENTRY 585declares a structure that connects the elements in 586the list. 587.Pp 588The macro 589.Nm LIST_HEAD_INITIALIZER 590provides a value which can be used to initialize a list head at 591compile time, and is used at the point that the list head 592variable is declared, like: 593.Bd -literal -offset indent 594struct HEADNAME head = LIST_HEAD_INITIALIZER(head); 595.Ed 596.Pp 597The macro 598.Nm LIST_FIRST 599returns the first element of the list 600.Fa head . 601.Pp 602The macro 603.Nm LIST_EMPTY 604return true if the list 605.Fa head 606has no elements. 607.Pp 608The macro 609.Nm LIST_NEXT 610returns the element after the element 611.Fa elm . 612.Pp 613The macro 614.Nm LIST_FOREACH 615traverses the list referenced by 616.Fa head 617in the forward direction, assigning each element in turn to 618.Fa var . 619.Pp 620The SAFE version uses 621.Fa tmp 622to hold the next element, so 623.Fa var 624may be freed or removed from the list. 625.Pp 626The macro 627.Nm LIST_INIT 628initializes the list referenced by 629.Fa head . 630.Pp 631The macro 632.Nm LIST_INSERT_AFTER 633inserts the new element 634.Fa elm 635after the element 636.Fa listelm . 637.Pp 638The macro 639.Nm LIST_INSERT_BEFORE 640inserts the new element 641.Fa elm 642before the element 643.Fa listelm . 644.Pp 645The macro 646.Nm LIST_INSERT_HEAD 647inserts the new element 648.Fa elm 649at the head of the list. 650.Pp 651The macro 652.Nm LIST_REMOVE 653removes the element 654.Fa elm 655from the list. 656.Pp 657The macro 658.Nm LIST_REPLACE 659replaces the element 660.Fa elm 661with 662.Fa new 663in the list. 664.Sh LIST EXAMPLE 665.Bd -literal 666LIST_HEAD(listhead, entry) head; 667struct listhead *headp; /* List head. */ 668struct entry { 669 ... 670 LIST_ENTRY(entry) entries; /* List. */ 671 ... 672} *n1, *n2, *np; 673 674LIST_INIT(\*[Am]head); /* Initialize the list. */ 675 676n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 677LIST_INSERT_HEAD(\*[Am]head, n1, entries); 678 679n2 = malloc(sizeof(struct entry)); /* Insert after. */ 680LIST_INSERT_AFTER(n1, n2, entries); 681 682n2 = malloc(sizeof(struct entry)); /* Insert before. */ 683LIST_INSERT_BEFORE(n1, n2, entries); 684 /* Forward traversal. */ 685LIST_FOREACH(np, \*[Am]head, entries) 686 np-\*[Gt] ... 687 /* Delete. */ 688while (LIST_FIRST(\*[Am]head) != NULL) 689 LIST_REMOVE(LIST_FIRST(\*[Am]head), entries); 690if (LIST_EMPTY(\*[Am]head)) /* Test for emptiness. */ 691 printf("nothing to do\\n"); 692.Ed 693.Sh SIMPLE QUEUES 694A simple queue is headed by a structure defined by the 695.Nm SIMPLEQ_HEAD 696macro. 697This structure contains a pair of pointers, 698one to the first element in the simple queue and the other to 699the last element in the simple queue. 700The elements are singly linked for minimum space and pointer manipulation 701overhead at the expense of O(n) removal for arbitrary elements. 702New elements can be added to the queue after an existing element, 703at the head of the queue, or at the end of the queue. 704A 705.Fa SIMPLEQ_HEAD 706structure is declared as follows: 707.Bd -literal -offset indent 708SIMPLEQ_HEAD(HEADNAME, TYPE) head; 709.Ed 710.Pp 711where 712.Li HEADNAME 713is the name of the structure to be defined, and 714.Li TYPE 715is the type of the elements to be linked into the simple queue. 716A pointer to the head of the simple queue can later be declared as: 717.Bd -literal -offset indent 718struct HEADNAME *headp; 719.Ed 720.Pp 721(The names 722.Li head 723and 724.Li headp 725are user selectable.) 726.Pp 727The macro 728.Nm SIMPLEQ_ENTRY 729declares a structure that connects the elements in 730the simple queue. 731.Pp 732The macro 733.Nm SIMPLEQ_HEAD_INITIALIZER 734provides a value which can be used to initialize a simple queue head at 735compile time, and is used at the point that the simple queue head 736variable is declared, like: 737.Bd -literal -offset indent 738struct HEADNAME head = SIMPLEQ_HEAD_INITIALIZER(head); 739.Ed 740.Pp 741The macro 742.Nm SIMPLEQ_FIRST 743returns the first element of the simple queue 744.Fa head . 745.Pp 746The macro 747.Nm SIMPLEQ_EMPTY 748return true if the simple queue 749.Fa head 750has no elements. 751.Pp 752The macro 753.Nm SIMPLEQ_NEXT 754returns the element after the element 755.Fa elm . 756.Pp 757The macro 758.Nm SIMPLEQ_LAST 759returns the last item on the tail queue. 760If the tail queue is empty the return value is 761.Dv NULL . 762.Pp 763The macro 764.Nm SIMPLEQ_FOREACH 765traverses the tail queue referenced by 766.Fa head 767in the forward direction, assigning each element 768in turn to 769.Fa var . 770.Pp 771The SAFE version uses 772.Fa tmp 773to hold the next element, so 774.Fa var 775may be freed or removed from the list. 776.Pp 777The macro 778.Nm SIMPLEQ_INIT 779initializes the simple queue referenced by 780.Fa head . 781.Pp 782The macro 783.Nm SIMPLEQ_INSERT_HEAD 784inserts the new element 785.Fa elm 786at the head of the simple queue. 787.Pp 788The macro 789.Nm SIMPLEQ_INSERT_TAIL 790inserts the new element 791.Fa elm 792at the end of the simple queue. 793.Pp 794The macro 795.Nm SIMPLEQ_INSERT_AFTER 796inserts the new element 797.Fa elm 798after the element 799.Fa listelm . 800.Pp 801The macro 802.Nm SIMPLEQ_REMOVE_HEAD 803removes the first element from the head of the simple queue. 804For optimum efficiency, 805elements being removed from the head of the queue should explicitly use 806this macro instead of the generic 807.Nm SIMPLQ_REMOVE 808macro. 809.Pp 810The macro 811.Nm SIMPLEQ_REMOVE_AFTER 812removes the element after the one specified from the simple queue. 813For optimum efficiency, 814elements being removed after specified elements should explicitly use 815this macro instead of the generic 816.Nm SIMPLQ_REMOVE 817macro. 818.Pp 819The macro 820.Nm SIMPLEQ_REMOVE 821removes 822.Fa elm 823from the simple queue. 824.Pp 825The macro 826.Nm SIMPLEQ_CONCAT 827concatenates the tail queue headed by 828.Fa head2 829onto the end of the one headed by 830.Fa head1 831removing all entries from the former. 832.Pp 833.Sh SIMPLE QUEUE EXAMPLE 834.Bd -literal 835SIMPLEQ_HEAD(simplehead, entry) head; 836struct simplehead *headp; /* Simple queue head. */ 837struct entry { 838 ... 839 SIMPLEQ_ENTRY(entry) entries; /* Simple queue. */ 840 ... 841} *n1, *n2, *np; 842 843SIMPLEQ_INIT(\*[Am]head); /* Initialize the queue. */ 844 845n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 846SIMPLEQ_INSERT_HEAD(\*[Am]head, n1, entries); 847 848n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 849SIMPLEQ_INSERT_TAIL(\*[Am]head, n1, entries); 850 851n2 = malloc(sizeof(struct entry)); /* Insert after. */ 852SIMPLEQ_INSERT_AFTER(\*[Am]head, n1, n2, entries); 853 /* Forward traversal. */ 854SIMPLEQ_FOREACH(np, \*[Am]head, entries) 855 np-\*[Gt] ... 856 /* Delete. */ 857while (SIMPLEQ_FIRST(\*[Am]head) != NULL) 858 SIMPLEQ_REMOVE_HEAD(\*[Am]head, entries); 859if (SIMPLEQ_EMPTY(\*[Am]head)) /* Test for emptiness. */ 860 printf("nothing to do\\n"); 861.Ed 862.Sh TAIL QUEUES 863A tail queue is headed by a structure defined by the 864.Nm TAILQ_HEAD 865macro. 866This structure contains a pair of pointers, 867one to the first element in the tail queue and the other to 868the last element in the tail queue. 869The elements are doubly linked so that an arbitrary element can be 870removed without traversing the tail queue. 871New elements can be added to the queue after an existing element, 872before an existing element, at the head of the queue, or at the end 873the queue. 874A 875.Fa TAILQ_HEAD 876structure is declared as follows: 877.Bd -literal -offset indent 878TAILQ_HEAD(HEADNAME, TYPE) head; 879.Ed 880.Pp 881where 882.Li HEADNAME 883is the name of the structure to be defined, and 884.Li TYPE 885is the type of the elements to be linked into the tail queue. 886A pointer to the head of the tail queue can later be declared as: 887.Bd -literal -offset indent 888struct HEADNAME *headp; 889.Ed 890.Pp 891(The names 892.Li head 893and 894.Li headp 895are user selectable.) 896.Pp 897The macro 898.Nm TAILQ_ENTRY 899declares a structure that connects the elements in 900the tail queue. 901.Pp 902The macro 903.Nm TAILQ_HEAD_INITIALIZER 904provides a value which can be used to initialize a tail queue head at 905compile time, and is used at the point that the tail queue head 906variable is declared, like: 907.Bd -literal -offset indent 908struct HEADNAME head = TAILQ_HEAD_INITIALIZER(head); 909.Ed 910.Pp 911The macro 912.Nm TAILQ_FIRST 913returns the first element of the tail queue 914.Fa head . 915.Pp 916The macro 917.Nm TAILQ_NEXT 918returns the element after the element 919.Fa elm . 920.Pp 921The macro 922.Nm TAILQ_LAST 923returns the last item on the tail queue. 924If the tail queue is empty the return value is 925.Dv NULL . 926.Pp 927The macro 928.Nm TAILQ_PREV 929returns the previous item on the tail queue, from the one specified. 930If the tail queue is empty the return value is 931.Dv NULL . 932.Pp 933The macro 934.Nm TAILQ_EMPTY 935return true if the tail queue 936.Fa head 937has no elements. 938.Pp 939The macros 940.Nm TAILQ_FOREACH , 941.Nm TAILQ_FOREACH_REVERSE , 942.Nm TAILQ_FOREACH_SAFE , 943and 944.Nm TAILQ_FOREACH_REVERSE_SAFE 945traverse the tail queue referenced by 946.Fa head 947in the forward or reverse direction direction, assigning each element in turn to 948.Fa var . 949.Pp 950The SAFE versions use 951.Fa tmp 952to hold the next element, so 953.Fa var 954may be freed or removed from the list. 955.Pp 956The macro 957.Nm TAILQ_INIT 958initializes the tail queue referenced by 959.Fa head . 960.Pp 961The macro 962.Nm TAILQ_INSERT_HEAD 963inserts the new element 964.Fa elm 965at the head of the tail queue. 966.Pp 967The macro 968.Nm TAILQ_INSERT_TAIL 969inserts the new element 970.Fa elm 971at the end of the tail queue. 972.Pp 973The macro 974.Nm TAILQ_INSERT_AFTER 975inserts the new element 976.Fa elm 977after the element 978.Fa listelm . 979.Pp 980The macro 981.Nm TAILQ_INSERT_BEFORE 982inserts the new element 983.Fa elm 984before the element 985.Fa listelm . 986.Pp 987The macro 988.Nm TAILQ_REMOVE 989removes the element 990.Fa elm 991from the tail queue. 992.Pp 993The macro 994.Nm TAILQ_REPLACE 995replace the element 996.Fa elm 997with the 998.Fa new 999one specified in the tail queue. 1000.Pp 1001The macro 1002.Nm TAILQ_CONCAT 1003concatenates the tail queue headed by 1004.Fa head2 1005onto the end of the one headed by 1006.Fa head1 1007removing all entries from the former. 1008.Sh TAIL QUEUE EXAMPLE 1009.Bd -literal 1010TAILQ_HEAD(tailhead, entry) head; 1011struct tailhead *headp; /* Tail queue head. */ 1012struct entry { 1013 ... 1014 TAILQ_ENTRY(entry) entries; /* Tail queue. */ 1015 ... 1016} *n1, *n2, *np; 1017 1018TAILQ_INIT(\*[Am]head); /* Initialize the queue. */ 1019 1020n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 1021TAILQ_INSERT_HEAD(\*[Am]head, n1, entries); 1022 1023n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 1024TAILQ_INSERT_TAIL(\*[Am]head, n1, entries); 1025 1026n2 = malloc(sizeof(struct entry)); /* Insert after. */ 1027TAILQ_INSERT_AFTER(\*[Am]head, n1, n2, entries); 1028 1029n2 = malloc(sizeof(struct entry)); /* Insert before. */ 1030TAILQ_INSERT_BEFORE(n1, n2, entries); 1031 /* Forward traversal. */ 1032TAILQ_FOREACH(np, \*[Am]head, entries) 1033 np-\*[Gt] ... 1034 /* Reverse traversal. */ 1035TAILQ_FOREACH_REVERSE(np, \*[Am]head, tailhead, entries) 1036 np-\*[Gt] ... 1037 /* Delete. */ 1038while (TAILQ_FIRST(\*[Am]head) != NULL) 1039 TAILQ_REMOVE(\*[Am]head, TAILQ_FIRST(\*[Am]head), entries); 1040if (TAILQ_EMPTY(\*[Am]head)) /* Test for emptiness. */ 1041 printf("nothing to do\\n"); 1042.Ed 1043.Sh SINGLY LINKED TAIL QUEUES 1044The macros prefixed with 1045.Dq Nm STAILQ_ 1046.Nm ( STAILQ_HEAD , 1047.Nm STAILQ_HEAD_INITIALIZER , 1048.Nm STAILQ_ENTRY , 1049.Nm STAILQ_FOREACH , 1050.Nm STAILQ_FOREACH_SAFE , 1051.Nm STAILQ_FIRST , 1052.Nm STAILQ_EMPTY , 1053.Nm STAILQ_NEXT , 1054.Nm STAILQ_LAST , 1055.Nm STAILQ_INIT , 1056.Nm STAILQ_INSERT_HEAD , 1057.Nm STAILQ_INSERT_TAIL , 1058.Nm STAILQ_INSERT_AFTER , 1059.Nm STAILQ_REMOVE_HEAD , 1060.Nm STAILQ_REMOVE , 1061and 1062.Nm STAILQ_CONCAT ) 1063are functionally identical to these simple queue functions, 1064and are provided for compatibility with 1065.Fx . 1066.Sh NOTES 1067Some of these macros or functions perform no error checking, 1068and invalid usage leads to undefined behaviour. 1069In the case of macros or functions that expect their arguments 1070to be elements that are present in the list or queue, passing an element 1071that is not present is invalid. 1072.Sh HISTORY 1073The 1074.Nm queue 1075functions first appeared in 1076.Bx 4.4 . 1077The 1078.Nm SIMPLEQ 1079functions first appeared in 1080.Nx 1.2 . 1081The 1082.Nm SLIST 1083and 1084.Nm STAILQ 1085functions first appeared in 1086.Fx 2.1.5 . 1087