#include <kern/priority_queue.h>
Kernel (KEXT) › kern/ primitives

kern/priority_queue.h Kernel.framework

A generic priorty ordered queue implementation based on pairing heaps. Reference Papers: - A Back-to-Basics Empirical Study of Priority Queues (https://arxiv.org/abs/1403.0252) - The Pairing Heap: A New Form of Self-Adjusting Heap (https://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf) The XNU implementation is a basic version of the pairing heap. It allows for O(1) insertion and amortized O(log n) deletion. It is not a stable data structure by default since adding stability would need more pointers and hence more memory. Type of queues There are several types of priority queues, with types named: struct priority_queue_<subtype>_<min|max> In the rest of this header, `struct priority_queue` is used as a generic type to mean any priority_queue type. min/max refers to whether the priority queue is a min or a max heap. the subtype can be: - sched, in which case the key is built in the linkage and assumed to be a scheduler priority. - sched_stable, in which case the key is a combination of: * a scheduler priority * whether the entry was preempted or not * a timestamp. - generic, in which case a comparison function must be passed to the priority_queue_init. Element Linkage: Both types use a common queue head and linkage pattern. The head of a priority queue is declared as: struct priority_queue_<subtype>_<min|max> pq_head; Elements in this queue are linked together using one of the struct priority_queue_entry_<subtype> objects embedded within a structure: struct some_data { int field1; int field2; ... struct priority_queue_entry link; ... int last_field; }; struct some_data is referred to as the queue "element" This method uses the next, prev and child pointers of the struct priority_queue_entry linkage object embedded in a queue element to point to other elements in the queue. The head of the priority queue (the priority_queue object) will point to the root of the pairing heap (NULL if heap is empty). This method allows multiple chains through a given object, by embedding multiple priority_queue_entry objects in the structure, while simultaneously providing fast removal and insertion into the heap using only priority_queue_entry object pointers.
includes: kern/kern_types.h, kern/macro_help.h, kern/assert.h, Kernel/stdbool.h, sys/cdefs.h
61 functions · 26 macros · 12 structs · 7 typedefs · 1 enum

macroPRIORITY_QUEUE_KEY_NONE

Priority keys maintained by the data structure. Since the priority is packed in the node itself, it restricts keys to be 16-bits only.
#define PRIORITY_QUEUE_KEY_NONE 0

typedefpriority_queue_key_t

typedef uint16_t priority_queue_key_t

macroPRIORITY_QUEUE_ENTRY_CHILD_BITS

#define PRIORITY_QUEUE_ENTRY_CHILD_BITS 48

macroPRIORITY_QUEUE_ENTRY_KEY_BITS

#define PRIORITY_QUEUE_ENTRY_KEY_BITS 16

structpriority_queue_entry

size 24, align 8
struct priority_queue_entry *next
struct priority_queue_entry *prev
long:16__key
long:48child

typedefpriority_queue_entry_t

typedef struct priority_queue_entry * priority_queue_entry_t;

structpriority_queue_entry_deadline

size 32, align 8
struct priority_queue_entry_deadline *next
struct priority_queue_entry_deadline *prev
long:16__key
long:48child
uint64_tdeadline

typedefpriority_queue_entry_deadline_t

typedef struct priority_queue_entry_deadline * priority_queue_entry_deadline_t;

structpriority_queue_entry_sched

size 24, align 8
struct priority_queue_entry_sched *next
struct priority_queue_entry_sched *prev
long:16key
long:48child

typedefpriority_queue_entry_sched_t

typedef struct priority_queue_entry_sched * priority_queue_entry_sched_t;

structpriority_queue_entry_stable

size 32, align 8
struct priority_queue_entry_stable *next
struct priority_queue_entry_stable *prev
long:16key
long:48child
uint64_tstamp

typedefpriority_queue_entry_stable_t

typedef struct priority_queue_entry_stable * priority_queue_entry_stable_t;

typedefpriority_queue_compare_fn_t

Comparator block prototype Args: - elements to compare Return: comparision result to indicate relative ordering of elements according to the heap type
typedef int (^)(struct priority_queue_entry *, struct priority_queue_entry *) priority_queue_compare_fn_t;

macropriority_heap_compare_ints

#define priority_heap_compare_ints(a, b) ((a) < (b) ? 1 : -1)

macropriority_heap_make_comparator

#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__;
	})

structpriority_queue_min

Type of generic heaps
size 16, align 8
struct priority_queue_entry *pq_root
priority_queue_compare_fn_tpq_cmp_fn

structpriority_queue_max

size 16, align 8
struct priority_queue_entry *pq_root
priority_queue_compare_fn_tpq_cmp_fn

structpriority_queue_deadline_min

Type of deadline heaps
size 8, align 8
struct priority_queue_entry_deadline *pq_root

structpriority_queue_sched_min

Type of scheduler priority based heaps
size 8, align 8
struct priority_queue_entry_sched *pq_root

structpriority_queue_sched_max

size 8, align 8
struct priority_queue_entry_sched *pq_root

structpriority_queue_sched_stable_min

Type of scheduler priority based stable heaps
size 8, align 8
struct priority_queue_entry_stable *pq_root

macroPRIORITY_QUEUE_INITIALIZER

#define PRIORITY_QUEUE_INITIALIZER { .pq_root = NULL }

macropriority_queue_is_min_heap

#define priority_queue_is_min_heap(pq) _Generic(pq,
	struct priority_queue_min *: true,
	struct priority_queue_max *: false,
	struct priority_queue_deadline_min *: true,
	struct priority_queue_deadline_max *: false,
	struct priority_queue_sched_min *: true,
	struct priority_queue_sched_max *: false,
	struct priority_queue_sched_stable_min *: true,
	struct priority_queue_sched_stable_max *: false)

macropriority_queue_is_max_heap

#define priority_queue_is_max_heap(pq) (!priority_queue_is_min_heap(pq))

macropqe_element_fast

Macro: pqe_element_fast Function: Convert a priority_queue_entry_t to a queue element pointer. Get a pointer to the user-defined element containing a given priority_queue_entry_t The fast variant assumes that `qe` is not NULL Header: pqe_element_fast(qe, type, field) <priority_queue_entry_t> qe <type> type of element in priority queue <field> chain field in (*<type>) Returns: <type *> containing qe
#define pqe_element_fast(qe, type, field) __container_of(qe, type, field)

