This is basically untested.
---
src/backend/lib/Makefile | 2 +-
src/backend/lib/simpleheap.c | 255 +++++++++++++++++++++++++++++++++++++++++++
src/include/lib/simpleheap.h | 91 +++++++++++++++
3 files changed, 347 insertions(+), 1 deletion(-)
create mode 100644 src/backend/lib/simpleheap.c
create mode 100644 src/include/lib/simpleheap.h
diff --git a/src/backend/lib/Makefile b/src/backend/lib/Makefile
index 2e1061e..1e1bd5c 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 = dllist.o stringinfo.o
+OBJS = dllist.o simpleheap.o stringinfo.o
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/lib/simpleheap.c b/src/backend/lib/simpleheap.c
new file mode 100644
index 0000000..825d0a8
--- /dev/null
+++ b/src/backend/lib/simpleheap.c
@@ -0,0 +1,255 @@
+/*-------------------------------------------------------------------------
+ *
+ * simpleheap.c
+ * A simple binary heap implementaion
+ *
+ * Portions Copyright (c) 2012, PostgreSQL Global Development Group
+ *
+ *
+ * IDENTIFICATION
+ * src/backend/lib/simpleheap.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#include <math.h>
+
+#include "lib/simpleheap.h"
+
+static inline int
+simpleheap_left_off(size_t i)
+{
+ return 2 * i + 1;
+}
+
+static inline int
+simpleheap_right_off(size_t i)
+{
+ return 2 * i + 2;
+}
+
+static inline int
+simpleheap_parent_off(size_t i)
+{
+ return floor((i - 1) / 2);
+}
+
+/* sift up */
+static void
+simpleheap_sift_up(simpleheap *heap, size_t node_off);
+
+/* sift down */
+static void
+simpleheap_sift_down(simpleheap *heap, size_t node_off);
+
+static inline void
+simpleheap_swap(simpleheap *heap, size_t a, size_t b)
+{
+ simpleheap_kv swap;
+ swap.value = heap->values[a].value;
+ swap.key = heap->values[a].key;
+
+ heap->values[a].value = heap->values[b].value;
+ heap->values[a].key = heap->values[b].key;
+
+ heap->values[b].key = swap.key;
+ heap->values[b].value = swap.value;
+}
+
+/* sift down */
+static void
+simpleheap_sift_down(simpleheap *heap, size_t node_off)
+{
+ /* manually unrolled tail recursion */
+ while (true)
+ {
+ size_t left_off = simpleheap_left_off(node_off);
+ size_t right_off = simpleheap_right_off(node_off);
+ size_t swap_off = 0;
+
+ /* only one child can violate the heap property after a change */
+
+ /* check left child */
+ if (left_off < heap->size &&
+ heap->compare(&heap->values[left_off],
+ &heap->values[node_off]) < 0)
+ {
+ /* heap condition violated */
+ swap_off = left_off;
+ }
+
+ /* check right child */
+ if (right_off < heap->size &&
+ heap->compare(&heap->values[right_off],
+ &heap->values[node_off]) < 0)
+ {
+ /* heap condition violated */
+
+ /* swap with the smaller child */
+ if (!swap_off ||
+ heap->compare(&heap->values[right_off],
+ &heap->values[left_off]) < 0)
+ {
+ swap_off = right_off;
+ }
+ }
+
+ if (!swap_off)
+ {
+ /* heap condition fullfilled, abort */
+ break;
+ }
+
+ /* swap node with the child violating the property */
+ simpleheap_swap(heap, swap_off, node_off);
+
+ /* recurse, check child subtree */
+ node_off = swap_off;
+ }
+}
+
+/* sift up */
+static void
+simpleheap_sift_up(simpleheap *heap, size_t node_off)
+{
+ /* manually unrolled tail recursion */
+ while (true)
+ {
+ size_t parent_off = simpleheap_parent_off(node_off);
+
+ if (heap->compare(&heap->values[parent_off],
+ &heap->values[node_off]) < 0)
+ {
+ /* heap property violated */
+ simpleheap_swap(heap, node_off, parent_off);
+
+ /* recurse */
+ node_off = parent_off;
+ }
+ else
+ break;
+ }
+}
+
+simpleheap*
+simpleheap_allocate(size_t allocate)
+{
+ simpleheap* heap = palloc(sizeof(simpleheap));
+ heap->values = palloc(sizeof(simpleheap_kv) * allocate);
+ heap->size = 0;
+ heap->space = allocate;
+ return heap;
+}
+
+void
+simpleheap_free(simpleheap* heap)
+{
+ pfree(heap->values);
+ pfree(heap);
+}
+
+/* initial building of a heap */
+void
+simpleheap_build(simpleheap *heap)
+{
+ int i;
+
+ for (i = simpleheap_parent_off(heap->size - 1); i >= 0; i--)
+ {
+ simpleheap_sift_down(heap, i);
+ }
+}
+
+/*
+ * Change the
+ */
+void
+simpleheap_change_key(simpleheap *heap, void* key)
+{
+ size_t next_off = 0;
+ int ret;
+ simpleheap_kv* kv;
+
+ heap->values[0].key = key;
+
+ /* no need to do anything if there is only one element */
+ if (heap->size == 1)
+ {
+ return;
+ }
+ else if (heap->size == 2)
+ {
+ next_off = 1;
+ }
+ else
+ {
+ ret = heap->compare(
+ &heap->values[simpleheap_left_off(0)],
+ &heap->values[simpleheap_right_off(0)]);
+
+ if (ret == -1)
+ next_off = simpleheap_left_off(0);
+ else
+ next_off = simpleheap_right_off(0);
+ }
+
+ /*
+ * compare with the next key. If were still smaller we can skip
+ * restructuring heap
+ */
+ ret = heap->compare(
+ &heap->values[0],
+ &heap->values[next_off]);
+
+ if (ret == -1)
+ return;
+
+ kv = simpleheap_remove_first(heap);
+ simpleheap_add(heap, kv->key, kv->value);
+}
+
+void
+simpleheap_add_unordered(simpleheap* heap, void *key, void *value)
+{
+ if (heap->size + 1 == heap->space)
+ Assert("Cannot resize heaps");
+ heap->values[heap->size].key = key;
+ heap->values[heap->size++].value = value;
+}
+
+void
+simpleheap_add(simpleheap* heap, void *key, void *value)
+{
+ simpleheap_add_unordered(heap, key, value);
+ simpleheap_sift_up(heap, heap->size - 1);
+}
+
+simpleheap_kv*
+simpleheap_first(simpleheap* heap)
+{
+ if (!heap->size)
+ Assert("heap is empty");
+ return &heap->values[0];
+}
+
+
+simpleheap_kv*
+simpleheap_remove_first(simpleheap* heap)
+{
+ if (heap->size == 0)
+ Assert("heap is empty");
+
+ if (heap->size == 1)
+ {
+ heap->size--;
+ return &heap->values[0];
+ }
+
+ simpleheap_swap(heap, 0, heap->size - 1);
+ simpleheap_sift_down(heap, 0);
+
+ heap->size--;
+ return &heap->values[heap->size];
+}
diff --git a/src/include/lib/simpleheap.h b/src/include/lib/simpleheap.h
new file mode 100644
index 0000000..ab2d2ea
--- /dev/null
+++ b/src/include/lib/simpleheap.h
@@ -0,0 +1,91 @@
+/*
+ * simpleheap.h
+ *
+ * A simple binary heap implementation
+ *
+ * Portions Copyright (c) 2012, PostgreSQL Global Development Group
+ *
+ * src/include/lib/simpleheap.h
+ */
+
+#ifndef SIMPLEHEAP_H
+#define SIMPLEHEAP_H
+
+typedef struct simpleheap_kv
+{
+ void* key;
+ void* value;
+} simpleheap_kv;
+
+typedef struct simpleheap
+{
+ size_t size;
+ size_t space;
+ /*
+ * Has to return:
+ * -1 iff a < b
+ * 0 iff a == b
+ * +1 iff a > b
+ */
+ int (*compare)(simpleheap_kv* a, simpleheap_kv* b);
+
+ simpleheap_kv *values;
+} simpleheap;
+
+simpleheap*
+simpleheap_allocate(size_t capacity);
+
+void
+simpleheap_free(simpleheap* heap);
+
+/*
+ * Add values without enforcing the heap property.
+ *
+ * simpleheap_build has to be called before relying on anything that needs a
+ * valid heap. This is mostly useful for initially filling a heap and staying
+ * in O(n) instead of O(n log n).
+ */
+void
+simpleheap_add_unordered(simpleheap* heap, void *key, void *value);
+
+/*
+ * Insert key/value pair
+ *
+ * O(log n)
+ */
+void
+simpleheap_add(simpleheap* heap, void *key, void *value);
+
+/*
+ * Returns the first element as indicated by comparisons of the ->compare()
+ * operator
+ *
+ * O(1)
+ */
+simpleheap_kv*
+simpleheap_first(simpleheap* heap);
+
+/*
+ * Returns and removes the first element as indicated by comparisons of the
+ * ->compare() operator
+ *
+ * O(log n)
+ */
+simpleheap_kv*
+simpleheap_remove_first(simpleheap* heap);
+
+void
+simpleheap_change_key(simpleheap *heap, void* newkey);
+
+
+/*
+ * make the heap fullfill the heap condition. Only needed if elements were
+ * added with simpleheap_add_unordered()
+ *
+ * O(n)
+ */
+void
+simpleheap_build(simpleheap *heap);
+
+
+#endif //SIMPLEHEAP_H
--
Sent via pgsql-hackers mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
