[Boost-commit] svn:boost r42106 - in sandbox/unordered: boost boost/unordered/detail libs/unordered/doc libs/unordered/test/container libs/unordered/test/objects

From: daniel_james_at_[hidden]
Date: 2007-12-16 12:48:26

Author: danieljames
Date: 2007-12-16 12:48:25 EST (Sun, 16 Dec 2007)
New Revision: 42106
URL: http://svn.boost.org/trac/boost/changeset/42106

Log:
operator== work in progress, undocumented and untested.

Text files modified: 
   sandbox/unordered/boost/unordered/detail/hash_table_impl.hpp      |    64 +++++++++++++                           
   sandbox/unordered/boost/unordered_map.hpp                         |    20 ++++                                    
   sandbox/unordered/boost/unordered_set.hpp                         |    20 ++++                                    
   sandbox/unordered/libs/unordered/doc/ref.xml                      |   192 ++++++++++++++++++++++++++++++++++++++++
   sandbox/unordered/libs/unordered/test/container/compile_tests.hpp |    14 +-                                      
   sandbox/unordered/libs/unordered/test/container/map_compile.cpp   |    32 ++++++                                  
   sandbox/unordered/libs/unordered/test/container/set_compile.cpp   |     2                                         
   sandbox/unordered/libs/unordered/test/objects/minimal.hpp         |    20 ++++                                    
   8 files changed, 357 insertions(+), 7 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 12:48:25 EST (Sun, 16 Dec 2007)
@@ -290,6 +290,11 @@
                     return get_value(node_);
                 }
 
+                value_type* operator->() const
+                {
+                    return &get_value(node_);
+                }
+
                 void increment()
                 {
                     BOOST_ASSERT(node_);
@@ -1862,6 +1867,65 @@
                 }
             }
 
+            //
+            // equals
+            //
+
+private:
+#if BOOST_UNORDERED_HASH_EQUIVALENT
+            inline bool group_equals(local_iterator_base it1,
+                    local_iterator_base it2, type_wrapper<key_type>*) const
+            {
+                return this->group_count(it1) == this->group_count(it2);
+            }
+
+            inline bool group_equals(local_iterator_base it1,
+                    local_iterator_base it2, void*) const
+            {
+                if(!it2.not_finished()) return false;
+                local_iterator_base end1 = it1, end2 = it2;
+                end1.next_group(); end2.next_group();
+                do {
+                    if(it1->second != it2->second) return false;
+                    it1.increment();
+                    it2.increment();
+                } while(it1 != end1 && it2 != end2);
+                return it1 == end1 && it2 == end2;
+            }
+#else
+            inline bool group_equals(local_iterator_base it1,
+                    local_iterator_base it2, type_wrapper<key_type>*) const
+            {
+                return true;
+            }
+
+            inline bool group_equals(local_iterator_base it1,
+                    local_iterator_base it2, void*) const
+            {
+                return it1->second == 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_ + this->bucket_count_; i != j; ++i)
+                {
+                    for(local_iterator_base it(i->next_); it.not_finished(); it.next_group())
+                    {
+                        local_iterator_base other_pos = other.find_iterator(other.extract_key(*it));
+                        if(!other_pos.not_finished() ||
+                            !group_equals(it, other_pos, (type_wrapper<value_type>*)0))
+                            return false;
+                    }
+                }
+
+                return true;
+            }
+
         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 12:48:25 EST (Sun, 16 Dec 2007)
@@ -325,6 +325,16 @@
         {
             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);
+        }
     }; // class template unordered_map
 
     template <class K, class T, class H, class P, class A>
@@ -622,6 +632,16 @@
         {
             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);
+        }
     }; // 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 12:48:25 EST (Sun, 16 Dec 2007)
@@ -295,6 +295,16 @@
         {
             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);
+        }
     }; // class template unordered_set
 
     template <class T, class H, class P, class A>
@@ -577,6 +587,16 @@
         {
             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);
+        }
     }; // 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 12:48:25 EST (Sun, 16 Dec 2007)
@@ -591,6 +591,52 @@
               </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>
+          </free-function-group>
           <free-function-group name="swap">
             <function name="swap">
               <template>
@@ -1202,6 +1248,52 @@
               </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>
+          </free-function-group>
           <free-function-group name="swap">
             <function name="swap">
               <template>
@@ -1864,6 +1956,56 @@
               </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>
+          </free-function-group>
           <free-function-group name="swap">
             <function name="swap">
               <template>
@@ -2485,6 +2627,56 @@
               </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>
+          </free-function-group>
           <free-function-group name="swap">
             <function name="swap">
               <template>

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 12:48:25 EST (Sun, 16 Dec 2007)
@@ -111,6 +111,7 @@
     (&a1)->~X();
 
     X const a_const;
+
     test::check_return_type<iterator>::equals(a.begin());
     test::check_return_type<const_iterator>::equals(a_const.begin());
     test::check_return_type<const_iterator>::equals(a.cbegin());
@@ -119,12 +120,13 @@
     test::check_return_type<const_iterator>::equals(a_const.end());
     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.
+template <class X, class T>
+void equality_test(X& r, T&)
+{
+    X const a = r, b = r;
 
-    a.swap(b);
-    test::check_return_type<X>::equals_ref(r = a);
-    test::check_return_type<size_type>::equals(a.size());
-    test::check_return_type<size_type>::equals(a.max_size());
-    test::check_return_type<bool>::convertible(a.empty());
+    test::check_return_type<bool>::equals(a == b);
+    test::check_return_type<bool>::equals(a != b);
 }

Modified: sandbox/unordered/libs/unordered/test/container/map_compile.cpp
==============================================================================
--- sandbox/unordered/libs/unordered/test/container/map_compile.cpp	(original)
+++ sandbox/unordered/libs/unordered/test/container/map_compile.cpp	2007-12-16 12:48:25 EST (Sun, 16 Dec 2007)
@@ -13,7 +13,7 @@
 #include "../objects/minimal.hpp"
 #include "./compile_tests.hpp"
 
-int main()
+void container_tests()
 {
     typedef std::pair<test::minimal::assignable const,
             test::minimal::copy_constructible> value_type;
@@ -40,6 +40,36 @@
         test::minimal::allocator<value_type> > multimap;
 
     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);
+}
 
+int main() {
+    container_tests();
+    equality_tests();
     return boost::report_errors();
 }

Modified: sandbox/unordered/libs/unordered/test/container/set_compile.cpp
==============================================================================
--- sandbox/unordered/libs/unordered/test/container/set_compile.cpp	(original)
+++ sandbox/unordered/libs/unordered/test/container/set_compile.cpp	2007-12-16 12:48:25 EST (Sun, 16 Dec 2007)
@@ -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);
 
     return boost::report_errors();
 }

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 12:48:25 EST (Sun, 16 Dec 2007)
@@ -18,6 +18,7 @@
 namespace minimal
 {
     class copy_constructible;
+    class copy_constructible_equality_comparable;
     class default_copy_constructible;
     class assignable;
     template <class T> class hash;
@@ -37,6 +38,25 @@
         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;
+    }
+
     class default_copy_constructible
     {
     public: