min_heap_ref.h

Go to the documentation of this file.

/*
 * Copyright (c) 2026 Aerlync Labs Inc.
 *
 * SPDX-License-Identifier: Apache-2.0
 */

 
#ifndef ZEPHYR_INCLUDE_SYS_MIN_HEAP_REF_H_
#define ZEPHYR_INCLUDE_SYS_MIN_HEAP_REF_H_
 
#include <zephyr/sys/util.h>
 
#ifdef __cplusplus
extern "C" {
#endif


struct min_heap_handle {
        uint16_t idx;
};

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

struct min_heap_ref {
        struct min_heap_handle **storage;
        size_t capacity;
        size_t size;
        min_heap_ref_cmp_t cmp;
};

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

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

static inline void min_heap_ref_init(struct min_heap_ref *heap, struct min_heap_handle **storage,
                                 size_t capacity, min_heap_ref_cmp_t cmp)
{
        __ASSERT_NO_MSG(heap != NULL);
        __ASSERT_NO_MSG(storage != NULL);
        __ASSERT_NO_MSG(cmp != NULL);
 
        heap->storage = storage;
        heap->capacity = capacity;
        heap->size = 0;
        heap->cmp = cmp;
}

static inline void min_heap_ref_swap(struct min_heap_ref *heap, size_t a, size_t b)
{
        struct min_heap_handle *tmp = heap->storage[a];
 
        heap->storage[a] = heap->storage[b];
        heap->storage[b] = tmp;
        heap->storage[a]->idx = (uint16_t)(a + 1U);
        heap->storage[b]->idx = (uint16_t)(b + 1U);
}

static inline void min_heap_ref_heapify_up(struct min_heap_ref *heap, size_t index)
{
        while (index > 0) {
                size_t parent = (index - 1U) / 2U;
 
                if (heap->cmp(heap->storage[index], heap->storage[parent]) >= 0) {
                        break;
                }
                min_heap_ref_swap(heap, index, parent);
                index = parent;
        }
}

static inline void min_heap_ref_heapify_down(struct min_heap_ref *heap, size_t index)
{
        for (size_t left = 2U * index + 1U; left < heap->size; left = 2U * index + 1U) {
                size_t right = left + 1U;
                size_t smallest = index;
 
                if (heap->cmp(heap->storage[left], heap->storage[smallest]) < 0) {
                        smallest = left;
                }
                if (right < heap->size &&
                    heap->cmp(heap->storage[right], heap->storage[smallest]) < 0) {
                        smallest = right;
                }
                if (smallest == index) {
                        break;
                }
                min_heap_ref_swap(heap, index, smallest);
                index = smallest;
        }
}

static inline int min_heap_ref_push(struct min_heap_ref *heap, struct min_heap_handle *handle)
{
        __ASSERT_NO_MSG(heap != NULL);
        __ASSERT_NO_MSG(handle != NULL);
        __ASSERT_NO_MSG(handle->idx == 0U);
        __ASSERT(heap->size < UINT16_MAX, "heap idx overflow");
 
        if (heap->size >= heap->capacity) {
                return -1;
        }
 
        heap->storage[heap->size] = handle;
        handle->idx = (uint16_t)(heap->size + 1U);
        heap->size++;
        min_heap_ref_heapify_up(heap, heap->size - 1U);
 
        return 0;
}

static inline const struct min_heap_handle *min_heap_ref_peek(const struct min_heap_ref *heap)
{
        __ASSERT_NO_MSG(heap != NULL);
        return heap->size == 0U ? NULL : heap->storage[0];
}

static inline bool min_heap_ref_remove(struct min_heap_ref *heap, struct min_heap_handle *handle)
{
        __ASSERT_NO_MSG(heap != NULL);
        __ASSERT_NO_MSG(handle != NULL);
 
        if (handle->idx == 0U || (size_t)handle->idx > heap->size) {
                return false;
        }
 
        size_t id = (size_t)(handle->idx - 1U);
 
        handle->idx = 0U;
        heap->size--;
 
        if (id != heap->size) {
                struct min_heap_handle *last = heap->storage[heap->size];
 
                heap->storage[heap->size] = NULL;
                heap->storage[id] = last;
                last->idx = (uint16_t)(id + 1U);
                min_heap_ref_heapify_down(heap, id);
                min_heap_ref_heapify_up(heap, id);
        } else {
                heap->storage[heap->size] = NULL;
        }
 
        return true;
}

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

static inline struct min_heap_handle *min_heap_ref_pop(struct min_heap_ref *heap)
{
        __ASSERT_NO_MSG(heap != NULL);
 
        if (heap->size == 0U) {
                return NULL;
        }
 
        struct min_heap_handle *min = heap->storage[0];
        bool ok = min_heap_ref_remove(heap, min);
 
        __ASSERT_NO_MSG(ok);
        (void)ok;
        return min;
}

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

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

 
#ifdef __cplusplus
}
#endif
 
#endif /* ZEPHYR_INCLUDE_SYS_MIN_HEAP_REF_H_ */