7#ifndef _PICO_UTIL_PHEAP_H
8#define _PICO_UTIL_PHEAP_H
17#ifndef PARAM_ASSERTIONS_ENABLED_PHEAP
18#define PARAM_ASSERTIONS_ENABLED_PHEAP 0
38#ifndef PICO_PHEAP_MAX_ENTRIES
39#define PICO_PHEAP_MAX_ENTRIES 255
43#if PICO_PHEAP_MAX_ENTRIES < 256
44typedef uint8_t pheap_node_id_t;
45#elif PICO_PHEAP_MAX_ENTRIES < 65535
46typedef uint16_t pheap_node_id_t;
48#error invalid PICO_PHEAP_MAX_ENTRIES
52 pheap_node_id_t child, sibling, parent;
61typedef bool (*
pheap_comparator)(
void *user_data, pheap_node_id_t a, pheap_node_id_t b);
67 pheap_node_id_t max_nodes;
68 pheap_node_id_t root_id;
70 pheap_node_id_t free_head_id;
71 pheap_node_id_t free_tail_id;
108 assert(
id && id <= heap->max_nodes);
109 return heap->nodes +
id - 1;
113static void ph_add_child_node(
pheap_t *heap, pheap_node_id_t parent_id, pheap_node_id_t child_id) {
117 assert(parent_id != child_id);
119 c->parent = parent_id;
123 c->sibling = n->child;
129static pheap_node_id_t ph_merge_nodes(
pheap_t *heap, pheap_node_id_t a, pheap_node_id_t b) {
132 if (heap->comparator(heap->user_data, a, b)) {
133 ph_add_child_node(heap, a, b);
136 ph_add_child_node(heap, b, a);
149 if (!heap->free_head_id)
return 0;
150 pheap_node_id_t
id = heap->free_head_id;
152 heap->free_head_id = hn->sibling;
153 if (!heap->free_head_id) heap->free_tail_id = 0;
154 hn->child = hn->sibling = hn->parent = 0;
173 hn->child = hn->sibling = hn->parent = 0;
174 heap->root_id = ph_merge_nodes(heap, heap->root_id,
id);
175 return heap->root_id;
187 return heap->root_id;
246 return id == heap->root_id || ph_get_node(heap,
id)->parent;
259 if (heap->free_tail_id) {
260 ph_get_node(heap, heap->free_tail_id)->sibling = id;
262 if (!heap->free_head_id) {
263 assert(!heap->free_tail_id);
264 heap->free_head_id = id;
266 heap->free_tail_id = id;
277void ph_dump(
pheap_t *heap,
void (*dump_key)(pheap_node_id_t
id,
void *user_data),
void *user_data);
296#define PHEAP_DEFINE_STATIC(name, _max_nodes) \
297 static_assert(_max_nodes && _max_nodes < (1u << (8 * sizeof(pheap_node_id_t))), ""); \
298 static pheap_node_t name ## _nodes[_max_nodes]; \
299 static pheap_t name = { \
300 .nodes = name ## _nodes, \
301 .max_nodes = _max_nodes \
bool(* pheap_comparator)(void *user_data, pheap_node_id_t a, pheap_node_id_t b)
A user comparator function for nodes in a pairing heap.
Definition pheap.h:61
void ph_destroy(pheap_t *heap)
De-allocates a pairing heap.
Definition pheap.c:37
static void ph_free_node(pheap_t *heap, pheap_node_id_t id)
Free a node that is not currently in the heap, but has been allocated.
Definition pheap.h:257
void ph_clear(pheap_t *heap)
Removes all nodes from the pairing heap.
Definition pheap.c:27
void ph_post_alloc_init(pheap_t *heap, uint max_nodes, pheap_comparator comparator, void *user_data)
Initialize a statically allocated heap (ph_create() using the C heap). The heap member nodes must be ...
Definition pheap.c:19
static bool ph_contains_node(pheap_t *heap, pheap_node_id_t id)
Determine if the heap contains a given node. Note containment refers to whether the node is inserted ...
Definition pheap.h:245
bool ph_remove_and_free_node(pheap_t *heap, pheap_node_id_t id)
Remove and free an arbitrary node from the pairing heap. This is a more costly operation than removin...
Definition pheap.c:82
pheap_node_id_t ph_remove_head(pheap_t *heap, bool free)
Remove the head node from the pairing heap. This head node is the node which compares first in the lo...
Definition pheap.c:76
static pheap_node_id_t ph_peek_head(pheap_t *heap)
Returns the head node in the heap, i.e. the node which compares first, but without removing it from t...
Definition pheap.h:186
void ph_dump(pheap_t *heap, void(*dump_key)(pheap_node_id_t id, void *user_data), void *user_data)
Print a representation of the heap for debugging.
static pheap_node_id_t ph_insert_node(pheap_t *heap, pheap_node_id_t id)
Inserts a node into the heap.
Definition pheap.h:170
pheap_t * ph_create(uint max_nodes, pheap_comparator comparator, void *user_data)
Create a pairing heap, which effectively maintains an efficient sorted ordering of nodes....
Definition pheap.c:11
static pheap_node_id_t ph_remove_and_free_head(pheap_t *heap)
Remove the head node from the pairing heap. This head node is the node which compares first in the lo...
Definition pheap.h:221
static pheap_node_id_t ph_new_node(pheap_t *heap)
Allocate a new node from the unused space in the heap.
Definition pheap.h:148