|
|
Boost-Commit : |
From: daniel_james_at_[hidden]
Date: 2007-12-16 13:20:26
Author: danieljames
Date: 2007-12-16 13:20:25 EST (Sun, 16 Dec 2007)
New Revision: 42108
URL: http://svn.boost.org/trac/boost/changeset/42108
Log:
If the containers have equality comparisons, they'll also need 'hash_value'. Untested and undocumented, as before.
Text files modified:
sandbox/unordered/boost/unordered/detail/hash_table_impl.hpp | 35 +++++++++++++++++
sandbox/unordered/boost/unordered_map.hpp | 12 +++++
sandbox/unordered/boost/unordered_set.hpp | 12 +++++
sandbox/unordered/libs/unordered/doc/ref.xml | 80 ++++++++++++++++++++++++++++++++++++++++
sandbox/unordered/libs/unordered/test/container/compile_tests.hpp | 5 ++
sandbox/unordered/libs/unordered/test/objects/minimal.hpp | 4 ++
6 files changed, 146 insertions(+), 2 deletions(-)
Modified: sandbox/unordered/boost/unordered/detail/hash_table_impl.hpp
==============================================================================
--- sandbox/unordered/boost/unordered/detail/hash_table_impl.hpp (original)
+++ sandbox/unordered/boost/unordered/detail/hash_table_impl.hpp 2007-12-16 13:20:25 EST (Sun, 16 Dec 2007)
@@ -1926,6 +1926,41 @@
return true;
}
+ inline bool group_hash(local_iterator_base it, type_wrapper<key_type>*) const
+ {
+ std::size_t seed = group_count(it);
+ boost::hash_combine(seed, hash_function()(*it));
+ return seed;
+ }
+
+ inline bool group_hash(local_iterator_base it, void*) const
+ {
+ std::size_t seed = hash_function()(it->first);
+
+ local_iterator_base end = it;
+ end.next_group();
+
+ do {
+ boost::hash_combine(seed, it->second);
+ } while(it != end);
+
+ return seed;
+ }
+
+ std::size_t hash_value() const
+ {
+ std::size_t seed = 0;
+
+ for(bucket_ptr i = this->cached_begin_bucket_,
+ j = this->buckets_ + this->bucket_count_; i != j; ++i)
+ {
+ for(local_iterator_base it(i->next_); it.not_finished(); it.next_group())
+ seed ^= group_hash(it, (type_wrapper<value_type>*)0);
+ }
+
+ return seed;
+ }
+
private:
// strong exception safety, no side effects
Modified: sandbox/unordered/boost/unordered_map.hpp
==============================================================================
--- sandbox/unordered/boost/unordered_map.hpp (original)
+++ sandbox/unordered/boost/unordered_map.hpp 2007-12-16 13:20:25 EST (Sun, 16 Dec 2007)
@@ -16,8 +16,8 @@
#include <functional>
#include <memory>
-#include <boost/unordered/detail/hash_table.hpp>
#include <boost/functional/hash.hpp>
+#include <boost/unordered/detail/hash_table.hpp>
namespace boost
{
@@ -335,6 +335,11 @@
{
return !m1.base.equals(m2.base);
}
+
+ friend std::size_t hash_value(unordered_map const& m)
+ {
+ return m.base.hash_value();
+ }
}; // class template unordered_map
template <class K, class T, class H, class P, class A>
@@ -642,6 +647,11 @@
{
return !m1.base.equals(m2.base);
}
+
+ friend std::size_t hash_value(unordered_multimap const& m)
+ {
+ return m.base.hash_value();
+ }
}; // class template unordered_multimap
template <class K, class T, class H, class P, class A>
Modified: sandbox/unordered/boost/unordered_set.hpp
==============================================================================
--- sandbox/unordered/boost/unordered_set.hpp (original)
+++ sandbox/unordered/boost/unordered_set.hpp 2007-12-16 13:20:25 EST (Sun, 16 Dec 2007)
@@ -16,8 +16,8 @@
#include <functional>
#include <memory>
-#include <boost/unordered/detail/hash_table.hpp>
#include <boost/functional/hash.hpp>
+#include <boost/unordered/detail/hash_table.hpp>
namespace boost
{
@@ -305,6 +305,11 @@
{
return !m1.base.equals(m2.base);
}
+
+ friend std::size_t hash_value(unordered_set const& m)
+ {
+ return m.base.hash_value();
+ }
}; // class template unordered_set
template <class T, class H, class P, class A>
@@ -597,6 +602,11 @@
{
return !m1.base.equals(m2.base);
}
+
+ friend std::size_t hash_value(unordered_multiset const& m)
+ {
+ return m.base.hash_value();
+ }
}; // class template unordered_multiset
template <class T, class H, class P, class A>
Modified: sandbox/unordered/libs/unordered/doc/ref.xml
==============================================================================
--- sandbox/unordered/libs/unordered/doc/ref.xml (original)
+++ sandbox/unordered/libs/unordered/doc/ref.xml 2007-12-16 13:20:25 EST (Sun, 16 Dec 2007)
@@ -636,6 +636,25 @@
<para>This is a boost extension.</para>
</notes>
</function>
+ <function name="hash_value">
+ <template>
+ <template-type-parameter name="Value">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_set<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>std::size_t</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
</free-function-group>
<free-function-group name="swap">
<function name="swap">
@@ -1293,6 +1312,25 @@
<para>This is a boost extension.</para>
</notes>
</function>
+ <function name="hash_value">
+ <template>
+ <template-type-parameter name="Value">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_multiset<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>std::size_t</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
</free-function-group>
<free-function-group name="swap">
<function name="swap">
@@ -2005,6 +2043,27 @@
<para>This is a boost extension.</para>
</notes>
</function>
+ <function name="hash_value">
+ <template>
+ <template-type-parameter name="Key">
+ </template-type-parameter>
+ <template-type-parameter name="Mapped">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_map<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>std::size_t</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
</free-function-group>
<free-function-group name="swap">
<function name="swap">
@@ -2676,6 +2735,27 @@
<para>This is a boost extension.</para>
</notes>
</function>
+ <function name="hash_value">
+ <template>
+ <template-type-parameter name="Key">
+ </template-type-parameter>
+ <template-type-parameter name="Mapped">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_multimap<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>std::size_t</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
</free-function-group>
<free-function-group name="swap">
<function name="swap">
Modified: sandbox/unordered/libs/unordered/test/container/compile_tests.hpp
==============================================================================
--- sandbox/unordered/libs/unordered/test/container/compile_tests.hpp (original)
+++ sandbox/unordered/libs/unordered/test/container/compile_tests.hpp 2007-12-16 13:20:25 EST (Sun, 16 Dec 2007)
@@ -129,4 +129,9 @@
test::check_return_type<bool>::equals(a == b);
test::check_return_type<bool>::equals(a != b);
+#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
+ test::check_return_type<std::size_t>::equals(boost::hash_value(a));
+#else
+ test::check_return_type<std::size_t>::equals(hash_value(a));
+#endif
}
Modified: sandbox/unordered/libs/unordered/test/objects/minimal.hpp
==============================================================================
--- sandbox/unordered/libs/unordered/test/objects/minimal.hpp (original)
+++ sandbox/unordered/libs/unordered/test/objects/minimal.hpp 2007-12-16 13:20:25 EST (Sun, 16 Dec 2007)
@@ -57,6 +57,10 @@
return false;
}
+ std::size_t hash_value(copy_constructible_equality_comparable) {
+ return 1;
+ }
+
class default_copy_constructible
{
public:
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk