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