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/* 74 * Queue of abstract objects. Queue is maintained 75 * within that object. 76 * 77 * Supports fast removal from within the queue. 78 * 79 * How to declare a queue of elements of type "foo_t": 80 * In the "*foo_t" type, you must have a field of 81 * type "queue_chain_t" to hold together this queue. 82 * There may be more than one chain through a 83 * "foo_t", for use by different queues. 84 * 85 * Declare the queue as a "queue_t" type. 86 * 87 * Elements of the queue (of type "foo_t", that is) 88 * are referred to by reference, and cast to type 89 * "queue_entry_t" within this module. 90 */ 91 92/* 93 * A generic doubly-linked list (queue). 94 */ 95 96struct queue_entry { 97 struct queue_entry *next; /* next element */ 98 struct queue_entry *prev; /* previous element */ 99}; 100 101typedef struct queue_entry *queue_t; 102typedef struct queue_entry queue_head_t; 103typedef struct queue_entry queue_chain_t; 104typedef struct queue_entry *queue_entry_t; 105 106/* 107 * enqueue puts "elt" on the "queue". 108 * dequeue returns the first element in the "queue". 109 * remqueue removes the specified "elt" from its queue. 110 */ 111 112#define enqueue(queue,elt) enqueue_tail(queue, elt) 113#define dequeue(queue) dequeue_head(queue) 114 115#if !defined(__GNUC__) 116 117#include <sys/cdefs.h> 118__BEGIN_DECLS 119 120/* Enqueue element to head of queue */ 121extern void enqueue_head( 122 queue_t que, 123 queue_entry_t elt); 124 125/* Enqueue element to tail of queue */ 126extern void enqueue_tail( 127 queue_t que, 128 queue_entry_t elt); 129 130/* Dequeue element from head of queue */ 131extern queue_entry_t dequeue_head( 132 queue_t que); 133 134/* Dequeue element from tail of queue */ 135extern queue_entry_t dequeue_tail( 136 queue_t que); 137 138/* Dequeue element */ 139extern void remqueue( 140 queue_entry_t elt); 141 142/* Enqueue element after a particular elem */ 143extern void insque( 144 queue_entry_t entry, 145 queue_entry_t pred); 146 147/* Dequeue element */ 148extern void remque( 149 queue_entry_t elt); 150 151__END_DECLS 152 153#else /* !__GNUC__ */ 154 155#ifdef XNU_KERNEL_PRIVATE 156#define __DEQUEUE_ELT_CLEANUP(elt) do { \ 157 (elt)->next = (queue_entry_t) 0; \ 158 (elt)->prev = (queue_entry_t) 0; \ 159 } while (0) 160#else 161#define __DEQUEUE_ELT_CLEANUP(elt) do { } while(0) 162#endif /* !XNU_KERNEL_PRIVATE */ 163 164static __inline__ void 165enqueue_head( 166 queue_t que, 167 queue_entry_t elt) 168{ 169 elt->next = que->next; 170 elt->prev = que; 171 elt->next->prev = elt; 172 que->next = elt; 173} 174 175static __inline__ void 176enqueue_tail( 177 queue_t que, 178 queue_entry_t elt) 179{ 180 elt->next = que; 181 elt->prev = que->prev; 182 elt->prev->next = elt; 183 que->prev = elt; 184} 185 186static __inline__ queue_entry_t 187dequeue_head( 188 queue_t que) 189{ 190 register queue_entry_t elt = (queue_entry_t) 0; 191 192 if (que->next != que) { 193 elt = que->next; 194 elt->next->prev = que; 195 que->next = elt->next; 196 __DEQUEUE_ELT_CLEANUP(elt); 197 } 198 199 return (elt); 200} 201 202static __inline__ queue_entry_t 203dequeue_tail( 204 queue_t que) 205{ 206 register queue_entry_t elt = (queue_entry_t) 0; 207 208 if (que->prev != que) { 209 elt = que->prev; 210 elt->prev->next = que; 211 que->prev = elt->prev; 212 __DEQUEUE_ELT_CLEANUP(elt); 213 } 214 215 return (elt); 216} 217 218static __inline__ void 219remqueue( 220 queue_entry_t elt) 221{ 222 elt->next->prev = elt->prev; 223 elt->prev->next = elt->next; 224 __DEQUEUE_ELT_CLEANUP(elt); 225} 226 227static __inline__ void 228insque( 229 queue_entry_t entry, 230 queue_entry_t pred) 231{ 232 entry->next = pred->next; 233 entry->prev = pred; 234 (pred->next)->prev = entry; 235 pred->next = entry; 236} 237 238static __inline__ void 239remque( 240 register queue_entry_t elt) 241{ 242 (elt->next)->prev = elt->prev; 243 (elt->prev)->next = elt->next; 244 __DEQUEUE_ELT_CLEANUP(elt); 245} 246 247#endif /* !__GNUC__ */ 248 249/* 250 * Macro: queue_init 251 * Function: 252 * Initialize the given queue. 253 * Header: 254 * void queue_init(q) 255 * queue_t q; \* MODIFIED *\ 256 */ 257#define queue_init(q) \ 258MACRO_BEGIN \ 259 (q)->next = (q);\ 260 (q)->prev = (q);\ 261MACRO_END 262 263/* 264 * Macro: queue_first 265 * Function: 266 * Returns the first entry in the queue, 267 * Header: 268 * queue_entry_t queue_first(q) 269 * queue_t q; \* IN *\ 270 */ 271#define queue_first(q) ((q)->next) 272 273/* 274 * Macro: queue_next 275 * Function: 276 * Returns the entry after an item in the queue. 277 * Header: 278 * queue_entry_t queue_next(qc) 279 * queue_t qc; 280 */ 281#define queue_next(qc) ((qc)->next) 282 283/* 284 * Macro: queue_last 285 * Function: 286 * Returns the last entry in the queue. 287 * Header: 288 * queue_entry_t queue_last(q) 289 * queue_t q; \* IN *\ 290 */ 291#define queue_last(q) ((q)->prev) 292 293/* 294 * Macro: queue_prev 295 * Function: 296 * Returns the entry before an item in the queue. 297 * Header: 298 * queue_entry_t queue_prev(qc) 299 * queue_t qc; 300 */ 301#define queue_prev(qc) ((qc)->prev) 302 303/* 304 * Macro: queue_end 305 * Function: 306 * Tests whether a new entry is really the end of 307 * the queue. 308 * Header: 309 * boolean_t queue_end(q, qe) 310 * queue_t q; 311 * queue_entry_t qe; 312 */ 313#define queue_end(q, qe) ((q) == (qe)) 314 315/* 316 * Macro: queue_empty 317 * Function: 318 * Tests whether a queue is empty. 319 * Header: 320 * boolean_t queue_empty(q) 321 * queue_t q; 322 */ 323#define queue_empty(q) queue_end((q), queue_first(q)) 324 325 326/*----------------------------------------------------------------*/ 327/* 328 * Macros that operate on generic structures. The queue 329 * chain may be at any location within the structure, and there 330 * may be more than one chain. 331 */ 332 333/* 334 * Macro: queue_enter 335 * Function: 336 * Insert a new element at the tail of the queue. 337 * Header: 338 * void queue_enter(q, elt, type, field) 339 * queue_t q; 340 * <type> elt; 341 * <type> is what's in our queue 342 * <field> is the chain field in (*<type>) 343 */ 344#define queue_enter(head, elt, type, field) \ 345MACRO_BEGIN \ 346 register queue_entry_t __prev; \ 347 \ 348 __prev = (head)->prev; \ 349 if ((head) == __prev) { \ 350 (head)->next = (queue_entry_t) (elt); \ 351 } \ 352 else { \ 353 ((type)__prev)->field.next = (queue_entry_t)(elt);\ 354 } \ 355 (elt)->field.prev = __prev; \ 356 (elt)->field.next = head; \ 357 (head)->prev = (queue_entry_t) elt; \ 358MACRO_END 359 360/* 361 * Macro: queue_enter_first 362 * Function: 363 * Insert a new element at the head of the queue. 364 * Header: 365 * void queue_enter_first(q, elt, type, field) 366 * queue_t q; 367 * <type> elt; 368 * <type> is what's in our queue 369 * <field> is the chain field in (*<type>) 370 */ 371#define queue_enter_first(head, elt, type, field) \ 372MACRO_BEGIN \ 373 register queue_entry_t __next; \ 374 \ 375 __next = (head)->next; \ 376 if ((head) == __next) { \ 377 (head)->prev = (queue_entry_t) (elt); \ 378 } \ 379 else { \ 380 ((type)__next)->field.prev = (queue_entry_t)(elt);\ 381 } \ 382 (elt)->field.next = __next; \ 383 (elt)->field.prev = head; \ 384 (head)->next = (queue_entry_t) elt; \ 385MACRO_END 386 387/* 388 * Macro: queue_insert_before 389 * Function: 390 * Insert a new element before a given element. 391 * Header: 392 * void queue_insert_before(q, elt, cur, type, field) 393 * queue_t q; 394 * <type> elt; 395 * <type> cur; 396 * <type> is what's in our queue 397 * <field> is the chain field in (*<type>) 398 */ 399#define queue_insert_before(head, elt, cur, type, field) \ 400MACRO_BEGIN \ 401 register queue_entry_t __prev; \ 402 \ 403 if ((head) == (queue_entry_t)(cur)) { \ 404 (elt)->field.next = (head); \ 405 if ((head)->next == (head)) { /* only element */ \ 406 (elt)->field.prev = (head); \ 407 (head)->next = (queue_entry_t)(elt); \ 408 } else { /* last element */ \ 409 __prev = (elt)->field.prev = (head)->prev; \ 410 ((type)__prev)->field.next = (queue_entry_t)(elt);\ 411 } \ 412 (head)->prev = (queue_entry_t)(elt); \ 413 } else { \ 414 (elt)->field.next = (queue_entry_t)(cur); \ 415 if ((head)->next == (queue_entry_t)(cur)) { \ 416 /* first element */ \ 417 (elt)->field.prev = (head); \ 418 (head)->next = (queue_entry_t)(elt); \ 419 } else { /* middle element */ \ 420 __prev = (elt)->field.prev = (cur)->field.prev; \ 421 ((type)__prev)->field.next = (queue_entry_t)(elt);\ 422 } \ 423 (cur)->field.prev = (queue_entry_t)(elt); \ 424 } \ 425MACRO_END 426 427/* 428 * Macro: queue_insert_after 429 * Function: 430 * Insert a new element after a given element. 431 * Header: 432 * void queue_insert_after(q, elt, cur, type, field) 433 * queue_t q; 434 * <type> elt; 435 * <type> cur; 436 * <type> is what's in our queue 437 * <field> is the chain field in (*<type>) 438 */ 439#define queue_insert_after(head, elt, cur, type, field) \ 440MACRO_BEGIN \ 441 register queue_entry_t __next; \ 442 \ 443 if ((head) == (queue_entry_t)(cur)) { \ 444 (elt)->field.prev = (head); \ 445 if ((head)->next == (head)) { /* only element */ \ 446 (elt)->field.next = (head); \ 447 (head)->prev = (queue_entry_t)(elt); \ 448 } else { /* first element */ \ 449 __next = (elt)->field.next = (head)->next; \ 450 ((type)__next)->field.prev = (queue_entry_t)(elt);\ 451 } \ 452 (head)->next = (queue_entry_t)(elt); \ 453 } else { \ 454 (elt)->field.prev = (queue_entry_t)(cur); \ 455 if ((head)->prev == (queue_entry_t)(cur)) { \ 456 /* last element */ \ 457 (elt)->field.next = (head); \ 458 (head)->prev = (queue_entry_t)(elt); \ 459 } else { /* middle element */ \ 460 __next = (elt)->field.next = (cur)->field.next; \ 461 ((type)__next)->field.prev = (queue_entry_t)(elt);\ 462 } \ 463 (cur)->field.next = (queue_entry_t)(elt); \ 464 } \ 465MACRO_END 466 467/* 468 * Macro: queue_field [internal use only] 469 * Function: 470 * Find the queue_chain_t (or queue_t) for the 471 * given element (thing) in the given queue (head) 472 */ 473#define queue_field(head, thing, type, field) \ 474 (((head) == (thing)) ? (head) : &((type)(thing))->field) 475 476/* 477 * Macro: queue_remove 478 * Function: 479 * Remove an arbitrary item from the queue. 480 * Header: 481 * void queue_remove(q, qe, type, field) 482 * arguments as in queue_enter 483 */ 484#define queue_remove(head, elt, type, field) \ 485MACRO_BEGIN \ 486 register queue_entry_t __next, __prev; \ 487 \ 488 __next = (elt)->field.next; \ 489 __prev = (elt)->field.prev; \ 490 \ 491 if ((head) == __next) \ 492 (head)->prev = __prev; \ 493 else \ 494 ((type)__next)->field.prev = __prev; \ 495 \ 496 if ((head) == __prev) \ 497 (head)->next = __next; \ 498 else \ 499 ((type)__prev)->field.next = __next; \ 500 \ 501 (elt)->field.next = NULL; \ 502 (elt)->field.prev = NULL; \ 503MACRO_END 504 505/* 506 * Macro: queue_remove_first 507 * Function: 508 * Remove and return the entry at the head of 509 * the queue. 510 * Header: 511 * queue_remove_first(head, entry, type, field) 512 * entry is returned by reference 513 */ 514#define queue_remove_first(head, entry, type, field) \ 515MACRO_BEGIN \ 516 register queue_entry_t __next; \ 517 \ 518 (entry) = (type) ((head)->next); \ 519 __next = (entry)->field.next; \ 520 \ 521 if ((head) == __next) \ 522 (head)->prev = (head); \ 523 else \ 524 ((type)(__next))->field.prev = (head); \ 525 (head)->next = __next; \ 526 \ 527 (entry)->field.next = NULL; \ 528 (entry)->field.prev = NULL; \ 529MACRO_END 530 531/* 532 * Macro: queue_remove_last 533 * Function: 534 * Remove and return the entry at the tail of 535 * the queue. 536 * Header: 537 * queue_remove_last(head, entry, type, field) 538 * entry is returned by reference 539 */ 540#define queue_remove_last(head, entry, type, field) \ 541MACRO_BEGIN \ 542 register queue_entry_t __prev; \ 543 \ 544 (entry) = (type) ((head)->prev); \ 545 __prev = (entry)->field.prev; \ 546 \ 547 if ((head) == __prev) \ 548 (head)->next = (head); \ 549 else \ 550 ((type)(__prev))->field.next = (head); \ 551 (head)->prev = __prev; \ 552 \ 553 (entry)->field.next = NULL; \ 554 (entry)->field.prev = NULL; \ 555MACRO_END 556 557/* 558 * Macro: queue_assign 559 */ 560#define queue_assign(to, from, type, field) \ 561MACRO_BEGIN \ 562 ((type)((from)->prev))->field.next = (to); \ 563 ((type)((from)->next))->field.prev = (to); \ 564 *to = *from; \ 565MACRO_END 566 567/* 568 * Macro: queue_new_head 569 * Function: 570 * rebase old queue to new queue head 571 * Header: 572 * queue_new_head(old, new, type, field) 573 * queue_t old; 574 * queue_t new; 575 * <type> is what's in our queue 576 * <field> is the chain field in (*<type>) 577 */ 578#define queue_new_head(old, new, type, field) \ 579MACRO_BEGIN \ 580 if (!queue_empty(old)) { \ 581 *(new) = *(old); \ 582 ((type)((new)->next))->field.prev = (new); \ 583 ((type)((new)->prev))->field.next = (new); \ 584 } else { \ 585 queue_init(new); \ 586 } \ 587MACRO_END 588 589/* 590 * Macro: queue_iterate 591 * Function: 592 * iterate over each item in the queue. 593 * Generates a 'for' loop, setting elt to 594 * each item in turn (by reference). 595 * Header: 596 * queue_iterate(q, elt, type, field) 597 * queue_t q; 598 * <type> elt; 599 * <type> is what's in our queue 600 * <field> is the chain field in (*<type>) 601 */ 602#define queue_iterate(head, elt, type, field) \ 603 for ((elt) = (type) queue_first(head); \ 604 !queue_end((head), (queue_entry_t)(elt)); \ 605 (elt) = (type) queue_next(&(elt)->field)) 606 607#ifdef MACH_KERNEL_PRIVATE 608 609#include <kern/lock.h> 610 611/*----------------------------------------------------------------*/ 612/* 613 * Define macros for queues with locks. 614 */ 615struct mpqueue_head { 616 struct queue_entry head; /* header for queue */ 617#if defined(__i386__) || defined(__x86_64__) 618 lck_mtx_t lock_data; 619 lck_mtx_ext_t lock_data_ext; 620#else 621 lck_spin_t lock_data; 622#endif 623}; 624 625typedef struct mpqueue_head mpqueue_head_t; 626 627#define round_mpq(size) (size) 628 629 630#if defined(__i386__) || defined(__x86_64__) 631 632#define mpqueue_init(q, lck_grp, lck_attr) \ 633MACRO_BEGIN \ 634 queue_init(&(q)->head); \ 635 lck_mtx_init_ext(&(q)->lock_data, \ 636 &(q)->lock_data_ext, \ 637 lck_grp, \ 638 lck_attr); \ 639MACRO_END 640 641#else 642 643#define mpqueue_init(q, lck_grp, lck_attr) \ 644MACRO_BEGIN \ 645 queue_init(&(q)->head); \ 646 lck_spin_init(&(q)->lock_data, \ 647 lck_grp, \ 648 lck_attr); \ 649MACRO_END 650#endif 651 652 653#define mpenqueue_tail(q, elt) \ 654MACRO_BEGIN \ 655 lck_mtx_lock_spin_always(&(q)->lock_data); \ 656 enqueue_tail(&(q)->head, elt); \ 657 lck_mtx_unlock_always(&(q)->lock_data); \ 658MACRO_END 659 660#define mpdequeue_head(q, elt) \ 661MACRO_BEGIN \ 662 lck_mtx_lock_spin_always(&(q)->lock_data); \ 663 if (queue_empty(&(q)->head)) \ 664 *(elt) = 0; \ 665 else \ 666 *(elt) = dequeue_head(&(q)->head); \ 667 lck_mtx_unlock_always(&(q)->lock_data); \ 668MACRO_END 669 670#endif /* MACH_KERNEL_PRIVATE */ 671 672#endif /* _KERN_QUEUE_H_ */ 673