1.\" $NetBSD: queue.3,v 1.33 2006/03/07 18:13:43 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 March 7, 2006 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.Sh SINGLY-LINKED LISTS 389A singly-linked list is headed by a structure defined by the 390.Nm SLIST_HEAD 391macro. 392This structure contains a single pointer to the first element 393on the list. 394The elements are singly linked for minimum space and pointer manipulation 395overhead at the expense of O(n) removal for arbitrary elements. 396New elements can be added to the list after an existing element or 397at the head of the list. 398An 399.Fa SLIST_HEAD 400structure is declared as follows: 401.Bd -literal -offset indent 402SLIST_HEAD(HEADNAME, TYPE) head; 403.Ed 404.Pp 405where 406.Fa HEADNAME 407is the name of the structure to be defined, and 408.Fa TYPE 409is the type of the elements to be linked into the list. 410A pointer to the head of the list can later be declared as: 411.Bd -literal -offset indent 412struct HEADNAME *headp; 413.Ed 414.Pp 415(The names 416.Li head 417and 418.Li headp 419are user selectable.) 420.Pp 421The macro 422.Nm SLIST_HEAD_INITIALIZER 423evaluates to an initializer for the list 424.Fa head . 425.Pp 426The macro 427.Nm SLIST_EMPTY 428evaluates to true if there are no elements in the list. 429.Pp 430The macro 431.Nm SLIST_ENTRY 432declares a structure that connects the elements in 433the list. 434.Pp 435The macro 436.Nm SLIST_FIRST 437returns the first element in the list or NULL if the list is empty. 438.Pp 439The macro 440.Nm SLIST_FOREACH 441traverses the list referenced by 442.Fa head 443in the forward direction, assigning each element in 444turn to 445.Fa var . 446.Pp 447The macro 448.Nm SLIST_INIT 449initializes the list referenced by 450.Fa head . 451.Pp 452The macro 453.Nm SLIST_INSERT_HEAD 454inserts the new element 455.Fa elm 456at the head of the list. 457.Pp 458The macro 459.Nm SLIST_INSERT_AFTER 460inserts the new element 461.Fa elm 462after the element 463.Fa listelm . 464.Pp 465The macro 466.Nm SLIST_NEXT 467returns the next element in the list. 468.Pp 469The macro 470.Nm SLIST_REMOVE 471removes the element 472.Fa elm 473from the list. 474.Pp 475The macro 476.Nm SLIST_REMOVE_HEAD 477removes the first element from the head of the list. 478For optimum efficiency, 479elements being removed from the head of the list should explicitly use 480this macro instead of the generic 481.Nm SLIST_REMOVE 482macro. 483.Sh SINGLY-LINKED LIST EXAMPLE 484.Bd -literal 485SLIST_HEAD(slisthead, entry) head = 486 SLIST_HEAD_INITIALIZER(head); 487struct slisthead *headp; /* Singly-linked List head. */ 488struct entry { 489 ... 490 SLIST_ENTRY(entry) entries; /* Singly-linked List. */ 491 ... 492} *n1, *n2, *n3, *np; 493 494SLIST_INIT(\*[Am]head); /* Initialize the list. */ 495 496n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 497SLIST_INSERT_HEAD(\*[Am]head, n1, entries); 498 499n2 = malloc(sizeof(struct entry)); /* Insert after. */ 500SLIST_INSERT_AFTER(n1, n2, entries); 501 502SLIST_REMOVE(\*[Am]head, n2, entry, entries);/* Deletion. */ 503free(n2); 504 505n3 = SLIST_FIRST(\*[Am]head); 506SLIST_REMOVE_HEAD(\*[Am]head, entries); /* Deletion from the head. */ 507free(n3); 508 /* Forward traversal. */ 509SLIST_FOREACH(np, \*[Am]head, entries) 510 np-\*[Gt] ... 511 512while (!SLIST_EMPTY(\*[Am]head)) { /* List Deletion. */ 513 n1 = SLIST_FIRST(\*[Am]head); 514 SLIST_REMOVE_HEAD(\*[Am]head, entries); 515 free(n1); 516} 517.Ed 518.Sh SIMPLE QUEUES 519A simple queue is headed by a structure defined by the 520.Nm SIMPLEQ_HEAD 521macro. 522This structure contains a pair of pointers, 523one to the first element in the simple queue and the other to 524the last element in the simple queue. 525The elements are singly linked for minimum space and pointer manipulation 526overhead at the expense of O(n) removal for arbitrary elements. 527New elements can be added to the queue after an existing element, 528at the head of the queue, or at the end of the queue. 529A 530.Fa SIMPLEQ_HEAD 531structure is declared as follows: 532.Bd -literal -offset indent 533SIMPLEQ_HEAD(HEADNAME, TYPE) head; 534.Ed 535.sp 536where 537.Li HEADNAME 538is the name of the structure to be defined, and 539.Li TYPE 540is the type of the elements to be linked into the simple queue. 541A pointer to the head of the simple queue can later be declared as: 542.Bd -literal -offset indent 543struct HEADNAME *headp; 544.Ed 545.sp 546(The names 547.Li head 548and 549.Li headp 550are user selectable.) 551.Pp 552The macro 553.Nm SIMPLEQ_ENTRY 554declares a structure that connects the elements in 555the simple queue. 556.Pp 557The macro 558.Nm SIMPLEQ_HEAD_INITIALIZER 559provides a value which can be used to initialize a simple queue head at 560compile time, and is used at the point that the simple queue head 561variable is declared, like: 562.Bd -literal -offset indent 563struct HEADNAME head = SIMPLEQ_HEAD_INITIALIZER(head); 564.Ed 565.Pp 566The macro 567.Nm SIMPLEQ_INIT 568initializes the simple queue referenced by 569.Fa head . 570.Pp 571The macro 572.Nm SIMPLEQ_INSERT_HEAD 573inserts the new element 574.Fa elm 575at the head of the simple queue. 576.Pp 577The macro 578.Nm SIMPLEQ_INSERT_TAIL 579inserts the new element 580.Fa elm 581at the end of the simple queue. 582.Pp 583The macro 584.Nm SIMPLEQ_INSERT_AFTER 585inserts the new element 586.Fa elm 587after the element 588.Fa listelm . 589.Pp 590The macro 591.Nm SIMPLEQ_REMOVE 592removes 593.Fa elm 594from the simple queue. 595.Pp 596The macro 597.Nm SIMPLEQ_REMOVE_HEAD 598removes the first element from the head of the simple queue. 599For optimum efficiency, 600elements being removed from the head of the queue should explicitly use 601this macro instead of the generic 602.Nm SIMPLQ_REMOVE 603macro. 604.Pp 605The macro 606.Nm SIMPLEQ_EMPTY 607return true if the simple queue 608.Fa head 609has no elements. 610.Pp 611The macro 612.Nm SIMPLEQ_FIRST 613returns the first element of the simple queue 614.Fa head . 615.Pp 616The macro 617.Nm SIMPLEQ_FOREACH 618traverses the tail queue referenced by 619.Fa head 620in the forward direction, assigning each element 621in turn to 622.Fa var . 623.Pp 624The macro 625.Nm SIMPLEQ_NEXT 626returns the element after the element 627.Fa elm . 628.Pp 629The macros prefixed with 630.Dq Nm STAILQ_ 631.Nm ( STAILQ_HEAD , 632.Nm STAILQ_HEAD_INITIALIZER , 633.Nm STAILQ_ENTRY , 634.Nm STAILQ_INIT , 635.Nm STAILQ_INSERT_HEAD , 636.Nm STAILQ_INSERT_TAIL , 637.Nm STAILQ_INSERT_AFTER , 638.Nm STAILQ_REMOVE_HEAD , 639.Nm STAILQ_REMOVE , 640.Nm STAILQ_FOREACH , 641.Nm STAILQ_EMPTY , 642.Nm STAILQ_FIRST , 643and 644.Nm STAILQ_NEXT ) 645are functionally identical to these simple queue functions, 646and are provided for compatibility with 647.Fx . 648.Sh SIMPLE QUEUE EXAMPLE 649.Bd -literal 650SIMPLEQ_HEAD(simplehead, entry) head; 651struct simplehead *headp; /* Simple queue head. */ 652struct entry { 653 ... 654 SIMPLEQ_ENTRY(entry) entries; /* Simple queue. */ 655 ... 656} *n1, *n2, *np; 657 658SIMPLEQ_INIT(\*[Am]head); /* Initialize the queue. */ 659 660n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 661SIMPLEQ_INSERT_HEAD(\*[Am]head, n1, entries); 662 663n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 664SIMPLEQ_INSERT_TAIL(\*[Am]head, n1, entries); 665 666n2 = malloc(sizeof(struct entry)); /* Insert after. */ 667SIMPLEQ_INSERT_AFTER(\*[Am]head, n1, n2, entries); 668 /* Forward traversal. */ 669SIMPLEQ_FOREACH(np, \*[Am]head, entries) 670 np-\*[Gt] ... 671 /* Delete. */ 672while (SIMPLEQ_FIRST(\*[Am]head) != NULL) 673 SIMPLEQ_REMOVE_HEAD(\*[Am]head, entries); 674if (SIMPLEQ_EMPTY(\*[Am]head)) /* Test for emptiness. */ 675 printf("nothing to do\\n"); 676.Ed 677.Sh LISTS 678A list is headed by a structure defined by the 679.Nm LIST_HEAD 680macro. 681This structure contains a single pointer to the first element 682on the list. 683The elements are doubly linked so that an arbitrary element can be 684removed without traversing the list. 685New elements can be added to the list after an existing element, 686before an existing element, or at the head of the list. 687A 688.Fa LIST_HEAD 689structure is declared as follows: 690.Bd -literal -offset indent 691LIST_HEAD(HEADNAME, TYPE) head; 692.Ed 693.sp 694where 695.Fa HEADNAME 696is the name of the structure to be defined, and 697.Fa TYPE 698is the type of the elements to be linked into the list. 699A pointer to the head of the list can later be declared as: 700.Bd -literal -offset indent 701struct HEADNAME *headp; 702.Ed 703.sp 704(The names 705.Li head 706and 707.Li headp 708are user selectable.) 709.Pp 710The macro 711.Nm LIST_ENTRY 712declares a structure that connects the elements in 713the list. 714.Pp 715The macro 716.Nm LIST_HEAD_INITIALIZER 717provides a value which can be used to initialize a list head at 718compile time, and is used at the point that the list head 719variable is declared, like: 720.Bd -literal -offset indent 721struct HEADNAME head = LIST_HEAD_INITIALIZER(head); 722.Ed 723.Pp 724The macro 725.Nm LIST_INIT 726initializes the list referenced by 727.Fa head . 728.Pp 729The macro 730.Nm LIST_INSERT_HEAD 731inserts the new element 732.Fa elm 733at the head of the list. 734.Pp 735The macro 736.Nm LIST_INSERT_AFTER 737inserts the new element 738.Fa elm 739after the element 740.Fa listelm . 741.Pp 742The macro 743.Nm LIST_INSERT_BEFORE 744inserts the new element 745.Fa elm 746before the element 747.Fa listelm . 748.Pp 749The macro 750.Nm LIST_REMOVE 751removes the element 752.Fa elm 753from the list. 754.Pp 755The macro 756.Nm LIST_EMPTY 757return true if the list 758.Fa head 759has no elements. 760.Pp 761The macro 762.Nm LIST_FIRST 763returns the first element of the list 764.Fa head . 765.Pp 766The macro 767.Nm LIST_FOREACH 768traverses the list referenced by 769.Fa head 770in the forward direction, assigning each element in turn to 771.Fa var . 772.Pp 773The macro 774.Nm LIST_NEXT 775returns the element after the element 776.Fa elm . 777.Sh LIST EXAMPLE 778.Bd -literal 779LIST_HEAD(listhead, entry) head; 780struct listhead *headp; /* List head. */ 781struct entry { 782 ... 783 LIST_ENTRY(entry) entries; /* List. */ 784 ... 785} *n1, *n2, *np; 786 787LIST_INIT(\*[Am]head); /* Initialize the list. */ 788 789n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 790LIST_INSERT_HEAD(\*[Am]head, n1, entries); 791 792n2 = malloc(sizeof(struct entry)); /* Insert after. */ 793LIST_INSERT_AFTER(n1, n2, entries); 794 795n2 = malloc(sizeof(struct entry)); /* Insert before. */ 796LIST_INSERT_BEFORE(n1, n2, entries); 797 /* Forward traversal. */ 798LIST_FOREACH(np, \*[Am]head, entries) 799 np-\*[Gt] ... 800 /* Delete. */ 801while (LIST_FIRST(\*[Am]head) != NULL) 802 LIST_REMOVE(LIST_FIRST(\*[Am]head), entries); 803if (LIST_EMPTY(\*[Am]head)) /* Test for emptiness. */ 804 printf("nothing to do\\n"); 805.Ed 806.Sh TAIL QUEUES 807A tail queue is headed by a structure defined by the 808.Nm TAILQ_HEAD 809macro. 810This structure contains a pair of pointers, 811one to the first element in the tail queue and the other to 812the last element in the tail queue. 813The elements are doubly linked so that an arbitrary element can be 814removed without traversing the tail queue. 815New elements can be added to the queue after an existing element, 816before an existing element, at the head of the queue, or at the end 817the queue. 818A 819.Fa TAILQ_HEAD 820structure is declared as follows: 821.Bd -literal -offset indent 822TAILQ_HEAD(HEADNAME, TYPE) head; 823.Ed 824.sp 825where 826.Li HEADNAME 827is the name of the structure to be defined, and 828.Li TYPE 829is the type of the elements to be linked into the tail queue. 830A pointer to the head of the tail queue can later be declared as: 831.Bd -literal -offset indent 832struct HEADNAME *headp; 833.Ed 834.sp 835(The names 836.Li head 837and 838.Li headp 839are user selectable.) 840.Pp 841The macro 842.Nm TAILQ_ENTRY 843declares a structure that connects the elements in 844the tail queue. 845.Pp 846The macro 847.Nm TAILQ_HEAD_INITIALIZER 848provides a value which can be used to initialize a tail queue head at 849compile time, and is used at the point that the tail queue head 850variable is declared, like: 851.Bd -literal -offset indent 852struct HEADNAME head = TAILQ_HEAD_INITIALIZER(head); 853.Ed 854.Pp 855The macro 856.Nm TAILQ_INIT 857initializes the tail queue referenced by 858.Fa head . 859.Pp 860The macro 861.Nm TAILQ_INSERT_HEAD 862inserts the new element 863.Fa elm 864at the head of the tail queue. 865.Pp 866The macro 867.Nm TAILQ_INSERT_TAIL 868inserts the new element 869.Fa elm 870at the end of the tail queue. 871.Pp 872The macro 873.Nm TAILQ_INSERT_AFTER 874inserts the new element 875.Fa elm 876after the element 877.Fa listelm . 878.Pp 879The macro 880.Nm TAILQ_INSERT_BEFORE 881inserts the new element 882.Fa elm 883before the element 884.Fa listelm . 885.Pp 886The macro 887.Nm TAILQ_REMOVE 888removes the element 889.Fa elm 890from the tail queue. 891.Pp 892The macro 893.Nm TAILQ_EMPTY 894return true if the tail queue 895.Fa head 896has no elements. 897.Pp 898The macro 899.Nm TAILQ_FIRST 900returns the first element of the tail queue 901.Fa head . 902.Pp 903The macro 904.Nm TAILQ_FOREACH 905traverses the tail queue referenced by 906.Fa head 907in the forward direction, assigning each element in turn to 908.Fa var . 909.Pp 910The macro 911.Nm TAILQ_FOREACH_REVERSE 912traverses the tail queue referenced by 913.Fa head 914in the reverse direction, assigning each element in turn to 915.Fa var . 916.Pp 917The macro 918.Nm TAILQ_NEXT 919returns the element after the element 920.Fa elm . 921.Sh TAIL QUEUE EXAMPLE 922.Bd -literal 923TAILQ_HEAD(tailhead, entry) head; 924struct tailhead *headp; /* Tail queue head. */ 925struct entry { 926 ... 927 TAILQ_ENTRY(entry) entries; /* Tail queue. */ 928 ... 929} *n1, *n2, *np; 930 931TAILQ_INIT(\*[Am]head); /* Initialize the queue. */ 932 933n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 934TAILQ_INSERT_HEAD(\*[Am]head, n1, entries); 935 936n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 937TAILQ_INSERT_TAIL(\*[Am]head, n1, entries); 938 939n2 = malloc(sizeof(struct entry)); /* Insert after. */ 940TAILQ_INSERT_AFTER(\*[Am]head, n1, n2, entries); 941 942n2 = malloc(sizeof(struct entry)); /* Insert before. */ 943TAILQ_INSERT_BEFORE(n1, n2, entries); 944 /* Forward traversal. */ 945TAILQ_FOREACH(np, \*[Am]head, entries) 946 np-\*[Gt] ... 947 /* Reverse traversal. */ 948TAILQ_FOREACH_REVERSE(np, \*[Am]head, tailhead, entries) 949 np-\*[Gt] ... 950 /* Delete. */ 951while (TAILQ_FIRST(\*[Am]head) != NULL) 952 TAILQ_REMOVE(\*[Am]head, TAILQ_FIRST(\*[Am]head), entries); 953if (TAILQ_EMPTY(\*[Am]head)) /* Test for emptiness. */ 954 printf("nothing to do\\n"); 955.Ed 956.Sh CIRCULAR QUEUES 957A circular queue is headed by a structure defined by the 958.Nm CIRCLEQ_HEAD 959macro. 960This structure contains a pair of pointers, 961one to the first element in the circular queue and the other to the 962last element in the circular queue. 963The elements are doubly linked so that an arbitrary element can be 964removed without traversing the queue. 965New elements can be added to the queue after an existing element, 966before an existing element, at the head of the queue, or at the end 967of the queue. 968A 969.Fa CIRCLEQ_HEAD 970structure is declared as follows: 971.Bd -literal -offset indent 972CIRCLEQ_HEAD(HEADNAME, TYPE) head; 973.Ed 974.sp 975where 976.Li HEADNAME 977is the name of the structure to be defined, and 978.Li TYPE 979is the type of the elements to be linked into the circular queue. 980A pointer to the head of the circular queue can later be declared as: 981.Bd -literal -offset indent 982struct HEADNAME *headp; 983.Ed 984.sp 985(The names 986.Li head 987and 988.Li headp 989are user selectable.) 990.Pp 991The macro 992.Nm CIRCLEQ_ENTRY 993declares a structure that connects the elements in 994the circular queue. 995.Pp 996The macro 997.Nm CIRCLEQ_HEAD_INITIALIZER 998provides a value which can be used to initialize a circular queue head at 999compile time, and is used at the point that the circular queue head 1000variable is declared, like: 1001.Bd -literal -offset indent 1002struct HEADNAME head = CIRCLEQ_HEAD_INITIALIZER(head); 1003.Ed 1004.Pp 1005The macro 1006.Nm CIRCLEQ_INIT 1007initializes the circular queue referenced by 1008.Fa head . 1009.Pp 1010The macro 1011.Nm CIRCLEQ_INSERT_HEAD 1012inserts the new element 1013.Fa elm 1014at the head of the circular queue. 1015.Pp 1016The macro 1017.Nm CIRCLEQ_INSERT_TAIL 1018inserts the new element 1019.Fa elm 1020at the end of the circular queue. 1021.Pp 1022The macro 1023.Nm CIRCLEQ_INSERT_AFTER 1024inserts the new element 1025.Fa elm 1026after the element 1027.Fa listelm . 1028.Pp 1029The macro 1030.Nm CIRCLEQ_INSERT_BEFORE 1031inserts the new element 1032.Fa elm 1033before the element 1034.Fa listelm . 1035.Pp 1036The macro 1037.Nm CIRCLEQ_REMOVE 1038removes the element 1039.Fa elm 1040from the circular queue. 1041.Pp 1042The macro 1043.Nm CIRCLEQ_EMPTY 1044return true if the circular queue 1045.Fa head 1046has no elements. 1047.Pp 1048The macro 1049.Nm CIRCLEQ_FIRST 1050returns the first element of the circular queue 1051.Fa head . 1052.Pp 1053The macro 1054.Nm CIRCLEQ_FOREACH 1055traverses the circle queue referenced by 1056.Fa head 1057in the forward direction, assigning each element in turn to 1058.Fa var . 1059Each element is assigned exactly once. 1060.Pp 1061The macro 1062.Nm CIRCLEQ_FOREACH_REVERSE 1063traverses the circle queue referenced by 1064.Fa head 1065in the reverse direction, assigning each element in turn to 1066.Fa var . 1067Each element is assigned exactly once. 1068.Pp 1069The macro 1070.Nm CIRCLEQ_LAST 1071returns the last element of the circular queue 1072.Fa head . 1073.Pp 1074The macro 1075.Nm CIRCLEQ_NEXT 1076returns the element after the element 1077.Fa elm . 1078.Pp 1079The macro 1080.Nm CIRCLEQ_PREV 1081returns the element before the element 1082.Fa elm . 1083.Pp 1084The macro 1085.Nm CIRCLEQ_LOOP_NEXT 1086returns the element after the element 1087.Fa elm . 1088If 1089.Fa elm 1090was the last element in the queue, the first element is returned. 1091.Pp 1092The macro 1093.Nm CIRCLEQ_LOOP_PREV 1094returns the element before the element 1095.Fa elm . 1096If 1097.Fa elm 1098was the first element in the queue, the last element is returned. 1099.Sh CIRCULAR QUEUE EXAMPLE 1100.Bd -literal 1101CIRCLEQ_HEAD(circleq, entry) head; 1102struct circleq *headp; /* Circular queue head. */ 1103struct entry { 1104 ... 1105 CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */ 1106 ... 1107} *n1, *n2, *np; 1108 1109CIRCLEQ_INIT(\*[Am]head); /* Initialize the circular queue. */ 1110 1111n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 1112CIRCLEQ_INSERT_HEAD(\*[Am]head, n1, entries); 1113 1114n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 1115CIRCLEQ_INSERT_TAIL(\*[Am]head, n1, entries); 1116 1117n2 = malloc(sizeof(struct entry)); /* Insert after. */ 1118CIRCLEQ_INSERT_AFTER(\*[Am]head, n1, n2, entries); 1119 1120n2 = malloc(sizeof(struct entry)); /* Insert before. */ 1121CIRCLEQ_INSERT_BEFORE(\*[Am]head, n1, n2, entries); 1122 /* Forward traversal. */ 1123CIRCLEQ_FOREACH(np, \*[Am]head, entries) 1124 np-\*[Gt] ... 1125 /* Reverse traversal. */ 1126CIRCLEQ_FOREACH_REVERSE(np, \*[Am]head, entries) 1127 np-\*[Gt] ... 1128 /* Delete. */ 1129while (CIRCLEQ_FIRST(\*[Am]head) != (void *)\*[Am]head) 1130 CIRCLEQ_REMOVE(\*[Am]head, CIRCLEQ_FIRST(\*[Am]head), entries); 1131if (CIRCLEQ_EMPTY(\*[Am]head)) /* Test for emptiness. */ 1132 printf("nothing to do\\n"); 1133.Ed 1134.Sh HISTORY 1135The 1136.Nm queue 1137functions first appeared in 1138.Bx 4.4 . 1139The 1140.Nm SIMPLEQ 1141functions first appeared in 1142.Nx 1.2 . 1143The 1144.Nm SLIST 1145and 1146.Nm STAILQ 1147functions first appeared in 1148.Fx 2.1.5 . 1149