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