[systemd-devel] [PATCH] prioq: avoid to swap item index

[Lennart Poettering]

On Mon, 16.12.13 13:15, Yang Chengwei (chengwei.yang at intel.com) wrote:

> On Mon, Dec 16, 2013 at 04:57:39AM +0100, Lennart Poettering wrote:
> > On Mon, 16.12.13 04:48, Lennart Poettering (lennart at poettering.net) wrote:
> > 
> > > 
> > > On Mon, 16.12.13 11:03, Chengwei Yang (chengwei.yang at intel.com) wrote:
> > > 
> > > > the swap() operation of prioq which in fact only swap item's data but
> > > > keep idx untouched. However, current implement does first swap the idx
> > > > and then swap back again.
> > > 
> > > Sorry, I do understand? Can you elaborate, please? Is this supposed to
> >          ^^^^wanted to say: I do *not* understand...
> 
> It's an optimization.
> 
> A condition of the queue is just like the assert says
> 
> assert(!q->items[j].idx || *(q->items[j].idx) == j);
> assert(!q->items[k].idx || *(q->items[k].idx) == k);
> 
> This is true before and after swap. So in fact no need to swap idx and
> then swap back again. Just do not touch idx, then item[j].idx is always
> 0 or j, so as item[k].
> 
> The deleted code does
> 
> 1. first swap the idx regardless it's 0 or not
> 
> 2. then, if idx isn't 0, swap back.
> 
> So this patch is a optimization for the case where item.idx isn't 0,
> which avoid to swap idx and swap idx back.
> 
> I'm not sure this is clear enough. In simple, the fact is *before* and
> *after* we need make sure item[j].idx == j or item[j].idx == 0, so why we
> change it during swap? Because if it changed during swap, we need then
> assign item[j].idx = j before the swap finish. So the simple way is keep
> it untouched.

Sorry, still not getting what you want to say.

Mayb ethere is some confusion regarding what .idx actually is? .idx is
supposed to point to some index integer that is stored in the actual
structure the user added to the priority queue and that can be used to
quickly remove an entry from the priority queue without requiring it to
be the first one. 

In the swap() call we hence first swap the the data and idx pointers
themselves, and then in a second step we finally update what the idx
pointers actually point to to the new index of the item in our priority
queue.

I totally don't see how any of that was redundant. We must make sure
after all that after the swap:

a) For both entries we know that the data pointer has been swapped
b) For both entries we know that the pointer to the index value that is part of the user structure has been swapped
c) For both entries we know that the index value that is part of the user structure has been swapped

Lennart

-- 
Lennart Poettering, Red Hat