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