|
|
Boost-Commit : |
From: daniel_james_at_[hidden]
Date: 2008-06-22 09:54:46
Author: danieljames
Date: 2008-06-22 09:54:45 EDT (Sun, 22 Jun 2008)
New Revision: 46607
URL: http://svn.boost.org/trac/boost/changeset/46607
Log:
Extract the hash and equality functions from hash_table_data_*.
As these are extensions and add extra requirements to the container elements,
they shouldn't be part of hash_table_data_* so that they won't get instantiated
if an unordered container is explicitly instantiated.
Merged revisions 46594-46604 via svnmerge from
https://svn.boost.org/svn/boost/branches/unordered/trunk
Properties modified:
trunk/ (props changed)
Text files modified:
trunk/boost/unordered/detail/hash_table_impl.hpp | 237 +++++++++++++++++++++++----------------
trunk/boost/unordered_map.hpp | 12 +-
trunk/boost/unordered_set.hpp | 12 +-
3 files changed, 153 insertions(+), 108 deletions(-)
Modified: trunk/boost/unordered/detail/hash_table_impl.hpp
==============================================================================
--- trunk/boost/unordered/detail/hash_table_impl.hpp (original)
+++ trunk/boost/unordered/detail/hash_table_impl.hpp 2008-06-22 09:54:45 EDT (Sun, 22 Jun 2008)
@@ -1493,8 +1493,6 @@
/ static_cast<float>(data_.bucket_manager_.bucket_count());
}
- private:
-
// key extractors
// no throw
@@ -2127,100 +2125,6 @@
}
}
- //
- // equals
- //
-
-private:
-#if BOOST_UNORDERED_EQUIVALENT_KEYS
- static inline bool group_equals(link_ptr it1, link_ptr it2,
- type_wrapper<key_type>*)
- {
- return data::group_count(it1) == data::group_count(it2);
- }
-
- static inline bool group_equals(link_ptr it1, link_ptr it2, void*)
- {
- link_ptr end1 = data::next_group(it1);
- link_ptr end2 = data::next_group(it2);
- do {
- if(data::get_value(it1).second != data::get_value(it2).second) return false;
- it1 = it1->next_;
- it2 = it2->next_;
- } while(it1 != end1 && it2 != end2);
- return it1 == end1 && it2 == end2;
- }
-#else
- static inline bool group_equals(link_ptr, link_ptr,
- type_wrapper<key_type>*)
- {
- return true;
- }
-
- static inline bool group_equals(link_ptr it1, link_ptr it2, void*)
- {
- return data::get_value(it1).second == data::get_value(it2).second;
- }
-#endif
-
-public:
- bool equals(BOOST_UNORDERED_TABLE const& other) const
- {
- if(size() != other.size()) return false;
-
- for(bucket_ptr i = data_.cached_begin_bucket_,
- j = data_.buckets_end(); i != j; ++i)
- {
- for(link_ptr it(i->next_); BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it))
- {
- link_ptr other_pos = other.find_iterator(other.extract_key(data::get_value(it)));
- if(!BOOST_UNORDERED_BORLAND_BOOL(other_pos) ||
- !group_equals(it, other_pos, (type_wrapper<value_type>*)0))
- return false;
- }
- }
-
- return true;
- }
-
- inline std::size_t group_hash(link_ptr it, type_wrapper<key_type>*) const
- {
- std::size_t seed = data::group_count(it);
- std::size_t hashed_key = hash_function()(data::get_value(it));
- boost::hash_combine(seed, hashed_key);
- return seed;
- }
-
- inline std::size_t group_hash(link_ptr it, void*) const
- {
- std::size_t seed = hash_function()(data::get_value(it).first);
-
- link_ptr end = data::next_group(it);
-
- do {
- boost::hash_combine(seed, data::get_value(it).second);
- it = it->next_;
- } while(it != end);
-
- return seed;
- }
-
- std::size_t hash_value() const
- {
- std::size_t seed = 0;
-
- for(bucket_ptr i = data_.cached_begin_bucket_,
- j = data_.buckets_end(); i != j; ++i)
- {
- for(link_ptr it(i->next_); BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it))
- seed ^= group_hash(it, (type_wrapper<value_type>*)0);
- }
-
- return seed;
- }
-
- private:
-
// strong exception safety, no side effects
bool equal(key_type const& k, value_type const& v) const
{
@@ -2255,6 +2159,147 @@
}
};
+ //
+ // Equals - unordered container equality comparison.
+ //
+
+#if BOOST_UNORDERED_EQUIVALENT_KEYS
+ template <typename A, typename KeyType>
+ inline bool group_equals(
+ BOOST_UNORDERED_TABLE_DATA<A>*,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it1,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it2,
+ KeyType*,
+ type_wrapper<KeyType>*)
+ {
+ typedef BOOST_UNORDERED_TABLE_DATA<A> data;
+ return data::group_count(it1) == data::group_count(it2);
+ }
+
+ template <typename A, typename KeyType>
+ inline bool group_equals(
+ BOOST_UNORDERED_TABLE_DATA<A>*,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it1,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it2,
+ KeyType*,
+ void*)
+ {
+ typedef BOOST_UNORDERED_TABLE_DATA<A> data;
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr end1 = data::next_group(it1);
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr end2 = data::next_group(it2);
+
+ do {
+ if(data::get_value(it1).second != data::get_value(it2).second) return false;
+ it1 = it1->next_;
+ it2 = it2->next_;
+ } while(it1 != end1 && it2 != end2);
+ return it1 == end1 && it2 == end2;
+ }
+#else
+ template <typename A, typename KeyType>
+ inline bool group_equals(
+ BOOST_UNORDERED_TABLE_DATA<A>*,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr,
+ KeyType*,
+ type_wrapper<KeyType>*)
+ {
+ return true;
+ }
+
+ template <typename A, typename KeyType>
+ inline bool group_equals(
+ BOOST_UNORDERED_TABLE_DATA<A>*,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it1,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it2,
+ KeyType*,
+ void*)
+ {
+ typedef BOOST_UNORDERED_TABLE_DATA<A> data;
+ return data::get_value(it1).second == data::get_value(it2).second;
+ }
+#endif
+
+ template <typename V, typename K, typename H, typename P, typename A>
+ bool equals(BOOST_UNORDERED_TABLE<V, K, H, P, A> const& t1,
+ BOOST_UNORDERED_TABLE<V, K, H, P, A> const& t2)
+ {
+ typedef BOOST_UNORDERED_TABLE_DATA<A> data;
+ typedef typename data::bucket_ptr bucket_ptr;
+ typedef typename data::link_ptr link_ptr;
+
+ if(t1.size() != t2.size()) return false;
+
+ for(bucket_ptr i = t1.data_.cached_begin_bucket_,
+ j = t1.data_.buckets_end(); i != j; ++i)
+ {
+ for(link_ptr it(i->next_); BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it))
+ {
+ link_ptr other_pos = t2.find_iterator(t2.extract_key(data::get_value(it)));
+ if(!BOOST_UNORDERED_BORLAND_BOOL(other_pos) ||
+ !group_equals((data*)0, it, other_pos, (K*)0, (type_wrapper<V>*)0))
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ //
+ // hash_value - unordered container hash function.
+ //
+
+ template <typename V, typename K, typename H, typename P, typename A>
+ std::size_t group_hash(BOOST_UNORDERED_TABLE<V, K, H, P, A> const& t,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it,
+ type_wrapper<K>*)
+ {
+ typedef BOOST_UNORDERED_TABLE_DATA<A> data;
+ std::size_t seed = data::group_count(it);
+ std::size_t hashed_key = t.hash_function()(data::get_value(it));
+ boost::hash_combine(seed, hashed_key);
+ return seed;
+ }
+
+ template <typename V, typename K, typename H, typename P, typename A>
+ std::size_t group_hash(BOOST_UNORDERED_TABLE<V, K, H, P, A> const& t,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it,
+ void*)
+ {
+ typedef BOOST_UNORDERED_TABLE_DATA<A> data;
+ typedef typename data::link_ptr link_ptr;
+
+ std::size_t seed = t.hash_function()(data::get_value(it).first);
+
+ link_ptr end = data::next_group(it);
+
+ do {
+ boost::hash_combine(seed, data::get_value(it).second);
+ it = it->next_;
+ } while(it != end);
+
+ return seed;
+ }
+
+ template <typename V, typename K, typename H, typename P, typename A>
+ std::size_t hash_value(BOOST_UNORDERED_TABLE<V, K, H, P, A> const& t)
+ {
+ typedef BOOST_UNORDERED_TABLE_DATA<A> data;
+ typedef typename data::link_ptr link_ptr;
+ typedef typename data::bucket_ptr bucket_ptr;
+
+ std::size_t seed = 0;
+
+ for(bucket_ptr i = t.data_.cached_begin_bucket_,
+ j = t.data_.buckets_end(); i != j; ++i)
+ {
+ for(link_ptr it(i->next_); BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it))
+ seed ^= group_hash(t, it, (type_wrapper<V>*)0);
+ }
+
+ return seed;
+ }
+
// Iterators
template <typename Alloc> class BOOST_UNORDERED_ITERATOR;
Modified: trunk/boost/unordered_map.hpp
==============================================================================
--- trunk/boost/unordered_map.hpp (original)
+++ trunk/boost/unordered_map.hpp 2008-06-22 09:54:45 EDT (Sun, 22 Jun 2008)
@@ -431,20 +431,20 @@
inline bool operator==(unordered_map<K, T, H, P, A> const& m1,
unordered_map<K, T, H, P, A> const& m2)
{
- return m1.base.equals(m2.base);
+ return boost::unordered_detail::equals(m1.base, m2.base);
}
template <class K, class T, class H, class P, class A>
inline bool operator!=(unordered_map<K, T, H, P, A> const& m1,
unordered_map<K, T, H, P, A> const& m2)
{
- return !m1.base.equals(m2.base);
+ return !boost::unordered_detail::equals(m1.base, m2.base);
}
template <class K, class T, class H, class P, class A>
inline std::size_t hash_value(unordered_map<K, T, H, P, A> const& m)
{
- return m.base.hash_value();
+ return boost::unordered_detail::hash_value(m.base);
}
template <class K, class T, class H, class P, class A>
@@ -805,20 +805,20 @@
inline bool operator==(unordered_multimap<K, T, H, P, A> const& m1,
unordered_multimap<K, T, H, P, A> const& m2)
{
- return m1.base.equals(m2.base);
+ return boost::unordered_detail::equals(m1.base, m2.base);
}
template <class K, class T, class H, class P, class A>
inline bool operator!=(unordered_multimap<K, T, H, P, A> const& m1,
unordered_multimap<K, T, H, P, A> const& m2)
{
- return !m1.base.equals(m2.base);
+ return !boost::unordered_detail::equals(m1.base, m2.base);
}
template <class K, class T, class H, class P, class A>
inline std::size_t hash_value(unordered_multimap<K, T, H, P, A> const& m)
{
- return m.base.hash_value();
+ return boost::unordered_detail::hash_value(m.base);
}
template <class K, class T, class H, class P, class A>
Modified: trunk/boost/unordered_set.hpp
==============================================================================
--- trunk/boost/unordered_set.hpp (original)
+++ trunk/boost/unordered_set.hpp 2008-06-22 09:54:45 EDT (Sun, 22 Jun 2008)
@@ -401,20 +401,20 @@
inline bool operator==(unordered_set<T, H, P, A> const& m1,
unordered_set<T, H, P, A> const& m2)
{
- return m1.base.equals(m2.base);
+ return boost::unordered_detail::equals(m1.base, m2.base);
}
template <class T, class H, class P, class A>
inline bool operator!=(unordered_set<T, H, P, A> const& m1,
unordered_set<T, H, P, A> const& m2)
{
- return !m1.base.equals(m2.base);
+ return !boost::unordered_detail::equals(m1.base, m2.base);
}
template <class T, class H, class P, class A>
inline std::size_t hash_value(unordered_set<T, H, P, A> const& m)
{
- return m.base.hash_value();
+ return boost::unordered_detail::hash_value(m.base);
}
template <class T, class H, class P, class A>
@@ -761,20 +761,20 @@
inline bool operator==(unordered_multiset<T, H, P, A> const& m1,
unordered_multiset<T, H, P, A> const& m2)
{
- return m1.base.equals(m2.base);
+ return boost::unordered_detail::equals(m1.base, m2.base);
}
template <class T, class H, class P, class A>
inline bool operator!=(unordered_multiset<T, H, P, A> const& m1,
unordered_multiset<T, H, P, A> const& m2)
{
- return !m1.base.equals(m2.base);
+ return !boost::unordered_detail::equals(m1.base, m2.base);
}
template <class T, class H, class P, class A>
inline std::size_t hash_value(unordered_multiset<T, H, P, A> const& m)
{
- return m.base.hash_value();
+ return boost::unordered_detail::hash_value(m.base);
}
template <class T, class H, class P, class A>
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