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