aboutsummaryrefslogtreecommitdiffstats
path: root/litmus/bheap.c
diff options
context:
space:
mode:
Diffstat (limited to 'litmus/bheap.c')
-rw-r--r--litmus/bheap.c314
1 files changed, 314 insertions, 0 deletions
diff --git a/litmus/bheap.c b/litmus/bheap.c
new file mode 100644
index 000000000000..528af97f18a6
--- /dev/null
+++ b/litmus/bheap.c
@@ -0,0 +1,314 @@
1#include "linux/kernel.h"
2#include "litmus/bheap.h"
3
4void bheap_init(struct bheap* heap)
5{
6 heap->head = NULL;
7 heap->min = NULL;
8}
9
10void bheap_node_init(struct bheap_node** _h, void* value)
11{
12 struct bheap_node* h = *_h;
13 h->parent = NULL;
14 h->next = NULL;
15 h->child = NULL;
16 h->degree = NOT_IN_HEAP;
17 h->value = value;
18 h->ref = _h;
19}
20
21
22/* make child a subtree of root */
23static void __bheap_link(struct bheap_node* root,
24 struct bheap_node* child)
25{
26 child->parent = root;
27 child->next = root->child;
28 root->child = child;
29 root->degree++;
30}
31
32/* merge root lists */
33static struct bheap_node* __bheap_merge(struct bheap_node* a,
34 struct bheap_node* b)
35{
36 struct bheap_node* head = NULL;
37 struct bheap_node** pos = &head;
38
39 while (a && b) {
40 if (a->degree < b->degree) {
41 *pos = a;
42 a = a->next;
43 } else {
44 *pos = b;
45 b = b->next;
46 }
47 pos = &(*pos)->next;
48 }
49 if (a)
50 *pos = a;
51 else
52 *pos = b;
53 return head;
54}
55
56/* reverse a linked list of nodes. also clears parent pointer */
57static struct bheap_node* __bheap_reverse(struct bheap_node* h)
58{
59 struct bheap_node* tail = NULL;
60 struct bheap_node* next;
61
62 if (!h)
63 return h;
64
65 h->parent = NULL;
66 while (h->next) {
67 next = h->next;
68 h->next = tail;
69 tail = h;
70 h = next;
71 h->parent = NULL;
72 }
73 h->next = tail;
74 return h;
75}
76
77static void __bheap_min(bheap_prio_t higher_prio, struct bheap* heap,
78 struct bheap_node** prev, struct bheap_node** node)
79{
80 struct bheap_node *_prev, *cur;
81 *prev = NULL;
82
83 if (!heap->head) {
84 *node = NULL;
85 return;
86 }
87
88 *node = heap->head;
89 _prev = heap->head;
90 cur = heap->head->next;
91 while (cur) {
92 if (higher_prio(cur, *node)) {
93 *node = cur;
94 *prev = _prev;
95 }
96 _prev = cur;
97 cur = cur->next;
98 }
99}
100
101static void __bheap_union(bheap_prio_t higher_prio, struct bheap* heap,
102 struct bheap_node* h2)
103{
104 struct bheap_node* h1;
105 struct bheap_node *prev, *x, *next;
106 if (!h2)
107 return;
108 h1 = heap->head;
109 if (!h1) {
110 heap->head = h2;
111 return;
112 }
113 h1 = __bheap_merge(h1, h2);
114 prev = NULL;
115 x = h1;
116 next = x->next;
117 while (next) {
118 if (x->degree != next->degree ||
119 (next->next && next->next->degree == x->degree)) {
120 /* nothing to do, advance */
121 prev = x;
122 x = next;
123 } else if (higher_prio(x, next)) {
124 /* x becomes the root of next */
125 x->next = next->next;
126 __bheap_link(x, next);
127 } else {
128 /* next becomes the root of x */
129 if (prev)
130 prev->next = next;
131 else
132 h1 = next;
133 __bheap_link(next, x);
134 x = next;
135 }
136 next = x->next;
137 }
138 heap->head = h1;
139}
140
141static struct bheap_node* __bheap_extract_min(bheap_prio_t higher_prio,
142 struct bheap* heap)
143{
144 struct bheap_node *prev, *node;
145 __bheap_min(higher_prio, heap, &prev, &node);
146 if (!node)
147 return NULL;
148 if (prev)
149 prev->next = node->next;
150 else
151 heap->head = node->next;
152 __bheap_union(higher_prio, heap, __bheap_reverse(node->child));
153 return node;
154}
155
156/* insert (and reinitialize) a node into the heap */
157void bheap_insert(bheap_prio_t higher_prio, struct bheap* heap,
158 struct bheap_node* node)
159{
160 struct bheap_node *min;
161 node->child = NULL;
162 node->parent = NULL;
163 node->next = NULL;
164 node->degree = 0;
165 if (heap->min && higher_prio(node, heap->min)) {
166 /* swap min cache */
167 min = heap->min;
168 min->child = NULL;
169 min->parent = NULL;
170 min->next = NULL;
171 min->degree = 0;
172 __bheap_union(higher_prio, heap, min);
173 heap->min = node;
174 } else
175 __bheap_union(higher_prio, heap, node);
176}
177
178void bheap_uncache_min(bheap_prio_t higher_prio, struct bheap* heap)
179{
180 struct bheap_node* min;
181 if (heap->min) {
182 min = heap->min;
183 heap->min = NULL;
184 bheap_insert(higher_prio, heap, min);
185 }
186}
187
188/* merge addition into target */
189void bheap_union(bheap_prio_t higher_prio,
190 struct bheap* target, struct bheap* addition)
191{
192 /* first insert any cached minima, if necessary */
193 bheap_uncache_min(higher_prio, target);
194 bheap_uncache_min(higher_prio, addition);
195 __bheap_union(higher_prio, target, addition->head);
196 /* this is a destructive merge */
197 addition->head = NULL;
198}
199
200struct bheap_node* bheap_peek(bheap_prio_t higher_prio,
201 struct bheap* heap)
202{
203 if (!heap->min)
204 heap->min = __bheap_extract_min(higher_prio, heap);
205 return heap->min;
206}
207
208struct bheap_node* bheap_take(bheap_prio_t higher_prio,
209 struct bheap* heap)
210{
211 struct bheap_node *node;
212 if (!heap->min)
213 heap->min = __bheap_extract_min(higher_prio, heap);
214 node = heap->min;
215 heap->min = NULL;
216 if (node)
217 node->degree = NOT_IN_HEAP;
218 return node;
219}
220
221int bheap_decrease(bheap_prio_t higher_prio, struct bheap_node* node)
222{
223 struct bheap_node *parent;
224 struct bheap_node** tmp_ref;
225 void* tmp;
226
227 /* bubble up */
228 parent = node->parent;
229 while (parent && higher_prio(node, parent)) {
230 /* swap parent and node */
231 tmp = parent->value;
232 parent->value = node->value;
233 node->value = tmp;
234 /* swap references */
235 *(parent->ref) = node;
236 *(node->ref) = parent;
237 tmp_ref = parent->ref;
238 parent->ref = node->ref;
239 node->ref = tmp_ref;
240 /* step up */
241 node = parent;
242 parent = node->parent;
243 }
244
245 return parent != NULL;
246}
247
248void bheap_delete(bheap_prio_t higher_prio, struct bheap* heap,
249 struct bheap_node* node)
250{
251 struct bheap_node *parent, *prev, *pos;
252 struct bheap_node** tmp_ref;
253 void* tmp;
254
255 if (heap->min != node) {
256 /* bubble up */
257 parent = node->parent;
258 while (parent) {
259 /* swap parent and node */
260 tmp = parent->value;
261 parent->value = node->value;
262 node->value = tmp;
263 /* swap references */
264 *(parent->ref) = node;
265 *(node->ref) = parent;
266 tmp_ref = parent->ref;
267 parent->ref = node->ref;
268 node->ref = tmp_ref;
269 /* step up */
270 node = parent;
271 parent = node->parent;
272 }
273 /* now delete:
274 * first find prev */
275 prev = NULL;
276 pos = heap->head;
277 while (pos != node) {
278 prev = pos;
279 pos = pos->next;
280 }
281 /* we have prev, now remove node */
282 if (prev)
283 prev->next = node->next;
284 else
285 heap->head = node->next;
286 __bheap_union(higher_prio, heap, __bheap_reverse(node->child));
287 } else
288 heap->min = NULL;
289 node->degree = NOT_IN_HEAP;
290}
291
292/* allocate a heap node for value and insert into the heap */
293int bheap_add(bheap_prio_t higher_prio, struct bheap* heap,
294 void* value, int gfp_flags)
295{
296 struct bheap_node* hn = bheap_node_alloc(gfp_flags);
297 if (likely(hn)) {
298 bheap_node_init(&hn, value);
299 bheap_insert(higher_prio, heap, hn);
300 }
301 return hn != NULL;
302}
303
304void* bheap_take_del(bheap_prio_t higher_prio,
305 struct bheap* heap)
306{
307 struct bheap_node* hn = bheap_take(higher_prio, heap);
308 void* ret = NULL;
309 if (hn) {
310 ret = hn->value;
311 bheap_node_free(hn);
312 }
313 return ret;
314}
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-29 00:13:48 -0500