binaryheap.diff

diff --git a/src/backend/lib/Makefile b/src/backend/lib/Makefile
index 98ce3d7..327a1bc 100644
--- a/src/backend/lib/Makefile
+++ b/src/backend/lib/Makefile
@@ -12,6 +12,6 @@ subdir = src/backend/lib
 top_builddir = ../../..
 include $(top_builddir)/src/Makefile.global
 
-OBJS = ilist.o stringinfo.o
+OBJS = ilist.o binaryheap.o stringinfo.o
 
 include $(top_srcdir)/src/backend/common.mk

diff --git a/src/include/lib/binaryheap.h b/src/include/lib/binaryheap.h
new file mode 100644
index 0000000..aebf08f
--- /dev/null
+++ b/src/include/lib/binaryheap.h
@@ -0,0 +1,138 @@
+/*
+ * binaryheap.h
+ *
+ * A simple binary heap implementation
+ *
+ * Portions Copyright (c) 2012, PostgreSQL Global Development Group
+ *
+ * src/include/lib/binaryheap.h
+ */
+
+#ifndef BINARYHEAP_H
+#define BINARYHEAP_H
+
+/*
+ * This structure represents a single node in a binaryheap, and just
+ * holds two pointers. The heap management code doesn't care what is
+ * stored in a node (in particular, the key or value may be NULL),
+ * only that the comparator function can compare any two nodes.
+ */
+
+typedef struct binaryheap_node
+{
+	void *key;
+	void *value;
+} binaryheap_node;
+
+/*
+ * For a max-heap, the comparator must return:
+ * -1 iff a < b
+ * 0 iff a == b
+ * +1 iff a > b
+ * For a min-heap, the conditions are reversed.
+ */
+typedef int (*binaryheap_comparator)(binaryheap_node *a, binaryheap_node *b);
+
+/*
+ * binaryheap
+ *
+ *		size			how many nodes are currently in "nodes"
+ *		space			how many nodes can be stored in "nodes"
+ *		comparator		comparator to define the heap property
+ *		nodes			the first of a list of "space" nodes
+ */
+
+typedef struct binaryheap
+{
+	size_t size;
+	size_t space;
+	binaryheap_comparator compare;
+	binaryheap_node nodes[1];
+} binaryheap;
+
+/*
+ * binaryheap_allocate
+ *
+ * Returns a pointer to a newly-allocated heap that has the capacity to
+ * store the given number of nodes, with the heap property defined by
+ * the given comparator function.
+ */
+
+binaryheap *
+binaryheap_allocate(size_t capacity, binaryheap_comparator compare);
+
+/*
+ * binaryheap_free
+ *
+ * Releases memory used by the given binaryheap.
+ */
+
+void
+binaryheap_free(binaryheap *heap);
+
+/*
+ * binaryheap_add_unordered
+ *
+ * Adds the given key and value to the end of the heap's list of nodes
+ * in O(1) without preserving the heap property. This is a convenience
+ * to add elements quickly to a new heap. To obtain a valid heap, one
+ * must call binaryheap_build() afterwards.
+ */
+
+void
+binaryheap_add_unordered(binaryheap *heap, void *key, void *value);
+
+/*
+ * binaryheap_build
+ *
+ * Assembles a valid heap in O(n) from the nodes added by
+ * binaryheap_add_unordered(). Not needed otherwise.
+ */
+
+void
+binaryheap_build(binaryheap *heap);
+
+/*
+ * binaryheap_add
+ *
+ * Adds the given key and value to the heap in O(log n), while
+ * preserving the heap property.
+ */
+
+void
+binaryheap_add(binaryheap *heap, void *key, void *value);
+
+/*
+ * binaryheap_first
+ *
+ * Returns a pointer to the first (root, topmost) node in the heap
+ * without modifying the heap. Returns NULL if the heap is empty.
+ * Always O(1).
+ */
+
+binaryheap_node *
+binaryheap_first(binaryheap *heap);
+
+/*
+ * binaryheap_remove_first
+ *
+ * Removes the first (root, topmost) node in the heap and returns a
+ * pointer to it after rebalancing the heap. Returns NULL if the heap
+ * is empty. O(log n) worst case.
+ */
+
+binaryheap_node *
+binaryheap_remove_first(binaryheap *heap);
+
+/*
+ * binaryheap_replace_first
+ *
+ * Change the key and/or value of the first (root, topmost) node and
+ * ensure that the heap property is preserved. O(1) in the best case,
+ * or O(log n) if it must fall back to sifting the new node down.
+ */
+
+void
+binaryheap_replace_first(binaryheap *heap, void *newkey, void *newval);
+
+#endif /* BINARYHEAP_H */

