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