On Mon, Dec 16, 2013 at 04:57:39AM +0100, Lennart Poettering wrote: > On Mon, 16.12.13 04:48, Lennart Poettering (lenn...@poettering.net) wrote: > > > > > On Mon, 16.12.13 11:03, Chengwei Yang (chengwei.y...@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
signature.asc
Description: Digital signature
_______________________________________________ systemd-devel mailing list systemd-devel@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/systemd-devel
