diff options
Diffstat (limited to '3rdParty/Boost/src/boost/unordered/detail/unique.hpp')
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/unique.hpp | 513 |
1 files changed, 513 insertions, 0 deletions
diff --git a/3rdParty/Boost/src/boost/unordered/detail/unique.hpp b/3rdParty/Boost/src/boost/unordered/detail/unique.hpp new file mode 100644 index 0000000..96fdfee --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/unique.hpp @@ -0,0 +1,513 @@ + +// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. +// Copyright (C) 2005-2010 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) + +#ifndef BOOST_UNORDERED_DETAIL_UNIQUE_HPP_INCLUDED +#define BOOST_UNORDERED_DETAIL_UNIQUE_HPP_INCLUDED + +#include <boost/unordered/detail/table.hpp> +#include <boost/unordered/detail/extract_key.hpp> + +namespace boost { namespace unordered_detail { + + template <class T> + class hash_unique_table : public T::table + { + public: + typedef BOOST_DEDUCED_TYPENAME T::hasher hasher; + typedef BOOST_DEDUCED_TYPENAME T::key_equal key_equal; + typedef BOOST_DEDUCED_TYPENAME T::value_allocator value_allocator; + typedef BOOST_DEDUCED_TYPENAME T::key_type key_type; + typedef BOOST_DEDUCED_TYPENAME T::value_type value_type; + typedef BOOST_DEDUCED_TYPENAME T::table table; + typedef BOOST_DEDUCED_TYPENAME T::node_constructor node_constructor; + + typedef BOOST_DEDUCED_TYPENAME T::node node; + typedef BOOST_DEDUCED_TYPENAME T::node_ptr node_ptr; + typedef BOOST_DEDUCED_TYPENAME T::bucket_ptr bucket_ptr; + typedef BOOST_DEDUCED_TYPENAME T::iterator_base iterator_base; + typedef BOOST_DEDUCED_TYPENAME T::extractor extractor; + + typedef std::pair<iterator_base, bool> emplace_return; + + // Constructors + + hash_unique_table(std::size_t n, hasher const& hf, key_equal const& eq, + value_allocator const& a) + : table(n, hf, eq, a) {} + hash_unique_table(hash_unique_table const& x) + : table(x, x.node_alloc()) {} + hash_unique_table(hash_unique_table const& x, value_allocator const& a) + : table(x, a) {} + hash_unique_table(hash_unique_table& x, move_tag m) + : table(x, m) {} + hash_unique_table(hash_unique_table& x, value_allocator const& a, + move_tag m) + : 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); + +#if defined(BOOST_UNORDERED_STD_FORWARD) + + template<class... Args> + emplace_return emplace(Args&&... args); + template<class... Args> + emplace_return emplace_impl(key_type const& k, Args&&... args); + template<class... Args> + emplace_return emplace_impl(no_key, Args&&... args); + template<class... Args> + emplace_return emplace_empty_impl(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)); + + BOOST_PP_REPEAT_FROM_TO(1, 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 + template <class InputIt> + 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_impl2(node_constructor&, 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> + struct set : public types< + BOOST_DEDUCED_TYPENAME A::value_type, + BOOST_DEDUCED_TYPENAME A::value_type, + H, P, A, + set_extractor<BOOST_DEDUCED_TYPENAME A::value_type>, + ungrouped> + { + typedef hash_unique_table<set<H, P, A> > impl; + typedef hash_table<set<H, P, A> > table; + }; + + template <class K, class H, class P, class A> + struct map : public types< + K, BOOST_DEDUCED_TYPENAME A::value_type, + H, P, A, + map_extractor<K, BOOST_DEDUCED_TYPENAME A::value_type>, + ungrouped> + { + typedef hash_unique_table<map<K, H, P, A> > impl; + typedef hash_table<map<K, H, P, A> > table; + }; + + //////////////////////////////////////////////////////////////////////////// + // Equality + + template <class T> + bool hash_unique_table<T> + ::equals(hash_unique_table<T> const& other) const + { + if(this->size_ != other.size_) return false; + if(!this->size_) return true; + + bucket_ptr end = this->get_bucket(this->bucket_count_); + for(bucket_ptr i = this->cached_begin_bucket_; i != end; ++i) + { + node_ptr it1 = i->next_; + while(BOOST_UNORDERED_BORLAND_BOOL(it1)) + { + node_ptr it2 = other.find_iterator(this->get_key_from_ptr(it1)); + if(!BOOST_UNORDERED_BORLAND_BOOL(it2)) return false; + if(!extractor::compare_mapped( + node::get_value(it1), node::get_value(it2))) + return false; + it1 = it1->next_; + } + } + + 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_impl2( + node_constructor& a, key_type const& k, InputIt i, InputIt j) + { + // 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)) { + // 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); + } + } + + 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 { + // 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. + // + // TODO: Might be worth storing the value_type instead of the key + // here. Could be more efficient if '*i' is expensive. Could be + // less efficient if copying the full value_type is expensive. + insert_range_impl2(a, extractor::extract(*i), i, j); + } 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 |