path: root/include/litmus/binheap.h

#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 macro-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_ON(!data);
		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