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 #include <sys/cdefs.h>
  74 #include <string.h>
  75
  76 __BEGIN_DECLS
  77
  78 /*
  79  * Queue Management APIs
  80  *
  81  * There are currently two subtly different methods of maintining
  82  * a queue of objects. Both APIs are contained in this file, and
  83  * unfortunately overlap.
  84  * (there is also a third way maintained in bsd/sys/queue.h)
  85  *
  86  * Both methods use a common queue head and linkage pattern:
  87  *      The head of a queue is declared as:
  88  *              queue_head_t q_head;
  89  *
  90  *      Elements in this queue are chained together using
  91  *      struct queue_entry objects embedded within a structure:
  92  *              struct some_data {
  93  *                      int field1;
  94  *                      int field2;
  95  *                      ...
  96  *                      queue_chain_t link;
  97  *                      ...
  98  *                      int last_field;
  99  *              };
 100  *      struct some_data is referred to as the queue "element."
 101  *      (note that queue_chain_t is typedef'd to struct queue_entry)
 102  *
 103  * IMPORTANT: The two queue iteration methods described below are not
 104  *            compatible with one another. You must choose one and be careful
 105  *            to use only the supported APIs for that method.
 106  *
 107  * Method 1: chaining of queue_chain_t (linkage chains)
 108  *      This method uses the next and prev pointers of the struct queue_entry
 109  *      linkage object embedded in a queue element to point to the next or
 110  *      previous queue_entry structure in the chain. The head of the queue
 111  *      (the queue_head_t object) will point to the first and last
 112  *      struct queue_entry object, and both the next and prev pointer will
 113  *      point back to the head if the queue is empty.
 114  *
 115  *      This method is the most flexible method of chaining objects together
 116  *      as it allows multiple chains through a given object, by embedding
 117  *      multiple queue_chain_t objects in the structure, while simultaneously
 118  *      providing fast removal and insertion into the queue using only
 119  *      struct queue_entry object pointers.
 120  *
 121  *      ++ Valid APIs for this style queue ++
 122  *      -------------------------------------
 123  *              [C] queue_init
 124  *              [C] queue_first
 125  *              [C] queue_next
 126  *              [C] queue_last
 127  *              [C] queue_prev
 128  *              [C] queue_end
 129  *              [C] queue_empty
 130  *
 131  *              [1] enqueue
 132  *              [1] dequeue
 133  *              [1] enqueue_head
 134  *              [1] enqueue_tail
 135  *              [1] dequeue_head
 136  *              [1] dequeue_tail
 137  *              [1] remqueue
 138  *              [1] insque
 139  *              [1] remque
 140  *              [1] re_queue_head
 141  *              [1] re_queue_tail
 142  *              [1] movqueue
 143  *              [1] qe_element
 144  *              [1] qe_foreach
 145  *              [1] qe_foreach_safe
 146  *              [1] qe_foreach_element
 147  *              [1] qe_foreach_element_safe
 148  *
 149  * Method 2: chaining of elements (element chains)
 150  *      This method uses the next and prev pointers of the struct queue_entry
 151  *      linkage object embedded in a queue element to point to the next or
 152  *      previous queue element (not another queue_entry). The head of the
 153  *      queue will point to the first and last queue element (struct some_data
 154  *      from the above example) NOT the embedded queue_entry structure. The
 155  *      first queue element will have a prev pointer that points to the
 156  *      queue_head_t, and the last queue element will have a next pointer
 157  *      that points to the queue_head_t.
 158  *
 159  *      This method requires knowledge of the queue_head_t of the queue on
 160  *      which an element resides in order to remove the element. Iterating
 161  *      through the elements of the queue is also more cumbersome because
 162  *      a check against the head pointer plus a cast then offset operation
 163  *      must be performed at each step of the iteration.
 164  *
 165  *      ++ Valid APIs for this style queue ++
 166  *      -------------------------------------
 167  *              [C] queue_init
 168  *              [C] queue_first
 169  *              [C] queue_next
 170  *              [C] queue_last
 171  *              [C] queue_prev
 172  *              [C] queue_end
 173  *              [C] queue_empty
 174  *
 175  *              [2] queue_enter
 176  *              [2] queue_enter_first
 177  *              [2] queue_insert_before
 178  *              [2] queue_insert_after
 179  *              [2] queue_field
 180  *              [2] queue_remove
 181  *              [2] queue_remove_first
 182  *              [2] queue_remove_last
 183  *              [2] queue_assign
 184  *              [2] queue_new_head
 185  *              [2] queue_iterate
 186  *
 187  * Legend:
 188  *      [C] -> API common to both methods
 189  *      [1] -> API used only in method 1 (linkage chains)
 190  *      [2] -> API used only in method 2 (element chains)
 191  */
 192
 193 /*
 194  *      A generic doubly-linked list (queue).
 195  */
 196
 197 struct queue_entry {
 198         struct queue_entry      *next;          /* next element */
 199         struct queue_entry      *prev;          /* previous element */
 200
 201 #if __arm__ && (__BIGGEST_ALIGNMENT__ > 4)
 202 /* For the newer ARMv7k ABI where 64-bit types are 64-bit aligned, but pointers
 203  * are 32-bit:
 204  * Since this type is so often cast to various 64-bit aligned types
 205  * aligning it to 64-bits will avoid -wcast-align without needing
 206  * to disable it entirely. The impact on memory footprint should be
 207  * negligible.
 208  */
 209 } __attribute__ ((aligned(8)));
 210 #else
 211 };
 212 #endif
 213
 214 typedef struct queue_entry      *queue_t;
 215 typedef struct queue_entry      queue_head_t;
 216 typedef struct queue_entry      queue_chain_t;
 217 typedef struct queue_entry      *queue_entry_t;
 218
 219 /*
 220  *      enqueue puts "elt" on the "queue".
 221  *      dequeue returns the first element in the "queue".
 222  *      remqueue removes the specified "elt" from its queue.
 223  */
 224
 225 #define enqueue(queue, elt)      enqueue_tail(queue, elt)
 226 #define dequeue(queue)          dequeue_head(queue)
 227
 228 #ifdef XNU_KERNEL_PRIVATE
 229 #include <kern/debug.h>
 230 static inline void
 231 __QUEUE_ELT_VALIDATE(queue_entry_t elt)
 232 {
 233         queue_entry_t   elt_next, elt_prev;
 234
 235         if (__improbable(elt == (queue_entry_t)NULL)) {
 236                 panic("Invalid queue element %p", elt);
 237         }
 238
 239         elt_next = elt->next;
 240         elt_prev = elt->prev;
 241
 242         if (__improbable(elt_next == (queue_entry_t)NULL || elt_prev == (queue_entry_t)NULL)) {
 243                 panic("Invalid queue element pointers for %p: next %p prev %p", elt, elt_next, elt_prev);
 244         }
 245         if (__improbable(elt_next->prev != elt || elt_prev->next != elt)) {
 246                 panic("Invalid queue element linkage for %p: next %p next->prev %p prev %p prev->next %p",
 247                     elt, elt_next, elt_next->prev, elt_prev, elt_prev->next);
 248         }
 249 }
 250
 251 static inline void
 252 __DEQUEUE_ELT_CLEANUP(queue_entry_t elt)
 253 {
 254         (elt)->next = (queue_entry_t)NULL;
 255         (elt)->prev = (queue_entry_t)NULL;
 256 }
 257 #else
 258 #define __QUEUE_ELT_VALIDATE(elt) do { } while (0)
 259 #define __DEQUEUE_ELT_CLEANUP(elt) do { } while(0)
 260 #endif /* !XNU_KERNEL_PRIVATE */
 261
 262 static __inline__ void
 263 enqueue_head(
 264         queue_t         que,
 265         queue_entry_t   elt)
 266 {
 267         queue_entry_t   old_head;
 268
 269         __QUEUE_ELT_VALIDATE((queue_entry_t)que);
 270         old_head = que->next;
 271         elt->next = old_head;
 272         elt->prev = que;
 273         old_head->prev = elt;
 274         que->next = elt;
 275 }
 276
 277 static __inline__ void
 278 enqueue_tail(
 279         queue_t         que,
 280         queue_entry_t   elt)
 281 {
 282         queue_entry_t   old_tail;
 283
 284         __QUEUE_ELT_VALIDATE((queue_entry_t)que);
 285         old_tail = que->prev;
 286         elt->next = que;
 287         elt->prev = old_tail;
 288         old_tail->next = elt;
 289         que->prev = elt;
 290 }
 291
 292 static __inline__ queue_entry_t
 293 dequeue_head(
 294         queue_t que)
 295 {
 296         queue_entry_t   elt = (queue_entry_t)NULL;
 297         queue_entry_t   new_head;
 298
 299         if (que->next != que) {
 300                 elt = que->next;
 301                 __QUEUE_ELT_VALIDATE(elt);
 302                 new_head = elt->next; /* new_head may point to que if elt was the only element */
 303                 new_head->prev = que;
 304                 que->next = new_head;
 305                 __DEQUEUE_ELT_CLEANUP(elt);
 306         }
 307
 308         return elt;
 309 }
 310
 311 static __inline__ queue_entry_t
 312 dequeue_tail(
 313         queue_t que)
 314 {
 315         queue_entry_t   elt = (queue_entry_t)NULL;
 316         queue_entry_t   new_tail;
 317
 318         if (que->prev != que) {
 319                 elt = que->prev;
 320                 __QUEUE_ELT_VALIDATE(elt);
 321                 new_tail = elt->prev; /* new_tail may point to queue if elt was the only element */
 322                 new_tail->next = que;
 323                 que->prev = new_tail;
 324                 __DEQUEUE_ELT_CLEANUP(elt);
 325         }
 326
 327         return elt;
 328 }
 329
 330 static __inline__ void
 331 remqueue(
 332         queue_entry_t   elt)
 333 {
 334         queue_entry_t   next_elt, prev_elt;
 335
 336         __QUEUE_ELT_VALIDATE(elt);
 337         next_elt = elt->next;
 338         prev_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
 339         next_elt->prev = prev_elt;
 340         prev_elt->next = next_elt;
 341         __DEQUEUE_ELT_CLEANUP(elt);
 342 }
 343
 344 static __inline__ void
 345 insque(
 346         queue_entry_t   entry,
 347         queue_entry_t   pred)
 348 {
 349         queue_entry_t   successor;
 350
 351         __QUEUE_ELT_VALIDATE(pred);
 352         successor = pred->next;
 353         entry->next = successor;
 354         entry->prev = pred;
 355         successor->prev = entry;
 356         pred->next = entry;
 357 }
 358
 359 static __inline__ void
 360 remque(
 361         queue_entry_t elt)
 362 {
 363         queue_entry_t   next_elt, prev_elt;
 364
 365         __QUEUE_ELT_VALIDATE(elt);
 366         next_elt = elt->next;
 367         prev_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
 368         next_elt->prev = prev_elt;
 369         prev_elt->next = next_elt;
 370         __DEQUEUE_ELT_CLEANUP(elt);
 371 }
 372
 373 /*
 374  *      Function:       re_queue_head
 375  *      Parameters:
 376  *              queue_t que       : queue onto which elt will be pre-pended
 377  *              queue_entry_t elt : element to re-queue
 378  *      Description:
 379  *              Remove elt from its current queue and put it onto the
 380  *              head of a new queue
 381  *      Note:
 382  *              This should only be used with Method 1 queue iteration (linkage chains)
 383  */
 384 static __inline__ void
 385 re_queue_head(queue_t que, queue_entry_t elt)
 386 {
 387         queue_entry_t   n_elt, p_elt;
 388
 389         __QUEUE_ELT_VALIDATE(elt);
 390         __QUEUE_ELT_VALIDATE((queue_entry_t)que);
 391
 392         /* remqueue */
 393         n_elt = elt->next;
 394         p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
 395         n_elt->prev = p_elt;
 396         p_elt->next = n_elt;
 397
 398         /* enqueue_head */
 399         n_elt = que->next;
 400         elt->next = n_elt;
 401         elt->prev = que;
 402         n_elt->prev = elt;
 403         que->next = elt;
 404 }
 405
 406 /*
 407  *      Function:       re_queue_tail
 408  *      Parameters:
 409  *              queue_t que       : queue onto which elt will be appended
 410  *              queue_entry_t elt : element to re-queue
 411  *      Description:
 412  *              Remove elt from its current queue and put it onto the
 413  *              end of a new queue
 414  *      Note:
 415  *              This should only be used with Method 1 queue iteration (linkage chains)
 416  */
 417 static __inline__ void
 418 re_queue_tail(queue_t que, queue_entry_t elt)
 419 {
 420         queue_entry_t   n_elt, p_elt;
 421
 422         __QUEUE_ELT_VALIDATE(elt);
 423         __QUEUE_ELT_VALIDATE((queue_entry_t)que);
 424
 425         /* remqueue */
 426         n_elt = elt->next;
 427         p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
 428         n_elt->prev = p_elt;
 429         p_elt->next = n_elt;
 430
 431         /* enqueue_tail */
 432         p_elt = que->prev;
 433         elt->next = que;
 434         elt->prev = p_elt;
 435         p_elt->next = elt;
 436         que->prev = elt;
 437 }
 438
 439 /*
 440  *      Macro:          qe_element
 441  *      Function:
 442  *              Convert a queue_entry_t to a queue element pointer.
 443  *              Get a pointer to the user-defined element containing
 444  *              a given queue_entry_t
 445  *      Header:
 446  *              <type> * qe_element(queue_entry_t qe, <type>, field)
 447  *                      qe      - queue entry to convert
 448  *                      <type>  - what's in the queue (e.g., struct some_data)
 449  *                      <field> - is the chain field in <type>
 450  *      Note:
 451  *              Do not use pointer types for <type>
 452  */
 453 #define qe_element(qe, type, field) __container_of(qe, type, field)
 454
 455 /*
 456  *      Macro:          qe_foreach
 457  *      Function:
 458  *              Iterate over each queue_entry_t structure.
 459  *              Generates a 'for' loop, setting 'qe' to
 460  *              each queue_entry_t in the queue.
 461  *      Header:
 462  *              qe_foreach(queue_entry_t qe, queue_t head)
 463  *                      qe   - iteration variable
 464  *                      head - pointer to queue_head_t (head of queue)
 465  *      Note:
 466  *              This should only be used with Method 1 queue iteration (linkage chains)
 467  */
 468 #define qe_foreach(qe, head) \
 469         for (qe = (head)->next; qe != (head); qe = (qe)->next)
 470
 471 /*
 472  *      Macro:          qe_foreach_safe
 473  *      Function:
 474  *              Safely iterate over each queue_entry_t structure.
 475  *
 476  *              Use this iterator macro if you plan to remove the
 477  *              queue_entry_t, qe, from the queue during the
 478  *              iteration.
 479  *      Header:
 480  *              qe_foreach_safe(queue_entry_t qe, queue_t head)
 481  *                      qe   - iteration variable
 482  *                      head - pointer to queue_head_t (head of queue)
 483  *      Note:
 484  *              This should only be used with Method 1 queue iteration (linkage chains)
 485  */
 486 #define qe_foreach_safe(qe, head) \
 487         for (queue_entry_t _ne = ((head)->next)->next, \
 488                  __ ## qe ## _unused_shadow __unused = (qe = (head)->next); \
 489              qe != (head); \
 490              qe = _ne, _ne = (qe)->next)
 491
 492 /*
 493  *      Macro:          qe_foreach_element
 494  *      Function:
 495  *              Iterate over each _element_ in a queue
 496  *              where each queue_entry_t points to another
 497  *              queue_entry_t, i.e., managed by the [de|en]queue_head/
 498  *              [de|en]queue_tail / remqueue / etc. function.
 499  *      Header:
 500  *              qe_foreach_element(<type> *elt, queue_t head, <field>)
 501  *                      elt     - iteration variable
 502  *                      <type>  - what's in the queue (e.g., struct some_data)
 503  *                      <field> - is the chain field in <type>
 504  *      Note:
 505  *              This should only be used with Method 1 queue iteration (linkage chains)
 506  */
 507 #define qe_foreach_element(elt, head, field) \
 508         for (elt = qe_element((head)->next, typeof(*(elt)), field); \
 509              &((elt)->field) != (head); \
 510              elt = qe_element((elt)->field.next, typeof(*(elt)), field))
 511
 512 /*
 513  *      Macro:          qe_foreach_element_safe
 514  *      Function:
 515  *              Safely iterate over each _element_ in a queue
 516  *              where each queue_entry_t points to another
 517  *              queue_entry_t, i.e., managed by the [de|en]queue_head/
 518  *              [de|en]queue_tail / remqueue / etc. function.
 519  *
 520  *              Use this iterator macro if you plan to remove the
 521  *              element, elt, from the queue during the iteration.
 522  *      Header:
 523  *              qe_foreach_element_safe(<type> *elt, queue_t head, <field>)
 524  *                      elt     - iteration variable
 525  *                      <type>  - what's in the queue (e.g., struct some_data)
 526  *                      <field> - is the chain field in <type>
 527  *      Note:
 528  *              This should only be used with Method 1 queue iteration (linkage chains)
 529  */
 530 #define qe_foreach_element_safe(elt, head, field) \
 531         for (typeof(*(elt)) *_nelt = qe_element(((head)->next)->next, typeof(*(elt)), field), \
 532              *__ ## elt ## _unused_shadow __unused = \
 533                  (elt = qe_element((head)->next, typeof(*(elt)), field)); \
 534              &((elt)->field) != (head); \
 535              elt = _nelt, _nelt = qe_element((elt)->field.next, typeof(*(elt)), field)) \
 536
 537 #ifdef XNU_KERNEL_PRIVATE
 538
 539 /* Dequeue an element from head, or return NULL if the queue is empty */
 540 #define qe_dequeue_head(head, type, field) ({ \
 541         queue_entry_t _tmp_entry = dequeue_head((head)); \
 542         type *_tmp_element = (type*) NULL; \
 543         if (_tmp_entry != (queue_entry_t) NULL) \
 544                 _tmp_element = qe_element(_tmp_entry, type, field); \
 545         _tmp_element; \
 546 })
 547
 548 /* Dequeue an element from tail, or return NULL if the queue is empty */
 549 #define qe_dequeue_tail(head, type, field) ({ \
 550         queue_entry_t _tmp_entry = dequeue_tail((head)); \
 551         type *_tmp_element = (type*) NULL; \
 552         if (_tmp_entry != (queue_entry_t) NULL) \
 553                 _tmp_element = qe_element(_tmp_entry, type, field); \
 554         _tmp_element; \
 555 })
 556
 557 /* Peek at the first element, or return NULL if the queue is empty */
 558 #define qe_queue_first(head, type, field) ({ \
 559         queue_entry_t _tmp_entry = queue_first((head)); \
 560         type *_tmp_element = (type*) NULL; \
 561         if (_tmp_entry != (queue_entry_t) head) \
 562                 _tmp_element = qe_element(_tmp_entry, type, field); \
 563         _tmp_element; \
 564 })
 565
 566 /* Peek at the last element, or return NULL if the queue is empty */
 567 #define qe_queue_last(head, type, field) ({ \
 568         queue_entry_t _tmp_entry = queue_last((head)); \
 569         type *_tmp_element = (type*) NULL; \
 570         if (_tmp_entry != (queue_entry_t) head) \
 571                 _tmp_element = qe_element(_tmp_entry, type, field); \
 572         _tmp_element; \
 573 })
 574
 575 #endif /* XNU_KERNEL_PRIVATE */
 576
 577 /*
 578  *      Macro:          queue_init
 579  *      Function:
 580  *              Initialize the given queue.
 581  *      Header:
 582  *              void queue_init(q)
 583  *                      queue_t         q;      \* MODIFIED *\
 584  */
 585 #define queue_init(q)   \
 586 MACRO_BEGIN             \
 587         (q)->next = (q);\
 588         (q)->prev = (q);\
 589 MACRO_END
 590
 591 /*
 592  *      Macro:          queue_head_init
 593  *      Function:
 594  *              Initialize the given queue head
 595  *      Header:
 596  *              void queue_head_init(q)
 597  *                      queue_head_t    q;      \* MODIFIED *\
 598  */
 599 #define queue_head_init(q) \
 600         queue_init(&(q))
 601
 602 /*
 603  *      Macro:          queue_chain_init
 604  *      Function:
 605  *              Initialize the given queue chain element
 606  *      Header:
 607  *              void queue_chain_init(q)
 608  *                      queue_chain_t   q;      \* MODIFIED *\
 609  */
 610 #define queue_chain_init(q) \
 611         queue_init(&(q))
 612
 613 /*
 614  *      Macro:          queue_first
 615  *      Function:
 616  *              Returns the first entry in the queue,
 617  *      Header:
 618  *              queue_entry_t queue_first(q)
 619  *                      queue_t q;              \* IN *\
 620  */
 621 #define queue_first(q)  ((q)->next)
 622
 623 /*
 624  *      Macro:          queue_next
 625  *      Function:
 626  *              Returns the entry after an item in the queue.
 627  *      Header:
 628  *              queue_entry_t queue_next(qc)
 629  *                      queue_t qc;
 630  */
 631 #define queue_next(qc)  ((qc)->next)
 632
 633 /*
 634  *      Macro:          queue_last
 635  *      Function:
 636  *              Returns the last entry in the queue.
 637  *      Header:
 638  *              queue_entry_t queue_last(q)
 639  *                      queue_t q;              \* IN *\
 640  */
 641 #define queue_last(q)   ((q)->prev)
 642
 643 /*
 644  *      Macro:          queue_prev
 645  *      Function:
 646  *              Returns the entry before an item in the queue.
 647  *      Header:
 648  *              queue_entry_t queue_prev(qc)
 649  *                      queue_t qc;
 650  */
 651 #define queue_prev(qc)  ((qc)->prev)
 652
 653 /*
 654  *      Macro:          queue_end
 655  *      Function:
 656  *              Tests whether a new entry is really the end of
 657  *              the queue.
 658  *      Header:
 659  *              boolean_t queue_end(q, qe)
 660  *                      queue_t q;
 661  *                      queue_entry_t qe;
 662  */
 663 #define queue_end(q, qe)        ((q) == (qe))
 664
 665 /*
 666  *      Macro:          queue_empty
 667  *      Function:
 668  *              Tests whether a queue is empty.
 669  *      Header:
 670  *              boolean_t queue_empty(q)
 671  *                      queue_t q;
 672  */
 673 #define queue_empty(q)          queue_end((q), queue_first(q))
 674
 675 /*
 676  *      Function:       movqueue
 677  *      Parameters:
 678  *              queue_t _old : head of a queue whose items will be moved
 679  *              queue_t _new : new queue head onto which items will be moved
 680  *      Description:
 681  *              Rebase queue items in _old onto _new then re-initialize
 682  *              the _old object to an empty queue.
 683  *              Equivalent to the queue_new_head Method 2 macro
 684  *      Note:
 685  *              Similar to the queue_new_head macro, this macros is intented
 686  *              to function as an initializer method for '_new' and thus may
 687  *              leak any list items that happen to be on the '_new' list.
 688  *              This should only be used with Method 1 queue iteration (linkage chains)
 689  */
 690 static __inline__ void
 691 movqueue(queue_t _old, queue_t _new)
 692 {
 693         queue_entry_t   next_elt, prev_elt;
 694
 695         __QUEUE_ELT_VALIDATE((queue_entry_t)_old);
 696
 697         if (queue_empty(_old)) {
 698                 queue_init(_new);
 699                 return;
 700         }
 701
 702         /*
 703          * move the queue at _old to _new
 704          * and re-initialize _old
 705          */
 706         next_elt = _old->next;
 707         prev_elt = _old->prev;
 708
 709         _new->next = next_elt;
 710         _new->prev = prev_elt;
 711         next_elt->prev = _new;
 712         prev_elt->next = _new;
 713
 714         queue_init(_old);
 715 }
 716
 717 /*----------------------------------------------------------------*/
 718 /*
 719  * Macros that operate on generic structures.  The queue
 720  * chain may be at any location within the structure, and there
 721  * may be more than one chain.
 722  */
 723
 724 /*
 725  *      Macro:          queue_enter
 726  *      Function:
 727  *              Insert a new element at the tail of the queue.
 728  *      Header:
 729  *              void queue_enter(q, elt, type, field)
 730  *                      queue_t q;
 731  *                      <type> elt;
 732  *                      <type> is what's in our queue
 733  *                      <field> is the chain field in (*<type>)
 734  *      Note:
 735  *              This should only be used with Method 2 queue iteration (element chains)
 736  *
 737  *              We insert a compiler barrier after setting the fields in the element
 738  *              to ensure that the element is updated before being added to the queue,
 739  *              which is especially important because stackshot, which operates from
 740  *              debugger context, iterates several queues that use this macro (the tasks
 741  *              lists and threads lists) without locks. Without this barrier, the
 742  *              compiler may re-order the instructions for this macro in a way that
 743  *              could cause stackshot to trip over an inconsistent queue during
 744  *              iteration.
 745  */
 746 #define queue_enter(head, elt, type, field)                     \
 747 MACRO_BEGIN                                                     \
 748         queue_entry_t __prev;                                   \
 749                                                                 \
 750         __prev = (head)->prev;                                  \
 751         (elt)->field.prev = __prev;                             \
 752         (elt)->field.next = head;                               \
 753         __compiler_barrier();                                   \
 754         if ((head) == __prev) {                                 \
 755                 (head)->next = (queue_entry_t) (elt);           \
 756         }                                                       \
 757         else {                                                  \
 758                 ((type)(void *)__prev)->field.next =            \
 759                         (queue_entry_t)(elt);                   \
 760         }                                                       \
 761         (head)->prev = (queue_entry_t) elt;                     \
 762 MACRO_END
 763
 764 /*
 765  *      Macro:          queue_enter_first
 766  *      Function:
 767  *              Insert a new element at the head of the queue.
 768  *      Header:
 769  *              void queue_enter_first(q, elt, type, field)
 770  *                      queue_t q;
 771  *                      <type> elt;
 772  *                      <type> is what's in our queue
 773  *                      <field> is the chain field in (*<type>)
 774  *      Note:
 775  *              This should only be used with Method 2 queue iteration (element chains)
 776  */
 777 #define queue_enter_first(head, elt, type, field)               \
 778 MACRO_BEGIN                                                     \
 779         queue_entry_t __next;                                   \
 780                                                                 \
 781         __next = (head)->next;                                  \
 782         if ((head) == __next) {                                 \
 783                 (head)->prev = (queue_entry_t) (elt);           \
 784         }                                                       \
 785         else {                                                  \
 786                 ((type)(void *)__next)->field.prev =            \
 787                         (queue_entry_t)(elt);                   \
 788         }                                                       \
 789         (elt)->field.next = __next;                             \
 790         (elt)->field.prev = head;                               \
 791         (head)->next = (queue_entry_t) elt;                     \
 792 MACRO_END
 793
 794 /*
 795  *      Macro:          queue_insert_before
 796  *      Function:
 797  *              Insert a new element before a given element.
 798  *      Header:
 799  *              void queue_insert_before(q, elt, cur, type, field)
 800  *                      queue_t q;
 801  *                      <type> elt;
 802  *                      <type> cur;
 803  *                      <type> is what's in our queue
 804  *                      <field> is the chain field in (*<type>)
 805  *      Note:
 806  *              This should only be used with Method 2 queue iteration (element chains)
 807  */
 808 #define queue_insert_before(head, elt, cur, type, field)                \
 809 MACRO_BEGIN                                                             \
 810         queue_entry_t __prev;                                           \
 811                                                                         \
 812         if ((head) == (queue_entry_t)(cur)) {                           \
 813                 (elt)->field.next = (head);                             \
 814                 if ((head)->next == (head)) {   /* only element */      \
 815                         (elt)->field.prev = (head);                     \
 816                         (head)->next = (queue_entry_t)(elt);            \
 817                 } else {                        /* last element */      \
 818                         __prev = (elt)->field.prev = (head)->prev;      \
 819                         ((type)(void *)__prev)->field.next =            \
 820                                 (queue_entry_t)(elt);                   \
 821                 }                                                       \
 822                 (head)->prev = (queue_entry_t)(elt);                    \
 823         } else {                                                        \
 824                 (elt)->field.next = (queue_entry_t)(cur);               \
 825                 if ((head)->next == (queue_entry_t)(cur)) {             \
 826         /* first element */     \
 827                         (elt)->field.prev = (head);                     \
 828                         (head)->next = (queue_entry_t)(elt);            \
 829                 } else {                        /* middle element */    \
 830                         __prev = (elt)->field.prev = (cur)->field.prev; \
 831                         ((type)(void *)__prev)->field.next =            \
 832                                 (queue_entry_t)(elt);                   \
 833                 }                                                       \
 834                 (cur)->field.prev = (queue_entry_t)(elt);               \
 835         }                                                               \
 836 MACRO_END
 837
 838 /*
 839  *      Macro:          queue_insert_after
 840  *      Function:
 841  *              Insert a new element after a given element.
 842  *      Header:
 843  *              void queue_insert_after(q, elt, cur, type, field)
 844  *                      queue_t q;
 845  *                      <type> elt;
 846  *                      <type> cur;
 847  *                      <type> is what's in our queue
 848  *                      <field> is the chain field in (*<type>)
 849  *      Note:
 850  *              This should only be used with Method 2 queue iteration (element chains)
 851  */
 852 #define queue_insert_after(head, elt, cur, type, field)                 \
 853 MACRO_BEGIN                                                             \
 854         queue_entry_t __next;                                           \
 855                                                                         \
 856         if ((head) == (queue_entry_t)(cur)) {                           \
 857                 (elt)->field.prev = (head);                             \
 858                 if ((head)->next == (head)) {   /* only element */      \
 859                         (elt)->field.next = (head);                     \
 860                         (head)->prev = (queue_entry_t)(elt);            \
 861                 } else {                        /* first element */     \
 862                         __next = (elt)->field.next = (head)->next;      \
 863                         ((type)(void *)__next)->field.prev =            \
 864                                 (queue_entry_t)(elt);                   \
 865                 }                                                       \
 866                 (head)->next = (queue_entry_t)(elt);                    \
 867         } else {                                                        \
 868                 (elt)->field.prev = (queue_entry_t)(cur);               \
 869                 if ((head)->prev == (queue_entry_t)(cur)) {             \
 870         /* last element */      \
 871                         (elt)->field.next = (head);                     \
 872                         (head)->prev = (queue_entry_t)(elt);            \
 873                 } else {                        /* middle element */    \
 874                         __next = (elt)->field.next = (cur)->field.next; \
 875                         ((type)(void *)__next)->field.prev =            \
 876                                 (queue_entry_t)(elt);                   \
 877                 }                                                       \
 878                 (cur)->field.next = (queue_entry_t)(elt);               \
 879         }                                                               \
 880 MACRO_END
 881
 882 /*
 883  *      Macro:          queue_field [internal use only]
 884  *      Function:
 885  *              Find the queue_chain_t (or queue_t) for the
 886  *              given element (thing) in the given queue (head)
 887  *      Note:
 888  *              This should only be used with Method 2 queue iteration (element chains)
 889  */
 890 #define queue_field(head, thing, type, field)                   \
 891                 (((head) == (thing)) ? (head) : &((type)(void *)(thing))->field)
 892
 893 /*
 894  *      Macro:          queue_remove
 895  *      Function:
 896  *              Remove an arbitrary item from the queue.
 897  *      Header:
 898  *              void queue_remove(q, qe, type, field)
 899  *                      arguments as in queue_enter
 900  *      Note:
 901  *              This should only be used with Method 2 queue iteration (element chains)
 902  */
 903 #define queue_remove(head, elt, type, field)                    \
 904 MACRO_BEGIN                                                     \
 905         queue_entry_t   __next, __prev;                         \
 906                                                                 \
 907         __next = (elt)->field.next;                             \
 908         __prev = (elt)->field.prev;                             \
 909                                                                 \
 910         if ((head) == __next)                                   \
 911                 (head)->prev = __prev;                          \
 912         else                                                    \
 913                 ((type)(void *)__next)->field.prev = __prev;    \
 914                                                                 \
 915         if ((head) == __prev)                                   \
 916                 (head)->next = __next;                          \
 917         else                                                    \
 918                 ((type)(void *)__prev)->field.next = __next;    \
 919                                                                 \
 920         (elt)->field.next = NULL;                               \
 921         (elt)->field.prev = NULL;                               \
 922 MACRO_END
 923
 924 /*
 925  *      Macro:          queue_remove_first
 926  *      Function:
 927  *              Remove and return the entry at the head of
 928  *              the queue.
 929  *      Header:
 930  *              queue_remove_first(head, entry, type, field)
 931  *              entry is returned by reference
 932  *      Note:
 933  *              This should only be used with Method 2 queue iteration (element chains)
 934  */
 935 #define queue_remove_first(head, entry, type, field)            \
 936 MACRO_BEGIN                                                     \
 937         queue_entry_t   __next;                                 \
 938                                                                 \
 939         (entry) = (type)(void *) ((head)->next);                \
 940         __next = (entry)->field.next;                           \
 941                                                                 \
 942         if ((head) == __next)                                   \
 943                 (head)->prev = (head);                          \
 944         else                                                    \
 945                 ((type)(void *)(__next))->field.prev = (head);  \
 946         (head)->next = __next;                                  \
 947                                                                 \
 948         (entry)->field.next = NULL;                             \
 949         (entry)->field.prev = NULL;                             \
 950 MACRO_END
 951
 952 /*
 953  *      Macro:          queue_remove_last
 954  *      Function:
 955  *              Remove and return the entry at the tail of
 956  *              the queue.
 957  *      Header:
 958  *              queue_remove_last(head, entry, type, field)
 959  *              entry is returned by reference
 960  *      Note:
 961  *              This should only be used with Method 2 queue iteration (element chains)
 962  */
 963 #define queue_remove_last(head, entry, type, field)             \
 964 MACRO_BEGIN                                                     \
 965         queue_entry_t   __prev;                                 \
 966                                                                 \
 967         (entry) = (type)(void *) ((head)->prev);                \
 968         __prev = (entry)->field.prev;                           \
 969                                                                 \
 970         if ((head) == __prev)                                   \
 971                 (head)->next = (head);                          \
 972         else                                                    \
 973                 ((type)(void *)(__prev))->field.next = (head);  \
 974         (head)->prev = __prev;                                  \
 975                                                                 \
 976         (entry)->field.next = NULL;                             \
 977         (entry)->field.prev = NULL;                             \
 978 MACRO_END
 979
 980 /*
 981  *      Macro:          queue_assign
 982  *      Note:
 983  *              This should only be used with Method 2 queue iteration (element chains)
 984  */
 985 #define queue_assign(to, from, type, field)                     \
 986 MACRO_BEGIN                                                     \
 987         ((type)(void *)((from)->prev))->field.next = (to);      \
 988         ((type)(void *)((from)->next))->field.prev = (to);      \
 989         *to = *from;                                            \
 990 MACRO_END
 991
 992 /*
 993  *      Macro:          queue_new_head
 994  *      Function:
 995  *              rebase old queue to new queue head
 996  *      Header:
 997  *              queue_new_head(old, new, type, field)
 998  *                      queue_t old;
 999  *                      queue_t new;
1000  *                      <type> is what's in our queue
1001  *                      <field> is the chain field in (*<type>)
1002  *      Note:
1003  *              This should only be used with Method 2 queue iteration (element chains)
1004  */
1005 #define queue_new_head(old, new, type, field)                   \
1006 MACRO_BEGIN                                                     \
1007         if (!queue_empty(old)) {                                \
1008                 *(new) = *(old);                                \
1009                 ((type)(void *)((new)->next))->field.prev =     \
1010                         (new);                                  \
1011                 ((type)(void *)((new)->prev))->field.next =     \
1012                         (new);                                  \
1013         } else {                                                \
1014                 queue_init(new);                                \
1015         }                                                       \
1016 MACRO_END
1017
1018 /*
1019  *      Macro:          queue_iterate
1020  *      Function:
1021  *              iterate over each item in the queue.
1022  *              Generates a 'for' loop, setting elt to
1023  *              each item in turn (by reference).
1024  *      Header:
1025  *              queue_iterate(q, elt, type, field)
1026  *                      queue_t q;
1027  *                      <type> elt;
1028  *                      <type> is what's in our queue
1029  *                      <field> is the chain field in (*<type>)
1030  *      Note:
1031  *              This should only be used with Method 2 queue iteration (element chains)
1032  */
1033 #define queue_iterate(head, elt, type, field)                   \
1034         for ((elt) = (type)(void *) queue_first(head);          \
1035              !queue_end((head), (queue_entry_t)(elt));          \
1036              (elt) = (type)(void *) queue_next(&(elt)->field))
1037
1038
1039 __END_DECLS
1040
1041 #endif  /* _KERN_QUEUE_H_ */