/*
* 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)) \
#ifdef XNU_KERNEL_PRIVATE
/* 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 */
/*
* 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_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_ */