[Top][All Lists]

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

Re: m4sugar and m4 1.6, bison

From: Eric Blake
Subject: Re: m4sugar and m4 1.6, bison
Date: Sun, 13 Jul 2008 07:18:37 -0600
User-agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv: Gecko/20080421 Thunderbird/ Mnenhy/

Hash: SHA1

According to Ralf Wildenhues on 7/12/2008 12:39 AM:
| * Ralf Wildenhues wrote on Sat, Jul 12, 2008 at 08:11:55AM CEST:
|> So then here's a first prototype for fast m4_append_uniq, completely
|> untested, and would probably need some more-unique separator after $1 in
|> the definition of m4_key.
| I'll blame it on lack of coffee...
|> # m4_make_macro_name(STRING)
|> # Turn all characters not fitting to be a macro name into '_'.
|> m4_define([m4_make_macro_name],
|> [m4_bpatsubst([$1], [...])dnl
|> ])

GNU m4 allows any character in a macro name (you just have to use indir
and defn to access such macros).  I think your approach can be made to
work without having to introduce m4_make_macro_name, and thus avoid
collisions altogether.  But there is still the matter of how to remove all
the stale macros if the key being appended to is redefined as empty.

|> # m4_append_uniq(MACRO-NAME, STRING, [SEPARATOR], [IF-UNIQ], [IF-DUP])
|> m4_define([m4_append_uniq],
|> [m4_pushdef([m4_key], [_$1_[]make_macro_name([$2])])dnl
|> m4_ifdef(m4_key,
|>   [m4_if([m4_defn(m4_key)], [$2],
| This is completely ignoring hash key collision.  So, assuming that
| collisions are rare, i.e., usually strings differ not only in characters
| not allowed in a macro name, then the duplicate test here can just reuse
| the one from the version of m4_append_uniq currently in Autoconf.  That
| will probably still give amortized fast check here.  Actually, I guess
| the uniq part is even O(n), only the reallocs necessary now and then
| will be loglinear.

Linear, actually - the check for whether a macro is defined is amortized
O(1), because macros are stored in a hash table, and coupling an O(1)
search along with Bruno's proof of O(n) insertion, the overall
m4_append_uniq is theoretically still O(n) rather than O(n log n).

At any rate, I see what you are trying to do - add an additional expense
of O(n) storage in order to avoid an expense of O(n) time in searching for
previously supplied entries (m4_append already uses O(n) storage for the
macro name, so you are just increasing the constant factor).  It seems
like libtool's ltsugar provides lt_dict* that does something like this
sort of operation.  And it certainly seems like something worth pursuing,
but not until after m4_append is fixed to be O(n) (no scaling improvements
result by making the search faster if the insertion is still slow).

| Still completely untested, of course...

- --
Don't work too hard, make some time for fun as well!

Eric Blake             address@hidden
Version: GnuPG v1.4.9 (Cygwin)
Comment: Public key at
Comment: Using GnuPG with Mozilla -


reply via email to

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