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