1 files changed, 188 insertions, 10 deletions

diff --git a/src/common/binaryheap.c b/src/common/binaryheap.c
index 2ffd656e87b..c20ed50acc6 100644
--- a/src/common/binaryheap.c
+++ b/src/common/binaryheap.c
@@ -22,8 +22,30 @@
 #ifdef FRONTEND
 #include "common/logging.h"
 #endif
+#include "common/hashfn.h"
 #include "lib/binaryheap.h"
 
+/*
+ * Define parameters for hash table code generation. The interface is *also*
+ * declared in binaryheap.h (to generate the types, which are externally
+ * visible).
+ */
+#define SH_PREFIX bh_nodeidx
+#define SH_ELEMENT_TYPE bh_nodeidx_entry
+#define SH_KEY_TYPE bh_node_type
+#define SH_KEY key
+#define SH_HASH_KEY(tb, key) \
+	hash_bytes((const unsigned char *) &key, sizeof(bh_node_type))
+#define SH_EQUAL(tb, a, b) (memcmp(&a, &b, sizeof(bh_node_type)) == 0)
+#define SH_SCOPE extern
+#ifdef FRONTEND
+#define SH_RAW_ALLOCATOR pg_malloc0
+#endif
+#define SH_STORE_HASH
+#define SH_GET_HASH(tb, a) a->hash
+#define SH_DEFINE
+#include "lib/simplehash.h"
+
 static void sift_down(binaryheap *heap, int node_off);
 static void sift_up(binaryheap *heap, int node_off);
 
@@ -34,9 +56,14 @@ static void sift_up(binaryheap *heap, int node_off);
  * of nodes, and with the heap property defined by the given comparator
  * function, which will be invoked with the additional argument specified by
  * 'arg'.
+ *
+ * If 'indexed' is true, we create a hash table to track each node's
+ * index in the heap, enabling to perform some operations such as
+ * binaryheap_remove_node_ptr() etc.
  */
 binaryheap *
-binaryheap_allocate(int num_nodes, binaryheap_comparator compare, void *arg)
+binaryheap_allocate(int num_nodes, binaryheap_comparator compare,
+					bool indexed, void *arg)
 {
 	binaryheap *heap;
 
@@ -48,6 +75,17 @@ binaryheap_allocate(int num_nodes, binaryheap_comparator compare, void *arg)
 	heap->bh_size = 0;
 	heap->bh_has_heap_property = true;
 	heap->bh_nodes = (bh_node_type *) palloc(sizeof(bh_node_type) * num_nodes);
+	heap->bh_nodeidx = NULL;
+
+	if (indexed)
+	{
+#ifdef FRONTEND
+		heap->bh_nodeidx = bh_nodeidx_create(num_nodes, NULL);
+#else
+		heap->bh_nodeidx = bh_nodeidx_create(CurrentMemoryContext, num_nodes,
+											 NULL);
+#endif
+	}
 
 	return heap;
 }
@@ -63,6 +101,9 @@ binaryheap_reset(binaryheap *heap)
 {
 	heap->bh_size = 0;
 	heap->bh_has_heap_property = true;
+
+	if (binaryheap_indexed(heap))
+		bh_nodeidx_reset(heap->bh_nodeidx);
 }
 
 /*
@@ -73,6 +114,9 @@ binaryheap_reset(binaryheap *heap)
 void
 binaryheap_free(binaryheap *heap)
 {
+	if (binaryheap_indexed(heap))
+		bh_nodeidx_destroy(heap->bh_nodeidx);
+
 	pfree(heap->bh_nodes);
 	pfree(heap);
 }
@@ -116,6 +160,67 @@ enlarge_node_array(binaryheap *heap)
 }
 
 /*
+ * Set the given node at the 'index' and track it if required.
+ *
+ * Return true if the node's index is already tracked.
+ */
+static bool
+set_node(binaryheap *heap, bh_node_type node, int index)
+{
+	bool		found = false;
+
+	/* Set the node to the nodes array */
+	heap->bh_nodes[index] = node;
+
+	if (binaryheap_indexed(heap))
+	{
+		bh_nodeidx_entry *ent;
+
+		/* Keep track of the node index */
+		ent = bh_nodeidx_insert(heap->bh_nodeidx, node, &found);
+		ent->index = index;
+	}
+
+	return found;
+}
+
+/*
+ * Remove the node's index from the hash table if the heap is indexed.
+ */
+static inline void
+delete_nodeidx(binaryheap *heap, bh_node_type node)
+{
+	if (binaryheap_indexed(heap))
+		bh_nodeidx_delete(heap->bh_nodeidx, node);
+}
+
+/*
+ * Replace the existing node at 'idx' with the given 'new_node'. Also
+ * update their positions accordingly. Note that we assume the new_node's
+ * position is already tracked if enabled, i.e. the new_node is already
+ * present in the heap.
+ */
+static void
+replace_node(binaryheap *heap, int index, bh_node_type new_node)
+{
+	bool		found PG_USED_FOR_ASSERTS_ONLY;
+
+	/* Quick return if not necessary to move */
+	if (heap->bh_nodes[index] == new_node)
+		return;
+
+	/* Remove the overwritten node's index */
+	delete_nodeidx(heap, heap->bh_nodes[index]);
+
+	/*
+	 * Replace it with the given new node. This node's position must also be
+	 * tracked as we assume to replace the node with the existing node.
+	 */
+	found = set_node(heap, new_node, index);
+	Assert(!binaryheap_indexed(heap) || found);
+}
+
+/*
  * binaryheap_add_unordered
  *
  * Adds the given datum to the end of the heap's list of nodes in O(1) without
@@ -131,7 +236,7 @@ binaryheap_add_unordered(binaryheap *heap, bh_node_type d)
 		enlarge_node_array(heap);
 
 	heap->bh_has_heap_property = false;
-	heap->bh_nodes[heap->bh_size] = d;
+	set_node(heap, d, heap->bh_size);
 	heap->bh_size++;
 }
 
@@ -164,7 +269,7 @@ binaryheap_add(binaryheap *heap, bh_node_type d)
 	if (heap->bh_size >= heap->bh_space)
 		enlarge_node_array(heap);
 
-	heap->bh_nodes[heap->bh_size] = d;
+	set_node(heap, d, heap->bh_size);
 	heap->bh_size++;
 	sift_up(heap, heap->bh_size - 1);
 }
@@ -205,6 +310,8 @@ binaryheap_remove_first(binaryheap *heap)
 	if (heap->bh_size == 1)
 	{
 		heap->bh_size--;
+		delete_nodeidx(heap, result);
+
 		return result;
 	}
 
@@ -212,7 +319,7 @@ binaryheap_remove_first(binaryheap *heap)
 	 * Remove the last node, placing it in the vacated root entry, and sift
 	 * the new root node down to its correct position.
 	 */
