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