aboutsummaryrefslogtreecommitdiffstats
path: root/litmus/binheap.c
diff options
context:
space:
mode:
Diffstat (limited to 'litmus/binheap.c')
-rw-r--r--litmus/binheap.c443
1 files changed, 443 insertions, 0 deletions
diff --git a/litmus/binheap.c b/litmus/binheap.c
new file mode 100644
index 000000000000..8d42403ad52c
--- /dev/null
+++ b/litmus/binheap.c
@@ -0,0 +1,443 @@
1#include <litmus/binheap.h>
2
3//extern void dump_node_data(struct binheap_node* parent, struct binheap_node* child);
4//extern void dump_node_data2(struct binheap_handle *handle, struct binheap_node* bad_node);
5
6int binheap_is_in_this_heap(struct binheap_node *node,
7 struct binheap_handle* heap)
8{
9 if(!binheap_is_in_heap(node)) {
10 return 0;
11 }
12
13 while(node->parent != NULL) {
14 node = node->parent;
15 }
16
17 return (node == heap->root);
18}
19
20/* Update the node reference pointers. Same logic as Litmus binomial heap. */
21static void __update_ref(struct binheap_node *parent,
22 struct binheap_node *child)
23{
24 *(parent->ref_ptr) = child;
25 *(child->ref_ptr) = parent;
26
27 swap(parent->ref_ptr, child->ref_ptr);
28}
29
30/* Swaps data between two nodes. */
31static void __binheap_swap(struct binheap_node *parent,
32 struct binheap_node *child)
33{
34// if(parent == BINHEAP_POISON || child == BINHEAP_POISON) {
35// dump_node_data(parent, child);
36// BUG();
37// }
38
39 swap(parent->data, child->data);
40 __update_ref(parent, child);
41}
42
43
44/* Swaps memory and data between two nodes. Actual nodes swap instead of
45 * just data. Needed when we delete nodes from the heap.
46 */
47static void __binheap_swap_safe(struct binheap_handle *handle,
48 struct binheap_node *a,
49 struct binheap_node *b)
50{
51 swap(a->data, b->data);
52 __update_ref(a, b);
53
54 if((a->parent != NULL) && (a->parent == b->parent)) {
55 /* special case: shared parent */
56 swap(a->parent->left, a->parent->right);
57 }
58 else {
59 /* Update pointers to swap parents. */
60
61 if(a->parent) {
62 if(a == a->parent->left) {
63 a->parent->left = b;
64 }
65 else {
66 a->parent->right = b;
67 }
68 }
69
70 if(b->parent) {
71 if(b == b->parent->left) {
72 b->parent->left = a;
73 }
74 else {
75 b->parent->right = a;
76 }
77 }
78
79 swap(a->parent, b->parent);
80 }
81
82 /* swap children */
83
84 if(a->left) {
85 a->left->parent = b;
86
87 if(a->right) {
88 a->right->parent = b;
89 }
90 }
91
92 if(b->left) {
93 b->left->parent = a;
94
95 if(b->right) {
96 b->right->parent = a;
97 }
98 }
99
100 swap(a->left, b->left);
101 swap(a->right, b->right);
102
103
104 /* update next/last/root pointers */
105
106 if(a == handle->next) {
107 handle->next = b;
108 }
109 else if(b == handle->next) {
110 handle->next = a;
111 }
112
113 if(a == handle->last) {
114 handle->last = b;
115 }
116 else if(b == handle->last) {
117 handle->last = a;
118 }
119
120 if(a == handle->root) {
121 handle->root = b;
122 }
123 else if(b == handle->root) {
124 handle->root = a;
125 }
126}
127
128
129/**
130 * Update the pointer to the last node in the complete binary tree.
131 * Called internally after the root node has been deleted.
132 */
133static void __binheap_update_last(struct binheap_handle *handle)
134{
135 struct binheap_node *temp = handle->last;
136
137 /* find a "bend" in the tree. */
138 while(temp->parent && (temp == temp->parent->left)) {
139 temp = temp->parent;
140 }
141
142 /* step over to sibling if we're not at root */
143 if(temp->parent != NULL) {
144 temp = temp->parent->left;
145 }
146
147 /* now travel right as far as possible. */
148 while(temp->right != NULL) {
149 temp = temp->right;
150 }
151
152 /* take one step to the left if we're not at the bottom-most level. */
153 if(temp->left != NULL) {
154 temp = temp->left;
155 }
156
157 //BUG_ON(!(temp->left == NULL && temp->right == NULL));
158
159 handle->last = temp;
160}
161
162/**
163 * Update the pointer to the node that will take the next inserted node.
164 * Called internally after a node has been inserted.
165 */
166static void __binheap_update_next(struct binheap_handle *handle)
167{
168 struct binheap_node *temp = handle->next;
169
170 /* find a "bend" in the tree. */
171 while(temp->parent && (temp == temp->parent->right)) {
172 temp = temp->parent;
173 }
174
175 /* step over to sibling if we're not at root */
176 if(temp->parent != NULL) {
177 temp = temp->parent->right;
178 }
179
180 /* now travel left as far as possible. */
181 while(temp->left != NULL) {
182 temp = temp->left;
183 }
184
185 handle->next = temp;
186}
187
188
189
190/* bubble node up towards root */
191static void __binheap_bubble_up(
192 struct binheap_handle *handle,
193 struct binheap_node *node)
194{
195 //BUG_ON(!binheap_is_in_heap(node));
196// if(!binheap_is_in_heap(node))
197// {
198// dump_node_data2(handle, node);
199// BUG();
200// }
201
202 while((node->parent != NULL) &&
203 ((node->data == BINHEAP_POISON) /* let BINHEAP_POISON data bubble to the top */ ||
204 handle->compare(node, node->parent))) {
205 __binheap_swap(node->parent, node);
206 node = node->parent;
207
208// if(!binheap_is_in_heap(node))
209// {
210// dump_node_data2(handle, node);
211// BUG();
212// }
213 }
214}
215
216
217/* bubble node down, swapping with min-child */
218static void __binheap_bubble_down(struct binheap_handle *handle)
219{
220 struct binheap_node *node = handle->root;
221
222 while(node->left != NULL) {
223 if(node->right && handle->compare(node->right, node->left)) {
224 if(handle->compare(node->right, node)) {
225 __binheap_swap(node, node->right);
226 node = node->right;
227 }
228 else {
229 break;
230 }
231 }
232 else {
233 if(handle->compare(node->left, node)) {
234 __binheap_swap(node, node->left);
235 node = node->left;
236 }
237 else {
238 break;
239 }
240 }
241 }
242}
243
244
245
246void __binheap_add(struct binheap_node *new_node,
247 struct binheap_handle *handle,
248 void *data)
249{
250// if(binheap_is_in_heap(new_node))
251// {
252// dump_node_data2(handle, new_node);
253// BUG();
254// }
255
256 new_node->data = data;
257 new_node->ref = new_node;
258 new_node->ref_ptr = &(new_node->ref);
259
260 if(!binheap_empty(handle)) {
261 /* insert left side first */
262 if(handle->next->left == NULL) {
263 handle->next->left = new_node;
264 new_node->parent = handle->next;
265 new_node->left = NULL;
266 new_node->right = NULL;
267
268 handle->last = new_node;
269
270 __binheap_bubble_up(handle, new_node);
271 }
272 else {
273 /* left occupied. insert right. */
274 handle->next->right = new_node;
275 new_node->parent = handle->next;
276 new_node->left = NULL;
277 new_node->right = NULL;
278
279 handle->last = new_node;
280
281 __binheap_update_next(handle);
282 __binheap_bubble_up(handle, new_node);
283 }
284 }
285 else {
286 /* first node in heap */
287
288 new_node->parent = NULL;
289 new_node->left = NULL;
290 new_node->right = NULL;
291
292 handle->root = new_node;
293 handle->next = new_node;
294 handle->last = new_node;
295 }
296}
297
298
299
300/**
301 * Removes the root node from the heap. The node is removed after coalescing
302 * the binheap_node with its original data pointer at the root of the tree.
303 *
304 * The 'last' node in the tree is then swapped up to the root and bubbled
305 * down.
306 */
307void __binheap_delete_root(struct binheap_handle *handle,
308 struct binheap_node *container)
309{
310 struct binheap_node *root = handle->root;
311
312// if(!binheap_is_in_heap(container))
313// {
314// dump_node_data2(handle, container);
315// BUG();
316// }
317
318 if(root != container) {
319 /* coalesce */
320 __binheap_swap_safe(handle, root, container);
321 root = container;
322 }
323
324 if(handle->last != root) {
325 /* swap 'last' node up to root and bubble it down. */
326
327 struct binheap_node *to_move = handle->last;
328
329 if(to_move->parent != root) {
330 handle->next = to_move->parent;
331
332 if(handle->next->right == to_move) {
333 /* disconnect from parent */
334 to_move->parent->right = NULL;
335 handle->last = handle->next->left;
336 }
337 else {
338 /* find new 'last' before we disconnect */
339 __binheap_update_last(handle);
340
341 /* disconnect from parent */
342 to_move->parent->left = NULL;
343 }
344 }
345 else {
346 /* 'last' is direct child of root */
347
348 handle->next = to_move;
349
350 if(to_move == to_move->parent->right) {
351 to_move->parent->right = NULL;
352 handle->last = to_move->parent->left;
353 }
354 else {
355 to_move->parent->left = NULL;
356 handle->last = to_move;
357 }
358 }
359 to_move->parent = NULL;
360
361 /* reconnect as root. We can't just swap data ptrs since root node
362 * may be freed after this function returns.
363 */
364 to_move->left = root->left;
365 to_move->right = root->right;
366 if(to_move->left != NULL) {
367 to_move->left->parent = to_move;
368 }
369 if(to_move->right != NULL) {
370 to_move->right->parent = to_move;
371 }
372
373 handle->root = to_move;
374
375 /* bubble down */
376 __binheap_bubble_down(handle);
377 }
378 else {
379 /* removing last node in tree */
380 handle->root = NULL;
381 handle->next = NULL;
382 handle->last = NULL;
383 }
384
385 /* mark as removed */
386 container->parent = BINHEAP_POISON;
387}
388
389
390/**
391 * Delete an arbitrary node. Bubble node to delete up to the root,
392 * and then delete to root.
393 */
394void __binheap_delete(struct binheap_node *node_to_delete,
395 struct binheap_handle *handle)
396{
397 struct binheap_node *target = node_to_delete->ref;
398 void *temp_data = target->data;
399
400// if(!binheap_is_in_heap(node_to_delete))
401// {
402// dump_node_data2(handle, node_to_delete);
403// BUG();
404// }
405//
406// if(!binheap_is_in_heap(target))
407// {
408// dump_node_data2(handle, target);
409// BUG();
410// }
411
412 /* temporarily set data to null to allow node to bubble up to the top. */
413 target->data = BINHEAP_POISON;
414
415 __binheap_bubble_up(handle, target);
416 __binheap_delete_root(handle, node_to_delete);
417
418 node_to_delete->data = temp_data; /* restore node data pointer */
419 //node_to_delete->parent = BINHEAP_POISON; /* poison the node */
420}
421
422/**
423 * Bubble up a node whose pointer has decreased in value.
424 */
425void __binheap_decrease(struct binheap_node *orig_node,
426 struct binheap_handle *handle)
427{
428 struct binheap_node *target = orig_node->ref;
429
430// if(!binheap_is_in_heap(orig_node))
431// {
432// dump_node_data2(handle, orig_node);
433// BUG();
434// }
435//
436// if(!binheap_is_in_heap(target))
437// {
438// dump_node_data2(handle, target);
439// BUG();
440// }
441//
442 __binheap_bubble_up(handle, target);
443}
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-27 11:48:49 -0500