1#include <kassert.h>
2#include <structures/pairing_heap.h>
3
4void pairing_heap_init(struct pairing_heap *h, pairing_cmp_t cmp) {
5 h->root = NULL;
6 h->cmp = cmp;
7 spinlock_init(lock: &h->lock);
8}
9
10static struct pairing_node *pairing_merge(struct pairing_heap *h,
11 struct pairing_node *a,
12 struct pairing_node *b) {
13 if (!a)
14 return b;
15
16 if (!b)
17 return a;
18
19 SPINLOCK_ASSERT_HELD(&h->lock);
20
21 if (h->cmp(a, b) <= 0) {
22 /* a is smaller, b becomes child of a */
23 b->parent = a;
24 b->sibling = a->child;
25 a->child = b;
26 return a;
27 } else {
28 /* b is smaller, a becomes child of b */
29 a->parent = b;
30 a->sibling = b->child;
31 b->child = a;
32 return b;
33 }
34}
35
36void pairing_heap_insert(struct pairing_heap *h, struct pairing_node *node) {
37 enum irql irql = spin_lock(lock: &h->lock);
38 node->parent = NULL;
39 node->child = NULL;
40 node->sibling = NULL;
41
42 h->root = pairing_merge(h, a: h->root, b: node);
43 spin_unlock(lock: &h->lock, old: irql);
44}
45
46struct pairing_node *pairing_heap_peek(struct pairing_heap *h) {
47 enum irql irql = spin_lock(lock: &h->lock);
48 struct pairing_node *n = h->root;
49 spin_unlock(lock: &h->lock, old: irql);
50 return n;
51}
52
53static struct pairing_node *pairing_two_pass(struct pairing_heap *h,
54 struct pairing_node *first) {
55 if (!first || !first->sibling)
56 return first;
57
58 SPINLOCK_ASSERT_HELD(&h->lock);
59
60 struct pairing_node *a = first;
61 struct pairing_node *b = first->sibling;
62 struct pairing_node *rest = b->sibling;
63
64 a->sibling = NULL;
65 b->sibling = NULL;
66
67 return pairing_merge(h, a: pairing_merge(h, a, b), b: pairing_two_pass(h, first: rest));
68}
69
70struct pairing_node *pairing_heap_pop(struct pairing_heap *h) {
71 enum irql irql = spin_lock(lock: &h->lock);
72 struct pairing_node *root = h->root;
73
74 if (!root)
75 goto out;
76
77 h->root = pairing_two_pass(h, first: root->child);
78
79 if (h->root)
80 h->root->parent = NULL;
81
82 root->child = NULL;
83 root->sibling = NULL;
84 root->parent = NULL;
85
86out:
87 spin_unlock(lock: &h->lock, old: irql);
88 return root;
89}
90
91void pairing_heap_decrease(struct pairing_heap *h, struct pairing_node *node) {
92 /* If already root, nothing to do */
93 enum irql irql = spin_lock(lock: &h->lock);
94 if (node == h->root)
95 goto out;
96
97 /* Cut node from its position */
98 struct pairing_node *parent = node->parent;
99
100 /* unlink node from siblings */
101 if (parent->child == node) {
102 parent->child = node->sibling;
103 } else {
104 struct pairing_node *s = parent->child;
105 while (s->sibling != node)
106 s = s->sibling;
107 s->sibling = node->sibling;
108 }
109
110 node->parent = NULL;
111 node->sibling = NULL;
112
113 /* Merge back with root */
114 h->root = pairing_merge(h, a: h->root, b: node);
115out:
116 spin_unlock(lock: &h->lock, old: irql);
117}
118