osfmk/kern/queue.h

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