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

[Yang Chengwei]

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.

--
Thanks,
Chengwei

> > be a bug fix or an optimization?
> > 
> > > ---
> > >  src/shared/prioq.c |   10 ----------
> > >  1 file changed, 10 deletions(-)
> > > 
> > > diff --git a/src/shared/prioq.c b/src/shared/prioq.c
> > > index 8af4c51..ef99c47 100644
> > > --- a/src/shared/prioq.c
> > > +++ b/src/shared/prioq.c
> > > @@ -68,7 +68,6 @@ int prioq_ensure_allocated(Prioq **q, compare_func_t compare_func) {
> > >  
> > >  static void swap(Prioq *q, unsigned j, unsigned k) {
> > >          void *saved_data;
> > > -        unsigned *saved_idx;
> > >  
> > >          assert(q);
> > >          assert(j < q->n_items);
> > > @@ -78,17 +77,8 @@ static void swap(Prioq *q, unsigned j, unsigned k) {
> > >          assert(!q->items[k].idx || *(q->items[k].idx) == k);
> > >  
> > >          saved_data = q->items[j].data;
> > > -        saved_idx = q->items[j].idx;
> > >          q->items[j].data = q->items[k].data;
> > > -        q->items[j].idx = q->items[k].idx;
> > >          q->items[k].data = saved_data;
> > > -        q->items[k].idx = saved_idx;
> > > -
> > > -        if (q->items[j].idx)
> > > -                *q->items[j].idx = j;
> > > -
> > > -        if (q->items[k].idx)
> > > -                *q->items[k].idx = k;
> > >  }
> > >  
> > >  static unsigned shuffle_up(Prioq *q, unsigned idx) {
> > 
> > 
> > Lennart
> > 
> 
> 
> Lennart
> 
> -- 
> Lennart Poettering, Red Hat
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 490 bytes
Desc: Digital signature
URL: <http://lists.freedesktop.org/archives/systemd-devel/attachments/20131216/7865984c/attachment.pgp>