Skip to content
charmOS docs

Minheap

include/structures/minheap.h View source View on GitHub

Structs

Section titled “Structs”

minheap_node

Section titled “minheap_node”
struct minheap_node {
    _Atomic uint64_t  key;
    _Atomic uint32_t  index;
};

minheap

Section titled “minheap”
struct minheap {
    struct minheap_node  **nodes;
    _Atomic uint32_t     capacity;
    _Atomic uint32_t     size;
    struct spinlock      lock;
};

Functions

Section titled “Functions”

minheap_create

Section titled “minheap_create”
struct minheap * minheap_create(void);

minheap_insert

Section titled “minheap_insert”
void minheap_insert(struct minheap *heap, struct minheap_node *node, uint64_t key);

minheap_remove

Section titled “minheap_remove”
void minheap_remove(struct minheap *heap, struct minheap_node *node);

minheap_expand

Section titled “minheap_expand”
void minheap_expand(struct minheap *heap, uint32_t new_size);

minheap_peek

Section titled “minheap_peek”
struct minheap_node minheap_peek(struct minheap *heap);

minheap_pop

Section titled “minheap_pop”
struct minheap_node * minheap_pop(struct minheap *heap);

minheap_node_valid

Section titled “minheap_node_valid”
bool minheap_node_valid(struct minheap_node *node);

Macros

Section titled “Macros”

MINHEAP_INIT_CAP

Section titled “MINHEAP_INIT_CAP”
#define MINHEAP_INIT_CAP 32

MINHEAP_INDEX_INVALID

Section titled “MINHEAP_INDEX_INVALID”
#define MINHEAP_INDEX_INVALID ((uint32_t) -1)

minheap_for_each

Section titled “minheap_for_each”
#define minheap_for_each(heap, node_ptr) \
    for (uint32_t __i = 0; \
         (node_ptr = ((heap)->nodes[__i]), __i < (heap)->size); __i++)

MINHEAP_SIZE

Section titled “MINHEAP_SIZE”
#define MINHEAP_SIZE(mh) (atomic_load(&mh->size))

MINHEAP_CAPACITY

Section titled “MINHEAP_CAPACITY”
#define MINHEAP_CAPACITY(mh) (atomic_load(&mh->capacity))

MINHEAP_NODE_KEY

Section titled “MINHEAP_NODE_KEY”
#define MINHEAP_NODE_KEY(mhn) (atomic_load(&mhn->key))

MINHEAP_NODE_INDEX

Section titled “MINHEAP_NODE_INDEX”
#define MINHEAP_NODE_INDEX(mhn) (atomic_load(&mhn->index))

MINHEAP_SET_SIZE

Section titled “MINHEAP_SET_SIZE”
#define MINHEAP_SET_SIZE(mh, n) (atomic_store(&mh->size, n))

MINHEAP_SET_CAPACITY

Section titled “MINHEAP_SET_CAPACITY”
#define MINHEAP_SET_CAPACITY(mh, n) (atomic_store(&mh->capacity, n))

MINHEAP_NODE_SET_KEY

Section titled “MINHEAP_NODE_SET_KEY”
#define MINHEAP_NODE_SET_KEY(mhn, n) (atomic_store(&mhn->key, n))

MINHEAP_NODE_SET_INDEX

Section titled “MINHEAP_NODE_SET_INDEX”
#define MINHEAP_NODE_SET_INDEX(mhn, n) (atomic_store(&mhn->index, n))

MINHEAP_NODE_INVALID

Section titled “MINHEAP_NODE_INVALID”
#define MINHEAP_NODE_INVALID(mhn) \
    (MINHEAP_NODE_INDEX(mhn) == MINHEAP_INDEX_INVALID)

MINHEAP_MARK_NODE_INVALID

Section titled “MINHEAP_MARK_NODE_INVALID”
#define MINHEAP_MARK_NODE_INVALID(mhn) \
    (MINHEAP_NODE_SET_INDEX(mhn, MINHEAP_INDEX_INVALID))