tor_queue.txt (31928B)
1 Below follows the manpage for tor_queue.h, as included with OpenBSD's 2 sys/queue.h. License follows at the end of the file. 3 4 ====================================================================== 5 QUEUE(3) OpenBSD Programmer's Manual QUEUE(3) 6 7 NAME 8 SLIST_ENTRY, SLIST_HEAD, SLIST_HEAD_INITIALIZER, SLIST_FIRST, SLIST_NEXT, 9 SLIST_END, SLIST_EMPTY, SLIST_FOREACH, SLIST_FOREACH_SAFE, SLIST_INIT, 10 SLIST_INSERT_AFTER, SLIST_INSERT_HEAD, SLIST_REMOVE_AFTER, 11 SLIST_REMOVE_HEAD, SLIST_REMOVE, LIST_ENTRY, LIST_HEAD, 12 LIST_HEAD_INITIALIZER, LIST_FIRST, LIST_NEXT, LIST_END, LIST_EMPTY, 13 LIST_FOREACH, LIST_FOREACH_SAFE, LIST_INIT, LIST_INSERT_AFTER, 14 LIST_INSERT_BEFORE, LIST_INSERT_HEAD, LIST_REMOVE, LIST_REPLACE, 15 SIMPLEQ_ENTRY, SIMPLEQ_HEAD, SIMPLEQ_HEAD_INITIALIZER, SIMPLEQ_FIRST, 16 SIMPLEQ_NEXT, SIMPLEQ_END, SIMPLEQ_EMPTY, SIMPLEQ_FOREACH, 17 SIMPLEQ_FOREACH_SAFE, SIMPLEQ_INIT, SIMPLEQ_INSERT_AFTER, 18 SIMPLEQ_INSERT_HEAD, SIMPLEQ_INSERT_TAIL, SIMPLEQ_REMOVE_AFTER, 19 SIMPLEQ_REMOVE_HEAD, TAILQ_ENTRY, TAILQ_HEAD, TAILQ_HEAD_INITIALIZER, 20 TAILQ_FIRST, TAILQ_NEXT, TAILQ_END, TAILQ_LAST, TAILQ_PREV, TAILQ_EMPTY, 21 TAILQ_FOREACH, TAILQ_FOREACH_SAFE, TAILQ_FOREACH_REVERSE, 22 TAILQ_FOREACH_REVERSE_SAFE, TAILQ_INIT, TAILQ_INSERT_AFTER, 23 TAILQ_INSERT_BEFORE, TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, TAILQ_REMOVE, 24 TAILQ_REPLACE, CIRCLEQ_ENTRY, CIRCLEQ_HEAD, CIRCLEQ_HEAD_INITIALIZER, 25 CIRCLEQ_FIRST, CIRCLEQ_LAST, CIRCLEQ_END, CIRCLEQ_NEXT, CIRCLEQ_PREV, 26 CIRCLEQ_EMPTY, CIRCLEQ_FOREACH, CIRCLEQ_FOREACH_SAFE, 27 CIRCLEQ_FOREACH_REVERSE_SAFE, CIRCLEQ_INIT, CIRCLEQ_INSERT_AFTER, 28 CIRCLEQ_INSERT_BEFORE, CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL, 29 CIRCLEQ_REMOVE, CIRCLEQ_REPLACE - implementations of singly-linked lists, 30 doubly-linked lists, simple queues, tail queues, and circular queues 31 32 SYNOPSIS 33 #include <sys/queue.h> 34 35 SLIST_ENTRY(TYPE); 36 37 SLIST_HEAD(HEADNAME, TYPE); 38 39 SLIST_HEAD_INITIALIZER(SLIST_HEAD head); 40 41 struct TYPE * 42 SLIST_FIRST(SLIST_HEAD *head); 43 44 struct TYPE * 45 SLIST_NEXT(struct TYPE *listelm, SLIST_ENTRY NAME); 46 47 struct TYPE * 48 SLIST_END(SLIST_HEAD *head); 49 50 int 51 SLIST_EMPTY(SLIST_HEAD *head); 52 53 SLIST_FOREACH(VARNAME, SLIST_HEAD *head, SLIST_ENTRY NAME); 54 55 SLIST_FOREACH_SAFE(VARNAME, SLIST_HEAD *head, SLIST_ENTRY 56 NAME, TEMP_VARNAME); 57 58 void 59 SLIST_INIT(SLIST_HEAD *head); 60 61 void 62 SLIST_INSERT_AFTER(struct TYPE *listelm, struct TYPE *elm, SLIST_ENTRY 63 NAME); 64 65 void 66 SLIST_INSERT_HEAD(SLIST_HEAD *head, struct TYPE *elm, SLIST_ENTRY NAME); 67 68 void 69 SLIST_REMOVE_AFTER(struct TYPE *elm, SLIST_ENTRY NAME); 70 71 void 72 SLIST_REMOVE_HEAD(SLIST_HEAD *head, SLIST_ENTRY NAME); 73 74 void 75 SLIST_REMOVE(SLIST_HEAD *head, struct TYPE *elm, TYPE, SLIST_ENTRY NAME); 76 77 LIST_ENTRY(TYPE); 78 79 LIST_HEAD(HEADNAME, TYPE); 80 81 LIST_HEAD_INITIALIZER(LIST_HEAD head); 82 83 struct TYPE * 84 LIST_FIRST(LIST_HEAD *head); 85 86 struct TYPE * 87 LIST_NEXT(struct TYPE *listelm, LIST_ENTRY NAME); 88 89 struct TYPE * 90 LIST_END(LIST_HEAD *head); 91 92 int 93 LIST_EMPTY(LIST_HEAD *head); 94 95 LIST_FOREACH(VARNAME, LIST_HEAD *head, LIST_ENTRY NAME); 96 97 LIST_FOREACH_SAFE(VARNAME, LIST_HEAD *head, LIST_ENTRY 98 NAME, TEMP_VARNAME); 99 100 void 101 LIST_INIT(LIST_HEAD *head); 102 103 void 104 LIST_INSERT_AFTER(struct TYPE *listelm, struct TYPE *elm, LIST_ENTRY 105 NAME); 106 107 void 108 LIST_INSERT_BEFORE(struct TYPE *listelm, struct TYPE *elm, LIST_ENTRY 109 NAME); 110 111 void 112 LIST_INSERT_HEAD(LIST_HEAD *head, struct TYPE *elm, LIST_ENTRY NAME); 113 114 void 115 LIST_REMOVE(struct TYPE *elm, LIST_ENTRY NAME); 116 117 void 118 LIST_REPLACE(struct TYPE *elm, struct TYPE *elm2, LIST_ENTRY NAME); 119 120 SIMPLEQ_ENTRY(TYPE); 121 122 SIMPLEQ_HEAD(HEADNAME, TYPE); 123 124 SIMPLEQ_HEAD_INITIALIZER(SIMPLEQ_HEAD head); 125 126 struct TYPE * 127 SIMPLEQ_FIRST(SIMPLEQ_HEAD *head); 128 129 struct TYPE * 130 SIMPLEQ_NEXT(struct TYPE *listelm, SIMPLEQ_ENTRY NAME); 131 132 struct TYPE * 133 SIMPLEQ_END(SIMPLEQ_HEAD *head); 134 135 int 136 SIMPLEQ_EMPTY(SIMPLEQ_HEAD *head); 137 138 SIMPLEQ_FOREACH(VARNAME, SIMPLEQ_HEAD *head, SIMPLEQ_ENTRY NAME); 139 140 SIMPLEQ_FOREACH_SAFE(VARNAME, SIMPLEQ_HEAD *head, SIMPLEQ_ENTRY 141 NAME, TEMP_VARNAME); 142 143 void 144 SIMPLEQ_INIT(SIMPLEQ_HEAD *head); 145 146 void 147 SIMPLEQ_INSERT_AFTER(SIMPLEQ_HEAD *head, struct TYPE *listelm, struct 148 TYPE *elm, SIMPLEQ_ENTRY NAME); 149 150 void 151 SIMPLEQ_INSERT_HEAD(SIMPLEQ_HEAD *head, struct TYPE *elm, SIMPLEQ_ENTRY 152 NAME); 153 154 void 155 SIMPLEQ_INSERT_TAIL(SIMPLEQ_HEAD *head, struct TYPE *elm, SIMPLEQ_ENTRY 156 NAME); 157 158 void 159 SIMPLEQ_REMOVE_AFTER(SIMPLEQ_HEAD *head, struct TYPE *elm, SIMPLEQ_ENTRY 160 NAME); 161 162 void 163 SIMPLEQ_REMOVE_HEAD(SIMPLEQ_HEAD *head, SIMPLEQ_ENTRY NAME); 164 165 TAILQ_ENTRY(TYPE); 166 167 TAILQ_HEAD(HEADNAME, TYPE); 168 169 TAILQ_HEAD_INITIALIZER(TAILQ_HEAD head); 170 171 struct TYPE * 172 TAILQ_FIRST(TAILQ_HEAD *head); 173 174 struct TYPE * 175 TAILQ_NEXT(struct TYPE *listelm, TAILQ_ENTRY NAME); 176 177 struct TYPE * 178 TAILQ_END(TAILQ_HEAD *head); 179 180 struct TYPE * 181 TAILQ_LAST(TAILQ_HEAD *head, HEADNAME NAME); 182 183 struct TYPE * 184 TAILQ_PREV(struct TYPE *listelm, HEADNAME NAME, TAILQ_ENTRY NAME); 185 186 int 187 TAILQ_EMPTY(TAILQ_HEAD *head); 188 189 TAILQ_FOREACH(VARNAME, TAILQ_HEAD *head, TAILQ_ENTRY NAME); 190 191 TAILQ_FOREACH_SAFE(VARNAME, TAILQ_HEAD *head, TAILQ_ENTRY 192 NAME, TEMP_VARNAME); 193 194 TAILQ_FOREACH_REVERSE(VARNAME, TAILQ_HEAD *head, HEADNAME, TAILQ_ENTRY 195 NAME); 196 197 TAILQ_FOREACH_REVERSE_SAFE(VARNAME, TAILQ_HEAD 198 *head, HEADNAME, TAILQ_ENTRY NAME, TEMP_VARNAME); 199 200 void 201 TAILQ_INIT(TAILQ_HEAD *head); 202 203 void 204 TAILQ_INSERT_AFTER(TAILQ_HEAD *head, struct TYPE *listelm, struct TYPE 205 *elm, TAILQ_ENTRY NAME); 206 207 void 208 TAILQ_INSERT_BEFORE(struct TYPE *listelm, struct TYPE *elm, TAILQ_ENTRY 209 NAME); 210 211 void 212 TAILQ_INSERT_HEAD(TAILQ_HEAD *head, struct TYPE *elm, TAILQ_ENTRY NAME); 213 214 void 215 TAILQ_INSERT_TAIL(TAILQ_HEAD *head, struct TYPE *elm, TAILQ_ENTRY NAME); 216 217 void 218 TAILQ_REMOVE(TAILQ_HEAD *head, struct TYPE *elm, TAILQ_ENTRY NAME); 219 220 void 221 TAILQ_REPLACE(TAILQ_HEAD *head, struct TYPE *elm, struct TYPE 222 *elm2, TAILQ_ENTRY NAME); 223 224 CIRCLEQ_ENTRY(TYPE); 225 226 CIRCLEQ_HEAD(HEADNAME, TYPE); 227 228 CIRCLEQ_HEAD_INITIALIZER(CIRCLEQ_HEAD head); 229 230 struct TYPE * 231 CIRCLEQ_FIRST(CIRCLEQ_HEAD *head); 232 233 struct TYPE * 234 CIRCLEQ_LAST(CIRCLEQ_HEAD *head); 235 236 struct TYPE * 237 CIRCLEQ_END(CIRCLEQ_HEAD *head); 238 239 struct TYPE * 240 CIRCLEQ_NEXT(struct TYPE *listelm, CIRCLEQ_ENTRY NAME); 241 242 struct TYPE * 243 CIRCLEQ_PREV(struct TYPE *listelm, CIRCLEQ_ENTRY NAME); 244 245 int 246 CIRCLEQ_EMPTY(CIRCLEQ_HEAD *head); 247 248 CIRCLEQ_FOREACH(VARNAME, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY NAME); 249 250 CIRCLEQ_FOREACH_SAFE(VARNAME, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY 251 NAME, TEMP_VARNAME); 252 253 CIRCLEQ_FOREACH_REVERSE(VARNAME, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY NAME); 254 255 CIRCLEQ_FOREACH_REVERSE_SAFE(VARNAME, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY 256 NAME, TEMP_VARNAME); 257 258 void 259 CIRCLEQ_INIT(CIRCLEQ_HEAD *head); 260 261 void 262 CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *head, struct TYPE *listelm, struct 263 TYPE *elm, CIRCLEQ_ENTRY NAME); 264 265 void 266 CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *head, struct TYPE *listelm, struct 267 TYPE *elm, CIRCLEQ_ENTRY NAME); 268 269 void 270 CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *head, struct TYPE *elm, CIRCLEQ_ENTRY 271 NAME); 272 273 void 274 CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *head, struct TYPE *elm, CIRCLEQ_ENTRY 275 NAME); 276 277 void 278 CIRCLEQ_REMOVE(CIRCLEQ_HEAD *head, struct TYPE *elm, CIRCLEQ_ENTRY NAME); 279 280 void 281 CIRCLEQ_REPLACE(CIRCLEQ_HEAD *head, struct TYPE *elm, struct TYPE 282 *elm2, CIRCLEQ_ENTRY NAME); 283 284 DESCRIPTION 285 These macros define and operate on five types of data structures: singly- 286 linked lists, simple queues, lists, tail queues, and circular queues. 287 All five structures support the following functionality: 288 289 1. Insertion of a new entry at the head of the list. 290 2. Insertion of a new entry after any element in the list. 291 3. Removal of an entry from the head of the list. 292 4. Forward traversal through the list. 293 294 Singly-linked lists are the simplest of the five data structures and 295 support only the above functionality. Singly-linked lists are ideal for 296 applications with large datasets and few or no removals, or for 297 implementing a LIFO queue. 298 299 Simple queues add the following functionality: 300 301 1. Entries can be added at the end of a list. 302 303 However: 304 305 1. All list insertions must specify the head of the list. 306 2. Each head entry requires two pointers rather than one. 307 3. Code size is about 15% greater and operations run about 20% 308 slower than singly-linked lists. 309 310 Simple queues are ideal for applications with large datasets and few or 311 no removals, or for implementing a FIFO queue. 312 313 All doubly linked types of data structures (lists, tail queues, and 314 circle queues) additionally allow: 315 316 1. Insertion of a new entry before any element in the list. 317 2. Removal of any entry in the list. 318 319 However: 320 321 1. Each element requires two pointers rather than one. 322 2. Code size and execution time of operations (except for 323 removal) is about twice that of the singly-linked data- 324 structures. 325 326 Lists are the simplest of the doubly linked data structures and support 327 only the above functionality over singly-linked lists. 328 329 Tail queues add the following functionality: 330 331 1. Entries can be added at the end of a list. 332 2. They may be traversed backwards, at a cost. 333 334 However: 335 336 1. All list insertions and removals must specify the head of the 337 list. 338 2. Each head entry requires two pointers rather than one. 339 3. Code size is about 15% greater and operations run about 20% 340 slower than singly-linked lists. 341 342 Circular queues add the following functionality: 343 344 1. Entries can be added at the end of a list. 345 2. They may be traversed backwards, from tail to head. 346 347 However: 348 349 1. All list insertions and removals must specify the head of the 350 list. 351 2. Each head entry requires two pointers rather than one. 352 3. The termination condition for traversal is more complex. 353 4. Code size is about 40% greater and operations run about 45% 354 slower than lists. 355 356 In the macro definitions, TYPE is the name tag of a user defined 357 structure that must contain a field of type SLIST_ENTRY, LIST_ENTRY, 358 SIMPLEQ_ENTRY, TAILQ_ENTRY, or CIRCLEQ_ENTRY, named NAME. The argument 359 HEADNAME is the name tag of a user defined structure that must be 360 declared using the macros SLIST_HEAD(), LIST_HEAD(), SIMPLEQ_HEAD(), 361 TAILQ_HEAD(), or CIRCLEQ_HEAD(). See the examples below for further 362 explanation of how these macros are used. 363 364 SINGLY-LINKED LISTS 365 A singly-linked list is headed by a structure defined by the SLIST_HEAD() 366 macro. This structure contains a single pointer to the first element on 367 the list. The elements are singly linked for minimum space and pointer 368 manipulation overhead at the expense of O(n) removal for arbitrary 369 elements. New elements can be added to the list after an existing 370 element or at the head of the list. A SLIST_HEAD structure is declared 371 as follows: 372 373 SLIST_HEAD(HEADNAME, TYPE) head; 374 375 where HEADNAME is the name of the structure to be defined, and struct 376 TYPE is the type of the elements to be linked into the list. A pointer 377 to the head of the list can later be declared as: 378 379 struct HEADNAME *headp; 380 381 (The names head and headp are user selectable.) 382 383 The HEADNAME facility is often not used, leading to the following bizarre 384 code: 385 386 SLIST_HEAD(, TYPE) head, *headp; 387 388 The SLIST_ENTRY() macro declares a structure that connects the elements 389 in the list. 390 391 The SLIST_INIT() macro initializes the list referenced by head. 392 393 The list can also be initialized statically by using the 394 SLIST_HEAD_INITIALIZER() macro like this: 395 396 SLIST_HEAD(HEADNAME, TYPE) head = SLIST_HEAD_INITIALIZER(head); 397 398 The SLIST_INSERT_HEAD() macro inserts the new element elm at the head of 399 the list. 400 401 The SLIST_INSERT_AFTER() macro inserts the new element elm after the 402 element listelm. 403 404 The SLIST_REMOVE_HEAD() macro removes the first element of the list 405 pointed by head. 406 407 The SLIST_REMOVE_AFTER() macro removes the list element immediately 408 following elm. 409 410 The SLIST_REMOVE() macro removes the element elm of the list pointed by 411 head. 412 413 The SLIST_FIRST() and SLIST_NEXT() macros can be used to traverse the 414 list: 415 416 for (np = SLIST_FIRST(&head); np != NULL; np = SLIST_NEXT(np, NAME)) 417 418 Or, for simplicity, one can use the SLIST_FOREACH() macro: 419 420 SLIST_FOREACH(np, head, NAME) 421 422 The macro SLIST_FOREACH_SAFE() traverses the list referenced by head in a 423 forward direction, assigning each element in turn to var. However, 424 unlike SLIST_FOREACH() it is permitted to remove var as well as free it 425 from within the loop safely without interfering with the traversal. 426 427 The SLIST_EMPTY() macro should be used to check whether a simple list is 428 empty. 429 430 SINGLY-LINKED LIST EXAMPLE 431 SLIST_HEAD(listhead, entry) head; 432 struct entry { 433 ... 434 SLIST_ENTRY(entry) entries; /* Simple list. */ 435 ... 436 } *n1, *n2, *np; 437 438 SLIST_INIT(&head); /* Initialize simple list. */ 439 440 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 441 SLIST_INSERT_HEAD(&head, n1, entries); 442 443 n2 = malloc(sizeof(struct entry)); /* Insert after. */ 444 SLIST_INSERT_AFTER(n1, n2, entries); 445 446 SLIST_FOREACH(np, &head, entries) /* Forward traversal. */ 447 np-> ... 448 449 while (!SLIST_EMPTY(&head)) { /* Delete. */ 450 n1 = SLIST_FIRST(&head); 451 SLIST_REMOVE_HEAD(&head, entries); 452 free(n1); 453 } 454 455 456 LISTS 457 A list is headed by a structure defined by the LIST_HEAD() macro. This 458 structure contains a single pointer to the first element on the list. 459 The elements are doubly linked so that an arbitrary element can be 460 removed without traversing the list. New elements can be added to the 461 list after an existing element, before an existing element, or at the 462 head of the list. A LIST_HEAD structure is declared as follows: 463 464 LIST_HEAD(HEADNAME, TYPE) head; 465 466 where HEADNAME is the name of the structure to be defined, and struct 467 TYPE is the type of the elements to be linked into the list. A pointer 468 to the head of the list can later be declared as: 469 470 struct HEADNAME *headp; 471 472 (The names head and headp are user selectable.) 473 474 The HEADNAME facility is often not used, leading to the following bizarre 475 code: 476 477 LIST_HEAD(, TYPE) head, *headp; 478 479 The LIST_ENTRY() macro declares a structure that connects the elements in 480 the list. 481 482 The LIST_INIT() macro initializes the list referenced by head. 483 484 The list can also be initialized statically by using the 485 LIST_HEAD_INITIALIZER() macro like this: 486 487 LIST_HEAD(HEADNAME, TYPE) head = LIST_HEAD_INITIALIZER(head); 488 489 The LIST_INSERT_HEAD() macro inserts the new element elm at the head of 490 the list. 491 492 The LIST_INSERT_AFTER() macro inserts the new element elm after the 493 element listelm. 494 495 The LIST_INSERT_BEFORE() macro inserts the new element elm before the 496 element listelm. 497 498 The LIST_REMOVE() macro removes the element elm from the list. 499 500 The LIST_REPLACE() macro replaces the list element elm with the new 501 element elm2. 502 503 The LIST_FIRST() and LIST_NEXT() macros can be used to traverse the list: 504 505 for (np = LIST_FIRST(&head); np != NULL; np = LIST_NEXT(np, NAME)) 506 507 Or, for simplicity, one can use the LIST_FOREACH() macro: 508 509 LIST_FOREACH(np, head, NAME) 510 511 The macro LIST_FOREACH_SAFE() traverses the list referenced by head in a 512 forward direction, assigning each element in turn to var. However, 513 unlike LIST_FOREACH() it is permitted to remove var as well as free it 514 from within the loop safely without interfering with the traversal. 515 516 The LIST_EMPTY() macro should be used to check whether a list is empty. 517 518 LIST EXAMPLE 519 LIST_HEAD(listhead, entry) head; 520 struct entry { 521 ... 522 LIST_ENTRY(entry) entries; /* List. */ 523 ... 524 } *n1, *n2, *np; 525 526 LIST_INIT(&head); /* Initialize list. */ 527 528 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 529 LIST_INSERT_HEAD(&head, n1, entries); 530 531 n2 = malloc(sizeof(struct entry)); /* Insert after. */ 532 LIST_INSERT_AFTER(n1, n2, entries); 533 534 n2 = malloc(sizeof(struct entry)); /* Insert before. */ 535 LIST_INSERT_BEFORE(n1, n2, entries); 536 /* Forward traversal. */ 537 LIST_FOREACH(np, &head, entries) 538 np-> ... 539 540 while (!LIST_EMPTY(&head)) /* Delete. */ 541 n1 = LIST_FIRST(&head); 542 LIST_REMOVE(n1, entries); 543 free(n1); 544 } 545 546 SIMPLE QUEUES 547 A simple queue is headed by a structure defined by the SIMPLEQ_HEAD() 548 macro. This structure contains a pair of pointers, one to the first 549 element in the simple queue and the other to the last element in the 550 simple queue. The elements are singly linked. New elements can be added 551 to the queue after an existing element, at the head of the queue or at 552 the tail of the queue. A SIMPLEQ_HEAD structure is declared as follows: 553 554 SIMPLEQ_HEAD(HEADNAME, TYPE) head; 555 556 where HEADNAME is the name of the structure to be defined, and struct 557 TYPE is the type of the elements to be linked into the queue. A pointer 558 to the head of the queue can later be declared as: 559 560 struct HEADNAME *headp; 561 562 (The names head and headp are user selectable.) 563 564 The SIMPLEQ_ENTRY() macro declares a structure that connects the elements 565 in the queue. 566 567 The SIMPLEQ_INIT() macro initializes the queue referenced by head. 568 569 The queue can also be initialized statically by using the 570 SIMPLEQ_HEAD_INITIALIZER() macro like this: 571 572 SIMPLEQ_HEAD(HEADNAME, TYPE) head = SIMPLEQ_HEAD_INITIALIZER(head); 573 574 The SIMPLEQ_INSERT_AFTER() macro inserts the new element elm after the 575 element listelm. 576 577 The SIMPLEQ_INSERT_HEAD() macro inserts the new element elm at the head 578 of the queue. 579 580 The SIMPLEQ_INSERT_TAIL() macro inserts the new element elm at the end of 581 the queue. 582 583 The SIMPLEQ_REMOVE_AFTER() macro removes the queue element immediately 584 following elm. 585 586 The SIMPLEQ_REMOVE_HEAD() macro removes the first element from the queue. 587 588 The SIMPLEQ_FIRST() and SIMPLEQ_NEXT() macros can be used to traverse the 589 queue. The SIMPLEQ_FOREACH() is used for queue traversal: 590 591 SIMPLEQ_FOREACH(np, head, NAME) 592 593 The macro SIMPLEQ_FOREACH_SAFE() traverses the queue referenced by head 594 in a forward direction, assigning each element in turn to var. However, 595 unlike SIMPLEQ_FOREACH() it is permitted to remove var as well as free it 596 from within the loop safely without interfering with the traversal. 597 598 The SIMPLEQ_EMPTY() macro should be used to check whether a list is 599 empty. 600 601 SIMPLE QUEUE EXAMPLE 602 SIMPLEQ_HEAD(listhead, entry) head = SIMPLEQ_HEAD_INITIALIZER(head); 603 struct entry { 604 ... 605 SIMPLEQ_ENTRY(entry) entries; /* Simple queue. */ 606 ... 607 } *n1, *n2, *np; 608 609 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 610 SIMPLEQ_INSERT_HEAD(&head, n1, entries); 611 612 n2 = malloc(sizeof(struct entry)); /* Insert after. */ 613 SIMPLEQ_INSERT_AFTER(&head, n1, n2, entries); 614 615 n2 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 616 SIMPLEQ_INSERT_TAIL(&head, n2, entries); 617 /* Forward traversal. */ 618 SIMPLEQ_FOREACH(np, &head, entries) 619 np-> ... 620 /* Delete. */ 621 while (!SIMPLEQ_EMPTY(&head)) { 622 n1 = SIMPLEQ_FIRST(&head); 623 SIMPLEQ_REMOVE_HEAD(&head, entries); 624 free(n1); 625 } 626 627 TAIL QUEUES 628 A tail queue is headed by a structure defined by the TAILQ_HEAD() macro. 629 This structure contains a pair of pointers, one to the first element in 630 the tail queue and the other to the last element in the tail queue. The 631 elements are doubly linked so that an arbitrary element can be removed 632 without traversing the tail queue. New elements can be added to the 633 queue after an existing element, before an existing element, at the head 634 of the queue, or at the end of the queue. A TAILQ_HEAD structure is 635 declared as follows: 636 637 TAILQ_HEAD(HEADNAME, TYPE) head; 638 639 where HEADNAME is the name of the structure to be defined, and struct 640 TYPE is the type of the elements to be linked into the tail queue. A 641 pointer to the head of the tail queue can later be declared as: 642 643 struct HEADNAME *headp; 644 645 (The names head and headp are user selectable.) 646 647 The TAILQ_ENTRY() macro declares a structure that connects the elements 648 in the tail queue. 649 650 The TAILQ_INIT() macro initializes the tail queue referenced by head. 651 652 The tail queue can also be initialized statically by using the 653 TAILQ_HEAD_INITIALIZER() macro. 654 655 The TAILQ_INSERT_HEAD() macro inserts the new element elm at the head of 656 the tail queue. 657 658 The TAILQ_INSERT_TAIL() macro inserts the new element elm at the end of 659 the tail queue. 660 661 The TAILQ_INSERT_AFTER() macro inserts the new element elm after the 662 element listelm. 663 664 The TAILQ_INSERT_BEFORE() macro inserts the new element elm before the 665 element listelm. 666 667 The TAILQ_REMOVE() macro removes the element elm from the tail queue. 668 669 The TAILQ_REPLACE() macro replaces the list element elm with the new 670 element elm2. 671 672 TAILQ_FOREACH() and TAILQ_FOREACH_REVERSE() are used for traversing a 673 tail queue. TAILQ_FOREACH() starts at the first element and proceeds 674 towards the last. TAILQ_FOREACH_REVERSE() starts at the last element and 675 proceeds towards the first. 676 677 TAILQ_FOREACH(np, &head, NAME) 678 TAILQ_FOREACH_REVERSE(np, &head, HEADNAME, NAME) 679 680 The macros TAILQ_FOREACH_SAFE() and TAILQ_FOREACH_REVERSE_SAFE() traverse 681 the list referenced by head in a forward or reverse direction 682 respectively, assigning each element in turn to var. However, unlike 683 their unsafe counterparts, they permit both the removal of var as well as 684 freeing it from within the loop safely without interfering with the 685 traversal. 686 687 The TAILQ_FIRST(), TAILQ_NEXT(), TAILQ_LAST() and TAILQ_PREV() macros can 688 be used to manually traverse a tail queue or an arbitrary part of one. 689 690 The TAILQ_EMPTY() macro should be used to check whether a tail queue is 691 empty. 692 693 TAIL QUEUE EXAMPLE 694 TAILQ_HEAD(tailhead, entry) head; 695 struct entry { 696 ... 697 TAILQ_ENTRY(entry) entries; /* Tail queue. */ 698 ... 699 } *n1, *n2, *np; 700 701 TAILQ_INIT(&head); /* Initialize queue. */ 702 703 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 704 TAILQ_INSERT_HEAD(&head, n1, entries); 705 706 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 707 TAILQ_INSERT_TAIL(&head, n1, entries); 708 709 n2 = malloc(sizeof(struct entry)); /* Insert after. */ 710 TAILQ_INSERT_AFTER(&head, n1, n2, entries); 711 712 n2 = malloc(sizeof(struct entry)); /* Insert before. */ 713 TAILQ_INSERT_BEFORE(n1, n2, entries); 714 /* Forward traversal. */ 715 TAILQ_FOREACH(np, &head, entries) 716 np-> ... 717 /* Manual forward traversal. */ 718 for (np = n2; np != NULL; np = TAILQ_NEXT(np, entries)) 719 np-> ... 720 /* Delete. */ 721 while ((np = TAILQ_FIRST(&head))) { 722 TAILQ_REMOVE(&head, np, entries); 723 free(np); 724 } 725 726 727 CIRCULAR QUEUES 728 A circular queue is headed by a structure defined by the CIRCLEQ_HEAD() 729 macro. This structure contains a pair of pointers, one to the first 730 element in the circular queue and the other to the last element in the 731 circular queue. The elements are doubly linked so that an arbitrary 732 element can be removed without traversing the queue. New elements can be 733 added to the queue after an existing element, before an existing element, 734 at the head of the queue, or at the end of the queue. A CIRCLEQ_HEAD 735 structure is declared as follows: 736 737 CIRCLEQ_HEAD(HEADNAME, TYPE) head; 738 739 where HEADNAME is the name of the structure to be defined, and struct 740 TYPE is the type of the elements to be linked into the circular queue. A 741 pointer to the head of the circular queue can later be declared as: 742 743 struct HEADNAME *headp; 744 745 (The names head and headp are user selectable.) 746 747 The CIRCLEQ_ENTRY() macro declares a structure that connects the elements 748 in the circular queue. 749 750 The CIRCLEQ_INIT() macro initializes the circular queue referenced by 751 head. 752 753 The circular queue can also be initialized statically by using the 754 CIRCLEQ_HEAD_INITIALIZER() macro. 755 756 The CIRCLEQ_INSERT_HEAD() macro inserts the new element elm at the head 757 of the circular queue. 758 759 The CIRCLEQ_INSERT_TAIL() macro inserts the new element elm at the end of 760 the circular queue. 761 762 The CIRCLEQ_INSERT_AFTER() macro inserts the new element elm after the 763 element listelm. 764 765 The CIRCLEQ_INSERT_BEFORE() macro inserts the new element elm before the 766 element listelm. 767 768 The CIRCLEQ_REMOVE() macro removes the element elm from the circular 769 queue. 770 771 The CIRCLEQ_REPLACE() macro replaces the list element elm with the new 772 element elm2. 773 774 The CIRCLEQ_FIRST(), CIRCLEQ_LAST(), CIRCLEQ_END(), CIRCLEQ_NEXT() and 775 CIRCLEQ_PREV() macros can be used to traverse a circular queue. The 776 CIRCLEQ_FOREACH() is used for circular queue forward traversal: 777 778 CIRCLEQ_FOREACH(np, head, NAME) 779 780 The CIRCLEQ_FOREACH_REVERSE() macro acts like CIRCLEQ_FOREACH() but 781 traverses the circular queue backwards. 782 783 The macros CIRCLEQ_FOREACH_SAFE() and CIRCLEQ_FOREACH_REVERSE_SAFE() 784 traverse the list referenced by head in a forward or reverse direction 785 respectively, assigning each element in turn to var. However, unlike 786 their unsafe counterparts, they permit both the removal of var as well as 787 freeing it from within the loop safely without interfering with the 788 traversal. 789 790 The CIRCLEQ_EMPTY() macro should be used to check whether a circular 791 queue is empty. 792 793 CIRCULAR QUEUE EXAMPLE 794 CIRCLEQ_HEAD(circleq, entry) head; 795 struct entry { 796 ... 797 CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */ 798 ... 799 } *n1, *n2, *np; 800 801 CIRCLEQ_INIT(&head); /* Initialize circular queue. */ 802 803 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ 804 CIRCLEQ_INSERT_HEAD(&head, n1, entries); 805 806 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ 807 CIRCLEQ_INSERT_TAIL(&head, n1, entries); 808 809 n2 = malloc(sizeof(struct entry)); /* Insert after. */ 810 CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries); 811 812 n2 = malloc(sizeof(struct entry)); /* Insert before. */ 813 CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries); 814 /* Forward traversal. */ 815 CIRCLEQ_FOREACH(np, &head, entries) 816 np-> ... 817 /* Reverse traversal. */ 818 CIRCLEQ_FOREACH_REVERSE(np, &head, entries) 819 np-> ... 820 /* Delete. */ 821 while (!CIRCLEQ_EMPTY(&head)) { 822 n1 = CIRCLEQ_FIRST(&head); 823 CIRCLEQ_REMOVE(&head, n1, entries); 824 free(n1); 825 } 826 827 NOTES 828 It is an error to assume the next and previous fields are preserved after 829 an element has been removed from a list or queue. Using any macro 830 (except the various forms of insertion) on an element removed from a list 831 or queue is incorrect. An example of erroneous usage is removing the 832 same element twice. 833 834 The SLIST_END(), LIST_END(), SIMPLEQ_END() and TAILQ_END() macros are 835 provided for symmetry with CIRCLEQ_END(). They expand to NULL and don't 836 serve any useful purpose. 837 838 Trying to free a list in the following way is a common error: 839 840 LIST_FOREACH(var, head, entry) 841 free(var); 842 free(head); 843 844 Since var is free'd, the FOREACH macros refer to a pointer that may have 845 been reallocated already. A similar situation occurs when the current 846 element is deleted from the list. In cases like these the data 847 structure's FOREACH_SAFE macros should be used instead. 848 849 HISTORY 850 The queue functions first appeared in 4.4BSD. 851 852 OpenBSD 5.0 April 11, 2012 OpenBSD 5.0 853 ====================================================================== 854 .\" $OpenBSD: queue.3,v 1.56 2012/04/11 13:29:14 naddy Exp $ 855 .\" $NetBSD: queue.3,v 1.4 1995/07/03 00:25:36 mycroft Exp $ 856 .\" 857 .\" Copyright (c) 1993 The Regents of the University of California. 858 .\" All rights reserved. 859 .\" 860 .\" Redistribution and use in source and binary forms, with or without 861 .\" modification, are permitted provided that the following conditions 862 .\" are met: 863 .\" 1. Redistributions of source code must retain the above copyright 864 .\" notice, this list of conditions and the following disclaimer. 865 .\" 2. Redistributions in binary form must reproduce the above copyright 866 .\" notice, this list of conditions and the following disclaimer in the 867 .\" documentation and/or other materials provided with the distribution. 868 .\" 3. Neither the name of the University nor the names of its contributors 869 .\" may be used to endorse or promote products derived from this software 870 .\" without specific prior written permission. 871 .\" 872 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 873 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 874 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 875 .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 876 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 877 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 878 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 879 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 880 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 881 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 882 .\" SUCH DAMAGE.