binheap.h

#ifndef BINARY_HEAP_H
#define BINARY_HEAP_H

#include "defs.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;

	/* facilitates node swapping */
	struct binheap_node **ref_ptr;

	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;
};

typedef struct binheap_node binheap_node_t;

/* Initialized heap nodes not in a heap have parent
 * set to BINHEAP_POISON.
 */
#define BINHEAP_POISON	((void*)(0xdeadbeef))

#define BINHEAP_NODE_INIT() {0, 0, BINHEAP_POISON, 0, 0, 0}

#define BINHEAP_NODE(name) \
struct binheap_node name = BINHEAP_NODE_INIT()

/**
 * Signature of compator function.  Assumed 'less-than' (min-heap).
 * Pass in 'greater-than' for max-heap.
 */
typedef int (*binheap_order_t)(const struct binheap_node *a,
				const struct binheap_node *b);


struct binheap {
	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.
 */
#define binheap_delete(to_delete, handle) \
__binheap_delete((to_delete), (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))

/**
 * 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))


static inline void INIT_BINHEAP_NODE(struct binheap_node *n)
{
	static const struct binheap_node init_node = BINHEAP_NODE_INIT();
	*n = init_node;
}

static inline void INIT_BINHEAP(struct binheap *handle,
				binheap_order_t compare)
{
	handle->root = 0;
	handle->next = 0;
	handle->last = 0;
	handle->compare = compare;
}

/* Returns true if binheap is empty. */
static inline int binheap_empty(struct binheap *handle)
{
	return(handle->root == 0);
}

/* Returns true if binheap node is in a heap. */
static inline int binheap_is_in_heap(const struct binheap_node *node)
{
	return (node->parent != BINHEAP_POISON);
}

/* Returns true if binheap node is in given heap. */
int binheap_is_in_this_heap(const struct binheap_node *node,
				const struct binheap* heap);

typedef void (*binheap_for_each_t)(struct binheap_node *node, void* args);
/* Visit every node in heap with function fn(args). Visit order undefined. */
void binheap_for_each(struct binheap *heap, binheap_for_each_t fn, void* args);

/* Add a node to a heap */
void __binheap_add(struct binheap_node *new_node,
				struct binheap *handle,
				void *data);

/**
 * 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);

/**
 * 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);

/**
 * Bubble up a node whose pointer has decreased in value.
 */
void __binheap_decrease(struct binheap_node *orig_node,
				struct binheap *handle);
#endif