osfmk/kern/queue.h

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