1/* @title: Pairing heap */
2#pragma once
3#include <stddef.h>
4#include <stdint.h>
5#include <sync/spinlock.h>
6
7struct pairing_node {
8 struct pairing_node *parent;
9 struct pairing_node *child;
10 struct pairing_node *sibling;
11};
12
13typedef int32_t (*pairing_cmp_t)(struct pairing_node *, struct pairing_node *);
14
15struct pairing_heap {
16 struct pairing_node *root;
17 pairing_cmp_t cmp;
18 struct spinlock lock;
19};
20void pairing_heap_init(struct pairing_heap *h, pairing_cmp_t cmp);
21void pairing_heap_insert(struct pairing_heap *h, struct pairing_node *node);
22struct pairing_node *pairing_heap_peek(struct pairing_heap *h);
23struct pairing_node *pairing_heap_pop(struct pairing_heap *h);
24void pairing_heap_decrease(struct pairing_heap *h, struct pairing_node *node);
25
26static inline void pairing_node_init(struct pairing_node *pn) {
27 pn->parent = NULL;
28 pn->child = NULL;
29 pn->sibling = NULL;
30}
31