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