Confusing point about GISTPQ

[Toan Nguyen]

What exactly is GISTPQ? In gist_private.h, there's this comment before the
struct:

/*
* GiST priority queue for search traversal. Priority is defined by a
* user-specified mindist metric. For now, a naive linked-list
* implementation, should be replaced with a smarter heap
*/
So I guess it's a PRIORITY QUEUE. But in gistget.c, I see these comments
before GIST_PQ_INSERTPG:

/* insert a new priority queue entry into so->pq */
static void
gist_pq_insertpq(GISTScanOpaque so, GISTPQ *newpq)
{
/* CS186 HW2: fill me in! */
}

Now it looks like GISTPQ is an ENTRY of the priority queue.

What's more:

/*
* given the current state of the index scan, generate a GISTPQ to insert
into
* the priority queue, and insert it.
*/
static void
gist_pq_insert(IndexScanDesc scan, /* scan descriptor */
OffsetNumber offset, /* "slot number" of item being inserted
*/
GISTSearchStack *stack, /* search stack to this item */
bool isData /* is the item being inserted a pointer to data?
*/
)
{
/* CS186 HW2: fill me in! Should call gist_pq_insertpq. */
}

This is more confusing. Generate a GISTPQ to insert into the priority queue?
The comment only makes sense if GISTPQ is an ENTRY of a priority queue since
I can't see why we would insert a priority queue into another.

Totally confused. Would appreciate any help.

[Eirinaios Michelakis]

On Thu, 27 Sep 2007 21:53:14 -0700, Toan Nguyen <toan....@berkeley.edu>
wrote:

As the comments are indicating, we don't want you to invest much time in
designing the perfect priority queue. The comments, and the API assume
that you will design a "special purpose" linked list. Further, we assume
that you'll design this list the usual way; there will be a member of the
struct which will be a pointer to itself. Thus, a pointer to an object of
type GISTPQ is both a list (or queue) entry, and a queue, if it points to
the head of the queue.

--

Eirinaios Michelakis

[Toan Nguyen]

Thanks. It makes sense now. I was thinking about the heap for GISTPQ.

"Eirinaios Michelakis" <ccs186b...@gmail.com> wrote in message
news:op.tzcmr2l20sa3qw@w8722dgyx91...

[Robert]

Yes.

> Further, we assume that
> you'll design this list the usual way; there will be a member of the struct
> which will be a pointer to itself.

> Thus, a pointer to an object of type
> GISTPQ is both a list (or queue) entry, and a queue, if it points to the head
> of the queue.
>

Okay, this has confused me a bit. Which one of these two options do you
mean?

A: the pointer each member has just points to the next element in the
priority queue. However, since any given subsection of the PQ could be
seen as a PQ in its own right, the pointer in a weird way could be seen
as pointing to a PQ rather than just an element of a PQ.

[. * ] [ . * ] [ . ]
| /|\ | /|\
+-------+ +--------+

B: literally a two dimensional priority queue--we have a priority queue of
priority queues.

[ * ]
+---------> [ another, separate priority queue ]

[ * ]
+---------> [ another, separate priority queue ]

[ * ]
+---------> [ another, separate priority queue ]

I know it's kind of silly to get so hung up on this, but I think the
explanation made me a bit more confused. I'm pretty sure A is what you
meant, Eirinaios, but can you clarify?

Robert

> --
>
> Eirinaios Michelakis

[Joe H]

Eirinios meant your option (a). I did the GISTPQ implementation in a
style based on the pre-existing GISTSearchStack implementation, so you
can look at that as a model.

But honestly, you can do this however you like as long as you respect
the interfaces to the various functions. GISTPQ is not used anywhere
else in the code ...

J

[Robert]

On Mon, 1 Oct 2007, Joe H wrote:

> Eirinios meant your option (a). I did the GISTPQ implementation in a
> style based on the pre-existing GISTSearchStack implementation, so you
> can look at that as a model.

Alright, thanks.

>
> But honestly, you can do this however you like as long as you respect
> the interfaces to the various functions. GISTPQ is not used anywhere
> else in the code ...
>

Yeah, I think I'll just stick to what you did...

Thanks!

Robert