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