osfmk/kern/queue.h

   1 /*
   2  * Copyright (c) 2000-2005 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * The contents of this file constitute Original Code as defined in and
   7  * are subject to the Apple Public Source License Version 1.1 (the
   8  * "License").  You may not use this file except in compliance with the
   9  * License.  Please obtain a copy of the License at
  10  * http://www.apple.com/publicsource and read it before using this file.
  11  *
  12  * This Original Code and all software distributed under the License are
  13  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  14  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  15  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
  17  * License for the specific language governing rights and limitations
  18  * under the License.
  19  *
  20  * @APPLE_LICENSE_HEADER_END@
  21  */
  22 /*
  23  * @OSF_COPYRIGHT@
  24  */
  25 /*
  26  * Mach Operating System
  27  * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
  28  * All Rights Reserved.
  29  *
  30  * Permission to use, copy, modify and distribute this software and its
  31  * documentation is hereby granted, provided that both the copyright
  32  * notice and this permission notice appear in all copies of the
  33  * software, derivative works or modified versions, and any portions
  34  * thereof, and that both notices appear in supporting documentation.
  35  *
  36  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
  37  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
  38  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  39  *
  40  * Carnegie Mellon requests users of this software to return to
  41  *
  42  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
  43  *  School of Computer Science
  44  *  Carnegie Mellon University
  45  *  Pittsburgh PA 15213-3890
  46  *
  47  * any improvements or extensions that they make and grant Carnegie Mellon rights
  48  * to redistribute these changes.
  49  */
  50 /*
  51  */
  52 /*
  53  *      File:   queue.h
  54  *      Author: Avadis Tevanian, Jr.
  55  *      Date:   1985
  56  *
  57  *      Type definitions for generic queues.
  58  *
  59  */
  60
  61 #ifndef _KERN_QUEUE_H_
  62 #define _KERN_QUEUE_H_
  63
  64 #include <mach/mach_types.h>
  65 #include <kern/macro_help.h>
  66
  67 /*
  68  *      Queue of abstract objects.  Queue is maintained
  69  *      within that object.
  70  *
  71  *      Supports fast removal from within the queue.
  72  *
  73  *      How to declare a queue of elements of type "foo_t":
  74  *              In the "*foo_t" type, you must have a field of
  75  *              type "queue_chain_t" to hold together this queue.
  76  *              There may be more than one chain through a
  77  *              "foo_t", for use by different queues.
  78  *
  79  *              Declare the queue as a "queue_t" type.
  80  *
  81  *              Elements of the queue (of type "foo_t", that is)
  82  *              are referred to by reference, and cast to type
  83  *              "queue_entry_t" within this module.
  84  */
  85
  86 /*
  87  *      A generic doubly-linked list (queue).
  88  */
  89
  90 struct queue_entry {
  91         struct queue_entry      *next;          /* next element */
  92         struct queue_entry      *prev;          /* previous element */
  93 };
  94
  95 typedef struct queue_entry      *queue_t;
  96 typedef struct queue_entry      queue_head_t;
  97 typedef struct queue_entry      queue_chain_t;
  98 typedef struct queue_entry      *queue_entry_t;
  99
 100 /*
 101  *      enqueue puts "elt" on the "queue".
 102  *      dequeue returns the first element in the "queue".
 103  *      remqueue removes the specified "elt" from the specified "queue".
 104  */
 105
 106 #define enqueue(queue,elt)      enqueue_tail(queue, elt)
 107 #define dequeue(queue)          dequeue_head(queue)
 108
 109 #if     !defined(__GNUC__)
 110
 111 #include <sys/cdefs.h>
 112 __BEGIN_DECLS
 113
 114 /* Enqueue element to head of queue */
 115 extern void             enqueue_head(
 116                                 queue_t         que,
 117                                 queue_entry_t   elt);
 118
 119 /* Enqueue element to tail of queue */
 120 extern void             enqueue_tail(
 121                                 queue_t         que,
 122                                 queue_entry_t   elt);
 123
 124 /* Dequeue element from head of queue */
 125 extern queue_entry_t    dequeue_head(
 126                                 queue_t que);
 127
 128 /* Dequeue element from tail of queue */
 129 extern queue_entry_t    dequeue_tail(
 130                                 queue_t que);
 131
 132 /* Dequeue element */
 133 extern void             remqueue(
 134                                 queue_t         que,
 135                                 queue_entry_t   elt);
 136
 137 /* Enqueue element after a particular elem */
 138 extern void             insque(
 139                                 queue_entry_t   entry,
 140                                 queue_entry_t   pred);
 141
 142 /* Dequeue element */
 143 extern int              remque(
 144                                 queue_entry_t elt);
 145
 146 __END_DECLS
 147
 148 #else   /* !__GNUC__ */
 149
 150 static __inline__ void
 151 enqueue_head(
 152         queue_t         que,
 153         queue_entry_t   elt)
 154 {
 155         elt->next = que->next;
 156         elt->prev = que;
 157         elt->next->prev = elt;
 158         que->next = elt;
 159 }
 160
 161 static __inline__ void
 162 enqueue_tail(
 163                 queue_t         que,
 164                 queue_entry_t   elt)
 165 {
 166         elt->next = que;
 167         elt->prev = que->prev;
 168         elt->prev->next = elt;
 169         que->prev = elt;
 170 }
 171
 172 static __inline__ queue_entry_t
 173 dequeue_head(
 174         queue_t que)
 175 {
 176         register queue_entry_t  elt = (queue_entry_t) 0;
 177
 178         if (que->next != que) {
 179                 elt = que->next;
 180                 elt->next->prev = que;
 181                 que->next = elt->next;
 182         }
 183
 184         return (elt);
 185 }
 186
 187 static __inline__ queue_entry_t
 188 dequeue_tail(
 189         queue_t que)
 190 {
 191         register queue_entry_t  elt = (queue_entry_t) 0;
 192
 193         if (que->prev != que) {
 194                 elt = que->prev;
 195                 elt->prev->next = que;
 196                 que->prev = elt->prev;
 197         }
 198
 199         return (elt);
 200 }
 201
 202 static __inline__ void
 203 remqueue(
 204         __unused queue_t                que,
 205         queue_entry_t   elt)
 206 {
 207         elt->next->prev = elt->prev;
 208         elt->prev->next = elt->next;
 209 }
 210
 211 static __inline__ void
 212 insque(
 213         queue_entry_t   entry,
 214         queue_entry_t   pred)
 215 {
 216         entry->next = pred->next;
 217         entry->prev = pred;
 218         (pred->next)->prev = entry;
 219         pred->next = entry;
 220 }
 221
 222 static __inline__ integer_t
 223 remque(
 224         register queue_entry_t elt)
 225 {
 226         (elt->next)->prev = elt->prev;
 227         (elt->prev)->next = elt->next;
 228
 229         return((integer_t)elt);
 230 }
 231
 232 #endif  /* !__GNUC__ */
 233
 234 /*
 235  *      Macro:          queue_init
 236  *      Function:
 237  *              Initialize the given queue.
 238  *      Header:
 239  *              void queue_init(q)
 240  *                      queue_t         q;      \* MODIFIED *\
 241  */
 242 #define queue_init(q)   \
 243 MACRO_BEGIN             \
 244         (q)->next = (q);\
 245         (q)->prev = (q);\
 246 MACRO_END
 247
 248 /*
 249  *      Macro:          queue_first
 250  *      Function:
 251  *              Returns the first entry in the queue,
 252  *      Header:
 253  *              queue_entry_t queue_first(q)
 254  *                      queue_t q;              \* IN *\
 255  */
 256 #define queue_first(q)  ((q)->next)
 257
 258 /*
 259  *      Macro:          queue_next
 260  *      Function:
 261  *              Returns the entry after an item in the queue.
 262  *      Header:
 263  *              queue_entry_t queue_next(qc)
 264  *                      queue_t qc;
 265  */
 266 #define queue_next(qc)  ((qc)->next)
 267
 268 /*
 269  *      Macro:          queue_last
 270  *      Function:
 271  *              Returns the last entry in the queue.
 272  *      Header:
 273  *              queue_entry_t queue_last(q)
 274  *                      queue_t q;              \* IN *\
 275  */
 276 #define queue_last(q)   ((q)->prev)
 277
 278 /*
 279  *      Macro:          queue_prev
 280  *      Function:
 281  *              Returns the entry before an item in the queue.
 282  *      Header:
 283  *              queue_entry_t queue_prev(qc)
 284  *                      queue_t qc;
 285  */
 286 #define queue_prev(qc)  ((qc)->prev)
 287
 288 /*
 289  *      Macro:          queue_end
 290  *      Function:
 291  *              Tests whether a new entry is really the end of
 292  *              the queue.
 293  *      Header:
 294  *              boolean_t queue_end(q, qe)
 295  *                      queue_t q;
 296  *                      queue_entry_t qe;
 297  */
 298 #define queue_end(q, qe)        ((q) == (qe))
 299
 300 /*
 301  *      Macro:          queue_empty
 302  *      Function:
 303  *              Tests whether a queue is empty.
 304  *      Header:
 305  *              boolean_t queue_empty(q)
 306  *                      queue_t q;
 307  */
 308 #define queue_empty(q)          queue_end((q), queue_first(q))
 309
 310
 311 /*----------------------------------------------------------------*/
 312 /*
 313  * Macros that operate on generic structures.  The queue
 314  * chain may be at any location within the structure, and there
 315  * may be more than one chain.
 316  */
 317
 318 /*
 319  *      Macro:          queue_enter
 320  *      Function:
 321  *              Insert a new element at the tail of the queue.
 322  *      Header:
 323  *              void queue_enter(q, elt, type, field)
 324  *                      queue_t q;
 325  *                      <type> elt;
 326  *                      <type> is what's in our queue
 327  *                      <field> is the chain field in (*<type>)
 328  */
 329 #define queue_enter(head, elt, type, field)                     \
 330 MACRO_BEGIN                                                     \
 331         register queue_entry_t __prev;                          \
 332                                                                 \
 333         __prev = (head)->prev;                                  \
 334         if ((head) == __prev) {                                 \
 335                 (head)->next = (queue_entry_t) (elt);           \
 336         }                                                       \
 337         else {                                                  \
 338                 ((type)__prev)->field.next = (queue_entry_t)(elt);\
 339         }                                                       \
 340         (elt)->field.prev = __prev;                             \
 341         (elt)->field.next = head;                               \
 342         (head)->prev = (queue_entry_t) elt;                     \
 343 MACRO_END
 344
 345 /*
 346  *      Macro:          queue_enter_first
 347  *      Function:
 348  *              Insert a new element at the head of the queue.
 349  *      Header:
 350  *              void queue_enter_first(q, elt, type, field)
 351  *                      queue_t q;
 352  *                      <type> elt;
 353  *                      <type> is what's in our queue
 354  *                      <field> is the chain field in (*<type>)
 355  */
 356 #define queue_enter_first(head, elt, type, field)               \
 357 MACRO_BEGIN                                                     \
 358         register queue_entry_t __next;                          \
 359                                                                 \
 360         __next = (head)->next;                                  \
 361         if ((head) == __next) {                                 \
 362                 (head)->prev = (queue_entry_t) (elt);           \
 363         }                                                       \
 364         else {                                                  \
 365                 ((type)__next)->field.prev = (queue_entry_t)(elt);\
 366         }                                                       \
 367         (elt)->field.next = __next;                             \
 368         (elt)->field.prev = head;                               \
 369         (head)->next = (queue_entry_t) elt;                     \
 370 MACRO_END
 371
 372 /*
 373  *      Macro:          queue_insert_before
 374  *      Function:
 375  *              Insert a new element before a given element.
 376  *      Header:
 377  *              void queue_insert_before(q, elt, cur, type, field)
 378  *                      queue_t q;
 379  *                      <type> elt;
 380  *                      <type> cur;
 381  *                      <type> is what's in our queue
 382  *                      <field> is the chain field in (*<type>)
 383  */
 384 #define queue_insert_before(head, elt, cur, type, field)                \
 385 MACRO_BEGIN                                                             \
 386         register queue_entry_t __prev;                                  \
 387                                                                         \
 388         if ((head) == (queue_entry_t)(cur)) {                           \
 389                 (elt)->field.next = (head);                             \
 390                 if ((head)->next == (head)) {   /* only element */      \
 391                         (elt)->field.prev = (head);                     \
 392                         (head)->next = (queue_entry_t)(elt);            \
 393                 } else {                        /* last element */      \
 394                         __prev = (elt)->field.prev = (head)->prev;      \
 395                         ((type)__prev)->field.next = (queue_entry_t)(elt);\
 396                 }                                                       \
 397                 (head)->prev = (queue_entry_t)(elt);                    \
 398         } else {                                                        \
 399                 (elt)->field.next = (queue_entry_t)(cur);               \
 400                 if ((head)->next == (queue_entry_t)(cur)) {             \
 401                                                 /* first element */     \
 402                         (elt)->field.prev = (head);                     \
 403                         (head)->next = (queue_entry_t)(elt);            \
 404                 } else {                        /* middle element */    \
 405                         __prev = (elt)->field.prev = (cur)->field.prev; \
 406                         ((type)__prev)->field.next = (queue_entry_t)(elt);\
 407                 }                                                       \
 408                 (cur)->field.prev = (queue_entry_t)(elt);               \
 409         }                                                               \
 410 MACRO_END
 411
 412 /*
 413  *      Macro:          queue_insert_after
 414  *      Function:
 415  *              Insert a new element after a given element.
 416  *      Header:
 417  *              void queue_insert_after(q, elt, cur, type, field)
 418  *                      queue_t q;
 419  *                      <type> elt;
 420  *                      <type> cur;
 421  *                      <type> is what's in our queue
 422  *                      <field> is the chain field in (*<type>)
 423  */
 424 #define queue_insert_after(head, elt, cur, type, field)                 \
 425 MACRO_BEGIN                                                             \
 426         register queue_entry_t __next;                                  \
 427                                                                         \
 428         if ((head) == (queue_entry_t)(cur)) {                           \
 429                 (elt)->field.prev = (head);                             \
 430                 if ((head)->next == (head)) {   /* only element */      \
 431                         (elt)->field.next = (head);                     \
 432                         (head)->prev = (queue_entry_t)(elt);            \
 433                 } else {                        /* first element */     \
 434                         __next = (elt)->field.next = (head)->next;      \
 435                         ((type)__next)->field.prev = (queue_entry_t)(elt);\
 436                 }                                                       \
 437                 (head)->next = (queue_entry_t)(elt);                    \
 438         } else {                                                        \
 439                 (elt)->field.prev = (queue_entry_t)(cur);               \
 440                 if ((head)->prev == (queue_entry_t)(cur)) {             \
 441                                                 /* last element */      \
 442                         (elt)->field.next = (head);                     \
 443                         (head)->prev = (queue_entry_t)(elt);            \
 444                 } else {                        /* middle element */    \
 445                         __next = (elt)->field.next = (cur)->field.next; \
 446                         ((type)__next)->field.prev = (queue_entry_t)(elt);\
 447                 }                                                       \
 448                 (cur)->field.next = (queue_entry_t)(elt);               \
 449         }                                                               \
 450 MACRO_END
 451
 452 /*
 453  *      Macro:          queue_field [internal use only]
 454  *      Function:
 455  *              Find the queue_chain_t (or queue_t) for the
 456  *              given element (thing) in the given queue (head)
 457  */
 458 #define queue_field(head, thing, type, field)                   \
 459                 (((head) == (thing)) ? (head) : &((type)(thing))->field)
 460
 461 /*
 462  *      Macro:          queue_remove
 463  *      Function:
 464  *              Remove an arbitrary item from the queue.
 465  *      Header:
 466  *              void queue_remove(q, qe, type, field)
 467  *                      arguments as in queue_enter
 468  */
 469 #define queue_remove(head, elt, type, field)                    \
 470 MACRO_BEGIN                                                     \
 471         register queue_entry_t  __next, __prev;                 \
 472                                                                 \
 473         __next = (elt)->field.next;                             \
 474         __prev = (elt)->field.prev;                             \
 475                                                                 \
 476         if ((head) == __next)                                   \
 477                 (head)->prev = __prev;                          \
 478         else                                                    \
 479                 ((type)__next)->field.prev = __prev;            \
 480                                                                 \
 481         if ((head) == __prev)                                   \
 482                 (head)->next = __next;                          \
 483         else                                                    \
 484                 ((type)__prev)->field.next = __next;            \
 485 MACRO_END
 486
 487 /*
 488  *      Macro:          queue_remove_first
 489  *      Function:
 490  *              Remove and return the entry at the head of
 491  *              the queue.
 492  *      Header:
 493  *              queue_remove_first(head, entry, type, field)
 494  *              entry is returned by reference
 495  */
 496 #define queue_remove_first(head, entry, type, field)            \
 497 MACRO_BEGIN                                                     \
 498         register queue_entry_t  __next;                         \
 499                                                                 \
 500         (entry) = (type) ((head)->next);                        \
 501         __next = (entry)->field.next;                           \
 502                                                                 \
 503         if ((head) == __next)                                   \
 504                 (head)->prev = (head);                          \
 505         else                                                    \
 506                 ((type)(__next))->field.prev = (head);          \
 507         (head)->next = __next;                                  \
 508 MACRO_END
 509
 510 /*
 511  *      Macro:          queue_remove_last
 512  *      Function:
 513  *              Remove and return the entry at the tail of
 514  *              the queue.
 515  *      Header:
 516  *              queue_remove_last(head, entry, type, field)
 517  *              entry is returned by reference
 518  */
 519 #define queue_remove_last(head, entry, type, field)             \
 520 MACRO_BEGIN                                                     \
 521         register queue_entry_t  __prev;                         \
 522                                                                 \
 523         (entry) = (type) ((head)->prev);                        \
 524         __prev = (entry)->field.prev;                           \
 525                                                                 \
 526         if ((head) == __prev)                                   \
 527                 (head)->next = (head);                          \
 528         else                                                    \
 529                 ((type)(__prev))->field.next = (head);          \
 530         (head)->prev = __prev;                                  \
 531 MACRO_END
 532
 533 /*
 534  *      Macro:          queue_assign
 535  */
 536 #define queue_assign(to, from, type, field)                     \
 537 MACRO_BEGIN                                                     \
 538         ((type)((from)->prev))->field.next = (to);              \
 539         ((type)((from)->next))->field.prev = (to);              \
 540         *to = *from;                                            \
 541 MACRO_END
 542
 543 /*
 544  *      Macro:          queue_new_head
 545  *      Function:
 546  *              rebase old queue to new queue head
 547  *      Header:
 548  *              queue_new_head(old, new, type, field)
 549  *                      queue_t old;
 550  *                      queue_t new;
 551  *                      <type> is what's in our queue
 552  *                      <field> is the chain field in (*<type>)
 553  */
 554 #define queue_new_head(old, new, type, field)                   \
 555 MACRO_BEGIN                                                     \
 556         if (!queue_empty(old)) {                                \
 557                 *(new) = *(old);                                \
 558                 ((type)((new)->next))->field.prev = (new);      \
 559                 ((type)((new)->prev))->field.next = (new);      \
 560         } else {                                                \
 561                 queue_init(new);                                \
 562         }                                                       \
 563 MACRO_END
 564
 565 /*
 566  *      Macro:          queue_iterate
 567  *      Function:
 568  *              iterate over each item in the queue.
 569  *              Generates a 'for' loop, setting elt to
 570  *              each item in turn (by reference).
 571  *      Header:
 572  *              queue_iterate(q, elt, type, field)
 573  *                      queue_t q;
 574  *                      <type> elt;
 575  *                      <type> is what's in our queue
 576  *                      <field> is the chain field in (*<type>)
 577  */
 578 #define queue_iterate(head, elt, type, field)                   \
 579         for ((elt) = (type) queue_first(head);                  \
 580              !queue_end((head), (queue_entry_t)(elt));          \
 581              (elt) = (type) queue_next(&(elt)->field))
 582
 583 #ifdef  MACH_KERNEL_PRIVATE
 584
 585 #include <kern/lock.h>
 586
 587 /*----------------------------------------------------------------*/
 588 /*
 589  *      Define macros for queues with locks.
 590  */
 591 struct mpqueue_head {
 592         struct queue_entry      head;           /* header for queue */
 593         decl_simple_lock_data(, lock)           /* lock for queue */
 594 };
 595
 596 typedef struct mpqueue_head     mpqueue_head_t;
 597
 598 #define round_mpq(size)         (size)
 599
 600 #define mpqueue_init(q)                                 \
 601 MACRO_BEGIN                                             \
 602         queue_init(&(q)->head);                         \
 603         simple_lock_init(&(q)->lock, 0);        \
 604 MACRO_END
 605
 606 #define mpenqueue_tail(q, elt)                          \
 607 MACRO_BEGIN                                             \
 608         simple_lock(&(q)->lock);                        \
 609         enqueue_tail(&(q)->head, elt);                  \
 610         simple_unlock(&(q)->lock);                      \
 611 MACRO_END
 612
 613 #define mpdequeue_head(q, elt)                          \
 614 MACRO_BEGIN                                             \
 615         simple_lock(&(q)->lock);                        \
 616         if (queue_empty(&(q)->head))                    \
 617                 *(elt) = 0;                             \
 618         else                                            \
 619                 *(elt) = dequeue_head(&(q)->head);      \
 620         simple_unlock(&(q)->lock);                      \
 621 MACRO_END
 622
 623 #endif  /* MACH_KERNEL_PRIVATE */
 624
 625 #endif  /* _KERN_QUEUE_H_ */