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