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