Min-Heap service

min_heap More...

Data Structures
struct	min_heap
	min-heap data structure with user-provided comparator. More...

Macros
#define	MIN_HEAP_DEFINE(name, storage, cap, size, cmp_func)
	Define and initialize a heap instance at runtime.
#define	MIN_HEAP_DEFINE_STATIC(name, cap, elem_sz, align, cmp_func)
	Define a statically allocated and aligned min-heap instance.
#define	MIN_HEAP_FOREACH(heap, node_var, body)
	Iterate over each node in the heap.

Typedefs
typedef int(*	min_heap_cmp_t) (const void *a, const void *b)
	Comparator function type for min-heap ordering.
typedef bool(*	min_heap_eq_t) (const void *node, const void *other)
	Equality function for finding a node in the heap.

Functions
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.
int	min_heap_push (struct min_heap *heap, const void *item)
	Push an element into the min-heap.
void *	min_heap_peek (const struct min_heap *heap)
	Peek at the top element of the min-heap.
bool	min_heap_remove (struct min_heap *heap, size_t id, void *out_buf)
	Remove a specific element from the min-heap.
static bool	min_heap_is_empty (struct min_heap *heap)
	Check if the min heap is empty.
bool	min_heap_pop (struct min_heap *heap, void *out_buf)
	Remove and return the highest priority element in the 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.
static void *	min_heap_get_element (const struct min_heap *heap, size_t index)
	Get a pointer to the element at the specified index.

Detailed Description

min_heap

Macro Definition Documentation

MIN_HEAP_DEFINE

#define MIN_HEAP_DEFINE	(		name,
			storage,
			cap,
			size,
			cmp_func )

#include <zephyr/sys/min_heap.h>

Value:

        struct min_heap name; \
        min_heap_init(&name, storage, cap, size, cmp_func)

Define and initialize a heap instance at runtime.

Parameters

name	Name of the heap variable.
storage	Pointer to the preallocated storage.
cap	Capacity (number of elements).
size	Size of each element.
cmp_func	Comparator function for the heap.

MIN_HEAP_DEFINE_STATIC

#define MIN_HEAP_DEFINE_STATIC	(		name,
			cap,
			elem_sz,
			align,
			cmp_func )

#include <zephyr/sys/min_heap.h>

Value:

        static uint8_t name##_storage[(cap) * (elem_sz)] __aligned(align); \
        static struct min_heap name = { \
                        .storage = name##_storage, \
                        .capacity = (cap), \
                        .elem_size = (elem_sz), \
                        .size = 0, \
                        .cmp = (cmp_func) \
        }

Define a statically allocated and aligned min-heap instance.

Parameters

name	Base name for the heap instance.
cap	Capacity (number of elements).
elem_sz	Size in bytes of each element.
align	Required alignment of each element.
cmp_func	Comparator function used by the heap

MIN_HEAP_FOREACH

#define MIN_HEAP_FOREACH	(		heap,
			node_var,
			body )

#include <zephyr/sys/min_heap.h>

Value:

        do { for (size_t _i = 0; _i < (heap)->size && \
                (((node_var) = min_heap_get_element((heap), _i)) || true); \
                ++_i) { \
                        body; \
                } \
        } while (0)

Iterate over each node in the heap.

Parameters

heap	Pointer to the heap.
node_var	The loop variable used to reference each node.
body	Code block to execute for each node.

Example:

void *node;
MIN_HEAP_FOREACH(&heap, node, {
     printk("Value: %d\n", node->value);
});

Typedef Documentation

min_heap_cmp_t

typedef int(* min_heap_cmp_t) (const void *a, const void *b)

#include <zephyr/sys/min_heap.h>

Comparator function type for min-heap ordering.

This function compares two heap nodes to establish their relative order. It must be implemented by the user and provided at min-heap initialization.

Parameters

a	First user defined data pointer for comparison.
b	Second user defined data pointer for comparison.

Returns

Negative value if a is less than b, positive value if a is greater than b, zero if they are equal.

min_heap_eq_t

