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