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.Pp 97.Bl -enum -compact -offset indent 98.It 99Insertion of a new entry at the head of the list. 100.It 101Insertion of a new entry before or after any list element. 102.It 103Removal of any entry in the list. 104.It 105Forward traversal through the list. 106.El 107.Pp 108Lists are the simplest of the three data structures and support 109only the above functionality. 110.Pp 111Tail queues add the following functionality: 112.Bl -enum -offset indent 113.It 114Entries can be added to the end of a list. 115.El 116.Pp 117However: 118.Pp 119.Bl -enum -compact -offset indent 120.It 121All list insertions and removals, except insertion before another element, must 122specify the head of the list. 123.It 124Each head entry requires two pointers rather than one. 125.It 126Code size is about 15% greater and operations run about 20% slower 127than lists. 128.El 129.Pp 130Circular queues add the following functionality: 131.Pp 132.Bl -enum -compact -offset indent 133.It 134Entries can be added to the end of a list. 135.It 136They may be traversed backwards, from tail to head. 137.El 138.Pp 139However: 140.Pp 141.Bl -enum -compact -offset indent 142.It 143All list insertions and removals must specify the head of the list. 144.It 145Each head entry requires two pointers rather than one. 146.It 147The termination condition for traversal is more complex. 148.It 149Code size is about 40% greater and operations run about 45% slower 150than lists. 151.El 152.Pp 153In the macro definitions, 154.Fa TYPE 155is the name of a user defined structure, 156that must contain a field of type 157.Li LIST_ENTRY , 158.Li TAILQ_ENTRY , 159or 160.Li CIRCLEQ_ENTRY , 161named 162.Fa NAME . 163The argument 164.Fa HEADNAME 165is the name of a user defined structure that must be declared 166using the macros 167.Fn LIST_HEAD , 168.Fn TAILQ_HEAD , 169or 170.Fn CIRCLEQ_HEAD . 171See the examples below for further explanation of how these 172macros are used. 173.Sh LISTS 174A list is headed by a structure defined by the 175.Fn LIST_HEAD 176macro. 177This structure contains a single pointer to the first element 178on the list. 179The elements are doubly linked so that an arbitrary element can be 180removed without traversing the list. 181New elements can be added to the list after an existing element, 182before an existing element, or at the head of the list. 183A 184.Fa LIST_HEAD 185structure is declared as follows: 186.Bd -literal -offset indent 187LIST_HEAD(HEADNAME, TYPE) head; 188.Ed 189.sp 190where 191.Fa HEADNAME 192is the name of the structure to be defined, and 193.Fa TYPE 194is the type of the elements to be linked into the list. 195A pointer to the head of the list can later be declared as: 196.Bd -literal -offset indent 197struct HEADNAME *headp; 198.Ed 199.sp 200(The names 201.Li head 202and 203.Li headp 204are user selectable.) 205.Pp 206The 207.Fn LIST_ENTRY 208macro declares a structure that connects the elements in 209the list. 210.Pp 211The 212.Fn LIST_INIT 213macro initializes the list referenced by 214.Fa head . 215.Pp 216The 217.Fn LIST_INSERT_HEAD 218macro inserts the new element 219.Fa elm 220at the head of the list. 221.Pp 222The 223.Fn LIST_INSERT_AFTER 224macro inserts the new element 225.Fa elm 226after the element 227.Fa listelm . 228.Pp 229The 230.Fn LIST_INSERT_BEFORE 231macro inserts the new element 232.Fa elm 233before the element 234.Fa listelm . 235.Pp 236The 237.Fn LIST_REMOVE 238macro removes the element 239.Fa elm 240from the list. 241.Sh LIST EXAMPLE 242.Bd -literal 243LIST_HEAD(listhead, entry) head; 244struct listhead *headp; /* List head. */ 245struct entry { 246 ... 247 LIST_ENTRY(entry) entries; /* List. */ 248 ... 249} *n1, *n2, *np; 250 251LIST_INIT(&head); /* Initialize the list. */ 252 253n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 254LIST_INSERT_HEAD(&head, n1, entries); 255 256n2 = malloc(sizeof(struct entry)); /* Insert after. */ 257LIST_INSERT_AFTER(n1, n2, entries); 258 259n2 = malloc(sizeof(struct entry)); /* Insert before. */ 260LIST_INSERT_BEFORE(n1, n2, entries); 261 /* Forward traversal. */ 262for (np = head.lh_first; np != NULL; np = np->entries.le_next) 263 np-> ... 264 265while (head.lh_first != NULL) /* Delete. */ 266 LIST_REMOVE(head.lh_first, entries); 267.Ed 268.Sh TAIL QUEUES 269A tail queue is headed by a structure defined by the 270.Fn TAILQ_HEAD 271macro. 272This structure contains a pair of pointers, 273one to the first element in the tail queue and the other to 274the last element in the tail queue. 275The elements are doubly linked so that an arbitrary element can be 276removed without traversing the tail queue. 277New elements can be added to the queue after an existing element, 278before an existing element, at the head of the queue, or at the end 279the queue. 280A 281.Fa TAILQ_HEAD 282structure is declared as follows: 283.Bd -literal -offset indent 284TAILQ_HEAD(HEADNAME, TYPE) head; 285.Ed 286.sp 287where 288.Fa HEADNAME 289is the name of the structure to be defined, and 290.Fa TYPE 291is the type of the elements to be linked into the tail queue. 292A pointer to the head of the tail queue can later be declared as: 293.Bd -literal -offset indent 294struct HEADNAME *headp; 295.Ed 296.sp 297(The names 298.Li head 299and 300.Li headp 301are user selectable.) 302.Pp 303The 304.Fn TAILQ_ENTRY 305macro declares a structure that connects the elements in 306the tail queue. 307.Pp 308The 309.Fn TAILQ_INIT 310macro initializes the tail queue referenced by 311.Fa head . 312.Pp 313The 314.Fn TAILQ_INSERT_HEAD 315macro inserts the new element 316.Fa elm 317at the head of the tail queue. 318.Pp 319The 320.Fn TAILQ_INSERT_TAIL 321macro inserts the new element 322.Fa elm 323at the end of the tail queue. 324.Pp 325The 326.Fn TAILQ_INSERT_AFTER 327macro inserts the new element 328.Fa elm 329after the element 330.Fa listelm . 331.Pp 332The 333.Fn TAILQ_INSERT_BEFORE 334macro inserts the new element 335.Fa elm 336before the element 337.Fa listelm . 338.Pp 339The 340.Fn TAILQ_REMOVE 341macro removes the element 342.Fa elm 343from the tail queue. 344.Sh TAIL QUEUE EXAMPLE 345.Bd -literal 346TAILQ_HEAD(tailhead, entry) head; 347struct tailhead *headp; /* Tail queue head. */ 348struct entry { 349 ... 350 TAILQ_ENTRY(entry) entries; /* Tail queue. */ 351 ... 352} *n1, *n2, *np; 353 354TAILQ_INIT(&head); /* Initialize the queue. */ 355 356n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 357TAILQ_INSERT_HEAD(&head, n1, entries); 358 359n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 360TAILQ_INSERT_TAIL(&head, n1, entries); 361 362n2 = malloc(sizeof(struct entry)); /* Insert after. */ 363TAILQ_INSERT_AFTER(&head, n1, n2, entries); 364 365n2 = malloc(sizeof(struct entry)); /* Insert before. */ 366TAILQ_INSERT_BEFORE(n1, n2, entries); 367 /* Forward traversal. */ 368for (np = head.tqh_first; np != NULL; np = np->entries.tqe_next) 369 np-> ... 370 /* Delete. */ 371while (head.tqh_first != NULL) 372 TAILQ_REMOVE(&head, head.tqh_first, entries); 373.Ed 374.Sh CIRCULAR QUEUES 375A circular queue is headed by a structure defined by the 376.Fn CIRCLEQ_HEAD 377macro. 378This structure contains a pair of pointers, 379one to the first element in the circular queue and the other to the 380last element in the circular queue. 381The elements are doubly linked so that an arbitrary element can be 382removed without traversing the queue. 383New elements can be added to the queue after an existing element, 384before an existing element, at the head of the queue, or at the end 385of the queue. 386A 387.Fa CIRCLEQ_HEAD 388structure is declared as follows: 389.Bd -literal -offset indent 390CIRCLEQ_HEAD(HEADNAME, TYPE) head; 391.Ed 392.sp 393where 394.Fa HEADNAME 395is the name of the structure to be defined, and 396.Fa TYPE 397is the type of the elements to be linked into the circular queue. 398A pointer to the head of the circular queue can later be declared as: 399.Bd -literal -offset indent 400struct HEADNAME *headp; 401.Ed 402.sp 403(The names 404.Li head 405and 406.Li headp 407are user selectable.) 408.Pp 409The 410.Fn CIRCLEQ_ENTRY 411macro declares a structure that connects the elements in 412the circular queue. 413.Pp 414The 415.Fn CIRCLEQ_INIT 416macro initializes the circular queue referenced by 417.Fa head . 418.Pp 419The 420.Fn CIRCLEQ_INSERT_HEAD 421macro inserts the new element 422.Fa elm 423at the head of the circular queue. 424.Pp 425The 426.Fn CIRCLEQ_INSERT_TAIL 427macro inserts the new element 428.Fa elm 429at the end of the circular queue. 430.Pp 431The 432.Fn CIRCLEQ_INSERT_AFTER 433macro inserts the new element 434.Fa elm 435after the element 436.Fa listelm . 437.Pp 438The 439.Fn CIRCLEQ_INSERT_BEFORE 440macro inserts the new element 441.Fa elm 442before the element 443.Fa listelm . 444.Pp 445The 446.Fn CIRCLEQ_REMOVE 447macro removes the element 448.Fa elm 449from the circular queue. 450.Sh CIRCULAR QUEUE EXAMPLE 451.Bd -literal 452CIRCLEQ_HEAD(circleq, entry) head; 453struct circleq *headp; /* Circular queue head. */ 454struct entry { 455 ... 456 CIRCLEQ_ENTRY entries; /* Circular queue. */ 457 ... 458} *n1, *n2, *np; 459 460CIRCLEQ_INIT(&head); /* Initialize the circular queue. */ 461 462n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 463CIRCLEQ_INSERT_HEAD(&head, n1, entries); 464 465n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 466CIRCLEQ_INSERT_TAIL(&head, n1, entries); 467 468n2 = malloc(sizeof(struct entry)); /* Insert after. */ 469CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries); 470 471n2 = malloc(sizeof(struct entry)); /* Insert before. */ 472CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries); 473 /* Forward traversal. */ 474for (np = head.cqh_first; np != (void *)&head; np = np->entries.cqe_next) 475 np-> ... 476 /* Reverse traversal. */ 477for (np = head.cqh_last; np != (void *)&head; np = np->entries.cqe_prev) 478 np-> ... 479 /* Delete. */ 480while (head.cqh_first != (void *)&head) 481 CIRCLEQ_REMOVE(&head, head.cqh_first, entries); 482.Ed 483.Sh HISTORY 484The 485.Nm queue 486functions first appeared in 487.Bx 4.4 . 488