diff options
| -rw-r--r-- | build2/algorithm.cxx | 4 | ||||
| -rw-r--r-- | build2/config/operation.cxx | 1 | ||||
| -rw-r--r-- | build2/prerequisite | 75 | ||||
| -rw-r--r-- | build2/prerequisite.cxx | 5 | ||||
| -rw-r--r-- | build2/target | 13 | ||||
| -rw-r--r-- | build2/target-key | 64 | ||||
| -rw-r--r-- | build2/utility | 3 |
7 files changed, 127 insertions, 38 deletions
diff --git a/build2/algorithm.cxx b/build2/algorithm.cxx index ce25acf..1b19fe5 100644 --- a/build2/algorithm.cxx +++ b/build2/algorithm.cxx @@ -21,8 +21,8 @@ namespace build2 target& search (const prerequisite_key& pk) { - // If this is a project-qualified prerequisite, then this - // is import's business. + // If this is a project-qualified prerequisite, then this is import's + // business. // if (pk.proj != nullptr) return import (pk); diff --git a/build2/config/operation.cxx b/build2/config/operation.cxx index 1c395d2..fe36034 100644 --- a/build2/config/operation.cxx +++ b/build2/config/operation.cxx @@ -4,6 +4,7 @@ #include <build2/config/operation> +#include <set> #include <fstream> #include <butl/filesystem> diff --git a/build2/prerequisite b/build2/prerequisite index f316fb5..7c913f3 100644 --- a/build2/prerequisite +++ b/build2/prerequisite @@ -5,7 +5,8 @@ #ifndef BUILD2_PREREQUISITE #define BUILD2_PREREQUISITE -#include <set> +#include <functional> // hash +#include <unordered_set> #include <build2/types> #include <build2/utility> @@ -32,18 +33,50 @@ namespace build2 }; inline bool - operator< (const prerequisite_key& x, const prerequisite_key& y) + operator== (const prerequisite_key& x, const prerequisite_key& y) { assert (x.scope == y.scope); // Can compare project name pointers since they are from project_name_pool. // - return x.proj < y.proj || (x.proj == y.proj && x.tk < y.tk); + return x.proj == y.proj && x.tk == y.tk; + } + + inline bool + operator!= (const prerequisite_key& x, const prerequisite_key& y) + { + return !(x == y); } ostream& operator<< (ostream&, const prerequisite_key&); +} + +namespace std +{ + // Note that we ignore the extension when calculating the hash because of + // its special "unspecified" logic (see target_key::operator==). + // + template <> + struct hash<build2::prerequisite_key> + { + using argument_type = build2::prerequisite_key; + using result_type = size_t; + + size_t + operator() (const build2::prerequisite_key& k) const noexcept + { + // Can hash project name pointers since they are from project_name_pool. + // + return build2::combine_hash (hash<const string*> () (k.proj), + hash<build2::target_key> () (k.tk)); + } + }; +} + +namespace build2 +{ class prerequisite { public: @@ -100,9 +133,15 @@ namespace build2 }; inline bool - operator< (const prerequisite& x, const prerequisite& y) + operator== (const prerequisite& x, const prerequisite& y) { - return x.key () < y.key (); + return x.key () == y.key (); + } + + inline bool + operator!= (const prerequisite& x, const prerequisite& y) + { + return !(x == y); } inline ostream& @@ -111,9 +150,33 @@ namespace build2 return os << p.key (); } +} + +namespace std +{ + template <> + struct hash<build2::prerequisite> + { + using argument_type = build2::prerequisite; + using result_type = size_t; + + size_t + operator() (const build2::prerequisite& p) const noexcept + { + return hash<build2::prerequisite_key> () (p.key ()); + } + }; +} + +namespace build2 +{ // Set of prerequisites in a scope. // - struct prerequisite_set: std::set<prerequisite> + // Similar to targets, specified and unspecified extensions are considered + // equal and we may update the extension in the existing entry. To make + // this work we use a hash set. + // + struct prerequisite_set: std::unordered_set<prerequisite> { pair<prerequisite&, bool> insert (const string* proj, diff --git a/build2/prerequisite.cxx b/build2/prerequisite.cxx index 4adfc92..d2f80cf 100644 --- a/build2/prerequisite.cxx +++ b/build2/prerequisite.cxx @@ -59,7 +59,8 @@ namespace build2 tracer& trace) -> pair<prerequisite&, bool> { //@@ OPT: would be nice to somehow first check if this prerequisite is - // already in the set before allocating a new instance. + // already in the set before allocating a new instance. Something with + // bounds and insert hints? // Find or insert. // @@ -68,8 +69,6 @@ namespace build2 // Update extension if the existing prerequisite has it unspecified. // - // @@ Changing the key! - // if (p.ext != ext) { l5 ([&]{ diff --git a/build2/target b/build2/target index 9061e2d..ac67ff8 100644 --- a/build2/target +++ b/build2/target @@ -5,9 +5,9 @@ #ifndef BUILD2_TARGET #define BUILD2_TARGET -#include <map> #include <iterator> // tags, etc. #include <type_traits> +#include <unordered_map> #include <butl/multi-index> // map_iterator_adapter @@ -779,13 +779,18 @@ namespace build2 a, reverse_iterate (group_prerequisites (t)), members); } - // + // A target with an unspecified extension is considered equal to the one + // with the specified one. And when we find a target with an unspecified + // extension via a key with the specified one, we update the extension, + // essentially modifying the map's key. To make this work we use a hash + // map. The key's hash ignores the extension, so the hash will stay stable + // across extension updates. // struct target_set { - // @@ When we update ext in key, don't we change it? I think we do. + // @@ Why do we dynalloc target? // - typedef std::map<target_key, unique_ptr<target>> map; + typedef std::unordered_map<target_key, unique_ptr<target>> map; typedef butl::map_iterator_adapter<map::const_iterator> iterator; iterator diff --git a/build2/target-key b/build2/target-key index 2c0d0f2..c911a1f 100644 --- a/build2/target-key +++ b/build2/target-key @@ -6,6 +6,7 @@ #define BUILD2_TARGET_KEY #include <map> +#include <functional> // hash #include <butl/utility> // compare_c_string @@ -25,30 +26,26 @@ namespace build2 const dir_path* const dir; // Can be relative if part of prerequisite_key. const dir_path* const out; // Can be relative if part of prerequisite_key. const string* const name; - const string* const& ext; - - friend bool - operator< (const target_key& x, const target_key& y) - { - const target_type* xt (x.type); - const target_type* yt (y.type); - - int t, n, d, o; - - // Unspecified and specified extension are assumed equal. The - // extension strings are from the pool, so we can just compare - // pointers. - // - return - ((t = xt < yt ? -1 : xt > yt ? 1 : 0) < 0) || - (t == 0 && (n = x.name->compare (*y.name)) < 0) || - (t == 0 && n == 0 && (d = x.dir->compare (*y.dir)) < 0) || - (t == 0 && n == 0 && d == 0 && (o = x.out->compare (*y.out)) < 0) || - (t == 0 && n == 0 && d == 0 && o == 0 && - x.ext != nullptr && y.ext != nullptr && *x.ext < *y.ext); - } + const string* const& ext; //@@ Iffy, whan happens when move/copy? }; + inline bool + operator== (const target_key& x, const target_key& y) + { + // Unspecified and specified extension are assumed equal. The extension + // strings are from the pool, so we can just compare pointers. + // + return + x.type == y.type && + *x.dir == *y.dir && + *x.out == *y.out && + *x.name == *y.name && + (x.ext == nullptr || y.ext == nullptr || x.ext == y.ext); + } + + inline bool + operator!= (const target_key& x, const target_key& y) {return !(x == y);} + // If the target type has a custom print function, call that. Otherwise, // call to_stream() with the current stream verbosity as a third argument. // Both are defined in target.cxx. @@ -60,4 +57,27 @@ namespace build2 to_stream (ostream&, const target_key&, uint16_t ext_verb); } +namespace std +{ + // Note that we ignore the extension when calculating the hash because of + // its special "unspecified" logic (see operator== above). + // + template <> + struct hash<build2::target_key> + { + using argument_type = build2::target_key; + using result_type = size_t; + + size_t + operator() (const build2::target_key& k) const noexcept + { + return build2::combine_hash ( + hash<const build2::target_type*> () (k.type), + hash<build2::dir_path> () (*k.dir), + hash<build2::dir_path> () (*k.out), + hash<string> () (*k.name)); + } + }; +} + #endif // BUILD2_TARGET_KEY diff --git a/build2/utility b/build2/utility index e433b5a..e7674c0 100644 --- a/build2/utility +++ b/build2/utility @@ -11,7 +11,7 @@ #include <cassert> // assert() #include <iterator> // make_move_iterator() -#include <butl/utility> // reverse_iterate() +#include <butl/utility> // combine_hash(), reverse_iterate() #include <exception> // uncaught_exception() #include <unordered_set> @@ -31,6 +31,7 @@ namespace build2 // <butl/utility> // + using butl::combine_hash; using butl::reverse_iterate; // Basic string utilities. |