autoconf: Set manipulation Macros
1
1 8.3.9 Set manipulation in M4
1 ----------------------------
1
1 Sometimes, it is necessary to track a set of data, where the order does
1 not matter and where there are no duplicates in the set. The following
1 macros facilitate set manipulations. Each set is an opaque object,
1 which can only be accessed via these basic operations. The underlying
1 implementation guarantees linear scaling for set creation, which is more
1 efficient than using the quadratic `m4_append_uniq'. Both set names
1 and values can be arbitrary strings, except for unbalanced quotes.
1 This implementation ties up memory for removed elements until the next
1 operation that must traverse all the elements of a set; and although
1 that may slow down some operations until the memory for removed elements
1 is pruned, it still guarantees linear performance.
1
1 -- Macro: m4_set_add (SET, VALUE, [IF-UNIQ], [IF-DUP])
1 Adds the string VALUE as a member of set SET. Expand IF-UNIQ if
1 the element was added, or IF-DUP if it was previously in the set.
1 Operates in amortized constant time, so that set creation scales
1 linearly.
1
1 -- Macro: m4_set_add_all (SET, VALUE...)
1 Adds each VALUE to the set SET. This is slightly more efficient
1 than repeatedly invoking `m4_set_add'.
1
1 -- Macro: m4_set_contains (SET, VALUE, [IF-PRESENT], [IF-ABSENT])
1 Expands IF-PRESENT if the string VALUE is a member of SET,
1 otherwise IF-ABSENT.
1
1 m4_set_contains([a], [1], [yes], [no])
1 =>no
1 m4_set_add([a], [1], [added], [dup])
1 =>added
1 m4_set_add([a], [1], [added], [dup])
1 =>dup
1 m4_set_contains([a], [1], [yes], [no])
1 =>yes
1 m4_set_remove([a], [1], [removed], [missing])
1 =>removed
1 m4_set_contains([a], [1], [yes], [no])
1 =>no
1 m4_set_remove([a], [1], [removed], [missing])
1 =>missing
1
1 -- Macro: m4_set_contents (SET, [SEP])
1 -- Macro: m4_set_dump (SET, [SEP])
1 Expands to a single string consisting of all the members of the set
1 SET, each separated by SEP, which is not expanded.
1 `m4_set_contents' leaves the elements in SET but reclaims any
1 memory occupied by removed elements, while `m4_set_dump' is a
1 faster one-shot action that also deletes the set. No provision is
1 made for disambiguating members that contain a non-empty SEP as a
1 substring; use `m4_set_empty' to distinguish between an empty set
1 and the set containing only the empty string. The order of the
1 output is unspecified; in the current implementation, part of the
1 speed of `m4_set_dump' results from using a different output order
1 than `m4_set_contents'. These macros scale linearly in the size
1 of the set before memory pruning, and `m4_set_contents([SET],
1 [SEP])' is faster than `m4_joinall([SEP]m4_set_listc([SET]))'.
1
1 m4_set_add_all([a], [1], [2], [3])
1 =>
1 m4_set_contents([a], [-])
1 =>1-2-3
1 m4_joinall([-]m4_set_listc([a]))
1 =>1-2-3
1 m4_set_dump([a], [-])
1 =>3-2-1
1 m4_set_contents([a])
1 =>
1 m4_set_add([a], [])
1 =>
1 m4_set_contents([a], [-])
1 =>
1
1 -- Macro: m4_set_delete (SET)
1 Delete all elements and memory associated with SET. This is
1 linear in the set size, and faster than removing one element at a
1 time.
1
1 -- Macro: m4_set_difference (SETA, SETB)
1 -- Macro: m4_set_intersection (SETA, SETB)
1 -- Macro: m4_set_union (SETA, SETB)
1 Compute the relation between SETA and SETB, and output the result
1 as a list of quoted arguments without duplicates and with a
1 leading comma. Set difference selects the elements in SETA but
1 not SETB, intersection selects only elements in both sets, and
1 union selects elements in either set. These actions are linear in
1 the sum of the set sizes. The leading comma is necessary to
1 distinguish between no elements and the empty string as the only
1 element.
1
1 m4_set_add_all([a], [1], [2], [3])
1 =>
1 m4_set_add_all([b], [3], [], [4])
1 =>
1 m4_set_difference([a], [b])
1 =>,1,2
1 m4_set_difference([b], [a])
1 =>,,4
1 m4_set_intersection([a], [b])
1 =>,3
1 m4_set_union([a], [b])
1 =>,1,2,3,,4
1
1 -- Macro: m4_set_empty (SET, [IF-EMPTY], [IF-ELEMENTS])
1 Expand IF-EMPTY if the set SET has no elements, otherwise expand
1 IF-ELEMENTS. This macro operates in constant time. Using this
1 macro can help disambiguate output from `m4_set_contents' or
1 `m4_set_list'.
1
1 -- Macro: m4_set_foreach (SET, VARIABLE, ACTION)
1 For each element in the set SET, expand ACTION with the macro
1 VARIABLE defined as the set element. Behavior is unspecified if
1 ACTION recursively lists the contents of SET (although listing
1 other sets is acceptable), or if it modifies the set in any way
1 other than removing the element currently contained in VARIABLE.
1 This macro is faster than the corresponding `m4_foreach([VARIABLE],
1 m4_indir([m4_dquote]m4_set_listc([SET])), [ACTION])', although
1 `m4_set_map' might be faster still.
1
1 m4_set_add_all([a]m4_for([i], [1], [5], [], [,i]))
1 =>
1 m4_set_contents([a])
1 =>12345
1 m4_set_foreach([a], [i],
1 [m4_if(m4_eval(i&1), [0], [m4_set_remove([a], i, [i])])])
1 =>24
1 m4_set_contents([a])
1 =>135
1
1 -- Macro: m4_set_list (SET)
1 -- Macro: m4_set_listc (SET)
1 Produce a list of arguments, where each argument is a quoted
1 element from the set SET. The variant `m4_set_listc' is
1 unambiguous, by adding a leading comma if there are any set
1 elements, whereas the variant `m4_set_list' cannot distinguish
1 between an empty set and a set containing only the empty string.
1 These can be directly used in macros that take multiple arguments,
1 such as `m4_join' or `m4_set_add_all', or wrapped by `m4_dquote'
1 for macros that take a quoted list, such as `m4_map' or
1 `m4_foreach'. Any memory occupied by removed elements is
1 reclaimed during these macros.
1
1 m4_set_add_all([a], [1], [2], [3])
1 =>
1 m4_set_list([a])
1 =>1,2,3
1 m4_set_list([b])
1 =>
1 m4_set_listc([b])
1 =>
1 m4_count(m4_set_list([b]))
1 =>1
1 m4_set_empty([b], [0], [m4_count(m4_set_list([b]))])
1 =>0
1 m4_set_add([b], [])
1 =>
1 m4_set_list([b])
1 =>
1 m4_set_listc([b])
1 =>,
1 m4_count(m4_set_list([b]))
1 =>1
1 m4_set_empty([b], [0], [m4_count(m4_set_list([b]))])
1 =>1
1
1 -- Macro: m4_set_map (SET, ACTION)
1 For each element in the set SET, expand ACTION with a single
1 argument of the set element. Behavior is unspecified if ACTION
1 recursively lists the contents of SET (although listing other sets
1 is acceptable), or if it modifies the set in any way other than
1 removing the element passed as an argument. This macro is faster
1 than either corresponding counterpart of
1 `m4_map_args([ACTION]m4_set_listc([SET]))' or
1 `m4_set_foreach([SET], [var], [ACTION(m4_defn([var]))])'. It is
1 possible to use `m4_curry' if more than one argument is needed for
1 ACTION, although it is more efficient to use `m4_set_map_sep' in
1 that case.
1
1 -- Macro: m4_set_map_sep (SET, [PRE], [POST], [SEP])
1 For each element in the set SET, expand `PRE[element]POST',
1 additionally expanding SEP between elements. Behavior is
1 unspecified if the expansion recursively lists the contents of SET
1 (although listing other sets is acceptable), or if it modifies the
1 set in any way other than removing the element visited by the
1 expansion. This macro provides the most efficient means for
1 non-destructively visiting the elements of a set; in particular,
1 `m4_set_map([SET], [ACTION])' is equivalent to
1 `m4_set_map_sep([SET], [ACTION(], [)])'.
1
1 -- Macro: m4_set_remove (SET, VALUE, [IF-PRESENT], [IF-ABSENT])
1 If VALUE is an element in the set SET, then remove it and expand
1 IF-PRESENT. Otherwise expand IF-ABSENT. This macro operates in
1 constant time so that multiple removals will scale linearly rather
1 than quadratically; but when used outside of `m4_set_foreach' or
1 `m4_set_map', it leaves memory occupied until the set is later
1 compacted by `m4_set_contents' or `m4_set_list'. Several other
1 set operations are then less efficient between the time of element
1 removal and subsequent memory compaction, but still maintain their
1 guaranteed scaling performance.
1
1 -- Macro: m4_set_size (SET)
1 Expand to the size of the set SET. This implementation operates
1 in constant time, and is thus more efficient than
1 `m4_eval(m4_count(m4_set_listc([set])) - 1)'.
1