Boost logo

Boost-Commit :

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:


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