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