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 * 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_head returns the id of an element that is no longer in the heap.
33 *
34 * The user can still use this to look at the data in their companion array, however obviously further operations
35 * on the heap may cause them to overwrite that data as the id may be reused on subsequent operations
36 *
37 */
38 // PICO_CONFIG: PICO_PHEAP_MAX_ENTRIES, Maximum number of entries in the pheap, min=1, max=65534, default=255, group=pico_util
39 #ifndef PICO_PHEAP_MAX_ENTRIES
40 #define PICO_PHEAP_MAX_ENTRIES 255
41 #endif
42
43 // public heap_node ids are numbered from 1 (0 means none)
44 #if PICO_PHEAP_MAX_ENTRIES < 256
45 typedef uint8_t pheap_node_id_t;
46 #elif PICO_PHEAP_MAX_ENTRIES < 65535
47 typedef uint16_t pheap_node_id_t;
48 #else
49 #error invalid PICO_PHEAP_MAX_ENTRIES
50 #endif
51
52 typedef struct pheap_node {
53 pheap_node_id_t child, sibling, parent;
54 } pheap_node_t;
55
56 // return true if a < b in natural order
57 typedef bool (*pheap_comparator)(void *user_data, pheap_node_id_t a, pheap_node_id_t b);
58
59 typedef struct pheap {
60 pheap_node_t *nodes;
61 pheap_comparator comparator;
62 void *user_data;
63 pheap_node_id_t max_nodes;
64 pheap_node_id_t root_id;
65 // we remove from head and add to tail to stop reusing the same ids
66 pheap_node_id_t free_head_id;
67 pheap_node_id_t free_tail_id;
68 } pheap_t;
69
70 pheap_t *ph_create(uint max_nodes, pheap_comparator comparator, void *user_data);
71
72 void ph_clear(pheap_t *heap);
73
74 void ph_destroy(pheap_t *heap);
75
ph_get_node(pheap_t * heap,pheap_node_id_t id)76 static inline pheap_node_t *ph_get_node(pheap_t *heap, pheap_node_id_t id) {
77 assert(id && id <= heap->max_nodes);
78 return heap->nodes + id - 1;
79 }
80
ph_add_child_node(pheap_t * heap,pheap_node_id_t parent_id,pheap_node_id_t child_id)81 static void ph_add_child_node(pheap_t *heap, pheap_node_id_t parent_id, pheap_node_id_t child_id) {
82 pheap_node_t *n = ph_get_node(heap, parent_id);
83 assert(parent_id);
84 assert(child_id);
85 assert(parent_id != child_id);
86 pheap_node_t *c = ph_get_node(heap, child_id);
87 c->parent = parent_id;
88 if (!n->child) {
89 n->child = child_id;
90 } else {
91 c->sibling = n->child;
92 n->child = child_id;
93 }
94 }
95
ph_merge_nodes(pheap_t * heap,pheap_node_id_t a,pheap_node_id_t b)96 static pheap_node_id_t ph_merge_nodes(pheap_t *heap, pheap_node_id_t a, pheap_node_id_t b) {
97 if (!a) return b;
98 if (!b) return a;
99 if (heap->comparator(heap->user_data, a, b)) {
100 ph_add_child_node(heap, a, b);
101 return a;
102 } else {
103 ph_add_child_node(heap, b, a);
104 return b;
105 }
106 }
107
ph_new_node(pheap_t * heap)108 static inline pheap_node_id_t ph_new_node(pheap_t *heap) {
109 if (!heap->free_head_id) return 0;
110 pheap_node_id_t id = heap->free_head_id;
111 heap->free_head_id = ph_get_node(heap, id)->sibling;
112 if (!heap->free_head_id) heap->free_tail_id = 0;
113 return id;
114 }
115
116 // note this will callback the comparator for the node
117 // returns the (new) root of the heap
ph_insert(pheap_t * heap,pheap_node_id_t id)118 static inline pheap_node_id_t ph_insert(pheap_t *heap, pheap_node_id_t id) {
119 assert(id);
120 pheap_node_t *hn = ph_get_node(heap, id);
121 hn->child = hn->sibling = hn->parent = 0;
122 heap->root_id = ph_merge_nodes(heap, heap->root_id, id);
123 return heap->root_id;
124 }
125
ph_peek_head(pheap_t * heap)126 static inline pheap_node_id_t ph_peek_head(pheap_t *heap) {
127 return heap->root_id;
128 }
129
130 pheap_node_id_t ph_remove_head_reserve(pheap_t *heap, bool reserve);
131
ph_remove_head(pheap_t * heap)132 static inline pheap_node_id_t ph_remove_head(pheap_t *heap) {
133 return ph_remove_head_reserve(heap, false);
134 }
135
ph_contains(pheap_t * heap,pheap_node_id_t id)136 static inline bool ph_contains(pheap_t *heap, pheap_node_id_t id) {
137 return id == heap->root_id || ph_get_node(heap, id)->parent;
138 }
139
140 bool ph_delete(pheap_t *heap, pheap_node_id_t id);
141
ph_add_to_free_list(pheap_t * heap,pheap_node_id_t id)142 static inline void ph_add_to_free_list(pheap_t *heap, pheap_node_id_t id) {
143 assert(id && !ph_contains(heap, id));
144 if (heap->free_tail_id) {
145 ph_get_node(heap, heap->free_tail_id)->sibling = id;
146 }
147 heap->free_tail_id = id;
148 }
149
150 void ph_dump(pheap_t *heap, void (*dump_key)(pheap_node_id_t, void *), void *user_data);
151 #ifdef __cplusplus
152 }
153 #endif
154
155 #endif
156