1/* @title: Minheap */
2#pragma once
3#include <atomic.h>
4#include <stddef.h>
5#include <stdint.h>
6#include <sync/spinlock.h>
7#define MINHEAP_INIT_CAP 32
8#define MINHEAP_INDEX_INVALID ((uint32_t) -1)
9
10#define minheap_for_each(node_ptr_, heap_) \
11 for (uint32_t __mh_idx = 0; \
12 __mh_idx < (heap_)->size && \
13 (((node_ptr_) = ((heap_)->nodes[__mh_idx])), true); \
14 __mh_idx++)
15
16struct minheap_node {
17 atomic_uint64_t key;
18 atomic_uint32_t index;
19};
20
21struct minheap {
22 struct minheap_node **nodes;
23 atomic_uint32_t capacity;
24 atomic_uint32_t size;
25 struct spinlock lock;
26};
27
28struct minheap *cc_nullable minheap_create(void);
29void minheap_insert(struct minheap *heap, struct minheap_node *node,
30 uint64_t key);
31void minheap_remove(struct minheap *heap, struct minheap_node *node);
32void minheap_expand(struct minheap *heap, uint32_t new_size);
33
34#define MINHEAP_SIZE(mh) (atomic_load(&mh->size))
35#define MINHEAP_CAPACITY(mh) (atomic_load(&mh->capacity))
36#define MINHEAP_NODE_KEY(mhn) (atomic_load(&mhn->key))
37#define MINHEAP_NODE_INDEX(mhn) (atomic_load(&mhn->index))
38
39#define MINHEAP_SET_SIZE(mh, n) (atomic_store(&mh->size, n))
40#define MINHEAP_SET_CAPACITY(mh, n) (atomic_store(&mh->capacity, n))
41#define MINHEAP_NODE_SET_KEY(mhn, n) (atomic_store(&mhn->key, n))
42#define MINHEAP_NODE_SET_INDEX(mhn, n) (atomic_store(&mhn->index, n))
43
44#define MINHEAP_NODE_INVALID(mhn) \
45 (MINHEAP_NODE_INDEX(mhn) == MINHEAP_INDEX_INVALID)
46#define MINHEAP_MARK_NODE_INVALID(mhn) \
47 (MINHEAP_NODE_SET_INDEX(mhn, MINHEAP_INDEX_INVALID))
48
49static inline struct minheap_node *minheap_peek(struct minheap *heap) {
50 return MINHEAP_SIZE(heap) == 0 ? NULL : heap->nodes[0];
51}
52
53struct minheap_node *minheap_pop(struct minheap *heap);
54
55static inline bool minheap_node_valid(struct minheap_node *node) {
56 bool valid = MINHEAP_NODE_INDEX(node) != MINHEAP_INDEX_INVALID;
57 return valid;
58}
59