1.\" $NetBSD: queue.3,v 1.8 1998/01/05 06:28:04 thorpej Exp $ 2.\" 3.\" Copyright (c) 1993 The Regents of the University of California. 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 University of 17.\" California, Berkeley and its contributors. 18.\" 4. Neither the name of the University nor the names of its contributors 19.\" may be used to endorse or promote products derived from this software 20.\" without specific prior written permission. 21.\" 22.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32.\" SUCH DAMAGE. 33.\" 34.\" @(#)queue.3 8.1 (Berkeley) 12/13/93 35.\" 36.Dd June 30, 1997 37.Dt QUEUE 3 38.Os BSD 4 39.Sh NAME 40.Nm LIST_ENTRY , 41.Nm LIST_HEAD , 42.Nm LIST_HEAD_INITIALIZER , 43.Nm LIST_INIT , 44.Nm LIST_INSERT_AFTER , 45.Nm LIST_INSERT_BEFORE , 46.Nm LIST_INSERT_HEAD , 47.Nm LIST_REMOVE , 48.Nm LIST_FIRST , 49.Nm LIST_NEXT , 50.Nm SIMPLEQ_ENTRY , 51.Nm SIMPLEQ_HEAD , 52.Nm SIMPLEQ_HEAD_INITIALIZER , 53.Nm SIMPLEQ_INIT , 54.Nm SIMPLEQ_INSERT_HEAD , 55.Nm SIMPLEQ_INSERT_TAIL , 56.Nm SIMPLEQ_INSERT_AFTER , 57.Nm SIMPLEQ_REMOVE_HEAD , 58.Nm SIMPLEQ_FIRST , 59.Nm SIMPLEQ_NEXT , 60.Nm TAILQ_ENTRY , 61.Nm TAILQ_HEAD , 62.Nm TAILQ_HEAD_INITIALIZER , 63.Nm TAILQ_INIT , 64.Nm TAILQ_INSERT_AFTER , 65.Nm TAILQ_INSERT_BEFORE , 66.Nm TAILQ_INSERT_HEAD , 67.Nm TAILQ_INSERT_TAIL , 68.Nm TAILQ_REMOVE , 69.Nm TAILQ_FIRST , 70.Nm TAILQ_NEXT , 71.Nm CIRCLEQ_ENTRY , 72.Nm CIRCLEQ_HEAD , 73.Nm CIRCLEQ_HEAD_INITIALIZER , 74.Nm CIRCLEQ_INIT , 75.Nm CIRCLEQ_INSERT_AFTER , 76.Nm CIRCLEQ_INSERT_BEFORE , 77.Nm CIRCLEQ_INSERT_HEAD , 78.Nm CIRCLEQ_INSERT_TAIL , 79.Nm CIRCLEQ_REMOVE , 80.Nm CIRCLEQ_FIRST , 81.Nm CIRCLEQ_LAST , 82.Nm CIRCLEQ_NEXT , 83.Nm CIRCLEQ_PREV 84.Nd implementations of lists, simple queues, tail queues, and circular queues 85.Sh SYNOPSIS 86.Fd #include <sys/queue.h> 87.sp 88.Fn LIST_ENTRY "TYPE" 89.Fn LIST_HEAD "HEADNAME" "TYPE" 90.Fn LIST_HEAD_INITIALIZER "head" 91.Fn LIST_INIT "LIST_HEAD *head" 92.Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" 93.Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" 94.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME" 95.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME" 96.Ft TYPE * 97.Fn LIST_FIRST "LIST_HEAD *head" 98.Ft TYPE * 99.Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME" 100.sp 101.Fn SIMPLEQ_ENTRY "TYPE" 102.Fn SIMPLEQ_HEAD "HEADNAME" "TYPE" 103.Fn SIMPLEQ_HEAD_INITIALIZER "head" 104.Fn SIMPLEQ_INIT "SIMPLEQ_HEAD *head" 105.Fn SIMPLEQ_INSERT_AFTER "SIMPLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "SIMPLEQ_ENTRY NAME" 106.Fn SIMPLEQ_INSERT_HEAD "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME" 107.Fn SIMPLEQ_INSERT_TAIL "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME" 108.Fn SIMPLEQ_REMOVE_HEAD "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME" 109.Ft TYPE * 110.Fn SIMPLEQ_FIRST "SIMPLEQ_HEAD *head" 111.Ft TYPE * 112.Fn SIMPLEQ_NEXT "TYPE *elm" "SIMPLEQ_ENTRY NAME" 113.sp 114.Fn TAILQ_ENTRY "TYPE" 115.Fn TAILQ_HEAD "HEADNAME" "TYPE" 116.Fn TAILQ_HEAD_INITIALIZER "head" 117.Fn TAILQ_INIT "TAILQ_HEAD *head" 118.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" 119.Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" 120.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 121.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 122.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 123.Ft TYPE * 124.Fn TAILQ_FIRST "TAILQ_HEAD *head" 125.Ft TYPE * 126.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME" 127.sp 128.Fn CIRCLEQ_ENTRY "TYPE" 129.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE" 130.Fn CIRCLEQ_HEAD_INITIALIZER "head" 131.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head" 132.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 133.Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 134.Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 135.Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 136.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 137.Ft TYPE * 138.Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head" 139.Ft TYPE * 140.Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head" 141.Ft TYPE * 142.Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME" 143.Ft TYPE * 144.Fn CIRCLEQ_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME" 145.Sh DESCRIPTION 146These macros define and operate on four types of data structures: 147lists, simple queues, tail queues, and circular queues. 148All four structures support the following functionality: 149.Bl -enum -compact -offset indent 150.It 151Insertion of a new entry at the head of the list. 152.It 153Insertion of a new entry before or after any element in the list. 154.It 155Removal of any entry in the list. 156.It 157Forward traversal through the list. 158.El 159.Pp 160Lists are the simplest of the four data structures and support 161only the above functionality. 162.Pp 163Simple queues add the following functionality: 164.Bl -enum -compact -offset indent 165.It 166Entries can be added at the end of a list. 167.El 168However: 169.Bl -enum -compact -offset indent 170.It 171Entries may not be added before any element in the list. 172.It 173Only the first entry in the list may be removed. 174.It 175All list insertions and removals must specify the head of the list. 176.It 177Each head entry requires two pointers rather than one. 178.El 179.Pp 180Tail queues add the following functionality: 181.Bl -enum -compact -offset indent 182.It 183Entries can be added at the end of a list. 184.El 185However: 186.Bl -enum -compact -offset indent 187.It 188All list insertions and removals, except insertion before another element, must 189specify the head of the list. 190.It 191Each head entry requires two pointers rather than one. 192.It 193Code size is about 15% greater and operations run about 20% slower 194than lists. 195.El 196.Pp 197Circular queues add the following functionality: 198.Bl -enum -compact -offset indent 199.It 200Entries can be added at the end of a list. 201.It 202They may be traversed backwards, from tail to head. 203.El 204However: 205.Bl -enum -compact -offset indent 206.It 207All list insertions and removals must specify the head of the list. 208.It 209Each head entry requires two pointers rather than one. 210.It 211The termination condition for traversal is more complex. 212.It 213Code size is about 40% greater and operations run about 45% slower 214than lists. 215.El 216.Pp 217In the macro definitions, 218.Fa TYPE 219is the name of a user defined structure, 220that must contain a field of type 221.Li LIST_ENTRY , 222.Li SIMPLEQ_ENTRY , 223.Li TAILQ_ENTRY , 224or 225.Li CIRCLEQ_ENTRY , 226named 227.Fa NAME . 228The argument 229.Fa HEADNAME 230is the name of a user defined structure that must be declared 231using the macros 232.Li LIST_HEAD , 233.Li SIMPLEQ_HEAD , 234.Li TAILQ_HEAD , 235or 236.Li CIRCLEQ_HEAD . 237See the examples below for further explanation of how these 238macros are used. 239.Sh LISTS 240A list is headed by a structure defined by the 241.Nm LIST_HEAD 242macro. 243This structure contains a single pointer to the first element 244on the list. 245The elements are doubly linked so that an arbitrary element can be 246removed without traversing the list. 247New elements can be added to the list after an existing element, 248before an existing element, or at the head of the list. 249A 250.Fa LIST_HEAD 251structure is declared as follows: 252.Bd -literal -offset indent 253LIST_HEAD(HEADNAME, TYPE) head; 254.Ed 255.sp 256where 257.Fa HEADNAME 258is the name of the structure to be defined, and 259.Fa TYPE 260is the type of the elements to be linked into the list. 261A pointer to the head of the list can later be declared as: 262.Bd -literal -offset indent 263struct HEADNAME *headp; 264.Ed 265.sp 266(The names 267.Li head 268and 269.Li headp 270are user selectable.) 271.Pp 272The macro 273.Nm LIST_ENTRY 274declares a structure that connects the elements in 275the list. 276.Pp 277The macro 278.Nm LIST_HEAD_INITIALIZER 279provides a value which can be used to initialize a list head at 280compile time, and is used at the point that the list head 281variable is declared, like: 282.Bd -literal -offset indent 283struct HEADNAME head = LIST_HEAD_INITIALIZER(head); 284.Ed 285.Pp 286The macro 287.Nm LIST_INIT 288initializes the list referenced by 289.Fa head . 290.Pp 291The macro 292.Nm LIST_INSERT_HEAD 293inserts the new element 294.Fa elm 295at the head of the list. 296.Pp 297The macro 298.Nm LIST_INSERT_AFTER 299inserts the new element 300.Fa elm 301after the element 302.Fa listelm . 303.Pp 304The macro 305.Nm LIST_INSERT_BEFORE 306inserts the new element 307.Fa elm 308before the element 309.Fa listelm . 310.Pp 311The macro 312.Nm LIST_REMOVE 313removes the element 314.Fa elm 315from the list. 316.Pp 317The macro 318.Nm LIST_FIRST 319returns the first elemement of the list 320.Fa head . 321.Pp 322The macro 323.Nm LIST_NEXT 324returns the element after the element 325.Fa elm . 326.Sh LIST EXAMPLE 327.Bd -literal 328LIST_HEAD(listhead, entry) head; 329struct listhead *headp; /* List head. */ 330struct entry { 331 ... 332 LIST_ENTRY(entry) entries; /* List. */ 333 ... 334} *n1, *n2, *np; 335 336LIST_INIT(&head); /* Initialize the list. */ 337 338n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 339LIST_INSERT_HEAD(&head, n1, entries); 340 341n2 = malloc(sizeof(struct entry)); /* Insert after. */ 342LIST_INSERT_AFTER(n1, n2, entries); 343 344n2 = malloc(sizeof(struct entry)); /* Insert before. */ 345LIST_INSERT_BEFORE(n1, n2, entries); 346 /* Forward traversal. */ 347for (np = LIST_FIRST(&head); np != NULL; np = LIST_NEXT(np, entries)) 348 np-> ... 349 /* Delete. */ 350while (LIST_FIRST(&head) != NULL) 351 LIST_REMOVE(LIST_FIRST(&head), entries); 352.Ed 353.Sh SIMPLE QUEUES 354A simple queue is headed by a structure defined by the 355.Nm SIMPLEQ_HEAD 356macro. 357This structure contains a pair of pointers, 358one to the first element in the simple queue and the other to 359the last element in the simple queue. 360The elements are doubly linked so that an arbitrary element can be 361removed without traversing the simple queue. 362New elements can be added to the queue after an existing element, 363before an existing element, at the head of the queue, or at the end 364the queue. 365A 366.Fa SIMPLEQ_HEAD 367structure is declared as follows: 368.Bd -literal -offset indent 369SIMPLEQ_HEAD(HEADNAME, TYPE) head; 370.Ed 371.sp 372where 373.Li HEADNAME 374is the name of the structure to be defined, and 375.Li TYPE 376is the type of the elements to be linked into the simple queue. 377A pointer to the head of the simple queue can later be declared as: 378.Bd -literal -offset indent 379struct HEADNAME *headp; 380.Ed 381.sp 382(The names 383.Li head 384and 385.Li headp 386are user selectable.) 387.Pp 388The macro 389.Nm SIMPLEQ_ENTRY 390declares a structure that connects the elements in 391the simple queue. 392.Pp 393The macro 394.Nm SIMPLEQ_HEAD_INITIALIZER 395provides a value which can be used to initialize a simple queue head at 396compile time, and is used at the point that the simple queue head 397variable is declared, like: 398.Bd -literal -offset indent 399struct HEADNAME head = SIMPLEQ_HEAD_INITIALIZER(head); 400.Ed 401.Pp 402The macro 403.Nm SIMPLEQ_INIT 404initializes the simple queue referenced by 405.Fa head . 406.Pp 407The macro 408.Nm SIMPLEQ_INSERT_HEAD 409inserts the new element 410.Fa elm 411at the head of the simple queue. 412.Pp 413The macro 414.Nm SIMPLEQ_INSERT_TAIL 415inserts the new element 416.Fa elm 417at the end of the simple queue. 418.Pp 419The macro 420.Nm SIMPLEQ_INSERT_AFTER 421inserts the new element 422.Fa elm 423after the element 424.Fa listelm . 425.Pp 426The macro 427.Nm SIMPLEQ_REMOVE_HEAD 428removes the first element from the simple queue. 429.Pp 430The macro 431.Nm SIMPLEQ_FIRST 432returns the first elemement of the simple queue 433.Fa head . 434.Pp 435The macro 436.Nm SIMPLEQ_NEXT 437returns the element after the element 438.Fa elm . 439.Sh SIMPLE QUEUE EXAMPLE 440.Bd -literal 441SIMPLEQ_HEAD(simplehead, entry) head; 442struct simplehead *headp; /* Simple queue head. */ 443struct entry { 444 ... 445 SIMPLEQ_ENTRY(entry) entries; /* Simple queue. */ 446 ... 447} *n1, *n2, *np; 448 449SIMPLEQ_INIT(&head); /* Initialize the queue. */ 450 451n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 452SIMPLEQ_INSERT_HEAD(&head, n1, entries); 453 454n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 455SIMPLEQ_INSERT_TAIL(&head, n1, entries); 456 457n2 = malloc(sizeof(struct entry)); /* Insert after. */ 458SIMPLEQ_INSERT_AFTER(&head, n1, n2, entries); 459 /* Forward traversal. */ 460for (np = SIMPLEQ_FIRST(&head); np != NULL; np = SIMPLEQ_NEXT(np, entries)) 461 np-> ... 462 /* Delete. */ 463while (SIMPLEQ_FIRST(&head) != NULL) 464 SIMPLEQ_REMOVE_HEAD(&head, SIMPLEQ_FIRST(&head), entries); 465.Ed 466.Sh TAIL QUEUES 467A tail queue is headed by a structure defined by the 468.Nm TAILQ_HEAD 469macro. 470This structure contains a pair of pointers, 471one to the first element in the tail queue and the other to 472the last element in the tail queue. 473The elements are doubly linked so that an arbitrary element can be 474removed without traversing the tail queue. 475New elements can be added to the queue after an existing element, 476before an existing element, at the head of the queue, or at the end 477the queue. 478A 479.Fa TAILQ_HEAD 480structure is declared as follows: 481.Bd -literal -offset indent 482TAILQ_HEAD(HEADNAME, TYPE) head; 483.Ed 484.sp 485where 486.Li HEADNAME 487is the name of the structure to be defined, and 488.Li TYPE 489is the type of the elements to be linked into the tail queue. 490A pointer to the head of the tail queue can later be declared as: 491.Bd -literal -offset indent 492struct HEADNAME *headp; 493.Ed 494.sp 495(The names 496.Li head 497and 498.Li headp 499are user selectable.) 500.Pp 501The macro 502.Nm TAILQ_ENTRY 503declares a structure that connects the elements in 504the tail queue. 505.Pp 506The macro 507.Nm TAILQ_HEAD_INITIALIZER 508provides a value which can be used to initialize a tail queue head at 509compile time, and is used at the point that the tail queue head 510variable is declared, like: 511.Bd -literal -offset indent 512struct HEADNAME head = TAILQ_HEAD_INITIALIZER(head); 513.Ed 514.Pp 515The macro 516.Nm TAILQ_INIT 517initializes the tail queue referenced by 518.Fa head . 519.Pp 520The macro 521.Nm TAILQ_INSERT_HEAD 522inserts the new element 523.Fa elm 524at the head of the tail queue. 525.Pp 526The macro 527.Nm TAILQ_INSERT_TAIL 528inserts the new element 529.Fa elm 530at the end of the tail queue. 531.Pp 532The macro 533.Nm TAILQ_INSERT_AFTER 534inserts the new element 535.Fa elm 536after the element 537.Fa listelm . 538.Pp 539The macro 540.Nm TAILQ_INSERT_BEFORE 541inserts the new element 542.Fa elm 543before the element 544.Fa listelm . 545.Pp 546The macro 547.Nm TAILQ_REMOVE 548removes the element 549.Fa elm 550from the tail queue. 551.Pp 552The macro 553.Nm TAILQ_FIRST 554returns the first elemement of the tail queue 555.Fa head . 556.Pp 557The macro 558.Nm TAILQ_NEXT 559returns the element after the element 560.Fa elm . 561.Sh TAIL QUEUE EXAMPLE 562.Bd -literal 563TAILQ_HEAD(tailhead, entry) head; 564struct tailhead *headp; /* Tail queue head. */ 565struct entry { 566 ... 567 TAILQ_ENTRY(entry) entries; /* Tail queue. */ 568 ... 569} *n1, *n2, *np; 570 571TAILQ_INIT(&head); /* Initialize the queue. */ 572 573n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 574TAILQ_INSERT_HEAD(&head, n1, entries); 575 576n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 577TAILQ_INSERT_TAIL(&head, n1, entries); 578 579n2 = malloc(sizeof(struct entry)); /* Insert after. */ 580TAILQ_INSERT_AFTER(&head, n1, n2, entries); 581 582n2 = malloc(sizeof(struct entry)); /* Insert before. */ 583TAILQ_INSERT_BEFORE(n1, n2, entries); 584 /* Forward traversal. */ 585for (np = TAILQ_FIRST(&head); np != NULL; np = TAILQ_NEXT(np, entries)) 586 np-> ... 587 /* Delete. */ 588while (TAILQ_FIRST(&head) != NULL) 589 TAILQ_REMOVE(&head, TAILQ_FIRST(&head), entries); 590.Ed 591.Sh CIRCULAR QUEUES 592A circular queue is headed by a structure defined by the 593.Nm CIRCLEQ_HEAD 594macro. 595This structure contains a pair of pointers, 596one to the first element in the circular queue and the other to the 597last element in the circular queue. 598The elements are doubly linked so that an arbitrary element can be 599removed without traversing the queue. 600New elements can be added to the queue after an existing element, 601before an existing element, at the head of the queue, or at the end 602of the queue. 603A 604.Fa CIRCLEQ_HEAD 605structure is declared as follows: 606.Bd -literal -offset indent 607CIRCLEQ_HEAD(HEADNAME, TYPE) head; 608.Ed 609.sp 610where 611.Li HEADNAME 612is the name of the structure to be defined, and 613.Li TYPE 614is the type of the elements to be linked into the circular queue. 615A pointer to the head of the circular queue can later be declared as: 616.Bd -literal -offset indent 617struct HEADNAME *headp; 618.Ed 619.sp 620(The names 621.Li head 622and 623.Li headp 624are user selectable.) 625.Pp 626The macro 627.Nm CIRCLEQ_ENTRY 628declares a structure that connects the elements in 629the circular queue. 630.Pp 631The macro 632.Nm CIRCLEQ_HEAD_INITIALIZER 633provides a value which can be used to initialize a circular queue head at 634compile time, and is used at the point that the circular queue head 635variable is declared, like: 636.Bd -literal -offset indent 637struct HEADNAME head = CIRCLEQ_HEAD_INITIALIZER(head); 638.Ed 639.Pp 640The macro 641.Nm CIRCLEQ_INIT 642initializes the circular queue referenced by 643.Fa head . 644.Pp 645The macro 646.Nm CIRCLEQ_INSERT_HEAD 647inserts the new element 648.Fa elm 649at the head of the circular queue. 650.Pp 651The macro 652.Nm CIRCLEQ_INSERT_TAIL 653inserts the new element 654.Fa elm 655at the end of the circular queue. 656.Pp 657The macro 658.Nm CIRCLEQ_INSERT_AFTER 659inserts the new element 660.Fa elm 661after the element 662.Fa listelm . 663.Pp 664The macro 665.Nm CIRCLEQ_INSERT_BEFORE 666inserts the new element 667.Fa elm 668before the element 669.Fa listelm . 670.Pp 671The macro 672.Nm CIRCLEQ_REMOVE 673removes the element 674.Fa elm 675from the circular queue. 676.Pp 677The macro 678.Nm CIRCLEQ_FIRST 679returns the first elemement of the circular queue 680.Fa head . 681.Pp 682The macro 683.Nm CIRCLEQ_LAST 684returns the last element of the circular queue 685.Fa head . 686.Pp 687The macro 688.Nm CIRCLEQ_NEXT 689returns the element after the element 690.Fa elm . 691.Pp 692The macro 693.Nm CIRCLEQ_PREV 694returns the element before the element 695.Fa elm . 696.Sh CIRCULAR QUEUE EXAMPLE 697.Bd -literal 698CIRCLEQ_HEAD(circleq, entry) head; 699struct circleq *headp; /* Circular queue head. */ 700struct entry { 701 ... 702 CIRCLEQ_ENTRY entries; /* Circular queue. */ 703 ... 704} *n1, *n2, *np; 705 706CIRCLEQ_INIT(&head); /* Initialize the circular queue. */ 707 708n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 709CIRCLEQ_INSERT_HEAD(&head, n1, entries); 710 711n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 712CIRCLEQ_INSERT_TAIL(&head, n1, entries); 713 714n2 = malloc(sizeof(struct entry)); /* Insert after. */ 715CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries); 716 717n2 = malloc(sizeof(struct entry)); /* Insert before. */ 718CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries); 719 /* Forward traversal. */ 720for (np = CIRCLEQ_FIRST(&head); np != (void *)&head; 721 np = CIRCLEQ_NEXT(np, entries)) 722 np-> ... 723 /* Reverse traversal. */ 724for (np = CIRCLEQ_LAST(&head); np != (void *)&head; 725 np = CIRCLEQ_PREV(np, entries)) 726 np-> ... 727 /* Delete. */ 728while (CIRCLEQ_HEAD(&head) != (void *)&head) 729 CIRCLEQ_REMOVE(&head, CIRCLEQ_HEAD(&head), entries); 730.Ed 731.Sh HISTORY 732The 733.Nm queue 734functions first appeared in 4.4BSD. 735The 736.Nm SIMPLEQ 737functions first appeared in 738.Nx 1.2 . 739