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