1.\" $NetBSD: queue.3,v 1.19 2001/06/24 01:32:29 wiz 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 <sys/queue.h> 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 four 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 351.Sh SINGLY-LINKED LISTS 352A singly-linked list is headed by a structure defined by the 353.Nm SLIST_HEAD 354macro. 355This structure contains a single pointer to the first element 356on the list. 357The elements are singly linked for minimum space and pointer manipulation 358overhead at the expense of O(n) removal for arbitrary elements. 359New elements can be added to the list after an existing element or 360at the head of the list. 361An 362.Fa SLIST_HEAD 363structure is declared as follows: 364.Bd -literal -offset indent 365SLIST_HEAD(HEADNAME, TYPE) head; 366.Ed 367.Pp 368where 369.Fa HEADNAME 370is the name of the structure to be defined, and 371.Fa TYPE 372is the type of the elements to be linked into the list. 373A pointer to the head of the list can later be declared as: 374.Bd -literal -offset indent 375struct HEADNAME *headp; 376.Ed 377.Pp 378(The names 379.Li head 380and 381.Li headp 382are user selectable.) 383.Pp 384The macro 385.Nm SLIST_HEAD_INITIALIZER 386evaluates to an initializer for the list 387.Fa head . 388.Pp 389The macro 390.Nm SLIST_EMPTY 391evaluates to true if there are no elements in the list. 392.Pp 393The macro 394.Nm SLIST_ENTRY 395declares a structure that connects the elements in 396the list. 397.Pp 398The macro 399.Nm SLIST_FIRST 400returns the first element in the list or NULL if the list is empty. 401.Pp 402The macro 403.Nm SLIST_FOREACH 404traverses the list referenced by 405.Fa head 406in the forward direction, assigning each element in 407turn to 408.Fa var . 409.Pp 410The macro 411.Nm SLIST_INIT 412initializes the list referenced by 413.Fa head . 414.Pp 415The macro 416.Nm SLIST_INSERT_HEAD 417inserts the new element 418.Fa elm 419at the head of the list. 420.Pp 421The macro 422.Nm SLIST_INSERT_AFTER 423inserts the new element 424.Fa elm 425after the element 426.Fa listelm . 427.Pp 428The macro 429.Nm SLIST_NEXT 430returns the next element in the list. 431.Pp 432The macro 433.Nm SLIST_REMOVE_HEAD 434removes the element 435.Fa elm 436from the head of the list. 437For optimum efficiency, 438elements being removed from the head of the list should explicitly use 439this macro instead of the generic 440.Fa SLIST_REMOVE 441macro. 442.Pp 443The macro 444.Nm SLIST_REMOVE 445removes the element 446.Fa elm 447from the list. 448.Sh SINGLY-LINKED LIST EXAMPLE 449.Bd -literal 450SLIST_HEAD(slisthead, entry) head = 451 SLIST_HEAD_INITIALIZER(head); 452struct slisthead *headp; /* Singly-linked List head. */ 453struct entry { 454 ... 455 SLIST_ENTRY(entry) entries; /* Singly-linked List. */ 456 ... 457} *n1, *n2, *n3, *np; 458 459SLIST_INIT(&head); /* Initialize the list. */ 460 461n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 462SLIST_INSERT_HEAD(&head, n1, entries); 463 464n2 = malloc(sizeof(struct entry)); /* Insert after. */ 465SLIST_INSERT_AFTER(n1, n2, entries); 466 467SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */ 468free(n2); 469 470n3 = SLIST_FIRST(&head); 471SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */ 472free(n3); 473 /* Forward traversal. */ 474SLIST_FOREACH(np, &head, entries) 475 np-> ... 476 477while (!SLIST_EMPTY(&head)) { /* List Deletion. */ 478 n1 = SLIST_FIRST(&head); 479 SLIST_REMOVE_HEAD(&head, entries); 480 free(n1); 481} 482.Ed 483.Sh LISTS 484A list is headed by a structure defined by the 485.Nm LIST_HEAD 486macro. 487This structure contains a single pointer to the first element 488on the list. 489The elements are doubly linked so that an arbitrary element can be 490removed without traversing the list. 491New elements can be added to the list after an existing element, 492before an existing element, or at the head of the list. 493A 494.Fa LIST_HEAD 495structure is declared as follows: 496.Bd -literal -offset indent 497LIST_HEAD(HEADNAME, TYPE) head; 498.Ed 499.sp 500where 501.Fa HEADNAME 502is the name of the structure to be defined, and 503.Fa TYPE 504is the type of the elements to be linked into the list. 505A pointer to the head of the list can later be declared as: 506.Bd -literal -offset indent 507struct HEADNAME *headp; 508.Ed 509.sp 510(The names 511.Li head 512and 513.Li headp 514are user selectable.) 515.Pp 516The macro 517.Nm LIST_ENTRY 518declares a structure that connects the elements in 519the list. 520.Pp 521The macro 522.Nm LIST_HEAD_INITIALIZER 523provides a value which can be used to initialize a list head at 524compile time, and is used at the point that the list head 525variable is declared, like: 526.Bd -literal -offset indent 527struct HEADNAME head = LIST_HEAD_INITIALIZER(head); 528.Ed 529.Pp 530The macro 531.Nm LIST_INIT 532initializes the list referenced by 533.Fa head . 534.Pp 535The macro 536.Nm LIST_INSERT_HEAD 537inserts the new element 538.Fa elm 539at the head of the list. 540.Pp 541The macro 542.Nm LIST_INSERT_AFTER 543inserts the new element 544.Fa elm 545after the element 546.Fa listelm . 547.Pp 548The macro 549.Nm LIST_INSERT_BEFORE 550inserts the new element 551.Fa elm 552before the element 553.Fa listelm . 554.Pp 555The macro 556.Nm LIST_REMOVE 557removes the element 558.Fa elm 559from the list. 560.Pp 561The macro 562.Nm LIST_EMPTY 563return true if the list 564.Fa head 565has no elements. 566.Pp 567The macro 568.Nm LIST_FIRST 569returns the first element of the list 570.Fa head . 571.Pp 572The macro 573.Nm LIST_FOREACH 574traverses the list referenced by 575.Fa head 576in the forward direction, assigning each element in turn to 577.Fa var . 578.Pp 579The macro 580.Nm LIST_NEXT 581returns the element after the element 582.Fa elm . 583.Sh LIST EXAMPLE 584.Bd -literal 585LIST_HEAD(listhead, entry) head; 586struct listhead *headp; /* List head. */ 587struct entry { 588 ... 589 LIST_ENTRY(entry) entries; /* List. */ 590 ... 591} *n1, *n2, *np; 592 593LIST_INIT(&head); /* Initialize the list. */ 594 595n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 596LIST_INSERT_HEAD(&head, n1, entries); 597 598n2 = malloc(sizeof(struct entry)); /* Insert after. */ 599LIST_INSERT_AFTER(n1, n2, entries); 600 601n2 = malloc(sizeof(struct entry)); /* Insert before. */ 602LIST_INSERT_BEFORE(n1, n2, entries); 603 /* Forward traversal. */ 604LIST_FOREACH(np, &head, entries) 605 np-> ... 606 /* Delete. */ 607while (LIST_FIRST(&head) != NULL) 608 LIST_REMOVE(LIST_FIRST(&head), entries); 609if (LIST_EMPTY(&head)) /* Test for emptiness. */ 610 printf("nothing to do\\n"); 611.Ed 612.Sh SIMPLE QUEUES 613A simple queue is headed by a structure defined by the 614.Nm SIMPLEQ_HEAD 615macro. 616This structure contains a pair of pointers, 617one to the first element in the simple queue and the other to 618the last element in the simple queue. 619New elements can be added to the queue after an existing element, 620at the head of the queue, or at the end of the queue. 621A 622.Fa SIMPLEQ_HEAD 623structure is declared as follows: 624.Bd -literal -offset indent 625SIMPLEQ_HEAD(HEADNAME, TYPE) head; 626.Ed 627.sp 628where 629.Li HEADNAME 630is the name of the structure to be defined, and 631.Li TYPE 632is the type of the elements to be linked into the simple queue. 633A pointer to the head of the simple queue can later be declared as: 634.Bd -literal -offset indent 635struct HEADNAME *headp; 636.Ed 637.sp 638(The names 639.Li head 640and 641.Li headp 642are user selectable.) 643.Pp 644The macro 645.Nm SIMPLEQ_ENTRY 646declares a structure that connects the elements in 647the simple queue. 648.Pp 649The macro 650.Nm SIMPLEQ_HEAD_INITIALIZER 651provides a value which can be used to initialize a simple queue head at 652compile time, and is used at the point that the simple queue head 653variable is declared, like: 654.Bd -literal -offset indent 655struct HEADNAME head = SIMPLEQ_HEAD_INITIALIZER(head); 656.Ed 657.Pp 658The macro 659.Nm SIMPLEQ_INIT 660initializes the simple queue referenced by 661.Fa head . 662.Pp 663The macro 664.Nm SIMPLEQ_INSERT_HEAD 665inserts the new element 666.Fa elm 667at the head of the simple queue. 668.Pp 669The macro 670.Nm SIMPLEQ_INSERT_TAIL 671inserts the new element 672.Fa elm 673at the end of the simple queue. 674.Pp 675The macro 676.Nm SIMPLEQ_INSERT_AFTER 677inserts the new element 678.Fa elm 679after the element 680.Fa listelm . 681.Pp 682The macro 683.Nm SIMPLEQ_REMOVE_HEAD 684removes the first element from the simple queue. 685.Pp 686The macro 687.Nm SIMPLEQ_EMPTY 688return true if the simple queue 689.Fa head 690has no elements. 691.Pp 692The macro 693.Nm SIMPLEQ_FIRST 694returns the first element of the simple queue 695.Fa head . 696.Pp 697The macro 698.Nm SIMPLEQ_FOREACH 699traverses the tail queue referenced by 700.Fa head 701in the forward direction, assigning each element 702in turn to 703.Fa var . 704.Pp 705The macro 706.Nm SIMPLEQ_NEXT 707returns the element after the element 708.Fa elm . 709.Sh SIMPLE QUEUE EXAMPLE 710.Bd -literal 711SIMPLEQ_HEAD(simplehead, entry) head; 712struct simplehead *headp; /* Simple queue head. */ 713struct entry { 714 ... 715 SIMPLEQ_ENTRY(entry) entries; /* Simple queue. */ 716 ... 717} *n1, *n2, *np; 718 719SIMPLEQ_INIT(&head); /* Initialize the queue. */ 720 721n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 722SIMPLEQ_INSERT_HEAD(&head, n1, entries); 723 724n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 725SIMPLEQ_INSERT_TAIL(&head, n1, entries); 726 727n2 = malloc(sizeof(struct entry)); /* Insert after. */ 728SIMPLEQ_INSERT_AFTER(&head, n1, n2, entries); 729 /* Forward traversal. */ 730SIMPLEQ_FOREACH(np, &head, entries) 731 np-> ... 732 /* Delete. */ 733while (SIMPLEQ_FIRST(&head) != NULL) 734 SIMPLEQ_REMOVE_HEAD(&head, SIMPLEQ_FIRST(&head), entries); 735if (SIMPLEQ_EMPTY(&head)) /* Test for emptiness. */ 736 printf("nothing to do\\n"); 737.Ed 738.Sh TAIL QUEUES 739A tail queue is headed by a structure defined by the 740.Nm TAILQ_HEAD 741macro. 742This structure contains a pair of pointers, 743one to the first element in the tail queue and the other to 744the last element in the tail queue. 745The elements are doubly linked so that an arbitrary element can be 746removed without traversing the tail queue. 747New elements can be added to the queue after an existing element, 748before an existing element, at the head of the queue, or at the end 749the queue. 750A 751.Fa TAILQ_HEAD 752structure is declared as follows: 753.Bd -literal -offset indent 754TAILQ_HEAD(HEADNAME, TYPE) head; 755.Ed 756.sp 757where 758.Li HEADNAME 759is the name of the structure to be defined, and 760.Li TYPE 761is the type of the elements to be linked into the tail queue. 762A pointer to the head of the tail queue can later be declared as: 763.Bd -literal -offset indent 764struct HEADNAME *headp; 765.Ed 766.sp 767(The names 768.Li head 769and 770.Li headp 771are user selectable.) 772.Pp 773The macro 774.Nm TAILQ_ENTRY 775declares a structure that connects the elements in 776the tail queue. 777.Pp 778The macro 779.Nm TAILQ_HEAD_INITIALIZER 780provides a value which can be used to initialize a tail queue head at 781compile time, and is used at the point that the tail queue head 782variable is declared, like: 783.Bd -literal -offset indent 784struct HEADNAME head = TAILQ_HEAD_INITIALIZER(head); 785.Ed 786.Pp 787The macro 788.Nm TAILQ_INIT 789initializes the tail queue referenced by 790.Fa head . 791.Pp 792The macro 793.Nm TAILQ_INSERT_HEAD 794inserts the new element 795.Fa elm 796at the head of the tail queue. 797.Pp 798The macro 799.Nm TAILQ_INSERT_TAIL 800inserts the new element 801.Fa elm 802at the end of the tail queue. 803.Pp 804The macro 805.Nm TAILQ_INSERT_AFTER 806inserts the new element 807.Fa elm 808after the element 809.Fa listelm . 810.Pp 811The macro 812.Nm TAILQ_INSERT_BEFORE 813inserts the new element 814.Fa elm 815before the element 816.Fa listelm . 817.Pp 818The macro 819.Nm TAILQ_REMOVE 820removes the element 821.Fa elm 822from the tail queue. 823.Pp 824The macro 825.Nm TAILQ_EMPTY 826return true if the tail queue 827.Fa head 828has no elements. 829.Pp 830The macro 831.Nm TAILQ_FIRST 832returns the first element of the tail queue 833.Fa head . 834.Pp 835The macro 836.Nm TAILQ_FOREACH 837traverses the tail queue referenced by 838.Fa head 839in the forward direction, assigning each element in turn to 840.Fa var . 841.Pp 842The macro 843.Nm TAILQ_FOREACH_REVERSE 844traverses the tail queue referenced by 845.Fa head 846in the reverse direction, assigning each element in turn to 847.Fa var . 848.Pp 849The macro 850.Nm TAILQ_NEXT 851returns the element after the element 852.Fa elm . 853.Sh TAIL QUEUE EXAMPLE 854.Bd -literal 855TAILQ_HEAD(tailhead, entry) head; 856struct tailhead *headp; /* Tail queue head. */ 857struct entry { 858 ... 859 TAILQ_ENTRY(entry) entries; /* Tail queue. */ 860 ... 861} *n1, *n2, *np; 862 863TAILQ_INIT(&head); /* Initialize the queue. */ 864 865n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 866TAILQ_INSERT_HEAD(&head, n1, entries); 867 868n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 869TAILQ_INSERT_TAIL(&head, n1, entries); 870 871n2 = malloc(sizeof(struct entry)); /* Insert after. */ 872TAILQ_INSERT_AFTER(&head, n1, n2, entries); 873 874n2 = malloc(sizeof(struct entry)); /* Insert before. */ 875TAILQ_INSERT_BEFORE(n1, n2, entries); 876 /* Forward traversal. */ 877TAILQ_FOREACH(np, &head, entries) 878 np-> ... 879 /* Reverse traversal. */ 880TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries) 881 np-> ... 882 /* Delete. */ 883while (TAILQ_FIRST(&head) != NULL) 884 TAILQ_REMOVE(&head, TAILQ_FIRST(&head), entries); 885if (TAILQ_EMPTY(&head)) /* Test for emptiness. */ 886 printf("nothing to do\\n"); 887.Ed 888.Sh CIRCULAR QUEUES 889A circular queue is headed by a structure defined by the 890.Nm CIRCLEQ_HEAD 891macro. 892This structure contains a pair of pointers, 893one to the first element in the circular queue and the other to the 894last element in the circular queue. 895The elements are doubly linked so that an arbitrary element can be 896removed without traversing the queue. 897New elements can be added to the queue after an existing element, 898before an existing element, at the head of the queue, or at the end 899of the queue. 900A 901.Fa CIRCLEQ_HEAD 902structure is declared as follows: 903.Bd -literal -offset indent 904CIRCLEQ_HEAD(HEADNAME, TYPE) head; 905.Ed 906.sp 907where 908.Li HEADNAME 909is the name of the structure to be defined, and 910.Li TYPE 911is the type of the elements to be linked into the circular queue. 912A pointer to the head of the circular queue can later be declared as: 913.Bd -literal -offset indent 914struct HEADNAME *headp; 915.Ed 916.sp 917(The names 918.Li head 919and 920.Li headp 921are user selectable.) 922.Pp 923The macro 924.Nm CIRCLEQ_ENTRY 925declares a structure that connects the elements in 926the circular queue. 927.Pp 928The macro 929.Nm CIRCLEQ_HEAD_INITIALIZER 930provides a value which can be used to initialize a circular queue head at 931compile time, and is used at the point that the circular queue head 932variable is declared, like: 933.Bd -literal -offset indent 934struct HEADNAME head = CIRCLEQ_HEAD_INITIALIZER(head); 935.Ed 936.Pp 937The macro 938.Nm CIRCLEQ_INIT 939initializes the circular queue referenced by 940.Fa head . 941.Pp 942The macro 943.Nm CIRCLEQ_INSERT_HEAD 944inserts the new element 945.Fa elm 946at the head of the circular queue. 947.Pp 948The macro 949.Nm CIRCLEQ_INSERT_TAIL 950inserts the new element 951.Fa elm 952at the end of the circular queue. 953.Pp 954The macro 955.Nm CIRCLEQ_INSERT_AFTER 956inserts the new element 957.Fa elm 958after the element 959.Fa listelm . 960.Pp 961The macro 962.Nm CIRCLEQ_INSERT_BEFORE 963inserts the new element 964.Fa elm 965before the element 966.Fa listelm . 967.Pp 968The macro 969.Nm CIRCLEQ_REMOVE 970removes the element 971.Fa elm 972from the circular queue. 973.Pp 974The macro 975.Nm CIRCLEQ_EMPTY 976return true if the circular queue 977.Fa head 978has no elements. 979.Pp 980The macro 981.Nm CIRCLEQ_FIRST 982returns the first element of the circular queue 983.Fa head . 984.Pp 985The macro 986.Nm CICRLEQ_FOREACH 987traverses the circle queue referenced by 988.Fa head 989in the forward direction, assigning each element in turn to 990.Fa var . 991.Pp 992The macro 993.Nm CICRLEQ_FOREACH_REVERSE 994traverses the circle queue referenced by 995.Fa head 996in the reverse direction, assigning each element in turn to 997.Fa var . 998.Pp 999The macro 1000.Nm CIRCLEQ_LAST 1001returns the last element of the circular queue 1002.Fa head . 1003.Pp 1004The macro 1005.Nm CIRCLEQ_NEXT 1006returns the element after the element 1007.Fa elm . 1008.Pp 1009The macro 1010.Nm CIRCLEQ_PREV 1011returns the element before the element 1012.Fa elm . 1013.Sh CIRCULAR QUEUE EXAMPLE 1014.Bd -literal 1015CIRCLEQ_HEAD(circleq, entry) head; 1016struct circleq *headp; /* Circular queue head. */ 1017struct entry { 1018 ... 1019 CIRCLEQ_ENTRY entries; /* Circular queue. */ 1020 ... 1021} *n1, *n2, *np; 1022 1023CIRCLEQ_INIT(&head); /* Initialize the circular queue. */ 1024 1025n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 1026CIRCLEQ_INSERT_HEAD(&head, n1, entries); 1027 1028n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 1029CIRCLEQ_INSERT_TAIL(&head, n1, entries); 1030 1031n2 = malloc(sizeof(struct entry)); /* Insert after. */ 1032CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries); 1033 1034n2 = malloc(sizeof(struct entry)); /* Insert before. */ 1035CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries); 1036 /* Forward traversal. */ 1037CIRCLEQ_FOREACH(np, &head, entries) 1038 np-> ... 1039 /* Reverse traversal. */ 1040CIRCLEQ_FOREACH_REVERSE(np, &head, entries) 1041 np-> ... 1042 /* Delete. */ 1043while (CIRCLEQ_FIRST(&head) != (void *)&head) 1044 CIRCLEQ_REMOVE(&head, CIRCLEQ_FIRST(&head), entries); 1045if (CIRCLEQ_EMPTY(&head)) /* Test for emptiness. */ 1046 printf("nothing to do\\n"); 1047.Ed 1048.Sh HISTORY 1049The 1050.Nm queue 1051functions first appeared in 1052.Bx 4.4 . 1053The 1054.Nm SIMPLEQ 1055functions first appeared in 1056.Nx 1.2 . 1057