On Sun, Jul 16, 2023 at 08:54:24PM -0700, Nathan Bossart wrote:
> This seems worth a try. IIUC you are suggesting making binaryheap.c
> frontend-friendly and expanding its API a bit. If no one has volunteered,
> I could probably hack something together.
I spent some time on the binaryheap changes. I haven't had a chance to
plug it into the ready_list yet.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
diff --git a/src/backend/lib/binaryheap.c b/src/backend/lib/binaryheap.c
index 1737546757..36b6f5c51f 100644
--- a/src/backend/lib/binaryheap.c
+++ b/src/backend/lib/binaryheap.c
@@ -11,10 +11,17 @@
*-------------------------------------------------------------------------
*/
+#ifndef FRONTEND
#include "postgres.h"
+#else
+#include "postgres_fe.h"
+#endif
#include <math.h>
+#ifdef FRONTEND
+#include "common/logging.h"
+#endif
#include "lib/binaryheap.h"
static void sift_down(binaryheap *heap, int node_off);
@@ -35,7 +42,11 @@ binaryheap_allocate(int capacity, binaryheap_comparator compare, void *arg)
binaryheap *heap;
sz = offsetof(binaryheap, bh_nodes) + sizeof(Datum) * capacity;
+#ifdef FRONTEND
+ heap = (binaryheap *) pg_malloc(sz);
+#else
heap = (binaryheap *) palloc(sz);
+#endif
heap->bh_space = capacity;
heap->bh_compare = compare;
heap->bh_arg = arg;
@@ -109,7 +120,11 @@ void
binaryheap_add_unordered(binaryheap *heap, Datum d)
{
if (heap->bh_size >= heap->bh_space)
+#ifdef FRONTEND
+ pg_fatal("out of binary heap slots");
+#else
elog(ERROR, "out of binary heap slots");
+#endif
heap->bh_has_heap_property = false;
heap->bh_nodes[heap->bh_size] = d;
heap->bh_size++;
@@ -141,7 +156,11 @@ void
binaryheap_add(binaryheap *heap, Datum d)
{
if (heap->bh_size >= heap->bh_space)
+#ifdef FRONTEND
+ pg_fatal("out of binary heap slots");
+#else
elog(ERROR, "out of binary heap slots");
+#endif
heap->bh_nodes[heap->bh_size] = d;
heap->bh_size++;
sift_up(heap, heap->bh_size - 1);
@@ -196,6 +215,65 @@ binaryheap_remove_first(binaryheap *heap)
return result;
}
+/*
+ * binaryheap_remove
+ *
+ * Removes the given datum from the heap. The caller must ensure that the
+ * datum exists in the heap. Always O(n).
+ */
+void
+binaryheap_remove(binaryheap *heap, Datum d)
+{
+ Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
+
+ for (int i = 0; i < heap->bh_size; i++)
+ {
+ if (heap->bh_compare(heap->bh_nodes[i],
+ d,
+ heap->bh_arg) == 0)
+ {
+ binaryheap_remove_node(heap, &heap->bh_nodes[i]);
+ return;
+ }
+ }
+
+#ifdef FRONTEND
+ pg_fatal("datum not found in heap");
+#else
+ elog(ERROR, "datum not found in heap");
+#endif
+}
+
+/*
+ * binaryheap_remove_node
+ *
+ * Removes the given node from the heap. The caller must ensure that the node
+ * exists in the heap. O(log n) worst case.
+ */
+void
+binaryheap_remove_node(binaryheap *heap, Datum *n)
+{
+ int cmp;
+
+ Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
+ Assert(n >= &heap->bh_nodes[0]);
+ Assert(n <= &heap->bh_nodes[heap->bh_size - 1]);
+
+ /* compare last node to the one that is being removed */
+ cmp = heap->bh_compare(heap->bh_nodes[--heap->bh_size],
+ *n,
+ heap->bh_arg);
+
+ /* remove the last node, placing it in the vacated entry */
+ *n = heap->bh_nodes[heap->bh_size];
+
+ /* sift as needed to preserve the heap property */
+ if (cmp > 0)
+ sift_up(heap, n - &heap->bh_nodes[0]);
+ else if (cmp < 0)
+ sift_down(heap, n - &heap->bh_nodes[0]);
+}
+
/*
* binaryheap_replace_first
*
diff --git a/src/include/lib/binaryheap.h b/src/include/lib/binaryheap.h
index 52f7b06b25..411f7358ba 100644
--- a/src/include/lib/binaryheap.h
+++ b/src/include/lib/binaryheap.h
@@ -47,6 +47,8 @@ extern void binaryheap_build(binaryheap *heap);
extern void binaryheap_add(binaryheap *heap, Datum d);
extern Datum binaryheap_first(binaryheap *heap);
extern Datum binaryheap_remove_first(binaryheap *heap);
+extern void binaryheap_remove(binaryheap *heap, Datum d);
+extern void binaryheap_remove_node(binaryheap *heap, Datum *n);
extern void binaryheap_replace_first(binaryheap *heap, Datum d);
#define binaryheap_empty(h) ((h)->bh_size == 0)
