1 /*
2 * Copyright (c) 2020 Raspberry Pi (Trading) Ltd.
3 *
4 * SPDX-License-Identifier: BSD-3-Clause
5 */
6
7 #ifndef _PICO_UTIL_PHEAP_H
8 #define _PICO_UTIL_PHEAP_H
9
10 #include "pico.h"
11
12 #ifdef __cplusplus
13 extern "C" {
14 #endif
15
16 // PICO_CONFIG: PARAM_ASSERTIONS_ENABLED_PHEAP, Enable/disable assertions in the pheap module, type=bool, default=0, group=pico_util
17 #ifndef PARAM_ASSERTIONS_ENABLED_PHEAP
18 #define PARAM_ASSERTIONS_ENABLED_PHEAP 0
19 #endif
20
21 /**
22 * \file pheap.h
23 * \defgroup util_pheap pheap
24 * \brief Pairing Heap Implementation
25 * \ingroup pico_util
26 *
27 * pheap defines a simple pairing heap. The implementation simply tracks array indexes, it is up to
28 * the user to provide storage for heap entries and a comparison function.
29 *
30 * NOTE: This class is not safe for concurrent usage. It should be externally protected. Furthermore
31 * if used concurrently, the caller needs to protect around their use of the returned id.
32 * For example, ph_remove_and_free_head returns the id of an element that is no longer in the heap.
33 * The user can still use this to look at the data in their companion array, however obviously further operations
34 * on the heap may cause them to overwrite that data as the id may be reused on subsequent operations
35 *
36 */
37 // PICO_CONFIG: PICO_PHEAP_MAX_ENTRIES, Maximum number of entries in the pheap, min=1, max=65534, default=255, group=pico_util
38 #ifndef PICO_PHEAP_MAX_ENTRIES
39 #define PICO_PHEAP_MAX_ENTRIES 255
40 #endif
41
42 // public heap_node ids are numbered from 1 (0 means none)
43 #if PICO_PHEAP_MAX_ENTRIES < 256
44 typedef uint8_t pheap_node_id_t;
45 #elif PICO_PHEAP_MAX_ENTRIES < 65535
46 typedef uint16_t pheap_node_id_t;
47 #else
48 #error invalid PICO_PHEAP_MAX_ENTRIES
49 #endif
50
51 typedef struct pheap_node {
52 pheap_node_id_t child, sibling, parent;
53 } pheap_node_t;
54
55 /**
56 * \brief A user comparator function for nodes in a pairing heap.
57 * \ingroup util_pheap
58 *
59 * \return true if a < b in natural order. Note this relative ordering must be stable from call to call.
60 */
61 typedef bool (*pheap_comparator)(void *user_data, pheap_node_id_t a, pheap_node_id_t b);
62
63 typedef struct pheap {
64 pheap_node_t *nodes;
65 pheap_comparator comparator;
66 void *user_data;
67 pheap_node_id_t max_nodes;
68 pheap_node_id_t root_id;
69 // we remove from head and add to tail to stop reusing the same ids
70 pheap_node_id_t free_head_id;
71 pheap_node_id_t free_tail_id;
72 } pheap_t;
73
74 /**
75 * \brief Create a pairing heap, which effectively maintains an efficient sorted ordering
76 * of nodes. The heap itself stores no user per-node state, it is expected
77 * that the user maintains a companion array. A comparator function must
78 * be provided so that the heap implementation can determine the relative ordering of nodes
79 * \ingroup util_pheap
80 *
81 * \param max_nodes the maximum number of nodes that may be in the heap (this is bounded by
82 * PICO_PHEAP_MAX_ENTRIES which defaults to 255 to be able to store indexes
83 * in a single byte).
84 * \param comparator the node comparison function
85 * \param user_data a user data pointer associated with the heap that is provided in callbacks
86 * \return a newly allocated and initialized heap
87 */
88 pheap_t *ph_create(uint max_nodes, pheap_comparator comparator, void *user_data);
89
90 /**
91 * \brief Removes all nodes from the pairing heap
92 * \ingroup util_pheap
93 * \param heap the heap
94 */
95 void ph_clear(pheap_t *heap);
96
97 /**
98 * \brief De-allocates a pairing heap
99 * \ingroup util_pheap
100 *
101 * Note this method must *ONLY* be called on heaps created by ph_create()
102 * \param heap the heap
103 */
104 void ph_destroy(pheap_t *heap);
105
106 // internal method
ph_get_node(pheap_t * heap,pheap_node_id_t id)107 static inline pheap_node_t *ph_get_node(pheap_t *heap, pheap_node_id_t id) {
108 assert(id && id <= heap->max_nodes);
109 return heap->nodes + id - 1;
110 }
111
112 // internal method
ph_add_child_node(pheap_t * heap,pheap_node_id_t parent_id,pheap_node_id_t child_id)113 static void ph_add_child_node(pheap_t *heap, pheap_node_id_t parent_id, pheap_node_id_t child_id) {
114 pheap_node_t *n = ph_get_node(heap, parent_id);
115 assert(parent_id);
116 assert(child_id);
117 assert(parent_id != child_id);
118 pheap_node_t *c = ph_get_node(heap, child_id);
119 c->parent = parent_id;
120 if (!n->child) {
121 n->child = child_id;
122 } else {
123 c->sibling = n->child;
124 n->child = child_id;
125 }
126 }
127
128 // internal method
ph_merge_nodes(pheap_t * heap,pheap_node_id_t a,pheap_node_id_t b)129 static pheap_node_id_t ph_merge_nodes(pheap_t *heap, pheap_node_id_t a, pheap_node_id_t b) {
130 if (!a) return b;
131 if (!b) return a;
132 if (heap->comparator(heap->user_data, a, b)) {
133 ph_add_child_node(heap, a, b);
134 return a;
135 } else {
136 ph_add_child_node(heap, b, a);
137 return b;
138 }
139 }
140
141 /**
142 * \brief Allocate a new node from the unused space in the heap
143 * \ingroup util_pheap
144 *
145 * \param heap the heap
146 * \return an identifier for the node, or 0 if the heap is full
147 */
ph_new_node(pheap_t * heap)148 static inline pheap_node_id_t ph_new_node(pheap_t *heap) {
149 if (!heap->free_head_id) return 0;
150 pheap_node_id_t id = heap->free_head_id;
151 pheap_node_t *hn = ph_get_node(heap, 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;
155 return id;
156 }
157
158 /**
159 * \brief Inserts a node into the heap.
160 * \ingroup util_pheap
161 *
162 * This method inserts a node (previously allocated by ph_new_node())
163 * into the heap, determining the correct order by calling
164 * the heap's comparator
165 *
166 * \param heap the heap
167 * \param id the id of the node to insert
168 * \return the id of the new head of the pairing heap (i.e. node that compares first)
169 */
ph_insert_node(pheap_t * heap,pheap_node_id_t id)170 static inline pheap_node_id_t ph_insert_node(pheap_t *heap, pheap_node_id_t id) {
171 assert(id);
172 pheap_node_t *hn = ph_get_node(heap, id);
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;
176 }
177
178 /**
179 * \brief Returns the head node in the heap, i.e. the node
180 * which compares first, but without removing it from the heap.
181 * \ingroup util_pheap
182 *
183 * \param heap the heap
184 * \return the current head node id
185 */
ph_peek_head(pheap_t * heap)186 static inline pheap_node_id_t ph_peek_head(pheap_t *heap) {
187 return heap->root_id;
188 }
189
190 /**
191 * \brief Remove the head node from the pairing heap. This head node is
192 * the node which compares first in the logical ordering provided
193 * by the comparator.
194 * \ingroup util_pheap
195 *
196 * Note that in the case of free == true, the returned id is no longer
197 * allocated and may be re-used by future node allocations, so the caller
198 * should retrieve any per node state from the companion array before modifying
199 * the heap further.
200 *
201 * @param heap the heap
202 * @param free true if the id is also to be freed; false if not - useful if the caller
203 * may wish to re-insert an item with the same id)
204 * @return the old head node id.
205 */
206 pheap_node_id_t ph_remove_head(pheap_t *heap, bool free);
207
208 /**
209 * \brief Remove the head node from the pairing heap. This head node is
210 * the node which compares first in the logical ordering provided
211 * by the comparator.
212 * \ingroup util_pheap
213 *
214 * Note that the returned id will be freed, and thus may be re-used by future node allocations,
215 * so the caller should retrieve any per node state from the companion array before modifying
216 * the heap further.
217 *
218 * @param heap the heap
219 * @return the old head node id.
220 */
ph_remove_and_free_head(pheap_t * heap)221 static inline pheap_node_id_t ph_remove_and_free_head(pheap_t *heap) {
222 return ph_remove_head(heap, true);
223 }
224
225 /**
226 * \brief Remove and free an arbitrary node from the pairing heap. This is a more
227 * costly operation than removing the head via ph_remove_and_free_head()
228 * \ingroup util_pheap
229 *
230 * @param heap the heap
231 * @param id the id of the node to free
232 * @return true if the the node was in the heap, false otherwise
233 */
234 bool ph_remove_and_free_node(pheap_t *heap, pheap_node_id_t id);
235
236 /**
237 * \brief Determine if the heap contains a given node. Note containment refers
238 * to whether the node is inserted (ph_insert_node()) vs allocated (ph_new_node())
239 * \ingroup util_pheap
240 *
241 * @param heap the heap
242 * @param id the id of the node
243 * @return true if the heap contains a node with the given id, false otherwise.
244 */
ph_contains_node(pheap_t * heap,pheap_node_id_t id)245 static inline bool ph_contains_node(pheap_t *heap, pheap_node_id_t id) {
246 return id == heap->root_id || ph_get_node(heap, id)->parent;
247 }
248
249
250 /**
251 * \brief Free a node that is not currently in the heap, but has been allocated
252 * \ingroup util_pheap
253 *
254 * @param heap the heap
255 * @param id the id of the node
256 */
ph_free_node(pheap_t * heap,pheap_node_id_t id)257 static inline void ph_free_node(pheap_t *heap, pheap_node_id_t id) {
258 assert(id && !ph_contains_node(heap, id));
259 if (heap->free_tail_id) {
260 ph_get_node(heap, heap->free_tail_id)->sibling = id;
261 }
262 if (!heap->free_head_id) {
263 assert(!heap->free_tail_id);
264 heap->free_head_id = id;
265 }
266 heap->free_tail_id = id;
267 }
268
269 /**
270 * \brief Print a representation of the heap for debugging
271 * \ingroup util_pheap
272 *
273 * @param heap the heap
274 * @param dump_key a method to print a node value
275 * @param user_data the user data to pass to the dump_key method
276 */
277 void ph_dump(pheap_t *heap, void (*dump_key)(pheap_node_id_t id, void *user_data), void *user_data);
278
279 /**
280 * \brief Initialize a statically allocated heap (ph_create() using the C heap).
281 * The heap member `nodes` must be allocated of size max_nodes.
282 * \ingroup util_pheap
283 *
284 * @param heap the heap
285 * @param max_nodes the max number of nodes in the heap (matching the size of the heap's nodes array)
286 * @param comparator the comparator for the heap
287 * @param user_data the user data for the heap.
288 */
289 void ph_post_alloc_init(pheap_t *heap, uint max_nodes, pheap_comparator comparator, void *user_data);
290
291 /**
292 * \brief Define a statically allocated pairing heap. This must be initialized
293 * by ph_post_alloc_init
294 * \ingroup util_pheap
295 */
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 \
302 };
303
304
305 #ifdef __cplusplus
306 }
307 #endif
308
309 #endif
310