* comparision result to indicate relative ordering of elements according to the heap type
*/
typedef int (^priority_queue_compare_fn_t)(struct priority_queue_entry *e1,
- struct priority_queue_entry *e2);
+ struct priority_queue_entry *e2);
/*
* Standard comparision routines for max and min heap.
}
#define priority_heap_make_comparator(name1, name2, type, field, ...) \
- (^int(priority_queue_entry_t __e1, priority_queue_entry_t __e2){ \
- type *name1 = pqe_element_fast(__e1, type, field); \
- type *name2 = pqe_element_fast(__e2, type, field); \
- __VA_ARGS__; \
- })
+ (^int(priority_queue_entry_t __e1, priority_queue_entry_t __e2){ \
+ type *name1 = pqe_element_fast(__e1, type, field); \
+ type *name2 = pqe_element_fast(__e2, type, field); \
+ __VA_ARGS__; \
+ })
#define PRIORITY_QUEUE_SCHED_PRI_MAX_HEAP_COMPARE \
- (^int(priority_queue_entry_t e1, priority_queue_entry_t e2){ \
- return -priority_queue_element_builtin_key_compare(e1, e2); \
- })
+ (^int(priority_queue_entry_t e1, priority_queue_entry_t e2){ \
+ return -priority_queue_element_builtin_key_compare(e1, e2); \
+ })
#define PRIORITY_QUEUE_SCHED_PRI_MIN_HEAP_COMPARE \
- (^int(priority_queue_entry_t e1, priority_queue_entry_t e2){ \
- return priority_queue_element_builtin_key_compare(e1, e2); \
- })
+ (^int(priority_queue_entry_t e1, priority_queue_entry_t e2){ \
+ return priority_queue_element_builtin_key_compare(e1, e2); \
+ })
/*
* Helper routines for packing/unpacking the child pointer in heap nodes.
* <type *> containing qe
*/
#define pqe_element(qe, type, field) ({ \
- priority_queue_entry_t _tmp_entry = (qe); \
- _tmp_entry ? pqe_element_fast(_tmp_entry, type, field) : ((type *)NULL); \
+ priority_queue_entry_t _tmp_entry = (qe); \
+ _tmp_entry ? pqe_element_fast(_tmp_entry, type, field) : ((type *)NULL); \
})
#define pqueue_has_generic_keys(p) \
- (((p)->pq_root_packed & PRIORITY_QUEUE_GENERIC_KEY) != 0)
+ (((p)->pq_root_packed & PRIORITY_QUEUE_GENERIC_KEY) != 0)
#define pqueue_has_builtin_keys(p) \
- (((p)->pq_root_packed & PRIORITY_QUEUE_GENERIC_KEY) == 0)
+ (((p)->pq_root_packed & PRIORITY_QUEUE_GENERIC_KEY) == 0)
#define pqueue_is_min_heap(p) \
- (((p)->pq_root_packed & PRIORITY_QUEUE_MIN_HEAP) != 0)
+ (((p)->pq_root_packed & PRIORITY_QUEUE_MIN_HEAP) != 0)
#define pqueue_is_max_heap(p) \
- (((p)->pq_root_packed & PRIORITY_QUEUE_MIN_HEAP) == 0)
+ (((p)->pq_root_packed & PRIORITY_QUEUE_MIN_HEAP) == 0)
/*
* Macro: pqueue_pack_root
*/
#define pqueue_pack_root(q, root_ptr) \
MACRO_BEGIN \
- uintptr_t __flags = (q)->pq_root_packed & PRIORITY_QUEUE_ROOT_FLAGS_MASK; \
- (q)->pq_root_packed = (uintptr_t)(root_ptr) | __flags; \
+ uintptr_t __flags = (q)->pq_root_packed & PRIORITY_QUEUE_ROOT_FLAGS_MASK; \
+ (q)->pq_root_packed = (uintptr_t)(root_ptr) | __flags; \
MACRO_END
/*
* <priority_queue_entry_t>
*/
#define pqueue_unpack_root(q) \
- ((priority_queue_entry_t)((q)->pq_root_packed & PRIORITY_QUEUE_ROOT_POINTER_MASK))
+ ((priority_queue_entry_t)((q)->pq_root_packed & PRIORITY_QUEUE_ROOT_POINTER_MASK))
/*
* Macro: pqueue_list_remove
elt->prev->next = elt->next;
}
/* Update prev for next element in list */
- if (elt->next != NULL)
+ if (elt->next != NULL) {
elt->next->prev = elt->prev;
+ }
}
/*
*/
static inline priority_queue_entry_t
pqueue_merge(priority_queue_entry_t subtree_a, priority_queue_entry_t subtree_b,
- priority_queue_compare_fn_t cmp_fn)
+ priority_queue_compare_fn_t cmp_fn)
{
priority_queue_entry_t merge_result = NULL;
if (subtree_a == NULL) {
/* Insert the child as the first element in the parent's child list */
child->next = pqueue_entry_unpack_child(parent);
child->prev = parent;
- if (pqueue_entry_unpack_child(parent) != NULL)
+ if (pqueue_entry_unpack_child(parent) != NULL) {
pqueue_entry_unpack_child(parent)->prev = child;
+ }
/* Create the parent child relationship */
pqueue_entry_pack_child(parent, child);
parent->next = NULL;
*/
static inline void
pqueue_update_key(struct priority_queue *que, priority_queue_entry_t elt,
- priority_queue_key_t new_key)
+ priority_queue_key_t new_key)
{
if (pqueue_has_builtin_keys(que)) {
assert(new_key <= UINT8_MAX);
*/
static inline priority_queue_entry_t
pqueue_remove_root(struct priority_queue *que, priority_queue_entry_t old_root,
- priority_queue_compare_fn_t cmp_fn)
+ priority_queue_compare_fn_t cmp_fn)
{
priority_queue_entry_t new_root = pqueue_entry_unpack_child(old_root);
- if (new_root) new_root = pqueue_pair_meld(new_root, cmp_fn);
+ if (new_root) {
+ new_root = pqueue_pair_meld(new_root, cmp_fn);
+ }
pqueue_pack_root(que, new_root);
return old_root;
}
*/
static inline priority_queue_entry_t
pqueue_remove_non_root(struct priority_queue *que, priority_queue_entry_t elt,
- priority_queue_compare_fn_t cmp_fn)
+ priority_queue_compare_fn_t cmp_fn)
{
priority_queue_entry_t child, new_root;
* None
*/
void
-pqueue_destroy(struct priority_queue *q, size_t offset,
- void (^callback)(void *e));
+ pqueue_destroy(struct priority_queue *q, size_t offset,
+ void (^callback)(void *e));
/*
* Priority Queue functionality routines
* <struct priority_queue_entry *> elt
*/
#define priority_queue_entry_key(q, elt) ({ \
- assert(pqueue_has_builtin_keys(q)); \
- (priority_queue_key_t)((elt)->key); \
+ assert(pqueue_has_builtin_keys(q)); \
+ (priority_queue_key_t)((elt)->key); \
})
/*
*/
#define priority_queue_init(q, flags) \
MACRO_BEGIN \
- pqueue_pack_root((q), NULL); \
- (q)->pq_root_packed = (flags); \
+ pqueue_pack_root((q), NULL); \
+ (q)->pq_root_packed = (flags); \
MACRO_END
/*
*/
#define priority_queue_entry_init(qe) \
MACRO_BEGIN \
- (qe)->next = NULL; \
- (qe)->prev = NULL; \
- pqueue_entry_pack_child((qe), NULL); \
- (qe)->key = PRIORITY_QUEUE_KEY_NONE; \
+ (qe)->next = NULL; \
+ (qe)->prev = NULL; \
+ pqueue_entry_pack_child((qe), NULL); \
+ (qe)->key = PRIORITY_QUEUE_KEY_NONE; \
MACRO_END
/*
*/
static inline boolean_t
priority_queue_insert(struct priority_queue *que, priority_queue_entry_t elt,
- priority_queue_key_t new_key, priority_queue_compare_fn_t cmp_fn)
+ priority_queue_key_t new_key, priority_queue_compare_fn_t cmp_fn)
{
priority_queue_entry_t new_root;
*/
static inline boolean_t
priority_queue_remove(struct priority_queue *que, priority_queue_entry_t elt,
- priority_queue_compare_fn_t cmp_fn)
+ priority_queue_compare_fn_t cmp_fn)
{
if (elt == pqueue_unpack_root(que)) {
pqueue_remove_root(que, elt, cmp_fn);
*/
static inline boolean_t
priority_queue_entry_decrease(struct priority_queue *que, priority_queue_entry_t elt,
- priority_queue_key_t new_key, priority_queue_compare_fn_t cmp_fn)
+ priority_queue_key_t new_key, priority_queue_compare_fn_t cmp_fn)
{
boolean_t was_root = priority_queue_remove(que, elt, cmp_fn);
/* Insert it back in the heap; insertion also causes the priority update in the element */
*/
static inline boolean_t
priority_queue_entry_increase(struct priority_queue *que, priority_queue_entry_t elt,
- priority_queue_key_t new_key, priority_queue_compare_fn_t cmp_fn)
+ priority_queue_key_t new_key, priority_queue_compare_fn_t cmp_fn)
{
if (elt == pqueue_unpack_root(que)) {
pqueue_update_key(que, elt, new_key);
* <type *> max element
*/
#define priority_queue_max(q, type, field) ({ \
- assert(pqueue_is_max_heap(q)); \
- pqe_element(pqueue_unpack_root(q), type, field); \
+ assert(pqueue_is_max_heap(q)); \
+ pqe_element(pqueue_unpack_root(q), type, field); \
})
/*
* <type *> min element
*/
#define priority_queue_min(q, type, field) ({ \
- assert(pqueue_is_min_heap(que)); \
- priority_queue_entry_key(pqueue_unpack_root(q), type, field); \
+ assert(pqueue_is_min_heap(q)); \
+ pqe_element(pqueue_unpack_root(q), type, field); \
})
/*
* <type *> max key
*/
#define priority_queue_max_key(q) ({ \
- assert(pqueue_is_max_heap(q)); \
- priority_queue_entry_key(q, pqueue_unpack_root(q)); \
+ assert(pqueue_is_max_heap(q)); \
+ priority_queue_entry_key(q, pqueue_unpack_root(q)); \
})
/*
* <type *> min key
*/
#define priority_queue_min_key(q) ({ \
- assert(pqueue_is_min_heap(q)); \
- priority_queue_entry_key(pqueue_unpack_root(q)); \
+ assert(pqueue_is_min_heap(q)); \
+ priority_queue_entry_key(pqueue_unpack_root(q)); \
})
/*
* <type *> max element
*/
#define priority_queue_remove_max(q, type, field, cmp_fn) ({ \
- assert(pqueue_is_max_heap(q)); \
- pqe_element(pqueue_remove_root(q, pqueue_unpack_root(q), cmp_fn), type, field); \
+ assert(pqueue_is_max_heap(q)); \
+ pqe_element(pqueue_remove_root(q, pqueue_unpack_root(q), cmp_fn), type, field); \
})
/*
* <type *> min element
*/
#define priority_queue_remove_min(q, type, field, cmp_fn) ({ \
- assert(pqueue_is_min_heap(que)); \
- pqe_element(pqueue_remove_root(q, pqueue_unpack_root(q), cmp_fn), type, field); \
+ assert(pqueue_is_min_heap(q)); \
+ pqe_element(pqueue_remove_root(q, pqueue_unpack_root(q), cmp_fn), type, field); \
})
/*
* None
*/
#define priority_queue_destroy(q, type, field, callback, ...) \
- pqueue_destroy(q, offsetof(type, field), callback, ##__VA_ARGS__)
+ pqueue_destroy(q, offsetof(type, field), callback, ##__VA_ARGS__)
__END_DECLS
projects / apple / xnu.git / blobdiff