osfmk/kern/queue.h

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