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