|
|
Boost-Commit : |
From: daniel_james_at_[hidden]
Date: 2008-06-23 13:44:55
Author: danieljames
Date: 2008-06-23 13:44:53 EDT (Mon, 23 Jun 2008)
New Revision: 46629
URL: http://svn.boost.org/trac/boost/changeset/46629
Log:
Merge from trunk. Fix some inspect errors, try to avoid instantiating the
equality operators when not required, and some bookkeeping.
................
r42539 | danieljames | 2008-01-06 17:48:11 +0000 (Sun, 06 Jan 2008) | 2 lines
Add the unordered library to the maintainers list.
................
r46579 | danieljames | 2008-06-21 16:32:11 +0100 (Sat, 21 Jun 2008) | 10 lines
Define unordered containers' friend functions outside of the class.
On some compilers, friend functions are being instantiated when the main class
is explicitly instantiated. This is slightly problematic because the equality
functions (which are an extension) put extra requirements on the types used. So
I'm going to try defining the functions outside of the class, in the hope that
they won't get instantiated. If someone wants non-member functions to be
instantiated, I think it's reasonable to expect them to explicitly instantiate
them, especially as compilers don't seem to be consistent about this.
................
r46587 | danieljames | 2008-06-21 20:58:39 +0100 (Sat, 21 Jun 2008) | 8 lines
Get the test to pass when pair's default constructor creates two instances of
the member classes.
With some standard libraries I was getting two copies of the object after
creating a default pair, probably because it was creating an instance for its
default parameter. So only test after creating the pair object - since it isn't
our concern how many instances that creates.
................
r46588 | danieljames | 2008-06-21 21:11:26 +0100 (Sat, 21 Jun 2008) | 1 line
Markup an expected failure for unordered.
................
r46594 | danieljames | 2008-06-21 23:02:15 +0100 (Sat, 21 Jun 2008) | 19 lines
Merge inspect fixes for the unordered library.
Merged revisions 46470-46592 via svnmerge from
https://svn.boost.org/svn/boost/branches/unordered/trunk
................
r46589 | danieljames | 2008-06-21 21:37:42 +0100 (Sat, 21 Jun 2008) | 2 lines
Fix some inspect errors (tabs and missing copyright/license).
................
r46591 | danieljames | 2008-06-21 21:47:51 +0100 (Sat, 21 Jun 2008) | 1 line
Move memory.hpp into the helpers subdirectory.
................
r46592 | danieljames | 2008-06-21 22:08:53 +0100 (Sat, 21 Jun 2008) | 1 line
Prevent inspect errors for unnamed namespaces in some of the test header files.
................
................
r46607 | danieljames | 2008-06-22 14:54:45 +0100 (Sun, 22 Jun 2008) | 9 lines
Extract the hash and equality functions from hash_table_data_*.
As these are extensions and add extra requirements to the container elements,
they shouldn't be part of hash_table_data_* so that they won't get instantiated
if an unordered container is explicitly instantiated.
Merged revisions 46594-46604 via svnmerge from
https://svn.boost.org/svn/boost/branches/unordered/trunk
................
r46608 | danieljames | 2008-06-22 16:00:02 +0100 (Sun, 22 Jun 2008) | 5 lines
Remove the svnmerge integration information for the unordered branch.
Now that the unordered library is moving towards release, the main development
version is in trunk. New features will be developed on a new branch.
................
Added:
branches/release/libs/unordered/test/helpers/memory.hpp
- copied unchanged from r46594, /trunk/libs/unordered/test/helpers/memory.hpp
Removed:
branches/release/libs/unordered/test/objects/memory.hpp
Properties modified:
branches/release/ (props changed)
Text files modified:
branches/release/boost/unordered/detail/hash_table_impl.hpp | 237 +++++++++++++++++++++++----------------
branches/release/boost/unordered_map.hpp | 112 +++++++++++++-----
branches/release/boost/unordered_set.hpp | 110 +++++++++++++-----
branches/release/libs/maintainers.txt | 1
branches/release/libs/unordered/doc/bibliography.xml | 5
branches/release/libs/unordered/examples/hash_functions/fnv-1.hpp | 7 +
branches/release/libs/unordered/test/helpers/count.hpp | 5
branches/release/libs/unordered/test/helpers/equivalent.hpp | 5
branches/release/libs/unordered/test/objects/exception.hpp | 2
branches/release/libs/unordered/test/objects/test.hpp | 7 +
branches/release/libs/unordered/test/unordered/equality_tests.cpp | 186 +++++++++++++++---------------
branches/release/libs/unordered/test/unordered/unnecessary_copy_tests.cpp | 5
branches/release/status/explicit-failures-markup.xml | 25 ++++
13 files changed, 447 insertions(+), 260 deletions(-)
Modified: branches/release/boost/unordered/detail/hash_table_impl.hpp
==============================================================================
--- branches/release/boost/unordered/detail/hash_table_impl.hpp (original)
+++ branches/release/boost/unordered/detail/hash_table_impl.hpp 2008-06-23 13:44:53 EDT (Mon, 23 Jun 2008)
@@ -1493,8 +1493,6 @@
/ static_cast<float>(data_.bucket_manager_.bucket_count());
}
- private:
-
// key extractors
// no throw
@@ -2127,100 +2125,6 @@
}
}
- //
- // 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*)
- {
- 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, link_ptr,
- 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
bool equal(key_type const& k, value_type const& v) const
{
@@ -2255,6 +2159,147 @@
}
};
+ //
+ // Equals - unordered container equality comparison.
+ //
+
+#if BOOST_UNORDERED_EQUIVALENT_KEYS
+ template <typename A, typename KeyType>
+ inline bool group_equals(
+ BOOST_UNORDERED_TABLE_DATA<A>*,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it1,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it2,
+ KeyType*,
+ type_wrapper<KeyType>*)
+ {
+ typedef BOOST_UNORDERED_TABLE_DATA<A> data;
+ return data::group_count(it1) == data::group_count(it2);
+ }
+
+ template <typename A, typename KeyType>
+ inline bool group_equals(
+ BOOST_UNORDERED_TABLE_DATA<A>*,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it1,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it2,
+ KeyType*,
+ void*)
+ {
+ typedef BOOST_UNORDERED_TABLE_DATA<A> data;
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr end1 = data::next_group(it1);
+ typename BOOST_UNORDERED_TABLE_DATA<A>::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
+ template <typename A, typename KeyType>
+ inline bool group_equals(
+ BOOST_UNORDERED_TABLE_DATA<A>*,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr,
+ KeyType*,
+ type_wrapper<KeyType>*)
+ {
+ return true;
+ }
+
+ template <typename A, typename KeyType>
+ inline bool group_equals(
+ BOOST_UNORDERED_TABLE_DATA<A>*,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it1,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it2,
+ KeyType*,
+ void*)
+ {
+ typedef BOOST_UNORDERED_TABLE_DATA<A> data;
+ return data::get_value(it1).second == data::get_value(it2).second;
+ }
+#endif
+
+ template <typename V, typename K, typename H, typename P, typename A>
+ bool equals(BOOST_UNORDERED_TABLE<V, K, H, P, A> const& t1,
+ BOOST_UNORDERED_TABLE<V, K, H, P, A> const& t2)
+ {
+ typedef BOOST_UNORDERED_TABLE_DATA<A> data;
+ typedef typename data::bucket_ptr bucket_ptr;
+ typedef typename data::link_ptr link_ptr;
+
+ if(t1.size() != t2.size()) return false;
+
+ for(bucket_ptr i = t1.data_.cached_begin_bucket_,
+ j = t1.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 = t2.find_iterator(t2.extract_key(data::get_value(it)));
+ if(!BOOST_UNORDERED_BORLAND_BOOL(other_pos) ||
+ !group_equals((data*)0, it, other_pos, (K*)0, (type_wrapper<V>*)0))
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ //
+ // hash_value - unordered container hash function.
+ //
+
+ template <typename V, typename K, typename H, typename P, typename A>
+ std::size_t group_hash(BOOST_UNORDERED_TABLE<V, K, H, P, A> const& t,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it,
+ type_wrapper<K>*)
+ {
+ typedef BOOST_UNORDERED_TABLE_DATA<A> data;
+ std::size_t seed = data::group_count(it);
+ std::size_t hashed_key = t.hash_function()(data::get_value(it));
+ boost::hash_combine(seed, hashed_key);
+ return seed;
+ }
+
+ template <typename V, typename K, typename H, typename P, typename A>
+ std::size_t group_hash(BOOST_UNORDERED_TABLE<V, K, H, P, A> const& t,
+ typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it,
+ void*)
+ {
+ typedef BOOST_UNORDERED_TABLE_DATA<A> data;
+ typedef typename data::link_ptr link_ptr;
+
+ std::size_t seed = t.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;
+ }
+
+ template <typename V, typename K, typename H, typename P, typename A>
+ std::size_t hash_value(BOOST_UNORDERED_TABLE<V, K, H, P, A> const& t)
+ {
+ typedef BOOST_UNORDERED_TABLE_DATA<A> data;
+ typedef typename data::link_ptr link_ptr;
+ typedef typename data::bucket_ptr bucket_ptr;
+
+ std::size_t seed = 0;
+
+ for(bucket_ptr i = t.data_.cached_begin_bucket_,
+ j = t.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(t, it, (type_wrapper<V>*)0);
+ }
+
+ return seed;
+ }
+
// Iterators
template <typename Alloc> class BOOST_UNORDERED_ITERATOR;
Modified: branches/release/boost/unordered_map.hpp
==============================================================================
--- branches/release/boost/unordered_map.hpp (original)
+++ branches/release/boost/unordered_map.hpp 2008-06-23 13:44:53 EDT (Mon, 23 Jun 2008)
@@ -32,6 +32,38 @@
class Hash = hash<Key>,
class Pred = std::equal_to<Key>,
class Alloc = std::allocator<std::pair<const Key, T> > >
+ class unordered_map;
+ template <class K, class T, class H, class P, class A>
+ bool operator==(unordered_map<K, T, H, P, A> const&,
+ unordered_map<K, T, H, P, A> const&);
+ template <class K, class T, class H, class P, class A>
+ bool operator!=(unordered_map<K, T, H, P, A> const&,
+ unordered_map<K, T, H, P, A> const&);
+ template <class K, class T, class H, class P, class A>
+ std::size_t hash_value(unordered_map<K, T, H, P, A> const&);
+ template <class K, class T, class H, class P, class A>
+ void swap(unordered_map<K, T, H, P, A>&,
+ unordered_map<K, T, H, P, A>&);
+
+ template <class Key,
+ class T,
+ class Hash = hash<Key>,
+ class Pred = std::equal_to<Key>,
+ class Alloc = std::allocator<std::pair<const Key, T> > >
+ class unordered_multimap;
+ template <class K, class T, class H, class P, class A>
+ bool operator==(unordered_multimap<K, T, H, P, A> const&,
+ unordered_multimap<K, T, H, P, A> const&);
+ template <class K, class T, class H, class P, class A>
+ bool operator!=(unordered_multimap<K, T, H, P, A> const&,
+ unordered_multimap<K, T, H, P, A> const&);
+ template <class K, class T, class H, class P, class A>
+ std::size_t hash_value(unordered_multimap<K, T, H, P, A> const&);
+ template <class K, class T, class H, class P, class A>
+ void swap(unordered_multimap<K, T, H, P, A>&,
+ unordered_multimap<K, T, H, P, A>&);
+
+ template <class Key, class T, class Hash, class Pred, class Alloc>
class unordered_map
{
typedef boost::unordered_detail::hash_types_unique_keys<
@@ -390,34 +422,39 @@
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&, unordered_map const&);
+ friend bool operator!=<>(unordered_map const&, unordered_map const&);
+ friend std::size_t hash_value<>(unordered_map const&);
+ }; // class template unordered_map
- friend bool operator!=(unordered_map const& m1, unordered_map const& m2)
- {
- return !m1.base.equals(m2.base);
- }
+ template <class K, class T, class H, class P, class A>
+ inline bool operator==(unordered_map<K, T, H, P, A> const& m1,
+ unordered_map<K, T, H, P, A> const& m2)
+ {
+ return boost::unordered_detail::equals(m1.base, 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>
+ inline bool operator!=(unordered_map<K, T, H, P, A> const& m1,
+ unordered_map<K, T, H, P, A> const& m2)
+ {
+ return !boost::unordered_detail::equals(m1.base, m2.base);
+ }
template <class K, class T, class H, class P, class A>
- void swap(unordered_map<K, T, H, P, A> &m1,
+ inline std::size_t hash_value(unordered_map<K, T, H, P, A> const& m)
+ {
+ return boost::unordered_detail::hash_value(m.base);
+ }
+
+ template <class K, class T, class H, class P, class A>
+ inline void swap(unordered_map<K, T, H, P, A> &m1,
unordered_map<K, T, H, P, A> &m2)
{
m1.swap(m2);
}
- template <class Key,
- class T,
- class Hash = hash<Key>,
- class Pred = std::equal_to<Key>,
- class Alloc = std::allocator<std::pair<const Key, T> > >
+ template <class Key, class T, class Hash, class Pred, class Alloc>
class unordered_multimap
{
typedef boost::unordered_detail::hash_types_equivalent_keys<
@@ -759,24 +796,33 @@
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&, unordered_multimap const&);
+ friend bool operator!=<>(unordered_multimap const&, unordered_multimap const&);
+ friend std::size_t hash_value<>(unordered_multimap const&);
+ }; // class template unordered_multimap
- friend bool operator!=(unordered_multimap const& m1, unordered_multimap const& m2)
- {
- return !m1.base.equals(m2.base);
- }
+ template <class K, class T, class H, class P, class A>
+ inline bool operator==(unordered_multimap<K, T, H, P, A> const& m1,
+ unordered_multimap<K, T, H, P, A> const& m2)
+ {
+ return boost::unordered_detail::equals(m1.base, 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>
+ inline bool operator!=(unordered_multimap<K, T, H, P, A> const& m1,
+ unordered_multimap<K, T, H, P, A> const& m2)
+ {
+ return !boost::unordered_detail::equals(m1.base, m2.base);
+ }
+
+ template <class K, class T, class H, class P, class A>
+ inline std::size_t hash_value(unordered_multimap<K, T, H, P, A> const& m)
+ {
+ return boost::unordered_detail::hash_value(m.base);
+ }
template <class K, class T, class H, class P, class A>
- void swap(unordered_multimap<K, T, H, P, A> &m1,
+ inline void swap(unordered_multimap<K, T, H, P, A> &m1,
unordered_multimap<K, T, H, P, A> &m2)
{
m1.swap(m2);
Modified: branches/release/boost/unordered_set.hpp
==============================================================================
--- branches/release/boost/unordered_set.hpp (original)
+++ branches/release/boost/unordered_set.hpp 2008-06-23 13:44:53 EDT (Mon, 23 Jun 2008)
@@ -31,6 +31,37 @@
class Hash = hash<Value>,
class Pred = std::equal_to<Value>,
class Alloc = std::allocator<Value> >
+ class unordered_set;
+ template <class T, class H, class P, class A>
+ bool operator==(unordered_set<T, H, P, A> const&,
+ unordered_set<T, H, P, A> const&);
+ template <class T, class H, class P, class A>
+ bool operator!=(unordered_set<T, H, P, A> const&,
+ unordered_set<T, H, P, A> const&);
+ template <class T, class H, class P, class A>
+ std::size_t hash_value(unordered_set<T, H, P, A> const& m);
+ template <class T, class H, class P, class A>
+ void swap(unordered_set<T, H, P, A> &m1,
+ unordered_set<T, H, P, A> &m2);
+
+ template <class Value,
+ class Hash = hash<Value>,
+ class Pred = std::equal_to<Value>,
+ class Alloc = std::allocator<Value> >
+ class unordered_multiset;
+ template <class T, class H, class P, class A>
+ bool operator==(unordered_multiset<T, H, P, A> const&,
+ unordered_multiset<T, H, P, A> const&);
+ template <class T, class H, class P, class A>
+ bool operator!=(unordered_multiset<T, H, P, A> const&,
+ unordered_multiset<T, H, P, A> const&);
+ template <class T, class H, class P, class A>
+ std::size_t hash_value(unordered_multiset<T, H, P, A> const& m);
+ template <class T, class H, class P, class A>
+ void swap(unordered_multiset<T, H, P, A> &m1,
+ unordered_multiset<T, H, P, A> &m2);
+
+ template <class Value, class Hash, class Pred, class Alloc>
class unordered_set
{
typedef boost::unordered_detail::hash_types_unique_keys<
@@ -361,33 +392,39 @@
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&, unordered_set const&);
+ friend bool operator!=<>(unordered_set const&, unordered_set const&);
+ friend std::size_t hash_value<>(unordered_set const&);
+ }; // class template unordered_set
- friend bool operator!=(unordered_set const& m1, unordered_set const& m2)
- {
- return !m1.base.equals(m2.base);
- }
+ template <class T, class H, class P, class A>
+ inline bool operator==(unordered_set<T, H, P, A> const& m1,
+ unordered_set<T, H, P, A> const& m2)
+ {
+ return boost::unordered_detail::equals(m1.base, 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>
+ inline bool operator!=(unordered_set<T, H, P, A> const& m1,
+ unordered_set<T, H, P, A> const& m2)
+ {
+ return !boost::unordered_detail::equals(m1.base, m2.base);
+ }
template <class T, class H, class P, class A>
- void swap(unordered_set<T, H, P, A> &m1,
+ inline std::size_t hash_value(unordered_set<T, H, P, A> const& m)
+ {
+ return boost::unordered_detail::hash_value(m.base);
+ }
+
+ template <class T, class H, class P, class A>
+ inline void swap(unordered_set<T, H, P, A> &m1,
unordered_set<T, H, P, A> &m2)
{
m1.swap(m2);
}
- template <class Value,
- class Hash = hash<Value>,
- class Pred = std::equal_to<Value>,
- class Alloc = std::allocator<Value> >
+ template <class Value, class Hash, class Pred, class Alloc>
class unordered_multiset
{
typedef boost::unordered_detail::hash_types_equivalent_keys<
@@ -715,24 +752,33 @@
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&, unordered_multiset const&);
+ friend bool operator!=<>(unordered_multiset const&, unordered_multiset const&);
+ friend std::size_t hash_value<>(unordered_multiset const&);
+ }; // class template unordered_multiset
- friend bool operator!=(unordered_multiset const& m1, unordered_multiset const& m2)
- {
- return !m1.base.equals(m2.base);
- }
+ template <class T, class H, class P, class A>
+ inline bool operator==(unordered_multiset<T, H, P, A> const& m1,
+ unordered_multiset<T, H, P, A> const& m2)
+ {
+ return boost::unordered_detail::equals(m1.base, 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>
+ inline bool operator!=(unordered_multiset<T, H, P, A> const& m1,
+ unordered_multiset<T, H, P, A> const& m2)
+ {
+ return !boost::unordered_detail::equals(m1.base, m2.base);
+ }
template <class T, class H, class P, class A>
- void swap(unordered_multiset<T, H, P, A> &m1,
+ inline std::size_t hash_value(unordered_multiset<T, H, P, A> const& m)
+ {
+ return boost::unordered_detail::hash_value(m.base);
+ }
+
+ template <class T, class H, class P, class A>
+ inline void swap(unordered_multiset<T, H, P, A> &m1,
unordered_multiset<T, H, P, A> &m2)
{
m1.swap(m2);
Modified: branches/release/libs/maintainers.txt
==============================================================================
--- branches/release/libs/maintainers.txt (original)
+++ branches/release/libs/maintainers.txt 2008-06-23 13:44:53 EDT (Mon, 23 Jun 2008)
@@ -67,6 +67,7 @@
type_traits John Maddock <john -at- johnmaddock.co.uk>
typeof Arkadiy Vertleyb <vertleyb -at- hotmail.com>, Peder Holt <peder.holt -at- gmail.com>
units Matthias Schabel <boost -at- schabel-family.org>, Steven Watanabe <steven -at- providere-consulting.com>
+unordered Daniel James <daniel_james -at- fmail.co.uk>
utility
utility/enable_if Jaakko Jarvi <jarvi -at- cs.tamu.edu>, Jeremiah Willcock <jewillco -at- osl.iu.edu>
variant Eric Friedman <ericbrandon -at- gmail.com>
Modified: branches/release/libs/unordered/doc/bibliography.xml
==============================================================================
--- branches/release/libs/unordered/doc/bibliography.xml (original)
+++ branches/release/libs/unordered/doc/bibliography.xml 2008-06-23 13:44:53 EDT (Mon, 23 Jun 2008)
@@ -1,3 +1,8 @@
+<!--
+Copyright Daniel James 2008
+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)
+-->
<section id="unordered.bibliography">
<title>Bibliography</title>
<bibliography>
Modified: branches/release/libs/unordered/examples/hash_functions/fnv-1.hpp
==============================================================================
--- branches/release/libs/unordered/examples/hash_functions/fnv-1.hpp (original)
+++ branches/release/libs/unordered/examples/hash_functions/fnv-1.hpp 2008-06-23 13:44:53 EDT (Mon, 23 Jun 2008)
@@ -1,4 +1,9 @@
-// See: http://www.isthe.com/chongo/tech/comp/fnv/
+
+// 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)
+
+// Algorithm from: http://www.isthe.com/chongo/tech/comp/fnv/
#include <string>
Modified: branches/release/libs/unordered/test/helpers/count.hpp
==============================================================================
--- branches/release/libs/unordered/test/helpers/count.hpp (original)
+++ branches/release/libs/unordered/test/helpers/count.hpp 2008-06-23 13:44:53 EDT (Mon, 23 Jun 2008)
@@ -53,6 +53,11 @@
struct globally_counted_object
: counted_object<globally_counted_object> {};
+ // This won't be a problem as I'm only using a single compile unit
+ // in each test (this is actually require by the minimal test
+ // framework).
+ //
+ // boostinspect:nounnamed
namespace {
object_count& global_object_count = globally_counted_object::count_;
}
Modified: branches/release/libs/unordered/test/helpers/equivalent.hpp
==============================================================================
--- branches/release/libs/unordered/test/helpers/equivalent.hpp (original)
+++ branches/release/libs/unordered/test/helpers/equivalent.hpp 2008-06-23 13:44:53 EDT (Mon, 23 Jun 2008)
@@ -44,6 +44,11 @@
}
};
+ // This won't be a problem as I'm only using a single compile unit
+ // in each test (this is actually require by the minimal test
+ // framework).
+ //
+ // boostinspect:nounnamed
namespace {
equivalent_type equivalent;
}
Modified: branches/release/libs/unordered/test/objects/exception.hpp
==============================================================================
--- branches/release/libs/unordered/test/objects/exception.hpp (original)
+++ branches/release/libs/unordered/test/objects/exception.hpp 2008-06-23 13:44:53 EDT (Mon, 23 Jun 2008)
@@ -14,7 +14,7 @@
#include <new>
#include "../helpers/fwd.hpp"
#include "../helpers/allocator.hpp"
-#include "./memory.hpp"
+#include "../helpers/memory.hpp"
namespace test
{
Deleted: branches/release/libs/unordered/test/objects/memory.hpp
==============================================================================
--- branches/release/libs/unordered/test/objects/memory.hpp 2008-06-23 13:44:53 EDT (Mon, 23 Jun 2008)
+++ (empty file)
@@ -1,170 +0,0 @@
-
-// Copyright 2006-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)
-
-#if !defined(BOOST_UNORDERED_TEST_MEMORY_HEADER)
-#define BOOST_UNORDERED_TEST_MEMORY_HEADER
-
-#include <memory>
-#include <map>
-#include <boost/mpl/apply.hpp>
-#include <boost/assert.hpp>
-#include <boost/unordered/detail/allocator_helpers.hpp>
-#include <boost/mpl/aux_/config/eti.hpp>
-#include "../helpers/test.hpp"
-
-namespace test
-{
- namespace detail
- {
- // This annoymous namespace won't cause ODR violations as I won't
- // be linking multiple translation units together. I'll probably
- // move this into a cpp file before a full release, but for now it's
- // the most convenient way.
-
- struct memory_area {
- void const* start;
- void const* end;
-
- memory_area(void const* s, void const* e)
- : start(s), end(e)
- {
- BOOST_ASSERT(start != end);
- }
- };
-
- struct memory_track {
- explicit memory_track(int tag = -1) :
- constructed_(0),
- tag_(tag) {}
-
- int constructed_;
- int tag_;
- };
-
- // This is a bit dodgy as it defines overlapping
- // areas as 'equal', so this isn't a total ordering.
- // But it is for non-overlapping memory regions - which
- // is what'll be stored.
- //
- // All searches will be for areas entirely contained by
- // a member of the set - so it should find the area that contains
- // the region that is searched for.
-
- struct memory_area_compare {
- bool operator()(memory_area const& x, memory_area const& y) const {
- return x.end <= y.start;
- }
- };
-
- template <class Alloc>
- struct allocator_memory_type_gen {
- typedef std::map<memory_area, memory_track, memory_area_compare,
- Alloc> type;
- };
-
-#if defined(BOOST_MPL_CFG_MSVC_ETI_BUG)
- template <>
- struct allocator_memory_type_gen<int> {
- typedef std::map<memory_area, memory_track, memory_area_compare> type;
- };
-#endif
-
- template <class Alloc = std::allocator<int> >
- struct memory_tracker {
- typedef BOOST_DEDUCED_TYPENAME
- boost::unordered_detail::rebind_wrap<Alloc,
- std::pair<memory_area const, memory_track> >::type
- allocator_type;
-
- typedef BOOST_DEDUCED_TYPENAME allocator_memory_type_gen<allocator_type>::type
- allocated_memory_type;
-
- allocated_memory_type allocated_memory;
- unsigned int count_allocators;
- unsigned int count_allocations;
- unsigned int count_constructions;
-
- memory_tracker() :
- count_allocators(0), count_allocations(0),
- count_constructions(0)
- {}
-
- void allocator_ref()
- {
- if(count_allocators == 0) {
- count_allocations = 0;
- count_constructions = 0;
- allocated_memory.clear();
- }
- ++count_allocators;
- }
-
- void allocator_unref()
- {
- BOOST_CHECK(count_allocators > 0);
- if(count_allocators > 0) {
- --count_allocators;
- if(count_allocators == 0) {
- bool no_allocations_left = (count_allocations == 0);
- bool no_constructions_left = (count_constructions == 0);
- bool allocated_memory_empty = allocated_memory.empty();
-
- // Clearing the data before the checks terminate the tests.
- count_allocations = 0;
- count_constructions = 0;
- allocated_memory.clear();
-
- BOOST_CHECK(no_allocations_left);
- BOOST_CHECK(no_constructions_left);
- BOOST_CHECK(allocated_memory_empty);
- }
- }
- }
-
- void track_allocate(void *ptr, std::size_t n, std::size_t size, int tag)
- {
- if(n == 0) {
- BOOST_ERROR("Allocating 0 length array.");
- }
- else {
- ++count_allocations;
- allocated_memory.insert(
- std::pair<memory_area const, memory_track>(
- memory_area(ptr, (char*) ptr + n * size),
- memory_track(tag)));
- }
- }
-
- void track_deallocate(void* ptr, std::size_t n, std::size_t size, int tag)
- {
- BOOST_DEDUCED_TYPENAME allocated_memory_type::iterator pos
- = allocated_memory.find(memory_area(ptr, (char*) ptr + n * size));
- if(pos == allocated_memory.end()) {
- BOOST_ERROR("Deallocating unknown pointer.");
- } else {
- BOOST_CHECK(pos->first.start == ptr);
- BOOST_CHECK(pos->first.end == (char*) ptr + n * size);
- BOOST_CHECK(pos->second.tag_ == tag);
- allocated_memory.erase(pos);
- }
- BOOST_CHECK(count_allocations > 0);
- if(count_allocations > 0) --count_allocations;
- }
-
- void track_construct(void* /*ptr*/, std::size_t /*size*/, int /*tag*/)
- {
- ++count_constructions;
- }
-
- void track_destroy(void* /*ptr*/, std::size_t /*size*/, int /*tag*/)
- {
- BOOST_CHECK(count_constructions > 0);
- if(count_constructions > 0) --count_constructions;
- }
- };
- }
-}
-
-#endif
Modified: branches/release/libs/unordered/test/objects/test.hpp
==============================================================================
--- branches/release/libs/unordered/test/objects/test.hpp (original)
+++ branches/release/libs/unordered/test/objects/test.hpp 2008-06-23 13:44:53 EDT (Mon, 23 Jun 2008)
@@ -12,7 +12,7 @@
#include <iostream>
#include "../helpers/fwd.hpp"
#include "../helpers/count.hpp"
-#include "./memory.hpp"
+#include "../helpers/memory.hpp"
#include <map>
namespace test
@@ -156,6 +156,11 @@
namespace detail
{
+ // This won't be a problem as I'm only using a single compile unit
+ // in each test (this is actually require by the minimal test
+ // framework).
+ //
+ // boostinspect:nounnamed
namespace {
test::detail::memory_tracker<std::allocator<int> > tracker;
}
Modified: branches/release/libs/unordered/test/unordered/equality_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/equality_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/equality_tests.cpp 2008-06-23 13:44:53 EDT (Mon, 23 Jun 2008)
@@ -25,118 +25,118 @@
};
#define UNORDERED_EQUALITY_SET_TEST(seq1, op, seq2) \
- do { \
- boost::unordered_set<int, mod_compare, mod_compare> set1, set2; \
- BOOST_PP_SEQ_FOR_EACH(UNORDERED_SET_INSERT, set1, seq1) \
- BOOST_PP_SEQ_FOR_EACH(UNORDERED_SET_INSERT, set2, seq2) \
- BOOST_CHECK(set1 op set2); \
- } while(false)
+ do { \
+ boost::unordered_set<int, mod_compare, mod_compare> set1, set2; \
+ BOOST_PP_SEQ_FOR_EACH(UNORDERED_SET_INSERT, set1, seq1) \
+ BOOST_PP_SEQ_FOR_EACH(UNORDERED_SET_INSERT, set2, seq2) \
+ BOOST_CHECK(set1 op set2); \
+ } while(false)
#define UNORDERED_EQUALITY_MULTISET_TEST(seq1, op, seq2) \
- do { \
- boost::unordered_multiset<int, mod_compare, mod_compare> set1, set2; \
- BOOST_PP_SEQ_FOR_EACH(UNORDERED_SET_INSERT, set1, seq1) \
- BOOST_PP_SEQ_FOR_EACH(UNORDERED_SET_INSERT, set2, seq2) \
- BOOST_CHECK(set1 op set2); \
- } while(false)
+ do { \
+ boost::unordered_multiset<int, mod_compare, mod_compare> set1, set2; \
+ BOOST_PP_SEQ_FOR_EACH(UNORDERED_SET_INSERT, set1, seq1) \
+ BOOST_PP_SEQ_FOR_EACH(UNORDERED_SET_INSERT, set2, seq2) \
+ BOOST_CHECK(set1 op set2); \
+ } while(false)
#define UNORDERED_EQUALITY_MAP_TEST(seq1, op, seq2) \
- do { \
- boost::unordered_map<int, int, mod_compare, mod_compare> map1, map2; \
- BOOST_PP_SEQ_FOR_EACH(UNORDERED_MAP_INSERT, map1, seq1) \
- BOOST_PP_SEQ_FOR_EACH(UNORDERED_MAP_INSERT, map2, seq2) \
- BOOST_CHECK(map1 op map2); \
- } while(false)
+ do { \
+ boost::unordered_map<int, int, mod_compare, mod_compare> map1, map2; \
+ BOOST_PP_SEQ_FOR_EACH(UNORDERED_MAP_INSERT, map1, seq1) \
+ BOOST_PP_SEQ_FOR_EACH(UNORDERED_MAP_INSERT, map2, seq2) \
+ BOOST_CHECK(map1 op map2); \
+ } while(false)
#define UNORDERED_EQUALITY_MULTIMAP_TEST(seq1, op, seq2) \
- do { \
- boost::unordered_multimap<int, int, mod_compare, mod_compare> map1, map2; \
- BOOST_PP_SEQ_FOR_EACH(UNORDERED_MAP_INSERT, map1, seq1) \
- BOOST_PP_SEQ_FOR_EACH(UNORDERED_MAP_INSERT, map2, seq2) \
- BOOST_CHECK(map1 op map2); \
- } while(false)
+ do { \
+ boost::unordered_multimap<int, int, mod_compare, mod_compare> map1, map2; \
+ BOOST_PP_SEQ_FOR_EACH(UNORDERED_MAP_INSERT, map1, seq1) \
+ BOOST_PP_SEQ_FOR_EACH(UNORDERED_MAP_INSERT, map2, seq2) \
+ BOOST_CHECK(map1 op map2); \
+ } while(false)
#define UNORDERED_SET_INSERT(r, set, item) set.insert(item);
#define UNORDERED_MAP_INSERT(r, map, item) \
- map.insert(std::pair<int const, int> BOOST_PP_SEQ_TO_TUPLE(item));
+ map.insert(std::pair<int const, int> BOOST_PP_SEQ_TO_TUPLE(item));
- UNORDERED_AUTO_TEST(equality_size_tests)
- {
- boost::unordered_set<int> x1, x2;
- BOOST_CHECK(x1 == x2);
- BOOST_CHECK(!(x1 != x2));
-
- x1.insert(1);
- BOOST_CHECK(x1 != x2);
- BOOST_CHECK(!(x1 == x2));
- BOOST_CHECK(x2 != x1);
- BOOST_CHECK(!(x2 == x1));
-
- x2.insert(1);
- BOOST_CHECK(x1 == x2);
- BOOST_CHECK(!(x1 != x2));
-
- x2.insert(2);
- BOOST_CHECK(x1 != x2);
- BOOST_CHECK(!(x1 == x2));
- BOOST_CHECK(x2 != x1);
- BOOST_CHECK(!(x2 == x1));
- }
-
- UNORDERED_AUTO_TEST(equality_key_value_tests)
- {
- UNORDERED_EQUALITY_MULTISET_TEST((1), !=, (2));
- UNORDERED_EQUALITY_SET_TEST((2), ==, (2));
- UNORDERED_EQUALITY_MAP_TEST(((1)(1))((2)(1)), !=, ((1)(1))((3)(1)));
- }
-
+ UNORDERED_AUTO_TEST(equality_size_tests)
+ {
+ boost::unordered_set<int> x1, x2;
+ BOOST_CHECK(x1 == x2);
+ BOOST_CHECK(!(x1 != x2));
+
+ x1.insert(1);
+ BOOST_CHECK(x1 != x2);
+ BOOST_CHECK(!(x1 == x2));
+ BOOST_CHECK(x2 != x1);
+ BOOST_CHECK(!(x2 == x1));
+
+ x2.insert(1);
+ BOOST_CHECK(x1 == x2);
+ BOOST_CHECK(!(x1 != x2));
+
+ x2.insert(2);
+ BOOST_CHECK(x1 != x2);
+ BOOST_CHECK(!(x1 == x2));
+ BOOST_CHECK(x2 != x1);
+ BOOST_CHECK(!(x2 == x1));
+ }
+
+ UNORDERED_AUTO_TEST(equality_key_value_tests)
+ {
+ UNORDERED_EQUALITY_MULTISET_TEST((1), !=, (2));
+ UNORDERED_EQUALITY_SET_TEST((2), ==, (2));
+ UNORDERED_EQUALITY_MAP_TEST(((1)(1))((2)(1)), !=, ((1)(1))((3)(1)));
+ }
+
UNORDERED_AUTO_TEST(equality_collision_test)
{
- UNORDERED_EQUALITY_MULTISET_TEST(
- (1), !=, (501));
- UNORDERED_EQUALITY_MULTISET_TEST(
- (1)(251), !=, (1)(501));
- UNORDERED_EQUALITY_MULTIMAP_TEST(
- ((251)(1))((1)(1)), !=, ((501)(1))((1)(1)));
- UNORDERED_EQUALITY_MULTISET_TEST(
- (1)(501), ==, (1)(501));
- UNORDERED_EQUALITY_SET_TEST(
- (1)(501), ==, (501)(1));
- }
-
- UNORDERED_AUTO_TEST(equality_group_size_test)
- {
- UNORDERED_EQUALITY_MULTISET_TEST(
- (10)(20)(20), !=, (10)(10)(20));
- UNORDERED_EQUALITY_MULTIMAP_TEST(
- ((10)(1))((20)(1))((20)(1)), !=,
- ((10)(1))((20)(1))((10)(1)));
- UNORDERED_EQUALITY_MULTIMAP_TEST(
- ((20)(1))((10)(1))((10)(1)), ==,
- ((10)(1))((20)(1))((10)(1)));
+ UNORDERED_EQUALITY_MULTISET_TEST(
+ (1), !=, (501));
+ UNORDERED_EQUALITY_MULTISET_TEST(
+ (1)(251), !=, (1)(501));
+ UNORDERED_EQUALITY_MULTIMAP_TEST(
+ ((251)(1))((1)(1)), !=, ((501)(1))((1)(1)));
+ UNORDERED_EQUALITY_MULTISET_TEST(
+ (1)(501), ==, (1)(501));
+ UNORDERED_EQUALITY_SET_TEST(
+ (1)(501), ==, (501)(1));
+ }
+
+ UNORDERED_AUTO_TEST(equality_group_size_test)
+ {
+ UNORDERED_EQUALITY_MULTISET_TEST(
+ (10)(20)(20), !=, (10)(10)(20));
+ UNORDERED_EQUALITY_MULTIMAP_TEST(
+ ((10)(1))((20)(1))((20)(1)), !=,
+ ((10)(1))((20)(1))((10)(1)));
+ UNORDERED_EQUALITY_MULTIMAP_TEST(
+ ((20)(1))((10)(1))((10)(1)), ==,
+ ((10)(1))((20)(1))((10)(1)));
}
UNORDERED_AUTO_TEST(equality_map_value_test)
{
- UNORDERED_EQUALITY_MAP_TEST(
- ((1)(1)), !=, ((1)(2)));
- UNORDERED_EQUALITY_MAP_TEST(
- ((1)(1)), ==, ((1)(1)));
- UNORDERED_EQUALITY_MULTIMAP_TEST(
- ((1)(1)), !=, ((1)(2)));
- UNORDERED_EQUALITY_MULTIMAP_TEST(
- ((1)(1))((1)(1)), !=, ((1)(1))((1)(2)));
- UNORDERED_EQUALITY_MULTIMAP_TEST(
- ((1)(2))((1)(1)), !=, ((1)(1))((1)(2)));
- }
+ UNORDERED_EQUALITY_MAP_TEST(
+ ((1)(1)), !=, ((1)(2)));
+ UNORDERED_EQUALITY_MAP_TEST(
+ ((1)(1)), ==, ((1)(1)));
+ UNORDERED_EQUALITY_MULTIMAP_TEST(
+ ((1)(1)), !=, ((1)(2)));
+ UNORDERED_EQUALITY_MULTIMAP_TEST(
+ ((1)(1))((1)(1)), !=, ((1)(1))((1)(2)));
+ UNORDERED_EQUALITY_MULTIMAP_TEST(
+ ((1)(2))((1)(1)), !=, ((1)(1))((1)(2)));
+ }
UNORDERED_AUTO_TEST(equality_predicate_test)
{
- UNORDERED_EQUALITY_SET_TEST(
- (1), ==, (1001));
- UNORDERED_EQUALITY_MAP_TEST(
- ((1)(2))((1001)(1)), ==, ((1001)(2))((1)(1)));
- }
+ UNORDERED_EQUALITY_SET_TEST(
+ (1), ==, (1001));
+ UNORDERED_EQUALITY_MAP_TEST(
+ ((1)(2))((1001)(1)), ==, ((1001)(2))((1)(1)));
+ }
}
Modified: branches/release/libs/unordered/test/unordered/unnecessary_copy_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/unnecessary_copy_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/unnecessary_copy_tests.cpp 2008-06-23 13:44:53 EDT (Mon, 23 Jun 2008)
@@ -84,12 +84,11 @@
template <class T>
void unnecessary_copy_insert_test(T*)
{
- reset();
T x;
BOOST_DEDUCED_TYPENAME T::value_type a;
- COPY_COUNT(1);
+ reset();
x.insert(a);
- COPY_COUNT(2);
+ COPY_COUNT(1);
}
boost::unordered_set<count_copies>* set;
Modified: branches/release/status/explicit-failures-markup.xml
==============================================================================
--- branches/release/status/explicit-failures-markup.xml (original)
+++ branches/release/status/explicit-failures-markup.xml 2008-06-23 13:44:53 EDT (Mon, 23 Jun 2008)
@@ -5499,6 +5499,31 @@
</mark-expected-failures>
</library>
+ <!-- unordered -->
+ <library name="unordered">
+ <mark-expected-failures>
+ <test name="move_tests"/>
+ <toolset name="msvc-*"/>
+ <toolset name="intel-win-10.1"/>
+ <toolset name="borland-*"/>
+ <toolset name="sun-*"/>
+ <toolset name="hp_css-*"/>
+ <toolset name="intel-linux-8*"/>
+ <toolset name="intel-linux-9.0*"/>
+ <toolset name="acc-pa_risc"/>
+ <note author="Daniel James">
+ This tests whether the container is successfully moved under
+ different circumstances, and fails if it is copied. Typically if
+ this one fails, it just means that return value optimization was
+ not applied. It might be possible to change the test to make it for
+ the compiler to apply ADL (by not having non-const reference
+ parameters for the function which returns the container). So this
+ is an acceptable failure.
+ </note>
+ </mark-expected-failures>
+ </library>
+
+
<!-- utility/enable_if -->
<library name="utility/enable_if">
<mark-unusable>
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