aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--build2/algorithm.cxx4
-rw-r--r--build2/config/operation.cxx1
-rw-r--r--build2/prerequisite75
-rw-r--r--build2/prerequisite.cxx5
-rw-r--r--build2/target13
-rw-r--r--build2/target-key64
-rw-r--r--build2/utility3
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.