From 5b73afc4eb1b0303cb92eb29a2ecc59c1db69537 Mon Sep 17 00:00:00 2001
From: Glenn Elliott <gelliott@cs.unc.edu>
Date: Wed, 21 Mar 2012 14:59:52 -0400
Subject: Binary heap implementation

Motivation: Linux's prio_heap.h is of fixed size. Litmus's binomial
heap may be overkill (and perhaps not general enough) for some applications.

Implemented in the style of linked lists.
---
 include/litmus/binheap.h | 543 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 543 insertions(+)
 create mode 100644 include/litmus/binheap.h

diff --git a/include/litmus/binheap.h b/include/litmus/binheap.h
new file mode 100644
index 000000000000..b8dd8e03da60
--- /dev/null
+++ b/include/litmus/binheap.h
@@ -0,0 +1,543 @@
+#ifndef LITMUS_BINARY_HEAP_H
+#define LITMUS_BINARY_HEAP_H
+
+/**
+ * Simple binary heap with add, arbitrary delete, delete_root, and top
+ * operations.
+ *
+ * Style meant to conform with list.h.
+ *
+ * Motivation: Linux's prio_heap.h is of fixed size. Litmus's binomial
+ * heap may be overkill (and perhaps not general enough) for some applications.
+ *
+ * Note: In order to make node swaps fast, a node inserted with a data pointer
+ * may not always hold said data pointer. This is similar to the binomial heap
+ * implementation. This does make node deletion tricky since we have to
+ * (1) locate the node that holds the data pointer to delete, and (2) the
+ * node that was originally inserted with said data pointer. These have to be
+ * coalesced into a single node before removal (see usage of
+ * __binheap_safe_swap()). We have to track node references to accomplish this.
+ */
+
+struct binheap_node {
+	void	*data;
+	struct binheap_node *parent;
+	struct binheap_node *left;
+	struct binheap_node *right;
+
+	/* pointer to binheap_node that holds *data for which this binheap_node
+	 * was originally inserted.  (*data "owns" this node)
+	 */
+	struct binheap_node *ref;
+	struct binheap_node **ref_ptr;
+};
+
+/**
+ * Signature of compator function.  Assumed 'less-than' (min-heap).
+ * Pass in 'greater-than' for max-heap.
+ *
+ * TODO: Consider macor-based implementation that allows comparator to be
+ * inlined (similar to Linux red/black tree) for greater efficiency.
+ */
+typedef int (*binheap_order_t)(struct binheap_node *a,
+							   struct binheap_node *b);
+
+
+struct binheap_handle {
+	struct binheap_node *root;
+
+	/* pointer to node to take next inserted child */
+	struct binheap_node *next;
+
+	/* pointer to last node in complete binary tree */
+	struct binheap_node *last;
+
+	/* comparator function pointer */
+	binheap_order_t compare;
+};
+
+
+/**
+ * binheap_entry - get the struct for this heap node.
+ *  Only valid when called upon heap nodes other than the root handle.
+ * @ptr:	the heap node.
+ * @type:	the type of struct pointed to by binheap_node::data.
+ * @member:	unused.
+ */
+#define binheap_entry(ptr, type, member) \
+((type *)((ptr)->data))
+
+/**
+ * binheap_node_container - get the struct that contains this node.
+ *  Only valid when called upon heap nodes other than the root handle.
+ * @ptr:	the heap node.
+ * @type:	the type of struct the node is embedded in.
+ * @member:	the name of the binheap_struct within the (type) struct.
+ */
+#define binheap_node_container(ptr, type, member) \
+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.
+ */
+#define binheap_top_entry(ptr, type, member) \
+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.
+ * @member:	 the name of the binheap_struct within the (type) struct.
+ */
+#define binheap_delete_root(handle, type, member) \
+__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))
+
+/**
+ * binheap_add - insert an element to the heap
+ * new_node:	node to add.
+ * @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_add(new_node, handle, type, member) \
+__binheap_add((new_node), (handle), container_of((new_node), type, member))
+
+
+#define BINHEAP_NODE_INIT() { NULL, NULL, NULL, NULL , NULL, NULL}
+
+#define BINHEAP_NODE(name) \
+	struct binheap_node name = BINHEAP_NODE_INIT()
+
+
+static inline void INIT_BINHEAP_NODE(struct binheap_node *n)
+{
+	n->data = NULL;
+	n->parent = NULL;
+	n->left = NULL;
+	n->right = NULL;
+	n->ref = NULL;
+	n->ref_ptr = NULL;
+}
+
+static inline void INIT_BINHEAP_HANDLE(
+	struct binheap_handle *handle,
+	binheap_order_t compare)
+{
+	handle->root = NULL;
+	handle->next = NULL;
+	handle->last = NULL;
+	handle->compare = compare;
+}
+
+/* Returns true (1) if binheap is empty. */
+static inline int binheap_empty(struct binheap_handle *handle)
+{
+	return(handle->root == NULL);
+}
+
+
+/* Update the node reference pointers.  Same logic as Litmus binomial heap. */
+static inline 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 inline 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 inline 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 inline 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 inline 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 inline 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 == NULL) /* let null 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 inline 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;
+			}
+		}
+	}
+}
+
+
+
+static inline void __binheap_add(struct binheap_node *new_node,
+								 struct binheap_handle *handle,
+								 void *data)
+{
+	/* NULL data pointers are used internally */
+	if(!data) {
+		WARN();
+		return;
+	}
+
+	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.
+ */
+static inline 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;
+	}
+}
+
+
+/**
+ * Delete an arbitrary node.  We first coalesce, then 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. */
+
+	/* 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);
+	__binheap_delete_root(handle, node_to_delete);
+
+	node_to_delete->data = temp_data;  /* restore node data pointer */
+}
+
+#endif
+
-- 
cgit v1.2.2