macropqe_element

Macro: pqe_element Function: Convert a priority_queue_entry_t to a queue element pointer. Get a pointer to the user-defined element containing a given priority_queue_entry_t The non fast variant handles NULL `qe` Header: pqe_element(qe, type, field) <priority_queue_entry_t> qe <type> type of element in priority queue <field> chain field in (*<type>) Returns: <type *> containing qe
#define pqe_element(qe, type, field) ({
	__auto_type _tmp_entry = (qe);
	_tmp_entry ? pqe_element_fast(_tmp_entry, type, field) : ((type *)NULL);
})

macropriority_queue_empty

Macro: priority_queue_empty Function: Tests whether a priority queue is empty. Header: boolean_t priority_queue_empty(pq) <struct priority_queue *> pq
#define priority_queue_empty(pq) ((pq)->pq_root == NULL)

functionpriority_queue_init

__pqueue_overloadable extern void priority_queue_init(struct priority_queue *pq, ...)
Macro: priority_queue_init Function: Initialize a <struct priority_queue *>. Header: priority_queue_init(pq) <struct priority_queue *> pq (optional) <cmp_fn> comparator function Returns: None
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Initializes a priority queue head. The kernel's priority queues are pairing heaps (O(1) insertion, amortized O(log n) deletion) declared as struct priority_queue_<subtype>_<min|max>; this initializer is overloaded for all eight types. For the generic priority_queue_min and priority_queue_max heaps it takes a priority_queue_compare_fn_t comparator block in addition to the queue, storing it for later ordering decisions and setting the root to NULL. For the deadline, sched, and sched_stable specializations the key lives in the entry linkage itself (a 64-bit deadline; a scheduler priority packed with a PRIORITY_QUEUE_ENTRY_PREEMPTED modifier; or priority, preemption modifier, and timestamp for the stable variant), so no comparator is taken and the head is simply zeroed. PRIORITY_QUEUE_INITIALIZER gives equivalent static initialization; element linkages are prepared separately with priority_queue_entry_init.

macropriority_queue_entry_init

Macro: priority_queue_entry_init Function: Initialize a priority_queue_entry_t Header: priority_queue_entry_init(qe) <priority_queue_entry_t> qe Returns: None
#define priority_queue_entry_init(qe) __builtin_bzero(qe, sizeof(*(qe)))

macropriority_queue_destroy

Macro: priority_queue_destroy Function: Destroy a priority queue safely. This routine accepts a callback to handle any cleanup for elements in the priority queue. The queue does not maintain its invariants while getting destroyed. The priority queue and the linkage nodes need to be re-initialized before re-using them. Header: priority_queue_destroy(pq, type, field, callback) <struct priority_queue *> pq <callback> callback for each element Returns: None
#define priority_queue_destroy(pq, type, field, callback) MACRO_BEGIN
	void (^__callback)(type *) = (callback); /* type check */
	_priority_queue_destroy(pq, offsetof(type, field),
	    (void (^)(void *))(__callback));
MACRO_END

macropriority_queue_min

Macro: priority_queue_min Function: Lookup the minimum in a min-priority queue. Header: priority_queue_min(pq, type, field) <struct priority_queue *> pq <type> type of element in priority queue <field> chain field in (*<type>) Returns: <type *> root element
#define priority_queue_min(pq, type, field) ({
	static_assert(priority_queue_is_min_heap(pq), "queue is min heap");
	pqe_element((pq)->pq_root, type, field);
})

macropriority_queue_max

Macro: priority_queue_max Function: Lookup the maximum element in a max-priority queue. Header: priority_queue_max(pq, type, field) <struct priority_queue *> pq <type> type of element in priority queue <field> chain field in (*<type>) Returns: <type *> root element
#define priority_queue_max(pq, type, field) ({
	static_assert(priority_queue_is_max_heap(pq), "queue is max heap");
	pqe_element((pq)->pq_root, type, field);
})

functionpriority_queue_insert

__pqueue_overloadable
extern bool priority_queue_insert(
	struct priority_queue *pq,
	struct priority_queue_entry *elt
)
Macro: priority_queue_insert Function: Insert an element into the priority queue The caller must have set the key prio to insertion Header: priority_queue_insert(pq, elt, new_key) <struct priority_queue *> pq <priority_queue_entry_t> elt Returns: Whether the inserted element became the new root
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Inserts an element into the priority queue; overloaded for all eight pairing-heap queue types. The caller must have set the entry's key before insertion: comparator-visible state for the generic heaps, the deadline field for deadline heaps, or priority_queue_entry_set_sched_pri for the sched and sched_stable heaps. Returns whether the inserted element became the new root (the new minimum of a min-heap or maximum of a max-heap). Insertion is O(1). The heaps are not stable by default; only the sched_stable variants break priority ties using a preemption modifier and timestamp.

macropriority_queue_remove_min

Macro: priority_queue_remove_min Function: Remove the minimum element in a min-heap priority queue. Header: priority_queue_remove_min(pq, type, field) <struct priority_queue *> pq <type> type of element in priority queue <field> chain field in (*<type>) Returns: <type *> max element
#define priority_queue_remove_min(pq, type, field) ({
	static_assert(priority_queue_is_min_heap(pq), "queue is min heap");
	pqe_element(_priority_queue_remove_root(pq), type, field);
})

macropriority_queue_remove_max

Macro: priority_queue_remove_max Function: Remove the maximum element in a max-heap priority queue. Header: priority_queue_remove_max(pq, type, field) <struct priority_queue *> pq <type> type of element in priority queue <field> chain field in (*<type>) Returns: <type *> max element
#define priority_queue_remove_max(pq, type, field) ({
	static_assert(priority_queue_is_max_heap(pq), "queue is max heap");
	pqe_element(_priority_queue_remove_root(pq), type, field);
})

functionpriority_queue_remove

__pqueue_overloadable
extern bool priority_queue_remove(
	struct priority_queue *pq,
	struct priority_queue_entry *elt
)
Macro: priority_queue_remove Function: Removes an element from the priority queue Header: priority_queue_remove(pq, elt) <struct priority_queue *> pq <priority_queue_entry_t> elt Returns: Whether the removed element was the root
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Removes an arbitrary element from the priority queue given its linkage entry; overloaded for all eight pairing-heap queue types. Returns whether the removed element was the root of the heap, letting scheduler callers notice when the minimum (or maximum) changed. Removal from a pairing heap is amortized O(log n).

