[SCM] GNU Autoconf source repository branch, master, updated. v2.62-41-g0bc266e

[Eric Blake]

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 Autoconf source repository".

http://git.sv.gnu.org/gitweb/?p=autoconf.git;a=commitdiff;h=0bc266ef1552bb68ec0d2483072b1f47bddcc4c4

The branch, master has been updated
       via  0bc266ef1552bb68ec0d2483072b1f47bddcc4c4 (commit)
      from  8d6a8686929e52e9bd1c4a0298132b172dfe96e1 (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 0bc266ef1552bb68ec0d2483072b1f47bddcc4c4
Author: Eric Blake <address@hidden>
Date:   Mon Jul 14 10:13:28 2008 -0600

    Tighten bound of potential speed of m4_append.
    
    * doc/autoconf.texi (Text processing Macros) <m4_append>
    <m4_prepend>: If m4 is fixed, m4_append can be linear rather than
    O(n log n).
    * lib/m4sugar/m4sugar.m4 (m4_append, m4_append_uniq): Fix comments.
    Analysis by Bruno Haible.
    
    Signed-off-by: Eric Blake <address@hidden>

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

Summary of changes:
 ChangeLog              |    9 +++++++++
 doc/autoconf.texi      |   12 ++++++------
 lib/m4sugar/m4sugar.m4 |    4 ++--
 3 files changed, 17 insertions(+), 8 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 9218ddc..8ae2ef6 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,12 @@
+2008-07-14  Eric Blake  <address@hidden>
+
+       Tighten bound of potential speed of m4_append.
+       * doc/autoconf.texi (Text processing Macros) <m4_append>
+       <m4_prepend>: If m4 is fixed, m4_append can be linear rather than
+       O(n log n).
+       * lib/m4sugar/m4sugar.m4 (m4_append, m4_append_uniq): Fix comments.
+       Analysis by Bruno Haible.
+
 2008-07-11  Eric Blake  <address@hidden>
 
        Inherit improvements from bison's fork of m4sugar.
diff --git a/doc/autoconf.texi b/doc/autoconf.texi
index 672e76b..a426cd8 100644
--- a/doc/autoconf.texi
+++ b/doc/autoconf.texi
@@ -11055,11 +11055,11 @@ to grow strings without duplicating substrings.  
Additionally,
 Also, @code{m4_append_uniq} warns if @var{separator} is not empty, but
 occurs within @var{string}, since that can lead to duplicates.
 
-Note that @code{m4_append} can scale @dfn{linearithmically} (ie., O(n
-log n) in complexity notation), depending on the quality of the
-underlying M4 implementation, while @code{m4_append_uniq} has an
-inherent quadratic scaling factor.  If an algorithm can tolerate
-duplicates in the final string, use the former for speed.
+Note that @code{m4_append} can scale linearly in the length of the final
+string, depending on the quality of the underlying M4 implementation,
+while @code{m4_append_uniq} has an inherent quadratic scaling factor.
+If an algorithm can tolerate duplicates in the final string, use the
+former for speed.
 
 @example
 m4_define([active], [ACTIVE])dnl
@@ -11184,7 +11184,7 @@ respectively, except that the @var{string} argument is 
added at the
 beginning instead of the end of the definition of @code{macro-name}.
 
 Also note that unlike @code{m4_append}, @code{m4_prepend} has quadratic
-rather than linearithmic scaling behavior.  Thus, if the order of list
+rather than linear scaling behavior.  Thus, if the order of list
 elements does not matter, it is better to append.
 @end defmac
 
diff --git a/lib/m4sugar/m4sugar.m4 b/lib/m4sugar/m4sugar.m4
index 0a708f6..a4d6f12 100644
--- a/lib/m4sugar/m4sugar.m4
+++ b/lib/m4sugar/m4sugar.m4
@@ -1923,7 +1923,7 @@ m4_define([m4_combine],
 #    => one, two, three
 #    => [one],[two],[three]
 #
-# Note that m4_append can benefit from amortized O(n log n) m4 behavior, if
+# Note that m4_append can benefit from amortized O(n) m4 behavior, if
 # the underlying m4 implementation is smart enough to avoid copying existing
 # contents when enlarging a macro's definition into any pre-allocated storage
 # (m4 1.4.x unfortunately does not implement this optimization).  m4_prepend
@@ -1947,7 +1947,7 @@ m4_define([m4_prepend],
 # was already present.  Also, warn if SEPARATOR is not empty and occurs
 # within STRING, as the algorithm no longer guarantees uniqueness.
 #
-# Note that while m4_append can be O(n log n) (depending on whether the
+# Note that while m4_append can be O(n) (depending on the quality of the
 # underlying M4 implementation), m4_append_uniq is inherently O(n^2)
 # because each append operation searches the entire string.
 m4_define([m4_append_uniq],


hooks/post-receive
--
GNU Autoconf source repository