-----BEGIN PGP SIGNED MESSAGE----- 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 [EMAIL PROTECTED] -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (Cygwin) Comment: Public key at home.comcast.net/~ericblake/eblake.gpg Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iEYEARECAAYFAkh6AKwACgkQ84KuGfSFAYC4KACeMD3eHciNCG/Mf/UHqfn5mRwF HmEAniLwS/k6bldZJSn4EcNgcwaoaHyv =3zLW -----END PGP SIGNATURE----- _______________________________________________ m4-discuss mailing list m4-discuss@gnu.org http://lists.gnu.org/mailman/listinfo/m4-discuss
