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