1.\" $NetBSD: queue.3,v 1.4 1995/07/03 00:25:36 mycroft Exp $ 2.\" 3.\" Copyright (c) 1993 The Regents of the University of California. 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 University of 17.\" California, Berkeley and its contributors. 18.\" 4. Neither the name of the University nor the names of its contributors 19.\" may be used to endorse or promote products derived from this software 20.\" without specific prior written permission. 21.\" 22.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32.\" SUCH DAMAGE. 33.\" 34.\" @(#)queue.3 8.1 (Berkeley) 12/13/93 35.\" 36.Dd "December 13, 1993" 37.Dt QUEUE 3 38.Os BSD 4 39.Sh NAME 40.Nm LIST_ENTRY , 41.Nm LIST_HEAD , 42.Nm LIST_INIT , 43.Nm LIST_INSERT_AFTER , 44.Nm LIST_INSERT_BEFORE , 45.Nm LIST_INSERT_HEAD , 46.Nm LIST_REMOVE , 47.Nm TAILQ_ENTRY , 48.Nm TAILQ_HEAD , 49.Nm TAILQ_INIT , 50.Nm TAILQ_INSERT_AFTER , 51.Nm TAILQ_INSERT_BEFORE , 52.Nm TAILQ_INSERT_HEAD , 53.Nm TAILQ_INSERT_TAIL , 54.Nm TAILQ_REMOVE , 55.Nm CIRCLEQ_ENTRY , 56.Nm CIRCLEQ_HEAD , 57.Nm CIRCLEQ_INIT , 58.Nm CIRCLEQ_INSERT_AFTER , 59.Nm CIRCLEQ_INSERT_BEFORE , 60.Nm CIRCLEQ_INSERT_HEAD , 61.Nm CIRCLEQ_INSERT_TAIL , 62.Nm CIRCLEQ_REMOVE 63.Nd implementations of lists, tail queues, and circular queues 64.Sh SYNOPSIS 65.Fd #include <sys/queue.h> 66.sp 67.Fn LIST_ENTRY "TYPE" 68.Fn LIST_HEAD "HEADNAME" "TYPE" 69.Fn LIST_INIT "LIST_HEAD *head" 70.Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" 71.Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" 72.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME" 73.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME" 74.sp 75.Fn TAILQ_ENTRY "TYPE" 76.Fn TAILQ_HEAD "HEADNAME" "TYPE" 77.Fn TAILQ_INIT "TAILQ_HEAD *head" 78.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" 79.Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" 80.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 81.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 82.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 83.sp 84.Fn CIRCLEQ_ENTRY "TYPE" 85.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE" 86.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head" 87.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 88.Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 89.Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 90.Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 91.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" 92.Sh DESCRIPTION 93These macros define and operate on three types of data structures: 94lists, tail queues, and circular queues. 95All three structures support the following functionality: 96.Bl -enum -compact -offset indent 97.It 98Insertion of a new entry at the head of the list. 99.It 100Insertion of a new entry before or after any element in the list. 101.It 102Removal of any entry in the list. 103.It 104Forward traversal through the list. 105.El 106.Pp 107Lists are the simplest of the three data structures and support 108only the above functionality. 109.Pp 110Tail queues add the following functionality: 111.Bl -enum -compact -offset indent 112.It 113Entries can be added at the end of a list. 114.El 115However: 116.Bl -enum -compact -offset indent 117.It 118All list insertions and removals, except insertion before another element, must 119specify the head of the list. 120.It 121Each head entry requires two pointers rather than one. 122.It 123Code size is about 15% greater and operations run about 20% slower 124than lists. 125.El 126.Pp 127Circular queues add the following functionality: 128.Bl -enum -compact -offset indent 129.It 130Entries can be added at the end of a list. 131.It 132They may be traversed backwards, from tail to head. 133.El 134However: 135.Bl -enum -compact -offset indent 136.It 137All list insertions and removals must specify the head of the list. 138.It 139Each head entry requires two pointers rather than one. 140.It 141The termination condition for traversal is more complex. 142.It 143Code size is about 40% greater and operations run about 45% slower 144than lists. 145.El 146.Pp 147In the macro definitions, 148.Fa TYPE 149is the name of a user defined structure, 150that must contain a field of type 151.Li LIST_ENTRY , 152.Li TAILQ_ENTRY , 153or 154.Li CIRCLEQ_ENTRY , 155named 156.Fa NAME . 157The argument 158.Fa HEADNAME 159is the name of a user defined structure that must be declared 160using the macros 161.Li LIST_HEAD , 162.Li TAILQ_HEAD , 163or 164.Li CIRCLEQ_HEAD . 165See the examples below for further explanation of how these 166macros are used. 167.Sh LISTS 168A list is headed by a structure defined by the 169.Nm LIST_HEAD 170macro. 171This structure contains a single pointer to the first element 172on the list. 173The elements are doubly linked so that an arbitrary element can be 174removed without traversing the list. 175New elements can be added to the list after an existing element, 176before an existing element, or at the head of the list. 177A 178.Fa LIST_HEAD 179structure is declared as follows: 180.Bd -literal -offset indent 181LIST_HEAD(HEADNAME, TYPE) head; 182.Ed 183.sp 184where 185.Fa HEADNAME 186is the name of the structure to be defined, and 187.Fa TYPE 188is the type of the elements to be linked into the list. 189A pointer to the head of the list can later be declared as: 190.Bd -literal -offset indent 191struct HEADNAME *headp; 192.Ed 193.sp 194(The names 195.Li head 196and 197.Li headp 198are user selectable.) 199.Pp 200The macro 201.Nm LIST_ENTRY 202declares a structure that connects the elements in 203the list. 204.Pp 205The macro 206.Nm LIST_INIT 207initializes the list referenced by 208.Fa head . 209.Pp 210The macro 211.Nm LIST_INSERT_HEAD 212inserts the new element 213.Fa elm 214at the head of the list. 215.Pp 216The macro 217.Nm LIST_INSERT_AFTER 218inserts the new element 219.Fa elm 220after the element 221.Fa listelm . 222.Pp 223The macro 224.Nm LIST_INSERT_BEFORE 225inserts the new element 226.Fa elm 227before the element 228.Fa listelm . 229.Pp 230The macro 231.Nm LIST_REMOVE 232removes the element 233.Fa elm 234from the list. 235.Sh LIST EXAMPLE 236.Bd -literal 237LIST_HEAD(listhead, entry) head; 238struct listhead *headp; /* List head. */ 239struct entry { 240 ... 241 LIST_ENTRY(entry) entries; /* List. */ 242 ... 243} *n1, *n2, *np; 244 245LIST_INIT(&head); /* Initialize the list. */ 246 247n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 248LIST_INSERT_HEAD(&head, n1, entries); 249 250n2 = malloc(sizeof(struct entry)); /* Insert after. */ 251LIST_INSERT_AFTER(n1, n2, entries); 252 253n2 = malloc(sizeof(struct entry)); /* Insert before. */ 254LIST_INSERT_BEFORE(n1, n2, entries); 255 /* Forward traversal. */ 256for (np = head.lh_first; np != NULL; np = np->entries.le_next) 257 np-> ... 258 259while (head.lh_first != NULL) /* Delete. */ 260 LIST_REMOVE(head.lh_first, entries); 261.Ed 262.Sh TAIL QUEUES 263A tail queue is headed by a structure defined by the 264.Nm TAILQ_HEAD 265macro. 266This structure contains a pair of pointers, 267one to the first element in the tail queue and the other to 268the last element in the tail queue. 269The elements are doubly linked so that an arbitrary element can be 270removed without traversing the tail queue. 271New elements can be added to the queue after an existing element, 272before an existing element, at the head of the queue, or at the end 273the queue. 274A 275.Fa TAILQ_HEAD 276structure is declared as follows: 277.Bd -literal -offset indent 278TAILQ_HEAD(HEADNAME, TYPE) head; 279.Ed 280.sp 281where 282.Li HEADNAME 283is the name of the structure to be defined, and 284.Li TYPE 285is the type of the elements to be linked into the tail queue. 286A pointer to the head of the tail queue can later be declared as: 287.Bd -literal -offset indent 288struct HEADNAME *headp; 289.Ed 290.sp 291(The names 292.Li head 293and 294.Li headp 295are user selectable.) 296.Pp 297The macro 298.Nm TAILQ_ENTRY 299declares a structure that connects the elements in 300the tail queue. 301.Pp 302The macro 303.Nm TAILQ_INIT 304initializes the tail queue referenced by 305.Fa head . 306.Pp 307The macro 308.Nm TAILQ_INSERT_HEAD 309inserts the new element 310.Fa elm 311at the head of the tail queue. 312.Pp 313The macro 314.Nm TAILQ_INSERT_TAIL 315inserts the new element 316.Fa elm 317at the end of the tail queue. 318.Pp 319The macro 320.Nm TAILQ_INSERT_AFTER 321inserts the new element 322.Fa elm 323after the element 324.Fa listelm . 325.Pp 326The macro 327.Nm TAILQ_INSERT_BEFORE 328inserts the new element 329.Fa elm 330before the element 331.Fa listelm . 332.Pp 333The macro 334.Nm TAILQ_REMOVE 335removes the element 336.Fa elm 337from the tail queue. 338.Sh TAIL QUEUE EXAMPLE 339.Bd -literal 340TAILQ_HEAD(tailhead, entry) head; 341struct tailhead *headp; /* Tail queue head. */ 342struct entry { 343 ... 344 TAILQ_ENTRY(entry) entries; /* Tail queue. */ 345 ... 346} *n1, *n2, *np; 347 348TAILQ_INIT(&head); /* Initialize the queue. */ 349 350n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 351TAILQ_INSERT_HEAD(&head, n1, entries); 352 353n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 354TAILQ_INSERT_TAIL(&head, n1, entries); 355 356n2 = malloc(sizeof(struct entry)); /* Insert after. */ 357TAILQ_INSERT_AFTER(&head, n1, n2, entries); 358 359n2 = malloc(sizeof(struct entry)); /* Insert before. */ 360TAILQ_INSERT_BEFORE(n1, n2, entries); 361 /* Forward traversal. */ 362for (np = head.tqh_first; np != NULL; np = np->entries.tqe_next) 363 np-> ... 364 /* Delete. */ 365while (head.tqh_first != NULL) 366 TAILQ_REMOVE(&head, head.tqh_first, entries); 367.Ed 368.Sh CIRCULAR QUEUES 369A circular queue is headed by a structure defined by the 370.Nm CIRCLEQ_HEAD 371macro. 372This structure contains a pair of pointers, 373one to the first element in the circular queue and the other to the 374last element in the circular queue. 375The elements are doubly linked so that an arbitrary element can be 376removed without traversing the queue. 377New elements can be added to the queue after an existing element, 378before an existing element, at the head of the queue, or at the end 379of the queue. 380A 381.Fa CIRCLEQ_HEAD 382structure is declared as follows: 383.Bd -literal -offset indent 384CIRCLEQ_HEAD(HEADNAME, TYPE) head; 385.Ed 386.sp 387where 388.Li HEADNAME 389is the name of the structure to be defined, and 390.Li TYPE 391is the type of the elements to be linked into the circular queue. 392A pointer to the head of the circular queue can later be declared as: 393.Bd -literal -offset indent 394struct HEADNAME *headp; 395.Ed 396.sp 397(The names 398.Li head 399and 400.Li headp 401are user selectable.) 402.Pp 403The macro 404.Nm CIRCLEQ_ENTRY 405declares a structure that connects the elements in 406the circular queue. 407.Pp 408The macro 409.Nm CIRCLEQ_INIT 410initializes the circular queue referenced by 411.Fa head . 412.Pp 413The macro 414.Nm CIRCLEQ_INSERT_HEAD 415inserts the new element 416.Fa elm 417at the head of the circular queue. 418.Pp 419The macro 420.Nm CIRCLEQ_INSERT_TAIL 421inserts the new element 422.Fa elm 423at the end of the circular queue. 424.Pp 425The macro 426.Nm CIRCLEQ_INSERT_AFTER 427inserts the new element 428.Fa elm 429after the element 430.Fa listelm . 431.Pp 432The macro 433.Nm CIRCLEQ_INSERT_BEFORE 434inserts the new element 435.Fa elm 436before the element 437.Fa listelm . 438.Pp 439The macro 440.Nm CIRCLEQ_REMOVE 441removes the element 442.Fa elm 443from the circular queue. 444.Sh CIRCULAR QUEUE EXAMPLE 445.Bd -literal 446CIRCLEQ_HEAD(circleq, entry) head; 447struct circleq *headp; /* Circular queue head. */ 448struct entry { 449 ... 450 CIRCLEQ_ENTRY entries; /* Circular queue. */ 451 ... 452} *n1, *n2, *np; 453 454CIRCLEQ_INIT(&head); /* Initialize the circular queue. */ 455 456n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 457CIRCLEQ_INSERT_HEAD(&head, n1, entries); 458 459n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 460CIRCLEQ_INSERT_TAIL(&head, n1, entries); 461 462n2 = malloc(sizeof(struct entry)); /* Insert after. */ 463CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries); 464 465n2 = malloc(sizeof(struct entry)); /* Insert before. */ 466CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries); 467 /* Forward traversal. */ 468for (np = head.cqh_first; np != (void *)&head; np = np->entries.cqe_next) 469 np-> ... 470 /* Reverse traversal. */ 471for (np = head.cqh_last; np != (void *)&head; np = np->entries.cqe_prev) 472 np-> ... 473 /* Delete. */ 474while (head.cqh_first != (void *)&head) 475 CIRCLEQ_REMOVE(&head, head.cqh_first, entries); 476.Ed 477.Sh HISTORY 478The 479.Nm queue 480functions first appeared in 4.4BSD. 481