aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2006-11-29 12:24:12 +0000
committerAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2006-11-29 12:24:12 +0000
commitb43f39919c06e471bac3e34f99c0c0ad8e05de7b (patch)
tree7eb4b3a9d1da9f825ff5c6a2f9365d9c16b06adb
parentcf6d968d41dd96fe01f3acc5f43644c8078860ac (diff)
downloadpaludis-b43f39919c06e471bac3e34f99c0c0ad8e05de7b.tar.gz
paludis-b43f39919c06e471bac3e34f99c0c0ad8e05de7b.tar.xz
Use a faster hash function for version specs
-rw-r--r--paludis/version_spec.cc99
-rw-r--r--paludis/version_spec_TEST.cc30
2 files changed, 107 insertions, 22 deletions
diff --git a/paludis/version_spec.cc b/paludis/version_spec.cc
index 8e5a498..2cf307f 100644
--- a/paludis/version_spec.cc
+++ b/paludis/version_spec.cc
@@ -79,6 +79,20 @@ namespace paludis
/// Our parts.
std::vector<Part> parts;
+
+ /// Our hash
+ mutable bool has_hash;
+ mutable std::size_t hash;
+
+ /// Our is_scm
+ mutable bool has_is_scm;
+ mutable bool is_scm;
+
+ Implementation() :
+ has_hash(false),
+ has_is_scm(false)
+ {
+ }
};
}
@@ -265,6 +279,10 @@ VersionSpec::operator= (const VersionSpec & other)
{
_imp->text = other._imp->text;
_imp->parts = other._imp->parts;
+ _imp->has_hash = other._imp->has_hash;
+ _imp->hash = other._imp->hash;
+ _imp->has_is_scm = other._imp->has_is_scm;
+ _imp->is_scm = other._imp->is_scm;
}
return *this;
}
@@ -334,10 +352,32 @@ VersionSpec::equal_star_compare(const VersionSpec & other) const
std::size_t
VersionSpec::hash_value() const
{
- /// \todo Improve this;
- if (_imp->parts.empty())
- return 0;
- return _imp->parts[0].value;
+ if (_imp->has_hash)
+ return _imp->hash;
+
+ size_t result(0);
+
+ const std::size_t h_shift = std::numeric_limits<std::size_t>::digits - 5;
+ const std::size_t h_mask = static_cast<std::size_t>(0x1f) << h_shift;
+
+ do
+ {
+ for (std::vector<Part>::const_iterator r(_imp->parts.begin()), r_end(_imp->parts.end()) ;
+ r != r_end ; ++r)
+ {
+ if (r->kind == empty && r->value == 0)
+ continue;
+
+ std::size_t hh(result & h_mask);
+ result <<= 5;
+ result ^= (hh >> h_shift);
+ result ^= (static_cast<std::size_t>(r->kind) + (r->value << 3));
+ }
+ } while (false);
+
+ _imp->has_hash = true;
+ _imp->hash = result;
+ return result;
}
namespace
@@ -397,26 +437,45 @@ paludis::operator<< (std::ostream & s, const VersionSpec & v)
bool
VersionSpec::is_scm() const
{
- std::vector<Part>::const_iterator r;
+ if (_imp->has_is_scm)
+ return _imp->is_scm;
+
+ bool result(false);
+ do
+ {
+ std::vector<Part>::const_iterator r;
- if (_imp->parts.empty())
- return false;
+ if (_imp->parts.empty())
+ break;
- /* are we an obvious scm version? */
- r = std::find_if(_imp->parts.begin(), _imp->parts.end(), IsPart<scm>());
- if (r != _imp->parts.end())
- return true;
+ /* are we an obvious scm version? */
+ r = std::find_if(_imp->parts.begin(), _imp->parts.end(), IsPart<scm>());
+ if (r != _imp->parts.end())
+ {
+ result = true;
+ break;
+ }
- /* are we a -r9999? */
- r = std::find_if(_imp->parts.begin(), _imp->parts.end(), IsPart<revision>());
- if (r != _imp->parts.end())
- if (r->value == 9999)
- return true;
+ /* are we a -r9999? */
+ r = std::find_if(_imp->parts.begin(), _imp->parts.end(), IsPart<revision>());
+ if (r != _imp->parts.end())
+ if (r->value == 9999)
+ {
+ result = true;
+ break;
+ }
- /* is our version without revisions exactly 9999? */
- if (remove_revision() == VersionSpec("9999"))
- return true;
+ /* is our version without revisions exactly 9999? */
+ if (remove_revision() == VersionSpec("9999"))
+ {
+ result = true;
+ break;
+ }
+ } while (false);
+
+ _imp->is_scm = result;
+ _imp->has_is_scm = true;
- return false;
+ return result;
}
diff --git a/paludis/version_spec_TEST.cc b/paludis/version_spec_TEST.cc
index d464c8a..3b5ff22 100644
--- a/paludis/version_spec_TEST.cc
+++ b/paludis/version_spec_TEST.cc
@@ -207,6 +207,20 @@ namespace test_cases
}
} test_version_is_scm;
+ struct VersionSpecHashTest : TestCase
+ {
+ VersionSpecHashTest() : TestCase("version spec hash_value()") { }
+
+ void run()
+ {
+ TEST_CHECK(VersionSpec("0").hash_value() == VersionSpec("0.0").hash_value());
+ TEST_CHECK(VersionSpec("1").hash_value() == VersionSpec("1.0").hash_value());
+ TEST_CHECK(VersionSpec("1.0").hash_value() == VersionSpec("1").hash_value());
+ TEST_CHECK(VersionSpec("1.0_alpha").hash_value() == VersionSpec("1_alpha").hash_value());
+ TEST_CHECK(VersionSpec("1_alpha").hash_value() == VersionSpec("1.0_alpha").hash_value());
+ }
+ } test_version_spec_hash_value;
+
/**
* \test VersionSpec ordering.
*
@@ -295,17 +309,21 @@ namespace test_cases
std::vector<VersionSpec>::iterator v1(v.begin()), v_end(v.end());
for ( ; v1 != v_end ; ++v1)
{
- TestMessageSuffix s1("v1:" + stringify(*v1), false);
+ TestMessageSuffix s1("v1:" + stringify(*v1), true);
std::vector<VersionSpec>::iterator v2(v.begin());
for ( ; v2 != v_end ; ++v2)
{
- TestMessageSuffix s2("v2:" + stringify(*v2), false);
+ TestMessageSuffix s2("v2:" + stringify(*v2), true);
if (std::distance(v.begin(), v1) < std::distance(v.begin(), v2))
{
TEST_CHECK(*v1 < *v2);
TEST_CHECK(*v2 > *v1);
TEST_CHECK(*v1 != *v2);
TEST_CHECK(*v2 != *v1);
+ TestMessageSuffix sv1("hv1:" + stringify(v1->hash_value()), true);
+ TestMessageSuffix sv2("hv2:" + stringify(v2->hash_value()), true);
+ TEST_CHECK(v1->hash_value() != v2->hash_value());
+ TEST_CHECK(v2->hash_value() != v1->hash_value());
}
else if (std::distance(v.begin(), v1) > std::distance(v.begin(), v2))
{
@@ -313,11 +331,19 @@ namespace test_cases
TEST_CHECK(*v1 > *v2);
TEST_CHECK(*v2 != *v1);
TEST_CHECK(*v1 != *v2);
+ TestMessageSuffix sv1("hv1:" + stringify(v1->hash_value()), true);
+ TestMessageSuffix sv2("hv2:" + stringify(v2->hash_value()), true);
+ TEST_CHECK(v1->hash_value() != v2->hash_value());
+ TEST_CHECK(v2->hash_value() != v1->hash_value());
}
else
{
TEST_CHECK(*v2 == *v1);
TEST_CHECK(*v1 == *v2);
+ TestMessageSuffix sv1("hv1:" + stringify(v1->hash_value()), true);
+ TestMessageSuffix sv2("hv2:" + stringify(v2->hash_value()), true);
+ TEST_CHECK(v1->hash_value() == v2->hash_value());
+ TEST_CHECK(v2->hash_value() == v1->hash_value());
}
}
}