From: daniel_james_at_[hidden]
Date: 2008-04-26 12:23:52
Author: danieljames
Date: 2008-04-26 12:23:51 EDT (Sat, 26 Apr 2008)
New Revision: 44779
URL: http://svn.boost.org/trac/boost/changeset/44779
Log:
Merge in support for equality operators.
Added:
branches/unordered/trunk/libs/unordered/test/unordered/equality_tests.cpp (contents, props changed)
Text files modified:
branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp | 93 ++++++++++++++++++++++++++++++++++++++++
branches/unordered/trunk/boost/unordered_map.hpp | 32 +++++++++++++
branches/unordered/trunk/boost/unordered_set.hpp | 32 +++++++++++++
branches/unordered/trunk/libs/unordered/test/objects/minimal.hpp | 24 ++++++++++
branches/unordered/trunk/libs/unordered/test/unordered/Jamfile.v2 | 1
branches/unordered/trunk/libs/unordered/test/unordered/compile_map.cpp | 37 +++++++++++++++
branches/unordered/trunk/libs/unordered/test/unordered/compile_set.cpp | 30 ++++++++++++
branches/unordered/trunk/libs/unordered/test/unordered/compile_tests.hpp | 18 ++++++-
8 files changed, 262 insertions(+), 5 deletions(-)
Modified: branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp
==============================================================================
--- branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp (original)
+++ branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp 2008-04-26 12:23:51 EDT (Sat, 26 Apr 2008)
@@ -2136,6 +2136,99 @@
}
}
+ //
+ // 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*)
+ {
+ if(!BOOST_UNORDERED_BORLAND_BOOL(it2)) return false;
+ 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 it1, link_ptr it2,
+ 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
Modified: branches/unordered/trunk/boost/unordered_map.hpp
==============================================================================
--- branches/unordered/trunk/boost/unordered_map.hpp (original)
+++ branches/unordered/trunk/boost/unordered_map.hpp 2008-04-26 12:23:51 EDT (Sat, 26 Apr 2008)
@@ -18,8 +18,8 @@
#include <functional>
#include <memory>
-#include <boost/unordered/detail/hash_table.hpp>
#include <boost/functional/hash.hpp>
+#include <boost/unordered/detail/hash_table.hpp>
#if !defined(BOOST_HAS_RVALUE_REFS)
#include <boost/unordered/detail/move.hpp>
@@ -387,6 +387,21 @@
{
base.rehash(n);
}
+
+ friend bool operator==(unordered_map const& m1, unordered_map const& m2)
+ {
+ return m1.base.equals(m2.base);
+ }
+
+ friend bool operator!=(unordered_map const& m1, unordered_map const& m2)
+ {
+ 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>
@@ -739,6 +754,21 @@
{
base.rehash(n);
}
+
+ friend bool operator==(unordered_multimap const& m1, unordered_multimap const& m2)
+ {
+ return m1.base.equals(m2.base);
+ }
+
+ friend bool operator!=(unordered_multimap const& m1, unordered_multimap const& m2)
+ {
+ 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: branches/unordered/trunk/boost/unordered_set.hpp
==============================================================================
--- branches/unordered/trunk/boost/unordered_set.hpp (original)
+++ branches/unordered/trunk/boost/unordered_set.hpp 2008-04-26 12:23:51 EDT (Sat, 26 Apr 2008)
@@ -18,8 +18,8 @@
#include <functional>
#include <memory>
-#include <boost/unordered/detail/hash_table.hpp>
#include <boost/functional/hash.hpp>
+#include <boost/unordered/detail/hash_table.hpp>
#if !defined(BOOST_HAS_RVALUE_REFS)
#include <boost/unordered/detail/move.hpp>
@@ -358,6 +358,21 @@
{
base.rehash(n);
}
+
+ friend bool operator==(unordered_set const& m1, unordered_set const& m2)
+ {
+ return m1.base.equals(m2.base);
+ }
+
+ friend bool operator!=(unordered_set const& m1, unordered_set const& m2)
+ {
+ 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>
@@ -695,6 +710,21 @@
{
base.rehash(n);
}
+
+ friend bool operator==(unordered_multiset const& m1, unordered_multiset const& m2)
+ {
+ return m1.base.equals(m2.base);
+ }
+
+ friend bool operator!=(unordered_multiset const& m1, unordered_multiset const& m2)
+ {
+ 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: branches/unordered/trunk/libs/unordered/test/objects/minimal.hpp
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/objects/minimal.hpp (original)
+++ branches/unordered/trunk/libs/unordered/test/objects/minimal.hpp 2008-04-26 12:23:51 EDT (Sat, 26 Apr 2008)
@@ -22,6 +22,7 @@
namespace minimal
{
class copy_constructible;
+ class copy_constructible_equality_comparable;
class default_copy_constructible;
class assignable;
@@ -42,6 +43,29 @@
copy_constructible() {}
};
+ class copy_constructible_equality_comparable
+ {
+ public:
+ static copy_constructible_equality_comparable create() { return copy_constructible_equality_comparable(); }
+ copy_constructible_equality_comparable(copy_constructible_equality_comparable const&) {}
+ ~copy_constructible_equality_comparable() {}
+ private:
+ copy_constructible_equality_comparable& operator=(copy_constructible_equality_comparable const&);
+ copy_constructible_equality_comparable() {}
+ };
+
+ bool operator==(copy_constructible_equality_comparable, copy_constructible_equality_comparable) {
+ return true;
+ }
+
+ bool operator!=(copy_constructible_equality_comparable, copy_constructible_equality_comparable) {
+ return false;
+ }
+
+ std::size_t hash_value(copy_constructible_equality_comparable) {
+ return 1;
+ }
+
class default_copy_constructible
{
public:
Modified: branches/unordered/trunk/libs/unordered/test/unordered/Jamfile.v2
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/unordered/Jamfile.v2 (original)
+++ branches/unordered/trunk/libs/unordered/test/unordered/Jamfile.v2 2008-04-26 12:23:51 EDT (Sat, 26 Apr 2008)
@@ -33,5 +33,6 @@
[ run bucket_tests.cpp ]
[ run load_factor_tests.cpp ]
[ run rehash_tests.cpp ]
+ [ run equality_tests.cpp ]
[ run swap_tests.cpp : : : <define>BOOST_UNORDERED_SWAP_METHOD=2 ]
;
Modified: branches/unordered/trunk/libs/unordered/test/unordered/compile_map.cpp
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/unordered/compile_map.cpp (original)
+++ branches/unordered/trunk/libs/unordered/test/unordered/compile_map.cpp 2008-04-26 12:23:51 EDT (Sat, 26 Apr 2008)
@@ -22,6 +22,9 @@
test::minimal::copy_constructible::create());
std::cout<<"Test unordered_map.\n";
+
+ boost::unordered_map<int, int> int_map;
+
boost::unordered_map<
test::minimal::assignable,
test::minimal::copy_constructible,
@@ -29,9 +32,13 @@
test::minimal::equal_to<test::minimal::assignable>,
test::minimal::allocator<value_type> > map;
+ container_test(int_map, std::pair<int const, int>(0, 0));
container_test(map, value);
std::cout<<"Test unordered_multimap.\n";
+
+ boost::unordered_multimap<int, int> int_multimap;
+
boost::unordered_multimap<
test::minimal::assignable,
test::minimal::copy_constructible,
@@ -39,9 +46,39 @@
test::minimal::equal_to<test::minimal::assignable>,
test::minimal::allocator<value_type> > multimap;
+ container_test(int_multimap, std::pair<int const, int>(0, 0));
container_test(multimap, value);
}
+UNORDERED_AUTO_TEST(equality_tests) {
+ typedef std::pair<test::minimal::assignable const,
+ test::minimal::copy_constructible> value_type;
+
+ boost::unordered_map<int, int> int_map;
+
+ boost::unordered_map<
+ test::minimal::assignable,
+ test::minimal::copy_constructible_equality_comparable,
+ test::minimal::hash<test::minimal::assignable>,
+ test::minimal::equal_to<test::minimal::assignable>,
+ test::minimal::allocator<value_type> > map;
+
+ equality_test(int_map);
+ equality_test(map);
+
+ boost::unordered_multimap<int, int> int_multimap;
+
+ boost::unordered_multimap<
+ test::minimal::assignable,
+ test::minimal::copy_constructible_equality_comparable,
+ test::minimal::hash<test::minimal::assignable>,
+ test::minimal::equal_to<test::minimal::assignable>,
+ test::minimal::allocator<value_type> > multimap;
+
+ equality_test(int_multimap);
+ equality_test(multimap);
+}
+
UNORDERED_AUTO_TEST(test1) {
boost::hash<int> hash;
std::equal_to<int> equal_to;
Modified: branches/unordered/trunk/libs/unordered/test/unordered/compile_set.cpp
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/unordered/compile_set.cpp (original)
+++ branches/unordered/trunk/libs/unordered/test/unordered/compile_set.cpp 2008-04-26 12:23:51 EDT (Sat, 26 Apr 2008)
@@ -18,24 +18,54 @@
test::minimal::assignable assignable = test::minimal::assignable::create();
std::cout<<"Test unordered_set.\n";
+ boost::unordered_set<int> int_set;
boost::unordered_set<
test::minimal::assignable,
test::minimal::hash<test::minimal::assignable>,
test::minimal::equal_to<test::minimal::assignable>,
test::minimal::allocator<test::minimal::assignable> > set;
+ container_test(int_set, 0);
container_test(set, assignable);
std::cout<<"Test unordered_multiset.\n";
+ boost::unordered_multiset<int> int_multiset;
boost::unordered_multiset<
test::minimal::assignable,
test::minimal::hash<test::minimal::assignable>,
test::minimal::equal_to<test::minimal::assignable>,
test::minimal::allocator<test::minimal::assignable> > multiset;
+ container_test(int_multiset, 0);
container_test(multiset, assignable);
}
+UNORDERED_AUTO_TEST(equality_tests) {
+ typedef test::minimal::assignable value_type;
+
+ boost::unordered_set<int> int_set;
+
+ boost::unordered_set<
+ test::minimal::assignable,
+ test::minimal::hash<test::minimal::assignable>,
+ test::minimal::equal_to<test::minimal::assignable>,
+ test::minimal::allocator<value_type> > set;
+
+ equality_test(int_set);
+ equality_test(set);
+
+ boost::unordered_multiset<int> int_multiset;
+
+ boost::unordered_multiset<
+ test::minimal::assignable,
+ test::minimal::hash<test::minimal::assignable>,
+ test::minimal::equal_to<test::minimal::assignable>,
+ test::minimal::allocator<value_type> > multiset;
+
+ equality_test(int_multiset);
+ equality_test(multiset);
+}
+
UNORDERED_AUTO_TEST(test1)
{
boost::hash<int> hash;
Modified: branches/unordered/trunk/libs/unordered/test/unordered/compile_tests.hpp
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/unordered/compile_tests.hpp (original)
+++ branches/unordered/trunk/libs/unordered/test/unordered/compile_tests.hpp 2008-04-26 12:23:51 EDT (Sat, 26 Apr 2008)
@@ -28,7 +28,7 @@
template <class T> T rvalue(T const& v) { return v; }
template <class X, class T>
-void container_test(X& r, T&)
+void container_test(X& r, T const&)
{
typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
typedef BOOST_DEDUCED_TYPENAME X::const_iterator const_iterator;
@@ -121,8 +121,6 @@
test::check_return_type<const_iterator>::equals(a.cend());
test::check_return_type<const_iterator>::equals(a_const.cend());
- // No tests for ==, != since they're not required for unordered containers.
-
a.swap(b);
test::check_return_type<X>::equals_ref(r = a);
test::check_return_type<size_type>::equals(a.size());
@@ -161,6 +159,20 @@
#endif
}
+template <class X>
+void equality_test(X& r)
+{
+ X const a = r, b = r;
+
+ 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
+}
+
template <class X, class T>
void unordered_unique_test(X& r, T const& t)
{
Added: branches/unordered/trunk/libs/unordered/test/unordered/equality_tests.cpp
==============================================================================
--- (empty file)
+++ branches/unordered/trunk/libs/unordered/test/unordered/equality_tests.cpp 2008-04-26 12:23:51 EDT (Sat, 26 Apr 2008)
@@ -0,0 +1,129 @@
+
+// Copyright 2008 Daniel James.
+// Distributed under the Boost Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/unordered_set.hpp>
+#include <boost/unordered_map.hpp>
+#include "../helpers/test.hpp"
+#include "../objects/test.hpp"
+#include "../helpers/random_values.hpp"
+#include <list>
+
+namespace equality_tests {
+ test::seed_t seed(78634);
+
+ template<class T>
+ struct container_holder {
+ test::random_values<T> values;
+ T container;
+
+ container_holder()
+ : values(0), container()
+ {}
+
+ container_holder(int count, test::random_generator const& generator)
+ : values(count, generator),
+ container(values.begin(), values.end())
+ {
+ }
+ };
+
+ template <class T>
+ void equality_tests1(T*, test::random_generator generator
+ = test::default_generator)
+ {
+ const std::size_t num_containers = 100;
+
+ std::list<container_holder<T> > containers;
+ container_holder<T> empty;
+ containers.push_back(container_holder<T>());
+ BOOST_CHECK(empty.values == empty.values);
+ BOOST_CHECK(empty.values == containers.back().values);
+ BOOST_CHECK(empty.container == empty.container);
+ BOOST_CHECK(empty.container == containers.back().container);
+
+ container_holder<T> one(1, generator);
+ containers.push_back(one);
+
+ BOOST_CHECK(empty.values != one.values);
+ BOOST_CHECK(one.values == one.values);
+ BOOST_CHECK(one.values == containers.back().values);
+ BOOST_CHECK(empty.container != one.container);
+ BOOST_CHECK(one.container == one.container);
+ BOOST_CHECK(one.container == containers.back().container);
+
+ container_holder<T> hundred(100, generator);
+ container_holder<T> hundred2(100, generator);
+ BOOST_CHECK(hundred.values != hundred2.values);
+
+ containers.push_back(hundred);
+ containers.push_back(hundred2);
+
+ BOOST_CHECK(empty.values != hundred.values);
+ BOOST_CHECK(one.values != hundred.values);
+ BOOST_CHECK(hundred.values == hundred.values);
+ BOOST_CHECK(hundred2.values != hundred.values);
+ BOOST_CHECK(hundred.values == hundred.values);
+ BOOST_CHECK(hundred2.values == containers.back().values);
+
+ BOOST_CHECK(empty.container != hundred.container);
+ BOOST_CHECK(one.container != hundred.container);
+ BOOST_CHECK(hundred.container == hundred.container);
+ BOOST_CHECK(hundred2.container != hundred.container);
+ BOOST_CHECK(hundred.container == hundred.container);
+ BOOST_CHECK(hundred2.container == containers.back().container);
+
+ for(std::size_t i = containers.size(); i < num_containers; ++i) {
+ using namespace std;
+ containers.push_back(
+ container_holder<T>(rand() % 150, generator));
+ }
+
+ std::size_t count1, count2;
+ typename std::list<container_holder<T> >::const_iterator it1, it2;
+ for(it1 = containers.begin(), count1 = 0; it1 != containers.end(); ++it1, ++count1) {
+ for(it2 = it1, count2 = count1; it2 != containers.end(); ++it2, ++count2) {
+ if(it1 == it2) {
+ if(it1->container != it2->container ||
+ !(it1->container == it2->container))
+ {
+ std::cerr<<"Container "<<count1<<":\n";
+ BOOST_ERROR("Not equal to itself!");
+ }
+ }
+ else if(it1->values == it2->values) {
+ if(it1->container != it2->container ||
+ !(it1->container == it2->container))
+ {
+ std::cerr<<"Containers "<<count1<<","<<count2<<":\n";
+ BOOST_ERROR("Should be equal");
+ }
+ }
+ else {
+ if(it1->container == it2->container ||
+ !(it1->container != it2->container))
+ {
+ std::cerr<<"Containers "<<count1<<","<<count2<<":\n";
+ BOOST_ERROR("Should not be equal");
+ }
+ }
+ }
+ }
+ }
+
+ boost::unordered_set<test::object, test::hash, test::equal_to, test::allocator<test::object> >* test_set;
+ boost::unordered_multiset<test::object, test::hash, test::equal_to, test::allocator<test::object> >* test_multiset;
+ boost::unordered_map<test::object, test::object, test::hash, test::equal_to, test::allocator<test::object> >* test_map;
+ boost::unordered_multimap<test::object, test::object, test::hash, test::equal_to, test::allocator<test::object> >* test_multimap;
+
+ using test::default_generator;
+ using test::generate_collisions;
+
+ UNORDERED_TEST(equality_tests1,
+ ((test_set)(test_multiset)(test_map)(test_multimap))
+ ((default_generator)(generate_collisions))
+ )
+}
+
+RUN_TESTS()