typedef bool(* min_heap_eq_t) (const void *node, const void *other)

#include <zephyr/sys/min_heap.h>

Equality function for finding a node in the heap.

Parameters

node	Pointer to a user defined data.
other	Pointer to a user-defined key or structure to compare with.

Returns

true if the node matches the search criteria, false otherwise.

Function Documentation

min_heap_find()

void * min_heap_find	(	struct min_heap *	heap,
		min_heap_eq_t	eq,
		const void *	other,
		size_t *	out_id )

#include <zephyr/sys/min_heap.h>

Search for a node in the heap matching a condition.

Parameters

heap	Pointer to the heap structure.
eq	Function used to compare each node with the search target.
other	Pointer to the data used for comparison in the eq function.
out_id	Optional output parameter to store the index of the found node.

Returns

Pointer to the first matching element, or NULL if not found.

min_heap_get_element()

static void * min_heap_get_element ( const struct min_heap * heap, size_t index )

inlinestatic

#include <zephyr/sys/min_heap.h>

Get a pointer to the element at the specified index.

Parameters

heap	Pointer to the min-heap.
index	Index of the element to retrieve.

Returns

Pointer to the element at the given index.

min_heap_init()

void min_heap_init	(	struct min_heap *	heap,
		void *	storage,
		size_t	cap,
		size_t	elem_size,
		min_heap_cmp_t	cmp )

#include <zephyr/sys/min_heap.h>

Initialize a min-heap instance at runtime.

Sets up the internal structure of a min heap using a user-provided memory block, capacity, and comparator function. This function must be called before using the heap if not statically defined.

Parameters

heap	Pointer to the min-heap structure.
storage	Pointer to memory block for storing elements.
cap	Maximum number of elements the heap can store.
elem_size	Size in bytes of each element.
cmp	Comparator function used to order the heap elements.

Note

All arguments must be valid. This function does not allocate memory.

min_heap_is_empty()

static bool min_heap_is_empty ( struct min_heap * heap )

inlinestatic

#include <zephyr/sys/min_heap.h>

Check if the min heap is empty.

This function checks whether the heap contains any elements.

Parameters

heap	Pointer to the min heap.

Returns

true if heap is empty, false otherwise.

min_heap_peek()

void * min_heap_peek

(

const struct min_heap *

heap

)

#include <zephyr/sys/min_heap.h>

Peek at the top element of the min-heap.

The function will not remove the element from the min-heap.

Parameters

heap	Pointer to the min-heap.

Returns

Pointer to the top priority element, or NULL if the heap is empty.

min_heap_pop()

bool min_heap_pop	(	struct min_heap *	heap,
		void *	out_buf )

#include <zephyr/sys/min_heap.h>

Remove and return the highest priority element in the heap.

The caller gains ownership of the returned element and is responsible for any further management of its memory or reuse. The min-heap is rebalanced after removal to ensure proper ordering.

Parameters

heap	Pointer to heap.
out_buf	User-provided buffer where the removed element will be copied.

Returns

true in success, false otherwise.

min_heap_push()

int min_heap_push	(	struct min_heap *	heap,
		const void *	item )

#include <zephyr/sys/min_heap.h>

Push an element into the min-heap.

Adds a new element to the min-heap and restores the heap order by moving it upward as necessary. Insert operation will fail if the min-heap has reached full capacity.

Parameters

heap	Pointer to the min-heap.
item	Pointer to the item to insert.

Returns

0 on Success, -ENOMEM if the heap is full.

min_heap_remove()

bool min_heap_remove	(	struct min_heap *	heap,
		size_t	id,
		void *	out_buf )

#include <zephyr/sys/min_heap.h>

Remove a specific element from the min-heap.

Removes the specified node from the min-heap based on the ID it stores internally. The min-heap is rebalanced after removal to ensure proper ordering. The caller gains ownership of the returned element and is responsible for any further management of its memory or reuse.

Parameters

heap	Pointer to the min-heap.
id	element ID to be removed.
out_buf	User-provided buffer where the removed element will be copied.

Returns

true in success, false otherwise.