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