Re: [PATCH] binary heap implementation

On 2012-11-20 22:55:52 -0500, Tom Lane wrote:
> Abhijit Menon-Sen <ams(at)2ndQuadrant(dot)com> writes:
> >> While I'm thinking about it, why are the fields of a binaryheap_node
> >> called "key" and "value"? That implies a semantics not actually used
> >> here. Maybe "value1" and "value2" instead?
>
> > Yes, I discussed this with Andres earlier (and considered ptr and value
> > or p1 and p2), but decided to wait for others to comment on the naming.
> > I have no problem with value1 and value2, though I'd very slightly
> > prefer d1 and d2 (d for Datum) now.
>
> d1/d2 would be fine with me.
>
> BTW, I probably missed some context upthread, but why do we have two
> fields at all? At least for the purposes of nodeMergeAppend, it
> would make a lot more sense for the binaryheap elements to be just
> single Datums, without all the redundant pointers to the MergeAppend
> node. The need to get at the comparison support info could be handled
> much more elegantly than that by providing a "void *" passthrough arg.
> That is, the heap creation function becomes
>
> binaryheap *binaryheap_allocate(size_t capacity,
> binaryheap_comparator compare,
> void *passthrough);
>
> and the comparator signature becomes
>
> typedef int (*binaryheap_comparator) (Datum a, Datum b, void *passthrough);
>
> For nodeMergeAppend, the Datums would be the slot indexes and the
> passthrough pointer could point to the MergeAppend node.
>
> This would make equal sense in a lot of other contexts, such as if you
> wanted a heap composed of tuples -- the info to compare tuples could be
> handled via the passthrough argument, rather than doubling the size of
> the heap in order to put that pointer into each heap element. If you
> have no use for the passthrough arg in a particular usage, just pass
> NULL.

The passthrough argument definitely makes sense, I am all for adding it.

The reasons I originally wanted to have two values was that it made it
easy/possible for the comparison function to work without any pointer
dereferences which was somewhat beneficial to performance. Completely
without dereferences only worked on 64bit systems anyway though...
With just one value I need an extra struct, but thats not too bad.

So if you all prefer just having one value, I am ok with that. Who is
updating the patch?

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services