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