diff options
Diffstat (limited to '3rdParty/Boost/src/boost/unordered/detail/unique.hpp')
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/unique.hpp | 984 |
1 files changed, 561 insertions, 423 deletions
diff --git a/3rdParty/Boost/src/boost/unordered/detail/unique.hpp b/3rdParty/Boost/src/boost/unordered/detail/unique.hpp index 96fdfee..8805652 100644 --- a/3rdParty/Boost/src/boost/unordered/detail/unique.hpp +++ b/3rdParty/Boost/src/boost/unordered/detail/unique.hpp @@ -1,513 +1,651 @@ // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. -// Copyright (C) 2005-2010 Daniel James +// Copyright (C) 2005-2011 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 +#if defined(_MSC_VER) && (_MSC_VER >= 1020) +# pragma once +#endif + #include <boost/unordered/detail/table.hpp> #include <boost/unordered/detail/extract_key.hpp> +#include <boost/throw_exception.hpp> +#include <stdexcept> + +namespace boost { namespace unordered { namespace detail { -namespace boost { namespace unordered_detail { + template <typename A, typename T> struct unique_node; + template <typename T> struct ptr_node; + template <typename Types> struct table_impl; - template <class T> - class hash_unique_table : public T::table + template <typename A, typename T> + struct unique_node : + boost::unordered::detail::value_base<T> { - 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; + typedef typename ::boost::unordered::detail::rebind_wrap< + A, unique_node<A, T> >::type::pointer link_pointer; - // Constructors + link_pointer next_; + std::size_t hash_; - 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); + unique_node() : + next_(), + hash_(0) + {} - // equals + void init(link_pointer) + { + } - bool equals(hash_unique_table const&) const; + private: + unique_node& operator=(unique_node const&); + }; - node_ptr add_node(node_constructor& a, bucket_ptr bucket); - -#if defined(BOOST_UNORDERED_STD_FORWARD) + template <typename T> + struct ptr_node : + boost::unordered::detail::value_base<T>, + boost::unordered::detail::ptr_bucket + { + typedef boost::unordered::detail::ptr_bucket bucket_base; + typedef ptr_bucket* link_pointer; - 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 + std::size_t hash_; -#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 + ptr_node() : + bucket_base(), + hash_(0) + {} -#endif + void init(link_pointer) + { + } - // 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); + private: + ptr_node& operator=(ptr_node const&); }; - 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; + // If the allocator uses raw pointers use ptr_node + // Otherwise use node. + + template <typename A, typename T, typename NodePtr, typename BucketPtr> + struct pick_node2 + { + typedef boost::unordered::detail::unique_node<A, T> node; + + typedef typename boost::unordered::detail::allocator_traits< + typename boost::unordered::detail::rebind_wrap<A, node>::type + >::pointer node_pointer; + + typedef boost::unordered::detail::bucket<node_pointer> bucket; + typedef node_pointer link_pointer; }; - 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> + template <typename A, typename T> + struct pick_node2<A, T, + boost::unordered::detail::ptr_node<T>*, + boost::unordered::detail::ptr_bucket*> { - typedef hash_unique_table<map<K, H, P, A> > impl; - typedef hash_table<map<K, H, P, A> > table; + typedef boost::unordered::detail::ptr_node<T> node; + typedef boost::unordered::detail::ptr_bucket bucket; + typedef bucket* link_pointer; }; - //////////////////////////////////////////////////////////////////////////// - // Equality + template <typename A, typename T> + struct pick_node + { + typedef boost::unordered::detail::allocator_traits< + typename boost::unordered::detail::rebind_wrap<A, + boost::unordered::detail::ptr_node<T> >::type + > tentative_node_traits; + + typedef boost::unordered::detail::allocator_traits< + typename boost::unordered::detail::rebind_wrap<A, + boost::unordered::detail::ptr_bucket >::type + > tentative_bucket_traits; + + typedef pick_node2<A, T, + typename tentative_node_traits::pointer, + typename tentative_bucket_traits::pointer> pick; + + typedef typename pick::node node; + typedef typename pick::bucket bucket; + typedef typename pick::link_pointer link_pointer; + }; + + template <typename A, typename T, typename H, typename P> + struct set + { + typedef boost::unordered::detail::set<A, T, H, P> types; + + typedef A allocator; + typedef T value_type; + typedef H hasher; + typedef P key_equal; + typedef T key_type; + + typedef boost::unordered::detail::allocator_traits<allocator> traits; + typedef boost::unordered::detail::pick_node<allocator, value_type> pick; + typedef typename pick::node node; + typedef typename pick::bucket bucket; + typedef typename pick::link_pointer link_pointer; + + typedef boost::unordered::detail::table_impl<types> table; + typedef boost::unordered::detail::set_extractor<value_type> extractor; + + typedef boost::unordered::detail::pick_policy::type policy; + }; + + template <typename A, typename K, typename M, typename H, typename P> + struct map + { + typedef boost::unordered::detail::map<A, K, M, H, P> types; + + typedef A allocator; + typedef std::pair<K const, M> value_type; + typedef H hasher; + typedef P key_equal; + typedef K key_type; + + typedef boost::unordered::detail::allocator_traits<allocator> + traits; + typedef boost::unordered::detail::pick_node<allocator, value_type> pick; + typedef typename pick::node node; + typedef typename pick::bucket bucket; + typedef typename pick::link_pointer link_pointer; + + typedef boost::unordered::detail::table_impl<types> table; + typedef boost::unordered::detail::map_extractor<key_type, value_type> + extractor; + + typedef boost::unordered::detail::pick_policy::type policy; + }; - template <class T> - bool hash_unique_table<T> - ::equals(hash_unique_table<T> const& other) const + template <typename Types> + struct table_impl : boost::unordered::detail::table<Types> { - if(this->size_ != other.size_) return false; - if(!this->size_) return true; + typedef boost::unordered::detail::table<Types> table; + typedef typename table::value_type value_type; + typedef typename table::bucket bucket; + typedef typename table::policy policy; + typedef typename table::node_pointer node_pointer; + typedef typename table::node_allocator node_allocator; + typedef typename table::node_allocator_traits node_allocator_traits; + typedef typename table::bucket_pointer bucket_pointer; + typedef typename table::link_pointer link_pointer; + typedef typename table::previous_pointer previous_pointer; + typedef typename table::hasher hasher; + typedef typename table::key_equal key_equal; + typedef typename table::key_type key_type; + typedef typename table::node_constructor node_constructor; + typedef typename table::extractor extractor; + typedef typename table::iterator iterator; + typedef typename table::c_iterator c_iterator; + + typedef std::pair<iterator, bool> emplace_return; + + // Constructors + + table_impl(std::size_t n, + hasher const& hf, + key_equal const& eq, + node_allocator const& a) + : table(n, hf, eq, a) + {} + + table_impl(table_impl const& x) + : table(x, node_allocator_traits:: + select_on_container_copy_construction(x.node_alloc())) + { + this->init(x); + } + + table_impl(table_impl const& x, + node_allocator const& a) + : table(x, a) + { + this->init(x); + } + + table_impl(table_impl& x, + boost::unordered::detail::move_tag m) + : table(x, m) + {} - bucket_ptr end = this->get_bucket(this->bucket_count_); - for(bucket_ptr i = this->cached_begin_bucket_; i != end; ++i) + table_impl(table_impl& x, + node_allocator const& a, + boost::unordered::detail::move_tag m) + : table(x, a, m) { - node_ptr it1 = i->next_; - while(BOOST_UNORDERED_BORLAND_BOOL(it1)) + this->move_init(x); + } + + // Accessors + + template <class Key, class Pred> + iterator find_node_impl( + std::size_t key_hash, + Key const& k, + Pred const& eq) const + { + std::size_t bucket_index = + policy::to_bucket(this->bucket_count_, key_hash); + iterator n = this->begin(bucket_index); + + for (;;) { - 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_; + if (!n.node_) return n; + + std::size_t node_hash = n.node_->hash_; + if (key_hash == node_hash) + { + if (eq(k, this->get_key(*n))) + return n; + } + else + { + if (policy::to_bucket(this->bucket_count_, node_hash) + != bucket_index) + return iterator(); + } + + ++n; } } - return true; - } + std::size_t count(key_type const& k) const + { + return this->find_node(k).node_ ? 1 : 0; + } - //////////////////////////////////////////////////////////////////////////// - // A convenience method for adding nodes. + value_type& at(key_type const& k) const + { + if (this->size_) { + iterator it = this->find_node(k); + if (it.node_) return *it; + } - 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); + boost::throw_exception( + std::out_of_range("Unable to find key in unordered_map.")); } - node_ptr pos = this->find_iterator(bucket, k); + std::pair<iterator, iterator> + equal_range(key_type const& k) const + { + iterator n = this->find_node(k); + iterator n2 = n; + if (n2.node_) ++n2; + return std::make_pair(n, n2); + } + + // equals - if (BOOST_UNORDERED_BORLAND_BOOL(pos)) { - return node::get_value(pos); + bool equals(table_impl const& other) const + { + if(this->size_ != other.size_) return false; + + for(iterator n1 = this->begin(); n1.node_; ++n1) + { + iterator n2 = other.find_matching_node(n1); + +#if !defined(BOOST_UNORDERED_DEPRECATED_EQUALITY) + if (!n2.node_ || *n1 != *n2) + return false; +#else + if (!n2.node_ || !extractor::compare_mapped(*n1, *n2)) + return false; +#endif + } + + return true; + } + + // Emplace/Insert + + inline iterator add_node( + node_constructor& a, + std::size_t key_hash) + { + node_pointer n = a.release(); + n->hash_ = key_hash; + + bucket_pointer b = this->get_bucket( + policy::to_bucket(this->bucket_count_, key_hash)); + + if (!b->next_) + { + previous_pointer start_node = this->get_previous_start(); + + if (start_node->next_) { + this->get_bucket(policy::to_bucket(this->bucket_count_, + static_cast<node_pointer>(start_node->next_)->hash_) + )->next_ = n; + } + + b->next_ = start_node; + n->next_ = start_node->next_; + start_node->next_ = static_cast<link_pointer>(n); + } + else + { + n->next_ = b->next_->next_; + b->next_->next_ = static_cast<link_pointer>(n); + } + + ++this->size_; + return iterator(n); } - else { - // Side effects only in this block. + value_type& operator[](key_type const& k) + { + typedef typename value_type::second_type mapped_type; + + std::size_t key_hash = this->hash(k); + iterator pos = this->find_node(key_hash, k); + + if (pos.node_) return *pos; + // 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); + node_constructor a(this->node_alloc()); + a.construct_with_value(BOOST_UNORDERED_EMPLACE_ARGS3( + boost::unordered::piecewise_construct, + boost::make_tuple(k), + boost::make_tuple())); + + this->reserve_for_insert(this->size_ + 1); + return *add_node(a, key_hash); + } - // 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); +#if defined(BOOST_NO_RVALUE_REFERENCES) +# if defined(BOOST_NO_VARIADIC_TEMPLATES) + emplace_return emplace(boost::unordered::detail::emplace_args1< + boost::unordered::detail::please_ignore_this_overload> const&) + { + BOOST_ASSERT(false); + return emplace_return(this->begin(), false); + } +# else + emplace_return emplace( + boost::unordered::detail::please_ignore_this_overload const&) + { + BOOST_ASSERT(false); + return emplace_return(this->begin(), false); + } +# endif +#endif - // Nothing after this point can throw. + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + emplace_return emplace(BOOST_UNORDERED_EMPLACE_ARGS) + { +#if !defined(BOOST_NO_VARIADIC_TEMPLATES) + return emplace_impl( + extractor::extract(BOOST_UNORDERED_EMPLACE_FORWARD), + BOOST_UNORDERED_EMPLACE_FORWARD); +#else + return emplace_impl( + extractor::extract(args.a0, args.a1), + BOOST_UNORDERED_EMPLACE_FORWARD); +#endif + } - return node::get_value(add_node(a, bucket)); +#if defined(BOOST_NO_VARIADIC_TEMPLATES) + template <typename A0> + emplace_return emplace( + boost::unordered::detail::emplace_args1<A0> const& args) + { + return emplace_impl(extractor::extract(args.a0), args); } - } +#endif - 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 { + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + emplace_return emplace_impl(key_type const& k, + BOOST_UNORDERED_EMPLACE_ARGS) + { + std::size_t key_hash = this->hash(k); + iterator pos = this->find_node(key_hash, k); + + if (pos.node_) return emplace_return(pos, false); + + // Create the node before rehashing in case it throws an + // exception (need strong safety in such a case). + node_constructor a(this->node_alloc()); + a.construct_with_value(BOOST_UNORDERED_EMPLACE_FORWARD); + // 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); + this->reserve_for_insert(this->size_ + 1); + return emplace_return(this->add_node(a, key_hash), true); + } - // Nothing after this point can throw. + emplace_return emplace_impl_with_node(node_constructor& a) + { + key_type const& k = this->get_key(a.value()); + std::size_t key_hash = this->hash(k); + iterator pos = this->find_node(key_hash, k); - return emplace_return( - iterator_base(bucket, add_node(a, bucket)), - true); - } - } + if (pos.node_) return emplace_return(pos, false); -#if defined(BOOST_UNORDERED_STD_FORWARD) + // reserve has basic exception safety if the hash function + // throws, strong otherwise. + this->reserve_for_insert(this->size_ + 1); + return emplace_return(this->add_node(a, key_hash), true); + } - 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); + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + emplace_return emplace_impl(no_key, BOOST_UNORDERED_EMPLACE_ARGS) + { + // Don't have a key, so construct the node first in order + // to be able to lookup the position. + node_constructor a(this->node_alloc()); + a.construct_with_value(BOOST_UNORDERED_EMPLACE_FORWARD); + return emplace_impl_with_node(a); + } - if (BOOST_UNORDERED_BORLAND_BOOL(pos)) { - // Found an existing key, return it (no throw). - return emplace_return(iterator_base(bucket, pos), false); + //////////////////////////////////////////////////////////////////////// + // Insert range methods + // + // if hash function throws, or inserting > 1 element, basic exception + // safety strong otherwise - } else { - // Doesn't already exist, add to bucket. - // Side effects only in this block. + template <class InputIt> + void insert_range(InputIt i, InputIt j) + { + if(i != j) + return insert_range_impl(extractor::extract(*i), i, j); + } - // 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)...); + template <class InputIt> + void insert_range_impl(key_type const& k, InputIt i, InputIt j) + { + node_constructor a(this->node_alloc()); + + insert_range_impl2(a, k, i, j); + + while(++i != j) { + // 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); + } + } - // 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); + template <class InputIt> + void insert_range_impl2(node_constructor& a, key_type const& k, + InputIt i, InputIt j) + { + // No side effects in this initial code + std::size_t key_hash = this->hash(k); + iterator pos = this->find_node(key_hash, k); + + if (!pos.node_) { + a.construct_with_value2(*i); + if(this->size_ + 1 > this->max_load_) + this->reserve_for_insert(this->size_ + + boost::unordered::detail::insert_size(i, j)); + + // Nothing after this point can throw. + this->add_node(a, key_hash); + } + } - // Nothing after this point can throw. + template <class InputIt> + void insert_range_impl(no_key, InputIt i, InputIt j) + { + node_constructor a(this->node_alloc()); - return emplace_return( - iterator_base(bucket, add_node(a, bucket)), - true); + do { + a.construct_with_value2(*i); + emplace_impl_with_node(a); + } while(++i != j); } - } - 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); - } + //////////////////////////////////////////////////////////////////////// + // Erase + // + // no throw -#else + std::size_t erase_key(key_type const& k) + { + if(!this->size_) return 0; -#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 + std::size_t key_hash = this->hash(k); + std::size_t bucket_index = + policy::to_bucket(this->bucket_count_, key_hash); + bucket_pointer this_bucket = this->get_bucket(bucket_index); -#endif + previous_pointer prev = this_bucket->next_; + if (!prev) return 0; -#if defined(BOOST_UNORDERED_STD_FORWARD) + for (;;) + { + if (!prev->next_) return 0; + std::size_t node_hash = + static_cast<node_pointer>(prev->next_)->hash_; + if (policy::to_bucket(this->bucket_count_, node_hash) + != bucket_index) + return 0; + if (node_hash == key_hash && + this->key_eq()(k, this->get_key( + static_cast<node_pointer>(prev->next_)->value()))) + break; + prev = static_cast<previous_pointer>(prev->next_); + } - // Emplace (unique keys) - // (I'm using an overloaded emplace for both 'insert' and 'emplace') + node_pointer pos = static_cast<node_pointer>(prev->next_); + node_pointer end = static_cast<node_pointer>(pos->next_); + prev->next_ = pos->next_; + this->fix_buckets(this_bucket, prev, end); + return this->delete_nodes(c_iterator(pos), c_iterator(end)); + } - // if hash function throws, basic exception safety - // strong otherwise + iterator erase(c_iterator r) + { + BOOST_ASSERT(r.node_); + iterator next(r.node_); + ++next; - 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)...); - } + bucket_pointer this_bucket = this->get_bucket( + policy::to_bucket(this->bucket_count_, r.node_->hash_)); + previous_pointer prev = unlink_node(*this_bucket, r.node_); -#else + this->fix_buckets(this_bucket, prev, next.node_); - 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 + this->delete_node(r); -#endif - - //////////////////////////////////////////////////////////////////////////// - // Insert range methods + return next; + } - 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); + iterator erase_range(c_iterator r1, c_iterator r2) + { + if (r1 == r2) return iterator(r2.node_); - if (!BOOST_UNORDERED_BORLAND_BOOL(pos)) { - // Doesn't already exist, add to bucket. - // Side effects only in this block. + std::size_t bucket_index = + policy::to_bucket(this->bucket_count_, r1.node_->hash_); + previous_pointer prev = unlink_nodes( + *this->get_bucket(bucket_index), r1.node_, r2.node_); + this->fix_buckets_range(bucket_index, prev, r1.node_, r2.node_); + this->delete_nodes(r1, r2); - // Create the node before rehashing in case it throws an - // exception (need strong safety in such a case). - a.construct(*i); + return iterator(r2.node_); + } - // 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); - } + static previous_pointer unlink_node(bucket& b, node_pointer n) + { + return unlink_nodes(b, n, static_cast<node_pointer>(n->next_)); + } - // Nothing after this point can throw. - add_node(a, bucket); + static previous_pointer unlink_nodes(bucket& b, + node_pointer begin, node_pointer end) + { + previous_pointer prev = b.next_; + link_pointer begin_void = static_cast<link_pointer>(begin); + while(prev->next_ != begin_void) + prev = static_cast<previous_pointer>(prev->next_); + prev->next_ = static_cast<link_pointer>(end); + return prev; } - } - 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); + //////////////////////////////////////////////////////////////////////// + // fill_buckets + + template <class NodeCreator> + static void fill_buckets(iterator n, table& dst, + NodeCreator& creator) + { + previous_pointer prev = dst.get_previous_start(); + + while (n.node_) { + node_pointer node = creator.create(*n); + node->hash_ = n.node_->hash_; + prev->next_ = static_cast<link_pointer>(node); + ++dst.size_; + ++n; - if(!this->size_) { - a.construct(*i); - this->emplace_empty_impl_with_node(a, 1); - ++i; - if(i == j) return; + prev = place_in_bucket(dst, prev); + } } - 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); + // strong otherwise exception safety + void rehash_impl(std::size_t num_buckets) + { + BOOST_ASSERT(this->buckets_); - if(!this->size_) { - a.construct(*i); - this->emplace_empty_impl_with_node(a, 1); - ++i; - if(i == j) return; + this->create_buckets(num_buckets); + previous_pointer prev = this->get_previous_start(); + while (prev->next_) + prev = place_in_bucket(*this, prev); } - 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); - } -}} + // Iterate through the nodes placing them in the correct buckets. + // pre: prev->next_ is not null. + static previous_pointer place_in_bucket(table& dst, + previous_pointer prev) + { + node_pointer n = static_cast<node_pointer>(prev->next_); + bucket_pointer b = dst.get_bucket( + table::to_bucket(dst.bucket_count_, n->hash_)); + + if (!b->next_) { + b->next_ = prev; + return static_cast<previous_pointer>(n); + } + else { + prev->next_ = n->next_; + n->next_ = b->next_->next_; + b->next_->next_ = static_cast<link_pointer>(n); + return prev; + } + } + }; +}}} #endif |