Line data Source code
1 0 : /*
2 : * Copyright (c) 2025 Aerlync Labs Inc.
3 : *
4 : * SPDX-License-Identifier: Apache-2.0
5 : */
6 :
7 : #ifndef ZEPHYR_INCLUDE_SYS_MIN_HEAP_H_
8 : #define ZEPHYR_INCLUDE_SYS_MIN_HEAP_H_
9 :
10 : #include <zephyr/sys/util.h>
11 : #include <zephyr/kernel.h>
12 :
13 : #ifdef __cplusplus
14 : extern "C" {
15 : #endif
16 :
17 : /**
18 : * @brief min_heap
19 : * @defgroup min_heap_apis Min-Heap service
20 : * @ingroup datastructure_apis
21 : * @{
22 : */
23 :
24 : /**
25 : * @brief Comparator function type for min-heap ordering.
26 : *
27 : * This function compares two heap nodes to establish their relative order.
28 : * It must be implemented by the user and provided at min-heap
29 : * initialization.
30 : *
31 : * @param a First user defined data pointer for comparison.
32 : * @param b Second user defined data pointer for comparison.
33 : *
34 : * @return Negative value if @p a is less than @p b,
35 : * positive value if @p a is greater than @p b,
36 : * zero if they are equal.
37 : */
38 1 : typedef int (*min_heap_cmp_t)(const void *a,
39 : const void *b);
40 :
41 : /**
42 : * @brief Equality function for finding a node in the heap.
43 : *
44 : * @param node Pointer to a user defined data.
45 : * @param other Pointer to a user-defined key or structure to compare with.
46 : *
47 : * @return true if the node matches the search criteria, false otherwise.
48 : */
49 1 : typedef bool (*min_heap_eq_t)(const void *node,
50 : const void *other);
51 :
52 : /**
53 : * @brief min-heap data structure with user-provided comparator.
54 : */
55 1 : struct min_heap {
56 : /** Raw pointer to contiguous memory for elements */
57 1 : void *storage;
58 : /** Maximum number of elements */
59 1 : size_t capacity;
60 : /** Size of each element*/
61 1 : size_t elem_size;
62 : /** Current elements count */
63 1 : size_t size;
64 : /** Comparator function */
65 1 : min_heap_cmp_t cmp;
66 : };
67 :
68 : /**
69 : * @brief Define a min-heap instance.
70 : *
71 : * @param name Base name for the heap instance.
72 : * @param cap Capacity (number of elements).
73 : * @param elem_sz Size in bytes of each element.
74 : * @param align Required alignment of each element.
75 : * @param cmp_func Comparator function used by the heap
76 : */
77 1 : #define MIN_HEAP_DEFINE(name, cap, elem_sz, align, cmp_func) \
78 : static uint8_t name##_storage[(cap) * (elem_sz)] __aligned(align); \
79 : struct min_heap name = {.storage = name##_storage, \
80 : .capacity = (cap), \
81 : .elem_size = (elem_sz), \
82 : .size = 0, \
83 : .cmp = (cmp_func)}
84 :
85 : /**
86 : * @brief Define a statically allocated and aligned min-heap instance.
87 : *
88 : * @param name Base name for the heap instance.
89 : * @param cap Capacity (number of elements).
90 : * @param elem_sz Size in bytes of each element.
91 : * @param align Required alignment of each element.
92 : * @param cmp_func Comparator function used by the heap
93 : */
94 1 : #define MIN_HEAP_DEFINE_STATIC(name, cap, elem_sz, align, cmp_func) \
95 : static uint8_t name##_storage[(cap) * (elem_sz)] __aligned(align); \
96 : static struct min_heap name = { \
97 : .storage = name##_storage, \
98 : .capacity = (cap), \
99 : .elem_size = (elem_sz), \
100 : .size = 0, \
101 : .cmp = (cmp_func) \
102 : }
103 :
104 : /**
105 : * @brief Initialize a min-heap instance at runtime.
106 : *
107 : * Sets up the internal structure of a min heap using a user-provided
108 : * memory block, capacity, and comparator function. This function must
109 : * be called before using the heap if not statically defined.
110 : *
111 : * @param heap Pointer to the min-heap structure.
112 : * @param storage Pointer to memory block for storing elements.
113 : * @param cap Maximum number of elements the heap can store.
114 : * @param elem_size Size in bytes of each element.
115 : * @param cmp Comparator function used to order the heap elements.
116 : *
117 : * @note All arguments must be valid. This function does not allocate memory.
118 : *
119 : */
120 1 : void min_heap_init(struct min_heap *heap, void *storage, size_t cap,
121 : size_t elem_size, min_heap_cmp_t cmp);
122 :
123 : /**
124 : * @brief Push an element into the min-heap.
125 : *
126 : * Adds a new element to the min-heap and restores the heap order by moving it
127 : * upward as necessary. Insert operation will fail if the min-heap
128 : * has reached full capacity.
129 : *
130 : * @param heap Pointer to the min-heap.
131 : * @param item Pointer to the item to insert.
132 : *
133 : * @return 0 on Success, -ENOMEM if the heap is full.
134 : */
135 1 : int min_heap_push(struct min_heap *heap, const void *item);
136 :
137 : /**
138 : * @brief Peek at the top element of the min-heap.
139 : *
140 : * The function will not remove the element from the min-heap.
141 : *
142 : * @param heap Pointer to the min-heap.
143 : *
144 : * @return Pointer to the top priority element, or NULL if the heap is empty.
145 : */
146 1 : void *min_heap_peek(const struct min_heap *heap);
147 :
148 : /**
149 : * @brief Remove a specific element from the min-heap.
150 : *
151 : * Removes the specified node from the min-heap based on the ID it stores
152 : * internally. The min-heap is rebalanced after removal to ensure
153 : * proper ordering.
154 : * The caller gains ownership of the returned element and is responsible for
155 : * any further management of its memory or reuse.
156 : *
157 : * @param heap Pointer to the min-heap.
158 : * @param id element ID to be removed.
159 : * @param out_buf User-provided buffer where the removed element will be copied.
160 : *
161 : * @return true in success, false otherwise.
162 : */
163 1 : bool min_heap_remove(struct min_heap *heap, size_t id, void *out_buf);
164 :
165 : /**
166 : * @brief Check if the min heap is empty.
167 : *
168 : * This function checks whether the heap contains any elements.
169 : *
170 : * @param heap Pointer to the min heap.
171 : *
172 : * @return true if heap is empty, false otherwise.
173 : */
174 1 : static inline bool min_heap_is_empty(struct min_heap *heap)
175 : {
176 : __ASSERT_NO_MSG(heap != NULL);
177 :
178 : return (heap->size == 0);
179 : }
180 :
181 : /**
182 : * @brief Remove and return the highest priority element in the heap.
183 : *
184 : * The caller gains ownership of the returned element and is responsible for
185 : * any further management of its memory or reuse. The min-heap is rebalanced
186 : * after removal to ensure proper ordering.
187 : *
188 : * @param heap Pointer to heap.
189 : * @param out_buf User-provided buffer where the removed element will be copied.
190 : *
191 : * @return true in success, false otherwise.
192 : */
193 1 : bool min_heap_pop(struct min_heap *heap, void *out_buf);
194 :
195 : /**
196 : * @brief Search for a node in the heap matching a condition.
197 : *
198 : * @param heap Pointer to the heap structure.
199 : * @param eq Function used to compare each node with the search target.
200 : * @param other Pointer to the data used for comparison in the eq function.
201 : * @param out_id Optional output parameter to store the index of the found node.
202 : *
203 : * @return Pointer to the first matching element, or NULL if not found.
204 : */
205 1 : void *min_heap_find(struct min_heap *heap, min_heap_eq_t eq,
206 : const void *other, size_t *out_id);
207 :
208 : /**
209 : * @brief Get a pointer to the element at the specified index.
210 : *
211 : * @param heap Pointer to the min-heap.
212 : * @param index Index of the element to retrieve.
213 : *
214 : * @return Pointer to the element at the given index.
215 : */
216 1 : static inline void *min_heap_get_element(const struct min_heap *heap,
217 : size_t index)
218 : {
219 : __ASSERT_NO_MSG(heap != NULL);
220 :
221 : return (void *)((uintptr_t)heap->storage + index * heap->elem_size);
222 : }
223 :
224 : /**
225 : * @brief Iterate over each node in the heap.
226 : *
227 : * @param heap Pointer to the heap.
228 : * @param node_var The loop variable used to reference each node.
229 : *
230 : * Example:
231 : * ```
232 : * void *node;
233 : * MIN_HEAP_FOREACH(&heap, node) {
234 : * printk("Value: %d\n", node->value);
235 : * }
236 : * ```
237 : */
238 1 : #define MIN_HEAP_FOREACH(heap, node_var) \
239 : for (size_t _i = 0; \
240 : _i < (heap)->size && (((node_var) = min_heap_get_element((heap), _i)) || true); ++_i)
241 :
242 : /**
243 : * @}
244 : */
245 :
246 : #ifdef __cplusplus
247 : }
248 : #endif
249 :
250 : #endif /* ZEPHYR_INCLUDE_SYS_MIN_HEAP_H_ */
|
