Reference min-heap

Reference (handle-based) min-heap implementation. More...

Files
file	min_heap_ref.h
	Header-file for the reference (handle-based) min-heap data structure.

Data Structures
struct	min_heap_handle
	Embeddable heap position handle. More...
struct	min_heap_ref
	min-heap data structure with user-provided comparator. More...

Macros
#define	MIN_HEAP_REF_DEFINE(name, cap, cmp_func)
	Define a min-heap instance.
#define	MIN_HEAP_REF_DEFINE_STATIC(name, cap, cmp_func)
	Define a statically allocated min-heap instance.
#define	MIN_HEAP_REF_FOREACH(__heap, __handle)
	Iterate over every element currently in the min-heap.
#define	MIN_HEAP_REF_FOREACH_CONTAINER(__heap, __cn, __field)
	Iterate over every element in the min-heap yielding the embedding container struct.

Typedefs
typedef int(*	min_heap_ref_cmp_t) (const struct min_heap_handle *a, const struct min_heap_handle *b)
	Comparator function type for min-heap ordering.

Functions
static void	min_heap_ref_init (struct min_heap_ref *heap, struct min_heap_handle **storage, size_t capacity, min_heap_ref_cmp_t cmp)
	Initialize a min-heap instance at runtime.
static void	min_heap_ref_swap (struct min_heap_ref *heap, size_t a, size_t b)
	Swap two elements in the heap storage, updating their idx fields.
static void	min_heap_ref_heapify_up (struct min_heap_ref *heap, size_t index)
	Restore heap order by moving a node up the tree.
static void	min_heap_ref_heapify_down (struct min_heap_ref *heap, size_t index)
	Restore heap order by moving a node down the tree.
static int	min_heap_ref_push (struct min_heap_ref *heap, struct min_heap_handle *handle)
	Push a handle into the min-heap.
static const struct min_heap_handle *	min_heap_ref_peek (const struct min_heap_ref *heap)
	Peek at the top element of the min-heap.
static bool	min_heap_ref_remove (struct min_heap_ref *heap, struct min_heap_handle *handle)
	Remove a specific element from the min-heap by handle.
static bool	min_heap_ref_is_empty (struct min_heap_ref *heap)
	Check if the min heap is empty.
static struct min_heap_handle *	min_heap_ref_pop (struct min_heap_ref *heap)
	Remove and return the highest priority element's handle.

Detailed Description

Reference (handle-based) min-heap implementation.

A min-heap is a binary tree-based data structure in which the smallest element is always at the root. Unlike the value-based min-heap, this variant stores pointers to caller-owned nodes that embed a min_heap_handle, so insertion is zero-copy and a specific node can be removed in O(log n) using its handle, with no search.

Macro Definition Documentation

MIN_HEAP_REF_DEFINE

#define MIN_HEAP_REF_DEFINE	(		name,
			cap,
			cmp_func )

#include <zephyr/sys/min_heap_ref.h>

Value:

