Le mardi 26 octobre 2010 à 11:21 -0700, David Lutterkort a écrit : > Hi Francis, > > On Fri, 2010-10-22 at 14:09 -0400, [email protected] > 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
>From b0128a8fe680d3124103c7c42f9022c010990673 Mon Sep 17 00:00:00 2001 From: Francis Giraldeau <[email protected]> Date: Fri, 22 Oct 2010 13:56:03 -0400 Subject: [PATCH] Fix bug#144: wrong behavior of iter concat This patch fix the list_tail_cons macro to fastforward the tail list when the first item is added to the list, otherwise if the first item added when the list is NULL has two item, the tail points the the first item. --- src/list.h | 3 +++ tests/modules/pass_iter_concat.aug | 7 +++++++ 2 files changed, 10 insertions(+), 0 deletions(-) create mode 100644 tests/modules/pass_iter_concat.aug diff --git a/src/list.h b/src/list.h index eb9f84f..881625f 100644 --- a/src/list.h +++ b/src/list.h @@ -115,6 +115,9 @@ if ((list) == NULL) { \ (list) = (elt); \ (tail) = (list); \ + if ((elt) != NULL) \ + for ((tail) = (list); (tail)->next != NULL; \ + (tail) = (tail)->next); \ } else { \ if ((tail) == NULL) \ for ((tail) = (list); (tail)->next != NULL; \ diff --git a/tests/modules/pass_iter_concat.aug b/tests/modules/pass_iter_concat.aug new file mode 100644 index 0000000..00dc4d8 --- /dev/null +++ b/tests/modules/pass_iter_concat.aug @@ -0,0 +1,7 @@ +module Pass_iter_concat = + +let l1 = [ key "a" . del "x" "x" ] +let l2 = [ key "b" . del "y" "y" ] +let l3 = (l1 . l2)* + +test l3 get "axbyaxby" = { "a" }{ "b" }{ "a" }{ "b" } -- 1.7.1
_______________________________________________ augeas-devel mailing list [email protected] https://www.redhat.com/mailman/listinfo/augeas-devel
