|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r61831 - trunk/boost/unordered/detail
From: daniel_james_at_[hidden]
Date: 2010-05-06 16:13:26
Author: danieljames
Date: 2010-05-06 16:13:25 EDT (Thu, 06 May 2010)
New Revision: 61831
URL: http://svn.boost.org/trac/boost/changeset/61831
Log:
Define several methods inline.
Sun 5.9 was having some issues.
Text files modified:
trunk/boost/unordered/detail/equivalent.hpp | 304 +++++++----------
trunk/boost/unordered/detail/unique.hpp | 661 +++++++++++++++++----------------------
2 files changed, 417 insertions(+), 548 deletions(-)
Modified: trunk/boost/unordered/detail/equivalent.hpp
==============================================================================
--- trunk/boost/unordered/detail/equivalent.hpp (original)
+++ trunk/boost/unordered/detail/equivalent.hpp 2010-05-06 16:13:25 EDT (Thu, 06 May 2010)
@@ -47,41 +47,150 @@
: table(x, a, m) {}
~hash_equivalent_table() {}
- // Insert methods
-
- iterator_base emplace_impl(node_constructor& a);
- void emplace_impl_no_rehash(node_constructor& a);
-
// equals
bool equals(hash_equivalent_table const&) const;
- inline node_ptr add_node(node_constructor& a,
- bucket_ptr bucket, node_ptr pos);
-
-#if defined(BOOST_UNORDERED_STD_FORWARD)
+ ////////////////////////////////////////////////////////////////////////
+ // A convenience method for adding nodes.
- template <class... Args>
- iterator_base emplace(Args&&... args);
+ 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;
+ }
-#else
+ ////////////////////////////////////////////////////////////////////////
+ // Insert methods
-#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \
- template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
- iterator_base emplace(BOOST_UNORDERED_FUNCTION_PARAMS(z, n));
+ 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));
+ }
+#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);
+ }
+
+#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); \
+ }
+
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>
- void insert_for_range(I i, I j, forward_traversal_tag);
+ 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
template <class I>
- void insert_for_range(I i, I j, boost::incrementable_traversal_tag);
+ 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
template <class I>
- void insert_range(I i, I j);
+ 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);
+ }
};
template <class H, class P, class A>
@@ -142,163 +251,6 @@
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/unique.hpp
==============================================================================
--- trunk/boost/unordered/detail/unique.hpp (original)
+++ trunk/boost/unordered/detail/unique.hpp 2010-05-06 16:13:25 EDT (Thu, 06 May 2010)
@@ -48,58 +48,318 @@
: 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;
- node_ptr add_node(node_constructor& a, bucket_ptr bucket);
+ ////////////////////////////////////////////////////////////////////////
+ // 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;
+ }
+ ////////////////////////////////////////////////////////////////////////
+ // 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>
- emplace_return emplace(Args&&... 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);
+ }
+ }
+
template<class... Args>
- emplace_return emplace_impl(key_type const& k, Args&&... 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);
+ }
+
template<class... Args>
- emplace_return emplace_impl(no_key, Args&&... 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
+
template<class... Args>
- emplace_return emplace_empty_impl(Args&&... args);
+ 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
-#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));
+ template <class Arg0>
+ emplace_return emplace(Arg0 const& arg0)
+ {
+ return this->size_ ?
+ emplace_impl(extractor::extract(arg0), arg0) :
+ emplace_empty_impl(arg0);
+ }
- BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+#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_UNORDERED_INSERT_IMPL, _)
#undef BOOST_UNORDERED_INSERT_IMPL
#endif
- // if hash function throws, or inserting > 1 element, basic exception
- // safety strong otherwise
+ ////////////////////////////////////////////////////////////////////////
+ // Insert range methods
+
template <class InputIt>
- void insert_range(InputIt i, InputIt j);
+ 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>
- void insert_range_impl(key_type const&, InputIt i, InputIt j);
+ 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_impl(no_key, InputIt i, InputIt j);
+ void insert_range(InputIt i, InputIt j)
+ {
+ if(i != j)
+ return insert_range_impl(extractor::extract(*i), i, j);
+ }
};
template <class H, class P, class A>
@@ -152,349 +412,6 @@
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
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