From c0d0492ec8c553807d790923f1be8bcd5d258450 Mon Sep 17 00:00:00 2001 From: Nathan Bossart Date: Tue, 25 Jul 2023 11:18:52 -0700 Subject: [PATCH v8 4/4] Remove open-coded binary heap in pg_dump_sort.c. 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