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.

1 files changed, 543 insertions, 0 deletions

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
+