1 files changed, 387 insertions, 0 deletions
diff --git a/litmus/binheap.c b/litmus/binheap.c
new file mode 100644
index 000000000000..f76260e64b0b
--- /dev/null
+++ b/litmus/binheap.c
@@ -0,0 +1,387 @@
+#include <litmus/binheap.h>
+int binheap_is_in_this_heap(struct binheap_node *node,
+        struct binheap_handle* heap)
+{
+        if(!binheap_is_in_heap(node)) {
+                return 0;
+        }
+        
+        while(node->parent != NULL) {
+                node = node->parent;
+        }
+        
+        return (node == heap->root);
+}
+/* Update the node reference pointers.  Same logic as Litmus binomial heap. */
+static void __update_ref(struct binheap_node *parent,
+        struct binheap_node *child)
+{
+        *(parent->ref_ptr) = child;
+        *(child->ref_ptr) = parent;
+        
+        swap(parent->ref_ptr, child->ref_ptr);
+}
+/* Swaps data between two nodes. */
+static void __binheap_swap(struct binheap_node *parent,
+        struct binheap_node *child)
+{
+        swap(parent->data, child->data);
+        __update_ref(parent, child);
+}
+/* Swaps memory and data between two nodes. Actual nodes swap instead of
+ * just data.  Needed when we delete nodes from the heap.
+ */
+static void __binheap_swap_safe(struct binheap_handle *handle,
+        struct binheap_node *a,
+        struct binheap_node *b)
+{
+        swap(a->data, b->data);
+        __update_ref(a, b);
+        
+        if((a->parent != NULL) && (a->parent == b->parent)) {
+                /* special case: shared parent */
+                swap(a->parent->left, a->parent->right);
+        }
+        else {
+                /* Update pointers to swap parents. */
+                
+                if(a->parent) {
+                        if(a == a->parent->left) {
+                                a->parent->left = b;
+                        }
+                        else {
+                                a->parent->right = b;
+                        }
+                }
+                
+                if(b->parent) {
+                        if(b == b->parent->left) {
+                                b->parent->left = a;
+                        }
+                        else {
+                                b->parent->right = a;
+                        }
+                }
+                
+                swap(a->parent, b->parent);
+        }
+        
+        /* swap children */
+        
+        if(a->left) {
+                a->left->parent = b;
+                
+                if(a->right) {
+                        a->right->parent = b;
+                }
+        }
+        
+        if(b->left) {
+                b->left->parent = a;
+                
+                if(b->right) {
+                        b->right->parent = a;
+                }
+        }
+        
+        swap(a->left, b->left);
+        swap(a->right, b->right);
+        
+        
+        /* update next/last/root pointers */
+        
+        if(a == handle->next) {
+                handle->next = b;
+        }
+        else if(b == handle->next) {
+                handle->next = a;
+        }
+        
+        if(a == handle->last) {
+                handle->last = b;
+        }
+        else if(b == handle->last) {
+                handle->last = a;
+        }
+        
+        if(a == handle->root) {
+                handle->root = b;
+        }
+        else if(b == handle->root) {
+                handle->root = a;
+        }
+}
+/**
+ * Update the pointer to the last node in the complete binary tree.
+ * Called internally after the root node has been deleted.
+ */
+static void __binheap_update_last(struct binheap_handle *handle)
+{
+        struct binheap_node *temp = handle->last;
+        
+        /* find a "bend" in the tree. */
+        while(temp->parent && (temp == temp->parent->left)) {
+                temp = temp->parent;
+        }
+        
+        /* step over to sibling if we're not at root */
+        if(temp->parent != NULL) {
+                temp = temp->parent->left;
+        }
+        
+        /* now travel right as far as possible. */
+        while(temp->right != NULL) {
+                temp = temp->right;
+        }
+        
+        /* take one step to the left if we're not at the bottom-most level. */
+        if(temp->left != NULL) {
+                temp = temp->left;
+        }
+        
+        //BUG_ON(!(temp->left == NULL && temp->right == NULL));
+        
+        handle->last = temp;
+}
+/**
+ * Update the pointer to the node that will take the next inserted node.
+ * Called internally after a node has been inserted.
+ */
+static void __binheap_update_next(struct binheap_handle *handle)
+{
+        struct binheap_node *temp = handle->next;
+        
+        /* find a "bend" in the tree. */
+        while(temp->parent && (temp == temp->parent->right)) {
+                temp = temp->parent;
+        }
+        
+        /* step over to sibling if we're not at root */
+        if(temp->parent != NULL) {
+                temp = temp->parent->right;
+        }
+        
+        /* now travel left as far as possible. */
+        while(temp->left != NULL) {
+                temp = temp->left;
+        }
+        
+        handle->next = temp;
+}
+/* bubble node up towards root */
+static void __binheap_bubble_up(
+        struct binheap_handle *handle,
+        struct binheap_node *node)
+{
+        /* Note: NULL data pointers are used internally for arbitrary delete */
+        while((node->parent != NULL) &&
+                  ((node->data == BINHEAP_POISON) /* let BINHEAP_POISON data bubble to the top */ ||
+                   handle->compare(node, node->parent))) {
+                          __binheap_swap(node->parent, node);
+                          node = node->parent;
+        }
+}
+/* bubble node down, swapping with min-child */
+static void __binheap_bubble_down(struct binheap_handle *handle)
+{
+        struct binheap_node *node = handle->root;
+        
+        while(node->left != NULL) {
+                if(node->right && handle->compare(node->right, node->left)) {
+                        if(handle->compare(node->right, node)) {
+                                __binheap_swap(node, node->right);
+                                node = node->right;
+                        }
+                        else {
+                                break;
+                        }
+                }
+                else {
+                        if(handle->compare(node->left, node)) {
+                                __binheap_swap(node, node->left);
+                                node = node->left;
+                        }
+                        else {
+                                break;
+                        }
+                }
+        }
+}
+void __binheap_add(struct binheap_node *new_node,
+        struct binheap_handle *handle,
+        void *data)
+{
+        new_node->data = data;
+        new_node->ref = new_node;
+        new_node->ref_ptr = &(new_node->ref);
+        
+        if(!binheap_empty(handle)) {
+                /* insert left side first */
+                if(handle->next->left == NULL) {
+                        handle->next->left = new_node;
+                        new_node->parent = handle->next;
+                        new_node->left = NULL;
+                        new_node->right = NULL;
+                        
+                        handle->last = new_node;
+                        
+                        __binheap_bubble_up(handle, new_node);
+                }
+                else {
+                        /* left occupied. insert right. */
+                        handle->next->right = new_node;
+                        new_node->parent = handle->next;
+                        new_node->left = NULL;
+                        new_node->right = NULL;
+                        
+                        handle->last = new_node;
+                        
+                        __binheap_update_next(handle);
+                        __binheap_bubble_up(handle, new_node);
+                }
+        }
+        else {
+                /* first node in heap */
+                
+                new_node->parent = NULL;
+                new_node->left = NULL;
+                new_node->right = NULL;
+                
+                handle->root = new_node;
+                handle->next = new_node;
+                handle->last = new_node;
+        }
+}
+/**
+ * Removes the root node from the heap. The node is removed after coalescing
+ * the binheap_node with its original data pointer at the root of the tree.
+ *
+ * The 'last' node in the tree is then swapped up to the root and bubbled
+ * down.
+ */
+void __binheap_delete_root(struct binheap_handle *handle,
+        struct binheap_node *container)
+{
+        struct binheap_node *root = handle->root;
+        
+        if(root != container) {
+                /* coalesce */
+                __binheap_swap_safe(handle, root, container);
+                root = container;
+        }
+        
+        if(handle->last != root) {
+                /* swap 'last' node up to root and bubble it down. */
+                
+                struct binheap_node *to_move = handle->last;
+                
+                if(to_move->parent != root) {
+                        handle->next = to_move->parent;
+                        
+                        if(handle->next->right == to_move) {
+                                /* disconnect from parent */
+                                to_move->parent->right = NULL;
+                                handle->last = handle->next->left;
+                        }
+                        else {
+                                /* find new 'last' before we disconnect */
+                                __binheap_update_last(handle);
+                                
+                                /* disconnect from parent */
+                                to_move->parent->left = NULL;
+                        }
+                }
+                else {
+                        /* 'last' is direct child of root */
+                        
+                        handle->next = to_move;
+                        
+                        if(to_move == to_move->parent->right) {
+                                to_move->parent->right = NULL;
+                                handle->last = to_move->parent->left;
+                        }
+                        else {
+                                to_move->parent->left = NULL;
+                                handle->last = to_move;
+                        }
+                }
+                to_move->parent = NULL;
+                
+                /* reconnect as root.  We can't just swap data ptrs since root node
+                 * may be freed after this function returns.
+                 */
+                to_move->left = root->left;
+                to_move->right = root->right;
+                if(to_move->left != NULL) {
+                        to_move->left->parent = to_move;
+                }
+                if(to_move->right != NULL) {
+                        to_move->right->parent = to_move;
+                }
+                
+                handle->root = to_move;
+                
+                /* bubble down */
+                __binheap_bubble_down(handle);
+        }
+        else {
+                /* removing last node in tree */
+                handle->root = NULL;
+                handle->next = NULL;
+                handle->last = NULL;
+        }
+        
+        /* mark as removed */
+        container->parent = BINHEAP_POISON;
+}
+/**
+ * Delete an arbitrary node.  Bubble node to delete up to the root,
+ * and then delete to root.
+ */
+void __binheap_delete(struct binheap_node *node_to_delete,
+        struct binheap_handle *handle)
+{
+        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. */
+        target->data = BINHEAP_POISON;
+        
+        __binheap_bubble_up(handle, target);
+        __binheap_delete_root(handle, node_to_delete);
+        
+        node_to_delete->data = temp_data;  /* restore node data pointer */
+        node_to_delete->parent = BINHEAP_POISON; /* poison the node */
+}
+/**
+ * Bubble up a node whose pointer has decreased in value.
+ */
+void __binheap_decrease(struct binheap_node *orig_node,
+        struct binheap_handle *handle)
+{
+        struct binheap_node *target = orig_node->ref;
+        __binheap_bubble_up(handle, target);
+}

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