1.\" Copyright (c) 1993 2.\" The Regents of the University of California. All rights reserved. 3.\" 4.\" Redistribution and use in source and binary forms, with or without 5.\" modification, are permitted provided that the following conditions 6.\" are met: 7.\" 1. Redistributions of source code must retain the above copyright 8.\" notice, this list of conditions and the following disclaimer. 9.\" 2. Redistributions in binary form must reproduce the above copyright 10.\" notice, this list of conditions and the following disclaimer in the 11.\" documentation and/or other materials provided with the distribution. 12.\" 3. All advertising materials mentioning features or use of this software 13.\" must display the following acknowledgement: 14.\" This product includes software developed by the University of 15.\" California, Berkeley and its contributors. 16.\" 4. Neither the name of the University nor the names of its contributors 17.\" may be used to endorse or promote products derived from this software 18.\" without specific prior written permission. 19.\" 20.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30.\" SUCH DAMAGE. 31.\" 32.\" @(#)queue.3 8.2 (Berkeley) 1/24/94 33.\" $FreeBSD: src/share/man/man3/queue.3,v 1.15.2.7 2001/12/18 10:09:02 ru Exp $ 34.\" $DragonFly: src/share/man/man3/queue.3,v 1.2 2003/06/17 04:36:58 dillon Exp $ 35.\" 36.Dd January 24, 1994 37.Dt QUEUE 3 38.Os 39.Sh NAME 40.Nm SLIST_EMPTY , 41.Nm SLIST_ENTRY , 42.Nm SLIST_FIRST , 43.Nm SLIST_FOREACH , 44.Nm SLIST_HEAD , 45.Nm SLIST_HEAD_INITIALIZER , 46.Nm SLIST_INIT , 47.Nm SLIST_INSERT_AFTER , 48.Nm SLIST_INSERT_HEAD , 49.Nm SLIST_NEXT , 50.Nm SLIST_REMOVE_HEAD , 51.Nm SLIST_REMOVE , 52.Nm STAILQ_EMPTY , 53.Nm STAILQ_ENTRY , 54.Nm STAILQ_FIRST , 55.Nm STAILQ_FOREACH , 56.Nm STAILQ_HEAD , 57.Nm STAILQ_HEAD_INITIALIZER , 58.Nm STAILQ_INIT , 59.Nm STAILQ_INSERT_AFTER , 60.Nm STAILQ_INSERT_HEAD , 61.Nm STAILQ_INSERT_TAIL , 62.Nm STAILQ_LAST , 63.Nm STAILQ_NEXT , 64.Nm STAILQ_REMOVE_HEAD , 65.Nm STAILQ_REMOVE , 66.Nm LIST_EMPTY , 67.Nm LIST_ENTRY , 68.Nm LIST_FIRST , 69.Nm LIST_FOREACH , 70.Nm LIST_HEAD , 71.Nm LIST_HEAD_INITIALIZER , 72.Nm LIST_INIT , 73.Nm LIST_INSERT_AFTER , 74.Nm LIST_INSERT_BEFORE , 75.Nm LIST_INSERT_HEAD , 76.Nm LIST_NEXT , 77.Nm LIST_REMOVE , 78.Nm TAILQ_EMPTY , 79.Nm TAILQ_ENTRY , 80.Nm TAILQ_FIRST , 81.Nm TAILQ_FOREACH , 82.Nm TAILQ_FOREACH_REVERSE , 83.Nm TAILQ_HEAD , 84.Nm TAILQ_HEAD_INITIALIZER , 85.Nm TAILQ_INIT , 86.Nm TAILQ_INSERT_AFTER , 87.Nm TAILQ_INSERT_BEFORE , 88.Nm TAILQ_INSERT_HEAD , 89.Nm TAILQ_INSERT_TAIL , 90.Nm TAILQ_LAST , 91.Nm TAILQ_NEXT , 92.Nm TAILQ_PREV , 93.Nm TAILQ_REMOVE , 94.Nm CIRCLEQ_EMPTY , 95.Nm CIRCLEQ_ENTRY , 96.Nm CIRCLEQ_FIRST , 97.Nm CIRCLEQ_FOREACH , 98.Nm CIRCLEQ_FOREACH_REVERSE , 99.Nm CIRCLEQ_HEAD , 100.Nm CIRCLEQ_HEAD_INITIALIZER , 101.Nm CIRCLEQ_INIT , 102.Nm CIRCLEQ_INSERT_AFTER , 103.Nm CIRCLEQ_INSERT_BEFORE , 104.Nm CIRCLEQ_INSERT_HEAD , 105.Nm CIRCLEQ_INSERT_TAIL , 106.Nm CIRCLE_LAST , 107.Nm CIRCLE_NEXT , 108.Nm CIRCLE_PREV , 109.Nm CIRCLEQ_REMOVE 110.Nd implementations of singly-linked lists, singly-linked tail queues, 111lists, tail queues, and circular queues 112.Sh SYNOPSIS 113.In sys/queue.h 114.\" 115.Fn SLIST_EMPTY "SLIST_HEAD *head" 116.Fn SLIST_ENTRY "TYPE" 117.Fn SLIST_FIRST "SLIST_HEAD *head" 118.Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" 119.Fn SLIST_HEAD "HEADNAME" "TYPE" 120.Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head" 121.Fn SLIST_INIT "SLIST_HEAD *head" 122.Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME" 123.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME" 124.Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME" 125.Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME" 126.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME" 127.\" 128.Fn STAILQ_EMPTY "STAILQ_HEAD *head" 129.Fn STAILQ_ENTRY "TYPE" 130.Fn STAILQ_FIRST "STAILQ_HEAD *head" 131.Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" 132.Fn STAILQ_HEAD "HEADNAME" "TYPE" 133.Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head" 134.Fn STAILQ_INIT "STAILQ_HEAD *head" 135.Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME" 136.Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" 137.Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" 138.Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME" 139.Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME" 140.Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" 141.Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME" 142.\" 143.Fn LIST_EMPTY "LIST_HEAD *head" 144.Fn LIST_ENTRY "TYPE" 145.Fn LIST_FIRST "LIST_HEAD *head" 146.Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" 147.Fn LIST_HEAD "HEADNAME" "TYPE" 148.Fn LIST_HEAD_INITIALIZER "LIST_HEAD head" 149.Fn LIST_INIT "LIST_HEAD *head" 150.Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" 151.Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" 152.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME" 153.Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME" 154.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME" 155.\" 156.Fn TAILQ_EMPTY "TAILQ_HEAD *head" 157.Fn TAILQ_ENTRY "TYPE" 158.Fn TAILQ_FIRST "TAILQ_HEAD *head" 159.Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" 160.Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" 161.Fn TAILQ_HEAD "HEADNAME" "TYPE" 162.Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head" 163.Fn TAILQ_INIT "TAILQ_HEAD *head" 164.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" 165.Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" 166.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 167.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 168.Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME" 169.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME" 170.Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME" 171.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 172.\" 173.Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head" 174.Fn CIRCLEQ_ENTRY "TYPE" 175.Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head" 176.Fn CIRCLEQ_FOREACH "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME" 177.Fn CIRCLEQ_FOREACH_REVERSE "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME" 178.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE" 179.Fn CIRCLEQ_HEAD_INITIALIZER "CIRCLEQ_HEAD head" 180.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head" 181.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 182.Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 183.Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 184.Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 185.Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head" 186.Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME" 187.Fn CIRCLE_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME" 188.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 189.Sh DESCRIPTION 190These macros define and operate on five types of data structures: 191singly-linked lists, singly-linked tail queues, lists, tail queues, 192and circular queues. 193All five structures support the following functionality: 194.Bl -enum -compact -offset indent 195.It 196Insertion of a new entry at the head of the list. 197.It 198Insertion of a new entry after any element in the list. 199.It 200O(1) removal of an entry from the head of the list. 201.It 202O(n) removal of any entry in the list. 203.It 204Forward traversal through the list. 205.El 206.Pp 207Singly-linked lists are the simplest of the five data structures 208and support only the above functionality. 209Singly-linked lists are ideal for applications with large datasets 210and few or no removals, 211or for implementing a LIFO queue. 212.Pp 213Singly-linked tail queues add the following functionality: 214.Bl -enum -compact -offset indent 215.It 216Entries can be added at the end of a list. 217.El 218However: 219.Bl -enum -compact -offset indent 220.It 221All list insertions must specify the head of the list. 222.It 223Each head entry requires two pointers rather than one. 224.It 225Code size is about 15% greater and operations run about 20% slower 226than singly-linked lists. 227.El 228.Pp 229Singly-linked tailqs are ideal for applications with large datasets and 230few or no removals, 231or for implementing a FIFO queue. 232.Pp 233All doubly linked types of data structures (lists, tail queues, and circle 234queues) additionally allow: 235.Bl -enum -compact -offset indent 236.It 237Insertion of a new entry before any element in the list. 238.It 239O(1) removal of any entry in the list. 240.El 241However: 242.Bl -enum -compact -offset indent 243.It 244Each elements requires two pointers rather than one. 245.It 246Code size and execution time of operations (except for removal) is about 247twice that of the singly-linked data-structures. 248.El 249.Pp 250Linked lists are the simplest of the doubly linked data structures and support 251only the above functionality over singly-linked lists. 252.Pp 253Tail queues add the following functionality: 254.Bl -enum -compact -offset indent 255.It 256Entries can be added at the end of a list. 257.It 258They may be traversed backwards, from tail to head. 259.El 260However: 261.Bl -enum -compact -offset indent 262.It 263All list insertions and removals must specify the head of the list. 264.It 265Each head entry requires two pointers rather than one. 266.It 267Code size is about 15% greater and operations run about 20% slower 268than singly-linked lists. 269.El 270.Pp 271Circular queues add the following functionality: 272.Bl -enum -compact -offset indent 273.It 274Entries can be added at the end of a list. 275.It 276They may be traversed backwards, from tail to head. 277.El 278However: 279.Bl -enum -compact -offset indent 280.It 281All list insertions and removals must specify the head of the list. 282.It 283Each head entry requires two pointers rather than one. 284.It 285The termination condition for traversal is more complex. 286.It 287Code size is about 40% greater and operations run about 45% slower 288than lists. 289.El 290.Pp 291In the macro definitions, 292.Fa TYPE 293is the name of a user defined structure, 294that must contain a field of type 295.Li SLIST_ENTRY , 296.Li STAILQ_ENTRY , 297.Li LIST_ENTRY , 298.Li TAILQ_ENTRY , 299or 300.Li CIRCLEQ_ENTRY , 301named 302.Fa NAME . 303The argument 304.Fa HEADNAME 305is the name of a user defined structure that must be declared 306using the macros 307.Li SLIST_HEAD , 308.Li STAILQ_HEAD , 309.Li LIST_HEAD , 310.Li TAILQ_HEAD , 311or 312.Li CIRCLEQ_HEAD . 313See the examples below for further explanation of how these 314macros are used. 315.Sh SINGLY-LINKED LISTS 316A singly-linked list is headed by a structure defined by the 317.Nm SLIST_HEAD 318macro. 319This structure contains a single pointer to the first element 320on the list. 321The elements are singly linked for minimum space and pointer manipulation 322overhead at the expense of O(n) removal for arbitrary elements. 323New elements can be added to the list after an existing element or 324at the head of the list. 325An 326.Fa SLIST_HEAD 327structure is declared as follows: 328.Bd -literal -offset indent 329SLIST_HEAD(HEADNAME, TYPE) head; 330.Ed 331.Pp 332where 333.Fa HEADNAME 334is the name of the structure to be defined, and 335.Fa TYPE 336is the type of the elements to be linked into the list. 337A pointer to the head of the list can later be declared as: 338.Bd -literal -offset indent 339struct HEADNAME *headp; 340.Ed 341.Pp 342(The names 343.Li head 344and 345.Li headp 346are user selectable.) 347.Pp 348The macro 349.Nm SLIST_HEAD_INITIALIZER 350evaluates to an initializer for the list 351.Fa head . 352.Pp 353The macro 354.Nm SLIST_EMPTY 355evaluates to true if there are no elements in the list. 356.Pp 357The macro 358.Nm SLIST_ENTRY 359declares a structure that connects the elements in 360the list. 361.Pp 362The macro 363.Nm SLIST_FIRST 364returns the first element in the list or NULL if the list is empty. 365.Pp 366The macro 367.Nm SLIST_FOREACH 368traverses the list referenced by 369.Fa head 370in the forward direction, assigning each element in 371turn to 372.Fa var . 373.Pp 374The macro 375.Nm SLIST_INIT 376initializes the list referenced by 377.Fa head . 378.Pp 379The macro 380.Nm SLIST_INSERT_HEAD 381inserts the new element 382.Fa elm 383at the head of the list. 384.Pp 385The macro 386.Nm SLIST_INSERT_AFTER 387inserts the new element 388.Fa elm 389after the element 390.Fa listelm . 391.Pp 392The macro 393.Nm SLIST_NEXT 394returns the next element in the list. 395.Pp 396The macro 397.Nm SLIST_REMOVE_HEAD 398removes the element 399.Fa elm 400from the head of the list. 401For optimum efficiency, 402elements being removed from the head of the list should explicitly use 403this macro instead of the generic 404.Fa SLIST_REMOVE 405macro. 406.Pp 407The macro 408.Nm SLIST_REMOVE 409removes the element 410.Fa elm 411from the list. 412.Sh SINGLY-LINKED LIST EXAMPLE 413.Bd -literal 414SLIST_HEAD(slisthead, entry) head = 415 SLIST_HEAD_INITIALIZER(head); 416struct slisthead *headp; /* Singly-linked List head. */ 417struct entry { 418 ... 419 SLIST_ENTRY(entry) entries; /* Singly-linked List. */ 420 ... 421} *n1, *n2, *n3, *np; 422 423SLIST_INIT(&head); /* Initialize the list. */ 424 425n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 426SLIST_INSERT_HEAD(&head, n1, entries); 427 428n2 = malloc(sizeof(struct entry)); /* Insert after. */ 429SLIST_INSERT_AFTER(n1, n2, entries); 430 431SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */ 432free(n2); 433 434n3 = SLIST_FIRST(&head); 435SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */ 436free(n3); 437 /* Forward traversal. */ 438SLIST_FOREACH(np, &head, entries) 439 np-> ... 440 441while (!SLIST_EMPTY(&head)) { /* List Deletion. */ 442 n1 = SLIST_FIRST(&head); 443 SLIST_REMOVE_HEAD(&head, entries); 444 free(n1); 445} 446.Ed 447.Sh SINGLY-LINKED TAIL QUEUES 448A singly-linked tail queue is headed by a structure defined by the 449.Nm STAILQ_HEAD 450macro. 451This structure contains a pair of pointers, 452one to the first element in the tail queue and the other to 453the last element in the tail queue. 454The elements are singly linked for minimum space and pointer 455manipulation overhead at the expense of O(n) removal for arbitrary 456elements. 457New elements can be added to the tail queue after an existing element, 458at the head of the tail queue, or at the end of the tail queue. 459A 460.Fa STAILQ_HEAD 461structure is declared as follows: 462.Bd -literal -offset indent 463STAILQ_HEAD(HEADNAME, TYPE) head; 464.Ed 465.Pp 466where 467.Li HEADNAME 468is the name of the structure to be defined, and 469.Li TYPE 470is the type of the elements to be linked into the tail queue. 471A pointer to the head of the tail queue can later be declared as: 472.Bd -literal -offset indent 473struct HEADNAME *headp; 474.Ed 475.Pp 476(The names 477.Li head 478and 479.Li headp 480are user selectable.) 481.Pp 482The macro 483.Nm STAILQ_HEAD_INITIALIZER 484evaluates to an initializer for the tail queue 485.Fa head . 486.Pp 487The macro 488.Nm STAILQ_EMPTY 489evaluates to true if there are no items on the tail queue. 490.Pp 491The macro 492.Nm STAILQ_ENTRY 493declares a structure that connects the elements in 494the tail queue. 495.Pp 496The macro 497.Nm STAILQ_FIRST 498returns the first item on the tail queue or NULL if the tail queue 499is empty. 500.Pp 501The macro 502.Nm STAILQ_FOREACH 503traverses the tail queue referenced by 504.Fa head 505in the forward direction, assigning each element 506in turn to 507.Fa var . 508.Pp 509The macro 510.Nm STAILQ_INIT 511initializes the tail queue referenced by 512.Fa head . 513.Pp 514The macro 515.Nm STAILQ_INSERT_HEAD 516inserts the new element 517.Fa elm 518at the head of the tail queue. 519.Pp 520The macro 521.Nm STAILQ_INSERT_TAIL 522inserts the new element 523.Fa elm 524at the end of the tail queue. 525.Pp 526The macro 527.Nm STAILQ_INSERT_AFTER 528inserts the new element 529.Fa elm 530after the element 531.Fa listelm . 532.Pp 533The macro 534.Nm STAILQ_LAST 535returns the last item on the tail queue. 536If the tail queue is empty the return value is undefined. 537.Pp 538The macro 539.Nm STAILQ_NEXT 540returns the next item on the tail queue, or NULL this item is the last. 541.Pp 542The macro 543.Nm STAILQ_REMOVE_HEAD 544removes the element at the head of the tail queue. 545For optimum efficiency, 546elements being removed from the head of the tail queue should 547use this macro explicitly rather than the generic 548.Fa STAILQ_REMOVE 549macro. 550.Pp 551The macro 552.Nm STAILQ_REMOVE 553removes the element 554.Fa elm 555from the tail queue. 556.Sh SINGLY-LINKED TAIL QUEUE EXAMPLE 557.Bd -literal 558STAILQ_HEAD(stailhead, entry) head = 559 STAILQ_HEAD_INITIALIZER(head); 560struct stailhead *headp; /* Singly-linked tail queue head. */ 561struct entry { 562 ... 563 STAILQ_ENTRY(entry) entries; /* Tail queue. */ 564 ... 565} *n1, *n2, *n3, *np; 566 567STAILQ_INIT(&head); /* Initialize the queue. */ 568 569n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 570STAILQ_INSERT_HEAD(&head, n1, entries); 571 572n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 573STAILQ_INSERT_TAIL(&head, n1, entries); 574 575n2 = malloc(sizeof(struct entry)); /* Insert after. */ 576STAILQ_INSERT_AFTER(&head, n1, n2, entries); 577 /* Deletion. */ 578STAILQ_REMOVE(&head, n2, entry, entries); 579free(n2); 580 /* Deletion from the head. */ 581n3 = STAILQ_FIRST(&head); 582STAILQ_REMOVE_HEAD(&head, entries); 583free(n3); 584 /* Forward traversal. */ 585STAILQ_FOREACH(np, &head, entries) 586 np-> ... 587 /* TailQ Deletion. */ 588while (!STAILQ_EMPTY(&head)) { 589 n1 = STAILQ_FIRST(&head); 590 STAILQ_REMOVE_HEAD(&head, entries); 591 free(n1); 592} 593 /* Faster TailQ Deletion. */ 594n1 = STAILQ_FIRST(&head); 595while (n1 != NULL) { 596 n2 = STAILQ_NEXT(n1, entries); 597 free(n1); 598 n1 = n2; 599} 600STAILQ_INIT(&head); 601.Ed 602.Sh LISTS 603A list is headed by a structure defined by the 604.Nm LIST_HEAD 605macro. 606This structure contains a single pointer to the first element 607on the list. 608The elements are doubly linked so that an arbitrary element can be 609removed without traversing the list. 610New elements can be added to the list after an existing element, 611before an existing element, or at the head of the list. 612A 613.Fa LIST_HEAD 614structure is declared as follows: 615.Bd -literal -offset indent 616LIST_HEAD(HEADNAME, TYPE) head; 617.Ed 618.Pp 619where 620.Fa HEADNAME 621is the name of the structure to be defined, and 622.Fa TYPE 623is the type of the elements to be linked into the list. 624A pointer to the head of the list can later be declared as: 625.Bd -literal -offset indent 626struct HEADNAME *headp; 627.Ed 628.Pp 629(The names 630.Li head 631and 632.Li headp 633are user selectable.) 634.Pp 635The macro 636.Nm LIST_HEAD_INITIALIZER 637evaluates to an initializer for the list 638.Fa head . 639.Pp 640The macro 641.Nm LIST_EMPTY 642evaluates to true if their are no elements in the list. 643.Pp 644The macro 645.Nm LIST_ENTRY 646declares a structure that connects the elements in 647the list. 648.Pp 649The macro 650.Nm LIST_FIRST 651returns the first element in the list or NULL if the list 652is empty. 653.Pp 654The macro 655.Nm LIST_FOREACH 656traverses the list referenced by 657.Fa head 658in the forward direction, assigning each element in turn to 659.Fa var . 660.Pp 661The macro 662.Nm LIST_INIT 663initializes the list referenced by 664.Fa head . 665.Pp 666The macro 667.Nm LIST_INSERT_HEAD 668inserts the new element 669.Fa elm 670at the head of the list. 671.Pp 672The macro 673.Nm LIST_INSERT_AFTER 674inserts the new element 675.Fa elm 676after the element 677.Fa listelm . 678.Pp 679The macro 680.Nm LIST_INSERT_BEFORE 681inserts the new element 682.Fa elm 683before the element 684.Fa listelm . 685.Pp 686The macro 687.Nm LIST_NEXT 688returns the next element in the list, or NULL if this is the last. 689.Pp 690The macro 691.Nm LIST_REMOVE 692removes the element 693.Fa elm 694from the list. 695.Sh LIST EXAMPLE 696.Bd -literal 697LIST_HEAD(listhead, entry) head = 698 LIST_HEAD_INITIALIZER(head); 699struct listhead *headp; /* List head. */ 700struct entry { 701 ... 702 LIST_ENTRY(entry) entries; /* List. */ 703 ... 704} *n1, *n2, *n3, *np; 705 706LIST_INIT(&head); /* Initialize the list. */ 707 708n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 709LIST_INSERT_HEAD(&head, n1, entries); 710 711n2 = malloc(sizeof(struct entry)); /* Insert after. */ 712LIST_INSERT_AFTER(n1, n2, entries); 713 714n3 = malloc(sizeof(struct entry)); /* Insert before. */ 715LIST_INSERT_BEFORE(n2, n3, entries); 716 717LIST_REMOVE(n2, entries); /* Deletion. */ 718free(n2); 719 /* Forward traversal. */ 720LIST_FOREACH(np, &head, entries) 721 np-> ... 722 723while (!LIST_EMPTY(&head)) { /* List Deletion. */ 724 n1 = LIST_FIRST(&head); 725 LIST_REMOVE(n1, entries); 726 free(n1); 727} 728 729n1 = LIST_FIRST(&head); /* Faster List Deletion. */ 730while (n1 != NULL) { 731 n2 = LIST_NEXT(n1, entries); 732 free(n1); 733 n1 = n2; 734} 735LIST_INIT(&head); 736.Ed 737.Sh TAIL QUEUES 738A tail queue is headed by a structure defined by the 739.Nm TAILQ_HEAD 740macro. 741This structure contains a pair of pointers, 742one to the first element in the tail queue and the other to 743the last element in the tail queue. 744The elements are doubly linked so that an arbitrary element can be 745removed without traversing the tail queue. 746New elements can be added to the tail queue after an existing element, 747before an existing element, at the head of the tail queue, 748or at the end of the tail queue. 749A 750.Fa TAILQ_HEAD 751structure is declared as follows: 752.Bd -literal -offset indent 753TAILQ_HEAD(HEADNAME, TYPE) head; 754.Ed 755.Pp 756where 757.Li HEADNAME 758is the name of the structure to be defined, and 759.Li TYPE 760is the type of the elements to be linked into the tail queue. 761A pointer to the head of the tail queue can later be declared as: 762.Bd -literal -offset indent 763struct HEADNAME *headp; 764.Ed 765.Pp 766(The names 767.Li head 768and 769.Li headp 770are user selectable.) 771.Pp 772The macro 773.Nm TAILQ_HEAD_INITIALIZER 774evaluates to an initializer for the tail queue 775.Fa head . 776.Pp 777The macro 778.Nm TAILQ_EMPTY 779evaluates to true if there are no items on the tail queue. 780.Pp 781The macro 782.Nm TAILQ_ENTRY 783declares a structure that connects the elements in 784the tail queue. 785.Pp 786The macro 787.Nm TAILQ_FIRST 788returns the first item on the tail queue or NULL if the tail queue 789is empty. 790.Pp 791The macro 792.Nm TAILQ_FOREACH 793traverses the tail queue referenced by 794.Fa head 795in the forward direction, assigning each element in turn to 796.Fa var . 797.Pp 798The macro 799.Nm TAILQ_FOREACH_REVERSE 800traverses the tail queue referenced by 801.Fa head 802in the reverse direction, assigning each element in turn to 803.Fa var . 804.Pp 805The macro 806.Nm TAILQ_INIT 807initializes the tail queue referenced by 808.Fa head . 809.Pp 810The macro 811.Nm TAILQ_INSERT_HEAD 812inserts the new element 813.Fa elm 814at the head of the tail queue. 815.Pp 816The macro 817.Nm TAILQ_INSERT_TAIL 818inserts the new element 819.Fa elm 820at the end of the tail queue. 821.Pp 822The macro 823.Nm TAILQ_INSERT_AFTER 824inserts the new element 825.Fa elm 826after the element 827.Fa listelm . 828.Pp 829The macro 830.Nm TAILQ_INSERT_BEFORE 831inserts the new element 832.Fa elm 833before the element 834.Fa listelm . 835.Pp 836The macro 837.Nm TAILQ_LAST 838returns the last item on the tail queue. 839If the tail queue is empty the return value is undefined. 840.Pp 841The macro 842.Nm TAILQ_NEXT 843returns the next item on the tail queue, or NULL if this item is the last. 844.Pp 845The macro 846.Nm TAILQ_PREV 847returns the previous item on the tail queue, or NULL if this item 848is the first. 849.Pp 850The macro 851.Nm TAILQ_REMOVE 852removes the element 853.Fa elm 854from the tail queue. 855.Sh TAIL QUEUE EXAMPLE 856.Bd -literal 857TAILQ_HEAD(tailhead, entry) head = 858 TAILQ_HEAD_INITIALIZER(head); 859struct tailhead *headp; /* Tail queue head. */ 860struct entry { 861 ... 862 TAILQ_ENTRY(entry) entries; /* Tail queue. */ 863 ... 864} *n1, *n2, *n3, *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 877n3 = malloc(sizeof(struct entry)); /* Insert before. */ 878TAILQ_INSERT_BEFORE(n2, n3, entries); 879 880TAILQ_REMOVE(&head, n2, entries); /* Deletion. */ 881free(n2); 882 /* Forward traversal. */ 883TAILQ_FOREACH(np, &head, entries) 884 np-> ... 885 /* Reverse traversal. */ 886TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries) 887 np-> ... 888 /* TailQ Deletion. */ 889while (!TAILQ_EMPTY(&head)) { 890 n1 = TAILQ_FIRST(&head); 891 TAILQ_REMOVE(&head, n1, entries); 892 free(n1); 893} 894 /* Faster TailQ Deletion. */ 895n1 = TAILQ_FIRST(&head); 896while (n1 != NULL) { 897 n2 = TAILQ_NEXT(n1, entries); 898 free(n1); 899 n1 = n2; 900} 901TAILQ_INIT(&head); 902.Ed 903.Sh CIRCULAR QUEUES 904A circular queue is headed by a structure defined by the 905.Nm CIRCLEQ_HEAD 906macro. 907This structure contains a pair of pointers, 908one to the first element in the circular queue and the other to the 909last element in the circular queue. 910The elements are doubly linked so that an arbitrary element can be 911removed without traversing the queue. 912New elements can be added to the queue after an existing element, 913before an existing element, at the head of the queue, or at the end 914of the queue. 915A 916.Fa CIRCLEQ_HEAD 917structure is declared as follows: 918.Bd -literal -offset indent 919CIRCLEQ_HEAD(HEADNAME, TYPE) head; 920.Ed 921.Pp 922where 923.Li HEADNAME 924is the name of the structure to be defined, and 925.Li TYPE 926is the type of the elements to be linked into the circular queue. 927A pointer to the head of the circular queue can later be declared as: 928.Bd -literal -offset indent 929struct HEADNAME *headp; 930.Ed 931.Pp 932(The names 933.Li head 934and 935.Li headp 936are user selectable.) 937.Pp 938The macro 939.Nm CIRCLEQ_HEAD_INITIALIZER 940evaluates to an initializer for the circle queue 941.Fa head . 942.Pp 943The macro 944.Nm CIRCLEQ_EMPTY 945evaluates to true if there are no items on the circle queue. 946.Pp 947The macro 948.Nm CIRCLEQ_ENTRY 949declares a structure that connects the elements in 950the circular queue. 951.Pp 952The macro 953.Nm CIRCLEQ_FIRST 954returns the first item on the circle queue. 955.Pp 956The macro 957.Nm CICRLEQ_FOREACH 958traverses the circle queue referenced by 959.Fa head 960in the forward direction, assigning each element in turn to 961.Fa var . 962.Pp 963The macro 964.Nm CICRLEQ_FOREACH_REVERSE 965traverses the circle queue referenced by 966.Fa head 967in the reverse direction, assigning each element in turn to 968.Fa var . 969.Pp 970The macro 971.Nm CIRCLEQ_INIT 972initializes the circular queue referenced by 973.Fa head . 974.Pp 975The macro 976.Nm CIRCLEQ_INSERT_HEAD 977inserts the new element 978.Fa elm 979at the head of the circular queue. 980.Pp 981The macro 982.Nm CIRCLEQ_INSERT_TAIL 983inserts the new element 984.Fa elm 985at the end of the circular queue. 986.Pp 987The macro 988.Nm CIRCLEQ_INSERT_AFTER 989inserts the new element 990.Fa elm 991after the element 992.Fa listelm . 993.Pp 994The macro 995.Nm CIRCLEQ_INSERT_BEFORE 996inserts the new element 997.Fa elm 998before the element 999.Fa listelm . 1000.Pp 1001The macro 1002.Nm CIRCLEQ_LAST 1003returns the last item on the circle queue. 1004.Pp 1005The macro 1006.Nm CIRCLEQ_NEXT 1007returns the next item on the circle queue. 1008.Pp 1009The macro 1010.Nm CIRCLEQ_PREV 1011returns the previous item on the circle queue. 1012.Pp 1013The macro 1014.Nm CIRCLEQ_REMOVE 1015removes the element 1016.Fa elm 1017from the circular queue. 1018.Sh CIRCULAR QUEUE EXAMPLE 1019.Bd -literal 1020CIRCLEQ_HEAD(circlehead, entry) head = 1021 CIRCLEQ_HEAD_INITIALIZER(head); 1022struct circlehead *headp; /* Circular queue head. */ 1023struct entry { 1024 ... 1025 CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */ 1026 ... 1027} *n1, *n2, *np; 1028 1029CIRCLEQ_INIT(&head); /* Initialize the circular queue. */ 1030 1031n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 1032CIRCLEQ_INSERT_HEAD(&head, n1, entries); 1033 1034n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 1035CIRCLEQ_INSERT_TAIL(&head, n1, entries); 1036 1037n2 = malloc(sizeof(struct entry)); /* Insert after. */ 1038CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries); 1039 1040n2 = malloc(sizeof(struct entry)); /* Insert before. */ 1041CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries); 1042 1043CIRCLEQ_REMOVE(&head, n1, entries); /* Deletion. */ 1044free(n1); 1045 /* Forward traversal. */ 1046CIRCLEQ_FOREACH(np, &head, entries) 1047 np-> ... 1048 /* Reverse traversal. */ 1049CIRCLEQ_FOREACH_REVERSE(np, &head, entries) 1050 np-> ... 1051 /* CircleQ Deletion. */ 1052while (CIRCLEQ_FIRST(&head) != (void *)&head) { 1053 n1 = CIRCLEQ_HEAD(&head); 1054 CIRCLEQ_REMOVE(&head, n1, entries); 1055 free(n1); 1056} 1057 /* Faster CircleQ Deletion. */ 1058n1 = CIRCLEQ_FIRST(&head); 1059while (n1 != (void *)&head) { 1060 n2 = CIRCLEQ_NEXT(n1, entries); 1061 free(n1); 1062 n1 = n2; 1063} 1064CIRCLEQ_INIT(&head); 1065.Ed 1066.Sh HISTORY 1067The 1068.Nm queue 1069functions first appeared in 1070.Bx 4.4 . 1071