@web-font-path: "roboto-debian.css";
v2.2.0 (RP2040)
Loading...
Searching...
No Matches
pheap.h
Go to the documentation of this file.
/*
* Copyright (c) 2020 Raspberry Pi (Trading) Ltd.
*
* SPDX-License-Identifier: BSD-3-Clause
*/
#ifndef _PICO_UTIL_PHEAP_H
#define _PICO_UTIL_PHEAP_H
#include "pico.h"
#ifdef __cplusplus
extern "C" {
#endif
// PICO_CONFIG: PARAM_ASSERTIONS_ENABLED_PHEAP, Enable/disable assertions in the pheap module, type=bool, default=0, group=pico_util
#ifndef PARAM_ASSERTIONS_ENABLED_PHEAP
#define PARAM_ASSERTIONS_ENABLED_PHEAP 0
#endif
// PICO_CONFIG: PICO_PHEAP_MAX_ENTRIES, Maximum number of entries in the pheap, min=1, max=65534, default=255, group=pico_util
#ifndef PICO_PHEAP_MAX_ENTRIES
#define PICO_PHEAP_MAX_ENTRIES 255
#endif
// public heap_node ids are numbered from 1 (0 means none)
#if PICO_PHEAP_MAX_ENTRIES < 256
typedef uint8_t pheap_node_id_t;
#elif PICO_PHEAP_MAX_ENTRIES < 65535
typedef uint16_t pheap_node_id_t;
#else
#error invalid PICO_PHEAP_MAX_ENTRIES
#endif
typedef struct pheap_node {
pheap_node_id_t child, sibling, parent;
} pheap_node_t;
typedef bool (*pheap_comparator)(void *user_data, pheap_node_id_t a, pheap_node_id_t b);
typedef struct pheap {
pheap_node_t *nodes;
pheap_comparator comparator;
void *user_data;
pheap_node_id_t max_nodes;
pheap_node_id_t root_id;
// we remove from head and add to tail to stop reusing the same ids
pheap_node_id_t free_head_id;
pheap_node_id_t free_tail_id;
} pheap_t;
pheap_t *ph_create(uint max_nodes, pheap_comparator comparator, void *user_data);
void ph_clear(pheap_t *heap);
void ph_destroy(pheap_t *heap);
// internal method
static inline pheap_node_t *ph_get_node(pheap_t *heap, pheap_node_id_t id) {
assert(id && id <= heap->max_nodes);
return heap->nodes + id - 1;
}
// internal method
static void ph_add_child_node(pheap_t *heap, pheap_node_id_t parent_id, pheap_node_id_t child_id) {
pheap_node_t *n = ph_get_node(heap, parent_id);
assert(parent_id);
assert(child_id);
assert(parent_id != child_id);
pheap_node_t *c = ph_get_node(heap, child_id);
c->parent = parent_id;
if (!n->child) {
n->child = child_id;
} else {
c->sibling = n->child;
n->child = child_id;
}
}
// internal method
static pheap_node_id_t ph_merge_nodes(pheap_t *heap, pheap_node_id_t a, pheap_node_id_t b) {
if (!a) return b;
if (!b) return a;
if (heap->comparator(heap->user_data, a, b)) {
ph_add_child_node(heap, a, b);
return a;
} else {
ph_add_child_node(heap, b, a);
return b;
}
}
static inline pheap_node_id_t ph_new_node(pheap_t *heap) {
if (!heap->free_head_id) return 0;
pheap_node_id_t id = heap->free_head_id;
pheap_node_t *hn = ph_get_node(heap, id);
heap->free_head_id = hn->sibling;
if (!heap->free_head_id) heap->free_tail_id = 0;
hn->child = hn->sibling = hn->parent = 0;
return id;
}
static inline pheap_node_id_t ph_insert_node(pheap_t *heap, pheap_node_id_t id) {
assert(id);
pheap_node_t *hn = ph_get_node(heap, id);
hn->child = hn->sibling = hn->parent = 0;
heap->root_id = ph_merge_nodes(heap, heap->root_id, id);
return heap->root_id;
}
static inline pheap_node_id_t ph_peek_head(pheap_t *heap) {
return heap->root_id;
}
pheap_node_id_t ph_remove_head(pheap_t *heap, bool free);
static inline pheap_node_id_t ph_remove_and_free_head(pheap_t *heap) {
return ph_remove_head(heap, true);
}
bool ph_remove_and_free_node(pheap_t *heap, pheap_node_id_t id);
static inline bool ph_contains_node(pheap_t *heap, pheap_node_id_t id) {
return id == heap->root_id || ph_get_node(heap, id)->parent;
}
static inline void ph_free_node(pheap_t *heap, pheap_node_id_t id) {
assert(id && !ph_contains_node(heap, id));
if (heap->free_tail_id) {
ph_get_node(heap, heap->free_tail_id)->sibling = id;
}
if (!heap->free_head_id) {
assert(!heap->free_tail_id);
heap->free_head_id = id;
}
heap->free_tail_id = id;
}
void ph_dump(pheap_t *heap, void (*dump_key)(pheap_node_id_t id, void *user_data), void *user_data);
void ph_post_alloc_init(pheap_t *heap, uint max_nodes, pheap_comparator comparator, void *user_data);
#define PHEAP_DEFINE_STATIC(name, _max_nodes) \
static_assert(_max_nodes && _max_nodes < (1u << (8 * sizeof(pheap_node_id_t))), ""); \
static pheap_node_t name ## _nodes[_max_nodes]; \
static pheap_t name = { \
.nodes = name ## _nodes, \
.max_nodes = _max_nodes \
};
#ifdef __cplusplus
}
#endif
#endif
pheap_comparator
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
ph_destroy
void ph_destroy(pheap_t *heap)
De-allocates a pairing heap.
Definition pheap.c:37
ph_free_node
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
ph_clear
void ph_clear(pheap_t *heap)
Removes all nodes from the pairing heap.
Definition pheap.c:27
ph_post_alloc_init
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
ph_contains_node
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
ph_remove_and_free_node
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
ph_remove_head
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
ph_peek_head
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
ph_dump
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.
Definition pheap.c:135
ph_insert_node
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
ph_create
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
ph_remove_and_free_head
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
ph_new_node
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
pico.h
pheap_node
Definition pheap.h:51
pheap
Definition pheap.h:63