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