m4-commit
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[SCM] GNU M4 source repository branch, branch-1.4, updated. v1.4.12-18-g


From: Eric Blake
Subject: [SCM] GNU M4 source repository branch, branch-1.4, updated. v1.4.12-18-g72506c2
Date: Thu, 12 Feb 2009 22:21:49 +0000

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU M4 source repository".

http://git.sv.gnu.org/gitweb/?p=m4.git;a=commitdiff;h=72506c2eb1d10571bcd2351aa1f3d2427be3c669

The branch, branch-1.4 has been updated
       via  72506c2eb1d10571bcd2351aa1f3d2427be3c669 (commit)
      from  d499df171ddb2161d1e75055009a9b3d18131591 (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
commit 72506c2eb1d10571bcd2351aa1f3d2427be3c669
Author: Eric Blake <address@hidden>
Date:   Thu Feb 12 14:59:08 2009 -0700

    Avoid quadratic code when walking definition stack.
    
    * examples/stack_sep.m4: Use linear, not quadratic
    implementation.
    * doc/m4.texinfo (Improved copy): Fix documentation and add test,
    based on recent autoconf bug fix.
    
    Signed-off-by: Eric Blake <address@hidden>

-----------------------------------------------------------------------

Summary of changes:
 ChangeLog             |    8 ++++++++
 doc/m4.texinfo        |   45 +++++++++++++++++++++++++++++++++++----------
 examples/stack_sep.m4 |    6 +++---
 3 files changed, 46 insertions(+), 13 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index c55e79f..3495018 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,11 @@
+2009-02-12  Eric Blake  <address@hidden>
+
+       Avoid quadratic code when walking definition stack.
+       * examples/stack_sep.m4: Use linear, not quadratic
+       implementation.
+       * doc/m4.texinfo (Improved copy): Fix documentation and add test,
+       based on recent autoconf bug fix.
+
 2009-01-24  Eric Blake  <address@hidden>
 
        Add URLs to --help output.
diff --git a/doc/m4.texinfo b/doc/m4.texinfo
index c09d771..9bbfcfd 100644
--- a/doc/m4.texinfo
+++ b/doc/m4.texinfo
@@ -8199,13 +8199,21 @@ equivalent to @code{stack_foreach_sep(address@hidden', 
address@hidden(',
 construct macro calls with more than one argument, without passing
 builtin tokens through a macro call.  It is likewise possible to
 directly reference the stack definitions without a macro call, by
-leaving @var{pre} and @var{post} empty.  The new macro also adds a
-separator that is only output after the first iteration of the helper
address@hidden, implemented by prepending the original
address@hidden to @var{pre} and omitting a @var{sep} argument in subsequent
-iterations.  As an added bonus, using @code{stack_foreach_sep} to
-implement @code{copy} performs fewer macro invocations.  The improved
-stack walking macros are available in
+leaving @var{pre} and @var{post} empty.  Thus, in addition to fixing
address@hidden on builtin tokens, it also executes with fewer macro
+invocations.
+
+The new macro also adds a separator that is only output after the first
+iteration of the helper @code{_stack_reverse_sep}, implemented by
+prepending the original @var{sep} to @var{pre} and omitting a @var{sep}
+argument in subsequent iterations.  Note that the empty string that
+separates @var{sep} from @var{pre} is provided as part of the fourth
+argument when originally calling @code{_stack_reverse_sep}, and not by
+writing @code{$4`'$3} as the third argument in the recursive call; while
+the other approach would give the same output, it does so at the expense
+of increasing the argument size on each iteration of
address@hidden, which results in quadratic instead of linear
+execution time.  The improved stack walking macros are available in
 @address@hidden/@/examples/@/stack_sep.m4}:
 
 @comment examples
@@ -8238,18 +8246,35 @@ undivert(`stack_sep.m4')dnl
 @result{}# separated by SEP between definitions.
 @result{}define(`stack_foreach_sep',
 @result{}`_stack_reverse_sep(`$1', `tmp-$1')'dnl
address@hidden(`tmp-$1', `$1', `$2`'defn(`$1')$3', `$4')')
address@hidden(`tmp-$1', `$1', `$2`'defn(`$1')$3', `$4`'')')
 @result{}# stack_foreach_sep_lifo(macro, pre, post, sep)
 @result{}# Like stack_foreach_sep, but starting with the newest definition.
 @result{}define(`stack_foreach_sep_lifo',
address@hidden(`$1', `tmp-$1', `$2`'defn(`$1')$3', `$4')'dnl
address@hidden(`$1', `tmp-$1', `$2`'defn(`$1')$3', `$4`'')'dnl
 @result{}`_stack_reverse_sep(`tmp-$1', `$1')')
 @result{}define(`_stack_reverse_sep',
 @result{}`ifdef(`$1', `pushdef(`$2', defn(`$1'))$3`'popdef(`$1')$0(
address@hidden  `$1', `$2', `$4`'$3')')')
address@hidden  `$1', `$2', `$4$3')')')
 @result{}divert`'dnl
 @end example
 
address@hidden
address@hidden Not worth putting in the manual, but make sure that
address@hidden stack_foreach_sep has linear performance.
+
address@hidden examples
address@hidden
+$ @kbd {m4 -I examples}
+include(`forloop3.m4')include(`stack_sep.m4')dnl
+forloop(`i', `1', `10000', `pushdef(`s', i)')
address@hidden
+define(`colon', `:')define(`dash', `-')
address@hidden
+len(stack_foreach_sep(`s', `dash', `', `colon'))
address@hidden
address@hidden example
address@hidden ignore
+
 @node Improved m4wrap
 @section Solution for @code{m4wrap}
 
diff --git a/examples/stack_sep.m4 b/examples/stack_sep.m4
index b11bc83..767d15e 100644
--- a/examples/stack_sep.m4
+++ b/examples/stack_sep.m4
@@ -5,13 +5,13 @@ divert(`-1')
 # separated by SEP between definitions.
 define(`stack_foreach_sep',
 `_stack_reverse_sep(`$1', `tmp-$1')'dnl
-`_stack_reverse_sep(`tmp-$1', `$1', `$2`'defn(`$1')$3', `$4')')
+`_stack_reverse_sep(`tmp-$1', `$1', `$2`'defn(`$1')$3', `$4`'')')
 # stack_foreach_sep_lifo(macro, pre, post, sep)
 # Like stack_foreach_sep, but starting with the newest definition.
 define(`stack_foreach_sep_lifo',
-`_stack_reverse_sep(`$1', `tmp-$1', `$2`'defn(`$1')$3', `$4')'dnl
+`_stack_reverse_sep(`$1', `tmp-$1', `$2`'defn(`$1')$3', `$4`'')'dnl
 `_stack_reverse_sep(`tmp-$1', `$1')')
 define(`_stack_reverse_sep',
 `ifdef(`$1', `pushdef(`$2', defn(`$1'))$3`'popdef(`$1')$0(
-  `$1', `$2', `$4`'$3')')')
+  `$1', `$2', `$4$3')')')
 divert`'dnl


hooks/post-receive
--
GNU M4 source repository




reply via email to

[Prev in Thread] Current Thread [Next in Thread]