Loading...
--- xnu/xnu-12377.101.15/iokit/DriverKit/queue_implementation.h
+++ /dev/null
@@ -1,1165 +0,0 @@
-/*
- * Copyright (c) 2000-2009 Apple Inc. All rights reserved.
- *
- * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
- *
- * This file contains Original Code and/or Modifications of Original Code
- * as defined in and that are subject to the Apple Public Source License
- * Version 2.0 (the 'License'). You may not use this file except in
- * compliance with the License. The rights granted to you under the License
- * may not be used to create, or enable the creation or redistribution of,
- * unlawful or unlicensed copies of an Apple operating system, or to
- * circumvent, violate, or enable the circumvention or violation of, any
- * terms of an Apple operating system software license agreement.
- *
- * Please obtain a copy of the License at
- * http://www.opensource.apple.com/apsl/ and read it before using this file.
- *
- * The Original Code and all software distributed under the License are
- * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
- * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
- * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
- * Please see the License for the specific language governing rights and
- * limitations under the License.
- *
- * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
- */
-/*
- * @OSF_COPYRIGHT@
- */
-/*
- * Mach Operating System
- * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
- * All Rights Reserved.
- *
- * Permission to use, copy, modify and distribute this software and its
- * documentation is hereby granted, provided that both the copyright
- * notice and this permission notice appear in all copies of the
- * software, derivative works or modified versions, and any portions
- * thereof, and that both notices appear in supporting documentation.
- *
- * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
- * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
- * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
- *
- * Carnegie Mellon requests users of this software to return to
- *
- * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
- * School of Computer Science
- * Carnegie Mellon University
- * Pittsburgh PA 15213-3890
- *
- * any improvements or extensions that they make and grant Carnegie Mellon rights
- * to redistribute these changes.
- */
-/*
- */
-/*
- * File: queue.h
- * Author: Avadis Tevanian, Jr.
- * Date: 1985
- *
- * Type definitions for generic queues.
- *
- */
-
-#ifndef _KERN_QUEUE_H_
-#define _KERN_QUEUE_H_
-
-#if DRIVERKIT_FRAMEWORK_INCLUDE
-#include <DriverKit/macro_help.h>
-#else
-#include <mach/mach_types.h>
-#include <kern/macro_help.h>
-#endif /* DRIVERKIT_FRAMEWORK_INCLUDE */
-
-#include <sys/cdefs.h>
-#include <string.h>
-
-__BEGIN_DECLS
-
-/*
- * Queue Management APIs
- *
- * There are currently two subtly different methods of maintaining
- * a queue of objects. Both APIs are contained in this file, and
- * unfortunately overlap.
- * (there is also a third way maintained in bsd/sys/queue.h)
- *
- * Both methods use a common queue head and linkage pattern:
- * The head of a queue is declared as:
- * queue_head_t q_head;
- *
- * Elements in this queue are chained together using
- * struct queue_entry objects embedded within a structure:
- * struct some_data {
- * int field1;
- * int field2;
- * ...
- * queue_chain_t link;
- * ...
- * int last_field;
- * };
- * struct some_data is referred to as the queue "element."
- * (note that queue_chain_t is typedef'd to struct queue_entry)
- *
- * IMPORTANT: The two queue iteration methods described below are not
- * compatible with one another. You must choose one and be careful
- * to use only the supported APIs for that method.
- *
- * Method 1: chaining of queue_chain_t (linkage chains)
- * This method uses the next and prev pointers of the struct queue_entry
- * linkage object embedded in a queue element to point to the next or
- * previous queue_entry structure in the chain. The head of the queue
- * (the queue_head_t object) will point to the first and last
- * struct queue_entry object, and both the next and prev pointer will
- * point back to the head if the queue is empty.
- *
- * This method is the most flexible method of chaining objects together
- * as it allows multiple chains through a given object, by embedding
- * multiple queue_chain_t objects in the structure, while simultaneously
- * providing fast removal and insertion into the queue using only
- * struct queue_entry object pointers.
- *
- * ++ Valid APIs for this style queue ++
- * -------------------------------------
- * [C] queue_init
- * [C] queue_first
- * [C] queue_next
- * [C] queue_last
- * [C] queue_prev
- * [C] queue_end
- * [C] queue_empty
- *
- * [1] enqueue
- * [1] dequeue
- * [1] enqueue_head
- * [1] enqueue_tail
- * [1] dequeue_head
- * [1] dequeue_tail
- * [1] remqueue
- * [1] insque
- * [1] remque
- * [1] re_queue_head
- * [1] re_queue_tail
- * [1] movqueue
- * [1] qe_element
- * [1] qe_foreach
- * [1] qe_foreach_safe
- * [1] qe_foreach_element
- * [1] qe_foreach_element_safe
- *
- * Method 2: chaining of elements (element chains)
- * This method uses the next and prev pointers of the struct queue_entry
- * linkage object embedded in a queue element to point to the next or
- * previous queue element (not another queue_entry). The head of the
- * queue will point to the first and last queue element (struct some_data
- * from the above example) NOT the embedded queue_entry structure. The
- * first queue element will have a prev pointer that points to the
- * queue_head_t, and the last queue element will have a next pointer
- * that points to the queue_head_t.
- *
- * This method requires knowledge of the queue_head_t of the queue on
- * which an element resides in order to remove the element. Iterating
- * through the elements of the queue is also more cumbersome because
- * a check against the head pointer plus a cast then offset operation
- * must be performed at each step of the iteration.
- *
- * ++ Valid APIs for this style queue ++
- * -------------------------------------
- * [C] queue_init
- * [C] queue_first
- * [C] queue_next
- * [C] queue_last
- * [C] queue_prev
- * [C] queue_end
- * [C] queue_empty
- *
- * [2] queue_enter
- * [2] queue_enter_first
- * [2] queue_insert_before
- * [2] queue_insert_after
- * [2] queue_field
- * [2] queue_remove
- * [2] queue_remove_first
- * [2] queue_remove_last
- * [2] queue_assign
- * [2] queue_new_head
- * [2] queue_iterate
- *
- * Legend:
- * [C] -> API common to both methods
- * [1] -> API used only in method 1 (linkage chains)
- * [2] -> API used only in method 2 (element chains)
- */
-
-/*
- * A generic doubly-linked list (queue).
- */
-
-struct queue_entry {
- struct queue_entry *next; /* next element */
- struct queue_entry *prev; /* previous element */
-};
-
-typedef struct queue_entry *queue_t;
-typedef struct queue_entry queue_head_t;
-typedef struct queue_entry queue_chain_t;
-typedef struct queue_entry *queue_entry_t;
-
-#if defined(KERNEL_PRIVATE) || DRIVERKIT_FRAMEWORK_INCLUDE
-
-#if KERNEL_PRIVATE
-#define __queue_element_linkage_invalid(e) \
- ml_fatal_trap_invalid_list_linkage((unsigned long)(e))
-#else
-#define __queue_element_linkage_invalid(e) \
- __builtin_trap()
-#endif
-
-static inline void
-__QUEUE_ELT_VALIDATE(queue_entry_t elt)
-{
- if (elt->prev->next != elt || elt->next->prev != elt) {
- __queue_element_linkage_invalid(elt);
- }
-}
-
-static inline queue_entry_t
-__QUEUE_ELT_VALIDATE_NEXT(queue_entry_t elt)
-{
- queue_entry_t __next = elt->next;
-
- if (__next->prev != elt) {
- __queue_element_linkage_invalid(elt);
- }
-
- return __next;
-}
-
-static inline queue_entry_t
-__QUEUE_ELT_VALIDATE_PREV(queue_entry_t elt)
-{
- queue_entry_t __prev = elt->prev;
-
- if (__prev->next != elt) {
- __queue_element_linkage_invalid(elt);
- }
-
- return __prev;
-}
-
-static inline void
-__DEQUEUE_ELT_CLEANUP(queue_entry_t elt)
-{
- elt->next = elt->prev = (queue_entry_t)NULL;
-}
-#else
-#define __QUEUE_ELT_VALIDATE(elt) ((void)0)
-#define __QUEUE_ELT_VALIDATE_NEXT(elt) ((elt)->next)
-#define __QUEUE_ELT_VALIDATE_PREV(elt) ((elt)->prev)
-#define __DEQUEUE_ELT_CLEANUP(elt) ((void)0)
-#define __queue_element_linkage_invalid(e) ((void)0)
-#endif /* !(XNU_KERNEL_PRIVATE || DRIVERKIT_FRAMEWORK_INCLUDE)*/
-
-/*
- * enqueue puts "elt" on the "queue".
- * dequeue returns the first element in the "queue".
- * remqueue removes the specified "elt" from its queue.
- */
-
-#if !DRIVERKIT_FRAMEWORK_INCLUDE
-#define enqueue(queue, elt) enqueue_tail(queue, elt)
-#define dequeue(queue) dequeue_head(queue)
-#endif
-
-static __inline__ void
-enqueue_head(
- queue_t que,
- queue_entry_t elt)
-{
- queue_entry_t old_head;
-
- old_head = __QUEUE_ELT_VALIDATE_NEXT(que);
- elt->next = old_head;
- elt->prev = que;
- old_head->prev = elt;
- que->next = elt;
-}
-
-static __inline__ void
-enqueue_tail(
- queue_t que,
- queue_entry_t elt)
-{
- queue_entry_t old_tail;
-
- old_tail = __QUEUE_ELT_VALIDATE_PREV(que);
- elt->next = que;
- elt->prev = old_tail;
- old_tail->next = elt;
- que->prev = elt;
-}
-
-static __inline__ queue_entry_t
-dequeue_head(
- queue_t que)
-{
- queue_entry_t elt = (queue_entry_t)NULL;
- queue_entry_t new_head;
-
- if (que->next != que) {
- elt = que->next;
- __QUEUE_ELT_VALIDATE(elt);
- new_head = elt->next; /* new_head may point to que if elt was the only element */
- new_head->prev = que;
- que->next = new_head;
- __DEQUEUE_ELT_CLEANUP(elt);
- }
-
- return elt;
-}
-
-static __inline__ queue_entry_t
-dequeue_tail(
- queue_t que)
-{
- queue_entry_t elt = (queue_entry_t)NULL;
- queue_entry_t new_tail;
-
- if (que->prev != que) {
- elt = que->prev;
- __QUEUE_ELT_VALIDATE(elt);
- new_tail = elt->prev; /* new_tail may point to queue if elt was the only element */
- new_tail->next = que;
- que->prev = new_tail;
- __DEQUEUE_ELT_CLEANUP(elt);
- }
-
- return elt;
-}
-
-static __inline__ void
-remqueue(
- queue_entry_t elt)
-{
- queue_entry_t next_elt, prev_elt;
-
- __QUEUE_ELT_VALIDATE(elt);
- next_elt = elt->next;
- prev_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
- next_elt->prev = prev_elt;
- prev_elt->next = next_elt;
- __DEQUEUE_ELT_CLEANUP(elt);
-}
-
-static __inline__ void
-insque(
- queue_entry_t entry,
- queue_entry_t pred)
-{
- queue_entry_t successor;
-
- successor = __QUEUE_ELT_VALIDATE_NEXT(pred);
- entry->next = successor;
- entry->prev = pred;
- successor->prev = entry;
- pred->next = entry;
-}
-
-static __inline__ void
-remque(
- queue_entry_t elt)
-{
- remqueue(elt);
-}
-
-/*
- * Function: re_queue_head
- * Parameters:
- * queue_t que : queue onto which elt will be pre-pended
- * queue_entry_t elt : element to re-queue
- * Description:
- * Remove elt from its current queue and put it onto the
- * head of a new queue
- * Note:
- * This should only be used with Method 1 queue iteration (linkage chains)
- */
-static __inline__ void
-re_queue_head(queue_t que, queue_entry_t elt)
-{
- queue_entry_t n_elt, p_elt;
-
- __QUEUE_ELT_VALIDATE(elt);
- __QUEUE_ELT_VALIDATE((queue_entry_t)que);
-
- /* remqueue */
- n_elt = elt->next;
- p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
- n_elt->prev = p_elt;
- p_elt->next = n_elt;
-
- /* enqueue_head */
- n_elt = que->next;
- elt->next = n_elt;
- elt->prev = que;
- n_elt->prev = elt;
- que->next = elt;
-}
-
-/*
- * Function: re_queue_tail
- * Parameters:
- * queue_t que : queue onto which elt will be appended
- * queue_entry_t elt : element to re-queue
- * Description:
- * Remove elt from its current queue and put it onto the
- * end of a new queue
- * Note:
- * This should only be used with Method 1 queue iteration (linkage chains)
- */
-static __inline__ void
-re_queue_tail(queue_t que, queue_entry_t elt)
-{
- queue_entry_t n_elt, p_elt;
-
- __QUEUE_ELT_VALIDATE(elt);
- __QUEUE_ELT_VALIDATE((queue_entry_t)que);
-
- /* remqueue */
- n_elt = elt->next;
- p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
- n_elt->prev = p_elt;
- p_elt->next = n_elt;
-
- /* enqueue_tail */
- p_elt = que->prev;
- elt->next = que;
- elt->prev = p_elt;
- p_elt->next = elt;
- que->prev = elt;
-}
-
-/*
- * Macro: qe_element
- * Function:
- * Convert a queue_entry_t to a queue element pointer.
- * Get a pointer to the user-defined element containing
- * a given queue_entry_t
- * Header:
- * <type> * qe_element(queue_entry_t qe, <type>, field)
- * qe - queue entry to convert
- * <type> - what's in the queue (e.g., struct some_data)
- * <field> - is the chain field in <type>
- * Note:
- * Do not use pointer types for <type>
- */
-#define qe_element(qe, type, field) __container_of(qe, type, field)
-
-/*
- * Macro: qe_foreach
- * Function:
- * Iterate over each queue_entry_t structure.
- * Generates a 'for' loop, setting 'qe' to
- * each queue_entry_t in the queue.
- * Header:
- * qe_foreach(queue_entry_t qe, queue_t head)
- * qe - iteration variable
- * head - pointer to queue_head_t (head of queue)
- * Note:
- * This should only be used with Method 1 queue iteration (linkage chains)
- */
-#define qe_foreach(qe, head) \
- for (qe = (head)->next; qe != (head); qe = (qe)->next)
-
-/*
- * Macro: qe_foreach_safe
- * Function:
- * Safely iterate over each queue_entry_t structure.
- *
- * Use this iterator macro if you plan to remove the
- * queue_entry_t, qe, from the queue during the
- * iteration.
- * Header:
- * qe_foreach_safe(queue_entry_t qe, queue_t head)
- * qe - iteration variable
- * head - pointer to queue_head_t (head of queue)
- * Note:
- * This should only be used with Method 1 queue iteration (linkage chains)
- */
-#define qe_foreach_safe(qe, head) \
- for (queue_entry_t _ne = ((head)->next)->next, \
- __ ## qe ## _unused_shadow __unused = (qe = (head)->next); \
- qe != (head); \
- qe = _ne, _ne = (qe)->next)
-
-/*
- * Macro: qe_foreach_element
- * Function:
- * Iterate over each _element_ in a queue
- * where each queue_entry_t points to another
- * queue_entry_t, i.e., managed by the [de|en]queue_head/
- * [de|en]queue_tail / remqueue / etc. function.
- * Header:
- * qe_foreach_element(<type> *elt, queue_t head, <field>)
- * elt - iteration variable
- * <type> - what's in the queue (e.g., struct some_data)
- * <field> - is the chain field in <type>
- * Note:
- * This should only be used with Method 1 queue iteration (linkage chains)
- */
-#define qe_foreach_element(elt, head, field) \
- for (elt = qe_element((head)->next, typeof(*(elt)), field); \
- &((elt)->field) != (head); \
- elt = qe_element((elt)->field.next, typeof(*(elt)), field))
-
-/*
- * Macro: qe_foreach_element_safe
- * Function:
- * Safely iterate over each _element_ in a queue
- * where each queue_entry_t points to another
- * queue_entry_t, i.e., managed by the [de|en]queue_head/
- * [de|en]queue_tail / remqueue / etc. function.
- *
- * Use this iterator macro if you plan to remove the
- * element, elt, from the queue during the iteration.
- * Header:
- * qe_foreach_element_safe(<type> *elt, queue_t head, <field>)
- * elt - iteration variable
- * <type> - what's in the queue (e.g., struct some_data)
- * <field> - is the chain field in <type>
- * Note:
- * This should only be used with Method 1 queue iteration (linkage chains)
- */
-#define qe_foreach_element_safe(elt, head, field) \
- for (typeof(*(elt)) *_nelt = qe_element(((head)->next)->next, typeof(*(elt)), field), \
- *__ ## elt ## _unused_shadow __unused = \
- (elt = qe_element((head)->next, typeof(*(elt)), field)); \
- &((elt)->field) != (head); \
- elt = _nelt, _nelt = qe_element((elt)->field.next, typeof(*(elt)), field)) \
-
-#if (defined(XNU_KERNEL_PRIVATE) || SCHED_TEST_HARNESS)
-
-/* Dequeue an element from head, or return NULL if the queue is empty */
-#define qe_dequeue_head(head, type, field) ({ \
- queue_entry_t _tmp_entry = dequeue_head((head)); \
- type *_tmp_element = (type*) NULL; \
- if (_tmp_entry != (queue_entry_t) NULL) \
- _tmp_element = qe_element(_tmp_entry, type, field); \
- _tmp_element; \
-})
-
-/* Dequeue an element from tail, or return NULL if the queue is empty */
-#define qe_dequeue_tail(head, type, field) ({ \
- queue_entry_t _tmp_entry = dequeue_tail((head)); \
- type *_tmp_element = (type*) NULL; \
- if (_tmp_entry != (queue_entry_t) NULL) \
- _tmp_element = qe_element(_tmp_entry, type, field); \
- _tmp_element; \
-})
-
-/* Peek at the first element, or return NULL if the queue is empty */
-#define qe_queue_first(head, type, field) ({ \
- queue_entry_t _tmp_entry = queue_first((head)); \
- type *_tmp_element = (type*) NULL; \
- if (_tmp_entry != (queue_entry_t) head) \
- _tmp_element = qe_element(_tmp_entry, type, field); \
- _tmp_element; \
-})
-
-/* Peek at the last element, or return NULL if the queue is empty */
-#define qe_queue_last(head, type, field) ({ \
- queue_entry_t _tmp_entry = queue_last((head)); \
- type *_tmp_element = (type*) NULL; \
- if (_tmp_entry != (queue_entry_t) head) \
- _tmp_element = qe_element(_tmp_entry, type, field); \
- _tmp_element; \
-})
-
-/* Peek at the next element, or return NULL if the next element is head (indicating queue_end) */
-#define qe_queue_next(head, element, type, field) ({ \
- queue_entry_t _tmp_entry = queue_next(&(element)->field); \
- type *_tmp_element = (type*) NULL; \
- if (_tmp_entry != (queue_entry_t) head) \
- _tmp_element = qe_element(_tmp_entry, type, field); \
- _tmp_element; \
-})
-
-/* Peek at the prev element, or return NULL if the prev element is head (indicating queue_end) */
-#define qe_queue_prev(head, element, type, field) ({ \
- queue_entry_t _tmp_entry = queue_prev(&(element)->field); \
- type *_tmp_element = (type*) NULL; \
- if (_tmp_entry != (queue_entry_t) head) \
- _tmp_element = qe_element(_tmp_entry, type, field); \
- _tmp_element; \
-})
-
-#endif /* XNU_KERNEL_PRIVATE || SCHED_TEST_HARNESS */
-
-/*
- * Macro: QUEUE_HEAD_INITIALIZER()
- * Function:
- * Static queue head initializer
- */
-#define QUEUE_HEAD_INITIALIZER(name) \
- { &name, &name }
-
-/*
- * Macro: queue_init
- * Function:
- * Initialize the given queue.
- * Header:
- * void queue_init(q)
- * queue_t q; \* MODIFIED *\
- */
-#define queue_init(q) \
-MACRO_BEGIN \
- (q)->next = (q);\
- (q)->prev = (q);\
-MACRO_END
-
-/*
- * Macro: queue_head_init
- * Function:
- * Initialize the given queue head
- * Header:
- * void queue_head_init(q)
- * queue_head_t q; \* MODIFIED *\
- */
-#define queue_head_init(q) \
- queue_init(&(q))
-
-/*
- * Macro: queue_chain_init
- * Function:
- * Initialize the given queue chain element
- * Header:
- * void queue_chain_init(q)
- * queue_chain_t q; \* MODIFIED *\
- */
-#define queue_chain_init(q) \
- queue_init(&(q))
-
-/*
- * Macro: queue_first
- * Function:
- * Returns the first entry in the queue,
- * Header:
- * queue_entry_t queue_first(q)
- * queue_t q; \* IN *\
- */
-#define queue_first(q) ((q)->next)
-
-/*
- * Macro: queue_next
- * Function:
- * Returns the entry after an item in the queue.
- * Header:
- * queue_entry_t queue_next(qc)
- * queue_t qc;
- */
-#define queue_next(qc) ((qc)->next)
-
-/*
- * Macro: queue_last
- * Function:
- * Returns the last entry in the queue.
- * Header:
- * queue_entry_t queue_last(q)
- * queue_t q; \* IN *\
- */
-#define queue_last(q) ((q)->prev)
-
-/*
- * Macro: queue_prev
- * Function:
- * Returns the entry before an item in the queue.
- * Header:
- * queue_entry_t queue_prev(qc)
- * queue_t qc;
- */
-#define queue_prev(qc) ((qc)->prev)
-
-/*
- * Macro: queue_end
- * Function:
- * Tests whether a new entry is really the end of
- * the queue.
- * Header:
- * boolean_t queue_end(q, qe)
- * queue_t q;
- * queue_entry_t qe;
- */
-#define queue_end(q, qe) ((q) == (qe))
-
-/*
- * Macro: queue_empty
- * Function:
- * Tests whether a queue is empty.
- * Header:
- * boolean_t queue_empty(q)
- * queue_t q;
- */
-#define queue_empty(q) queue_end((q), queue_first(q))
-
-/*
- * Function: movqueue
- * Parameters:
- * queue_t _old : head of a queue whose items will be moved
- * queue_t _new : new queue head onto which items will be moved
- * Description:
- * Rebase queue items in _old onto _new then re-initialize
- * the _old object to an empty queue.
- * Equivalent to the queue_new_head Method 2 macro
- * Note:
- * Similar to the queue_new_head macro, this macros is intented
- * to function as an initializer method for '_new' and thus may
- * leak any list items that happen to be on the '_new' list.
- * This should only be used with Method 1 queue iteration (linkage chains)
- */
-static __inline__ void
-movqueue(queue_t _old, queue_t _new)
-{
- queue_entry_t next_elt, prev_elt;
-
- __QUEUE_ELT_VALIDATE((queue_entry_t)_old);
-
- if (queue_empty(_old)) {
- queue_init(_new);
- return;
- }
-
- /*
- * move the queue at _old to _new
- * and re-initialize _old
- */
- next_elt = _old->next;
- prev_elt = _old->prev;
-
- _new->next = next_elt;
- _new->prev = prev_elt;
- next_elt->prev = _new;
- prev_elt->next = _new;
-
- queue_init(_old);
-}
-
-/*----------------------------------------------------------------*/
-/*
- * Macros that operate on generic structures. The queue
- * chain may be at any location within the structure, and there
- * may be more than one chain.
- */
-
-/* check __prev->next == __elt */
-#define __QUEUE2_CHECK_NEXT(__fail, __elt, __prev, __head, type, field) \
-MACRO_BEGIN \
- if (__prev == __head) { \
- __fail |= __head->next != (queue_entry_t)__elt; \
- } else { \
- __fail |= ((type)(void *)__prev)->field.next != \
- (queue_entry_t)__elt; \
- } \
-MACRO_END
-
-/* check __next->prev == __elt */
-#define __QUEUE2_CHECK_PREV(__fail, __elt, __next, __head, type, field) \
-MACRO_BEGIN \
- if (__next == __head) { \
- __fail |= __head->prev != (queue_entry_t)__elt; \
- } else { \
- __fail |= ((type)(void *)__next)->field.prev != \
- (queue_entry_t)__elt; \
- } \
-MACRO_END
-
-#define __QUEUE2_CHECK_FAIL(__fail, __elt) \
-MACRO_BEGIN \
- if (__improbable(__fail)) { \
- __queue_element_linkage_invalid(__elt); \
- } \
-MACRO_END
-
-/* sets __prev->next to __elt */
-#define __QUEUE2_SET_NEXT(__prev, __elt, __head, type, field) \
-MACRO_BEGIN \
- if (__head == __prev) { \
- __head->next = (queue_entry_t)__elt; \
- } else { \
- ((type)(void *)__prev)->field.next = (queue_entry_t)__elt; \
- } \
-MACRO_END
-
-/* sets __next->prev to __elt */
-#define __QUEUE2_SET_PREV(__next, __elt, __head, type, field) \
-MACRO_BEGIN \
- if (__head == __next) { \
- __head->prev = (queue_entry_t)__elt; \
- } else { \
- ((type)(void *)__next)->field.prev = (queue_entry_t)__elt; \
- } \
-MACRO_END
-
-
-
-/*
- * Macro: queue_enter
- * Function:
- * Insert a new element at the tail of the queue.
- * Header:
- * void queue_enter(q, elt, type, field)
- * queue_t q;
- * <type> elt;
- * <type> is what's in our queue
- * <field> is the chain field in (*<type>)
- * Note:
- * This should only be used with Method 2 queue iteration (element chains)
- *
- * We insert a compiler barrier after setting the fields in the element
- * to ensure that the element is updated before being added to the queue,
- * which is especially important because stackshot, which operates from
- * debugger context, iterates several queues that use this macro (the tasks
- * lists and threads lists) without locks. Without this barrier, the
- * compiler may re-order the instructions for this macro in a way that
- * could cause stackshot to trip over an inconsistent queue during
- * iteration.
- */
-#define queue_enter(head, elt, type, field) \
-MACRO_BEGIN \
- queue_entry_t __head, __prev; \
- type __elt; \
- int __fail = 0; \
- \
- __elt = (elt); \
- __head = (head); \
- __prev = __head->prev; \
- \
- __QUEUE2_CHECK_NEXT(__fail, __head, __prev, __head, type, field); \
- __QUEUE2_CHECK_FAIL(__fail, __head); \
- \
- __elt->field.prev = __prev; \
- __elt->field.next = __head; \
- __compiler_barrier(); \
- __QUEUE2_SET_NEXT(__prev, __elt, __head, type, field); \
- __head->prev = (queue_entry_t)__elt; \
-MACRO_END
-
-/*
- * Macro: queue_enter_first
- * Function:
- * Insert a new element at the head of the queue.
- * Header:
- * void queue_enter_first(q, elt, type, field)
- * queue_t q;
- * <type> elt;
- * <type> is what's in our queue
- * <field> is the chain field in (*<type>)
- * Note:
- * This should only be used with Method 2 queue iteration (element chains)
- */
-#define queue_enter_first(head, elt, type, field) \
-MACRO_BEGIN \
- queue_entry_t __head, __next; \
- type __elt; \
- int __fail = 0; \
- \
- __elt = (elt); \
- __head = (head); \
- __next = __head->next; \
- \
- __QUEUE2_CHECK_PREV(__fail, __head, __next, __head, type, field); \
- __QUEUE2_CHECK_FAIL(__fail, __head); \
- \
- __elt->field.next = __next; \
- __elt->field.prev = __head; \
- __compiler_barrier(); \
- __QUEUE2_SET_PREV(__next, __elt, __head, type, field); \
- __head->next = (queue_entry_t)__elt; \
-MACRO_END
-
-/*
- * Macro: queue_insert_before
- * Function:
- * Insert a new element before a given element.
- * Header:
- * void queue_insert_before(q, elt, cur, type, field)
- * queue_t q;
- * <type> elt;
- * <type> cur;
- * <type> is what's in our queue
- * <field> is the chain field in (*<type>)
- * Note:
- * This should only be used with Method 2 queue iteration (element chains)
- */
-#define queue_insert_before(head, elt, cur, type, field) \
-MACRO_BEGIN \
- queue_entry_t __head, __cur, __prev; \
- type __elt; \
- int __fail = 0; \
- \
- __elt = (elt); \
- __cur = (queue_entry_t)(cur); \
- __head = (head); \
- \
- if (__head == __cur) { \
- __prev = __head->prev; \
- } else { \
- __prev = ((type)(void *)__cur)->field.prev; \
- } \
- \
- __QUEUE2_CHECK_NEXT(__fail, __cur, __prev, __head, type, field); \
- __QUEUE2_CHECK_FAIL(__fail, __head); \
- \
- __elt->field.prev = __prev; \
- __elt->field.next = __cur; \
- __compiler_barrier(); \
- __QUEUE2_SET_NEXT(__prev, __elt, __head, type, field); \
- __QUEUE2_SET_PREV(__cur, __elt, __head, type, field); \
-MACRO_END
-
-/*
- * Macro: queue_insert_after
- * Function:
- * Insert a new element after a given element.
- * Header:
- * void queue_insert_after(q, elt, cur, type, field)
- * queue_t q;
- * <type> elt;
- * <type> cur;
- * <type> is what's in our queue
- * <field> is the chain field in (*<type>)
- * Note:
- * This should only be used with Method 2 queue iteration (element chains)
- */
-#define queue_insert_after(head, elt, cur, type, field) \
-MACRO_BEGIN \
- queue_entry_t __head, __cur, __next; \
- type __elt; \
- int __fail = 0; \
- \
- __elt = (elt); \
- __cur = (queue_entry_t)(cur); \
- __head = (head); \
- \
- if (__head == __cur) { \
- __next = __head->next; \
- } else { \
- __next = ((type)(void *)__cur)->field.next; \
- } \
- \
- __QUEUE2_CHECK_PREV(__fail, __cur, __next, __head, type, field); \
- __QUEUE2_CHECK_FAIL(__fail, __head); \
- \
- __elt->field.prev = __cur; \
- __elt->field.next = __next; \
- __compiler_barrier(); \
- __QUEUE2_SET_NEXT(__cur, __elt, __head, type, field); \
- __QUEUE2_SET_PREV(__next, __elt, __head, type, field); \
-MACRO_END
-
-/*
- * Macro: queue_field [internal use only]
- * Function:
- * Find the queue_chain_t (or queue_t) for the
- * given element (thing) in the given queue (head)
- * Note:
- * This should only be used with Method 2 queue iteration (element chains)
- */
-#define queue_field(head, thing, type, field) \
- (((head) == (thing)) ? (head) : &((type)(void *)(thing))->field)
-
-/*
- * Macro: queue_remove
- * Function:
- * Remove an arbitrary item from the queue.
- * Header:
- * void queue_remove(q, qe, type, field)
- * arguments as in queue_enter
- * Note:
- * This should only be used with Method 2 queue iteration (element chains)
- */
-#define queue_remove(head, elt, type, field) \
-MACRO_BEGIN \
- queue_entry_t __head, __next, __prev; \
- type __elt; \
- int __fail = 0; \
- \
- __elt = (elt); \
- __head = (head); \
- __next = __elt->field.next; \
- __prev = __elt->field.prev; \
- \
- __QUEUE2_CHECK_PREV(__fail, __elt, __next, __head, type, field); \
- __QUEUE2_CHECK_NEXT(__fail, __elt, __prev, __head, type, field); \
- __QUEUE2_CHECK_FAIL(__fail, __head); \
- \
- __QUEUE2_SET_PREV(__next, __prev, __head, type, field); \
- __QUEUE2_SET_NEXT(__prev, __next, __head, type, field); \
- __compiler_barrier(); \
- __elt->field.next = NULL; \
- __elt->field.prev = NULL; \
-MACRO_END
-
-/*
- * Macro: queue_remove_first
- * Function:
- * Remove and return the entry at the head of
- * the queue.
- * Header:
- * queue_remove_first(head, entry, type, field)
- * entry is returned by reference
- * Note:
- * This should only be used with Method 2 queue iteration (element chains)
- */
-#define queue_remove_first(head, entry, type, field) \
-MACRO_BEGIN \
- queue_entry_t __hd; \
- type __entry; \
- \
- __hd = (head); \
- __entry = (type)(void *)__hd->next; \
- \
- if ((queue_entry_t)__entry != __hd) { \
- queue_remove(__hd, __entry, type, field); \
- } \
- (entry) = __entry; \
-MACRO_END
-
-/*
- * Macro: queue_remove_last
- * Function:
- * Remove and return the entry at the tail of
- * the queue.
- * Header:
- * queue_remove_last(head, entry, type, field)
- * entry is returned by reference
- * Note:
- * This should only be used with Method 2 queue iteration (element chains)
- */
-#define queue_remove_last(head, entry, type, field) \
-MACRO_BEGIN \
- queue_entry_t __hd; \
- type __entry; \
- \
- __hd = (head); \
- __entry = (type)(void *)__hd->prev; \
- \
- if ((queue_entry_t)__entry != __hd) { \
- queue_remove(__hd, __entry, type, field); \
- } \
- (entry) = __entry; \
-MACRO_END
-
-/*
- * Macro: queue_assign
- * Note:
- * This should only be used with Method 2 queue iteration (element chains)
- */
-#define queue_assign(to, from, type, field) \
-MACRO_BEGIN \
- ((type)(void *)((from)->prev))->field.next = (to); \
- ((type)(void *)((from)->next))->field.prev = (to); \
- *to = *from; \
-MACRO_END
-
-/*
- * Macro: queue_new_head
- * Function:
- * rebase old queue to new queue head
- * Header:
- * queue_new_head(old, new, type, field)
- * queue_t old;
- * queue_t new;
- * <type> is what's in our queue
- * <field> is the chain field in (*<type>)
- * Note:
- * This should only be used with Method 2 queue iteration (element chains)
- */
-#define queue_new_head(old, new, type, field) \
-MACRO_BEGIN \
- if (!queue_empty(old)) { \
- *(new) = *(old); \
- ((type)(void *)((new)->next))->field.prev = \
- (new); \
- ((type)(void *)((new)->prev))->field.next = \
- (new); \
- } else { \
- queue_init(new); \
- } \
-MACRO_END
-
-/*
- * Macro: queue_extend_last
- * Function:
- * Move the elements of a source queue to the end of a destination queue.
- * Note:
- * This should only be used with Method 2 queue iteration (element chains)
- */
-#define queue_extend_last(dst, src, type, field) \
-MACRO_BEGIN \
- queue_entry_t __src = (src); \
- queue_entry_t __dst = (dst); \
- if (queue_empty(__dst)) { \
- queue_new_head(__src, __dst, type, field); \
- queue_init(__src); \
- } else if (!queue_empty(__src)) { \
- ((type)(void *)queue_first(__src))->field.prev = \
- queue_last(__dst); \
- ((type)(void *)queue_last(__dst))->field.next = \
- queue_first(__src); \
- queue_last(__dst) = queue_last(__src); \
- ((type)(void *)queue_last(__dst))->field.next = __dst; \
- queue_init(__src); \
- } \
-MACRO_END
-
-/*
- * Macro: queue_extend_first
- * Function:
- * Move the elements of a source queue to the beginning of a destination queue.
- * Note:
- * This should only be used with Method 2 queue iteration (element chains)
- */
-#define queue_extend_first(dst, src, type, field) \
-MACRO_BEGIN \
- queue_entry_t __src = (src); \
- queue_entry_t __dst = (dst); \
- if (queue_empty(__dst)) { \
- queue_new_head(__src, __dst, type, field); \
- queue_init(__src); \
- } else if (!queue_empty(__src)) { \
- ((type)(void *)queue_first(__dst))->field.prev = \
- queue_last(__src); \
- ((type)(void *)queue_last(__src))->field.next = \
- queue_first(__dst); \
- queue_first(__dst) = queue_first(__src); \
- ((type)(void *)queue_first(__dst))->field.prev = __dst; \
- queue_init(__src); \
- } \
-MACRO_END
-
-/*
- * Macro: queue_iterate
- * Function:
- * iterate over each item in the queue.
- * Generates a 'for' loop, setting elt to
- * each item in turn (by reference).
- * Header:
- * queue_iterate(q, elt, type, field)
- * queue_t q;
- * <type> elt;
- * <type> is what's in our queue
- * <field> is the chain field in (*<type>)
- * Note:
- * This should only be used with Method 2 queue iteration (element chains)
- */
-#define queue_iterate(head, elt, type, field) \
- for ((elt) = (type)(void *) queue_first(head); \
- !queue_end((head), (queue_entry_t)(elt)); \
- (elt) = (type)(void *) queue_next(&(elt)->field))
-
-
-__END_DECLS
-
-#endif /* _KERN_QUEUE_H_ */