diff --git a/src/backend/lib/binaryheap.c b/src/backend/lib/binaryheap.c
new file mode 100644
index 0000000..0fa8525
--- /dev/null
+++ b/src/backend/lib/binaryheap.c
@@ -0,0 +1,342 @@
+/*-------------------------------------------------------------------------
+ *
+ * binaryheap.c
+ *	  A simple binary heap implementaion
+ *
+ * Portions Copyright (c) 2012, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *	  src/backend/lib/binaryheap.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#include <math.h>
+
+#include "lib/binaryheap.h"
+
+/* XXX
+ * The following is only to allow testbinheap.c to use this code outside
+ * the backend; should be removed before committing. */
+#ifdef TESTBINHEAP
+#define palloc malloc
+#define pfree free
+#endif
+
+static void sift_down(binaryheap *heap, size_t node_off);
+static void sift_up(binaryheap *heap, size_t node_off);
+static inline void swap_nodes(binaryheap *heap, size_t a, size_t b);
+
+/*
+ * binaryheap_allocate
+ *
+ * Returns a pointer to a newly-allocated heap that has the capacity to
+ * store the given number of nodes, with the heap property defined by
+ * the given comparator function.
+ */
+
+binaryheap *
+binaryheap_allocate(size_t capacity, binaryheap_comparator compare)
+{
+	int sz = sizeof(binaryheap) + sizeof(binaryheap_node) * (capacity-1);
+
+	binaryheap *heap = palloc(sz);
+	heap->compare = compare;
+	heap->space = capacity;
+	heap->size = 0;
+	return heap;
+}
+
+/*
+ * binaryheap_free
+ *
+ * Releases memory used by the given binaryheap.
+ */
+
+void
+binaryheap_free(binaryheap *heap)
+{
+	pfree(heap);
+}
+
+/*
+ * These utility functions return the offset of the left child, right
+ * child, and parent of the node at the given index, respectively.
+ *
+ * The heap is represented as an array of nodes, with the root node
+ * stored at index 0. The left child of node i is at index 2*i+1, and
+ * the right child at 2*i+2. The parent of node i is at index (i-1)/2.
+ */
+
+static inline int
+left_offset(size_t i)
+{
+	return 2 * i + 1;
+}
+
+static inline int
+right_offset(size_t i)
+{
+	return 2 * i + 2;
+}
+
+static inline int
+parent_offset(size_t i)
+{
+	return floor((i - 1) / 2);
+}
+
+/*
+ * binaryheap_add_unordered
+ *
+ * Adds the given key and value to the end of the heap's list of nodes
+ * in O(1) without preserving the heap property. This is a convenience
+ * to add elements quickly to a new heap. To obtain a valid heap, one
+ * must call binaryheap_build() afterwards.
+ */
+
+void
+binaryheap_add_unordered(binaryheap *heap, void *key, void *value)
+{
+	if (heap->size + 1 == heap->space)
+		Assert("binary heap is full");
+	heap->nodes[heap->size].key = key;
+	heap->nodes[heap->size++].value = value;
+}
+
+/*
+ * binaryheap_build
+ *
+ * Assembles a valid heap in O(n) from the nodes added by
+ * binaryheap_add_unordered(). Not needed otherwise.
+ */
+
+void
+binaryheap_build(binaryheap *heap)
+{
+	int i;
+
+	for (i = parent_offset(heap->size - 1); i >= 0; i--)
+	{
+		sift_down(heap, i);
+	}
+}
+
+/*
+ * binaryheap_add
+ *
+ * Adds the given key and value to the heap in O(log n), while
+ * preserving the heap property.
+ */
+
+void
+binaryheap_add(binaryheap *heap, void *key, void *value)
+{
+	binaryheap_add_unordered(heap, key, value);
+	sift_up(heap, heap->size - 1);
+}
+
+/*
+ * binaryheap_first
+ *
+ * Returns a pointer to the first (root, topmost) node in the heap
+ * without modifying the heap. Returns NULL if the heap is empty.
+ * Always O(1).
+ */
+
+binaryheap_node *
+binaryheap_first(binaryheap *heap)
+{
+	if (!heap->size)
+		return NULL;
+	return &heap->nodes[0];
+}
+
+/*
+ * binaryheap_remove_first
+ *
+ * Removes the first (root, topmost) node in the heap and returns a
+ * pointer to it after rebalancing the heap. Returns NULL if the heap
+ * is empty. O(log n) worst case.
+ */
+
+binaryheap_node *
+binaryheap_remove_first(binaryheap *heap)
+{
+	if (heap->size == 0)
+		return NULL;
+
+	if (heap->size == 1)
+	{
+		heap->size--;
+		return &heap->nodes[0];
+	}
+
+	/*
+	 * Swap the root and last nodes, decrease the size of the heap (i.e.
+	 * remove the former root node) and sift the new root node down to
+	 * its correct position.
+	 */
+
+	swap_nodes(heap, 0, heap->size - 1);
+
+	heap->size--;
+	sift_down(heap, 0);
+	return &heap->nodes[heap->size];
+}
+
+/*
+ * binaryheap_replace_first
+ *
+ * Change the key and/or value of the first (root, topmost) node and
+ * ensure that the heap property is preserved. O(1) in the best case,
+ * or O(log n) if it must fall back to sifting the new node down.
+ */
+
+void
+binaryheap_replace_first(binaryheap *heap, void *key, void *val)
+{
+	int ret;
+	size_t next_off = 0;
+
+	if (key)
+		heap->nodes[0].key = key;
+	if (val)
+		heap->nodes[0].value = val;
+
+	/*
+	 * If the new root node is still larger than the largest of its
+	 * children (of which there may be 0, 1, or 2), then the heap is
+	 * still valid.
+	 */
+
+	if (heap->size == 1) {
+		return;
+	}
+	if (heap->size == 2) {
+		next_off = 1;
+	}
+	else {
+		/* Two children: pick the larger one */
+		ret = heap->compare(&heap->nodes[2], &heap->nodes[1]);
+		if (ret == -1)
+			next_off = 1;
+		else
+			next_off = 2;
+	}
+
+	ret = heap->compare(&heap->nodes[next_off], &heap->nodes[0]);
+	if (ret == -1)
+		return;
+
+	/* The child is larger. Swap and sift the new node down. */
+
+	swap_nodes(heap, 0, next_off);
+	sift_down(heap, next_off);
+}
+
+/*
+ * Swap the contents of two nodes.
+ */
+
+static inline void
+swap_nodes(binaryheap *heap, size_t a, size_t b)
+{
+	binaryheap_node swap;
+	swap.value = heap->nodes[a].value;
+	swap.key = heap->nodes[a].key;
+
+	heap->nodes[a].value = heap->nodes[b].value;
+	heap->nodes[a].key = heap->nodes[b].key;
+
+	heap->nodes[b].key = swap.key;
+	heap->nodes[b].value = swap.value;
+}
+
+/*
+ * Sift a node up to the highest position it can hold according to the
+ * comparator.
+ */
+
+static void
+sift_up(binaryheap *heap, size_t node_off)
+{
+	/* manually unrolled tail recursion */
+	while (true)
+	{
+		size_t parent_off = parent_offset(node_off);
+
+		if (node_off == 0)
+			break;
+
+		if (heap->compare(&heap->nodes[parent_off],
+		                  &heap->nodes[node_off]) < 0)
+		{
+			/* heap property violated */
+			swap_nodes(heap, node_off, parent_off);
+
+			/* recurse */
+			node_off = parent_off;
+		}
+		else
+			break;
+	}
+}
+
+/*
+ * Sift a node down from its current position to satisfy the heap
+ * property.
+ */
+
+static void
+sift_down(binaryheap *heap, size_t node_off)
+{
+	/* manually unrolled tail recursion */
+	while (true)
+	{
+		size_t left_off = left_offset(node_off);
+		size_t right_off = right_offset(node_off);
+		size_t swap_off = 0;
+
+		/* Is the left child larger than the parent? */
+
+		if (left_off < heap->size &&
+		    heap->compare(&heap->nodes[node_off],
+		                  &heap->nodes[left_off]) < 0)
+		{
+			swap_off = left_off;
+		}
+
+		/*
+		 * If not (note: only one child can violate the heap property
+		 * after a change), is the right child larger?
+		 */
+
+		if (right_off < heap->size &&
+		    heap->compare(&heap->nodes[node_off],
+		                  &heap->nodes[right_off]) < 0)
+		{
+			/* swap with the larger child */
+			if (!swap_off ||
+			    heap->compare(&heap->nodes[left_off],
+			                  &heap->nodes[right_off]) < 0)
+			{
+				swap_off = right_off;
+			}
+		}
+
+		if (!swap_off)
+		{
+			/* heap condition fullfilled, abort */
+			break;
+		}
+
+		/* swap node with the child violating the property */
+		swap_nodes(heap, swap_off, node_off);
+
+		/* recurse, check child subtree */
+		node_off = swap_off;
+	}
+}