-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 According to Ralf Wildenhues on 7/14/2008 1:26 PM: |> But there is still the matter of how to remove all |> the stale macros if the key being appended to is redefined as empty. | | ... are certainly enough of a churn to require that such an improved | algorithm gets a new name, and the old one *remains*, supported with | its current semantics.
I came to the same conclusion - the API I'm thinking of, along with lightly tested code, is: # Expand IF-PRESENT or IF-ABSENT depending on whether VALUE # is in the set KEY. # O(1) #m4_set_contains(KEY, VALUE, [IF-PRESENT], [IF_ABSENT]) m4_define([m4_set_contains], [dnl track creation of this value m4_if(m4_ifdef([_m4_set_entry($1,$2)], ~ [m4_defn([_m4_set_entry($1,$2)])], [0]), ~ [1], [$3], [$4])[]dnl ]) # Add VALUE to the set KEY, if it is not already present. # VALUE can be arbitrary text (except that unbalanced quotes should # be given via quadrigraphs), while KEY must not contain a comma. # Expand IF-NEW or IF-DUP accordingly. # O(n) in the maximum length of unpruned set (depending on m4 quality) #m4_set_add(KEY, VALUE, [IF-NEW], [IF-DUP]) m4_define([m4_set_add], [m4_set_contains([$1], [$2], [$4], [dnl track creation of this value m4_define([_m4_set_entry($1,$2)], [1])dnl dnl and keep running track of all values in set m4_append([_m4_set_values($1)], [[$2]], [,])$3])[]dnl ]) # Remove VALUE from the set KEY, if it is present. # Expand IF-DELETED or IF-ABSENT accordingly. # Note that this implementation occupies extra memory until the next # m4_set_prune (which may be via m4_set_display or m4_set_delete). # O(1) #m4_set_remove(KEY, VALUE, [IF-DELETED], [IF-ABSENT]) m4_define([m4_set_remove], [m4_set_contains([$1], [$2], ~ [m4_define([_m4_set_entry($1,$2)], [0])$3], [$4])[]dnl ]) # Return a string containing all the elements of the set KEY, # separated by SEP. No provision is made for disambiguating # set elements that contain non-empty SEP as a sub-string. # This implementation also prunes any extra memory from deleted values. # O(n) in the maximum length of unpruned set (depending on m4 quality) #m4_set_contents(KEY, [SEP]) m4_define([m4_set_contents], [m4_set_prune([$1])m4_join([$2], m4_ifdef([_m4_set_values($1)], ~ [m4_unquote(m4_defn([_m4_set_values($1)]))]))[]dnl ]) # Return a string containing only the VALUEs that are elements # of the set KEY, separated by SEP. No provision is made for # disambiguating set elements that contain non-empty SEP as a # sub-string. The resulting string can contain duplicates, if # a given VALUE in the set is listed in multiple arguments. # No pruning of extra memory from deleted values is performed. # O(m) in the number of VALUEs. #m4_set_filter(KEY, [SEP], VALUE, [...]) m4_define([m4_set_filter], [m4_join([$2]m4_foreach([m4_value], m4_dquote(m4_shift2($@)), ~ [m4_set_contains([$1], m4_defn([m4_value]), ~ [, m4_defn([m4_value])])]))[]dnl ]) # Delete the set KEY, reclaiming all its memory. # O(n) in the maximum length of unpruned set #m4_set_delete(KEY) m4_define([m4_set_delete], [m4_ifdef([_m4_set_values($1)], ~ [m4_foreach([m4_value], m4_defn([_m4_set_values($1)]), ~ [m4_undefine([_m4_set_entry($1,]m4_defn([m4_value])[)])])dnl m4_undefine([_m4_set_values($1)])])dnl ]) # Reclaim any memory occupied by deleted set elements from the set KEY. # O(n) in the maximum length of unpruned set #m4_set_prune(KEY) m4_define([m4_set_prune], [m4_ifdef([_m4_set_values($1)], [m4_define([_m4_set_values($1)], ~ m4_join([,]m4_foreach([m4_value], m4_defn([_m4_set_values($1)]), ~ [m4_if(m4_defn([_m4_set_entry($1,]m4_defn([m4_value])[)]), ~ [0], [m4_undefine([_m4_set_entry($1,]m4_defn([m4_value])[)])], ~ [, m4_dquote(m4_defn([m4_value]))])[]dnl ])))])dnl ]) With the above, counting the number of set elements is O(n). We could additionally add O(1) set size querying, if desired, by making m4_set_add and m4_set_remove modify _m4_set_size($1). - -- 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 iEYEARECAAYFAkh8FOgACgkQ84KuGfSFAYCV/gCgglJtmCAJDgxCO+iN8/FBxf+l HesAn0mXPQAipt8DjcA2pkc2oE7AbFmT =z5B5 -----END PGP SIGNATURE----- _______________________________________________ m4-discuss mailing list m4-discuss@gnu.org http://lists.gnu.org/mailman/listinfo/m4-discuss
