#ifndef _KERN_QUEUE_H_
#define _KERN_QUEUE_H_
#include <mach/mach_types.h>
#include <kern/macro_help.h>
struct queue_entry {
struct queue_entry *next;
struct queue_entry *prev;
};
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;
#define enqueue(queue,elt) enqueue_tail(queue, elt)
#define dequeue(queue) dequeue_head(queue)
#if !defined(__GNUC__)
#include <sys/cdefs.h>
__BEGIN_DECLS
extern void enqueue_head(
queue_t que,
queue_entry_t elt);
extern void enqueue_tail(
queue_t que,
queue_entry_t elt);
extern queue_entry_t dequeue_head(
queue_t que);
extern queue_entry_t dequeue_tail(
queue_t que);
extern void remqueue(
queue_entry_t elt);
extern void insque(
queue_entry_t entry,
queue_entry_t pred);
extern void remque(
queue_entry_t elt);
__END_DECLS
#else
#ifdef XNU_KERNEL_PRIVATE
#define __DEQUEUE_ELT_CLEANUP(elt) do { \
(elt)->next = (queue_entry_t) 0; \
(elt)->prev = (queue_entry_t) 0; \
} while (0)
#else
#define __DEQUEUE_ELT_CLEANUP(elt) do { } while(0)
#endif
static __inline__ void
enqueue_head(
queue_t que,
queue_entry_t elt)
{
elt->next = que->next;
elt->prev = que;
elt->next->prev = elt;
que->next = elt;
}
static __inline__ void
enqueue_tail(
queue_t que,
queue_entry_t elt)
{
elt->next = que;
elt->prev = que->prev;
elt->prev->next = elt;
que->prev = elt;
}
static __inline__ queue_entry_t
dequeue_head(
queue_t que)
{
register queue_entry_t elt = (queue_entry_t) 0;
if (que->next != que) {
elt = que->next;
elt->next->prev = que;
que->next = elt->next;
__DEQUEUE_ELT_CLEANUP(elt);
}
return (elt);
}
static __inline__ queue_entry_t
dequeue_tail(
queue_t que)
{
register queue_entry_t elt = (queue_entry_t) 0;
if (que->prev != que) {
elt = que->prev;
elt->prev->next = que;
que->prev = elt->prev;
__DEQUEUE_ELT_CLEANUP(elt);
}
return (elt);
}
static __inline__ void
remqueue(
queue_entry_t elt)
{
elt->next->prev = elt->prev;
elt->prev->next = elt->next;
__DEQUEUE_ELT_CLEANUP(elt);
}
static __inline__ void
insque(
queue_entry_t entry,
queue_entry_t pred)
{
entry->next = pred->next;
entry->prev = pred;
(pred->next)->prev = entry;
pred->next = entry;
}
static __inline__ void
remque(
register queue_entry_t elt)
{
(elt->next)->prev = elt->prev;
(elt->prev)->next = elt->next;
__DEQUEUE_ELT_CLEANUP(elt);
}
#endif
#define queue_init(q) \
MACRO_BEGIN \
(q)->next = (q);\
(q)->prev = (q);\
MACRO_END
#define queue_first(q) ((q)->next)
#define queue_next(qc) ((qc)->next)
#define queue_last(q) ((q)->prev)
#define queue_prev(qc) ((qc)->prev)
#define queue_end(q, qe) ((q) == (qe))
#define queue_empty(q) queue_end((q), queue_first(q))
#define queue_enter(head, elt, type, field) \
MACRO_BEGIN \
register queue_entry_t __prev; \
\
__prev = (head)->prev; \
if ((head) == __prev) { \
(head)->next = (queue_entry_t) (elt); \
} \
else { \
((type)__prev)->field.next = (queue_entry_t)(elt);\
} \
(elt)->field.prev = __prev; \
(elt)->field.next = head; \
(head)->prev = (queue_entry_t) elt; \
MACRO_END
#define queue_enter_first(head, elt, type, field) \
MACRO_BEGIN \
register queue_entry_t __next; \
\
__next = (head)->next; \
if ((head) == __next) { \
(head)->prev = (queue_entry_t) (elt); \
} \
else { \
((type)__next)->field.prev = (queue_entry_t)(elt);\
} \
(elt)->field.next = __next; \
(elt)->field.prev = head; \
(head)->next = (queue_entry_t) elt; \
MACRO_END
#define queue_insert_before(head, elt, cur, type, field) \
MACRO_BEGIN \
register queue_entry_t __prev; \
\
if ((head) == (queue_entry_t)(cur)) { \
(elt)->field.next = (head); \
if ((head)->next == (head)) { \
(elt)->field.prev = (head); \
(head)->next = (queue_entry_t)(elt); \
} else { \
__prev = (elt)->field.prev = (head)->prev; \
((type)__prev)->field.next = (queue_entry_t)(elt);\
} \
(head)->prev = (queue_entry_t)(elt); \
} else { \
(elt)->field.next = (queue_entry_t)(cur); \
if ((head)->next == (queue_entry_t)(cur)) { \
\
(elt)->field.prev = (head); \
(head)->next = (queue_entry_t)(elt); \
} else { \
__prev = (elt)->field.prev = (cur)->field.prev; \
((type)__prev)->field.next = (queue_entry_t)(elt);\
} \
(cur)->field.prev = (queue_entry_t)(elt); \
} \
MACRO_END
#define queue_insert_after(head, elt, cur, type, field) \
MACRO_BEGIN \
register queue_entry_t __next; \
\
if ((head) == (queue_entry_t)(cur)) { \
(elt)->field.prev = (head); \
if ((head)->next == (head)) { \
(elt)->field.next = (head); \
(head)->prev = (queue_entry_t)(elt); \
} else { \
__next = (elt)->field.next = (head)->next; \
((type)__next)->field.prev = (queue_entry_t)(elt);\
} \
(head)->next = (queue_entry_t)(elt); \
} else { \
(elt)->field.prev = (queue_entry_t)(cur); \
if ((head)->prev == (queue_entry_t)(cur)) { \
\
(elt)->field.next = (head); \
(head)->prev = (queue_entry_t)(elt); \
} else { \
__next = (elt)->field.next = (cur)->field.next; \
((type)__next)->field.prev = (queue_entry_t)(elt);\
} \
(cur)->field.next = (queue_entry_t)(elt); \
} \
MACRO_END
#define queue_field(head, thing, type, field) \
(((head) == (thing)) ? (head) : &((type)(thing))->field)
#define queue_remove(head, elt, type, field) \
MACRO_BEGIN \
register queue_entry_t __next, __prev; \
\
__next = (elt)->field.next; \
__prev = (elt)->field.prev; \
\
if ((head) == __next) \
(head)->prev = __prev; \
else \
((type)__next)->field.prev = __prev; \
\
if ((head) == __prev) \
(head)->next = __next; \
else \
((type)__prev)->field.next = __next; \
\
(elt)->field.next = NULL; \
(elt)->field.prev = NULL; \
MACRO_END
#define queue_remove_first(head, entry, type, field) \
MACRO_BEGIN \
register queue_entry_t __next; \
\
(entry) = (type) ((head)->next); \
__next = (entry)->field.next; \
\
if ((head) == __next) \
(head)->prev = (head); \
else \
((type)(__next))->field.prev = (head); \
(head)->next = __next; \
\
(entry)->field.next = NULL; \
(entry)->field.prev = NULL; \
MACRO_END
#define queue_remove_last(head, entry, type, field) \
MACRO_BEGIN \
register queue_entry_t __prev; \
\
(entry) = (type) ((head)->prev); \
__prev = (entry)->field.prev; \
\
if ((head) == __prev) \
(head)->next = (head); \
else \
((type)(__prev))->field.next = (head); \
(head)->prev = __prev; \
\
(entry)->field.next = NULL; \
(entry)->field.prev = NULL; \
MACRO_END
#define queue_assign(to, from, type, field) \
MACRO_BEGIN \
((type)((from)->prev))->field.next = (to); \
((type)((from)->next))->field.prev = (to); \
*to = *from; \
MACRO_END
#define queue_new_head(old, new, type, field) \
MACRO_BEGIN \
if (!queue_empty(old)) { \
*(new) = *(old); \
((type)((new)->next))->field.prev = (new); \
((type)((new)->prev))->field.next = (new); \
} else { \
queue_init(new); \
} \
MACRO_END
#define queue_iterate(head, elt, type, field) \
for ((elt) = (type) queue_first(head); \
!queue_end((head), (queue_entry_t)(elt)); \
(elt) = (type) queue_next(&(elt)->field))
#ifdef MACH_KERNEL_PRIVATE
#include <kern/lock.h>
struct mpqueue_head {
struct queue_entry head;
lck_mtx_t lock_data;
lck_mtx_ext_t lock_data_ext;
};
typedef struct mpqueue_head mpqueue_head_t;
#define round_mpq(size) (size)
#if defined(__i386__) || defined(__x86_64__)
#define mpqueue_init(q, lck_grp, lck_attr) \
MACRO_BEGIN \
queue_init(&(q)->head); \
lck_mtx_init_ext(&(q)->lock_data, \
&(q)->lock_data_ext, \
lck_grp, \
lck_attr); \
MACRO_END
#else
#define mpqueue_init(q, lck_grp, lck_attr) \
MACRO_BEGIN \
queue_init(&(q)->head); \
lck_spin_init(&(q)->lock_data, \
lck_grp, \
lck_attr); \
MACRO_END
#endif
#define mpenqueue_tail(q, elt) \
MACRO_BEGIN \
lck_mtx_lock_spin_always(&(q)->lock_data); \
enqueue_tail(&(q)->head, elt); \
lck_mtx_unlock_always(&(q)->lock_data); \
MACRO_END
#define mpdequeue_head(q, elt) \
MACRO_BEGIN \
lck_mtx_lock_spin_always(&(q)->lock_data); \
if (queue_empty(&(q)->head)) \
*(elt) = 0; \
else \
*(elt) = dequeue_head(&(q)->head); \
lck_mtx_unlock_always(&(q)->lock_data); \
MACRO_END
#endif
#endif