Subject: [Boost-commit] svn:boost r62117 - trunk/boost/unordered/detail
From: daniel_james_at_[hidden]
Date: 2010-05-21 03:06:36
Author: danieljames
Date: 2010-05-21 03:06:33 EDT (Fri, 21 May 2010)
New Revision: 62117
URL: http://svn.boost.org/trac/boost/changeset/62117
Log:
Revert changes for sun 5.9.
Nobody seems to be running the tests now.
Text files modified:
trunk/boost/unordered/detail/equivalent.hpp | 304 ++++++++++-------
trunk/boost/unordered/detail/fwd.hpp | 24 -
trunk/boost/unordered/detail/node.hpp | 6
trunk/boost/unordered/detail/table.hpp | 17 +
trunk/boost/unordered/detail/unique.hpp | 661 ++++++++++++++++++++++-----------------
5 files changed, 574 insertions(+), 438 deletions(-)
Modified: trunk/boost/unordered/detail/equivalent.hpp
==============================================================================
--- trunk/boost/unordered/detail/equivalent.hpp (original)
+++ trunk/boost/unordered/detail/equivalent.hpp 2010-05-21 03:06:33 EDT (Fri, 21 May 2010)
@@ -47,150 +47,41 @@
: table(x, a, m) {}
~hash_equivalent_table() {}
- // equals
-
- bool equals(hash_equivalent_table const&) const;
+ // Insert methods
- ////////////////////////////////////////////////////////////////////////
- // A convenience method for adding nodes.
+ iterator_base emplace_impl(node_constructor& a);
+ void emplace_impl_no_rehash(node_constructor& a);
- inline node_ptr add_node(
- node_constructor& a, bucket_ptr bucket, node_ptr pos)
- {
- node_ptr n = a.release();
- if(BOOST_UNORDERED_BORLAND_BOOL(pos)) {
- node::add_after_node(n, pos);
- }
- else {
- node::add_to_bucket(n, *bucket);
- if(bucket < this->cached_begin_bucket_)
- this->cached_begin_bucket_ = bucket;
- }
- ++this->size_;
- return n;
- }
+ // equals
- ////////////////////////////////////////////////////////////////////////
- // Insert methods
+ bool equals(hash_equivalent_table const&) const;
- inline iterator_base emplace_impl(node_constructor& a)
- {
- key_type const& k = this->get_key(a.value());
- std::size_t hash_value = this->hash_function()(k);
-
- if(!this->size_) {
- return this->emplace_empty_impl_with_node(a, 1);
- }
- else {
- bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
- node_ptr position = this->find_iterator(bucket, k);
-
- // reserve has basic exception safety if the hash function
- // throws, strong otherwise.
- if(this->reserve_for_insert(this->size_ + 1))
- bucket = this->bucket_ptr_from_hash(hash_value);
-
- return iterator_base(bucket, add_node(a, bucket, position));
- }
- }
-
- inline void emplace_impl_no_rehash(node_constructor& a)
- {
- key_type const& k = this->get_key(a.value());
- bucket_ptr bucket = this->get_bucket(this->bucket_index(k));
- add_node(a, bucket, this->find_iterator(bucket, k));
- }
+ inline node_ptr add_node(node_constructor& a,
+ bucket_ptr bucket, node_ptr pos);
#if defined(BOOST_UNORDERED_STD_FORWARD)
-
- // Emplace (equivalent key containers)
- // (I'm using an overloaded emplace for both 'insert' and 'emplace')
-
- // if hash function throws, basic exception safety
- // strong otherwise
+
template <class... Args>
- iterator_base emplace(Args&&... args)
- {
- // Create the node before rehashing in case it throws an
- // exception (need strong safety in such a case).
- node_constructor a(*this);
- a.construct(std::forward<Args>(args)...);
-
- return emplace_impl(a);
- }
-
+ iterator_base emplace(Args&&... args);
+
#else
-
-#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _) \
- template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
- iterator_base emplace( \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
- { \
- node_constructor a(*this); \
- a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
- return emplace_impl(a); \
- }
-
+
+#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ iterator_base emplace(BOOST_UNORDERED_FUNCTION_PARAMS(z, n));
+
BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
BOOST_UNORDERED_INSERT_IMPL, _)
-
+
#undef BOOST_UNORDERED_INSERT_IMPL
#endif
-
- ////////////////////////////////////////////////////////////////////////////
- // Insert range methods
- // if hash function throws, or inserting > 1 element, basic exception safety
- // strong otherwise
template <class I>
- inline void insert_for_range(I i, I j, forward_traversal_tag)
- {
- if(i == j) return;
- std::size_t distance = unordered_detail::distance(i, j);
- if(distance == 1) {
- emplace(*i);
- }
- else {
- node_constructor a(*this);
-
- // Only require basic exception safety here
- if(this->size_) {
- this->reserve_for_insert(this->size_ + distance);
- }
- else {
- a.construct(*i++);
- this->emplace_empty_impl_with_node(a, distance);
- }
-
- for (; i != j; ++i) {
- a.construct(*i);
- emplace_impl_no_rehash(a);
- }
- }
- }
-
- // if hash function throws, or inserting > 1 element, basic exception
- // safety strong otherwise
+ void insert_for_range(I i, I j, forward_traversal_tag);
template <class I>
- inline void insert_for_range(
- I i, I j, boost::incrementable_traversal_tag)
- {
- node_constructor a(*this);
- for (; i != j; ++i) {
- a.construct(*i);
- emplace_impl(a);
- }
- }
-
- // if hash function throws, or inserting > 1 element, basic exception
- // safety strong otherwise
+ void insert_for_range(I i, I j, boost::incrementable_traversal_tag);
template <class I>
- void insert_range(I i, I j)
- {
- BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type
- iterator_traversal_tag;
- insert_for_range(i, j, iterator_traversal_tag);
- }
+ void insert_range(I i, I j);
};
template <class H, class P, class A>
@@ -251,6 +142,163 @@
return true;
}
+
+ ////////////////////////////////////////////////////////////////////////////
+ // A convenience method for adding nodes.
+
+ template <class T>
+ inline BOOST_DEDUCED_TYPENAME hash_equivalent_table<T>::node_ptr
+ hash_equivalent_table<T>
+ ::add_node(node_constructor& a, bucket_ptr bucket, node_ptr pos)
+ {
+ node_ptr n = a.release();
+ if(BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+ node::add_after_node(n, pos);
+ }
+ else {
+ node::add_to_bucket(n, *bucket);
+ if(bucket < this->cached_begin_bucket_)
+ this->cached_begin_bucket_ = bucket;
+ }
+ ++this->size_;
+ return n;
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Insert methods
+
+ template <class T>
+ inline BOOST_DEDUCED_TYPENAME
+ hash_equivalent_table<T>::iterator_base
+ hash_equivalent_table<T>::emplace_impl(node_constructor& a)
+ {
+ key_type const& k = this->get_key(a.value());
+ std::size_t hash_value = this->hash_function()(k);
+
+ if(!this->size_) {
+ return this->emplace_empty_impl_with_node(a, 1);
+ }
+ else {
+ bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
+ node_ptr position = this->find_iterator(bucket, k);
+
+ // reserve has basic exception safety if the hash function
+ // throws, strong otherwise.
+ if(this->reserve_for_insert(this->size_ + 1))
+ bucket = this->bucket_ptr_from_hash(hash_value);
+
+ return iterator_base(bucket, add_node(a, bucket, position));
+ }
+ }
+
+ template <class T>
+ inline void hash_equivalent_table<T>
+ ::emplace_impl_no_rehash(node_constructor& a)
+ {
+ key_type const& k = this->get_key(a.value());
+ bucket_ptr bucket = this->get_bucket(this->bucket_index(k));
+ add_node(a, bucket, this->find_iterator(bucket, k));
+ }
+
+#if defined(BOOST_UNORDERED_STD_FORWARD)
+
+ // Emplace (equivalent key containers)
+ // (I'm using an overloaded emplace for both 'insert' and 'emplace')
+
+ // if hash function throws, basic exception safety
+ // strong otherwise
+ template <class T>
+ template <class... Args>
+ BOOST_DEDUCED_TYPENAME hash_equivalent_table<T>::iterator_base
+ hash_equivalent_table<T>
+ ::emplace(Args&&... args)
+ {
+ // Create the node before rehashing in case it throws an
+ // exception (need strong safety in such a case).
+ node_constructor a(*this);
+ a.construct(std::forward<Args>(args)...);
+
+ return emplace_impl(a);
+ }
+
+#else
+
+#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _) \
+ template <class T> \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
+ BOOST_DEDUCED_TYPENAME hash_equivalent_table<T>::iterator_base \
+ hash_equivalent_table<T> \
+ ::emplace(BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
+ { \
+ node_constructor a(*this); \
+ a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
+ return emplace_impl(a); \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_INSERT_IMPL, _)
+
+#undef BOOST_UNORDERED_INSERT_IMPL
+#endif
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Insert range methods
+
+ // if hash function throws, or inserting > 1 element, basic exception safety
+ // strong otherwise
+ template <class T>
+ template <class I>
+ inline void hash_equivalent_table<T>
+ ::insert_for_range(I i, I j, forward_traversal_tag)
+ {
+ if(i == j) return;
+ std::size_t distance = unordered_detail::distance(i, j);
+ if(distance == 1) {
+ emplace(*i);
+ }
+ else {
+ node_constructor a(*this);
+
+ // Only require basic exception safety here
+ if(this->size_) {
+ this->reserve_for_insert(this->size_ + distance);
+ }
+ else {
+ a.construct(*i++);
+ this->emplace_empty_impl_with_node(a, distance);
+ }
+
+ for (; i != j; ++i) {
+ a.construct(*i);
+ emplace_impl_no_rehash(a);
+ }
+ }
+ }
+
+ // if hash function throws, or inserting > 1 element, basic exception safety
+ // strong otherwise
+ template <class T>
+ template <class I>
+ inline void hash_equivalent_table<T>
+ ::insert_for_range(I i, I j, boost::incrementable_traversal_tag)
+ {
+ node_constructor a(*this);
+ for (; i != j; ++i) {
+ a.construct(*i);
+ emplace_impl(a);
+ }
+ }
+
+ // if hash function throws, or inserting > 1 element, basic exception safety
+ // strong otherwise
+ template <class T>
+ template <class I>
+ void hash_equivalent_table<T>::insert_range(I i, I j)
+ {
+ BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type
+ iterator_traversal_tag;
+ insert_for_range(i, j, iterator_traversal_tag);
+ }
}}
#endif
Modified: trunk/boost/unordered/detail/fwd.hpp
==============================================================================
--- trunk/boost/unordered/detail/fwd.hpp (original)
+++ trunk/boost/unordered/detail/fwd.hpp 2010-05-21 03:06:33 EDT (Fri, 21 May 2010)
@@ -58,12 +58,6 @@
#endif
-#if BOOST_WORKAROUND(__BORLANDC__, <= 0X0582)
-#define BOOST_UNORDERED_BORLAND_BOOL(x) (bool)(x)
-#else
-#define BOOST_UNORDERED_BORLAND_BOOL(x) x
-#endif
-
namespace boost { namespace unordered_detail {
static const float minimum_max_load_factor = 1e-3f;
@@ -475,25 +469,13 @@
return extractor::extract(node::get_value(n));
}
bool equal(key_type const& k, value_type const& v) const;
-
template <class Key, class Pred>
- inline node_ptr find_iterator(bucket_ptr bucket, Key const& k,
- Pred const& eq) const
- {
- node_ptr it = bucket->next_;
- while (BOOST_UNORDERED_BORLAND_BOOL(it) &&
- !eq(k, get_key(node::get_value(it))))
- {
- it = node::next_group(it);
- }
-
- return it;
- }
-
+ node_ptr find_iterator(bucket_ptr bucket, Key const& k,
+ Pred const&) const;
node_ptr find_iterator(bucket_ptr bucket, key_type const& k) const;
node_ptr find_iterator(key_type const& k) const;
node_ptr* find_for_erase(bucket_ptr bucket, key_type const& k) const;
-
+
// Load methods
std::size_t max_size() const;
Modified: trunk/boost/unordered/detail/node.hpp
==============================================================================
--- trunk/boost/unordered/detail/node.hpp (original)
+++ trunk/boost/unordered/detail/node.hpp 2010-05-21 03:06:33 EDT (Fri, 21 May 2010)
@@ -16,6 +16,12 @@
#include <boost/detail/workaround.hpp>
#include <boost/unordered/detail/fwd.hpp>
+#if BOOST_WORKAROUND(__BORLANDC__, <= 0X0582)
+#define BOOST_UNORDERED_BORLAND_BOOL(x) (bool)(x)
+#else
+#define BOOST_UNORDERED_BORLAND_BOOL(x) x
+#endif
+
namespace boost { namespace unordered_detail {
////////////////////////////////////////////////////////////////////////////
Modified: trunk/boost/unordered/detail/table.hpp
==============================================================================
--- trunk/boost/unordered/detail/table.hpp (original)
+++ trunk/boost/unordered/detail/table.hpp 2010-05-21 03:06:33 EDT (Fri, 21 May 2010)
@@ -31,6 +31,23 @@
// strong exception safety, no side effects
template <class T>
+ template <class Key, class Pred>
+ inline BOOST_DEDUCED_TYPENAME T::node_ptr
+ hash_table<T>::find_iterator(bucket_ptr bucket, Key const& k,
+ Pred const& eq) const
+ {
+ node_ptr it = bucket->next_;
+ while (BOOST_UNORDERED_BORLAND_BOOL(it) &&
+ !eq(k, get_key(node::get_value(it))))
+ {
+ it = node::next_group(it);
+ }
+
+ return it;
+ }
+
+ // strong exception safety, no side effects
+ template <class T>
inline BOOST_DEDUCED_TYPENAME T::node_ptr
hash_table<T>::find_iterator(
bucket_ptr bucket, key_type const& k) const
Modified: trunk/boost/unordered/detail/unique.hpp
==============================================================================
--- trunk/boost/unordered/detail/unique.hpp (original)
+++ trunk/boost/unordered/detail/unique.hpp 2010-05-21 03:06:33 EDT (Fri, 21 May 2010)
@@ -48,318 +48,58 @@
: table(x, a, m) {}
~hash_unique_table() {}
+ // Insert methods
+
+ emplace_return emplace_impl_with_node(node_constructor& a);
+ value_type& operator[](key_type const& k);
+
// equals
bool equals(hash_unique_table const&) const;
- ////////////////////////////////////////////////////////////////////////
- // A convenience method for adding nodes.
-
- inline node_ptr add_node(node_constructor& a, bucket_ptr bucket)
- {
- node_ptr n = a.release();
- node::add_to_bucket(n, *bucket);
- ++this->size_;
- if(bucket < this->cached_begin_bucket_)
- this->cached_begin_bucket_ = bucket;
- return n;
- }
+ node_ptr add_node(node_constructor& a, bucket_ptr bucket);
- ////////////////////////////////////////////////////////////////////////
- // Insert methods
-
- // if hash function throws, basic exception safety
- // strong otherwise
- value_type& operator[](key_type const& k)
- {
- typedef BOOST_DEDUCED_TYPENAME value_type::second_type mapped_type;
-
- std::size_t hash_value = this->hash_function()(k);
- bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
-
- if(!this->buckets_) {
- node_constructor a(*this);
- a.construct_pair(k, (mapped_type*) 0);
- return *this->emplace_empty_impl_with_node(a, 1);
- }
-
- node_ptr pos = this->find_iterator(bucket, k);
-
- if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
- return node::get_value(pos);
- }
- else {
- // Side effects only in this block.
-
- // Create the node before rehashing in case it throws an
- // exception (need strong safety in such a case).
- node_constructor a(*this);
- a.construct_pair(k, (mapped_type*) 0);
-
- // reserve has basic exception safety if the hash function
- // throws, strong otherwise.
- if(this->reserve_for_insert(this->size_ + 1))
- bucket = this->bucket_ptr_from_hash(hash_value);
-
- // Nothing after this point can throw.
-
- return node::get_value(add_node(a, bucket));
- }
- }
-
- inline emplace_return emplace_impl_with_node(node_constructor& a)
- {
- // No side effects in this initial code
- key_type const& k = this->get_key(a.value());
- std::size_t hash_value = this->hash_function()(k);
- bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
- node_ptr pos = this->find_iterator(bucket, k);
-
- if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
- // Found an existing key, return it (no throw).
- return emplace_return(iterator_base(bucket, pos), false);
- } else {
- // reserve has basic exception safety if the hash function
- // throws, strong otherwise.
- if(this->reserve_for_insert(this->size_ + 1))
- bucket = this->bucket_ptr_from_hash(hash_value);
-
- // Nothing after this point can throw.
-
- return emplace_return(
- iterator_base(bucket, add_node(a, bucket)),
- true);
- }
- }
-
#if defined(BOOST_UNORDERED_STD_FORWARD)
template<class... Args>
- inline emplace_return emplace_impl(key_type const& k, Args&&... args)
- {
- // No side effects in this initial code
- std::size_t hash_value = this->hash_function()(k);
- bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
- node_ptr pos = this->find_iterator(bucket, k);
-
- if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
- // Found an existing key, return it (no throw).
- return emplace_return(iterator_base(bucket, pos), false);
-
- } else {
- // Doesn't already exist, add to bucket.
- // Side effects only in this block.
-
- // Create the node before rehashing in case it throws an
- // exception (need strong safety in such a case).
- node_constructor a(*this);
- a.construct(std::forward<Args>(args)...);
-
- // reserve has basic exception safety if the hash function
- // throws, strong otherwise.
- if(this->reserve_for_insert(this->size_ + 1))
- bucket = this->bucket_ptr_from_hash(hash_value);
-
- // Nothing after this point can throw.
-
- return emplace_return(
- iterator_base(bucket, add_node(a, bucket)),
- true);
- }
- }
-
+ emplace_return emplace(Args&&... args);
template<class... Args>
- inline emplace_return emplace_impl(no_key, Args&&... args)
- {
- // Construct the node regardless - in order to get the key.
- // It will be discarded if it isn't used
- node_constructor a(*this);
- a.construct(std::forward<Args>(args)...);
- return emplace_impl_with_node(a);
- }
-
+ emplace_return emplace_impl(key_type const& k, Args&&... args);
template<class... Args>
- inline emplace_return emplace_empty_impl(Args&&... args)
- {
- node_constructor a(*this);
- a.construct(std::forward<Args>(args)...);
- return emplace_return(this->emplace_empty_impl_with_node(a, 1),
- true);
- }
-
-#else
-
-#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _) \
- template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
- inline emplace_return emplace_impl( \
- key_type const& k, BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
- { \
- std::size_t hash_value = this->hash_function()(k); \
- bucket_ptr bucket \
- = this->bucket_ptr_from_hash(hash_value); \
- node_ptr pos = this->find_iterator(bucket, k); \
- \
- if (BOOST_UNORDERED_BORLAND_BOOL(pos)) { \
- return emplace_return(iterator_base(bucket, pos), false); \
- } else { \
- node_constructor a(*this); \
- a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
- \
- if(this->reserve_for_insert(this->size_ + 1)) \
- bucket = this->bucket_ptr_from_hash(hash_value); \
- \
- return emplace_return(iterator_base(bucket, \
- add_node(a, bucket)), true); \
- } \
- } \
- \
- template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
- inline emplace_return emplace_impl( \
- no_key, BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
- { \
- node_constructor a(*this); \
- a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
- return emplace_impl_with_node(a); \
- } \
- \
- template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
- inline emplace_return emplace_empty_impl( \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
- { \
- node_constructor a(*this); \
- a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
- return emplace_return(this->emplace_empty_impl_with_node(a, 1), \
- true); \
- }
-
- BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
- BOOST_UNORDERED_INSERT_IMPL, _)
-
-#undef BOOST_UNORDERED_INSERT_IMPL
-
-#endif
-
-#if defined(BOOST_UNORDERED_STD_FORWARD)
-
- // Emplace (unique keys)
- // (I'm using an overloaded emplace for both 'insert' and 'emplace')
-
- // if hash function throws, basic exception safety
- // strong otherwise
-
+ emplace_return emplace_impl(no_key, Args&&... args);
template<class... Args>
- emplace_return emplace(Args&&... args)
- {
- return this->size_ ?
- emplace_impl(
- extractor::extract(std::forward<Args>(args)...),
- std::forward<Args>(args)...) :
- emplace_empty_impl(std::forward<Args>(args)...);
- }
-
+ emplace_return emplace_empty_impl(Args&&... args);
#else
- template <class Arg0>
- emplace_return emplace(Arg0 const& arg0)
- {
- return this->size_ ?
- emplace_impl(extractor::extract(arg0), arg0) :
- emplace_empty_impl(arg0);
- }
+#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ emplace_return emplace( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ emplace_return emplace_impl(key_type const& k, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ emplace_return emplace_impl(no_key, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ emplace_return emplace_empty_impl( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n));
-#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _) \
- template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
- emplace_return emplace( \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
- { \
- return this->size_ ? \
- emplace_impl(extractor::extract(arg0, arg1), \
- BOOST_UNORDERED_CALL_PARAMS(z, num_params)) : \
- emplace_empty_impl( \
- BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
- }
-
- BOOST_PP_REPEAT_FROM_TO(2, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
BOOST_UNORDERED_INSERT_IMPL, _)
#undef BOOST_UNORDERED_INSERT_IMPL
#endif
- ////////////////////////////////////////////////////////////////////////
- // Insert range methods
-
- template <class InputIt>
- inline void insert_range_impl(key_type const&, InputIt i, InputIt j)
- {
- node_constructor a(*this);
-
- if(!this->size_) {
- a.construct(*i);
- this->emplace_empty_impl_with_node(a, 1);
- ++i;
- if(i == j) return;
- }
-
- do {
- // No side effects in this initial code
- // Note: can't use get_key as '*i' might not be value_type - it
- // could be a pair with first_types as key_type without const or
- // a different second_type.
- key_type const& k = extractor::extract(*i);
- std::size_t hash_value = this->hash_function()(k);
- bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
- node_ptr pos = this->find_iterator(bucket, k);
-
- if (!BOOST_UNORDERED_BORLAND_BOOL(pos)) {
- // Doesn't already exist, add to bucket.
- // Side effects only in this block.
-
- // Create the node before rehashing in case it throws an
- // exception (need strong safety in such a case).
- a.construct(*i);
-
- // reserve has basic exception safety if the hash function
- // throws, strong otherwise.
- if(this->size_ + 1 >= this->max_load_) {
- this->reserve_for_insert(
- this->size_ + insert_size(i, j));
- bucket = this->bucket_ptr_from_hash(hash_value);
- }
-
- // Nothing after this point can throw.
- add_node(a, bucket);
- }
- } while(++i != j);
- }
-
- template <class InputIt>
- inline void insert_range_impl(no_key, InputIt i, InputIt j)
- {
- node_constructor a(*this);
-
- if(!this->size_) {
- a.construct(*i);
- this->emplace_empty_impl_with_node(a, 1);
- ++i;
- if(i == j) return;
- }
-
- do {
- // No side effects in this initial code
- a.construct(*i);
- emplace_impl_with_node(a);
- } while(++i != j);
- }
-
// if hash function throws, or inserting > 1 element, basic exception
// safety strong otherwise
template <class InputIt>
- void insert_range(InputIt i, InputIt j)
- {
- if(i != j)
- return insert_range_impl(extractor::extract(*i), i, j);
- }
+ void insert_range(InputIt i, InputIt j);
+ template <class InputIt>
+ void insert_range_impl(key_type const&, InputIt i, InputIt j);
+ template <class InputIt>
+ void insert_range_impl(no_key, InputIt i, InputIt j);
};
template <class H, class P, class A>
@@ -412,6 +152,349 @@
return true;
}
+
+ ////////////////////////////////////////////////////////////////////////////
+ // A convenience method for adding nodes.
+
+ template <class T>
+ inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::node_ptr
+ hash_unique_table<T>::add_node(node_constructor& a,
+ bucket_ptr bucket)
+ {
+ node_ptr n = a.release();
+ node::add_to_bucket(n, *bucket);
+ ++this->size_;
+ if(bucket < this->cached_begin_bucket_)
+ this->cached_begin_bucket_ = bucket;
+ return n;
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Insert methods
+
+ // if hash function throws, basic exception safety
+ // strong otherwise
+ template <class T>
+ BOOST_DEDUCED_TYPENAME hash_unique_table<T>::value_type&
+ hash_unique_table<T>::operator[](key_type const& k)
+ {
+ typedef BOOST_DEDUCED_TYPENAME value_type::second_type mapped_type;
+
+ std::size_t hash_value = this->hash_function()(k);
+ bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
+
+ if(!this->buckets_) {
+ node_constructor a(*this);
+ a.construct_pair(k, (mapped_type*) 0);
+ return *this->emplace_empty_impl_with_node(a, 1);
+ }
+
+ node_ptr pos = this->find_iterator(bucket, k);
+
+ if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+ return node::get_value(pos);
+ }
+ else {
+ // Side effects only in this block.
+
+ // Create the node before rehashing in case it throws an
+ // exception (need strong safety in such a case).
+ node_constructor a(*this);
+ a.construct_pair(k, (mapped_type*) 0);
+
+ // reserve has basic exception safety if the hash function
+ // throws, strong otherwise.
+ if(this->reserve_for_insert(this->size_ + 1))
+ bucket = this->bucket_ptr_from_hash(hash_value);
+
+ // Nothing after this point can throw.
+
+ return node::get_value(add_node(a, bucket));
+ }
+ }
+
+ template <class T>
+ inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return
+ hash_unique_table<T>::emplace_impl_with_node(node_constructor& a)
+ {
+ // No side effects in this initial code
+ key_type const& k = this->get_key(a.value());
+ std::size_t hash_value = this->hash_function()(k);
+ bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
+ node_ptr pos = this->find_iterator(bucket, k);
+
+ if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+ // Found an existing key, return it (no throw).
+ return emplace_return(iterator_base(bucket, pos), false);
+ } else {
+ // reserve has basic exception safety if the hash function
+ // throws, strong otherwise.
+ if(this->reserve_for_insert(this->size_ + 1))
+ bucket = this->bucket_ptr_from_hash(hash_value);
+
+ // Nothing after this point can throw.
+
+ return emplace_return(
+ iterator_base(bucket, add_node(a, bucket)),
+ true);
+ }
+ }
+
+#if defined(BOOST_UNORDERED_STD_FORWARD)
+
+ template <class T>
+ template<class... Args>
+ inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return
+ hash_unique_table<T>::emplace_impl(key_type const& k,
+ Args&&... args)
+ {
+ // No side effects in this initial code
+ std::size_t hash_value = this->hash_function()(k);
+ bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
+ node_ptr pos = this->find_iterator(bucket, k);
+
+ if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+ // Found an existing key, return it (no throw).
+ return emplace_return(iterator_base(bucket, pos), false);
+
+ } else {
+ // Doesn't already exist, add to bucket.
+ // Side effects only in this block.
+
+ // Create the node before rehashing in case it throws an
+ // exception (need strong safety in such a case).
+ node_constructor a(*this);
+ a.construct(std::forward<Args>(args)...);
+
+ // reserve has basic exception safety if the hash function
+ // throws, strong otherwise.
+ if(this->reserve_for_insert(this->size_ + 1))
+ bucket = this->bucket_ptr_from_hash(hash_value);
+
+ // Nothing after this point can throw.
+
+ return emplace_return(
+ iterator_base(bucket, add_node(a, bucket)),
+ true);
+ }
+ }
+
+ template <class T>
+ template<class... Args>
+ inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return
+ hash_unique_table<T>::emplace_impl(no_key, Args&&... args)
+ {
+ // Construct the node regardless - in order to get the key.
+ // It will be discarded if it isn't used
+ node_constructor a(*this);
+ a.construct(std::forward<Args>(args)...);
+ return emplace_impl_with_node(a);
+ }
+
+ template <class T>
+ template<class... Args>
+ inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return
+ hash_unique_table<T>::emplace_empty_impl(Args&&... args)
+ {
+ node_constructor a(*this);
+ a.construct(std::forward<Args>(args)...);
+ return emplace_return(this->emplace_empty_impl_with_node(a, 1), true);
+ }
+
+#else
+
+#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _) \
+ template <class T> \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
+ inline BOOST_DEDUCED_TYPENAME \
+ hash_unique_table<T>::emplace_return \
+ hash_unique_table<T>::emplace_impl( \
+ key_type const& k, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
+ { \
+ std::size_t hash_value = this->hash_function()(k); \
+ bucket_ptr bucket \
+ = this->bucket_ptr_from_hash(hash_value); \
+ node_ptr pos = this->find_iterator(bucket, k); \
+ \
+ if (BOOST_UNORDERED_BORLAND_BOOL(pos)) { \
+ return emplace_return(iterator_base(bucket, pos), false); \
+ } else { \
+ node_constructor a(*this); \
+ a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
+ \
+ if(this->reserve_for_insert(this->size_ + 1)) \
+ bucket = this->bucket_ptr_from_hash(hash_value); \
+ \
+ return emplace_return(iterator_base(bucket, \
+ add_node(a, bucket)), true); \
+ } \
+ } \
+ \
+ template <class T> \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
+ inline BOOST_DEDUCED_TYPENAME \
+ hash_unique_table<T>::emplace_return \
+ hash_unique_table<T>:: \
+ emplace_impl(no_key, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
+ { \
+ node_constructor a(*this); \
+ a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
+ return emplace_impl_with_node(a); \
+ } \
+ \
+ template <class T> \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
+ inline BOOST_DEDUCED_TYPENAME \
+ hash_unique_table<T>::emplace_return \
+ hash_unique_table<T>:: \
+ emplace_empty_impl( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
+ { \
+ node_constructor a(*this); \
+ a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
+ return emplace_return(this->emplace_empty_impl_with_node(a, 1), true); \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_INSERT_IMPL, _)
+
+#undef BOOST_UNORDERED_INSERT_IMPL
+
+#endif
+
+#if defined(BOOST_UNORDERED_STD_FORWARD)
+
+ // Emplace (unique keys)
+ // (I'm using an overloaded emplace for both 'insert' and 'emplace')
+
+ // if hash function throws, basic exception safety
+ // strong otherwise
+
+ template <class T>
+ template<class... Args>
+ BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return
+ hash_unique_table<T>::emplace(Args&&... args)
+ {
+ return this->size_ ?
+ emplace_impl(
+ extractor::extract(std::forward<Args>(args)...),
+ std::forward<Args>(args)...) :
+ emplace_empty_impl(std::forward<Args>(args)...);
+ }
+
+#else
+
+ template <class T>
+ template <class Arg0>
+ BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return
+ hash_unique_table<T>::emplace(Arg0 const& arg0)
+ {
+ return this->size_ ?
+ emplace_impl(extractor::extract(arg0), arg0) :
+ emplace_empty_impl(arg0);
+ }
+
+#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _) \
+ template <class T> \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
+ BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return \
+ hash_unique_table<T>::emplace( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
+ { \
+ return this->size_ ? \
+ emplace_impl(extractor::extract(arg0, arg1), \
+ BOOST_UNORDERED_CALL_PARAMS(z, num_params)) : \
+ emplace_empty_impl( \
+ BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(2, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_INSERT_IMPL, _)
+
+#undef BOOST_UNORDERED_INSERT_IMPL
+
+#endif
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Insert range methods
+
+ template <class T>
+ template <class InputIt>
+ inline void hash_unique_table<T>::insert_range_impl(
+ key_type const&, InputIt i, InputIt j)
+ {
+ node_constructor a(*this);
+
+ if(!this->size_) {
+ a.construct(*i);
+ this->emplace_empty_impl_with_node(a, 1);
+ ++i;
+ if(i == j) return;
+ }
+
+ do {
+ // No side effects in this initial code
+ // Note: can't use get_key as '*i' might not be value_type - it
+ // could be a pair with first_types as key_type without const or a
+ // different second_type.
+ key_type const& k = extractor::extract(*i);
+ std::size_t hash_value = this->hash_function()(k);
+ bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
+ node_ptr pos = this->find_iterator(bucket, k);
+
+ if (!BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+ // Doesn't already exist, add to bucket.
+ // Side effects only in this block.
+
+ // Create the node before rehashing in case it throws an
+ // exception (need strong safety in such a case).
+ a.construct(*i);
+
+ // reserve has basic exception safety if the hash function
+ // throws, strong otherwise.
+ if(this->size_ + 1 >= this->max_load_) {
+ this->reserve_for_insert(this->size_ + insert_size(i, j));
+ bucket = this->bucket_ptr_from_hash(hash_value);
+ }
+
+ // Nothing after this point can throw.
+ add_node(a, bucket);
+ }
+ } while(++i != j);
+ }
+
+ template <class T>
+ template <class InputIt>
+ inline void hash_unique_table<T>::insert_range_impl(
+ no_key, InputIt i, InputIt j)
+ {
+ node_constructor a(*this);
+
+ if(!this->size_) {
+ a.construct(*i);
+ this->emplace_empty_impl_with_node(a, 1);
+ ++i;
+ if(i == j) return;
+ }
+
+ do {
+ // No side effects in this initial code
+ a.construct(*i);
+ emplace_impl_with_node(a);
+ } while(++i != j);
+ }
+
+ // if hash function throws, or inserting > 1 element, basic exception safety
+ // strong otherwise
+ template <class T>
+ template <class InputIt>
+ void hash_unique_table<T>::insert_range(InputIt i, InputIt j)
+ {
+ if(i != j)
+ return insert_range_impl(extractor::extract(*i), i, j);
+ }
}}
#endif