On Thu, Sep 8, 2016 at 10:40 AM, Tom Lane <t...@sss.pgh.pa.us> wrote:
>> On Thu, Sep 8, 2016 at 12:01 AM, Heikki Linnakangas <hlinn...@iki.fi> wrote:
>>> I still think tuplesort_heap_siftup is a confusing name, although I'm not
>>> sure that Peter's "compact" is much better. I suggest that we rename it to
>>> tuplesort_heap_delete_top(). In comments within the function, explain that
>>> the *loop* corresponds to the "siftup" in Knuth's book.
>
>> I'm also fine with that name.
>
> I can live with it too.
Attached patch does it that way, then. I stuck with the reference to
"shift down", though, since I think we all agree that that is
unambiguous.
--
Peter Geoghegan
From e9af6dbd2bb80b83efa50f748cbe8be0882d1f9c Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <p...@bowt.ie>
Date: Wed, 7 Sep 2016 13:51:38 -0700
Subject: [PATCH] Rename tuplesort_heap_siftup function
tuplesort_heap_siftup is renamed to tuplesort_heap_delete_top. The new
name is chosen to describe the function at a slightly higher level,
since the underlying heap operation is just an implementation detail.
---
src/backend/utils/sort/tuplesort.c | 27 +++++++++++++--------------
1 file changed, 13 insertions(+), 14 deletions(-)
diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index aa8e0e4..92e3db4 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -570,7 +570,7 @@ static void sort_bounded_heap(Tuplesortstate *state);
static void tuplesort_sort_memtuples(Tuplesortstate *state);
static void tuplesort_heap_insert(Tuplesortstate *state, SortTuple *tuple,
int tupleindex, bool checkIndex);
-static void tuplesort_heap_siftup(Tuplesortstate *state, bool checkIndex);
+static void tuplesort_heap_delete_top(Tuplesortstate *state, bool checkIndex);
static void reversedirection(Tuplesortstate *state);
static unsigned int getlen(Tuplesortstate *state, int tapenum, bool eofOK);
static void markrunend(Tuplesortstate *state, int tapenum);
@@ -1617,9 +1617,9 @@ puttuple_common(Tuplesortstate *state, SortTuple *tuple)
}
else
{
- /* discard top of heap, sift up, insert new tuple */
+ /* discard top of heap, and insert new tuple */
free_sort_tuple(state, &state->memtuples[0]);
- tuplesort_heap_siftup(state, false);
+ tuplesort_heap_delete_top(state, false);
tuplesort_heap_insert(state, tuple, 0, false);
}
break;
@@ -1987,7 +1987,7 @@ tuplesort_gettuple_common(Tuplesortstate *state, bool forward,
* more generally.
*/
*stup = state->memtuples[0];
- tuplesort_heap_siftup(state, false);
+ tuplesort_heap_delete_top(state, false);
if ((tupIndex = state->mergenext[srcTape]) == 0)
{
/*
@@ -2643,7 +2643,7 @@ mergeonerun(Tuplesortstate *state)
spaceFreed = state->availMem - priorAvail;
state->mergeavailmem[srcTape] += spaceFreed;
/* compact the heap */
- tuplesort_heap_siftup(state, false);
+ tuplesort_heap_delete_top(state, false);
if ((tupIndex = state->mergenext[srcTape]) == 0)
{
/* out of preloaded data on this tape, try to read more */
@@ -3275,13 +3275,12 @@ dumptuples(Tuplesortstate *state, bool alltuples)
* Still holding out for a case favorable to replacement
* selection. Still incrementally spilling using heap.
*
- * Dump the heap's frontmost entry, and sift up to remove it from
- * the heap.
+ * Dump the heap's top entry, and delete it from the heap.
*/
Assert(state->memtupcount > 0);
WRITETUP(state, state->tp_tapenum[state->destTape],
&state->memtuples[0]);
- tuplesort_heap_siftup(state, true);
+ tuplesort_heap_delete_top(state, true);
}
else
{
@@ -3663,7 +3662,7 @@ make_bounded_heap(Tuplesortstate *state)
if (state->memtupcount > state->bound)
{
free_sort_tuple(state, &state->memtuples[0]);
- tuplesort_heap_siftup(state, false);
+ tuplesort_heap_delete_top(state, false);
}
}
}
@@ -3693,8 +3692,8 @@ sort_bounded_heap(Tuplesortstate *state)
{
SortTuple stup = state->memtuples[0];
- /* this sifts-up the next-largest entry and decreases memtupcount */
- tuplesort_heap_siftup(state, false);
+ /* this puts next-largest entry at top, and decreases memtupcount */
+ tuplesort_heap_delete_top(state, false);
state->memtuples[state->memtupcount] = stup;
}
state->memtupcount = tupcount;
@@ -3784,10 +3783,10 @@ tuplesort_heap_insert(Tuplesortstate *state, SortTuple *tuple,
/*
* The tuple at state->memtuples[0] has been removed from the heap.
- * Decrement memtupcount, and sift up to maintain the heap invariant.
+ * Decrement memtupcount, and shift down to maintain the heap invariant.
*/
static void
-tuplesort_heap_siftup(Tuplesortstate *state, bool checkIndex)
+tuplesort_heap_delete_top(Tuplesortstate *state, bool checkIndex)
{
SortTuple *memtuples = state->memtuples;
SortTuple *tuple;
@@ -3801,7 +3800,7 @@ tuplesort_heap_siftup(Tuplesortstate *state, bool checkIndex)
CHECK_FOR_INTERRUPTS();
n = state->memtupcount;
- tuple = &memtuples[n]; /* tuple that must be reinserted */
+ tuple = &memtuples[n]; /* tuple that must be relocated */
i = 0; /* i is where the "hole" is */
for (;;)
{
--
2.7.4
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