functionpriority_queue_entry_decreased

__pqueue_overloadable
extern bool priority_queue_entry_decreased(
	struct priority_queue *pq,
	struct priority_queue_entry *elt
)
Macro: priority_queue_entry_decreased Function: Signal the priority queue that the entry priority has decreased. The new value for the element priority must have been set prior to calling this function. Header: priority_queue_entry_decreased(pq, elt) <struct priority_queue *> pq <priority_queue_entry_t> elt Returns: Whether the update caused the root or its key to change.
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Signals the priority queue that an entry's priority has decreased so the pairing heap can restore its invariants; overloaded for all eight queue types. The new value for the element's priority must have been set before calling (comparator-visible state, the deadline field, or priority_queue_entry_set_sched_pri, according to the queue subtype). Returns whether the update caused the root or its key to change. Counterpart of priority_queue_entry_increased.

functionpriority_queue_entry_increased

__pqueue_overloadable
extern bool priority_queue_entry_increased(
	struct priority_queue *pq,
	struct priority_queue_entry *elt
)
Macro: priority_queue_entry_increased Function: Signal the priority queue that the entry priority has increased. The new value for the element priority must have been set prior to calling this function. Header: priority_queue_entry_increased(pq, elt, new_key) <struct priority_queue *> pq <priority_queue_entry_t> elt Returns: Whether the update caused the root or its key to change.
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Signals the priority queue that an entry's priority has increased so the pairing heap can restore its invariants; overloaded for all eight queue types. The new value for the element's priority must have been set before calling (comparator-visible state, the deadline field, or priority_queue_entry_set_sched_pri, according to the queue subtype). Returns whether the update caused the root or its key to change. Counterpart of priority_queue_entry_decreased.

enumpriority_queue_entry_sched_modifier_t

underlying type uint8_t
PRIORITY_QUEUE_ENTRY_NONE0
PRIORITY_QUEUE_ENTRY_PREEMPTED1

typedefpriority_queue_entry_sched_modifier_t

typedef enum priority_queue_entry_sched_modifier_t priority_queue_entry_sched_modifier_t;

macropriority_queue_is_sched_heap

#define priority_queue_is_sched_heap(pq) _Generic(pq,
	struct priority_queue_sched_min *: true,
	struct priority_queue_sched_max *: true,
	struct priority_queue_sched_stable_min *: true,
	struct priority_queue_sched_stable_max *: true,
	default: false)

macropriority_queue_entry_set_sched_pri

Macro: priority_queue_entry_set_sched_pri Function: Sets the scheduler priority on an entry supporting this concept. The priority is expected to fit on 8 bits. An optional sorting modifier. Header: priority_queue_entry_set_sched_pri(pq, elt, pri, modifier) <struct priority_queue *> pq <priority_queue_entry_t> elt <uint8_t> pri <priority_queue_entry_sched_modifier_t> modifier
#define priority_queue_entry_set_sched_pri(pq, elt, pri, modifier) MACRO_BEGIN
	static_assert(priority_queue_is_sched_heap(pq), "is a sched heap");
	(elt)->key = (priority_queue_key_t)(((pri) << 8) + (modifier));
MACRO_END

macropriority_queue_entry_sched_pri

Macro: priority_queue_entry_sched_pri Function: Return the scheduler priority on an entry supporting this concept. Header: priority_queue_entry_sched_pri(pq, elt) <struct priority_queue *> pq <priority_queue_entry_t> elt Returns: The scheduler priority of this entry
#define priority_queue_entry_sched_pri(pq, elt) ({
	static_assert(priority_queue_is_sched_heap(pq), "is a sched heap");
	(priority_queue_key_t)((elt)->key >> 8);
})

macropriority_queue_entry_sched_modifier

Macro: priority_queue_entry_sched_modifier Function: Return the scheduler modifier on an entry supporting this concept. Header: priority_queue_entry_sched_modifier(pq, elt) <struct priority_queue *> pq <priority_queue_entry_t> elt Returns: The scheduler priority of this entry
#define priority_queue_entry_sched_modifier(pq, elt) ({
	static_assert(priority_queue_is_sched_heap(pq), "is a sched heap");
	(priority_queue_entry_sched_modifier_t)(elt)->key;
})

macropriority_queue_min_sched_pri

Macro: priority_queue_min_sched_pri Function: Return the scheduler priority of the minimum element of a scheduler priority queue. Header: priority_queue_min_sched_pri(pq) <struct priority_queue *> pq Returns: The scheduler priority of this entry
#define priority_queue_min_sched_pri(pq) ({
	static_assert(priority_queue_is_min_heap(pq), "queue is min heap");
	priority_queue_entry_sched_pri(pq, (pq)->pq_root);
})

macropriority_queue_max_sched_pri

Macro: priority_queue_max_sched_pri Function: Return the scheduler priority of the maximum element of a scheduler priority queue. Header: priority_queue_max_sched_pri(pq) <struct priority_queue *> pq Returns: The scheduler priority of this entry
#define priority_queue_max_sched_pri(pq) ({
	static_assert(priority_queue_is_max_heap(pq), "queue is max heap");
	priority_queue_entry_sched_pri(pq, (pq)->pq_root);
})

macroPRIORITY_QUEUE_MAKE_BASE

#define PRIORITY_QUEUE_MAKE_BASE(pqueue_t, pqelem_t) __pqueue_overloadable extern void
_priority_queue_destroy(pqueue_t pq, uintptr_t offset, void (^cb)(void *));

__pqueue_overloadable extern bool
priority_queue_insert(pqueue_t que, pqelem_t elt);

__pqueue_overloadable extern pqelem_t
_priority_queue_remove_root(pqueue_t que);

__pqueue_overloadable extern bool
priority_queue_remove(pqueue_t que, pqelem_t elt);

__pqueue_overloadable extern bool
priority_queue_entry_decreased(pqueue_t que, pqelem_t elt);

__pqueue_overloadable extern bool
priority_queue_entry_increased(pqueue_t que, pqelem_t elt)

macroPRIORITY_QUEUE_MAKE

#define PRIORITY_QUEUE_MAKE(pqueue_t, pqelem_t) __pqueue_overloadable
static inline void
priority_queue_init(pqueue_t que)
{
	__builtin_bzero(que, sizeof(*que));
}

PRIORITY_QUEUE_MAKE_BASE(pqueue_t, pqelem_t)

macroPRIORITY_QUEUE_MAKE_CB

#define PRIORITY_QUEUE_MAKE_CB(pqueue_t, pqelem_t) __pqueue_overloadable
static inline void
priority_queue_init(pqueue_t pq, priority_queue_compare_fn_t cmp_fn)
{
	pq->pq_root = NULL;
	pq->pq_cmp_fn = cmp_fn;
}

PRIORITY_QUEUE_MAKE_BASE(pqueue_t, pqelem_t)

functionpriority_queue_init

PRIORITY_QUEUE_MAKE_CB(struct priority_queue_min *, priority_queue_entry_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Initializes a priority queue head. The kernel's priority queues are pairing heaps (O(1) insertion, amortized O(log n) deletion) declared as struct priority_queue_<subtype>_<min|max>; this initializer is overloaded for all eight types. For the generic priority_queue_min and priority_queue_max heaps it takes a priority_queue_compare_fn_t comparator block in addition to the queue, storing it for later ordering decisions and setting the root to NULL. For the deadline, sched, and sched_stable specializations the key lives in the entry linkage itself (a 64-bit deadline; a scheduler priority packed with a PRIORITY_QUEUE_ENTRY_PREEMPTED modifier; or priority, preemption modifier, and timestamp for the stable variant), so no comparator is taken and the head is simply zeroed. PRIORITY_QUEUE_INITIALIZER gives equivalent static initialization; element linkages are prepared separately with priority_queue_entry_init.

function_priority_queue_destroy

PRIORITY_QUEUE_MAKE_CB(struct priority_queue_min *, priority_queue_entry_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Implementation routine behind the priority_queue_destroy macro; overloaded for all eight priority queue types. Destroys a priority queue safely, invoking the supplied cleanup block on every element; the offset argument, offsetof(type, field) of the linkage within the element, is filled in by the macro. The queue does not maintain its heap invariants while being destroyed, and both the queue head and the linkage nodes must be re-initialized (priority_queue_init, priority_queue_entry_init) before reuse. Callers use priority_queue_destroy(pq, type, field, callback) rather than this routine directly.

functionpriority_queue_insert

PRIORITY_QUEUE_MAKE_CB(struct priority_queue_min *, priority_queue_entry_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Inserts an element into the priority queue; overloaded for all eight pairing-heap queue types. The caller must have set the entry's key before insertion: comparator-visible state for the generic heaps, the deadline field for deadline heaps, or priority_queue_entry_set_sched_pri for the sched and sched_stable heaps. Returns whether the inserted element became the new root (the new minimum of a min-heap or maximum of a max-heap). Insertion is O(1). The heaps are not stable by default; only the sched_stable variants break priority ties using a preemption modifier and timestamp.

function_priority_queue_remove_root

PRIORITY_QUEUE_MAKE_CB(struct priority_queue_min *, priority_queue_entry_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Removes the root entry of the pairing heap and returns its linkage pointer, NULL if the queue is empty; overloaded for all eight priority queue types. Backs the priority_queue_remove_min and priority_queue_remove_max macros, which statically assert the heap direction and convert the returned linkage to the containing element with pqe_element. The root is the minimum element of a min-heap or the maximum of a max-heap; removal is amortized O(log n).

functionpriority_queue_remove

PRIORITY_QUEUE_MAKE_CB(struct priority_queue_min *, priority_queue_entry_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Removes an arbitrary element from the priority queue given its linkage entry; overloaded for all eight pairing-heap queue types. Returns whether the removed element was the root of the heap, letting scheduler callers notice when the minimum (or maximum) changed. Removal from a pairing heap is amortized O(log n).

functionpriority_queue_entry_decreased

PRIORITY_QUEUE_MAKE_CB(struct priority_queue_min *, priority_queue_entry_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Signals the priority queue that an entry's priority has decreased so the pairing heap can restore its invariants; overloaded for all eight queue types. The new value for the element's priority must have been set before calling (comparator-visible state, the deadline field, or priority_queue_entry_set_sched_pri, according to the queue subtype). Returns whether the update caused the root or its key to change. Counterpart of priority_queue_entry_increased.

functionpriority_queue_entry_increased

PRIORITY_QUEUE_MAKE_CB(struct priority_queue_min *, priority_queue_entry_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Signals the priority queue that an entry's priority has increased so the pairing heap can restore its invariants; overloaded for all eight queue types. The new value for the element's priority must have been set before calling (comparator-visible state, the deadline field, or priority_queue_entry_set_sched_pri, according to the queue subtype). Returns whether the update caused the root or its key to change. Counterpart of priority_queue_entry_decreased.

functionpriority_queue_init

PRIORITY_QUEUE_MAKE_CB(struct priority_queue_max *, priority_queue_entry_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Initializes a priority queue head. The kernel's priority queues are pairing heaps (O(1) insertion, amortized O(log n) deletion) declared as struct priority_queue_<subtype>_<min|max>; this initializer is overloaded for all eight types. For the generic priority_queue_min and priority_queue_max heaps it takes a priority_queue_compare_fn_t comparator block in addition to the queue, storing it for later ordering decisions and setting the root to NULL. For the deadline, sched, and sched_stable specializations the key lives in the entry linkage itself (a 64-bit deadline; a scheduler priority packed with a PRIORITY_QUEUE_ENTRY_PREEMPTED modifier; or priority, preemption modifier, and timestamp for the stable variant), so no comparator is taken and the head is simply zeroed. PRIORITY_QUEUE_INITIALIZER gives equivalent static initialization; element linkages are prepared separately with priority_queue_entry_init.

function_priority_queue_destroy

PRIORITY_QUEUE_MAKE_CB(struct priority_queue_max *, priority_queue_entry_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Implementation routine behind the priority_queue_destroy macro; overloaded for all eight priority queue types. Destroys a priority queue safely, invoking the supplied cleanup block on every element; the offset argument, offsetof(type, field) of the linkage within the element, is filled in by the macro. The queue does not maintain its heap invariants while being destroyed, and both the queue head and the linkage nodes must be re-initialized (priority_queue_init, priority_queue_entry_init) before reuse. Callers use priority_queue_destroy(pq, type, field, callback) rather than this routine directly.

functionpriority_queue_insert

PRIORITY_QUEUE_MAKE_CB(struct priority_queue_max *, priority_queue_entry_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Inserts an element into the priority queue; overloaded for all eight pairing-heap queue types. The caller must have set the entry's key before insertion: comparator-visible state for the generic heaps, the deadline field for deadline heaps, or priority_queue_entry_set_sched_pri for the sched and sched_stable heaps. Returns whether the inserted element became the new root (the new minimum of a min-heap or maximum of a max-heap). Insertion is O(1). The heaps are not stable by default; only the sched_stable variants break priority ties using a preemption modifier and timestamp.

function_priority_queue_remove_root

PRIORITY_QUEUE_MAKE_CB(struct priority_queue_max *, priority_queue_entry_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Removes the root entry of the pairing heap and returns its linkage pointer, NULL if the queue is empty; overloaded for all eight priority queue types. Backs the priority_queue_remove_min and priority_queue_remove_max macros, which statically assert the heap direction and convert the returned linkage to the containing element with pqe_element. The root is the minimum element of a min-heap or the maximum of a max-heap; removal is amortized O(log n).

functionpriority_queue_remove

PRIORITY_QUEUE_MAKE_CB(struct priority_queue_max *, priority_queue_entry_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Removes an arbitrary element from the priority queue given its linkage entry; overloaded for all eight pairing-heap queue types. Returns whether the removed element was the root of the heap, letting scheduler callers notice when the minimum (or maximum) changed. Removal from a pairing heap is amortized O(log n).

functionpriority_queue_entry_decreased

PRIORITY_QUEUE_MAKE_CB(struct priority_queue_max *, priority_queue_entry_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Signals the priority queue that an entry's priority has decreased so the pairing heap can restore its invariants; overloaded for all eight queue types. The new value for the element's priority must have been set before calling (comparator-visible state, the deadline field, or priority_queue_entry_set_sched_pri, according to the queue subtype). Returns whether the update caused the root or its key to change. Counterpart of priority_queue_entry_increased.

functionpriority_queue_entry_increased

PRIORITY_QUEUE_MAKE_CB(struct priority_queue_max *, priority_queue_entry_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Signals the priority queue that an entry's priority has increased so the pairing heap can restore its invariants; overloaded for all eight queue types. The new value for the element's priority must have been set before calling (comparator-visible state, the deadline field, or priority_queue_entry_set_sched_pri, according to the queue subtype). Returns whether the update caused the root or its key to change. Counterpart of priority_queue_entry_decreased.

functionpriority_queue_init

PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_min *, priority_queue_entry_deadline_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Initializes a priority queue head. The kernel's priority queues are pairing heaps (O(1) insertion, amortized O(log n) deletion) declared as struct priority_queue_<subtype>_<min|max>; this initializer is overloaded for all eight types. For the generic priority_queue_min and priority_queue_max heaps it takes a priority_queue_compare_fn_t comparator block in addition to the queue, storing it for later ordering decisions and setting the root to NULL. For the deadline, sched, and sched_stable specializations the key lives in the entry linkage itself (a 64-bit deadline; a scheduler priority packed with a PRIORITY_QUEUE_ENTRY_PREEMPTED modifier; or priority, preemption modifier, and timestamp for the stable variant), so no comparator is taken and the head is simply zeroed. PRIORITY_QUEUE_INITIALIZER gives equivalent static initialization; element linkages are prepared separately with priority_queue_entry_init.

function_priority_queue_destroy

PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_min *, priority_queue_entry_deadline_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Implementation routine behind the priority_queue_destroy macro; overloaded for all eight priority queue types. Destroys a priority queue safely, invoking the supplied cleanup block on every element; the offset argument, offsetof(type, field) of the linkage within the element, is filled in by the macro. The queue does not maintain its heap invariants while being destroyed, and both the queue head and the linkage nodes must be re-initialized (priority_queue_init, priority_queue_entry_init) before reuse. Callers use priority_queue_destroy(pq, type, field, callback) rather than this routine directly.

functionpriority_queue_insert

PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_min *, priority_queue_entry_deadline_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Inserts an element into the priority queue; overloaded for all eight pairing-heap queue types. The caller must have set the entry's key before insertion: comparator-visible state for the generic heaps, the deadline field for deadline heaps, or priority_queue_entry_set_sched_pri for the sched and sched_stable heaps. Returns whether the inserted element became the new root (the new minimum of a min-heap or maximum of a max-heap). Insertion is O(1). The heaps are not stable by default; only the sched_stable variants break priority ties using a preemption modifier and timestamp.

function_priority_queue_remove_root

PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_min *, priority_queue_entry_deadline_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Removes the root entry of the pairing heap and returns its linkage pointer, NULL if the queue is empty; overloaded for all eight priority queue types. Backs the priority_queue_remove_min and priority_queue_remove_max macros, which statically assert the heap direction and convert the returned linkage to the containing element with pqe_element. The root is the minimum element of a min-heap or the maximum of a max-heap; removal is amortized O(log n).

functionpriority_queue_remove

PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_min *, priority_queue_entry_deadline_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Removes an arbitrary element from the priority queue given its linkage entry; overloaded for all eight pairing-heap queue types. Returns whether the removed element was the root of the heap, letting scheduler callers notice when the minimum (or maximum) changed. Removal from a pairing heap is amortized O(log n).

functionpriority_queue_entry_decreased

PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_min *, priority_queue_entry_deadline_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Signals the priority queue that an entry's priority has decreased so the pairing heap can restore its invariants; overloaded for all eight queue types. The new value for the element's priority must have been set before calling (comparator-visible state, the deadline field, or priority_queue_entry_set_sched_pri, according to the queue subtype). Returns whether the update caused the root or its key to change. Counterpart of priority_queue_entry_increased.

functionpriority_queue_entry_increased

PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_min *, priority_queue_entry_deadline_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Signals the priority queue that an entry's priority has increased so the pairing heap can restore its invariants; overloaded for all eight queue types. The new value for the element's priority must have been set before calling (comparator-visible state, the deadline field, or priority_queue_entry_set_sched_pri, according to the queue subtype). Returns whether the update caused the root or its key to change. Counterpart of priority_queue_entry_decreased.

functionpriority_queue_init

PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_max *, priority_queue_entry_deadline_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Initializes a priority queue head. The kernel's priority queues are pairing heaps (O(1) insertion, amortized O(log n) deletion) declared as struct priority_queue_<subtype>_<min|max>; this initializer is overloaded for all eight types. For the generic priority_queue_min and priority_queue_max heaps it takes a priority_queue_compare_fn_t comparator block in addition to the queue, storing it for later ordering decisions and setting the root to NULL. For the deadline, sched, and sched_stable specializations the key lives in the entry linkage itself (a 64-bit deadline; a scheduler priority packed with a PRIORITY_QUEUE_ENTRY_PREEMPTED modifier; or priority, preemption modifier, and timestamp for the stable variant), so no comparator is taken and the head is simply zeroed. PRIORITY_QUEUE_INITIALIZER gives equivalent static initialization; element linkages are prepared separately with priority_queue_entry_init.

function_priority_queue_destroy

PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_max *, priority_queue_entry_deadline_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Implementation routine behind the priority_queue_destroy macro; overloaded for all eight priority queue types. Destroys a priority queue safely, invoking the supplied cleanup block on every element; the offset argument, offsetof(type, field) of the linkage within the element, is filled in by the macro. The queue does not maintain its heap invariants while being destroyed, and both the queue head and the linkage nodes must be re-initialized (priority_queue_init, priority_queue_entry_init) before reuse. Callers use priority_queue_destroy(pq, type, field, callback) rather than this routine directly.

functionpriority_queue_insert

PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_max *, priority_queue_entry_deadline_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Inserts an element into the priority queue; overloaded for all eight pairing-heap queue types. The caller must have set the entry's key before insertion: comparator-visible state for the generic heaps, the deadline field for deadline heaps, or priority_queue_entry_set_sched_pri for the sched and sched_stable heaps. Returns whether the inserted element became the new root (the new minimum of a min-heap or maximum of a max-heap). Insertion is O(1). The heaps are not stable by default; only the sched_stable variants break priority ties using a preemption modifier and timestamp.

function_priority_queue_remove_root

PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_max *, priority_queue_entry_deadline_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Removes the root entry of the pairing heap and returns its linkage pointer, NULL if the queue is empty; overloaded for all eight priority queue types. Backs the priority_queue_remove_min and priority_queue_remove_max macros, which statically assert the heap direction and convert the returned linkage to the containing element with pqe_element. The root is the minimum element of a min-heap or the maximum of a max-heap; removal is amortized O(log n).

functionpriority_queue_remove

PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_max *, priority_queue_entry_deadline_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Removes an arbitrary element from the priority queue given its linkage entry; overloaded for all eight pairing-heap queue types. Returns whether the removed element was the root of the heap, letting scheduler callers notice when the minimum (or maximum) changed. Removal from a pairing heap is amortized O(log n).

functionpriority_queue_entry_decreased

PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_max *, priority_queue_entry_deadline_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Signals the priority queue that an entry's priority has decreased so the pairing heap can restore its invariants; overloaded for all eight queue types. The new value for the element's priority must have been set before calling (comparator-visible state, the deadline field, or priority_queue_entry_set_sched_pri, according to the queue subtype). Returns whether the update caused the root or its key to change. Counterpart of priority_queue_entry_increased.

functionpriority_queue_entry_increased

PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_max *, priority_queue_entry_deadline_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Signals the priority queue that an entry's priority has increased so the pairing heap can restore its invariants; overloaded for all eight queue types. The new value for the element's priority must have been set before calling (comparator-visible state, the deadline field, or priority_queue_entry_set_sched_pri, according to the queue subtype). Returns whether the update caused the root or its key to change. Counterpart of priority_queue_entry_decreased.

functionpriority_queue_init

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_min *, priority_queue_entry_sched_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Initializes a priority queue head. The kernel's priority queues are pairing heaps (O(1) insertion, amortized O(log n) deletion) declared as struct priority_queue_<subtype>_<min|max>; this initializer is overloaded for all eight types. For the generic priority_queue_min and priority_queue_max heaps it takes a priority_queue_compare_fn_t comparator block in addition to the queue, storing it for later ordering decisions and setting the root to NULL. For the deadline, sched, and sched_stable specializations the key lives in the entry linkage itself (a 64-bit deadline; a scheduler priority packed with a PRIORITY_QUEUE_ENTRY_PREEMPTED modifier; or priority, preemption modifier, and timestamp for the stable variant), so no comparator is taken and the head is simply zeroed. PRIORITY_QUEUE_INITIALIZER gives equivalent static initialization; element linkages are prepared separately with priority_queue_entry_init.

function_priority_queue_destroy

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_min *, priority_queue_entry_sched_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Implementation routine behind the priority_queue_destroy macro; overloaded for all eight priority queue types. Destroys a priority queue safely, invoking the supplied cleanup block on every element; the offset argument, offsetof(type, field) of the linkage within the element, is filled in by the macro. The queue does not maintain its heap invariants while being destroyed, and both the queue head and the linkage nodes must be re-initialized (priority_queue_init, priority_queue_entry_init) before reuse. Callers use priority_queue_destroy(pq, type, field, callback) rather than this routine directly.

functionpriority_queue_insert

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_min *, priority_queue_entry_sched_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Inserts an element into the priority queue; overloaded for all eight pairing-heap queue types. The caller must have set the entry's key before insertion: comparator-visible state for the generic heaps, the deadline field for deadline heaps, or priority_queue_entry_set_sched_pri for the sched and sched_stable heaps. Returns whether the inserted element became the new root (the new minimum of a min-heap or maximum of a max-heap). Insertion is O(1). The heaps are not stable by default; only the sched_stable variants break priority ties using a preemption modifier and timestamp.

function_priority_queue_remove_root

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_min *, priority_queue_entry_sched_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Removes the root entry of the pairing heap and returns its linkage pointer, NULL if the queue is empty; overloaded for all eight priority queue types. Backs the priority_queue_remove_min and priority_queue_remove_max macros, which statically assert the heap direction and convert the returned linkage to the containing element with pqe_element. The root is the minimum element of a min-heap or the maximum of a max-heap; removal is amortized O(log n).

functionpriority_queue_remove

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_min *, priority_queue_entry_sched_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Removes an arbitrary element from the priority queue given its linkage entry; overloaded for all eight pairing-heap queue types. Returns whether the removed element was the root of the heap, letting scheduler callers notice when the minimum (or maximum) changed. Removal from a pairing heap is amortized O(log n).

functionpriority_queue_entry_decreased

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_min *, priority_queue_entry_sched_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Signals the priority queue that an entry's priority has decreased so the pairing heap can restore its invariants; overloaded for all eight queue types. The new value for the element's priority must have been set before calling (comparator-visible state, the deadline field, or priority_queue_entry_set_sched_pri, according to the queue subtype). Returns whether the update caused the root or its key to change. Counterpart of priority_queue_entry_increased.

functionpriority_queue_entry_increased

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_min *, priority_queue_entry_sched_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Signals the priority queue that an entry's priority has increased so the pairing heap can restore its invariants; overloaded for all eight queue types. The new value for the element's priority must have been set before calling (comparator-visible state, the deadline field, or priority_queue_entry_set_sched_pri, according to the queue subtype). Returns whether the update caused the root or its key to change. Counterpart of priority_queue_entry_decreased.

functionpriority_queue_init

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_max *, priority_queue_entry_sched_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Initializes a priority queue head. The kernel's priority queues are pairing heaps (O(1) insertion, amortized O(log n) deletion) declared as struct priority_queue_<subtype>_<min|max>; this initializer is overloaded for all eight types. For the generic priority_queue_min and priority_queue_max heaps it takes a priority_queue_compare_fn_t comparator block in addition to the queue, storing it for later ordering decisions and setting the root to NULL. For the deadline, sched, and sched_stable specializations the key lives in the entry linkage itself (a 64-bit deadline; a scheduler priority packed with a PRIORITY_QUEUE_ENTRY_PREEMPTED modifier; or priority, preemption modifier, and timestamp for the stable variant), so no comparator is taken and the head is simply zeroed. PRIORITY_QUEUE_INITIALIZER gives equivalent static initialization; element linkages are prepared separately with priority_queue_entry_init.

function_priority_queue_destroy

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_max *, priority_queue_entry_sched_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Implementation routine behind the priority_queue_destroy macro; overloaded for all eight priority queue types. Destroys a priority queue safely, invoking the supplied cleanup block on every element; the offset argument, offsetof(type, field) of the linkage within the element, is filled in by the macro. The queue does not maintain its heap invariants while being destroyed, and both the queue head and the linkage nodes must be re-initialized (priority_queue_init, priority_queue_entry_init) before reuse. Callers use priority_queue_destroy(pq, type, field, callback) rather than this routine directly.

functionpriority_queue_insert

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_max *, priority_queue_entry_sched_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Inserts an element into the priority queue; overloaded for all eight pairing-heap queue types. The caller must have set the entry's key before insertion: comparator-visible state for the generic heaps, the deadline field for deadline heaps, or priority_queue_entry_set_sched_pri for the sched and sched_stable heaps. Returns whether the inserted element became the new root (the new minimum of a min-heap or maximum of a max-heap). Insertion is O(1). The heaps are not stable by default; only the sched_stable variants break priority ties using a preemption modifier and timestamp.

function_priority_queue_remove_root

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_max *, priority_queue_entry_sched_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Removes the root entry of the pairing heap and returns its linkage pointer, NULL if the queue is empty; overloaded for all eight priority queue types. Backs the priority_queue_remove_min and priority_queue_remove_max macros, which statically assert the heap direction and convert the returned linkage to the containing element with pqe_element. The root is the minimum element of a min-heap or the maximum of a max-heap; removal is amortized O(log n).

functionpriority_queue_remove

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_max *, priority_queue_entry_sched_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Removes an arbitrary element from the priority queue given its linkage entry; overloaded for all eight pairing-heap queue types. Returns whether the removed element was the root of the heap, letting scheduler callers notice when the minimum (or maximum) changed. Removal from a pairing heap is amortized O(log n).

functionpriority_queue_entry_decreased

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_max *, priority_queue_entry_sched_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Signals the priority queue that an entry's priority has decreased so the pairing heap can restore its invariants; overloaded for all eight queue types. The new value for the element's priority must have been set before calling (comparator-visible state, the deadline field, or priority_queue_entry_set_sched_pri, according to the queue subtype). Returns whether the update caused the root or its key to change. Counterpart of priority_queue_entry_increased.

functionpriority_queue_entry_increased

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_max *, priority_queue_entry_sched_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Signals the priority queue that an entry's priority has increased so the pairing heap can restore its invariants; overloaded for all eight queue types. The new value for the element's priority must have been set before calling (comparator-visible state, the deadline field, or priority_queue_entry_set_sched_pri, according to the queue subtype). Returns whether the update caused the root or its key to change. Counterpart of priority_queue_entry_decreased.

functionpriority_queue_init

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_min *, priority_queue_entry_stable_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Initializes a priority queue head. The kernel's priority queues are pairing heaps (O(1) insertion, amortized O(log n) deletion) declared as struct priority_queue_<subtype>_<min|max>; this initializer is overloaded for all eight types. For the generic priority_queue_min and priority_queue_max heaps it takes a priority_queue_compare_fn_t comparator block in addition to the queue, storing it for later ordering decisions and setting the root to NULL. For the deadline, sched, and sched_stable specializations the key lives in the entry linkage itself (a 64-bit deadline; a scheduler priority packed with a PRIORITY_QUEUE_ENTRY_PREEMPTED modifier; or priority, preemption modifier, and timestamp for the stable variant), so no comparator is taken and the head is simply zeroed. PRIORITY_QUEUE_INITIALIZER gives equivalent static initialization; element linkages are prepared separately with priority_queue_entry_init.

function_priority_queue_destroy

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_min *, priority_queue_entry_stable_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Implementation routine behind the priority_queue_destroy macro; overloaded for all eight priority queue types. Destroys a priority queue safely, invoking the supplied cleanup block on every element; the offset argument, offsetof(type, field) of the linkage within the element, is filled in by the macro. The queue does not maintain its heap invariants while being destroyed, and both the queue head and the linkage nodes must be re-initialized (priority_queue_init, priority_queue_entry_init) before reuse. Callers use priority_queue_destroy(pq, type, field, callback) rather than this routine directly.

functionpriority_queue_insert

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_min *, priority_queue_entry_stable_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Inserts an element into the priority queue; overloaded for all eight pairing-heap queue types. The caller must have set the entry's key before insertion: comparator-visible state for the generic heaps, the deadline field for deadline heaps, or priority_queue_entry_set_sched_pri for the sched and sched_stable heaps. Returns whether the inserted element became the new root (the new minimum of a min-heap or maximum of a max-heap). Insertion is O(1). The heaps are not stable by default; only the sched_stable variants break priority ties using a preemption modifier and timestamp.

function_priority_queue_remove_root

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_min *, priority_queue_entry_stable_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Removes the root entry of the pairing heap and returns its linkage pointer, NULL if the queue is empty; overloaded for all eight priority queue types. Backs the priority_queue_remove_min and priority_queue_remove_max macros, which statically assert the heap direction and convert the returned linkage to the containing element with pqe_element. The root is the minimum element of a min-heap or the maximum of a max-heap; removal is amortized O(log n).

functionpriority_queue_remove

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_min *, priority_queue_entry_stable_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Removes an arbitrary element from the priority queue given its linkage entry; overloaded for all eight pairing-heap queue types. Returns whether the removed element was the root of the heap, letting scheduler callers notice when the minimum (or maximum) changed. Removal from a pairing heap is amortized O(log n).

functionpriority_queue_entry_decreased

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_min *, priority_queue_entry_stable_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Signals the priority queue that an entry's priority has decreased so the pairing heap can restore its invariants; overloaded for all eight queue types. The new value for the element's priority must have been set before calling (comparator-visible state, the deadline field, or priority_queue_entry_set_sched_pri, according to the queue subtype). Returns whether the update caused the root or its key to change. Counterpart of priority_queue_entry_increased.

functionpriority_queue_entry_increased

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_min *, priority_queue_entry_stable_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Signals the priority queue that an entry's priority has increased so the pairing heap can restore its invariants; overloaded for all eight queue types. The new value for the element's priority must have been set before calling (comparator-visible state, the deadline field, or priority_queue_entry_set_sched_pri, according to the queue subtype). Returns whether the update caused the root or its key to change. Counterpart of priority_queue_entry_decreased.

functionpriority_queue_init

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_max *, priority_queue_entry_stable_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Initializes a priority queue head. The kernel's priority queues are pairing heaps (O(1) insertion, amortized O(log n) deletion) declared as struct priority_queue_<subtype>_<min|max>; this initializer is overloaded for all eight types. For the generic priority_queue_min and priority_queue_max heaps it takes a priority_queue_compare_fn_t comparator block in addition to the queue, storing it for later ordering decisions and setting the root to NULL. For the deadline, sched, and sched_stable specializations the key lives in the entry linkage itself (a 64-bit deadline; a scheduler priority packed with a PRIORITY_QUEUE_ENTRY_PREEMPTED modifier; or priority, preemption modifier, and timestamp for the stable variant), so no comparator is taken and the head is simply zeroed. PRIORITY_QUEUE_INITIALIZER gives equivalent static initialization; element linkages are prepared separately with priority_queue_entry_init.

function_priority_queue_destroy

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_max *, priority_queue_entry_stable_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Implementation routine behind the priority_queue_destroy macro; overloaded for all eight priority queue types. Destroys a priority queue safely, invoking the supplied cleanup block on every element; the offset argument, offsetof(type, field) of the linkage within the element, is filled in by the macro. The queue does not maintain its heap invariants while being destroyed, and both the queue head and the linkage nodes must be re-initialized (priority_queue_init, priority_queue_entry_init) before reuse. Callers use priority_queue_destroy(pq, type, field, callback) rather than this routine directly.

functionpriority_queue_insert

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_max *, priority_queue_entry_stable_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Inserts an element into the priority queue; overloaded for all eight pairing-heap queue types. The caller must have set the entry's key before insertion: comparator-visible state for the generic heaps, the deadline field for deadline heaps, or priority_queue_entry_set_sched_pri for the sched and sched_stable heaps. Returns whether the inserted element became the new root (the new minimum of a min-heap or maximum of a max-heap). Insertion is O(1). The heaps are not stable by default; only the sched_stable variants break priority ties using a preemption modifier and timestamp.

function_priority_queue_remove_root

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_max *, priority_queue_entry_stable_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Removes the root entry of the pairing heap and returns its linkage pointer, NULL if the queue is empty; overloaded for all eight priority queue types. Backs the priority_queue_remove_min and priority_queue_remove_max macros, which statically assert the heap direction and convert the returned linkage to the containing element with pqe_element. The root is the minimum element of a min-heap or the maximum of a max-heap; removal is amortized O(log n).

functionpriority_queue_remove

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_max *, priority_queue_entry_stable_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Removes an arbitrary element from the priority queue given its linkage entry; overloaded for all eight pairing-heap queue types. Returns whether the removed element was the root of the heap, letting scheduler callers notice when the minimum (or maximum) changed. Removal from a pairing heap is amortized O(log n).

functionpriority_queue_entry_decreased

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_max *, priority_queue_entry_stable_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Signals the priority queue that an entry's priority has decreased so the pairing heap can restore its invariants; overloaded for all eight queue types. The new value for the element's priority must have been set before calling (comparator-visible state, the deadline field, or priority_queue_entry_set_sched_pri, according to the queue subtype). Returns whether the update caused the root or its key to change. Counterpart of priority_queue_entry_increased.

functionpriority_queue_entry_increased

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_max *, priority_queue_entry_stable_t)
▾
claude-fable-5, 2026-08-24 · not from Apple sources · verified against xnu osfmk/kern/priority_queue.h
Signals the priority queue that an entry's priority has increased so the pairing heap can restore its invariants; overloaded for all eight queue types. The new value for the element's priority must have been set before calling (comparator-visible state, the deadline field, or priority_queue_entry_set_sched_pri, according to the queue subtype). Returns whether the update caused the root or its key to change. Counterpart of priority_queue_entry_decreased.