share/man/man3/queue.3

   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 .\" $FreeBSD: src/share/man/man3/queue.3,v 1.15.2.7 2001/12/18 10:09:02 ru Exp $
  34 .\"
  35 .Dd January 24, 1994
  36 .Dt QUEUE 3
  37 .Os
  38 .Sh NAME
  39 .Nm SLIST_EMPTY ,
  40 .Nm SLIST_ENTRY ,
  41 .Nm SLIST_FIRST ,
  42 .Nm SLIST_FOREACH ,
  43 .Nm SLIST_HEAD ,
  44 .Nm SLIST_HEAD_INITIALIZER ,
  45 .Nm SLIST_INIT ,
  46 .Nm SLIST_INSERT_AFTER ,
  47 .Nm SLIST_INSERT_HEAD ,
  48 .Nm SLIST_NEXT ,
  49 .Nm SLIST_REMOVE_HEAD ,
  50 .Nm SLIST_REMOVE ,
  51 .Nm STAILQ_EMPTY ,
  52 .Nm STAILQ_ENTRY ,
  53 .Nm STAILQ_FIRST ,
  54 .Nm STAILQ_FOREACH ,
  55 .Nm STAILQ_HEAD ,
  56 .Nm STAILQ_HEAD_INITIALIZER ,
  57 .Nm STAILQ_INIT ,
  58 .Nm STAILQ_INSERT_AFTER ,
  59 .Nm STAILQ_INSERT_HEAD ,
  60 .Nm STAILQ_INSERT_TAIL ,
  61 .Nm STAILQ_LAST ,
  62 .Nm STAILQ_NEXT ,
  63 .Nm STAILQ_REMOVE_HEAD ,
  64 .Nm STAILQ_REMOVE ,
  65 .Nm LIST_EMPTY ,
  66 .Nm LIST_ENTRY ,
  67 .Nm LIST_FIRST ,
  68 .Nm LIST_FOREACH ,
  69 .Nm LIST_HEAD ,
  70 .Nm LIST_HEAD_INITIALIZER ,
  71 .Nm LIST_INIT ,
  72 .Nm LIST_INSERT_AFTER ,
  73 .Nm LIST_INSERT_BEFORE ,
  74 .Nm LIST_INSERT_HEAD ,
  75 .Nm LIST_NEXT ,
  76 .Nm LIST_REMOVE ,
  77 .Nm TAILQ_EMPTY ,
  78 .Nm TAILQ_ENTRY ,
  79 .Nm TAILQ_FIRST ,
  80 .Nm TAILQ_FOREACH ,
  81 .Nm TAILQ_FOREACH_REVERSE ,
  82 .Nm TAILQ_HEAD ,
  83 .Nm TAILQ_HEAD_INITIALIZER ,
  84 .Nm TAILQ_INIT ,
  85 .Nm TAILQ_INSERT_AFTER ,
  86 .Nm TAILQ_INSERT_BEFORE ,
  87 .Nm TAILQ_INSERT_HEAD ,
  88 .Nm TAILQ_INSERT_TAIL ,
  89 .Nm TAILQ_LAST ,
  90 .Nm TAILQ_NEXT ,
  91 .Nm TAILQ_PREV ,
  92 .Nm TAILQ_REMOVE ,
  93 .Nm CIRCLEQ_EMPTY ,
  94 .Nm CIRCLEQ_ENTRY ,
  95 .Nm CIRCLEQ_FIRST ,
  96 .Nm CIRCLEQ_FOREACH ,
  97 .Nm CIRCLEQ_FOREACH_REVERSE ,
  98 .Nm CIRCLEQ_HEAD ,
  99 .Nm CIRCLEQ_HEAD_INITIALIZER ,
 100 .Nm CIRCLEQ_INIT ,
 101 .Nm CIRCLEQ_INSERT_AFTER ,
 102 .Nm CIRCLEQ_INSERT_BEFORE ,
 103 .Nm CIRCLEQ_INSERT_HEAD ,
 104 .Nm CIRCLEQ_INSERT_TAIL ,
 105 .Nm CIRCLE_LAST ,
 106 .Nm CIRCLE_NEXT ,
 107 .Nm CIRCLE_PREV ,
 108 .Nm CIRCLEQ_REMOVE
 109 .Nd implementations of singly-linked lists, singly-linked tail queues,
 110 lists, tail queues, and circular queues
 111 .Sh SYNOPSIS
 112 .In sys/queue.h
 113 .\"
 114 .Fn SLIST_EMPTY "SLIST_HEAD *head"
 115 .Fn SLIST_ENTRY "TYPE"
 116 .Fn SLIST_FIRST "SLIST_HEAD *head"
 117 .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
 118 .Fn SLIST_HEAD "HEADNAME" "TYPE"
 119 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
 120 .Fn SLIST_INIT "SLIST_HEAD *head"
 121 .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
 122 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
 123 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
 124 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
 125 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
 126 .\"
 127 .Fn STAILQ_EMPTY "STAILQ_HEAD *head"
 128 .Fn STAILQ_ENTRY "TYPE"
 129 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
 130 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
 131 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
 132 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
 133 .Fn STAILQ_INIT "STAILQ_HEAD *head"
 134 .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
 135 .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
 136 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
 137 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
 138 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
 139 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
 140 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
 141 .\"
 142 .Fn LIST_EMPTY "LIST_HEAD *head"
 143 .Fn LIST_ENTRY "TYPE"
 144 .Fn LIST_FIRST "LIST_HEAD *head"
 145 .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
 146 .Fn LIST_HEAD "HEADNAME" "TYPE"
 147 .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
 148 .Fn LIST_INIT "LIST_HEAD *head"
 149 .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
 150 .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
 151 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
 152 .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
 153 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
 154 .\"
 155 .Fn TAILQ_EMPTY "TAILQ_HEAD *head"
 156 .Fn TAILQ_ENTRY "TYPE"
 157 .Fn TAILQ_FIRST "TAILQ_HEAD *head"
 158 .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
 159 .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
 160 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
 161 .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
 162 .Fn TAILQ_INIT "TAILQ_HEAD *head"
 163 .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
 164 .Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
 165 .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
 166 .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
 167 .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
 168 .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
 169 .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
 170 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
 171 .\"
 172 .Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head"
 173 .Fn CIRCLEQ_ENTRY "TYPE"
 174 .Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head"
 175 .Fn CIRCLEQ_FOREACH "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
 176 .Fn CIRCLEQ_FOREACH_REVERSE "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
 177 .Fn CIRCLEQ_HEAD "HEADNAME" "TYPE"
 178 .Fn CIRCLEQ_HEAD_INITIALIZER "CIRCLEQ_HEAD head"
 179 .Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head"
 180 .Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
 181 .Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
 182 .Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
 183 .Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
 184 .Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head"
 185 .Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME"
 186 .Fn CIRCLE_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME"
 187 .Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
 188 .Sh DESCRIPTION
 189 These macros define and operate on five types of data structures:
 190 singly-linked lists, singly-linked tail queues, lists, tail queues,
 191 and circular queues.
 192 All five structures support the following functionality:
 193 .Bl -enum -compact -offset indent
 194 .It
 195 Insertion of a new entry at the head of the list.
 196 .It
 197 Insertion of a new entry after any element in the list.
 198 .It
 199 O(1) removal of an entry from the head of the list.
 200 .It
 201 O(n) removal of any entry in the list.
 202 .It
 203 Forward traversal through the list.
 204 .El
 205 .Pp
 206 Singly-linked lists are the simplest of the five data structures
 207 and support only the above functionality.
 208 Singly-linked lists are ideal for applications with large datasets
 209 and few or no removals,
 210 or for implementing a LIFO queue.
 211 .Pp
 212 Singly-linked tail queues add the following functionality:
 213 .Bl -enum -compact -offset indent
 214 .It
 215 Entries can be added at the end of a list.
 216 .El
 217 However:
 218 .Bl -enum -compact -offset indent
 219 .It
 220 All list insertions must specify the head of the list.
 221 .It
 222 Each head entry requires two pointers rather than one.
 223 .It
 224 Code size is about 15% greater and operations run about 20% slower
 225 than singly-linked lists.
 226 .El
 227 .Pp
 228 Singly-linked tailqs are ideal for applications with large datasets and
 229 few or no removals,
 230 or for implementing a FIFO queue.
 231 .Pp
 232 All doubly linked types of data structures (lists, tail queues, and circle
 233 queues) additionally allow:
 234 .Bl -enum -compact -offset indent
 235 .It
 236 Insertion of a new entry before any element in the list.
 237 .It
 238 O(1) removal of any entry in the list.
 239 .El
 240 However:
 241 .Bl -enum -compact -offset indent
 242 .It
 243 Each elements requires two pointers rather than one.
 244 .It
 245 Code size and execution time of operations (except for removal) is about
 246 twice that of the singly-linked data-structures.
 247 .El
 248 .Pp
 249 Linked lists are the simplest of the doubly linked data structures and support
 250 only the above functionality over singly-linked lists.
 251 .Pp
 252 Tail queues add the following functionality:
 253 .Bl -enum -compact -offset indent
 254 .It
 255 Entries can be added at the end of a list.
 256 .It
 257 They may be traversed backwards, from tail to head.
 258 .El
 259 However:
 260 .Bl -enum -compact -offset indent
 261 .It
 262 All list insertions and removals must specify the head of the list.
 263 .It
 264 Each head entry requires two pointers rather than one.
 265 .It
 266 Code size is about 15% greater and operations run about 20% slower
 267 than singly-linked lists.
 268 .El
 269 .Pp
 270 Circular queues add the following functionality:
 271 .Bl -enum -compact -offset indent
 272 .It
 273 Entries can be added at the end of a list.
 274 .It
 275 They may be traversed backwards, from tail to head.
 276 .El
 277 However:
 278 .Bl -enum -compact -offset indent
 279 .It
 280 All list insertions and removals must specify the head of the list.
 281 .It
 282 Each head entry requires two pointers rather than one.
 283 .It
 284 The termination condition for traversal is more complex.
 285 .It
 286 Code size is about 40% greater and operations run about 45% slower
 287 than lists.
 288 .El
 289 .Pp
 290 In the macro definitions,
 291 .Fa TYPE
 292 is the name of a user defined structure,
 293 that must contain a field of type
 294 .Li SLIST_ENTRY ,
 295 .Li STAILQ_ENTRY ,
 296 .Li LIST_ENTRY ,
 297 .Li TAILQ_ENTRY ,
 298 or
 299 .Li CIRCLEQ_ENTRY ,
 300 named
 301 .Fa NAME .
 302 The argument
 303 .Fa HEADNAME
 304 is the name of a user defined structure that must be declared
 305 using the macros
 306 .Li SLIST_HEAD ,
 307 .Li STAILQ_HEAD ,
 308 .Li LIST_HEAD ,
 309 .Li TAILQ_HEAD ,
 310 or
 311 .Li CIRCLEQ_HEAD .
 312 See the examples below for further explanation of how these
 313 macros are used.
 314 .Sh SINGLY-LINKED LISTS
 315 A singly-linked list is headed by a structure defined by the
 316 .Nm SLIST_HEAD
 317 macro.
 318 This structure contains a single pointer to the first element
 319 on the list.
 320 The elements are singly linked for minimum space and pointer manipulation
 321 overhead at the expense of O(n) removal for arbitrary elements.
 322 New elements can be added to the list after an existing element or
 323 at the head of the list.
 324 An
 325 .Fa SLIST_HEAD
 326 structure is declared as follows:
 327 .Bd -literal -offset indent
 328 SLIST_HEAD(HEADNAME, TYPE) head;
 329 .Ed
 330 .Pp
 331 where
 332 .Fa HEADNAME
 333 is the name of the structure to be defined, and
 334 .Fa TYPE
 335 is the type of the elements to be linked into the list.
 336 A pointer to the head of the list can later be declared as:
 337 .Bd -literal -offset indent
 338 struct HEADNAME *headp;
 339 .Ed
 340 .Pp
 341 (The names
 342 .Li head
 343 and
 344 .Li headp
 345 are user selectable.)
 346 .Pp
 347 The macro
 348 .Nm SLIST_HEAD_INITIALIZER
 349 evaluates to an initializer for the list
 350 .Fa head .
 351 .Pp
 352 The macro
 353 .Nm SLIST_EMPTY
 354 evaluates to true if there are no elements in the list.
 355 .Pp
 356 The macro
 357 .Nm SLIST_ENTRY
 358 declares a structure that connects the elements in
 359 the list.
 360 .Pp
 361 The macro
 362 .Nm SLIST_FIRST
 363 returns the first element in the list or NULL if the list is empty.
 364 .Pp
 365 The macro
 366 .Nm SLIST_FOREACH
 367 traverses the list referenced by
 368 .Fa head
 369 in the forward direction, assigning each element in
 370 turn to
 371 .Fa var .
 372 .Pp
 373 The macro
 374 .Nm SLIST_INIT
 375 initializes the list referenced by
 376 .Fa head .
 377 .Pp
 378 The macro
 379 .Nm SLIST_INSERT_HEAD
 380 inserts the new element
 381 .Fa elm
 382 at the head of the list.
 383 .Pp
 384 The macro
 385 .Nm SLIST_INSERT_AFTER
 386 inserts the new element
 387 .Fa elm
 388 after the element
 389 .Fa listelm .
 390 .Pp
 391 The macro
 392 .Nm SLIST_NEXT
 393 returns the next element in the list.
 394 .Pp
 395 The macro
 396 .Nm SLIST_REMOVE_HEAD
 397 removes the element
 398 .Fa elm
 399 from the head of the list.
 400 For optimum efficiency,
 401 elements being removed from the head of the list should explicitly use
 402 this macro instead of the generic
 403 .Fa SLIST_REMOVE
 404 macro.
 405 .Pp
 406 The macro
 407 .Nm SLIST_REMOVE
 408 removes the element
 409 .Fa elm
 410 from the list.
 411 .Sh SINGLY-LINKED LIST EXAMPLE
 412 .Bd -literal
 413 SLIST_HEAD(slisthead, entry) head =
 414     SLIST_HEAD_INITIALIZER(head);
 415 struct slisthead *headp;                /* Singly-linked List head. */
 416 struct entry {
 417         ...
 418         SLIST_ENTRY(entry) entries;     /* Singly-linked List. */
 419         ...
 420 } *n1, *n2, *n3, *np;
 421
 422 SLIST_INIT(&head);                      /* Initialize the list. */
 423
 424 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 425 SLIST_INSERT_HEAD(&head, n1, entries);
 426
 427 n2 = malloc(sizeof(struct entry));      /* Insert after. */
 428 SLIST_INSERT_AFTER(n1, n2, entries);
 429
 430 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
 431 free(n2);
 432
 433 n3 = SLIST_FIRST(&head);
 434 SLIST_REMOVE_HEAD(&head, entries);      /* Deletion from the head. */
 435 free(n3);
 436                                         /* Forward traversal. */
 437 SLIST_FOREACH(np, &head, entries)
 438         np-> ...
 439
 440 while (!SLIST_EMPTY(&head)) {           /* List Deletion. */
 441         n1 = SLIST_FIRST(&head);
 442         SLIST_REMOVE_HEAD(&head, entries);
 443         free(n1);
 444 }
 445 .Ed
 446 .Sh SINGLY-LINKED TAIL QUEUES
 447 A singly-linked tail queue is headed by a structure defined by the
 448 .Nm STAILQ_HEAD
 449 macro.
 450 This structure contains a pair of pointers,
 451 one to the first element in the tail queue and the other to
 452 the last element in the tail queue.
 453 The elements are singly linked for minimum space and pointer
 454 manipulation overhead at the expense of O(n) removal for arbitrary
 455 elements.
 456 New elements can be added to the tail queue after an existing element,
 457 at the head of the tail queue, or at the end of the tail queue.
 458 A
 459 .Fa STAILQ_HEAD
 460 structure is declared as follows:
 461 .Bd -literal -offset indent
 462 STAILQ_HEAD(HEADNAME, TYPE) head;
 463 .Ed
 464 .Pp
 465 where
 466 .Li HEADNAME
 467 is the name of the structure to be defined, and
 468 .Li TYPE
 469 is the type of the elements to be linked into the tail queue.
 470 A pointer to the head of the tail queue can later be declared as:
 471 .Bd -literal -offset indent
 472 struct HEADNAME *headp;
 473 .Ed
 474 .Pp
 475 (The names
 476 .Li head
 477 and
 478 .Li headp
 479 are user selectable.)
 480 .Pp
 481 The macro
 482 .Nm STAILQ_HEAD_INITIALIZER
 483 evaluates to an initializer for the tail queue
 484 .Fa head .
 485 .Pp
 486 The macro
 487 .Nm STAILQ_EMPTY
 488 evaluates to true if there are no items on the tail queue.
 489 .Pp
 490 The macro
 491 .Nm STAILQ_ENTRY
 492 declares a structure that connects the elements in
 493 the tail queue.
 494 .Pp
 495 The macro
 496 .Nm STAILQ_FIRST
 497 returns the first item on the tail queue or NULL if the tail queue
 498 is empty.
 499 .Pp
 500 The macro
 501 .Nm STAILQ_FOREACH
 502 traverses the tail queue referenced by
 503 .Fa head
 504 in the forward direction, assigning each element
 505 in turn to
 506 .Fa var .
 507 .Pp
 508 The macro
 509 .Nm STAILQ_INIT
 510 initializes the tail queue referenced by
 511 .Fa head .
 512 .Pp
 513 The macro
 514 .Nm STAILQ_INSERT_HEAD
 515 inserts the new element
 516 .Fa elm
 517 at the head of the tail queue.
 518 .Pp
 519 The macro
 520 .Nm STAILQ_INSERT_TAIL
 521 inserts the new element
 522 .Fa elm
 523 at the end of the tail queue.
 524 .Pp
 525 The macro
 526 .Nm STAILQ_INSERT_AFTER
 527 inserts the new element
 528 .Fa elm
 529 after the element
 530 .Fa listelm .
 531 .Pp
 532 The macro
 533 .Nm STAILQ_LAST
 534 returns the last item on the tail queue.
 535 If the tail queue is empty the return value is undefined.
 536 .Pp
 537 The macro
 538 .Nm STAILQ_NEXT
 539 returns the next item on the tail queue, or NULL this item is the last.
 540 .Pp
 541 The macro
 542 .Nm STAILQ_REMOVE_HEAD
 543 removes the element at the head of the tail queue.
 544 For optimum efficiency,
 545 elements being removed from the head of the tail queue should
 546 use this macro explicitly rather than the generic
 547 .Fa STAILQ_REMOVE
 548 macro.
 549 .Pp
 550 The macro
 551 .Nm STAILQ_REMOVE
 552 removes the element
 553 .Fa elm
 554 from the tail queue.
 555 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
 556 .Bd -literal
 557 STAILQ_HEAD(stailhead, entry) head =
 558     STAILQ_HEAD_INITIALIZER(head);
 559 struct stailhead *headp;                /* Singly-linked tail queue head. */
 560 struct entry {
 561         ...
 562         STAILQ_ENTRY(entry) entries;    /* Tail queue. */
 563         ...
 564 } *n1, *n2, *n3, *np;
 565
 566 STAILQ_INIT(&head);                     /* Initialize the queue. */
 567
 568 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 569 STAILQ_INSERT_HEAD(&head, n1, entries);
 570
 571 n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
 572 STAILQ_INSERT_TAIL(&head, n1, entries);
 573
 574 n2 = malloc(sizeof(struct entry));      /* Insert after. */
 575 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
 576                                         /* Deletion. */
 577 STAILQ_REMOVE(&head, n2, entry, entries);
 578 free(n2);
 579                                         /* Deletion from the head. */
 580 n3 = STAILQ_FIRST(&head);
 581 STAILQ_REMOVE_HEAD(&head, entries);
 582 free(n3);
 583                                         /* Forward traversal. */
 584 STAILQ_FOREACH(np, &head, entries)
 585         np-> ...
 586                                         /* TailQ Deletion. */
 587 while (!STAILQ_EMPTY(&head)) {
 588         n1 = STAILQ_FIRST(&head);
 589         STAILQ_REMOVE_HEAD(&head, entries);
 590         free(n1);
 591 }
 592                                         /* Faster TailQ Deletion. */
 593 n1 = STAILQ_FIRST(&head);
 594 while (n1 != NULL) {
 595         n2 = STAILQ_NEXT(n1, entries);
 596         free(n1);
 597         n1 = n2;
 598 }
 599 STAILQ_INIT(&head);
 600 .Ed
 601 .Sh LISTS
 602 A list is headed by a structure defined by the
 603 .Nm LIST_HEAD
 604 macro.
 605 This structure contains a single pointer to the first element
 606 on the list.
 607 The elements are doubly linked so that an arbitrary element can be
 608 removed without traversing the list.
 609 New elements can be added to the list after an existing element,
 610 before an existing element, or at the head of the list.
 611 A
 612 .Fa LIST_HEAD
 613 structure is declared as follows:
 614 .Bd -literal -offset indent
 615 LIST_HEAD(HEADNAME, TYPE) head;
 616 .Ed
 617 .Pp
 618 where
 619 .Fa HEADNAME
 620 is the name of the structure to be defined, and
 621 .Fa TYPE
 622 is the type of the elements to be linked into the list.
 623 A pointer to the head of the list can later be declared as:
 624 .Bd -literal -offset indent
 625 struct HEADNAME *headp;
 626 .Ed
 627 .Pp
 628 (The names
 629 .Li head
 630 and
 631 .Li headp
 632 are user selectable.)
 633 .Pp
 634 The macro
 635 .Nm LIST_HEAD_INITIALIZER
 636 evaluates to an initializer for the list
 637 .Fa head .
 638 .Pp
 639 The macro
 640 .Nm LIST_EMPTY
 641 evaluates to true if their are no elements in the list.
 642 .Pp
 643 The macro
 644 .Nm LIST_ENTRY
 645 declares a structure that connects the elements in
 646 the list.
 647 .Pp
 648 The macro
 649 .Nm LIST_FIRST
 650 returns the first element in the list or NULL if the list
 651 is empty.
 652 .Pp
 653 The macro
 654 .Nm LIST_FOREACH
 655 traverses the list referenced by
 656 .Fa head
 657 in the forward direction, assigning each element in turn to
 658 .Fa var .
 659 .Pp
 660 The macro
 661 .Nm LIST_INIT
 662 initializes the list referenced by
 663 .Fa head .
 664 .Pp
 665 The macro
 666 .Nm LIST_INSERT_HEAD
 667 inserts the new element
 668 .Fa elm
 669 at the head of the list.
 670 .Pp
 671 The macro
 672 .Nm LIST_INSERT_AFTER
 673 inserts the new element
 674 .Fa elm
 675 after the element
 676 .Fa listelm .
 677 .Pp
 678 The macro
 679 .Nm LIST_INSERT_BEFORE
 680 inserts the new element
 681 .Fa elm
 682 before the element
 683 .Fa listelm .
 684 .Pp
 685 The macro
 686 .Nm LIST_NEXT
 687 returns the next element in the list, or NULL if this is the last.
 688 .Pp
 689 The macro
 690 .Nm LIST_REMOVE
 691 removes the element
 692 .Fa elm
 693 from the list.
 694 .Sh LIST EXAMPLE
 695 .Bd -literal
 696 LIST_HEAD(listhead, entry) head =
 697     LIST_HEAD_INITIALIZER(head);
 698 struct listhead *headp;                 /* List head. */
 699 struct entry {
 700         ...
 701         LIST_ENTRY(entry) entries;      /* List. */
 702         ...
 703 } *n1, *n2, *n3, *np;
 704
 705 LIST_INIT(&head);                       /* Initialize the list. */
 706
 707 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 708 LIST_INSERT_HEAD(&head, n1, entries);
 709
 710 n2 = malloc(sizeof(struct entry));      /* Insert after. */
 711 LIST_INSERT_AFTER(n1, n2, entries);
 712
 713 n3 = malloc(sizeof(struct entry));      /* Insert before. */
 714 LIST_INSERT_BEFORE(n2, n3, entries);
 715
 716 LIST_REMOVE(n2, entries);               /* Deletion. */
 717 free(n2);
 718                                         /* Forward traversal. */
 719 LIST_FOREACH(np, &head, entries)
 720         np-> ...
 721
 722 while (!LIST_EMPTY(&head)) {            /* List Deletion. */
 723         n1 = LIST_FIRST(&head);
 724         LIST_REMOVE(n1, entries);
 725         free(n1);
 726 }
 727
 728 n1 = LIST_FIRST(&head);                 /* Faster List Deletion. */
 729 while (n1 != NULL) {
 730         n2 = LIST_NEXT(n1, entries);
 731         free(n1);
 732         n1 = n2;
 733 }
 734 LIST_INIT(&head);
 735 .Ed
 736 .Sh TAIL QUEUES
 737 A tail queue is headed by a structure defined by the
 738 .Nm TAILQ_HEAD
 739 macro.
 740 This structure contains a pair of pointers,
 741 one to the first element in the tail queue and the other to
 742 the last element in the tail queue.
 743 The elements are doubly linked so that an arbitrary element can be
 744 removed without traversing the tail queue.
 745 New elements can be added to the tail queue after an existing element,
 746 before an existing element, at the head of the tail queue,
 747 or at the end of the tail queue.
 748 A
 749 .Fa TAILQ_HEAD
 750 structure is declared as follows:
 751 .Bd -literal -offset indent
 752 TAILQ_HEAD(HEADNAME, TYPE) head;
 753 .Ed
 754 .Pp
 755 where
 756 .Li HEADNAME
 757 is the name of the structure to be defined, and
 758 .Li TYPE
 759 is the type of the elements to be linked into the tail queue.
 760 A pointer to the head of the tail queue can later be declared as:
 761 .Bd -literal -offset indent
 762 struct HEADNAME *headp;
 763 .Ed
 764 .Pp
 765 (The names
 766 .Li head
 767 and
 768 .Li headp
 769 are user selectable.)
 770 .Pp
 771 The macro
 772 .Nm TAILQ_HEAD_INITIALIZER
 773 evaluates to an initializer for the tail queue
 774 .Fa head .
 775 .Pp
 776 The macro
 777 .Nm TAILQ_EMPTY
 778 evaluates to true if there are no items on the tail queue.
 779 .Pp
 780 The macro
 781 .Nm TAILQ_ENTRY
 782 declares a structure that connects the elements in
 783 the tail queue.
 784 .Pp
 785 The macro
 786 .Nm TAILQ_FIRST
 787 returns the first item on the tail queue or NULL if the tail queue
 788 is empty.
 789 .Pp
 790 The macro
 791 .Nm TAILQ_FOREACH
 792 traverses the tail queue referenced by
 793 .Fa head
 794 in the forward direction, assigning each element in turn to
 795 .Fa var .
 796 .Pp
 797 The macro
 798 .Nm TAILQ_FOREACH_REVERSE
 799 traverses the tail queue referenced by
 800 .Fa head
 801 in the reverse direction, assigning each element in turn to
 802 .Fa var .
 803 .Pp
 804 The macro
 805 .Nm TAILQ_INIT
 806 initializes the tail queue referenced by
 807 .Fa head .
 808 .Pp
 809 The macro
 810 .Nm TAILQ_INSERT_HEAD
 811 inserts the new element
 812 .Fa elm
 813 at the head of the tail queue.
 814 .Pp
 815 The macro
 816 .Nm TAILQ_INSERT_TAIL
 817 inserts the new element
 818 .Fa elm
 819 at the end of the tail queue.
 820 .Pp
 821 The macro
 822 .Nm TAILQ_INSERT_AFTER
 823 inserts the new element
 824 .Fa elm
 825 after the element
 826 .Fa listelm .
 827 .Pp
 828 The macro
 829 .Nm TAILQ_INSERT_BEFORE
 830 inserts the new element
 831 .Fa elm
 832 before the element
 833 .Fa listelm .
 834 .Pp
 835 The macro
 836 .Nm TAILQ_LAST
 837 returns the last item on the tail queue.
 838 If the tail queue is empty the return value is undefined.
 839 .Pp
 840 The macro
 841 .Nm TAILQ_NEXT
 842 returns the next item on the tail queue, or NULL if this item is the last.
 843 .Pp
 844 The macro
 845 .Nm TAILQ_PREV
 846 returns the previous item on the tail queue, or NULL if this item
 847 is the first.
 848 .Pp
 849 The macro
 850 .Nm TAILQ_REMOVE
 851 removes the element
 852 .Fa elm
 853 from the tail queue.
 854 .Sh TAIL QUEUE EXAMPLE
 855 .Bd -literal
 856 TAILQ_HEAD(tailhead, entry) head =
 857     TAILQ_HEAD_INITIALIZER(head);
 858 struct tailhead *headp;                 /* Tail queue head. */
 859 struct entry {
 860         ...
 861         TAILQ_ENTRY(entry) entries;     /* Tail queue. */
 862         ...
 863 } *n1, *n2, *n3, *np;
 864
 865 TAILQ_INIT(&head);                      /* Initialize the queue. */
 866
 867 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 868 TAILQ_INSERT_HEAD(&head, n1, entries);
 869
 870 n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
 871 TAILQ_INSERT_TAIL(&head, n1, entries);
 872
 873 n2 = malloc(sizeof(struct entry));      /* Insert after. */
 874 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
 875
 876 n3 = malloc(sizeof(struct entry));      /* Insert before. */
 877 TAILQ_INSERT_BEFORE(n2, n3, entries);
 878
 879 TAILQ_REMOVE(&head, n2, entries);       /* Deletion. */
 880 free(n2);
 881                                         /* Forward traversal. */
 882 TAILQ_FOREACH(np, &head, entries)
 883         np-> ...
 884                                         /* Reverse traversal. */
 885 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
 886         np-> ...
 887                                         /* TailQ Deletion. */
 888 while (!TAILQ_EMPTY(&head)) {
 889         n1 = TAILQ_FIRST(&head);
 890         TAILQ_REMOVE(&head, n1, entries);
 891         free(n1);
 892 }
 893                                         /* Faster TailQ Deletion. */
 894 n1 = TAILQ_FIRST(&head);
 895 while (n1 != NULL) {
 896         n2 = TAILQ_NEXT(n1, entries);
 897         free(n1);
 898         n1 = n2;
 899 }
 900 TAILQ_INIT(&head);
 901 .Ed
 902 .Sh CIRCULAR QUEUES
 903 A circular queue is headed by a structure defined by the
 904 .Nm CIRCLEQ_HEAD
 905 macro.
 906 This structure contains a pair of pointers,
 907 one to the first element in the circular queue and the other to the
 908 last element in the circular queue.
 909 The elements are doubly linked so that an arbitrary element can be
 910 removed without traversing the queue.
 911 New elements can be added to the queue after an existing element,
 912 before an existing element, at the head of the queue, or at the end
 913 of the queue.
 914 A
 915 .Fa CIRCLEQ_HEAD
 916 structure is declared as follows:
 917 .Bd -literal -offset indent
 918 CIRCLEQ_HEAD(HEADNAME, TYPE) head;
 919 .Ed
 920 .Pp
 921 where
 922 .Li HEADNAME
 923 is the name of the structure to be defined, and
 924 .Li TYPE
 925 is the type of the elements to be linked into the circular queue.
 926 A pointer to the head of the circular queue can later be declared as:
 927 .Bd -literal -offset indent
 928 struct HEADNAME *headp;
 929 .Ed
 930 .Pp
 931 (The names
 932 .Li head
 933 and
 934 .Li headp
 935 are user selectable.)
 936 .Pp
 937 The macro
 938 .Nm CIRCLEQ_HEAD_INITIALIZER
 939 evaluates to an initializer for the circle queue
 940 .Fa head .
 941 .Pp
 942 The macro
 943 .Nm CIRCLEQ_EMPTY
 944 evaluates to true if there are no items on the circle queue.
 945 .Pp
 946 The macro
 947 .Nm CIRCLEQ_ENTRY
 948 declares a structure that connects the elements in
 949 the circular queue.
 950 .Pp
 951 The macro
 952 .Nm CIRCLEQ_FIRST
 953 returns the first item on the circle queue.
 954 .Pp
 955 The macro
 956 .Nm CICRLEQ_FOREACH
 957 traverses the circle queue referenced by
 958 .Fa head
 959 in the forward direction, assigning each element in turn to
 960 .Fa var .
 961 .Pp
 962 The macro
 963 .Nm CICRLEQ_FOREACH_REVERSE
 964 traverses the circle queue referenced by
 965 .Fa head
 966 in the reverse direction, assigning each element in turn to
 967 .Fa var .
 968 .Pp
 969 The macro
 970 .Nm CIRCLEQ_INIT
 971 initializes the circular queue referenced by
 972 .Fa head .
 973 .Pp
 974 The macro
 975 .Nm CIRCLEQ_INSERT_HEAD
 976 inserts the new element
 977 .Fa elm
 978 at the head of the circular queue.
 979 .Pp
 980 The macro
 981 .Nm CIRCLEQ_INSERT_TAIL
 982 inserts the new element
 983 .Fa elm
 984 at the end of the circular queue.
 985 .Pp
 986 The macro
 987 .Nm CIRCLEQ_INSERT_AFTER
 988 inserts the new element
 989 .Fa elm
 990 after the element
 991 .Fa listelm .
 992 .Pp
 993 The macro
 994 .Nm CIRCLEQ_INSERT_BEFORE
 995 inserts the new element
 996 .Fa elm
 997 before the element
 998 .Fa listelm .
 999 .Pp
