[Boost-commit] svn:boost r44779 - in branches/unordered/trunk: boost boost/unordered/detail libs/unordered/test/objects libs/unordered/test/unordered

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()