[Boost-commit] svn:boost r42736 - in branches/unordered/dev: boost boost/unordered/detail libs/unordered/doc libs/unordered/test/objects libs/unordered/test/unordered

From: daniel_james_at_[hidden]
Date: 2008-01-13 15:45:38

Author: danieljames
Date: 2008-01-13 15:45:37 EST (Sun, 13 Jan 2008)
New Revision: 42736
URL: http://svn.boost.org/trac/boost/changeset/42736

Log:
Work in progress equality operators + hash_value for unordered.
Text files modified: 
   branches/unordered/dev/boost/unordered/detail/hash_table_impl.hpp      |    93 +++++++++++++                           
   branches/unordered/dev/boost/unordered_map.hpp                         |    32 ++++                                    
   branches/unordered/dev/boost/unordered_set.hpp                         |    32 ++++                                    
   branches/unordered/dev/libs/unordered/doc/ref.xml                      |   272 ++++++++++++++++++++++++++++++++++++++++
   branches/unordered/dev/libs/unordered/test/objects/minimal.hpp         |    24 +++                                     
   branches/unordered/dev/libs/unordered/test/unordered/compile_map.cpp   |    27 +++                                     
   branches/unordered/dev/libs/unordered/test/unordered/compile_set.cpp   |     2                                         
   branches/unordered/dev/libs/unordered/test/unordered/compile_tests.hpp |    16 ++                                      
   8 files changed, 494 insertions(+), 4 deletions(-)

