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