From 1397444e5de3281431d2174564dfd76fe7b7b32f Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Thu, 21 Apr 2016 07:19:03 +0200 Subject: Use hash map/set for targets/prerequisites to resolve key change issue --- build2/algorithm.cxx | 4 +-- build2/config/operation.cxx | 1 + build2/prerequisite | 75 +++++++++++++++++++++++++++++++++++++++++---- build2/prerequisite.cxx | 5 ++- build2/target | 13 +++++--- build2/target-key | 64 +++++++++++++++++++++++++------------- 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 +#include #include #include 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 +#include // hash +#include #include #include @@ -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 + { + 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 () (k.proj), + hash () (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 + { + using argument_type = build2::prerequisite; + using result_type = size_t; + + size_t + operator() (const build2::prerequisite& p) const noexcept + { + return hash () (p.key ()); + } + }; +} + +namespace build2 +{ // Set of prerequisites in a scope. // - struct prerequisite_set: std::set + // 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 { pair 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 { //@@ 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 #include // tags, etc. #include +#include #include // 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> map; + typedef std::unordered_map> map; typedef butl::map_iterator_adapter 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 +#include // hash #include // 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 + { + 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 () (k.type), + hash () (*k.dir), + hash () (*k.out), + hash () (*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 // assert() #include // make_move_iterator() -#include // reverse_iterate() +#include // combine_hash(), reverse_iterate() #include // uncaught_exception() #include @@ -31,6 +31,7 @@ namespace build2 // // + using butl::combine_hash; using butl::reverse_iterate; // Basic string utilities. -- cgit v1.1