Boost logo

Boost-Commit :

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;


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