From 33f5fe82661086d27467821aaf418364774e360a Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Wed, 21 Mar 2012 19:21:46 -0400 Subject: Simplify binheap_delete and add binheap_decrease --- include/litmus/binheap.h | 73 ++++++++++++++++++++++-------------------------- 1 file 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 -- cgit v1.2.2