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