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)