[augeas-devel] [PATCH] Fix bug#144: wrong behavior of iter concat

[Francis Giraldeau]

Le mardi 26 octobre 2010 à 11:21 -0700, David Lutterkort a écrit : 
> Hi Francis,
> 
> On Fri, 2010-10-22 at 14:09 -0400, francis.giraldeau at usherbrooke.ca
> wrote:
> > diff --git a/src/get.c b/src/get.c
> > index 11ea5de..9d420af 100644
> > --- a/src/get.c
> > +++ b/src/get.c
> > @@ -572,6 +572,7 @@ static struct tree *get_quant_star(struct lens *lens, struct state *state) {
> >  
> >          t = get_lens(lens->child, state);
> >          list_tail_cons(tree, tail, t);
> > +        list_update_tail(tree, tail);
> 
> Why is a new macro needed here ? The list_tail_cons macro should already
> maintain tail as the tail of the list tree. If it doesn't, there's a bug
> in it.

It has a bug only on the first call, when tail is NULL. If tree has more
than one node, the tail is not updated appropriately. 

> The reason I added list_tail_cons is that for long lists, the quadratic
> behavior of walking the entire list becomes too expensive. I fear that
> list_update_tail will cause a similar problem.

The new macro has linear time, because we always use the tail to update
the tail, never from the begening of the list. But, anyway, you're
right, it's better to fix the list_tail_cons macro. 

Here is the patch. 

Francis

-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Fix-bug-144-wrong-behavior-of-iter-concat.patch
Type: text/x-patch
Size: 1837 bytes
Desc: not available
URL: <http://listman.redhat.com/archives/augeas-devel/attachments/20101026/d4c20cd7/attachment.bin>