public inbox for [email protected]
help / color / mirror / Atom feedFrom: Nathan Bossart <[email protected]>
Subject: [PATCH v10 4/4] Remove open-coded binary heap in pg_dump_sort.c.
Date: Tue, 25 Jul 2023 11:18:52 -0700
Thanks to commit XXXXXXXXXX, binaryheap is available to frontend
code. This commit replaces the open-coded heap implementation in
pg_dump_sort.c with a binaryheap, saving a few lines of code.
Reviewed-by: Tom Lane
Discussion: https://postgr.es/m/3612876.1689443232%40sss.pgh.pa.us
---
src/bin/pg_dump/pg_dump_sort.c | 105 +++++++--------------------------
1 file changed, 22 insertions(+), 83 deletions(-)
diff --git a/src/bin/pg_dump/pg_dump_sort.c b/src/bin/pg_dump/pg_dump_sort.c
index 523a19c155..8436c1d757 100644
--- a/src/bin/pg_dump/pg_dump_sort.c
+++ b/src/bin/pg_dump/pg_dump_sort.c
@@ -16,6 +16,7 @@
#include "postgres_fe.h"
#include "catalog/pg_class_d.h"
+#include "lib/binaryheap.h"
#include "pg_backup_archiver.h"
#include "pg_backup_utils.h"
#include "pg_dump.h"
@@ -161,8 +162,6 @@ static bool TopoSort(DumpableObject **objs,
int numObjs,
DumpableObject **ordering,
int *nOrdering);
-static void addHeapElement(int val, int *heap, int heapLength);
-static int removeHeapElement(int *heap, int heapLength);
static void findDependencyLoops(DumpableObject **objs, int nObjs, int totObjs);
static int findLoop(DumpableObject *obj,
DumpId startPoint,
@@ -174,6 +173,7 @@ static void repairDependencyLoop(DumpableObject **loop,
int nLoop);
static void describeDumpableObject(DumpableObject *obj,
char *buf, int bufsize);
+static int int_cmp(void *a, void *b, void *arg);
/*
@@ -374,11 +374,10 @@ TopoSort(DumpableObject **objs,
int *nOrdering) /* output argument */
{
DumpId maxDumpId = getMaxDumpId();
- int *pendingHeap;
+ binaryheap *pendingHeap;
int *beforeConstraints;
int *idMap;
DumpableObject *obj;
- int heapLength;
int i,
j,
k;
@@ -403,7 +402,7 @@ TopoSort(DumpableObject **objs,
return true;
/* Create workspace for the above-described heap */
- pendingHeap = (int *) pg_malloc(numObjs * sizeof(int));
+ pendingHeap = binaryheap_allocate(numObjs, int_cmp, NULL);
/*
* Scan the constraints, and for each item in the input, generate a count
@@ -434,19 +433,16 @@ TopoSort(DumpableObject **objs,
* Now initialize the heap of items-ready-to-output by filling it with the
* indexes of items that already have beforeConstraints[id] == 0.
*
- * The essential property of a heap is heap[(j-1)/2] >= heap[j] for each j
- * in the range 1..heapLength-1 (note we are using 0-based subscripts
- * here, while the discussion in Knuth assumes 1-based subscripts). So, if
- * we simply enter the indexes into pendingHeap[] in decreasing order, we
- * a-fortiori have the heap invariant satisfied at completion of this
- * loop, and don't need to do any sift-up comparisons.
+ * We enter the objects into pendingHeap in decreasing order so that the
+ * heap invariant is satisfied at the completion of this loop. This
+ * reduces the amount of work that binaryheap_build() must do.
*/
- heapLength = 0;
for (i = numObjs; --i >= 0;)
{
if (beforeConstraints[objs[i]->dumpId] == 0)
- pendingHeap[heapLength++] = i;
+ binaryheap_add_unordered(pendingHeap, (void *) (intptr_t) i);
}
+ binaryheap_build(pendingHeap);
/*--------------------
* Now emit objects, working backwards in the output list. At each step,
@@ -464,10 +460,10 @@ TopoSort(DumpableObject **objs,
*--------------------
*/
i = numObjs;
- while (heapLength > 0)
+ while (!binaryheap_empty(pendingHeap))
{
/* Select object to output by removing largest heap member */
- j = removeHeapElement(pendingHeap, heapLength--);
+ j = (int) (intptr_t) binaryheap_remove_first(pendingHeap);
obj = objs[j];
/* Output candidate to ordering[] */
ordering[--i] = obj;
@@ -477,7 +473,7 @@ TopoSort(DumpableObject **objs,
int id = obj->dependencies[k];
if ((--beforeConstraints[id]) == 0)
- addHeapElement(idMap[id], pendingHeap, heapLength++);
+ binaryheap_add(pendingHeap, (void *) (intptr_t) idMap[id]);
}
}
@@ -497,79 +493,13 @@ TopoSort(DumpableObject **objs,
}
/* Done */
- free(pendingHeap);
+ binaryheap_free(pendingHeap);
free(beforeConstraints);
free(idMap);
return (i == 0);
}
-/*
- * Add an item to a heap (priority queue)
- *
- * heapLength is the current heap size; caller is responsible for increasing
- * its value after the call. There must be sufficient storage at *heap.
- */
-static void
-addHeapElement(int val, int *heap, int heapLength)
-{
- int j;
-
- /*
- * Sift-up the new entry, per Knuth 5.2.3 exercise 16. Note that Knuth is
- * using 1-based array indexes, not 0-based.
- */
- j = heapLength;
- while (j > 0)
- {
- int i = (j - 1) >> 1;
-
- if (val <= heap[i])
- break;
- heap[j] = heap[i];
- j = i;
- }
- heap[j] = val;
-}
-
-/*
- * Remove the largest item present in a heap (priority queue)
- *
- * heapLength is the current heap size; caller is responsible for decreasing
- * its value after the call.
- *
- * We remove and return heap[0], which is always the largest element of
- * the heap, and then "sift up" to maintain the heap invariant.
- */
-static int
-removeHeapElement(int *heap, int heapLength)
-{
- int result = heap[0];
- int val;
- int i;
-
- if (--heapLength <= 0)
- return result;
- val = heap[heapLength]; /* value that must be reinserted */
- i = 0; /* i is where the "hole" is */
- for (;;)
- {
- int j = 2 * i + 1;
-
- if (j >= heapLength)
- break;
- if (j + 1 < heapLength &&
- heap[j] < heap[j + 1])
- j++;
- if (val >= heap[j])
- break;
- heap[i] = heap[j];
- i = j;
- }
- heap[i] = val;
- return result;
-}
-
/*
* findDependencyLoops - identify loops in TopoSort's failure output,
* and pass each such loop to repairDependencyLoop() for action
@@ -1559,3 +1489,12 @@ describeDumpableObject(DumpableObject *obj, char *buf, int bufsize)
(int) obj->objType,
obj->dumpId, obj->catId.oid);
}
+
+/*
+ * Compares "a" and "b" as integers.
+ */
+static int
+int_cmp(void *a, void *b, void *arg)
+{
+ return (int) (intptr_t) a - (int) (intptr_t) b;
+}
--
2.25.1
--y0ulUmNC+osPPQO6--
view thread (1047+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected]
Subject: Re: [PATCH v10 4/4] Remove open-coded binary heap in pg_dump_sort.c.
In-Reply-To: <no-message-id-1856548@localhost>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox