Zephyr API Documentation 4.2.0-rc1
A Scalable Open Source RTOS
 4.2.0-rc1
All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Modules Pages
min_heap.h
Go to the documentation of this file.
1/*
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
14extern "C" {
15#endif
16
38typedef int (*min_heap_cmp_t)(const void *a,
39 const void *b);
40
49typedef bool (*min_heap_eq_t)(const void *node,
50 const void *other);
51
55struct min_heap {
57 void *storage;
59 size_t capacity;
61 size_t elem_size;
63 size_t size;
66};
67
77#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
94#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
120void min_heap_init(struct min_heap *heap, void *storage, size_t cap,
121 size_t elem_size, min_heap_cmp_t cmp);
122
135int min_heap_push(struct min_heap *heap, const void *item);
136
146void *min_heap_peek(const struct min_heap *heap);
147
163bool min_heap_remove(struct min_heap *heap, size_t id, void *out_buf);
164
174static 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
193bool min_heap_pop(struct min_heap *heap, void *out_buf);
194
205void *min_heap_find(struct min_heap *heap, min_heap_eq_t eq,
206 const void *other, size_t *out_id);
207
216static 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
238#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
246#ifdef __cplusplus
247}
248#endif
249
250#endif /* ZEPHYR_INCLUDE_SYS_MIN_HEAP_H_ */
void * min_heap_peek(const struct min_heap *heap)
Peek at the top element of the min-heap.
void * min_heap_find(struct min_heap *heap, min_heap_eq_t eq, const void *other, size_t *out_id)
Search for a node in the heap matching a condition.
int min_heap_push(struct min_heap *heap, const void *item)
Push an element into the min-heap.
int(* min_heap_cmp_t)(const void *a, const void *b)
Comparator function type for min-heap ordering.
Definition min_heap.h:38
void min_heap_init(struct min_heap *heap, void *storage, size_t cap, size_t elem_size, min_heap_cmp_t cmp)
Initialize a min-heap instance at runtime.
static bool min_heap_is_empty(struct min_heap *heap)
Check if the min heap is empty.
Definition min_heap.h:174
bool(* min_heap_eq_t)(const void *node, const void *other)
Equality function for finding a node in the heap.
Definition min_heap.h:49
bool min_heap_remove(struct min_heap *heap, size_t id, void *out_buf)
Remove a specific element from the min-heap.
static void * min_heap_get_element(const struct min_heap *heap, size_t index)
Get a pointer to the element at the specified index.
Definition min_heap.h:216
bool min_heap_pop(struct min_heap *heap, void *out_buf)
Remove and return the highest priority element in the heap.
#define NULL
Definition iar_missing_defs.h:20
Public kernel APIs.
#define bool
Definition stdbool.h:13
__UINTPTR_TYPE__ uintptr_t
Definition stdint.h:105
min-heap data structure with user-provided comparator.
Definition min_heap.h:55
min_heap_cmp_t cmp
Comparator function.
Definition min_heap.h:65
void * storage
Raw pointer to contiguous memory for elements.
Definition min_heap.h:57
size_t size
Current elements count.
Definition min_heap.h:63
size_t elem_size
Size of each element.
Definition min_heap.h:61
size_t capacity
Maximum number of elements.
Definition min_heap.h:59
Misc utilities.