1.\" $NetBSD: queue.3,v 1.16 2000/07/20 03:19:18 deberg 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 elemement 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. 619The elements are doubly linked so that an arbitrary element can be 620removed without traversing the simple queue. 621New elements can be added to the queue after an existing element, 622before an existing element, at the head of the queue, or at the end 623the queue. 624A 625.Fa SIMPLEQ_HEAD 626structure is declared as follows: 627.Bd -literal -offset indent 628SIMPLEQ_HEAD(HEADNAME, TYPE) head; 629.Ed 630.sp 631where 632.Li HEADNAME 633is the name of the structure to be defined, and 634.Li TYPE 635is the type of the elements to be linked into the simple queue. 636A pointer to the head of the simple queue can later be declared as: 637.Bd -literal -offset indent 638struct HEADNAME *headp; 639.Ed 640.sp 641(The names 642.Li head 643and 644.Li headp 645are user selectable.) 646.Pp 647The macro 648.Nm SIMPLEQ_ENTRY 649declares a structure that connects the elements in 650the simple queue. 651.Pp 652The macro 653.Nm SIMPLEQ_HEAD_INITIALIZER 654provides a value which can be used to initialize a simple queue head at 655compile time, and is used at the point that the simple queue head 656variable is declared, like: 657.Bd -literal -offset indent 658struct HEADNAME head = SIMPLEQ_HEAD_INITIALIZER(head); 659.Ed 660.Pp 661The macro 662.Nm SIMPLEQ_INIT 663initializes the simple queue referenced by 664.Fa head . 665.Pp 666The macro 667.Nm SIMPLEQ_INSERT_HEAD 668inserts the new element 669.Fa elm 670at the head of the simple queue. 671.Pp 672The macro 673.Nm SIMPLEQ_INSERT_TAIL 674inserts the new element 675.Fa elm 676at the end of the simple queue. 677.Pp 678The macro 679.Nm SIMPLEQ_INSERT_AFTER 680inserts the new element 681.Fa elm 682after the element 683.Fa listelm . 684.Pp 685The macro 686.Nm SIMPLEQ_REMOVE_HEAD 687removes the first element from the simple queue. 688.Pp 689The macro 690.Nm SIMPLEQ_EMPTY 691return true if the simple queue 692.Fa head 693has no elements. 694.Pp 695The macro 696.Nm SIMPLEQ_FIRST 697returns the first elemement of the simple queue 698.Fa head . 699.Pp 700The macro 701.Nm SIMPLEQ_FOREACH 702traverses the tail queue referenced by 703.Fa head 704in the forward direction, assigning each element 705in turn to 706.Fa var . 707.Pp 708The macro 709.Nm SIMPLEQ_NEXT 710returns the element after the element 711.Fa elm . 712.Sh SIMPLE QUEUE EXAMPLE 713.Bd -literal 714SIMPLEQ_HEAD(simplehead, entry) head; 715struct simplehead *headp; /* Simple queue head. */ 716struct entry { 717 ... 718 SIMPLEQ_ENTRY(entry) entries; /* Simple queue. */ 719 ... 720} *n1, *n2, *np; 721 722SIMPLEQ_INIT(&head); /* Initialize the queue. */ 723 724n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 725SIMPLEQ_INSERT_HEAD(&head, n1, entries); 726 727n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 728SIMPLEQ_INSERT_TAIL(&head, n1, entries); 729 730n2 = malloc(sizeof(struct entry)); /* Insert after. */ 731SIMPLEQ_INSERT_AFTER(&head, n1, n2, entries); 732 /* Forward traversal. */ 733SIMPLEQ_FOREACH(np, &head, entries) 734 np-> ... 735 /* Delete. */ 736while (SIMPLEQ_FIRST(&head) != NULL) 737 SIMPLEQ_REMOVE_HEAD(&head, SIMPLEQ_FIRST(&head), entries); 738if (SIMPLEQ_EMPTY(&head)) /* Test for emptiness. */ 739 printf("nothing to do\\n"); 740.Ed 741.Sh TAIL QUEUES 742A tail queue is headed by a structure defined by the 743.Nm TAILQ_HEAD 744macro. 745This structure contains a pair of pointers, 746one to the first element in the tail queue and the other to 747the last element in the tail queue. 748The elements are doubly linked so that an arbitrary element can be 749removed without traversing the tail queue. 750New elements can be added to the queue after an existing element, 751before an existing element, at the head of the queue, or at the end 752the queue. 753A 754.Fa TAILQ_HEAD 755structure is declared as follows: 756.Bd -literal -offset indent 757TAILQ_HEAD(HEADNAME, TYPE) head; 758.Ed 759.sp 760where 761.Li HEADNAME 762is the name of the structure to be defined, and 763.Li TYPE 764is the type of the elements to be linked into the tail queue. 765A pointer to the head of the tail queue can later be declared as: 766.Bd -literal -offset indent 767struct HEADNAME *headp; 768.Ed 769.sp 770(The names 771.Li head 772and 773.Li headp 774are user selectable.) 775.Pp 776The macro 777.Nm TAILQ_ENTRY 778declares a structure that connects the elements in 779the tail queue. 780.Pp 781The macro 782.Nm TAILQ_HEAD_INITIALIZER 783provides a value which can be used to initialize a tail queue head at 784compile time, and is used at the point that the tail queue head 785variable is declared, like: 786.Bd -literal -offset indent 787struct HEADNAME head = TAILQ_HEAD_INITIALIZER(head); 788.Ed 789.Pp 790The macro 791.Nm TAILQ_INIT 792initializes the tail queue referenced by 793.Fa head . 794.Pp 795The macro 796.Nm TAILQ_INSERT_HEAD 797inserts the new element 798.Fa elm 799at the head of the tail queue. 800.Pp 801The macro 802.Nm TAILQ_INSERT_TAIL 803inserts the new element 804.Fa elm 805at the end of the tail queue. 806.Pp 807The macro 808.Nm TAILQ_INSERT_AFTER 809inserts the new element 810.Fa elm 811after the element 812.Fa listelm . 813.Pp 814The macro 815.Nm TAILQ_INSERT_BEFORE 816inserts the new element 817.Fa elm 818before the element 819.Fa listelm . 820.Pp 821The macro 822.Nm TAILQ_REMOVE 823removes the element 824.Fa elm 825from the tail queue. 826.Pp 827The macro 828.Nm TAILQ_EMPTY 829return true if the tail queue 830.Fa head 831has no elements. 832.Pp 833The macro 834.Nm TAILQ_FIRST 835returns the first elemement of the tail queue 836.Fa head . 837.Pp 838The macro 839.Nm TAILQ_FOREACH 840traverses the tail queue referenced by 841.Fa head 842in the forward direction, assigning each element in turn to 843.Fa var . 844.Pp 845The macro 846.Nm TAILQ_FOREACH_REVERSE 847traverses the tail queue referenced by 848.Fa head 849in the reverse direction, assigning each element in turn to 850.Fa var . 851.Pp 852The macro 853.Nm TAILQ_NEXT 854returns the element after the element 855.Fa elm . 856.Sh TAIL QUEUE EXAMPLE 857.Bd -literal 858TAILQ_HEAD(tailhead, entry) head; 859struct tailhead *headp; /* Tail queue head. */ 860struct entry { 861 ... 862 TAILQ_ENTRY(entry) entries; /* Tail queue. */ 863 ... 864} *n1, *n2, *np; 865 866TAILQ_INIT(&head); /* Initialize the queue. */ 867 868n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 869TAILQ_INSERT_HEAD(&head, n1, entries); 870 871n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 872TAILQ_INSERT_TAIL(&head, n1, entries); 873 874n2 = malloc(sizeof(struct entry)); /* Insert after. */ 875TAILQ_INSERT_AFTER(&head, n1, n2, entries); 876 877n2 = malloc(sizeof(struct entry)); /* Insert before. */ 878TAILQ_INSERT_BEFORE(n1, n2, entries); 879 /* Forward traversal. */ 880TAILQ_FOREACH(np, &head, entries) 881 np-> ... 882 /* Reverse traversal. */ 883TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries) 884 np-> ... 885 /* Delete. */ 886while (TAILQ_FIRST(&head) != NULL) 887 TAILQ_REMOVE(&head, TAILQ_FIRST(&head), entries); 888if (TAILQ_EMPTY(&head)) /* Test for emptiness. */ 889 printf("nothing to do\\n"); 890.Ed 891.Sh CIRCULAR QUEUES 892A circular queue is headed by a structure defined by the 893.Nm CIRCLEQ_HEAD 894macro. 895This structure contains a pair of pointers, 896one to the first element in the circular queue and the other to the 897last element in the circular queue. 898The elements are doubly linked so that an arbitrary element can be 899removed without traversing the queue. 900New elements can be added to the queue after an existing element, 901before an existing element, at the head of the queue, or at the end 902of the queue. 903A 904.Fa CIRCLEQ_HEAD 905structure is declared as follows: 906.Bd -literal -offset indent 907CIRCLEQ_HEAD(HEADNAME, TYPE) head; 908.Ed 909.sp 910where 911.Li HEADNAME 912is the name of the structure to be defined, and 913.Li TYPE 914is the type of the elements to be linked into the circular queue. 915A pointer to the head of the circular queue can later be declared as: 916.Bd -literal -offset indent 917struct HEADNAME *headp; 918.Ed 919.sp 920(The names 921.Li head 922and 923.Li headp 924are user selectable.) 925.Pp 926The macro 927.Nm CIRCLEQ_ENTRY 928declares a structure that connects the elements in 929the circular queue. 930.Pp 931The macro 932.Nm CIRCLEQ_HEAD_INITIALIZER 933provides a value which can be used to initialize a circular queue head at 934compile time, and is used at the point that the circular queue head 935variable is declared, like: 936.Bd -literal -offset indent 937struct HEADNAME head = CIRCLEQ_HEAD_INITIALIZER(head); 938.Ed 939.Pp 940The macro 941.Nm CIRCLEQ_INIT 942initializes the circular queue referenced by 943.Fa head . 944.Pp 945The macro 946.Nm CIRCLEQ_INSERT_HEAD 947inserts the new element 948.Fa elm 949at the head of the circular queue. 950.Pp 951The macro 952.Nm CIRCLEQ_INSERT_TAIL 953inserts the new element 954.Fa elm 955at the end of the circular queue. 956.Pp 957The macro 958.Nm CIRCLEQ_INSERT_AFTER 959inserts the new element 960.Fa elm 961after the element 962.Fa listelm . 963.Pp 964The macro 965.Nm CIRCLEQ_INSERT_BEFORE 966inserts the new element 967.Fa elm 968before the element 969.Fa listelm . 970.Pp 971The macro 972.Nm CIRCLEQ_REMOVE 973removes the element 974.Fa elm 975from the circular queue. 976.Pp 977The macro 978.Nm CIRCLEQ_EMPTY 979return true if the circular queue 980.Fa head 981has no elements. 982.Pp 983The macro 984.Nm CIRCLEQ_FIRST 985returns the first elemement of the circular queue 986.Fa head . 987.Pp 988The macro 989.Nm CICRLEQ_FOREACH 990traverses the circle queue referenced by 991.Fa head 992in the forward direction, assigning each element in turn to 993.Fa var . 994.Pp 995The macro 996.Nm CICRLEQ_FOREACH_REVERSE 997traverses the circle queue referenced by 998.Fa head 999in the reverse direction, assigning each element in turn to 1000.Fa var . 1001.Pp 1002The macro 1003.Nm CIRCLEQ_LAST 1004returns the last element of the circular queue 1005.Fa head . 1006.Pp 1007The macro 1008.Nm CIRCLEQ_NEXT 1009returns the element after the element 1010.Fa elm . 1011.Pp 1012The macro 1013.Nm CIRCLEQ_PREV 1014returns the element before the element 1015.Fa elm . 1016.Sh CIRCULAR QUEUE EXAMPLE 1017.Bd -literal 1018CIRCLEQ_HEAD(circleq, entry) head; 1019struct circleq *headp; /* Circular queue head. */ 1020struct entry { 1021 ... 1022 CIRCLEQ_ENTRY entries; /* Circular queue. */ 1023 ... 1024} *n1, *n2, *np; 1025 1026CIRCLEQ_INIT(&head); /* Initialize the circular queue. */ 1027 1028n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 1029CIRCLEQ_INSERT_HEAD(&head, n1, entries); 1030 1031n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 1032CIRCLEQ_INSERT_TAIL(&head, n1, entries); 1033 1034n2 = malloc(sizeof(struct entry)); /* Insert after. */ 1035CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries); 1036 1037n2 = malloc(sizeof(struct entry)); /* Insert before. */ 1038CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries); 1039 /* Forward traversal. */ 1040CIRCLEQ_FOREACH(np, &head, entries) 1041 np-> ... 1042 /* Reverse traversal. */ 1043CIRCLEQ_FOREACH_REVERSE(np, &head, entries) 1044 np-> ... 1045 /* Delete. */ 1046while (CIRCLEQ_HEAD(&head) != (void *)&head) 1047 CIRCLEQ_REMOVE(&head, CIRCLEQ_HEAD(&head), entries); 1048if (CIRCLEQ_EMPTY(&head)) /* Test for emptiness. */ 1049 printf("nothing to do\\n"); 1050.Ed 1051.Sh HISTORY 1052The 1053.Nm queue 1054functions first appeared in 1055.Bx 4.4 . 1056The 1057.Nm SIMPLEQ 1058functions first appeared in 1059.Nx 1.2 . 1060