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