Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit559bc17

Browse files
Remove open-coded binary heap in pg_dump_sort.c.
Thanks to commit5af0263, binaryheap is available to frontendcode. This commit replaces the open-coded heap implementation inpg_dump_sort.c with a binaryheap, saving a few lines of code.Reviewed-by: Tom LaneDiscussion:https://postgr.es/m/3612876.1689443232%40sss.pgh.pa.us
1 parentc868cbf commit559bc17

File tree

1 file changed

+27
-83
lines changed

1 file changed

+27
-83
lines changed

‎src/bin/pg_dump/pg_dump_sort.c

Lines changed: 27 additions & 83 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@
1616
#include"postgres_fe.h"
1717

1818
#include"catalog/pg_class_d.h"
19+
#include"lib/binaryheap.h"
1920
#include"pg_backup_archiver.h"
2021
#include"pg_backup_utils.h"
2122
#include"pg_dump.h"
@@ -161,8 +162,6 @@ static bool TopoSort(DumpableObject **objs,
161162
intnumObjs,
162163
DumpableObject**ordering,
163164
int*nOrdering);
164-
staticvoidaddHeapElement(intval,int*heap,intheapLength);
165-
staticintremoveHeapElement(int*heap,intheapLength);
166165
staticvoidfindDependencyLoops(DumpableObject**objs,intnObjs,inttotObjs);
167166
staticintfindLoop(DumpableObject*obj,
168167
DumpIdstartPoint,
@@ -174,6 +173,7 @@ static void repairDependencyLoop(DumpableObject **loop,
174173
intnLoop);
175174
staticvoiddescribeDumpableObject(DumpableObject*obj,
176175
char*buf,intbufsize);
176+
staticintint_cmp(void*a,void*b,void*arg);
177177

178178

179179
/*
@@ -374,11 +374,10 @@ TopoSort(DumpableObject **objs,
374374
int*nOrdering)/* output argument */
375375
{
376376
DumpIdmaxDumpId=getMaxDumpId();
377-
int*pendingHeap;
377+
binaryheap*pendingHeap;
378378
int*beforeConstraints;
379379
int*idMap;
380380
DumpableObject*obj;
381-
intheapLength;
382381
inti,
383382
j,
384383
k;
@@ -403,7 +402,7 @@ TopoSort(DumpableObject **objs,
403402
return true;
404403

405404
/* Create workspace for the above-described heap */
406-
pendingHeap=(int*)pg_malloc(numObjs*sizeof(int));
405+
pendingHeap=binaryheap_allocate(numObjs,int_cmp,NULL);
407406

408407
/*
409408
* Scan the constraints, and for each item in the input, generate a count
@@ -434,19 +433,16 @@ TopoSort(DumpableObject **objs,
434433
* Now initialize the heap of items-ready-to-output by filling it with the
435434
* indexes of items that already have beforeConstraints[id] == 0.
436435
*
437-
* The essential property of a heap is heap[(j-1)/2] >= heap[j] for each j
438-
* in the range 1..heapLength-1 (note we are using 0-based subscripts
439-
* here, while the discussion in Knuth assumes 1-based subscripts). So, if
440-
* we simply enter the indexes into pendingHeap[] in decreasing order, we
441-
* a-fortiori have the heap invariant satisfied at completion of this
442-
* loop, and don't need to do any sift-up comparisons.
436+
* We enter the indexes into pendingHeap in decreasing order so that the
437+
* heap invariant is satisfied at the completion of this loop. This
438+
* reduces the amount of work that binaryheap_build() must do.
443439
*/
444-
heapLength=0;
445440
for (i=numObjs;--i >=0;)
446441
{
447442
if (beforeConstraints[objs[i]->dumpId]==0)
448-
pendingHeap[heapLength++]=i;
443+
binaryheap_add_unordered(pendingHeap, (void*) (intptr_t)i);
449444
}
445+
binaryheap_build(pendingHeap);
450446

451447
/*--------------------
452448
* Now emit objects, working backwards in the output list. At each step,
@@ -464,10 +460,10 @@ TopoSort(DumpableObject **objs,
464460
*--------------------
465461
*/
466462
i=numObjs;
467-
while (heapLength>0)
463+
while (!binaryheap_empty(pendingHeap))
468464
{
469465
/* Select object to output by removing largest heap member */
470-
j=removeHeapElement(pendingHeap,heapLength--);
466+
j=(int) (intptr_t)binaryheap_remove_first(pendingHeap);
471467
obj=objs[j];
472468
/* Output candidate to ordering[] */
473469
ordering[--i]=obj;
@@ -477,7 +473,7 @@ TopoSort(DumpableObject **objs,
477473
intid=obj->dependencies[k];
478474

479475
if ((--beforeConstraints[id])==0)
480-
addHeapElement(idMap[id],pendingHeap,heapLength++);
476+
binaryheap_add(pendingHeap, (void*) (intptr_t)idMap[id]);
481477
}
482478
}
483479

@@ -497,79 +493,13 @@ TopoSort(DumpableObject **objs,
497493
}
498494

499495
/* Done */
500-
free(pendingHeap);
496+
binaryheap_free(pendingHeap);
501497
free(beforeConstraints);
502498
free(idMap);
503499

504500
return (i==0);
505501
}
506502

507-
/*
508-
* Add an item to a heap (priority queue)
509-
*
510-
* heapLength is the current heap size; caller is responsible for increasing
511-
* its value after the call. There must be sufficient storage at *heap.
512-
*/
513-
staticvoid
514-
addHeapElement(intval,int*heap,intheapLength)
515-
{
516-
intj;
517-
518-
/*
519-
* Sift-up the new entry, per Knuth 5.2.3 exercise 16. Note that Knuth is
520-
* using 1-based array indexes, not 0-based.
521-
*/
522-
j=heapLength;
523-
while (j>0)
524-
{
525-
inti= (j-1) >>1;
526-
527-
if (val <=heap[i])
528-
break;
529-
heap[j]=heap[i];
530-
j=i;
531-
}
532-
heap[j]=val;
533-
}
534-
535-
/*
536-
* Remove the largest item present in a heap (priority queue)
537-
*
538-
* heapLength is the current heap size; caller is responsible for decreasing
539-
* its value after the call.
540-
*
541-
* We remove and return heap[0], which is always the largest element of
542-
* the heap, and then "sift up" to maintain the heap invariant.
543-
*/
544-
staticint
545-
removeHeapElement(int*heap,intheapLength)
546-
{
547-
intresult=heap[0];
548-
intval;
549-
inti;
550-
551-
if (--heapLength <=0)
552-
returnresult;
553-
val=heap[heapLength];/* value that must be reinserted */
554-
i=0;/* i is where the "hole" is */
555-
for (;;)
556-
{
557-
intj=2*i+1;
558-
559-
if (j >=heapLength)
560-
break;
561-
if (j+1<heapLength&&
562-
heap[j]<heap[j+1])
563-
j++;
564-
if (val >=heap[j])
565-
break;
566-
heap[i]=heap[j];
567-
i=j;
568-
}
569-
heap[i]=val;
570-
returnresult;
571-
}
572-
573503
/*
574504
* findDependencyLoops - identify loops in TopoSort's failure output,
575505
*and pass each such loop to repairDependencyLoop() for action
@@ -1559,3 +1489,17 @@ describeDumpableObject(DumpableObject *obj, char *buf, int bufsize)
15591489
(int)obj->objType,
15601490
obj->dumpId,obj->catId.oid);
15611491
}
1492+
1493+
/* binaryheap comparator that compares "a" and "b" as integers */
1494+
staticint
1495+
int_cmp(void*a,void*b,void*arg)
1496+
{
1497+
intai= (int) (intptr_t)a;
1498+
intbi= (int) (intptr_t)b;
1499+
1500+
if (ai<bi)
1501+
return-1;
1502+
if (ai>bi)
1503+
return1;
1504+
return0;
1505+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp