priority_queue.cpp [plain text]
#if KERNEL
#include <kern/priority_queue.h>
#include <mach/vm_param.h>
#ifdef __LP64__
static_assert(PRIORITY_QUEUE_ENTRY_CHILD_BITS >= VM_KERNEL_POINTER_SIGNIFICANT_BITS,
"Priority Queue child pointer packing failed");
#endif
#endif // KERNEL
#pragma mark priority queue helpers
template <typename queue_t, typename entry_t>
struct pqueue_entry_traits {
static inline int
compare(queue_t que, entry_t a, entry_t b);
};
template <typename queue_t>
struct pqueue_entry_traits<queue_t, priority_queue_entry_t> {
static inline int
compare(queue_t que, priority_queue_entry_t e1, priority_queue_entry_t e2)
{
return que->pq_cmp_fn(e1, e2);
}
};
template <typename queue_t>
struct pqueue_entry_traits<queue_t, priority_queue_entry_deadline_t> {
static inline int
compare(queue_t que __unused,
priority_queue_entry_deadline_t e1, priority_queue_entry_deadline_t e2)
{
return priority_heap_compare_ints(e1->deadline, e2->deadline);
}
};
template <typename queue_t>
struct pqueue_entry_traits<queue_t, priority_queue_entry_sched_t> {
static inline int
compare(queue_t que __unused,
priority_queue_entry_sched_t e1, priority_queue_entry_sched_t e2)
{
return (int)e2->key - (int)e1->key;
}
};
template <typename queue_t>
struct pqueue_entry_traits<queue_t, priority_queue_entry_stable_t> {
static inline int
compare(queue_t que __unused,
priority_queue_entry_stable_t e1, priority_queue_entry_stable_t e2)
{
if (e1->key != e2->key) {
return (int)e2->key - (int)e1->key;
}
if (e1->stamp != e2->stamp) {
if (e1->key & PRIORITY_QUEUE_ENTRY_PREEMPTED) {
return e1->stamp < e2->stamp ? 1 : -1;
} else {
return e1->stamp > e2->stamp ? 1 : -1;
}
}
return 0;
}
};
#pragma mark main template
template <typename queue_t, typename entry_t>
struct pqueue {
using entry_traits = pqueue_entry_traits<queue_t, entry_t>;
static inline void
pack_child(entry_t e, const entry_t child)
{
e->child = (long)child;
}
static inline entry_t
unpack_child(entry_t e)
{
return (entry_t)e->child;
}
private:
static inline bool
merge_parent_is_subtree_b(queue_t que, entry_t subtree_a, entry_t subtree_b)
{
if (priority_queue_is_max_heap((queue_t)nullptr)) {
return entry_traits::compare(que, subtree_a, subtree_b) > 0;
}
return entry_traits::compare(que, subtree_a, subtree_b) < 0;
}
static inline entry_t
merge_pair_inline(queue_t que, entry_t subtree_a, entry_t subtree_b)
{
entry_t merge_result = NULL;
if (subtree_a == NULL) {
merge_result = subtree_b;
} else if (subtree_b == NULL || (subtree_a == subtree_b)) {
merge_result = subtree_a;
} else {
entry_t parent = subtree_a;
entry_t child = subtree_b;
if (merge_parent_is_subtree_b(que, subtree_a, subtree_b)) {
parent = subtree_b;
child = subtree_a;
}
child->next = unpack_child(parent);
child->prev = parent;
if (unpack_child(parent) != NULL) {
unpack_child(parent)->prev = child;
}
pack_child(parent, child);
parent->next = NULL;
parent->prev = NULL;
merge_result = parent;
}
return merge_result;
}
OS_NOINLINE
static entry_t
merge_pair(queue_t que, entry_t subtree_a, entry_t subtree_b)
{
return merge_pair_inline(que, subtree_a, subtree_b);
}
OS_NOINLINE
static entry_t
meld_pair(queue_t que, entry_t elt)
{
entry_t pq_meld_result = NULL;
entry_t pair_list = NULL;
assert(elt);
do {
entry_t pair_item_a = elt;
entry_t pair_item_b = elt->next;
if (pair_item_b == NULL) {
pair_item_a->prev = pair_list;
pair_list = pair_item_a;
break;
}
elt = pair_item_b->next;
entry_t pair = merge_pair_inline(que, pair_item_a, pair_item_b);
pair->prev = pair_list;
pair_list = pair;
} while (elt != NULL);
do {
elt = pair_list->prev;
pq_meld_result = merge_pair_inline(que, pq_meld_result, pair_list);
pair_list = elt;
} while (pair_list != NULL);
return pq_meld_result;
}
static inline void
list_remove(entry_t elt)
{
assert(elt->prev != NULL);
if (unpack_child(elt->prev) == elt) {
pack_child(elt->prev, elt->next);
} else {
elt->prev->next = elt->next;
}
if (elt->next != NULL) {
elt->next->prev = elt->prev;
}
}
static inline bool
sift_down(queue_t que, entry_t elt)
{
bool was_root = remove(que, elt);
insert(que, elt);
return was_root;
}
static inline bool
sift_up(queue_t que, entry_t elt)
{
if (elt == que->pq_root) {
return true;
}
list_remove(elt);
return insert(que, elt);
}
static inline entry_t
remove_non_root(queue_t que, entry_t elt)
{
entry_t child, new_root;
list_remove(elt);
child = unpack_child(elt);
if (child) {
child = meld_pair(que, child);
new_root = merge_pair(que, que->pq_root, child);
que->pq_root = new_root;
}
return elt;
}
public:
OS_NOINLINE
static void
destroy(queue_t que, uintptr_t offset, void (^callback)(void *e))
{
assert(callback != NULL);
entry_t head = que->pq_root;
entry_t tail = head;
while (head != NULL) {
entry_t child_list = unpack_child(head);
if (child_list) {
tail->next = child_list;
while (tail->next) {
tail = tail->next;
}
}
entry_t elt = head;
head = head->next;
callback((void *)((char *)elt - offset));
}
que->pq_root = (entry_t)(~0ul);
}
static inline bool
insert(queue_t que, entry_t elt)
{
return (que->pq_root = merge_pair(que, que->pq_root, elt)) == elt;
}
static inline entry_t
remove_root(queue_t que, entry_t old_root)
{
entry_t new_root = unpack_child(old_root);
que->pq_root = new_root ? meld_pair(que, new_root) : NULL;
return old_root;
}
static inline bool
remove(queue_t que, entry_t elt)
{
if (elt == que->pq_root) {
remove_root(que, elt);
elt->next = elt->prev = NULL;
elt->child = 0;
return true;
} else {
remove_non_root(que, elt);
elt->next = elt->prev = NULL;
elt->child = 0;
return false;
}
}
static inline bool
entry_increased(queue_t que, entry_t elt)
{
if (priority_queue_is_max_heap(que)) {
return sift_up(que, elt);
} else {
return sift_down(que, elt);
}
}
static inline bool
entry_decreased(queue_t que, entry_t elt)
{
if (priority_queue_is_min_heap(que)) {
return sift_up(que, elt);
} else {
return sift_down(que, elt);
}
}
};
#pragma mark instantiation
#define PRIORITY_QUEUE_MAKE_IMPL(pqueue_t, queue_t, entry_t) \
\
using pqueue_t = pqueue<queue_t, entry_t>; \
\
extern "C" { \
\
__pqueue_overloadable void \
_priority_queue_destroy(queue_t que, uintptr_t offset, void (^cb)(void *e)) \
{ \
pqueue_t::destroy(que, offset, cb); \
} \
\
__pqueue_overloadable extern bool \
priority_queue_insert(queue_t que, entry_t elt) \
{ \
return pqueue_t::insert(que, elt); \
} \
\
__pqueue_overloadable extern entry_t \
_priority_queue_remove_root(queue_t que) \
{ \
return pqueue_t::remove_root(que, que->pq_root); \
} \
\
__pqueue_overloadable extern bool \
priority_queue_remove(queue_t que, entry_t elt) \
{ \
return pqueue_t::remove(que, elt); \
} \
\
__pqueue_overloadable extern bool \
priority_queue_entry_decreased(queue_t que, entry_t elt) \
{ \
return pqueue_t::entry_decreased(que, elt); \
} \
\
__pqueue_overloadable extern bool \
priority_queue_entry_increased(queue_t que, entry_t elt) \
{ \
return pqueue_t::entry_increased(que, elt); \
} \
\
}
PRIORITY_QUEUE_MAKE_IMPL(pqueue_min_t,
struct priority_queue_min *, priority_queue_entry_t);
PRIORITY_QUEUE_MAKE_IMPL(pqueue_max_t,
struct priority_queue_max *, priority_queue_entry_t);
PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_min_t,
struct priority_queue_sched_min *, priority_queue_entry_sched_t);
PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_max_t,
struct priority_queue_sched_max *, priority_queue_entry_sched_t);
PRIORITY_QUEUE_MAKE_IMPL(pqueue_deadline_min_t,
struct priority_queue_deadline_min *, priority_queue_entry_deadline_t);
PRIORITY_QUEUE_MAKE_IMPL(pqueue_deadline_max_t,
struct priority_queue_deadline_max *, priority_queue_entry_deadline_t);
PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_stable_min_t,
struct priority_queue_sched_stable_min *, priority_queue_entry_stable_t);
PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_stable_max_t,
struct priority_queue_sched_stable_max *, priority_queue_entry_stable_t);