osfmk/kern/queue.h

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