queue.h
1 /* 2 * Copyright (c) 2000-2009 Apple Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 */ 28 /* 29 * @OSF_COPYRIGHT@ 30 */ 31 /* 32 * Mach Operating System 33 * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University 34 * All Rights Reserved. 35 * 36 * Permission to use, copy, modify and distribute this software and its 37 * documentation is hereby granted, provided that both the copyright 38 * notice and this permission notice appear in all copies of the 39 * software, derivative works or modified versions, and any portions 40 * thereof, and that both notices appear in supporting documentation. 41 * 42 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" 43 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR 44 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. 45 * 46 * Carnegie Mellon requests users of this software to return to 47 * 48 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU 49 * School of Computer Science 50 * Carnegie Mellon University 51 * Pittsburgh PA 15213-3890 52 * 53 * any improvements or extensions that they make and grant Carnegie Mellon rights 54 * to redistribute these changes. 55 */ 56 /* 57 */ 58 /* 59 * File: queue.h 60 * Author: Avadis Tevanian, Jr. 61 * Date: 1985 62 * 63 * Type definitions for generic queues. 64 * 65 */ 66 67 #ifndef _KERN_QUEUE_H_ 68 #define _KERN_QUEUE_H_ 69 70 #include <mach/mach_types.h> 71 #include <kern/macro_help.h> 72 73 #include <sys/cdefs.h> 74 #include <string.h> 75 76 __BEGIN_DECLS 77 78 /* 79 * Queue Management APIs 80 * 81 * There are currently two subtly different methods of maintining 82 * a queue of objects. Both APIs are contained in this file, and 83 * unfortunately overlap. 84 * (there is also a third way maintained in bsd/sys/queue.h) 85 * 86 * Both methods use a common queue head and linkage pattern: 87 * The head of a queue is declared as: 88 * queue_head_t q_head; 89 * 90 * Elements in this queue are chained together using 91 * struct queue_entry objects embedded within a structure: 92 * struct some_data { 93 * int field1; 94 * int field2; 95 * ... 96 * queue_chain_t link; 97 * ... 98 * int last_field; 99 * }; 100 * struct some_data is referred to as the queue "element." 101 * (note that queue_chain_t is typedef'd to struct queue_entry) 102 * 103 * IMPORTANT: The two queue iteration methods described below are not 104 * compatible with one another. You must choose one and be careful 105 * to use only the supported APIs for that method. 106 * 107 * Method 1: chaining of queue_chain_t (linkage chains) 108 * This method uses the next and prev pointers of the struct queue_entry 109 * linkage object embedded in a queue element to point to the next or 110 * previous queue_entry structure in the chain. The head of the queue 111 * (the queue_head_t object) will point to the first and last 112 * struct queue_entry object, and both the next and prev pointer will 113 * point back to the head if the queue is empty. 114 * 115 * This method is the most flexible method of chaining objects together 116 * as it allows multiple chains through a given object, by embedding 117 * multiple queue_chain_t objects in the structure, while simultaneously 118 * providing fast removal and insertion into the queue using only 119 * struct queue_entry object pointers. 120 * 121 * ++ Valid APIs for this style queue ++ 122 * ------------------------------------- 123 * [C] queue_init 124 * [C] queue_first 125 * [C] queue_next 126 * [C] queue_last 127 * [C] queue_prev 128 * [C] queue_end 129 * [C] queue_empty 130 * 131 * [1] enqueue 132 * [1] dequeue 133 * [1] enqueue_head 134 * [1] enqueue_tail 135 * [1] dequeue_head 136 * [1] dequeue_tail 137 * [1] remqueue 138 * [1] insque 139 * [1] remque 140 * [1] re_queue_head 141 * [1] re_queue_tail 142 * [1] movqueue 143 * [1] qe_element 144 * [1] qe_foreach 145 * [1] qe_foreach_safe 146 * [1] qe_foreach_element 147 * [1] qe_foreach_element_safe 148 * 149 * Method 2: chaining of elements (element chains) 150 * This method uses the next and prev pointers of the struct queue_entry 151 * linkage object embedded in a queue element to point to the next or 152 * previous queue element (not another queue_entry). The head of the 153 * queue will point to the first and last queue element (struct some_data 154 * from the above example) NOT the embedded queue_entry structure. The 155 * first queue element will have a prev pointer that points to the 156 * queue_head_t, and the last queue element will have a next pointer 157 * that points to the queue_head_t. 158 * 159 * This method requires knowledge of the queue_head_t of the queue on 160 * which an element resides in order to remove the element. Iterating 161 * through the elements of the queue is also more cumbersome because 162 * a check against the head pointer plus a cast then offset operation 163 * must be performed at each step of the iteration. 164 * 165 * ++ Valid APIs for this style queue ++ 166 * ------------------------------------- 167 * [C] queue_init 168 * [C] queue_first 169 * [C] queue_next 170 * [C] queue_last 171 * [C] queue_prev 172 * [C] queue_end 173 * [C] queue_empty 174 * 175 * [2] queue_enter 176 * [2] queue_enter_first 177 * [2] queue_insert_before 178 * [2] queue_insert_after 179 * [2] queue_field 180 * [2] queue_remove 181 * [2] queue_remove_first 182 * [2] queue_remove_last 183 * [2] queue_assign 184 * [2] queue_new_head 185 * [2] queue_iterate 186 * 187 * Legend: 188 * [C] -> API common to both methods 189 * [1] -> API used only in method 1 (linkage chains) 190 * [2] -> API used only in method 2 (element chains) 191 */ 192 193 /* 194 * A generic doubly-linked list (queue). 195 */ 196 197 struct queue_entry { 198 struct queue_entry *next; /* next element */ 199 struct queue_entry *prev; /* previous element */ 200 201 #if __arm__ && (__BIGGEST_ALIGNMENT__ > 4) 202 /* For the newer ARMv7k ABI where 64-bit types are 64-bit aligned, but pointers 203 * are 32-bit: 204 * Since this type is so often cast to various 64-bit aligned types 205 * aligning it to 64-bits will avoid -wcast-align without needing 206 * to disable it entirely. The impact on memory footprint should be 207 * negligible. 208 */ 209 } __attribute__ ((aligned(8))); 210 #else 211 }; 212 #endif 213 214 typedef struct queue_entry *queue_t; 215 typedef struct queue_entry queue_head_t; 216 typedef struct queue_entry queue_chain_t; 217 typedef struct queue_entry *queue_entry_t; 218 219 /* 220 * enqueue puts "elt" on the "queue". 221 * dequeue returns the first element in the "queue". 222 * remqueue removes the specified "elt" from its queue. 223 */ 224 225 #define enqueue(queue, elt) enqueue_tail(queue, elt) 226 #define dequeue(queue) dequeue_head(queue) 227 228 #ifdef XNU_KERNEL_PRIVATE 229 #include <kern/debug.h> 230 static inline void 231 __QUEUE_ELT_VALIDATE(queue_entry_t elt) 232 { 233 queue_entry_t elt_next, elt_prev; 234 235 if (__improbable(elt == (queue_entry_t)NULL)) { 236 panic("Invalid queue element %p", elt); 237 } 238 239 elt_next = elt->next; 240 elt_prev = elt->prev; 241 242 if (__improbable(elt_next == (queue_entry_t)NULL || elt_prev == (queue_entry_t)NULL)) { 243 panic("Invalid queue element pointers for %p: next %p prev %p", elt, elt_next, elt_prev); 244 } 245 if (__improbable(elt_next->prev != elt || elt_prev->next != elt)) { 246 panic("Invalid queue element linkage for %p: next %p next->prev %p prev %p prev->next %p", 247 elt, elt_next, elt_next->prev, elt_prev, elt_prev->next); 248 } 249 } 250 251 static inline void 252 __DEQUEUE_ELT_CLEANUP(queue_entry_t elt) 253 { 254 (elt)->next = (queue_entry_t)NULL; 255 (elt)->prev = (queue_entry_t)NULL; 256 } 257 #else 258 #define __QUEUE_ELT_VALIDATE(elt) do { } while (0) 259 #define __DEQUEUE_ELT_CLEANUP(elt) do { } while(0) 260 #endif /* !XNU_KERNEL_PRIVATE */ 261 262 static __inline__ void 263 enqueue_head( 264 queue_t que, 265 queue_entry_t elt) 266 { 267 queue_entry_t old_head; 268 269 __QUEUE_ELT_VALIDATE((queue_entry_t)que); 270 old_head = que->next; 271 elt->next = old_head; 272 elt->prev = que; 273 old_head->prev = elt; 274 que->next = elt; 275 } 276 277 static __inline__ void 278 enqueue_tail( 279 queue_t que, 280 queue_entry_t elt) 281 { 282 queue_entry_t old_tail; 283 284 __QUEUE_ELT_VALIDATE((queue_entry_t)que); 285 old_tail = que->prev; 286 elt->next = que; 287 elt->prev = old_tail; 288 old_tail->next = elt; 289 que->prev = elt; 290 } 291 292 static __inline__ queue_entry_t 293 dequeue_head( 294 queue_t que) 295 { 296 queue_entry_t elt = (queue_entry_t)NULL; 297 queue_entry_t new_head; 298 299 if (que->next != que) { 300 elt = que->next; 301 __QUEUE_ELT_VALIDATE(elt); 302 new_head = elt->next; /* new_head may point to que if elt was the only element */ 303 new_head->prev = que; 304 que->next = new_head; 305 __DEQUEUE_ELT_CLEANUP(elt); 306 } 307 308 return elt; 309 } 310 311 static __inline__ queue_entry_t 312 dequeue_tail( 313 queue_t que) 314 { 315 queue_entry_t elt = (queue_entry_t)NULL; 316 queue_entry_t new_tail; 317 318 if (que->prev != que) { 319 elt = que->prev; 320 __QUEUE_ELT_VALIDATE(elt); 321 new_tail = elt->prev; /* new_tail may point to queue if elt was the only element */ 322 new_tail->next = que; 323 que->prev = new_tail; 324 __DEQUEUE_ELT_CLEANUP(elt); 325 } 326 327 return elt; 328 } 329 330 static __inline__ void 331 remqueue( 332 queue_entry_t elt) 333 { 334 queue_entry_t next_elt, prev_elt; 335 336 __QUEUE_ELT_VALIDATE(elt); 337 next_elt = elt->next; 338 prev_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */ 339 next_elt->prev = prev_elt; 340 prev_elt->next = next_elt; 341 __DEQUEUE_ELT_CLEANUP(elt); 342 } 343 344 static __inline__ void 345 insque( 346 queue_entry_t entry, 347 queue_entry_t pred) 348 { 349 queue_entry_t successor; 350 351 __QUEUE_ELT_VALIDATE(pred); 352 successor = pred->next; 353 entry->next = successor; 354 entry->prev = pred; 355 successor->prev = entry; 356 pred->next = entry; 357 } 358 359 static __inline__ void 360 remque( 361 queue_entry_t elt) 362 { 363 remqueue(elt); 364 } 365 366 /* 367 * Function: re_queue_head 368 * Parameters: 369 * queue_t que : queue onto which elt will be pre-pended 370 * queue_entry_t elt : element to re-queue 371 * Description: 372 * Remove elt from its current queue and put it onto the 373 * head of a new queue 374 * Note: 375 * This should only be used with Method 1 queue iteration (linkage chains) 376 */ 377 static __inline__ void 378 re_queue_head(queue_t que, queue_entry_t elt) 379 { 380 queue_entry_t n_elt, p_elt; 381 382 __QUEUE_ELT_VALIDATE(elt); 383 __QUEUE_ELT_VALIDATE((queue_entry_t)que); 384 385 /* remqueue */ 386 n_elt = elt->next; 387 p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */ 388 n_elt->prev = p_elt; 389 p_elt->next = n_elt; 390 391 /* enqueue_head */ 392 n_elt = que->next; 393 elt->next = n_elt; 394 elt->prev = que; 395 n_elt->prev = elt; 396 que->next = elt; 397 } 398 399 /* 400 * Function: re_queue_tail 401 * Parameters: 402 * queue_t que : queue onto which elt will be appended 403 * queue_entry_t elt : element to re-queue 404 * Description: 405 * Remove elt from its current queue and put it onto the 406 * end of a new queue 407 * Note: 408 * This should only be used with Method 1 queue iteration (linkage chains) 409 */ 410 static __inline__ void 411 re_queue_tail(queue_t que, queue_entry_t elt) 412 { 413 queue_entry_t n_elt, p_elt; 414 415 __QUEUE_ELT_VALIDATE(elt); 416 __QUEUE_ELT_VALIDATE((queue_entry_t)que); 417 418 /* remqueue */ 419 n_elt = elt->next; 420 p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */ 421 n_elt->prev = p_elt; 422 p_elt->next = n_elt; 423 424 /* enqueue_tail */ 425 p_elt = que->prev; 426 elt->next = que; 427 elt->prev = p_elt; 428 p_elt->next = elt; 429 que->prev = elt; 430 } 431 432 /* 433 * Macro: qe_element 434 * Function: 435 * Convert a queue_entry_t to a queue element pointer. 436 * Get a pointer to the user-defined element containing 437 * a given queue_entry_t 438 * Header: 439 * <type> * qe_element(queue_entry_t qe, <type>, field) 440 * qe - queue entry to convert 441 * <type> - what's in the queue (e.g., struct some_data) 442 * <field> - is the chain field in <type> 443 * Note: 444 * Do not use pointer types for <type> 445 */ 446 #define qe_element(qe, type, field) __container_of(qe, type, field) 447 448 /* 449 * Macro: qe_foreach 450 * Function: 451 * Iterate over each queue_entry_t structure. 452 * Generates a 'for' loop, setting 'qe' to 453 * each queue_entry_t in the queue. 454 * Header: 455 * qe_foreach(queue_entry_t qe, queue_t head) 456 * qe - iteration variable 457 * head - pointer to queue_head_t (head of queue) 458 * Note: 459 * This should only be used with Method 1 queue iteration (linkage chains) 460 */ 461 #define qe_foreach(qe, head) \ 462 for (qe = (head)->next; qe != (head); qe = (qe)->next) 463 464 /* 465 * Macro: qe_foreach_safe 466 * Function: 467 * Safely iterate over each queue_entry_t structure. 468 * 469 * Use this iterator macro if you plan to remove the 470 * queue_entry_t, qe, from the queue during the 471 * iteration. 472 * Header: 473 * qe_foreach_safe(queue_entry_t qe, queue_t head) 474 * qe - iteration variable 475 * head - pointer to queue_head_t (head of queue) 476 * Note: 477 * This should only be used with Method 1 queue iteration (linkage chains) 478 */ 479 #define qe_foreach_safe(qe, head) \ 480 for (queue_entry_t _ne = ((head)->next)->next, \ 481 __ ## qe ## _unused_shadow __unused = (qe = (head)->next); \ 482 qe != (head); \ 483 qe = _ne, _ne = (qe)->next) 484 485 /* 486 * Macro: qe_foreach_element 487 * Function: 488 * Iterate over each _element_ in a queue 489 * where each queue_entry_t points to another 490 * queue_entry_t, i.e., managed by the [de|en]queue_head/ 491 * [de|en]queue_tail / remqueue / etc. function. 492 * Header: 493 * qe_foreach_element(<type> *elt, queue_t head, <field>) 494 * elt - iteration variable 495 * <type> - what's in the queue (e.g., struct some_data) 496 * <field> - is the chain field in <type> 497 * Note: 498 * This should only be used with Method 1 queue iteration (linkage chains) 499 */ 500 #define qe_foreach_element(elt, head, field) \ 501 for (elt = qe_element((head)->next, typeof(*(elt)), field); \ 502 &((elt)->field) != (head); \ 503 elt = qe_element((elt)->field.next, typeof(*(elt)), field)) 504 505 /* 506 * Macro: qe_foreach_element_safe 507 * Function: 508 * Safely iterate over each _element_ in a queue 509 * where each queue_entry_t points to another 510 * queue_entry_t, i.e., managed by the [de|en]queue_head/ 511 * [de|en]queue_tail / remqueue / etc. function. 512 * 513 * Use this iterator macro if you plan to remove the 514 * element, elt, from the queue during the iteration. 515 * Header: 516 * qe_foreach_element_safe(<type> *elt, queue_t head, <field>) 517 * elt - iteration variable 518 * <type> - what's in the queue (e.g., struct some_data) 519 * <field> - is the chain field in <type> 520 * Note: 521 * This should only be used with Method 1 queue iteration (linkage chains) 522 */ 523 #define qe_foreach_element_safe(elt, head, field) \ 524 for (typeof(*(elt)) *_nelt = qe_element(((head)->next)->next, typeof(*(elt)), field), \ 525 *__ ## elt ## _unused_shadow __unused = \ 526 (elt = qe_element((head)->next, typeof(*(elt)), field)); \ 527 &((elt)->field) != (head); \ 528 elt = _nelt, _nelt = qe_element((elt)->field.next, typeof(*(elt)), field)) \ 529 530 #ifdef XNU_KERNEL_PRIVATE 531 532 /* Dequeue an element from head, or return NULL if the queue is empty */ 533 #define qe_dequeue_head(head, type, field) ({ \ 534 queue_entry_t _tmp_entry = dequeue_head((head)); \ 535 type *_tmp_element = (type*) NULL; \ 536 if (_tmp_entry != (queue_entry_t) NULL) \ 537 _tmp_element = qe_element(_tmp_entry, type, field); \ 538 _tmp_element; \ 539 }) 540 541 /* Dequeue an element from tail, or return NULL if the queue is empty */ 542 #define qe_dequeue_tail(head, type, field) ({ \ 543 queue_entry_t _tmp_entry = dequeue_tail((head)); \ 544 type *_tmp_element = (type*) NULL; \ 545 if (_tmp_entry != (queue_entry_t) NULL) \ 546 _tmp_element = qe_element(_tmp_entry, type, field); \ 547 _tmp_element; \ 548 }) 549 550 /* Peek at the first element, or return NULL if the queue is empty */ 551 #define qe_queue_first(head, type, field) ({ \ 552 queue_entry_t _tmp_entry = queue_first((head)); \ 553 type *_tmp_element = (type*) NULL; \ 554 if (_tmp_entry != (queue_entry_t) head) \ 555 _tmp_element = qe_element(_tmp_entry, type, field); \ 556 _tmp_element; \ 557 }) 558 559 /* Peek at the last element, or return NULL if the queue is empty */ 560 #define qe_queue_last(head, type, field) ({ \ 561 queue_entry_t _tmp_entry = queue_last((head)); \ 562 type *_tmp_element = (type*) NULL; \ 563 if (_tmp_entry != (queue_entry_t) head) \ 564 _tmp_element = qe_element(_tmp_entry, type, field); \ 565 _tmp_element; \ 566 }) 567 568 /* Peek at the next element, or return NULL if the next element is head (indicating queue_end) */ 569 #define qe_queue_next(head, element, type, field) ({ \ 570 queue_entry_t _tmp_entry = queue_next(&(element)->field); \ 571 type *_tmp_element = (type*) NULL; \ 572 if (_tmp_entry != (queue_entry_t) head) \ 573 _tmp_element = qe_element(_tmp_entry, type, field); \ 574 _tmp_element; \ 575 }) 576 577 /* Peek at the prev element, or return NULL if the prev element is head (indicating queue_end) */ 578 #define qe_queue_prev(head, element, type, field) ({ \ 579 queue_entry_t _tmp_entry = queue_prev(&(element)->field); \ 580 type *_tmp_element = (type*) NULL; \ 581 if (_tmp_entry != (queue_entry_t) head) \ 582 _tmp_element = qe_element(_tmp_entry, type, field); \ 583 _tmp_element; \ 584 }) 585 586 #endif /* XNU_KERNEL_PRIVATE */ 587 588 /* 589 * Macro: QUEUE_HEAD_INITIALIZER() 590 * Function: 591 * Static queue head initializer 592 */ 593 #define QUEUE_HEAD_INITIALIZER(name) \ 594 { &name, &name } 595 596 /* 597 * Macro: queue_init 598 * Function: 599 * Initialize the given queue. 600 * Header: 601 * void queue_init(q) 602 * queue_t q; \* MODIFIED *\ 603 */ 604 #define queue_init(q) \ 605 MACRO_BEGIN \ 606 (q)->next = (q);\ 607 (q)->prev = (q);\ 608 MACRO_END 609 610 /* 611 * Macro: queue_head_init 612 * Function: 613 * Initialize the given queue head 614 * Header: 615 * void queue_head_init(q) 616 * queue_head_t q; \* MODIFIED *\ 617 */ 618 #define queue_head_init(q) \ 619 queue_init(&(q)) 620 621 /* 622 * Macro: queue_chain_init 623 * Function: 624 * Initialize the given queue chain element 625 * Header: 626 * void queue_chain_init(q) 627 * queue_chain_t q; \* MODIFIED *\ 628 */ 629 #define queue_chain_init(q) \ 630 queue_init(&(q)) 631 632 /* 633 * Macro: queue_first 634 * Function: 635 * Returns the first entry in the queue, 636 * Header: 637 * queue_entry_t queue_first(q) 638 * queue_t q; \* IN *\ 639 */ 640 #define queue_first(q) ((q)->next) 641 642 /* 643 * Macro: queue_next 644 * Function: 645 * Returns the entry after an item in the queue. 646 * Header: 647 * queue_entry_t queue_next(qc) 648 * queue_t qc; 649 */ 650 #define queue_next(qc) ((qc)->next) 651 652 /* 653 * Macro: queue_last 654 * Function: 655 * Returns the last entry in the queue. 656 * Header: 657 * queue_entry_t queue_last(q) 658 * queue_t q; \* IN *\ 659 */ 660 #define queue_last(q) ((q)->prev) 661 662 /* 663 * Macro: queue_prev 664 * Function: 665 * Returns the entry before an item in the queue. 666 * Header: 667 * queue_entry_t queue_prev(qc) 668 * queue_t qc; 669 */ 670 #define queue_prev(qc) ((qc)->prev) 671 672 /* 673 * Macro: queue_end 674 * Function: 675 * Tests whether a new entry is really the end of 676 * the queue. 677 * Header: 678 * boolean_t queue_end(q, qe) 679 * queue_t q; 680 * queue_entry_t qe; 681 */ 682 #define queue_end(q, qe) ((q) == (qe)) 683 684 /* 685 * Macro: queue_empty 686 * Function: 687 * Tests whether a queue is empty. 688 * Header: 689 * boolean_t queue_empty(q) 690 * queue_t q; 691 */ 692 #define queue_empty(q) queue_end((q), queue_first(q)) 693 694 /* 695 * Function: movqueue 696 * Parameters: 697 * queue_t _old : head of a queue whose items will be moved 698 * queue_t _new : new queue head onto which items will be moved 699 * Description: 700 * Rebase queue items in _old onto _new then re-initialize 701 * the _old object to an empty queue. 702 * Equivalent to the queue_new_head Method 2 macro 703 * Note: 704 * Similar to the queue_new_head macro, this macros is intented 705 * to function as an initializer method for '_new' and thus may 706 * leak any list items that happen to be on the '_new' list. 707 * This should only be used with Method 1 queue iteration (linkage chains) 708 */ 709 static __inline__ void 710 movqueue(queue_t _old, queue_t _new) 711 { 712 queue_entry_t next_elt, prev_elt; 713 714 __QUEUE_ELT_VALIDATE((queue_entry_t)_old); 715 716 if (queue_empty(_old)) { 717 queue_init(_new); 718 return; 719 } 720 721 /* 722 * move the queue at _old to _new 723 * and re-initialize _old 724 */ 725 next_elt = _old->next; 726 prev_elt = _old->prev; 727 728 _new->next = next_elt; 729 _new->prev = prev_elt; 730 next_elt->prev = _new; 731 prev_elt->next = _new; 732 733 queue_init(_old); 734 } 735 736 /*----------------------------------------------------------------*/ 737 /* 738 * Macros that operate on generic structures. The queue 739 * chain may be at any location within the structure, and there 740 * may be more than one chain. 741 */ 742 743 /* 744 * Macro: queue_enter 745 * Function: 746 * Insert a new element at the tail of the queue. 747 * Header: 748 * void queue_enter(q, elt, type, field) 749 * queue_t q; 750 * <type> elt; 751 * <type> is what's in our queue 752 * <field> is the chain field in (*<type>) 753 * Note: 754 * This should only be used with Method 2 queue iteration (element chains) 755 * 756 * We insert a compiler barrier after setting the fields in the element 757 * to ensure that the element is updated before being added to the queue, 758 * which is especially important because stackshot, which operates from 759 * debugger context, iterates several queues that use this macro (the tasks 760 * lists and threads lists) without locks. Without this barrier, the 761 * compiler may re-order the instructions for this macro in a way that 762 * could cause stackshot to trip over an inconsistent queue during 763 * iteration. 764 */ 765 #define queue_enter(head, elt, type, field) \ 766 MACRO_BEGIN \ 767 queue_entry_t __prev; \ 768 \ 769 __prev = (head)->prev; \ 770 (elt)->field.prev = __prev; \ 771 (elt)->field.next = head; \ 772 __compiler_barrier(); \ 773 if ((head) == __prev) { \ 774 (head)->next = (queue_entry_t) (elt); \ 775 } \ 776 else { \ 777 ((type)(void *)__prev)->field.next = \ 778 (queue_entry_t)(elt); \ 779 } \ 780 (head)->prev = (queue_entry_t) elt; \ 781 MACRO_END 782 783 /* 784 * Macro: queue_enter_first 785 * Function: 786 * Insert a new element at the head of the queue. 787 * Header: 788 * void queue_enter_first(q, elt, type, field) 789 * queue_t q; 790 * <type> elt; 791 * <type> is what's in our queue 792 * <field> is the chain field in (*<type>) 793 * Note: 794 * This should only be used with Method 2 queue iteration (element chains) 795 */ 796 #define queue_enter_first(head, elt, type, field) \ 797 MACRO_BEGIN \ 798 queue_entry_t __next; \ 799 \ 800 __next = (head)->next; \ 801 if ((head) == __next) { \ 802 (head)->prev = (queue_entry_t) (elt); \ 803 } \ 804 else { \ 805 ((type)(void *)__next)->field.prev = \ 806 (queue_entry_t)(elt); \ 807 } \ 808 (elt)->field.next = __next; \ 809 (elt)->field.prev = head; \ 810 (head)->next = (queue_entry_t) elt; \ 811 MACRO_END 812 813 /* 814 * Macro: queue_insert_before 815 * Function: 816 * Insert a new element before a given element. 817 * Header: 818 * void queue_insert_before(q, elt, cur, type, field) 819 * queue_t q; 820 * <type> elt; 821 * <type> cur; 822 * <type> is what's in our queue 823 * <field> is the chain field in (*<type>) 824 * Note: 825 * This should only be used with Method 2 queue iteration (element chains) 826 */ 827 #define queue_insert_before(head, elt, cur, type, field) \ 828 MACRO_BEGIN \ 829 queue_entry_t __prev; \ 830 \ 831 if ((head) == (queue_entry_t)(cur)) { \ 832 (elt)->field.next = (head); \ 833 if ((head)->next == (head)) { /* only element */ \ 834 (elt)->field.prev = (head); \ 835 (head)->next = (queue_entry_t)(elt); \ 836 } else { /* last element */ \ 837 __prev = (elt)->field.prev = (head)->prev; \ 838 ((type)(void *)__prev)->field.next = \ 839 (queue_entry_t)(elt); \ 840 } \ 841 (head)->prev = (queue_entry_t)(elt); \ 842 } else { \ 843 (elt)->field.next = (queue_entry_t)(cur); \ 844 if ((head)->next == (queue_entry_t)(cur)) { \ 845 /* first element */ \ 846 (elt)->field.prev = (head); \ 847 (head)->next = (queue_entry_t)(elt); \ 848 } else { /* middle element */ \ 849 __prev = (elt)->field.prev = (cur)->field.prev; \ 850 ((type)(void *)__prev)->field.next = \ 851 (queue_entry_t)(elt); \ 852 } \ 853 (cur)->field.prev = (queue_entry_t)(elt); \ 854 } \ 855 MACRO_END 856 857 /* 858 * Macro: queue_insert_after 859 * Function: 860 * Insert a new element after a given element. 861 * Header: 862 * void queue_insert_after(q, elt, cur, type, field) 863 * queue_t q; 864 * <type> elt; 865 * <type> cur; 866 * <type> is what's in our queue 867 * <field> is the chain field in (*<type>) 868 * Note: 869 * This should only be used with Method 2 queue iteration (element chains) 870 */ 871 #define queue_insert_after(head, elt, cur, type, field) \ 872 MACRO_BEGIN \ 873 queue_entry_t __next; \ 874 \ 875 if ((head) == (queue_entry_t)(cur)) { \ 876 (elt)->field.prev = (head); \ 877 if ((head)->next == (head)) { /* only element */ \ 878 (elt)->field.next = (head); \ 879 (head)->prev = (queue_entry_t)(elt); \ 880 } else { /* first element */ \ 881 __next = (elt)->field.next = (head)->next; \ 882 ((type)(void *)__next)->field.prev = \ 883 (queue_entry_t)(elt); \ 884 } \ 885 (head)->next = (queue_entry_t)(elt); \ 886 } else { \ 887 (elt)->field.prev = (queue_entry_t)(cur); \ 888 if ((head)->prev == (queue_entry_t)(cur)) { \ 889 /* last element */ \ 890 (elt)->field.next = (head); \ 891 (head)->prev = (queue_entry_t)(elt); \ 892 } else { /* middle element */ \ 893 __next = (elt)->field.next = (cur)->field.next; \ 894 ((type)(void *)__next)->field.prev = \ 895 (queue_entry_t)(elt); \ 896 } \ 897 (cur)->field.next = (queue_entry_t)(elt); \ 898 } \ 899 MACRO_END 900 901 /* 902 * Macro: queue_field [internal use only] 903 * Function: 904 * Find the queue_chain_t (or queue_t) for the 905 * given element (thing) in the given queue (head) 906 * Note: 907 * This should only be used with Method 2 queue iteration (element chains) 908 */ 909 #define queue_field(head, thing, type, field) \ 910 (((head) == (thing)) ? (head) : &((type)(void *)(thing))->field) 911 912 /* 913 * Macro: queue_remove 914 * Function: 915 * Remove an arbitrary item from the queue. 916 * Header: 917 * void queue_remove(q, qe, type, field) 918 * arguments as in queue_enter 919 * Note: 920 * This should only be used with Method 2 queue iteration (element chains) 921 */ 922 #define queue_remove(head, elt, type, field) \ 923 MACRO_BEGIN \ 924 queue_entry_t __next, __prev; \ 925 \ 926 __next = (elt)->field.next; \ 927 __prev = (elt)->field.prev; \ 928 \ 929 if ((head) == __next) \ 930 (head)->prev = __prev; \ 931 else \ 932 ((type)(void *)__next)->field.prev = __prev; \ 933 \ 934 if ((head) == __prev) \ 935 (head)->next = __next; \ 936 else \ 937 ((type)(void *)__prev)->field.next = __next; \ 938 \ 939 (elt)->field.next = NULL; \ 940 (elt)->field.prev = NULL; \ 941 MACRO_END 942 943 /* 944 * Macro: queue_remove_first 945 * Function: 946 * Remove and return the entry at the head of 947 * the queue. 948 * Header: 949 * queue_remove_first(head, entry, type, field) 950 * entry is returned by reference 951 * Note: 952 * This should only be used with Method 2 queue iteration (element chains) 953 */ 954 #define queue_remove_first(head, entry, type, field) \ 955 MACRO_BEGIN \ 956 queue_entry_t __next; \ 957 \ 958 (entry) = (type)(void *) ((head)->next); \ 959 __next = (entry)->field.next; \ 960 \ 961 if ((head) == __next) \ 962 (head)->prev = (head); \ 963 else \ 964 ((type)(void *)(__next))->field.prev = (head); \ 965 (head)->next = __next; \ 966 \ 967 (entry)->field.next = NULL; \ 968 (entry)->field.prev = NULL; \ 969 MACRO_END 970 971 /* 972 * Macro: queue_remove_last 973 * Function: 974 * Remove and return the entry at the tail of 975 * the queue. 976 * Header: 977 * queue_remove_last(head, entry, type, field) 978 * entry is returned by reference 979 * Note: 980 * This should only be used with Method 2 queue iteration (element chains) 981 */ 982 #define queue_remove_last(head, entry, type, field) \ 983 MACRO_BEGIN \ 984 queue_entry_t __prev; \ 985 \ 986 (entry) = (type)(void *) ((head)->prev); \ 987 __prev = (entry)->field.prev; \ 988 \ 989 if ((head) == __prev) \ 990 (head)->next = (head); \ 991 else \ 992 ((type)(void *)(__prev))->field.next = (head); \ 993 (head)->prev = __prev; \ 994 \ 995 (entry)->field.next = NULL; \ 996 (entry)->field.prev = NULL; \ 997 MACRO_END 998 999 /* 1000 * Macro: queue_assign 1001 * Note: 1002 * This should only be used with Method 2 queue iteration (element chains) 1003 */ 1004 #define queue_assign(to, from, type, field) \ 1005 MACRO_BEGIN \ 1006 ((type)(void *)((from)->prev))->field.next = (to); \ 1007 ((type)(void *)((from)->next))->field.prev = (to); \ 1008 *to = *from; \ 1009 MACRO_END 1010 1011 /* 1012 * Macro: queue_new_head 1013 * Function: 1014 * rebase old queue to new queue head 1015 * Header: 1016 * queue_new_head(old, new, type, field) 1017 * queue_t old; 1018 * queue_t new; 1019 * <type> is what's in our queue 1020 * <field> is the chain field in (*<type>) 1021 * Note: 1022 * This should only be used with Method 2 queue iteration (element chains) 1023 */ 1024 #define queue_new_head(old, new, type, field) \ 1025 MACRO_BEGIN \ 1026 if (!queue_empty(old)) { \ 1027 *(new) = *(old); \ 1028 ((type)(void *)((new)->next))->field.prev = \ 1029 (new); \ 1030 ((type)(void *)((new)->prev))->field.next = \ 1031 (new); \ 1032 } else { \ 1033 queue_init(new); \ 1034 } \ 1035 MACRO_END 1036 1037 /* 1038 * Macro: queue_iterate 1039 * Function: 1040 * iterate over each item in the queue. 1041 * Generates a 'for' loop, setting elt to 1042 * each item in turn (by reference). 1043 * Header: 1044 * queue_iterate(q, elt, type, field) 1045 * queue_t q; 1046 * <type> elt; 1047 * <type> is what's in our queue 1048 * <field> is the chain field in (*<type>) 1049 * Note: 1050 * This should only be used with Method 2 queue iteration (element chains) 1051 */ 1052 #define queue_iterate(head, elt, type, field) \ 1053 for ((elt) = (type)(void *) queue_first(head); \ 1054 !queue_end((head), (queue_entry_t)(elt)); \ 1055 (elt) = (type)(void *) queue_next(&(elt)->field)) 1056 1057 1058 __END_DECLS 1059 1060 #endif /* _KERN_QUEUE_H_ */