1000 The macro
1001 .Nm CIRCLEQ_LAST
1002 returns the last item on the circle queue.
1003 .Pp
1004 The macro
1005 .Nm CIRCLEQ_NEXT
1006 returns the next item on the circle queue.
1007 .Pp
1008 The macro
1009 .Nm CIRCLEQ_PREV
1010 returns the previous item on the circle queue.
1011 .Pp
1012 The macro
1013 .Nm CIRCLEQ_REMOVE
1014 removes the element
1015 .Fa elm
1016 from the circular queue.
1017 .Sh CIRCULAR QUEUE EXAMPLE
1018 .Bd -literal
1019 CIRCLEQ_HEAD(circlehead, entry) head =
1020     CIRCLEQ_HEAD_INITIALIZER(head);
1021 struct circlehead *headp;               /* Circular queue head. */
1022 struct entry {
1023         ...
1024         CIRCLEQ_ENTRY(entry) entries;   /* Circular queue. */
1025         ...
1026 } *n1, *n2, *np;
1027
1028 CIRCLEQ_INIT(&head);                    /* Initialize the circular queue. */
1029
1030 n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
1031 CIRCLEQ_INSERT_HEAD(&head, n1, entries);
1032
1033 n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
1034 CIRCLEQ_INSERT_TAIL(&head, n1, entries);
1035
1036 n2 = malloc(sizeof(struct entry));      /* Insert after. */
1037 CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
1038
1039 n2 = malloc(sizeof(struct entry));      /* Insert before. */
1040 CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
1041
1042 CIRCLEQ_REMOVE(&head, n1, entries);     /* Deletion. */
1043 free(n1);
1044                                         /* Forward traversal. */
1045 CIRCLEQ_FOREACH(np, &head, entries)
1046         np-> ...
1047                                         /* Reverse traversal. */
1048 CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
1049         np-> ...
1050                                         /* CircleQ Deletion. */
1051 while (CIRCLEQ_FIRST(&head) != (void *)&head) {
1052         n1 = CIRCLEQ_HEAD(&head);
1053         CIRCLEQ_REMOVE(&head, n1, entries);
1054         free(n1);
1055 }
1056                                         /* Faster CircleQ Deletion. */
1057 n1 = CIRCLEQ_FIRST(&head);
1058 while (n1 != (void *)&head) {
1059         n2 = CIRCLEQ_NEXT(n1, entries);
1060         free(n1);
1061         n1 = n2;
1062 }
1063 CIRCLEQ_INIT(&head);
1064 .Ed
1065 .Sh HISTORY
1066 The
1067 .Nm queue
1068 functions first appeared in
1069 .Bx 4.4 .