-	heap->bh_nodes[0] = heap->bh_nodes[--heap->bh_size];
+	replace_node(heap, 0, heap->bh_nodes[--heap->bh_size]);
 	sift_down(heap, 0);
 
 	return result;
@@ -238,7 +345,7 @@ binaryheap_remove_node(binaryheap *heap, int n)
 						   heap->bh_arg);
 
 	/* remove the last node, placing it in the vacated entry */
-	heap->bh_nodes[n] = heap->bh_nodes[heap->bh_size];
+	replace_node(heap, n, heap->bh_nodes[heap->bh_size]);
 
 	/* sift as needed to preserve the heap property */
 	if (cmp > 0)
@@ -248,6 +355,77 @@ binaryheap_remove_node(binaryheap *heap, int n)
 }
 
 /*
+ * binaryheap_remove_node_ptr
+ *
+ * Similar to binaryheap_remove_node() but removes the given node. The caller
+ * must ensure that the given node is in the heap. O(log n) worst case.
+ *
+ * This function can be used only if the heap is indexed.
+ */
+void
+binaryheap_remove_node_ptr(binaryheap *heap, bh_node_type d)
+{
+	bh_nodeidx_entry *ent;
+
+	Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
+	Assert(binaryheap_indexed(heap));
+
+	ent = bh_nodeidx_lookup(heap->bh_nodeidx, d);
+	Assert(ent);
+
+	binaryheap_remove_node(heap, ent->index);
+}
+
+/*
+ * Workhorse for binaryheap_update_up and binaryheap_update_down.
+ */
+static void
+resift_node(binaryheap *heap, bh_node_type node, bool sift_dir_up)
+{
+	bh_nodeidx_entry *ent;
+
+	Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
+	Assert(binaryheap_indexed(heap));
+
+	ent = bh_nodeidx_lookup(heap->bh_nodeidx, node);
+	Assert(ent);
+	Assert(ent->index >= 0 && ent->index < heap->bh_size);
+
+	if (sift_dir_up)
+		sift_up(heap, ent->index);
+	else
+		sift_down(heap, ent->index);
+}
+
+/*
+ * binaryheap_update_up
+ *
+ * Sift the given node up after the node's key is updated. The caller must
+ * ensure that the given node is in the heap. O(log n) worst case.
+ *
+ * This function can be used only if the heap is indexed.
+ */
+void
+binaryheap_update_up(binaryheap *heap, bh_node_type d)
+{
+	resift_node(heap, d, true);
+}
+
+/*
+ * binaryheap_update_down
+ *
+ * Sift the given node down after the node's key is updated. The caller must
+ * ensure that the given node is in the heap. O(log n) worst case.
+ *
+ * This function can be used only if the heap is indexed.
+ */
+void
+binaryheap_update_down(binaryheap *heap, bh_node_type d)
+{
+	resift_node(heap, d, false);
+}
+
+/*
  * binaryheap_replace_first
  *
  * Replace the topmost element of a non-empty heap, preserving the heap
@@ -259,7 +437,7 @@ binaryheap_replace_first(binaryheap *heap, bh_node_type d)
 {
 	Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
 
-	heap->bh_nodes[0] = d;
+	replace_node(heap, 0, d);
 
 	if (heap->bh_size > 1)
 		sift_down(heap, 0);
@@ -301,11 +479,11 @@ sift_up(binaryheap *heap, int node_off)
 		 * Otherwise, swap the parent value with the hole, and go on to check
 		 * the node's new parent.
 		 */
-		heap->bh_nodes[node_off] = parent_val;
+		set_node(heap, parent_val, node_off);
 		node_off = parent_off;
 	}
 	/* Re-fill the hole */
-	heap->bh_nodes[node_off] = node_val;
+	set_node(heap, node_val, node_off);
 }
 
 /*
@@ -360,9 +538,9 @@ sift_down(binaryheap *heap, int node_off)
 		 * Otherwise, swap the hole with the child that violates the heap
 		 * property; then go on to check its children.
 		 */
-		heap->bh_nodes[node_off] = heap->bh_nodes[swap_off];
+		set_node(heap, heap->bh_nodes[swap_off], node_off);
 		node_off = swap_off;
 	}
 	/* Re-fill the hole */
-	heap->bh_nodes[node_off] = node_val;
+	set_node(heap, node_val, node_off);
 }