Simplify binheap_delete and add binheap_decrease

1 files changed, 33 insertions, 40 deletions

diff --git a/include/litmus/binheap.h b/include/litmus/binheap.h
index 9fe5dc13d032..fd4c0a318b96 100644
--- a/include/litmus/binheap.h
+++ b/include/litmus/binheap.h
@@ -80,9 +80,9 @@ container_of((ptr), type, member)
 /**
  * binheap_top_entry - get the struct for the node at the top of the heap.
  *  Only valid when called upon the heap handle node.
- * @ptr:                the special heap-handle node.
- * @type:          the type of the struct the head is embedded in.
- * @member:      the name of the binheap_struct within the (type) struct.
+ * @ptr:    the special heap-handle node.
+ * @type:   the type of the struct the head is embedded in.
+ * @member:     the name of the binheap_struct within the (type) struct.
  */
 #define binheap_top_entry(ptr, type, member) \
 binheap_entry((ptr)->root, type, member)
@@ -90,7 +90,7 @@ binheap_entry((ptr)->root, type, member)
 /**
  * binheap_delete_root - remove the root element from the heap.
  * @handle:      handle to the heap.
- * @type:          the type of the struct the head is embedded in.
+ * @type:    the type of the struct the head is embedded in.
  * @member:      the name of the binheap_struct within the (type) struct.
  */
 #define binheap_delete_root(handle, type, member) \
@@ -100,22 +100,30 @@ __binheap_delete_root((handle), &((type *)((handle)->root->data))->member)
  * binheap_delete - remove an arbitrary element from the heap.
  * @to_delete:  pointer to node to be removed.
  * @handle:      handle to the heap.
- * @type:          the type of the struct the head is embedded in.
- * @member:      the name of the binheap_struct within the (type) struct.
  */
-#define binheap_delete(to_delete, handle, type, member) \
-__binheap_delete((to_delete), &((((type*)((to_delete)->data))->member)), (handle))
+#define binheap_delete(to_delete, handle) \
+__binheap_delete((to_delete), (handle))
 
 /**
  * binheap_add - insert an element to the heap
- * new_node:    node to add.
+ * new_node: node to add.
  * @handle:      handle to the heap.
- * @type:          the type of the struct the head is embedded in.
+ * @type:    the type of the struct the head is embedded in.
  * @member:      the name of the binheap_struct within the (type) struct.
  */
 #define binheap_add(new_node, handle, type, member) \
 __binheap_add((new_node), (handle), container_of((new_node), type, member))
 
+/**
+ * binheap_decrease - re-eval the position of a node (based upon its
+ * original data pointer).
+ * @handle: handle to the heap.
+ * @orig_node: node that was associated with the data pointer
+ *             (whose value has changed) when said pointer was
+ *             added to the heap.
+ */
+#define binheap_decrease(orig_node, handle) \
+__binheap_decrease((orig_node), (handle))
 
 #define BINHEAP_NODE_INIT() { NULL, NULL, NULL, NULL , NULL, NULL}
 
@@ -494,43 +502,17 @@ static inline void __binheap_delete_root(struct binheap_handle *handle,
 
 
 /**
- * Delete an arbitrary node.  We first coalesce, then bubble
- * node to delete up to the root, and then delete to root.
+ * Delete an arbitrary node.  Bubble node to delete up to the root,
+ * and then delete to root.
  */
 static inline void __binheap_delete(
                                                                 struct binheap_node *node_to_delete,
-                                                                struct binheap_node *user_of_node,
                                                                 struct binheap_handle *handle)
 {
-        struct binheap_node *root, *target;
-        void *temp_data;
-
-        /* Position the node to delete at the root. */
-
-        /* coalesce: swap nodes with user of the node to delete. */
-        if(node_to_delete != user_of_node) {
-                /* we need to take container's memory/node out of the heap,
-                 * so swap with the user of the node
-                 */
-                __binheap_swap_safe(handle, user_of_node, node_to_delete);
-        }
-
-        root = handle->root;
-
-        /* Move the _node_ to the root */
-        if(root != node_to_delete) {
-                __binheap_swap_safe(handle, root, node_to_delete);
-                node_to_delete = root;
-        }
-
-        node_to_delete = handle->root;
-        target  = node_to_delete->ref;
-
-        /* Bubble the data pointer back up to its node, which has already been
-         * positioned at the root. */
+        struct binheap_node *target = node_to_delete->ref;
+        void *temp_data = target->data;
 
         /* temporarily set data to null to allow node to bubble up to the top. */
-        temp_data = target->data;
         target->data = NULL;
 
         __binheap_bubble_up(handle, target);
@@ -539,5 +521,16 @@ static inline void __binheap_delete(
         node_to_delete->data = temp_data;  /* restore node data pointer */
 }
 
+/**
+ * Bubble up a node whose pointer has decreased in value.
+ */
+static inline void __binheap_decrease(
+                                struct binheap_node *orig_node,
+                                struct binheap_handle *handle)
+{
+        struct binheap_node *target = orig_node->ref;
+        __binheap_bubble_up(handle, target);
+}
+
 #endif