min_heap.h

Go to the documentation of this file.

/*
 * Copyright (c) 2025 Aerlync Labs Inc.
 *
 * SPDX-License-Identifier: Apache-2.0
 */
 
/*
 * @file
 * @brief Header-file for min-heap data structure
 * @ingroup min_heap_apis
 */
 
#ifndef ZEPHYR_INCLUDE_SYS_MIN_HEAP_H_
#define ZEPHYR_INCLUDE_SYS_MIN_HEAP_H_
 
#include <zephyr/sys/util.h>
#include <zephyr/kernel.h>
 
#ifdef __cplusplus
extern "C" {
#endif


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

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

struct min_heap {
        void *storage;
        size_t capacity;
        size_t elem_size;
        size_t size;
        min_heap_cmp_t cmp;
};

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

#define MIN_HEAP_DEFINE_STATIC(name, cap, elem_sz, align, cmp_func) \
        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) \
        }

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

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

void *min_heap_peek(const struct min_heap *heap);

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

static inline bool min_heap_is_empty(struct min_heap *heap)
{
        __ASSERT_NO_MSG(heap != NULL);
 
        return (heap->size == 0);
}

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

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

static inline void *min_heap_get_element(const struct min_heap *heap,
                                          size_t index)
{
        __ASSERT_NO_MSG(heap != NULL);
 
        return (void *)((uintptr_t)heap->storage + index * heap->elem_size);
}

#define MIN_HEAP_FOREACH(heap, node_var)                                                           \
        for (size_t _i = 0;                                                                        \
             _i < (heap)->size && (((node_var) = min_heap_get_element((heap), _i)) || true); ++_i)

 
#ifdef __cplusplus
}
#endif
 
#endif /* ZEPHYR_INCLUDE_SYS_MIN_HEAP_H_ */