Modified: branches/unordered/dev/boost/unordered/detail/hash_table_impl.hpp
==============================================================================
--- branches/unordered/dev/boost/unordered/detail/hash_table_impl.hpp	(original)
+++ branches/unordered/dev/boost/unordered/detail/hash_table_impl.hpp	2008-01-13 15:45:37 EST (Sun, 13 Jan 2008)
@@ -1818,6 +1818,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(this->size() != other.size()) return false;
+
+                for(bucket_ptr i = this->cached_begin_bucket_,
+                        j = this->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 = this->cached_begin_bucket_,
+                        j = this->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/dev/boost/unordered_map.hpp
==============================================================================
--- branches/unordered/dev/boost/unordered_map.hpp	(original)
+++ branches/unordered/dev/boost/unordered_map.hpp	2008-01-13 15:45:37 EST (Sun, 13 Jan 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>
 
 namespace boost
 {
@@ -327,6 +327,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>
@@ -624,6 +639,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/dev/boost/unordered_set.hpp
==============================================================================
--- branches/unordered/dev/boost/unordered_set.hpp	(original)
+++ branches/unordered/dev/boost/unordered_set.hpp	2008-01-13 15:45:37 EST (Sun, 13 Jan 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>
 
 namespace boost
 {
@@ -297,6 +297,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>
@@ -579,6 +594,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/dev/libs/unordered/doc/ref.xml
==============================================================================
--- branches/unordered/dev/libs/unordered/doc/ref.xml	(original)
+++ branches/unordered/dev/libs/unordered/doc/ref.xml	2008-01-13 15:45:37 EST (Sun, 13 Jan 2008)
@@ -594,6 +594,71 @@
               </throws>
             </method>
           </method-group>
+          <free-function-group name="Equality Comparisons">
+            <function name="operator==">
+              <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&lt;Value, Hash, Pred, Alloc&gt; const&amp;</paramtype>
+              </parameter>
+              <parameter name="y">
+                <paramtype>unordered_set&lt;Value, Hash, Pred, Alloc&gt; const&amp;</paramtype>
+              </parameter>
+              <type>bool</type>
+              <notes>
+                <para>This is a boost extension.</para>
+              </notes>
+            </function>
+            <function name="operator!=">
+              <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&lt;Value, Hash, Pred, Alloc&gt; const&amp;</paramtype>
+              </parameter>
+              <parameter name="y">
+                <paramtype>unordered_set&lt;Value, Hash, Pred, Alloc&gt; const&amp;</paramtype>
+              </parameter>
+              <type>bool</type>
+              <notes>
+                <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&lt;Value, Hash, Pred, Alloc&gt; const&amp;</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">
               <template>
@@ -1208,6 +1273,71 @@
               </throws>
             </method>
           </method-group>
+          <free-function-group name="Equality Comparisons">
+            <function name="operator==">
+              <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&lt;Value, Hash, Pred, Alloc&gt; const&amp;</paramtype>
+              </parameter>
+              <parameter name="y">
+                <paramtype>unordered_multiset&lt;Value, Hash, Pred, Alloc&gt; const&amp;</paramtype>
+              </parameter>
+              <type>bool</type>
+              <notes>
+                <para>This is a boost extension.</para>
+              </notes>
+            </function>
+            <function name="operator!=">
+              <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&lt;Value, Hash, Pred, Alloc&gt; const&amp;</paramtype>
+              </parameter>
+              <parameter name="y">
+                <paramtype>unordered_multiset&lt;Value, Hash, Pred, Alloc&gt; const&amp;</paramtype>
+              </parameter>
+              <type>bool</type>
+              <notes>
+                <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&lt;Value, Hash, Pred, Alloc&gt; const&amp;</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">
               <template>
@@ -1874,6 +2004,77 @@
               </throws>
             </method>
           </method-group>
+          <free-function-group name="Equality Comparisons">
+            <function name="operator==">
+              <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&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</paramtype>
+              </parameter>
+              <parameter name="y">
+                <paramtype>unordered_map&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</paramtype>
+              </parameter>
+              <type>bool</type>
+              <notes>
+                <para>This is a boost extension.</para>
+              </notes>
+            </function>
+            <function name="operator!=">
+              <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&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</paramtype>
+              </parameter>
+              <parameter name="y">
+                <paramtype>unordered_map&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</paramtype>
+              </parameter>
+              <type>bool</type>
+              <notes>
+                <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&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</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">
               <template>
@@ -2498,6 +2699,77 @@
               </throws>
             </method>
           </method-group>
+          <free-function-group name="Equality Comparisons">
+            <function name="operator==">
+              <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&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</paramtype>
+              </parameter>
+              <parameter name="y">
+                <paramtype>unordered_multimap&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</paramtype>
+              </parameter>
+              <type>bool</type>
+              <notes>
+                <para>This is a boost extension.</para>
+              </notes>
+            </function>
+            <function name="operator!=">
+              <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&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</paramtype>
+              </parameter>
+              <parameter name="y">
+                <paramtype>unordered_multimap&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</paramtype>
+              </parameter>
+              <type>bool</type>
+              <notes>
+                <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&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</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">
               <template>

Modified: branches/unordered/dev/libs/unordered/test/objects/minimal.hpp
==============================================================================
--- branches/unordered/dev/libs/unordered/test/objects/minimal.hpp	(original)
+++ branches/unordered/dev/libs/unordered/test/objects/minimal.hpp	2008-01-13 15:45:37 EST (Sun, 13 Jan 2008)
@@ -22,6 +22,7 @@
 namespace minimal
 {
     class copy_constructible;
+    class copy_constructible_equality_comparable;
     class default_copy_constructible;
     class assignable;
     template <class T> class hash;
@@ -41,6 +42,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/dev/libs/unordered/test/unordered/compile_map.cpp
==============================================================================
--- branches/unordered/dev/libs/unordered/test/unordered/compile_map.cpp	(original)
+++ branches/unordered/dev/libs/unordered/test/unordered/compile_map.cpp	2008-01-13 15:45:37 EST (Sun, 13 Jan 2008)
@@ -42,6 +42,32 @@
     container_test(multimap, value);
 }
 
+void equality_tests() {
+    typedef std::pair<test::minimal::assignable const,
+            test::minimal::copy_constructible_equality_comparable> value_type;
+    value_type value(
+            test::minimal::assignable::create(),
+            test::minimal::copy_constructible_equality_comparable::create());
+
+    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(map, value);
+
+    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(multimap, value);
+}
+
 void test1()
 {
     boost::hash<int> hash;
@@ -124,6 +150,7 @@
 int main()
 {
     test0();
+    equality_tests();
     test1();
     test2();
 

Modified: branches/unordered/dev/libs/unordered/test/unordered/compile_set.cpp
==============================================================================
--- branches/unordered/dev/libs/unordered/test/unordered/compile_set.cpp	(original)
+++ branches/unordered/dev/libs/unordered/test/unordered/compile_set.cpp	2008-01-13 15:45:37 EST (Sun, 13 Jan 2008)
@@ -25,6 +25,7 @@
         test::minimal::allocator<test::minimal::assignable> > set;
 
     container_test(set, assignable);
+    equality_test(set, assignable);
 
     std::cout<<"Test unordered_multiset.\n";
     boost::unordered_multiset<
@@ -34,6 +35,7 @@
         test::minimal::allocator<test::minimal::assignable> > multiset;
 
     container_test(multiset, assignable);
+    equality_test(multiset, assignable);
 }
 
 void test1()

Modified: branches/unordered/dev/libs/unordered/test/unordered/compile_tests.hpp
==============================================================================
--- branches/unordered/dev/libs/unordered/test/unordered/compile_tests.hpp	(original)
+++ branches/unordered/dev/libs/unordered/test/unordered/compile_tests.hpp	2008-01-13 15:45:37 EST (Sun, 13 Jan 2008)
@@ -120,8 +120,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());
@@ -147,6 +145,20 @@
 }
 
 template <class X, class T>
+void equality_test(X& r, T&)
+{
+    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)
 {
     typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;