[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[SCM] GNU M4 source repository branch, branch-1.6, updated. v1.5.89a-42-
From: |
Eric Blake |
Subject: |
[SCM] GNU M4 source repository branch, branch-1.6, updated. v1.5.89a-42-geeaceb3 |
Date: |
Sat, 26 Jul 2008 22:43:48 +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=eeaceb311464f6d88d2782ed8773c01d49f83aba
The branch, branch-1.6 has been updated
via eeaceb311464f6d88d2782ed8773c01d49f83aba (commit)
from ffaa885fc0efb39bf0ca0df0a592a1c39f92729c (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 eeaceb311464f6d88d2782ed8773c01d49f83aba
Author: Eric Blake <address@hidden>
Date: Sat Jul 26 15:39:48 2008 -0600
Give example for O(n) foreach on m4 1.4.x.
* examples/foreachq4.m4: New file.
* examples/Makefile.am (EXTRA_DIST): Distribute it.
* doc/m4.texinfo (Improved foreach): Document linear foreach with
m4 1.4.5 and greater.
Signed-off-by: Eric Blake <address@hidden>
-----------------------------------------------------------------------
Summary of changes:
ChangeLog | 6 +++
doc/m4.texinfo | 83 +++++++++++++++++++++++++++++++++++++++++++++++++
examples/Makefile.am | 1 +
examples/foreachq4.m4 | 13 ++++++++
examples/loop.m4 | 5 ++-
5 files changed, 106 insertions(+), 2 deletions(-)
create mode 100644 examples/foreachq4.m4
diff --git a/ChangeLog b/ChangeLog
index de44226..9572436 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
2008-07-26 Eric Blake <address@hidden>
+ Give example for O(n) foreach on m4 1.4.x.
+ * examples/foreachq4.m4: New file.
+ * examples/Makefile.am (EXTRA_DIST): Distribute it.
+ * doc/m4.texinfo (Improved foreach): Document linear foreach with
+ m4 1.4.5 and greater.
+
Use hash module for self-growing symbol table.
* m4/gnulib-cache.m4: Import hash module.
* src/m4.h (struct symbol): Remove next member, change stack to be
diff --git a/doc/m4.texinfo b/doc/m4.texinfo
index e78061c..0185ba5 100644
--- a/doc/m4.texinfo
+++ b/doc/m4.texinfo
@@ -7879,6 +7879,61 @@ noticeable; in fact, after the change, the
@file{foreachq2.m4} version
uses slightly less memory since it tracks fewer arguments per macro
invocation.
address@hidden nine arguments, more than
address@hidden more than nine arguments
address@hidden arguments, more than nine
+So far, all of the implementations of @code{foreachq} presented have
+been quadratic with M4 1.4.x. But @code{forloop} is linear, because
+each iteration parses a constant amount of arguments. So, it is
+possible to design a variant that uses @code{forloop} to do the
+iteration, then uses @samp{$@@} only once at the end, giving a linear
+result even with older M4 implementations. This implementation relies
+on the @acronym{GNU} extension that @samp{$10} expands to the tenth
+argument rather than the first argument concatenated with @samp{0}. The
+trick is to define an intermediate macro that repeats the text
address@hidden(`$1', `$n')$2`'}, with @samp{n} set to successive
+integers corresponding to each argument. The helper macro
address@hidden is needed in order to generate the literal sequences
+such as @samp{$1} into the intermediate macro, rather than expanding
+them as the arguments of @code{_foreachq}. With this approach, no
address@hidden calls are even needed! However, when linear recursion is
+available in new enough M4, the time and memory cost of using
address@hidden to build an intermediate macro outweigh the costs of any
+of the previous implementations. Additionally, this approach will need
+adjustment when a future version of M4 follows @acronym{POSIX} by no
+longer treating @samp{$10} as the tenth argument; the anticipation is
+that @address@hidden@}} can be used instead, although that alternative
+syntax is not yet supported.
+
address@hidden examples
address@hidden
+$ @kbd{m4 -I examples}
+include(`foreachq4.m4')
address@hidden
+undivert(`foreachq4.m4')dnl
address@hidden(`forloop2.m4')dnl
address@hidden(`-1')
address@hidden foreachq(x, `item_1, item_2, ..., item_n', stmt)
address@hidden quoted list, version based on forloop
address@hidden(`foreachq',
address@hidden(`$2', `', `', `_$0(`$1', `$3', $2)')')
address@hidden(`_foreachq',
address@hidden(`$1', forloop(`$1', `3', `$#',
address@hidden `$0_(`1', `2', indir(`$1'))')`popdef(
address@hidden `$1')')indir(`$1', $@@)')
address@hidden(`_foreachq_',
address@hidden(`$$1', `$$3')$$2`''')
address@hidden'dnl
+traceon(`shift')debugmode(`aq')
address@hidden
+foreachq(`x', ``1', `2', `3', `4'', `x
+')dnl
address@hidden
address@hidden
address@hidden
address@hidden
address@hidden example
+
For yet another approach, the improved version of @code{foreach},
available in @address@hidden/@/examples/@/foreach2.m4}, simply
overquotes the arguments to @address@hidden to begin with, using
@@ -8065,6 +8120,34 @@ include(`loop.m4')dnl
@result{}10000
@end example
address@hidden foreach via forloop recursion
+
address@hidden examples
address@hidden options: -Dlimit=10 -Dverbose -Dalt=4
address@hidden
+$ @kbd {m4 -I examples -Dlimit=10 -Dverbose -Dalt=4}
+include(`loop.m4')dnl
address@hidden 1 2 3 4 5 6 7 8 9 10
address@hidden example
+
address@hidden examples
address@hidden options: -Dlimit=2500 -Dalt=4
address@hidden
+$ @kbd {m4 -I examples -Dlimit=2500 -Dalt=4}
+include(`loop.m4')dnl
address@hidden example
+
address@hidden examples
address@hidden options: -Dlimit=10000 -Dalt=4
address@hidden
+$ @kbd {m4 -I examples -Dlimit=10000 -Dalt=4}
+define(`foo', `divert`'len(popdef(`_foreachq')_foreachq($@@))')dnl
+define(`debug', `pushdef(`_foreachq', defn(`foo'))')
address@hidden
+include(`loop.m4')dnl
address@hidden
address@hidden example
+
@end ignore
@node Improved m4wrap
diff --git a/examples/Makefile.am b/examples/Makefile.am
index 254d2ab..47bf0c0 100644
--- a/examples/Makefile.am
+++ b/examples/Makefile.am
@@ -34,6 +34,7 @@ foreach2.m4 \
foreachq.m4 \
foreachq2.m4 \
foreachq3.m4 \
+foreachq4.m4 \
forloop.m4 \
forloop2.m4 \
fstab.m4 \
diff --git a/examples/foreachq4.m4 b/examples/foreachq4.m4
new file mode 100644
index 0000000..3da64c9
--- /dev/null
+++ b/examples/foreachq4.m4
@@ -0,0 +1,13 @@
+include(`forloop2.m4')dnl
+divert(`-1')
+# foreachq(x, `item_1, item_2, ..., item_n', stmt)
+# quoted list, version based on forloop
+define(`foreachq',
+`ifelse(`$2', `', `', `_$0(`$1', `$3', $2)')')
+define(`_foreachq',
+`pushdef(`$1', forloop(`$1', `3', `$#',
+ `$0_(`1', `2', indir(`$1'))')`popdef(
+ `$1')')indir(`$1', $@)')
+define(`_foreachq_',
+``define(`$$1', `$$3')$$2`''')
+divert`'dnl
diff --git a/examples/loop.m4 b/examples/loop.m4
index 31761c9..b2fc64c 100644
--- a/examples/loop.m4
+++ b/examples/loop.m4
@@ -1,7 +1,7 @@
dnl Stress test for recursion algorithms. Usage:
dnl m4 -Ipath/to/examples [-Doptions] loop.m4
dnl Options include:
-dnl -Dalt - test with foreachq3 instead of foreachq2
+dnl -Dalt[=<n>] - test with foreachq<n> instead of foreachq2, default 3
dnl -Dlimit=<num> - set upper limit of sequence to <num>, default 1000
dnl -Dverbose - print the sequence to the screen, rather than discarding
dnl -Ddebug[=<code>] - execute <code> after forloop but before foreach
@@ -9,7 +9,8 @@ dnl -Dsleep=<num> - sleep for <num> seconds before exit, to
allow time
dnl to examine peak process memory usage
include(`forloop2.m4')dnl
include(`quote.m4')dnl
-include(ifdef(`alt', ``foreachq3.m4'', ``foreachq2.m4''))dnl
+ifelse(alt, `alt', `define(`alt', `2')', alt, `', `define(`alt', `3')')dnl
+include(`foreachq'alt`.m4')dnl
ifdef(`limit', `', `define(`limit', `1000')')dnl
ifdef(`verbose', `', `divert(`-1')')dnl
ifdef(`debug', `', `define(`debug')')dnl
hooks/post-receive
--
GNU M4 source repository
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [SCM] GNU M4 source repository branch, branch-1.6, updated. v1.5.89a-42-geeaceb3,
Eric Blake <=