1.\" $NetBSD: queue.3,v 1.15 2000/05/27 22:34:24 mycroft 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 May 27, 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_EMPTY , 80.Nm LIST_FIRST , 81.Nm LIST_NEXT , 82.Nm SIMPLEQ_ENTRY , 83.Nm SIMPLEQ_HEAD , 84.Nm SIMPLEQ_HEAD_INITIALIZER , 85.Nm SIMPLEQ_INIT , 86.Nm SIMPLEQ_INSERT_HEAD , 87.Nm SIMPLEQ_INSERT_TAIL , 88.Nm SIMPLEQ_INSERT_AFTER , 89.Nm SIMPLEQ_REMOVE_HEAD , 90.Nm SIMPLEQ_EMPTY , 91.Nm SIMPLEQ_FIRST , 92.Nm SIMPLEQ_NEXT , 93.Nm TAILQ_ENTRY , 94.Nm TAILQ_HEAD , 95.Nm TAILQ_HEAD_INITIALIZER , 96.Nm TAILQ_INIT , 97.Nm TAILQ_INSERT_AFTER , 98.Nm TAILQ_INSERT_BEFORE , 99.Nm TAILQ_INSERT_HEAD , 100.Nm TAILQ_INSERT_TAIL , 101.Nm TAILQ_REMOVE , 102.Nm TAILQ_EMPTY , 103.Nm TAILQ_FIRST , 104.Nm TAILQ_NEXT , 105.Nm CIRCLEQ_ENTRY , 106.Nm CIRCLEQ_HEAD , 107.Nm CIRCLEQ_HEAD_INITIALIZER , 108.Nm CIRCLEQ_INIT , 109.Nm CIRCLEQ_INSERT_AFTER , 110.Nm CIRCLEQ_INSERT_BEFORE , 111.Nm CIRCLEQ_INSERT_HEAD , 112.Nm CIRCLEQ_INSERT_TAIL , 113.Nm CIRCLEQ_REMOVE , 114.Nm CIRCLEQ_EMPTY , 115.Nm CIRCLEQ_FIRST , 116.Nm CIRCLEQ_LAST , 117.Nm CIRCLEQ_NEXT , 118.Nm CIRCLEQ_PREV 119.Nd "implementations of lists, simple queues, tail queues, and circular queues" 120.Sh SYNOPSIS 121.Fd #include <sys/queue.h> 122.sp 123.Fn LIST_ENTRY "TYPE" 124.Fn LIST_HEAD "HEADNAME" "TYPE" 125.Fn LIST_HEAD_INITIALIZER "head" 126.Fn LIST_INIT "LIST_HEAD *head" 127.Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" 128.Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" 129.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME" 130.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME" 131.Ft int 132.Fn LIST_EMPTY "LIST_HEAD *head" 133.Ft TYPE * 134.Fn LIST_FIRST "LIST_HEAD *head" 135.Ft TYPE * 136.Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME" 137.sp 138.Fn SIMPLEQ_ENTRY "TYPE" 139.Fn SIMPLEQ_HEAD "HEADNAME" "TYPE" 140.Fn SIMPLEQ_HEAD_INITIALIZER "head" 141.Fn SIMPLEQ_INIT "SIMPLEQ_HEAD *head" 142.Fn SIMPLEQ_INSERT_AFTER "SIMPLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "SIMPLEQ_ENTRY NAME" 143.Fn SIMPLEQ_INSERT_HEAD "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME" 144.Fn SIMPLEQ_INSERT_TAIL "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME" 145.Fn SIMPLEQ_REMOVE_HEAD "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME" 146.Ft int 147.Fn SIMPLEQ_EMPTY "SIMPLEQ_HEAD *head" 148.Ft TYPE * 149.Fn SIMPLEQ_FIRST "SIMPLEQ_HEAD *head" 150.Ft TYPE * 151.Fn SIMPLEQ_NEXT "TYPE *elm" "SIMPLEQ_ENTRY NAME" 152.sp 153.Fn TAILQ_ENTRY "TYPE" 154.Fn TAILQ_HEAD "HEADNAME" "TYPE" 155.Fn TAILQ_HEAD_INITIALIZER "head" 156.Fn TAILQ_INIT "TAILQ_HEAD *head" 157.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" 158.Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" 159.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 160.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 161.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 162.Ft int 163.Fn TAILQ_EMPTY "TAILQ_HEAD *head" 164.Ft TYPE * 165.Fn TAILQ_FIRST "TAILQ_HEAD *head" 166.Ft TYPE * 167.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME" 168.sp 169.Fn CIRCLEQ_ENTRY "TYPE" 170.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE" 171.Fn CIRCLEQ_HEAD_INITIALIZER "head" 172.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head" 173.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 174.Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 175.Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 176.Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 177.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 178.Ft int 179.Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head" 180.Ft TYPE * 181.Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head" 182.Ft TYPE * 183.Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head" 184.Ft TYPE * 185.Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME" 186.Ft TYPE * 187.Fn CIRCLEQ_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME" 188.Sh DESCRIPTION 189These macros define and operate on four types of data structures: 190lists, simple queues, tail queues, and circular queues. 191All four structures support the following functionality: 192.Bl -enum -compact -offset indent 193.It 194Insertion of a new entry at the head of the list. 195.It 196Insertion of a new entry before or after any element in the list. 197.It 198Removal of any entry in the list. 199.It 200Forward traversal through the list. 201.El 202.Pp 203Lists are the simplest of the four data structures and support 204only the above functionality. 205.Pp 206Simple queues add the following functionality: 207.Bl -enum -compact -offset indent 208.It 209Entries can be added at the end of a list. 210.El 211However: 212.Bl -enum -compact -offset indent 213.It 214Entries may not be added before any element in the list. 215.It 216Only the first entry in the list may be removed. 217.It 218All list insertions and removals must specify the head of the list. 219.It 220Each head entry requires two pointers rather than one. 221.El 222.Pp 223Tail queues add the following functionality: 224.Bl -enum -compact -offset indent 225.It 226Entries can be added at the end of a list. 227.El 228However: 229.Bl -enum -compact -offset indent 230.It 231All list insertions and removals, except insertion before another element, must 232specify the head of the list. 233.It 234Each head entry requires two pointers rather than one. 235.It 236Code size is about 15% greater and operations run about 20% slower 237than lists. 238.El 239.Pp 240Circular queues add the following functionality: 241.Bl -enum -compact -offset indent 242.It 243Entries can be added at the end of a list. 244.It 245They may be traversed backwards, from tail to head. 246.El 247However: 248.Bl -enum -compact -offset indent 249.It 250All list insertions and removals must specify the head of the list. 251.It 252Each head entry requires two pointers rather than one. 253.It 254The termination condition for traversal is more complex. 255.It 256Code size is about 40% greater and operations run about 45% slower 257than lists. 258.El 259.Pp 260In the macro definitions, 261.Fa TYPE 262is the name of a user defined structure, 263that must contain a field of type 264.Li LIST_ENTRY , 265.Li SIMPLEQ_ENTRY , 266.Li TAILQ_ENTRY , 267or 268.Li CIRCLEQ_ENTRY , 269named 270.Fa NAME . 271The argument 272.Fa HEADNAME 273is the name of a user defined structure that must be declared 274using the macros 275.Li LIST_HEAD , 276.Li SIMPLEQ_HEAD , 277.Li TAILQ_HEAD , 278or 279.Li CIRCLEQ_HEAD . 280See the examples below for further explanation of how these 281macros are used. 282.Sh LISTS 283A list is headed by a structure defined by the 284.Nm LIST_HEAD 285macro. 286This structure contains a single pointer to the first element 287on the list. 288The elements are doubly linked so that an arbitrary element can be 289removed without traversing the list. 290New elements can be added to the list after an existing element, 291before an existing element, or at the head of the list. 292A 293.Fa LIST_HEAD 294structure is declared as follows: 295.Bd -literal -offset indent 296LIST_HEAD(HEADNAME, TYPE) head; 297.Ed 298.sp 299where 300.Fa HEADNAME 301is the name of the structure to be defined, and 302.Fa TYPE 303is the type of the elements to be linked into the list. 304A pointer to the head of the list can later be declared as: 305.Bd -literal -offset indent 306struct HEADNAME *headp; 307.Ed 308.sp 309(The names 310.Li head 311and 312.Li headp 313are user selectable.) 314.Pp 315The macro 316.Nm LIST_ENTRY 317declares a structure that connects the elements in 318the list. 319.Pp 320The macro 321.Nm LIST_HEAD_INITIALIZER 322provides a value which can be used to initialize a list head at 323compile time, and is used at the point that the list head 324variable is declared, like: 325.Bd -literal -offset indent 326struct HEADNAME head = LIST_HEAD_INITIALIZER(head); 327.Ed 328.Pp 329The macro 330.Nm LIST_INIT 331initializes the list referenced by 332.Fa head . 333.Pp 334The macro 335.Nm LIST_INSERT_HEAD 336inserts the new element 337.Fa elm 338at the head of the list. 339.Pp 340The macro 341.Nm LIST_INSERT_AFTER 342inserts the new element 343.Fa elm 344after the element 345.Fa listelm . 346.Pp 347The macro 348.Nm LIST_INSERT_BEFORE 349inserts the new element 350.Fa elm 351before the element 352.Fa listelm . 353.Pp 354The macro 355.Nm LIST_REMOVE 356removes the element 357.Fa elm 358from the list. 359.Pp 360The macro 361.Nm LIST_EMPTY 362return true if the list 363.Fa head 364has no elements. 365.Pp 366The macro 367.Nm LIST_FIRST 368returns the first elemement of the list 369.Fa head . 370.Pp 371The macro 372.Nm LIST_NEXT 373returns the element after the element 374.Fa elm . 375.Sh LIST EXAMPLE 376.Bd -literal 377LIST_HEAD(listhead, entry) head; 378struct listhead *headp; /* List head. */ 379struct entry { 380 ... 381 LIST_ENTRY(entry) entries; /* List. */ 382 ... 383} *n1, *n2, *np; 384 385LIST_INIT(&head); /* Initialize the list. */ 386 387n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 388LIST_INSERT_HEAD(&head, n1, entries); 389 390n2 = malloc(sizeof(struct entry)); /* Insert after. */ 391LIST_INSERT_AFTER(n1, n2, entries); 392 393n2 = malloc(sizeof(struct entry)); /* Insert before. */ 394LIST_INSERT_BEFORE(n1, n2, entries); 395 /* Forward traversal. */ 396for (np = LIST_FIRST(&head); np != NULL; np = LIST_NEXT(np, entries)) 397 np-> ... 398 /* Delete. */ 399while (LIST_FIRST(&head) != NULL) 400 LIST_REMOVE(LIST_FIRST(&head), entries); 401if (LIST_EMPTY(&head)) /* Test for emptiness. */ 402 printf("nothing to do\\n"); 403.Ed 404.Sh SIMPLE QUEUES 405A simple queue is headed by a structure defined by the 406.Nm SIMPLEQ_HEAD 407macro. 408This structure contains a pair of pointers, 409one to the first element in the simple queue and the other to 410the last element in the simple queue. 411The elements are doubly linked so that an arbitrary element can be 412removed without traversing the simple queue. 413New elements can be added to the queue after an existing element, 414before an existing element, at the head of the queue, or at the end 415the queue. 416A 417.Fa SIMPLEQ_HEAD 418structure is declared as follows: 419.Bd -literal -offset indent 420SIMPLEQ_HEAD(HEADNAME, TYPE) head; 421.Ed 422.sp 423where 424.Li HEADNAME 425is the name of the structure to be defined, and 426.Li TYPE 427is the type of the elements to be linked into the simple queue. 428A pointer to the head of the simple queue can later be declared as: 429.Bd -literal -offset indent 430struct HEADNAME *headp; 431.Ed 432.sp 433(The names 434.Li head 435and 436.Li headp 437are user selectable.) 438.Pp 439The macro 440.Nm SIMPLEQ_ENTRY 441declares a structure that connects the elements in 442the simple queue. 443.Pp 444The macro 445.Nm SIMPLEQ_HEAD_INITIALIZER 446provides a value which can be used to initialize a simple queue head at 447compile time, and is used at the point that the simple queue head 448variable is declared, like: 449.Bd -literal -offset indent 450struct HEADNAME head = SIMPLEQ_HEAD_INITIALIZER(head); 451.Ed 452.Pp 453The macro 454.Nm SIMPLEQ_INIT 455initializes the simple queue referenced by 456.Fa head . 457.Pp 458The macro 459.Nm SIMPLEQ_INSERT_HEAD 460inserts the new element 461.Fa elm 462at the head of the simple queue. 463.Pp 464The macro 465.Nm SIMPLEQ_INSERT_TAIL 466inserts the new element 467.Fa elm 468at the end of the simple queue. 469.Pp 470The macro 471.Nm SIMPLEQ_INSERT_AFTER 472inserts the new element 473.Fa elm 474after the element 475.Fa listelm . 476.Pp 477The macro 478.Nm SIMPLEQ_REMOVE_HEAD 479removes the first element from the simple queue. 480.Pp 481The macro 482.Nm SIMPLEQ_EMPTY 483return true if the simple queue 484.Fa head 485has no elements. 486.Pp 487The macro 488.Nm SIMPLEQ_FIRST 489returns the first elemement of the simple queue 490.Fa head . 491.Pp 492The macro 493.Nm SIMPLEQ_NEXT 494returns the element after the element 495.Fa elm . 496.Sh SIMPLE QUEUE EXAMPLE 497.Bd -literal 498SIMPLEQ_HEAD(simplehead, entry) head; 499struct simplehead *headp; /* Simple queue head. */ 500struct entry { 501 ... 502 SIMPLEQ_ENTRY(entry) entries; /* Simple queue. */ 503 ... 504} *n1, *n2, *np; 505 506SIMPLEQ_INIT(&head); /* Initialize the queue. */ 507 508n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 509SIMPLEQ_INSERT_HEAD(&head, n1, entries); 510 511n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 512SIMPLEQ_INSERT_TAIL(&head, n1, entries); 513 514n2 = malloc(sizeof(struct entry)); /* Insert after. */ 515SIMPLEQ_INSERT_AFTER(&head, n1, n2, entries); 516 /* Forward traversal. */ 517for (np = SIMPLEQ_FIRST(&head); np != NULL; np = SIMPLEQ_NEXT(np, entries)) 518 np-> ... 519 /* Delete. */ 520while (SIMPLEQ_FIRST(&head) != NULL) 521 SIMPLEQ_REMOVE_HEAD(&head, SIMPLEQ_FIRST(&head), entries); 522if (SIMPLEQ_EMPTY(&head)) /* Test for emptiness. */ 523 printf("nothing to do\\n"); 524.Ed 525.Sh TAIL QUEUES 526A tail queue is headed by a structure defined by the 527.Nm TAILQ_HEAD 528macro. 529This structure contains a pair of pointers, 530one to the first element in the tail queue and the other to 531the last element in the tail queue. 532The elements are doubly linked so that an arbitrary element can be 533removed without traversing the tail queue. 534New elements can be added to the queue after an existing element, 535before an existing element, at the head of the queue, or at the end 536the queue. 537A 538.Fa TAILQ_HEAD 539structure is declared as follows: 540.Bd -literal -offset indent 541TAILQ_HEAD(HEADNAME, TYPE) head; 542.Ed 543.sp 544where 545.Li HEADNAME 546is the name of the structure to be defined, and 547.Li TYPE 548is the type of the elements to be linked into the tail queue. 549A pointer to the head of the tail queue can later be declared as: 550.Bd -literal -offset indent 551struct HEADNAME *headp; 552.Ed 553.sp 554(The names 555.Li head 556and 557.Li headp 558are user selectable.) 559.Pp 560The macro 561.Nm TAILQ_ENTRY 562declares a structure that connects the elements in 563the tail queue. 564.Pp 565The macro 566.Nm TAILQ_HEAD_INITIALIZER 567provides a value which can be used to initialize a tail queue head at 568compile time, and is used at the point that the tail queue head 569variable is declared, like: 570.Bd -literal -offset indent 571struct HEADNAME head = TAILQ_HEAD_INITIALIZER(head); 572.Ed 573.Pp 574The macro 575.Nm TAILQ_INIT 576initializes the tail queue referenced by 577.Fa head . 578.Pp 579The macro 580.Nm TAILQ_INSERT_HEAD 581inserts the new element 582.Fa elm 583at the head of the tail queue. 584.Pp 585The macro 586.Nm TAILQ_INSERT_TAIL 587inserts the new element 588.Fa elm 589at the end of the tail queue. 590.Pp 591The macro 592.Nm TAILQ_INSERT_AFTER 593inserts the new element 594.Fa elm 595after the element 596.Fa listelm . 597.Pp 598The macro 599.Nm TAILQ_INSERT_BEFORE 600inserts the new element 601.Fa elm 602before the element 603.Fa listelm . 604.Pp 605The macro 606.Nm TAILQ_REMOVE 607removes the element 608.Fa elm 609from the tail queue. 610.Pp 611The macro 612.Nm TAILQ_EMPTY 613return true if the tail queue 614.Fa head 615has no elements. 616.Pp 617The macro 618.Nm TAILQ_FIRST 619returns the first elemement of the tail queue 620.Fa head . 621.Pp 622The macro 623.Nm TAILQ_NEXT 624returns the element after the element 625.Fa elm . 626.Sh TAIL QUEUE EXAMPLE 627.Bd -literal 628TAILQ_HEAD(tailhead, entry) head; 629struct tailhead *headp; /* Tail queue head. */ 630struct entry { 631 ... 632 TAILQ_ENTRY(entry) entries; /* Tail queue. */ 633 ... 634} *n1, *n2, *np; 635 636TAILQ_INIT(&head); /* Initialize the queue. */ 637 638n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 639TAILQ_INSERT_HEAD(&head, n1, entries); 640 641n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 642TAILQ_INSERT_TAIL(&head, n1, entries); 643 644n2 = malloc(sizeof(struct entry)); /* Insert after. */ 645TAILQ_INSERT_AFTER(&head, n1, n2, entries); 646 647n2 = malloc(sizeof(struct entry)); /* Insert before. */ 648TAILQ_INSERT_BEFORE(n1, n2, entries); 649 /* Forward traversal. */ 650for (np = TAILQ_FIRST(&head); np != NULL; np = TAILQ_NEXT(np, entries)) 651 np-> ... 652 /* Delete. */ 653while (TAILQ_FIRST(&head) != NULL) 654 TAILQ_REMOVE(&head, TAILQ_FIRST(&head), entries); 655if (TAILQ_EMPTY(&head)) /* Test for emptiness. */ 656 printf("nothing to do\\n"); 657.Ed 658.Sh CIRCULAR QUEUES 659A circular queue is headed by a structure defined by the 660.Nm CIRCLEQ_HEAD 661macro. 662This structure contains a pair of pointers, 663one to the first element in the circular queue and the other to the 664last element in the circular queue. 665The elements are doubly linked so that an arbitrary element can be 666removed without traversing the queue. 667New elements can be added to the queue after an existing element, 668before an existing element, at the head of the queue, or at the end 669of the queue. 670A 671.Fa CIRCLEQ_HEAD 672structure is declared as follows: 673.Bd -literal -offset indent 674CIRCLEQ_HEAD(HEADNAME, TYPE) head; 675.Ed 676.sp 677where 678.Li HEADNAME 679is the name of the structure to be defined, and 680.Li TYPE 681is the type of the elements to be linked into the circular queue. 682A pointer to the head of the circular queue can later be declared as: 683.Bd -literal -offset indent 684struct HEADNAME *headp; 685.Ed 686.sp 687(The names 688.Li head 689and 690.Li headp 691are user selectable.) 692.Pp 693The macro 694.Nm CIRCLEQ_ENTRY 695declares a structure that connects the elements in 696the circular queue. 697.Pp 698The macro 699.Nm CIRCLEQ_HEAD_INITIALIZER 700provides a value which can be used to initialize a circular queue head at 701compile time, and is used at the point that the circular queue head 702variable is declared, like: 703.Bd -literal -offset indent 704struct HEADNAME head = CIRCLEQ_HEAD_INITIALIZER(head); 705.Ed 706.Pp 707The macro 708.Nm CIRCLEQ_INIT 709initializes the circular queue referenced by 710.Fa head . 711.Pp 712The macro 713.Nm CIRCLEQ_INSERT_HEAD 714inserts the new element 715.Fa elm 716at the head of the circular queue. 717.Pp 718The macro 719.Nm CIRCLEQ_INSERT_TAIL 720inserts the new element 721.Fa elm 722at the end of the circular queue. 723.Pp 724The macro 725.Nm CIRCLEQ_INSERT_AFTER 726inserts the new element 727.Fa elm 728after the element 729.Fa listelm . 730.Pp 731The macro 732.Nm CIRCLEQ_INSERT_BEFORE 733inserts the new element 734.Fa elm 735before the element 736.Fa listelm . 737.Pp 738The macro 739.Nm CIRCLEQ_REMOVE 740removes the element 741.Fa elm 742from the circular queue. 743.Pp 744The macro 745.Nm CIRCLEQ_EMPTY 746return true if the circular queue 747.Fa head 748has no elements. 749.Pp 750The macro 751.Nm CIRCLEQ_FIRST 752returns the first elemement of the circular queue 753.Fa head . 754.Pp 755The macro 756.Nm CIRCLEQ_LAST 757returns the last element of the circular queue 758.Fa head . 759.Pp 760The macro 761.Nm CIRCLEQ_NEXT 762returns the element after the element 763.Fa elm . 764.Pp 765The macro 766.Nm CIRCLEQ_PREV 767returns the element before the element 768.Fa elm . 769.Sh CIRCULAR QUEUE EXAMPLE 770.Bd -literal 771CIRCLEQ_HEAD(circleq, entry) head; 772struct circleq *headp; /* Circular queue head. */ 773struct entry { 774 ... 775 CIRCLEQ_ENTRY entries; /* Circular queue. */ 776 ... 777} *n1, *n2, *np; 778 779CIRCLEQ_INIT(&head); /* Initialize the circular queue. */ 780 781n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 782CIRCLEQ_INSERT_HEAD(&head, n1, entries); 783 784n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 785CIRCLEQ_INSERT_TAIL(&head, n1, entries); 786 787n2 = malloc(sizeof(struct entry)); /* Insert after. */ 788CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries); 789 790n2 = malloc(sizeof(struct entry)); /* Insert before. */ 791CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries); 792 /* Forward traversal. */ 793for (np = CIRCLEQ_FIRST(&head); np != (void *)&head; 794 np = CIRCLEQ_NEXT(np, entries)) 795 np-> ... 796 /* Reverse traversal. */ 797for (np = CIRCLEQ_LAST(&head); np != (void *)&head; 798 np = CIRCLEQ_PREV(np, entries)) 799 np-> ... 800 /* Delete. */ 801while (CIRCLEQ_HEAD(&head) != (void *)&head) 802 CIRCLEQ_REMOVE(&head, CIRCLEQ_HEAD(&head), entries); 803if (CIRCLEQ_EMPTY(&head)) /* Test for emptiness. */ 804 printf("nothing to do\\n"); 805.Ed 806.Sh HISTORY 807The 808.Nm queue 809functions first appeared in 810.Bx 4.4 . 811The 812.Nm SIMPLEQ 813functions first appeared in 814.Nx 1.2 . 815