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