binomial heap: support decrease() operation

Used to adjust position of heap node after
the key of the node was decreased
(= made more important). Cannot be used if
key was increased (= made less important).

2 files changed, 34 insertions, 4 deletions

diff --git a/include/litmus/heap.h b/include/litmus/heap.h
index 19230f550f..da959b0bec 100644
--- a/include/litmus/heap.h
+++ b/include/litmus/heap.h
@@ -1,6 +1,6 @@
 /* heaps.h -- Binomial Heaps
  *
- * (c) 2008 Bjoern Brandenburg
+ * (c) 2008, 2009 Bjoern Brandenburg
  */
 
 #ifndef HEAP_H
@@ -57,6 +57,9 @@ struct heap_node* heap_peek(heap_prio_t higher_prio,
 struct heap_node* heap_take(heap_prio_t higher_prio,
                             struct heap* heap);
 
+void heap_uncache_min(heap_prio_t higher_prio, struct heap* heap);
+int  heap_decrease(heap_prio_t higher_prio, struct heap_node* node);
+
 void heap_delete(heap_prio_t higher_prio,
                  struct heap* heap,
                  struct heap_node* node);
diff --git a/litmus/heap.c b/litmus/heap.c
index 4d0d7b96ae..112d14da46 100644
--- a/litmus/heap.c
+++ b/litmus/heap.c
@@ -175,7 +175,7 @@ void heap_insert(heap_prio_t higher_prio, struct heap* heap,
                 __heap_union(higher_prio, heap, node);
 }
 
-static void __uncache_min(heap_prio_t higher_prio, struct heap* heap)
+void heap_uncache_min(heap_prio_t higher_prio, struct heap* heap)
 {
         struct heap_node* min;
         if (heap->min) {
@@ -190,8 +190,8 @@ void heap_union(heap_prio_t higher_prio,
                 struct heap* target, struct heap* addition)
 {
         /* first insert any cached minima, if necessary */
-        __uncache_min(higher_prio, target);
-        __uncache_min(higher_prio, addition);
+        heap_uncache_min(higher_prio, target);
+        heap_uncache_min(higher_prio, addition);
         __heap_union(higher_prio, target, addition->head);
         /* this is a destructive merge */
         addition->head = NULL;
@@ -218,6 +218,33 @@ struct heap_node* heap_take(heap_prio_t higher_prio,
         return node;
 }
 
+int heap_decrease(heap_prio_t higher_prio, struct heap_node* node)
+{
+        struct heap_node  *parent;
+        struct heap_node** tmp_ref;
+        void* tmp;
+
+        /* bubble up */
+        parent = node->parent;
+        while (parent && higher_prio(node, parent)) {
+                /* swap parent and node */
+                tmp           = parent->value;
+                parent->value = node->value;
+                node->value   = tmp;
+                /* swap references */
+                *(parent->ref) = node;
+                *(node->ref)   = parent;
+                tmp_ref        = parent->ref;
+                parent->ref    = node->ref;
+                node->ref      = tmp_ref;
+                /* step up */
+                node   = parent;
+                parent = node->parent;
+        }
+
+        return parent != NULL;
+}
+
 void heap_delete(heap_prio_t higher_prio, struct heap* heap,
                  struct heap_node* node)
 {