static struct min_heap_handle *(name##_storage)[(cap)];                        \
struct min_heap_ref name = {                                                   \
        .storage = (name##_storage),                                           \
        .capacity = (cap),                                                     \
        .size = 0,                                                             \
        .cmp = (cmp_func),                                                     \
}

Define a min-heap instance.

Parameters

name	Base name for the heap instance.
cap	Capacity (number of elements).
cmp_func	Comparator function used by the heap

MIN_HEAP_REF_DEFINE_STATIC

#define MIN_HEAP_REF_DEFINE_STATIC	(		name,
			cap,
			cmp_func )

#include <zephyr/sys/min_heap_ref.h>

Value:

static struct min_heap_handle *(name##_storage)[(cap)];                        \
static struct min_heap_ref name = {                                            \
        .storage = (name##_storage),                                           \
        .capacity = (cap),                                                     \
        .size = 0,                                                             \
        .cmp = (cmp_func),                                                     \
}

Define a statically allocated min-heap instance.

Parameters

name	Base name for the heap instance.
cap	Capacity (number of elements).
cmp_func	Comparator function used by the heap

MIN_HEAP_REF_FOREACH

#define MIN_HEAP_REF_FOREACH	(		__heap,
			__handle )

#include <zephyr/sys/min_heap_ref.h>

Value:

for (size_t __mh_i = 0;                                                        \
     (__mh_i < (__heap)->size) && ((__handle) = (__heap)->storage[__mh_i], true); \
     __mh_i++)

Iterate over every element currently in the min-heap.

Visits all elements in internal storage-array order (BFS level order). This is NOT the sorted order

Usage:

struct min_heap_handle *h;
MIN_HEAP_REF_FOREACH(&heap, h) {
   struct data *t = CONTAINER_OF(h, struct data, handle);
}

Parameters

__heap	Pointer to the min-heap.
__handle	min_heap_handle pointer.

MIN_HEAP_REF_FOREACH_CONTAINER

#define MIN_HEAP_REF_FOREACH_CONTAINER	(		__heap,
			__cn,
			__field )

#include <zephyr/sys/min_heap_ref.h>

Value:

for (size_t __mh_i = 0;                                                        \
     (__mh_i < (__heap)->size) &&                                              \
     ((__cn) = CONTAINER_OF((__heap)->storage[__mh_i], __typeof__(*(__cn)), __field), \
     true);                                                                    \
     __mh_i++)

Iterate over every element in the min-heap yielding the embedding container struct.

Usage:

struct data *t;
MIN_HEAP_REF_FOREACH_CONTAINER(&heap, t, handle) {
   printk("key=%d\n", t->key);
}

Parameters

__heap	Pointer to the min-heap
__cn	Caller-declared pointer to the container struct type
__field	Name of the min_heap_handle member in the container

Typedef Documentation

min_heap_ref_cmp_t

typedef int(* min_heap_ref_cmp_t) (const struct min_heap_handle *a, const struct min_heap_handle *b)

#include <zephyr/sys/min_heap_ref.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 handle pointer for comparison.
b	Second handle 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.

Function Documentation

min_heap_ref_heapify_down()

void min_heap_ref_heapify_down ( struct min_heap_ref * heap, size_t index )

inlinestatic

#include <zephyr/sys/min_heap_ref.h>

Restore heap order by moving a node down the tree.

Moves the node at the sepcified index downward in the heap until the min-heap property is restored.

Parameters

heap	Pointer to the min-heap.
index	Index of the node to heapify downward.

min_heap_ref_heapify_up()

void min_heap_ref_heapify_up ( struct min_heap_ref * heap, size_t index )

inlinestatic

#include <zephyr/sys/min_heap_ref.h>

Restore heap order by moving a node up the tree.

Moves the node at the given index upward in the heap until the min-heap property is restored.

Parameters

heap	Pointer to the min-heap.
index	Index of the node to heapify upwards.

min_heap_ref_init()

void min_heap_ref_init ( struct min_heap_ref * heap, struct min_heap_handle ** storage, size_t capacity, min_heap_ref_cmp_t cmp )

inlinestatic

#include <zephyr/sys/min_heap_ref.h>

Initialize a min-heap instance at runtime.

Sets up the internal structure of a min heap using a user-provided handle pointer array, 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 array of handle pointers.
capacity	Maximum number of elements the heap can store.
cmp	Comparator function used to order the heap elements.

Note

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

min_heap_ref_is_empty()

bool min_heap_ref_is_empty ( struct min_heap_ref * heap )

inlinestatic

#include <zephyr/sys/min_heap_ref.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_ref_peek()

const struct min_heap_handle * min_heap_ref_peek ( const struct min_heap_ref * heap )

inlinestatic

#include <zephyr/sys/min_heap_ref.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 handle, or NULL if the heap is empty.

min_heap_ref_pop()

struct min_heap_handle * min_heap_ref_pop ( struct min_heap_ref * heap )

inlinestatic

#include <zephyr/sys/min_heap_ref.h>

Remove and return the highest priority element's handle.

Parameters

heap	Pointer to heap.

Returns

Handle of the removed minimum element, or NULL if empty. Use CONTAINER_OF() to recover the containing struct.

min_heap_ref_push()

int min_heap_ref_push ( struct min_heap_ref * heap, struct min_heap_handle * handle )

inlinestatic

#include <zephyr/sys/min_heap_ref.h>

Push a handle into the min-heap.

Adds a new handle 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.
handle	Pointer to the handle to insert.

Returns

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

min_heap_ref_remove()

bool min_heap_ref_remove ( struct min_heap_ref * heap, struct min_heap_handle * handle )

inlinestatic

#include <zephyr/sys/min_heap_ref.h>

Remove a specific element from the min-heap by handle.

The handle's idx field gives the O(1) location, no linear scan needed.

Parameters

heap	Pointer to the min-heap.
handle	Handle of the element to remove (must currently be in heap).

Returns

true in success, false otherwise.

min_heap_ref_swap()

void min_heap_ref_swap ( struct min_heap_ref * heap, size_t a, size_t b )

inlinestatic

#include <zephyr/sys/min_heap_ref.h>

Swap two elements in the heap storage, updating their idx fields.

Parameters

heap	Pointer to the min-heap.
a	Index of the first element.
b	Index of the second element.