osfmk/kern/queue.h

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