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 int              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__ integer_t
 229 remque(
 230         register queue_entry_t elt)
 231 {
 232         (elt->next)->prev = elt->prev;
 233         (elt->prev)->next = elt->next;
 234
 235         return((integer_t)elt);
 236 }
 237
 238 #endif  /* !__GNUC__ */
 239
 240 /*
 241  *      Macro:          queue_init
 242  *      Function:
 243  *              Initialize the given queue.
 244  *      Header:
 245  *              void queue_init(q)
 246  *                      queue_t         q;      \* MODIFIED *\
 247  */
 248 #define queue_init(q)   \
 249 MACRO_BEGIN             \
 250         (q)->next = (q);\
 251         (q)->prev = (q);\
 252 MACRO_END
 253
 254 /*
 255  *      Macro:          queue_first
 256  *      Function:
 257  *              Returns the first entry in the queue,
 258  *      Header:
 259  *              queue_entry_t queue_first(q)
 260  *                      queue_t q;              \* IN *\
 261  */
 262 #define queue_first(q)  ((q)->next)
 263
 264 /*
 265  *      Macro:          queue_next
 266  *      Function:
 267  *              Returns the entry after an item in the queue.
 268  *      Header:
 269  *              queue_entry_t queue_next(qc)
 270  *                      queue_t qc;
 271  */
 272 #define queue_next(qc)  ((qc)->next)
 273
 274 /*
 275  *      Macro:          queue_last
 276  *      Function:
 277  *              Returns the last entry in the queue.
 278  *      Header:
 279  *              queue_entry_t queue_last(q)
 280  *                      queue_t q;              \* IN *\
 281  */
 282 #define queue_last(q)   ((q)->prev)
 283
 284 /*
 285  *      Macro:          queue_prev
 286  *      Function:
 287  *              Returns the entry before an item in the queue.
 288  *      Header:
 289  *              queue_entry_t queue_prev(qc)
 290  *                      queue_t qc;
 291  */
 292 #define queue_prev(qc)  ((qc)->prev)
 293
 294 /*
 295  *      Macro:          queue_end
 296  *      Function:
 297  *              Tests whether a new entry is really the end of
 298  *              the queue.
 299  *      Header:
 300  *              boolean_t queue_end(q, qe)
 301  *                      queue_t q;
 302  *                      queue_entry_t qe;
 303  */
 304 #define queue_end(q, qe)        ((q) == (qe))
 305
 306 /*
 307  *      Macro:          queue_empty
 308  *      Function:
 309  *              Tests whether a queue is empty.
 310  *      Header:
 311  *              boolean_t queue_empty(q)
 312  *                      queue_t q;
 313  */
 314 #define queue_empty(q)          queue_end((q), queue_first(q))
 315
 316
 317 /*----------------------------------------------------------------*/
 318 /*
 319  * Macros that operate on generic structures.  The queue
 320  * chain may be at any location within the structure, and there
 321  * may be more than one chain.
 322  */
 323
 324 /*
 325  *      Macro:          queue_enter
 326  *      Function:
 327  *              Insert a new element at the tail of the queue.
 328  *      Header:
 329  *              void queue_enter(q, elt, type, field)
 330  *                      queue_t q;
 331  *                      <type> elt;
 332  *                      <type> is what's in our queue
 333  *                      <field> is the chain field in (*<type>)
 334  */
 335 #define queue_enter(head, elt, type, field)                     \
 336 MACRO_BEGIN                                                     \
 337         register queue_entry_t __prev;                          \
 338                                                                 \
 339         __prev = (head)->prev;                                  \
 340         if ((head) == __prev) {                                 \
 341                 (head)->next = (queue_entry_t) (elt);           \
 342         }                                                       \
 343         else {                                                  \
 344                 ((type)__prev)->field.next = (queue_entry_t)(elt);\
 345         }                                                       \
 346         (elt)->field.prev = __prev;                             \
 347         (elt)->field.next = head;                               \
 348         (head)->prev = (queue_entry_t) elt;                     \
 349 MACRO_END
 350
 351 /*
 352  *      Macro:          queue_enter_first
 353  *      Function:
 354  *              Insert a new element at the head of the queue.
 355  *      Header:
 356  *              void queue_enter_first(q, elt, type, field)
 357  *                      queue_t q;
 358  *                      <type> elt;
 359  *                      <type> is what's in our queue
 360  *                      <field> is the chain field in (*<type>)
 361  */
 362 #define queue_enter_first(head, elt, type, field)               \
 363 MACRO_BEGIN                                                     \
 364         register queue_entry_t __next;                          \
 365                                                                 \
 366         __next = (head)->next;                                  \
 367         if ((head) == __next) {                                 \
 368                 (head)->prev = (queue_entry_t) (elt);           \
 369         }                                                       \
 370         else {                                                  \
 371                 ((type)__next)->field.prev = (queue_entry_t)(elt);\
 372         }                                                       \
 373         (elt)->field.next = __next;                             \
 374         (elt)->field.prev = head;                               \
 375         (head)->next = (queue_entry_t) elt;                     \
 376 MACRO_END
 377
 378 /*
 379  *      Macro:          queue_insert_before
 380  *      Function:
 381  *              Insert a new element before a given element.
 382  *      Header:
 383  *              void queue_insert_before(q, elt, cur, type, field)
 384  *                      queue_t q;
 385  *                      <type> elt;
 386  *                      <type> cur;
 387  *                      <type> is what's in our queue
 388  *                      <field> is the chain field in (*<type>)
 389  */
 390 #define queue_insert_before(head, elt, cur, type, field)                \
 391 MACRO_BEGIN                                                             \
 392         register queue_entry_t __prev;                                  \
 393                                                                         \
 394         if ((head) == (queue_entry_t)(cur)) {                           \
 395                 (elt)->field.next = (head);                             \
 396                 if ((head)->next == (head)) {   /* only element */      \
 397                         (elt)->field.prev = (head);                     \
 398                         (head)->next = (queue_entry_t)(elt);            \
 399                 } else {                        /* last element */      \
 400                         __prev = (elt)->field.prev = (head)->prev;      \
 401                         ((type)__prev)->field.next = (queue_entry_t)(elt);\
 402                 }                                                       \
 403                 (head)->prev = (queue_entry_t)(elt);                    \
 404         } else {                                                        \
 405                 (elt)->field.next = (queue_entry_t)(cur);               \
 406                 if ((head)->next == (queue_entry_t)(cur)) {             \
 407                                                 /* first element */     \
 408                         (elt)->field.prev = (head);                     \
 409                         (head)->next = (queue_entry_t)(elt);            \
 410                 } else {                        /* middle element */    \
 411                         __prev = (elt)->field.prev = (cur)->field.prev; \
 412                         ((type)__prev)->field.next = (queue_entry_t)(elt);\
 413                 }                                                       \
 414                 (cur)->field.prev = (queue_entry_t)(elt);               \
 415         }                                                               \
 416 MACRO_END
 417
 418 /*
 419  *      Macro:          queue_insert_after
 420  *      Function:
 421  *              Insert a new element after a given element.
 422  *      Header:
 423  *              void queue_insert_after(q, elt, cur, type, field)
 424  *                      queue_t q;
 425  *                      <type> elt;
 426  *                      <type> cur;
 427  *                      <type> is what's in our queue
 428  *                      <field> is the chain field in (*<type>)
 429  */
 430 #define queue_insert_after(head, elt, cur, type, field)                 \
 431 MACRO_BEGIN                                                             \
 432         register queue_entry_t __next;                                  \
 433                                                                         \
 434         if ((head) == (queue_entry_t)(cur)) {                           \
 435                 (elt)->field.prev = (head);                             \
 436                 if ((head)->next == (head)) {   /* only element */      \
 437                         (elt)->field.next = (head);                     \
 438                         (head)->prev = (queue_entry_t)(elt);            \
 439                 } else {                        /* first element */     \
 440                         __next = (elt)->field.next = (head)->next;      \
 441                         ((type)__next)->field.prev = (queue_entry_t)(elt);\
 442                 }                                                       \
 443                 (head)->next = (queue_entry_t)(elt);                    \
 444         } else {                                                        \
 445                 (elt)->field.prev = (queue_entry_t)(cur);               \
 446                 if ((head)->prev == (queue_entry_t)(cur)) {             \
 447                                                 /* last element */      \
 448                         (elt)->field.next = (head);                     \
 449                         (head)->prev = (queue_entry_t)(elt);            \
 450                 } else {                        /* middle element */    \
 451                         __next = (elt)->field.next = (cur)->field.next; \
 452                         ((type)__next)->field.prev = (queue_entry_t)(elt);\
 453                 }                                                       \
 454                 (cur)->field.next = (queue_entry_t)(elt);               \
 455         }                                                               \
 456 MACRO_END
 457
 458 /*
 459  *      Macro:          queue_field [internal use only]
 460  *      Function:
 461  *              Find the queue_chain_t (or queue_t) for the
 462  *              given element (thing) in the given queue (head)
 463  */
 464 #define queue_field(head, thing, type, field)                   \
 465                 (((head) == (thing)) ? (head) : &((type)(thing))->field)
 466
 467 /*
 468  *      Macro:          queue_remove
 469  *      Function:
 470  *              Remove an arbitrary item from the queue.
 471  *      Header:
 472  *              void queue_remove(q, qe, type, field)
 473  *                      arguments as in queue_enter
 474  */
 475 #define queue_remove(head, elt, type, field)                    \
 476 MACRO_BEGIN                                                     \
 477         register queue_entry_t  __next, __prev;                 \
 478                                                                 \
 479         __next = (elt)->field.next;                             \
 480         __prev = (elt)->field.prev;                             \
 481                                                                 \
 482         if ((head) == __next)                                   \
 483                 (head)->prev = __prev;                          \
 484         else                                                    \
 485                 ((type)__next)->field.prev = __prev;            \
 486                                                                 \
 487         if ((head) == __prev)                                   \
 488                 (head)->next = __next;                          \
 489         else                                                    \
 490                 ((type)__prev)->field.next = __next;            \
 491 MACRO_END
 492
 493 /*
 494  *      Macro:          queue_remove_first
 495  *      Function:
 496  *              Remove and return the entry at the head of
 497  *              the queue.
 498  *      Header:
 499  *              queue_remove_first(head, entry, type, field)
 500  *              entry is returned by reference
 501  */
 502 #define queue_remove_first(head, entry, type, field)            \
 503 MACRO_BEGIN                                                     \
 504         register queue_entry_t  __next;                         \
 505                                                                 \
 506         (entry) = (type) ((head)->next);                        \
 507         __next = (entry)->field.next;                           \
 508                                                                 \
 509         if ((head) == __next)                                   \
 510                 (head)->prev = (head);                          \
 511         else                                                    \
 512                 ((type)(__next))->field.prev = (head);          \
 513         (head)->next = __next;                                  \
 514 MACRO_END
 515
 516 /*
 517  *      Macro:          queue_remove_last
 518  *      Function:
 519  *              Remove and return the entry at the tail of
 520  *              the queue.
 521  *      Header:
 522  *              queue_remove_last(head, entry, type, field)
 523  *              entry is returned by reference
 524  */
 525 #define queue_remove_last(head, entry, type, field)             \
 526 MACRO_BEGIN                                                     \
 527         register queue_entry_t  __prev;                         \
 528                                                                 \
 529         (entry) = (type) ((head)->prev);                        \
 530         __prev = (entry)->field.prev;                           \
 531                                                                 \
 532         if ((head) == __prev)                                   \
 533                 (head)->next = (head);                          \
 534         else                                                    \
 535                 ((type)(__prev))->field.next = (head);          \
 536         (head)->prev = __prev;                                  \
 537 MACRO_END
 538
 539 /*
 540  *      Macro:          queue_assign
 541  */
 542 #define queue_assign(to, from, type, field)                     \
 543 MACRO_BEGIN                                                     \
 544         ((type)((from)->prev))->field.next = (to);              \
 545         ((type)((from)->next))->field.prev = (to);              \
 546         *to = *from;                                            \
 547 MACRO_END
 548
 549 /*
 550  *      Macro:          queue_new_head
 551  *      Function:
 552  *              rebase old queue to new queue head
 553  *      Header:
 554  *              queue_new_head(old, new, type, field)
 555  *                      queue_t old;
 556  *                      queue_t new;
 557  *                      <type> is what's in our queue
 558  *                      <field> is the chain field in (*<type>)
 559  */
 560 #define queue_new_head(old, new, type, field)                   \
 561 MACRO_BEGIN                                                     \
 562         if (!queue_empty(old)) {                                \
 563                 *(new) = *(old);                                \
 564                 ((type)((new)->next))->field.prev = (new);      \
 565                 ((type)((new)->prev))->field.next = (new);      \
 566         } else {                                                \
 567                 queue_init(new);                                \
 568         }                                                       \
 569 MACRO_END
 570
 571 /*
 572  *      Macro:          queue_iterate
 573  *      Function:
 574  *              iterate over each item in the queue.
 575  *              Generates a 'for' loop, setting elt to
 576  *              each item in turn (by reference).
 577  *      Header:
 578  *              queue_iterate(q, elt, type, field)
 579  *                      queue_t q;
 580  *                      <type> elt;
 581  *                      <type> is what's in our queue
 582  *                      <field> is the chain field in (*<type>)
 583  */
 584 #define queue_iterate(head, elt, type, field)                   \
 585         for ((elt) = (type) queue_first(head);                  \
 586              !queue_end((head), (queue_entry_t)(elt));          \
 587              (elt) = (type) queue_next(&(elt)->field))
 588
 589 #ifdef  MACH_KERNEL_PRIVATE
 590
 591 #include <kern/lock.h>
 592
 593 /*----------------------------------------------------------------*/
 594 /*
 595  *      Define macros for queues with locks.
 596  */
 597 struct mpqueue_head {
 598         struct queue_entry      head;           /* header for queue */
 599         decl_simple_lock_data(, lock)           /* lock for queue */
 600 };
 601
 602 typedef struct mpqueue_head     mpqueue_head_t;
 603
 604 #define round_mpq(size)         (size)
 605
 606 #define mpqueue_init(q)                                 \
 607 MACRO_BEGIN                                             \
 608         queue_init(&(q)->head);                         \
 609         simple_lock_init(&(q)->lock, 0);        \
 610 MACRO_END
 611
 612 #define mpenqueue_tail(q, elt)                          \
 613 MACRO_BEGIN                                             \
 614         simple_lock(&(q)->lock);                        \
 615         enqueue_tail(&(q)->head, elt);                  \
 616         simple_unlock(&(q)->lock);                      \
 617 MACRO_END
 618
 619 #define mpdequeue_head(q, elt)                          \
 620 MACRO_BEGIN                                             \
 621         simple_lock(&(q)->lock);                        \
 622         if (queue_empty(&(q)->head))                    \
 623                 *(elt) = 0;                             \
 624         else                                            \
 625                 *(elt) = dequeue_head(&(q)->head);      \
 626         simple_unlock(&(q)->lock);                      \
 627 MACRO_END
 628
 629 #endif  /* MACH_KERNEL_PRIVATE */
 630
 631 #endif  /* _KERN_QUEUE_H_ */