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