diff options
Diffstat (limited to '3rdParty/Boost/src/boost/unordered/detail')
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/allocator_helpers.hpp | 111 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/buckets.hpp | 183 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp | 304 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/extract_key.hpp | 148 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/fwd.hpp | 856 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/move.hpp | 243 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/node.hpp | 226 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/table.hpp | 778 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/unique.hpp | 513 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/util.hpp | 331 |
10 files changed, 3693 insertions, 0 deletions
diff --git a/3rdParty/Boost/src/boost/unordered/detail/allocator_helpers.hpp b/3rdParty/Boost/src/boost/unordered/detail/allocator_helpers.hpp new file mode 100644 index 0000000..2c64223 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/allocator_helpers.hpp @@ -0,0 +1,111 @@ + +// Copyright 2005-2009 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) + +// A couple of templates to make using allocators easier. + +#ifndef BOOST_UNORDERED_DETAIL_ALLOCATOR_UTILITIES_HPP_INCLUDED +#define BOOST_UNORDERED_DETAIL_ALLOCATOR_UTILITIES_HPP_INCLUDED + +#if defined(_MSC_VER) && (_MSC_VER >= 1020) +# pragma once +#endif + +#include <boost/config.hpp> + +#if (defined(BOOST_NO_STD_ALLOCATOR) || defined(BOOST_DINKUMWARE_STDLIB)) \ + && !defined(__BORLANDC__) +# define BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES +#endif + +#if defined(BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES) +# include <boost/detail/allocator_utilities.hpp> +#endif + +namespace boost { namespace unordered_detail { + + // rebind_wrap + // + // Rebind allocators. For some problematic libraries, use rebind_to + // from <boost/detail/allocator_utilities.hpp>. + +#if defined(BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES) + template <class Alloc, class T> + struct rebind_wrap : ::boost::detail::allocator::rebind_to<Alloc, T> {}; +#else + template <class Alloc, class T> + struct rebind_wrap + { + typedef BOOST_DEDUCED_TYPENAME + Alloc::BOOST_NESTED_TEMPLATE rebind<T>::other + type; + }; +#endif + + // allocator_array_constructor + // + // Allocate and construct an array in an exception safe manner, and + // clean up if an exception is thrown before the container takes charge + // of it. + + template <class Allocator> + struct allocator_array_constructor + { + typedef BOOST_DEDUCED_TYPENAME Allocator::pointer pointer; + + Allocator& alloc_; + pointer ptr_; + pointer constructed_; + std::size_t length_; + + allocator_array_constructor(Allocator& a) + : alloc_(a), ptr_(), constructed_(), length_(0) + { + constructed_ = pointer(); + ptr_ = pointer(); + } + + ~allocator_array_constructor() { + if (ptr_) { + for(pointer p = ptr_; p != constructed_; ++p) + alloc_.destroy(p); + + alloc_.deallocate(ptr_, length_); + } + } + + template <class V> + void construct(V const& v, std::size_t l) + { + BOOST_ASSERT(!ptr_); + length_ = l; + ptr_ = alloc_.allocate(length_); + pointer end = ptr_ + static_cast<std::ptrdiff_t>(length_); + for(constructed_ = ptr_; constructed_ != end; ++constructed_) + alloc_.construct(constructed_, v); + } + + pointer get() const + { + return ptr_; + } + + pointer release() + { + pointer p(ptr_); + ptr_ = pointer(); + return p; + } + private: + allocator_array_constructor(allocator_array_constructor const&); + allocator_array_constructor& operator=( + allocator_array_constructor const&); + }; +}} + +#if defined(BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES) +# undef BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES +#endif + +#endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp b/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp new file mode 100644 index 0000000..b1dee5c --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp @@ -0,0 +1,183 @@ + +// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. +// Copyright (C) 2005-2009 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_MANAGER_HPP_INCLUDED +#define BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED + +#include <boost/config.hpp> +#include <boost/assert.hpp> +#include <boost/unordered/detail/node.hpp> +#include <boost/unordered/detail/util.hpp> + +namespace boost { namespace unordered_detail { + + //////////////////////////////////////////////////////////////////////////// + // Buckets + + template <class A, class G> + inline std::size_t hash_buckets<A, G>::max_bucket_count() const { + // -1 to account for the sentinel. + return prev_prime(this->bucket_alloc().max_size() - 1); + } + + template <class A, class G> + inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr + hash_buckets<A, G>::get_bucket(std::size_t num) const + { + return buckets_ + static_cast<std::ptrdiff_t>(num); + } + + template <class A, class G> + inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr + hash_buckets<A, G>::bucket_ptr_from_hash(std::size_t hashed) const + { + return get_bucket(hashed % bucket_count_); + } + + template <class A, class G> + std::size_t hash_buckets<A, G>::bucket_size(std::size_t index) const + { + if(!buckets_) return 0; + bucket_ptr ptr = get_bucket(index)->next_; + std::size_t count = 0; + while(ptr) { + ++count; + ptr = ptr->next_; + } + return count; + } + + template <class A, class G> + inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::node_ptr + hash_buckets<A, G>::bucket_begin(std::size_t num) const + { + return buckets_ ? get_bucket(num)->next_ : node_ptr(); + } + + //////////////////////////////////////////////////////////////////////////// + // Delete + + template <class A, class G> + inline void hash_buckets<A, G>::delete_node(node_ptr b) + { + node* raw_ptr = static_cast<node*>(&*b); + boost::unordered_detail::destroy(&raw_ptr->value()); + real_node_ptr n(node_alloc().address(*raw_ptr)); + node_alloc().destroy(n); + node_alloc().deallocate(n, 1); + } + + template <class A, class G> + inline void hash_buckets<A, G>::clear_bucket(bucket_ptr b) + { + node_ptr node_it = b->next_; + b->next_ = node_ptr(); + + while(node_it) { + node_ptr node_to_delete = node_it; + node_it = node_it->next_; + delete_node(node_to_delete); + } + } + + template <class A, class G> + inline void hash_buckets<A, G>::delete_buckets() + { + bucket_ptr end = this->get_bucket(this->bucket_count_); + + for(bucket_ptr begin = this->buckets_; begin != end; ++begin) { + clear_bucket(begin); + } + + // Destroy the buckets (including the sentinel bucket). + ++end; + for(bucket_ptr begin = this->buckets_; begin != end; ++begin) { + bucket_alloc().destroy(begin); + } + + bucket_alloc().deallocate(this->buckets_, this->bucket_count_ + 1); + + this->buckets_ = bucket_ptr(); + } + + template <class A, class G> + inline std::size_t hash_buckets<A, G>::delete_nodes( + node_ptr begin, node_ptr end) + { + std::size_t count = 0; + while(begin != end) { + node_ptr n = begin; + begin = begin->next_; + delete_node(n); + ++count; + } + return count; + } + + //////////////////////////////////////////////////////////////////////////// + // Constructors and Destructors + + template <class A, class G> + inline hash_buckets<A, G>::hash_buckets( + node_allocator const& a, std::size_t bucket_count) + : buckets_(), + bucket_count_(bucket_count), + allocators_(a,a) + { + } + + template <class A, class G> + inline hash_buckets<A, G>::~hash_buckets() + { + if(this->buckets_) { this->delete_buckets(); } + } + + template <class A, class G> + inline void hash_buckets<A, G>::create_buckets() + { + // The array constructor will clean up in the event of an + // exception. + allocator_array_constructor<bucket_allocator> + constructor(bucket_alloc()); + + // Creates an extra bucket to act as a sentinel. + constructor.construct(bucket(), this->bucket_count_ + 1); + + // Set up the sentinel (node_ptr cast) + bucket_ptr sentinel = constructor.get() + + static_cast<std::ptrdiff_t>(this->bucket_count_); + sentinel->next_ = sentinel; + + // Only release the buckets once everything is successfully + // done. + this->buckets_ = constructor.release(); + } + + //////////////////////////////////////////////////////////////////////////// + // Constructors and Destructors + + // no throw + template <class A, class G> + inline void hash_buckets<A, G>::move(hash_buckets& other) + { + BOOST_ASSERT(node_alloc() == other.node_alloc()); + if(this->buckets_) { this->delete_buckets(); } + this->buckets_ = other.buckets_; + this->bucket_count_ = other.bucket_count_; + other.buckets_ = bucket_ptr(); + other.bucket_count_ = 0; + } + + template <class A, class G> + inline void hash_buckets<A, G>::swap(hash_buckets<A, G>& other) + { + BOOST_ASSERT(node_alloc() == other.node_alloc()); + std::swap(buckets_, other.buckets_); + std::swap(bucket_count_, other.bucket_count_); + } +}} + +#endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp b/3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp new file mode 100644 index 0000000..1c497c3 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp @@ -0,0 +1,304 @@ + +// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. +// Copyright (C) 2005-2009 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_EQUIVALENT_HPP_INCLUDED +#define BOOST_UNORDERED_DETAIL_EQUIVALENT_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_equivalent_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; + + // Constructors + + hash_equivalent_table(std::size_t n, + hasher const& hf, key_equal const& eq, value_allocator const& a) + : table(n, hf, eq, a) {} + hash_equivalent_table(hash_equivalent_table const& x) + : table(x, x.node_alloc()) {} + hash_equivalent_table(hash_equivalent_table const& x, + value_allocator const& a) + : table(x, a) {} + hash_equivalent_table(hash_equivalent_table& x, move_tag m) + : table(x, m) {} + hash_equivalent_table(hash_equivalent_table& x, + value_allocator const& a, move_tag m) + : 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) + + template <class... Args> + iterator_base emplace(Args&&... args); + +#else + +#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 + + template <class I> + void insert_for_range(I i, I j, forward_traversal_tag); + template <class I> + void insert_for_range(I i, I j, boost::incrementable_traversal_tag); + template <class I> + void insert_range(I i, I j); + }; + + template <class H, class P, class A> + struct multiset : 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>, + grouped> + { + typedef hash_equivalent_table<multiset<H, P, A> > impl; + typedef hash_table<multiset<H, P, A> > table; + }; + + template <class K, class H, class P, class A> + struct multimap : public types< + K, BOOST_DEDUCED_TYPENAME A::value_type, + H, P, A, + map_extractor<K, BOOST_DEDUCED_TYPENAME A::value_type>, + grouped> + { + typedef hash_equivalent_table<multimap<K, H, P, A> > impl; + typedef hash_table<multimap<K, H, P, A> > table; + }; + + //////////////////////////////////////////////////////////////////////////// + // Equality + + template <class T> + bool hash_equivalent_table<T> + ::equals(hash_equivalent_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; + + node_ptr end1 = node::next_group(it1); + node_ptr end2 = node::next_group(it2); + + do { + if(!extractor::compare_mapped( + node::get_value(it1), node::get_value(it2))) + return false; + it1 = it1->next_; + it2 = it2->next_; + } while(it1 != end1 && it2 != end2); + if(it1 != end1 || it2 != end2) return false; + } + } + + 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 diff --git a/3rdParty/Boost/src/boost/unordered/detail/extract_key.hpp b/3rdParty/Boost/src/boost/unordered/detail/extract_key.hpp new file mode 100644 index 0000000..bedb175 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/extract_key.hpp @@ -0,0 +1,148 @@ + +// Copyright (C) 2005-2009 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_EXTRACT_KEY_HPP_INCLUDED +#define BOOST_UNORDERED_DETAIL_EXTRACT_KEY_HPP_INCLUDED + +#include <boost/config.hpp> +#include <boost/type_traits/remove_const.hpp> +#include <boost/unordered/detail/fwd.hpp> + +namespace boost { +namespace unordered_detail { + + // key extractors + // + // no throw + // + // 'extract_key' is called with the emplace parameters to return a + // key if available or 'no_key' is one isn't and will need to be + // constructed. This could be done by overloading the emplace implementation + // for the different cases, but that's a bit tricky on compilers without + // variadic templates. + + struct no_key { + no_key() {} + template <class T> no_key(T const&) {} + }; + + template <class ValueType> + struct set_extractor + { + typedef ValueType value_type; + typedef ValueType key_type; + + static key_type const& extract(key_type const& v) + { + return v; + } + + static no_key extract() + { + return no_key(); + } + +#if defined(BOOST_UNORDERED_STD_FORWARD) + template <class... Args> + static no_key extract(Args const&...) + { + return no_key(); + } + +#else + template <class Arg> + static no_key extract(Arg const&) + { + return no_key(); + } + + template <class Arg> + static no_key extract(Arg const&, Arg const&) + { + return no_key(); + } +#endif + + static bool compare_mapped(value_type const&, value_type const&) + { + return true; + } + }; + + template <class Key, class ValueType> + struct map_extractor + { + typedef ValueType value_type; + typedef BOOST_DEDUCED_TYPENAME boost::remove_const<Key>::type key_type; + + static key_type const& extract(value_type const& v) + { + return v.first; + } + + static key_type const& extract(key_type const& v) + { + return v; + } + + template <class Second> + static key_type const& extract(std::pair<key_type, Second> const& v) + { + return v.first; + } + + template <class Second> + static key_type const& extract( + std::pair<key_type const, Second> const& v) + { + return v.first; + } + +#if defined(BOOST_UNORDERED_STD_FORWARD) + template <class Arg1, class... Args> + static key_type const& extract(key_type const& k, + Arg1 const&, Args const&...) + { + return k; + } + + template <class... Args> + static no_key extract(Args const&...) + { + return no_key(); + } +#else + template <class Arg1> + static key_type const& extract(key_type const& k, Arg1 const&) + { + return k; + } + + static no_key extract() + { + return no_key(); + } + + template <class Arg> + static no_key extract(Arg const&) + { + return no_key(); + } + + template <class Arg, class Arg1> + static no_key extract(Arg const&, Arg1 const&) + { + return no_key(); + } +#endif + + static bool compare_mapped(value_type const& x, value_type const& y) + { + return x.second == y.second; + } + }; +}} + +#endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp b/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp new file mode 100644 index 0000000..be4d5e1 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp @@ -0,0 +1,856 @@ + +// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. +// Copyright (C) 2005-2009 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) + +// This contains the basic data structure, apart from the actual values. There's +// no construction or deconstruction here. So this only depends on the pointer +// type. + +#ifndef BOOST_UNORDERED_DETAIL_FWD_HPP_INCLUDED +#define BOOST_UNORDERED_DETAIL_FWD_HPP_INCLUDED + +#include <boost/config.hpp> +#include <boost/iterator.hpp> +#include <boost/compressed_pair.hpp> +#include <boost/type_traits/aligned_storage.hpp> +#include <boost/type_traits/alignment_of.hpp> +#include <boost/unordered/detail/allocator_helpers.hpp> +#include <algorithm> + +// This header defines most of the classes used to implement the unordered +// containers. It doesn't include the insert methods as they require a lot +// of preprocessor metaprogramming - they are in insert.hpp + +// Template parameters: +// +// H = Hash Function +// P = Predicate +// A = Value Allocator +// G = Grouped/Ungrouped +// E = Key Extractor + +#if !defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_NO_VARIADIC_TEMPLATES) +# if defined(__SGI_STL_PORT) || defined(_STLPORT_VERSION) + // STLport doesn't have std::forward. +# else +# define BOOST_UNORDERED_STD_FORWARD +# endif +#endif + +#if !defined(BOOST_UNORDERED_EMPLACE_LIMIT) +#define BOOST_UNORDERED_EMPLACE_LIMIT 10 +#endif + +#if !defined(BOOST_UNORDERED_STD_FORWARD) + +#include <boost/preprocessor/repetition/enum_params.hpp> +#include <boost/preprocessor/repetition/enum_binary_params.hpp> +#include <boost/preprocessor/repetition/repeat_from_to.hpp> + +#define BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ + BOOST_PP_ENUM_PARAMS_Z(z, num_params, class Arg) +#define BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \ + BOOST_PP_ENUM_BINARY_PARAMS_Z(z, num_params, Arg, const& arg) +#define BOOST_UNORDERED_CALL_PARAMS(z, num_params) \ + BOOST_PP_ENUM_PARAMS_Z(z, num_params, arg) + +#endif + +namespace boost { namespace unordered_detail { + + static const float minimum_max_load_factor = 1e-3f; + static const std::size_t default_bucket_count = 11; + struct move_tag {}; + + template <class T> class hash_unique_table; + template <class T> class hash_equivalent_table; + template <class Alloc, class Grouped> + class hash_node_constructor; + template <class ValueType> + struct set_extractor; + template <class Key, class ValueType> + struct map_extractor; + struct no_key; + + // Explicitly call a destructor + +#if defined(BOOST_MSVC) +#pragma warning(push) +#pragma warning(disable:4100) // unreferenced formal parameter +#endif + + template <class T> + inline void destroy(T* x) { + x->~T(); + } + +#if defined(BOOST_MSVC) +#pragma warning(pop) +#endif + + // hash_bucket + + template <class A> + class hash_bucket + { + hash_bucket& operator=(hash_bucket const&); + public: + typedef hash_bucket<A> bucket; + typedef BOOST_DEDUCED_TYPENAME + boost::unordered_detail::rebind_wrap<A, bucket>::type + bucket_allocator; + typedef BOOST_DEDUCED_TYPENAME bucket_allocator::pointer bucket_ptr; + typedef bucket_ptr node_ptr; + + node_ptr next_; + + hash_bucket() : next_() {} + }; + + template <class A> + struct ungrouped_node_base : hash_bucket<A> { + typedef hash_bucket<A> bucket; + typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; + typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; + + ungrouped_node_base() : bucket() {} + static inline node_ptr& next_group(node_ptr ptr); + static inline std::size_t group_count(node_ptr ptr); + static inline void add_to_bucket(node_ptr n, bucket& b); + static inline void add_after_node(node_ptr n, node_ptr position); + static void unlink_node(bucket& b, node_ptr n); + static void unlink_nodes(bucket& b, node_ptr begin, node_ptr end); + static void unlink_nodes(bucket& b, node_ptr end); + }; + + template <class A> + struct grouped_node_base : hash_bucket<A> + { + typedef hash_bucket<A> bucket; + typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; + typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; + + node_ptr group_prev_; + + grouped_node_base() : bucket(), group_prev_() {} + static inline node_ptr& next_group(node_ptr ptr); + static inline node_ptr first_in_group(node_ptr n); + static inline std::size_t group_count(node_ptr ptr); + static inline void add_to_bucket(node_ptr n, bucket& b); + static inline void add_after_node(node_ptr n, node_ptr position); + static void unlink_node(bucket& b, node_ptr n); + static void unlink_nodes(bucket& b, node_ptr begin, node_ptr end); + static void unlink_nodes(bucket& b, node_ptr end); + + private: + static inline node_ptr split_group(node_ptr split); + static inline grouped_node_base& get(node_ptr ptr) { + return static_cast<grouped_node_base&>(*ptr); + } + }; + + struct ungrouped + { + template <class A> + struct base { + typedef ungrouped_node_base<A> type; + }; + }; + + struct grouped + { + template <class A> + struct base { + typedef grouped_node_base<A> type; + }; + }; + + template <class ValueType> + struct value_base + { + typedef ValueType value_type; + BOOST_DEDUCED_TYPENAME boost::aligned_storage< + sizeof(value_type), + ::boost::alignment_of<value_type>::value>::type data_; + + void* address() { + return this; + } + value_type& value() { + return *(ValueType*) this; + } + private: + value_base& operator=(value_base const&); + }; + + // Node + + template <class A, class G> + class hash_node : + public G::BOOST_NESTED_TEMPLATE base<A>::type, + public value_base<BOOST_DEDUCED_TYPENAME A::value_type> + { + public: + typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; + typedef BOOST_DEDUCED_TYPENAME hash_bucket<A>::node_ptr node_ptr; + + static value_type& get_value(node_ptr p) { + return static_cast<hash_node&>(*p).value(); + } + private: + hash_node& operator=(hash_node const&); + }; + + // Iterator Base + + template <class A, class G> + class hash_iterator_base + { + public: + typedef A value_allocator; + typedef hash_bucket<A> bucket; + typedef hash_node<A, G> node; + typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; + typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; + typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; + + bucket_ptr bucket_; + node_ptr node_; + + hash_iterator_base() : bucket_(), node_() {} + explicit hash_iterator_base(bucket_ptr b) + : bucket_(b), + node_(b ? b->next_ : node_ptr()) {} + hash_iterator_base(bucket_ptr b, node_ptr n) + : bucket_(b), + node_(n) {} + + bool operator==(hash_iterator_base const& x) const { + return node_ == x.node_; } + bool operator!=(hash_iterator_base const& x) const { + return node_ != x.node_; } + value_type& operator*() const { + return node::get_value(node_); + } + + void increment_bucket(node_ptr n) { + while(!n) { + ++bucket_; + n = bucket_->next_; + } + node_ = bucket_ == n ? node_ptr() : n; + } + + void increment() { + increment_bucket(node_->next_); + } + }; + + // hash_buckets + // + // This is responsible for allocating and deallocating buckets and nodes. + // + // Notes: + // 1. For the sake exception safety the allocators themselves don't allocate + // anything. + // 2. It's the callers responsibility to allocate the buckets before calling + // any of the methods (other than getters and setters). + + template <class A, class G> + class hash_buckets + { + hash_buckets(hash_buckets const&); + hash_buckets& operator=(hash_buckets const&); + public: + // Types + + typedef A value_allocator; + typedef hash_bucket<A> bucket; + typedef hash_iterator_base<A, G> iterator_base; + typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; + typedef BOOST_DEDUCED_TYPENAME iterator_base::node node; + + typedef BOOST_DEDUCED_TYPENAME bucket::bucket_allocator + bucket_allocator; + typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; + typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; + + typedef BOOST_DEDUCED_TYPENAME rebind_wrap<value_allocator, node>::type + node_allocator; + typedef BOOST_DEDUCED_TYPENAME node_allocator::pointer real_node_ptr; + + // Members + + bucket_ptr buckets_; + std::size_t bucket_count_; + boost::compressed_pair<bucket_allocator, node_allocator> allocators_; + + // Data access + + bucket_allocator const& bucket_alloc() const { + return allocators_.first(); } + node_allocator const& node_alloc() const { + return allocators_.second(); } + bucket_allocator& bucket_alloc() { + return allocators_.first(); } + node_allocator& node_alloc() { + return allocators_.second(); } + std::size_t max_bucket_count() const; + + // Constructors + + hash_buckets(node_allocator const& a, std::size_t n); + void create_buckets(); + ~hash_buckets(); + + // no throw + void swap(hash_buckets& other); + void move(hash_buckets& other); + + // For the remaining functions, buckets_ must not be null. + + bucket_ptr get_bucket(std::size_t n) const; + bucket_ptr bucket_ptr_from_hash(std::size_t hashed) const; + std::size_t bucket_size(std::size_t index) const; + node_ptr bucket_begin(std::size_t n) const; + + // Alloc/Dealloc + + void delete_node(node_ptr); + + // + void delete_buckets(); + void clear_bucket(bucket_ptr); + std::size_t delete_nodes(node_ptr begin, node_ptr end); + std::size_t delete_to_bucket_end(node_ptr begin); + }; + + template <class H, class P> class set_hash_functions; + + template <class H, class P> + class hash_buffered_functions + { + friend class set_hash_functions<H, P>; + hash_buffered_functions& operator=(hash_buffered_functions const&); + + typedef boost::compressed_pair<H, P> function_pair; + typedef BOOST_DEDUCED_TYPENAME boost::aligned_storage< + sizeof(function_pair), + ::boost::alignment_of<function_pair>::value>::type aligned_function; + + bool current_; // The currently active functions. + aligned_function funcs_[2]; + + function_pair const& current() const { + return *static_cast<function_pair const*>( + static_cast<void const*>(&funcs_[current_])); + } + + void construct(bool which, H const& hf, P const& eq) + { + new((void*) &funcs_[which]) function_pair(hf, eq); + } + + void construct(bool which, function_pair const& f) + { + new((void*) &funcs_[which]) function_pair(f); + } + + void destroy(bool which) + { + boost::unordered_detail::destroy((function_pair*)(&funcs_[which])); + } + + public: + + hash_buffered_functions(H const& hf, P const& eq) + : current_(false) + { + construct(current_, hf, eq); + } + + hash_buffered_functions(hash_buffered_functions const& bf) + : current_(false) + { + construct(current_, bf.current()); + } + + ~hash_buffered_functions() { + destroy(current_); + } + + H const& hash_function() const { + return current().first(); + } + + P const& key_eq() const { + return current().second(); + } + }; + + template <class H, class P> + class set_hash_functions + { + set_hash_functions(set_hash_functions const&); + set_hash_functions& operator=(set_hash_functions const&); + + typedef hash_buffered_functions<H, P> buffered_functions; + buffered_functions& buffered_functions_; + bool tmp_functions_; + + public: + + set_hash_functions(buffered_functions& f, H const& h, P const& p) + : buffered_functions_(f), + tmp_functions_(!f.current_) + { + f.construct(tmp_functions_, h, p); + } + + set_hash_functions(buffered_functions& f, + buffered_functions const& other) + : buffered_functions_(f), + tmp_functions_(!f.current_) + { + f.construct(tmp_functions_, other.current()); + } + + ~set_hash_functions() + { + buffered_functions_.destroy(tmp_functions_); + } + + void commit() + { + buffered_functions_.current_ = tmp_functions_; + tmp_functions_ = !tmp_functions_; + } + }; + + template <class T> + class hash_table : public T::buckets, public T::buffered_functions + { + hash_table(hash_table const&); + 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::buffered_functions base; + typedef BOOST_DEDUCED_TYPENAME T::buckets buckets; + typedef BOOST_DEDUCED_TYPENAME T::extractor extractor; + typedef BOOST_DEDUCED_TYPENAME T::node_constructor node_constructor; + + typedef BOOST_DEDUCED_TYPENAME T::node node; + typedef BOOST_DEDUCED_TYPENAME T::bucket bucket; + 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::node_allocator node_allocator; + typedef BOOST_DEDUCED_TYPENAME T::iterator_pair iterator_pair; + + // Members + + std::size_t size_; + float mlf_; + // Cached data - invalid if !this->buckets_ + bucket_ptr cached_begin_bucket_; + std::size_t max_load_; + + // Helper methods + + key_type const& get_key(value_type const& v) const { + return extractor::extract(v); + } + key_type const& get_key_from_ptr(node_ptr n) const { + return extractor::extract(node::get_value(n)); + } + bool equal(key_type const& k, value_type const& v) const; + template <class Key, class Pred> + 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; + std::size_t bucket_index(key_type const& k) const; + void max_load_factor(float z); + std::size_t min_buckets_for_size(std::size_t n) const; + std::size_t calculate_max_load(); + + // Constructors + + hash_table(std::size_t n, hasher const& hf, key_equal const& eq, + node_allocator const& a); + hash_table(hash_table const& x, node_allocator const& a); + hash_table(hash_table& x, move_tag m); + hash_table(hash_table& x, node_allocator const& a, move_tag m); + ~hash_table() {} + hash_table& operator=(hash_table const&); + + // Iterators + + iterator_base begin() const { + return this->size_ ? + iterator_base(this->cached_begin_bucket_) : + iterator_base(); + } + iterator_base end() const { + return iterator_base(); + } + + // Swap & Move + + void swap(hash_table& x); + void fast_swap(hash_table& other); + void slow_swap(hash_table& other); + void partial_swap(hash_table& other); + void move(hash_table& x); + + // Reserve and rehash + + void create_for_insert(std::size_t n); + bool reserve_for_insert(std::size_t n); + void rehash(std::size_t n); + void rehash_impl(std::size_t n); + + // Move/copy buckets + + void move_buckets_to(buckets& dst); + void copy_buckets_to(buckets& dst) const; + + // Misc. key methods + + std::size_t count(key_type const& k) const; + iterator_base find(key_type const& k) const; + template <class Key, class Hash, class Pred> + iterator_base find(Key const& k, Hash const& h, Pred const& eq) const; + value_type& at(key_type const& k) const; + iterator_pair equal_range(key_type const& k) const; + + // Erase + // + // no throw + + void clear(); + std::size_t erase_key(key_type const& k); + iterator_base erase_return_iterator(iterator_base r); + void erase(iterator_base r); + std::size_t erase_group(node_ptr* it, bucket_ptr bucket); + iterator_base erase_range(iterator_base r1, iterator_base r2); + + // recompute_begin_bucket + + void init_buckets(); + + // After an erase cached_begin_bucket_ might be left pointing to + // an empty bucket, so this is called to update it + // + // no throw + + void recompute_begin_bucket(bucket_ptr b); + + // This is called when a range has been erased + // + // no throw + + void recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2); + + // no throw + float load_factor() const; + + iterator_base emplace_empty_impl_with_node( + node_constructor&, std::size_t); + }; + + // Iterator Access + +#if !defined(__clang__) + class iterator_access + { + public: + template <class Iterator> + static BOOST_DEDUCED_TYPENAME Iterator::base const& + get(Iterator const& it) + { + return it.base_; + } + }; +#else + class iterator_access + { + public: + // Note: we access Iterator::base here, rather than in the function + // signature to work around a bug in the friend support of an + // early version of clang. + + template <class Iterator> + struct base + { + typedef BOOST_DEDUCED_TYPENAME Iterator::base type; + }; + + template <class Iterator> + static BOOST_DEDUCED_TYPENAME base<Iterator>::type const& + get(Iterator const& it) + { + return it.base_; + } + }; +#endif + + // Iterators + + template <class A, class G> class hash_iterator; + template <class A, class G> class hash_const_iterator; + template <class A, class G> class hash_local_iterator; + template <class A, class G> class hash_const_local_iterator; + + // Local Iterators + // + // all no throw + + template <class A, class G> + class hash_local_iterator + : public boost::iterator < + std::forward_iterator_tag, + BOOST_DEDUCED_TYPENAME A::value_type, + std::ptrdiff_t, + BOOST_DEDUCED_TYPENAME A::pointer, + BOOST_DEDUCED_TYPENAME A::reference> + { + public: + typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; + + private: + typedef hash_buckets<A, G> buckets; + typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr; + typedef BOOST_DEDUCED_TYPENAME buckets::node node; + typedef hash_const_local_iterator<A, G> const_local_iterator; + + friend class hash_const_local_iterator<A, G>; + node_ptr ptr_; + + public: + hash_local_iterator() : ptr_() {} + explicit hash_local_iterator(node_ptr x) : ptr_(x) {} + BOOST_DEDUCED_TYPENAME A::reference operator*() const { + return node::get_value(ptr_); + } + value_type* operator->() const { + return &node::get_value(ptr_); + } + hash_local_iterator& operator++() { + ptr_ = ptr_->next_; return *this; + } + hash_local_iterator operator++(int) { + hash_local_iterator tmp(ptr_); ptr_ = ptr_->next_; return tmp; } + bool operator==(hash_local_iterator x) const { + return ptr_ == x.ptr_; + } + bool operator==(const_local_iterator x) const { + return ptr_ == x.ptr_; + } + bool operator!=(hash_local_iterator x) const { + return ptr_ != x.ptr_; + } + bool operator!=(const_local_iterator x) const { + return ptr_ != x.ptr_; + } + }; + + template <class A, class G> + class hash_const_local_iterator + : public boost::iterator < + std::forward_iterator_tag, + BOOST_DEDUCED_TYPENAME A::value_type, + std::ptrdiff_t, + BOOST_DEDUCED_TYPENAME A::const_pointer, + BOOST_DEDUCED_TYPENAME A::const_reference > + { + public: + typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; + + private: + typedef hash_buckets<A, G> buckets; + typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr ptr; + typedef BOOST_DEDUCED_TYPENAME buckets::node node; + typedef hash_local_iterator<A, G> local_iterator; + friend class hash_local_iterator<A, G>; + ptr ptr_; + + public: + hash_const_local_iterator() : ptr_() {} + explicit hash_const_local_iterator(ptr x) : ptr_(x) {} + hash_const_local_iterator(local_iterator x) : ptr_(x.ptr_) {} + BOOST_DEDUCED_TYPENAME A::const_reference + operator*() const { + return node::get_value(ptr_); + } + value_type const* operator->() const { + return &node::get_value(ptr_); + } + hash_const_local_iterator& operator++() { + ptr_ = ptr_->next_; return *this; + } + hash_const_local_iterator operator++(int) { + hash_const_local_iterator tmp(ptr_); ptr_ = ptr_->next_; return tmp; + } + bool operator==(local_iterator x) const { + return ptr_ == x.ptr_; + } + bool operator==(hash_const_local_iterator x) const { + return ptr_ == x.ptr_; + } + bool operator!=(local_iterator x) const { + return ptr_ != x.ptr_; + } + bool operator!=(hash_const_local_iterator x) const { + return ptr_ != x.ptr_; + } + }; + + // iterators + // + // all no throw + + + template <class A, class G> + class hash_iterator + : public boost::iterator < + std::forward_iterator_tag, + BOOST_DEDUCED_TYPENAME A::value_type, + std::ptrdiff_t, + BOOST_DEDUCED_TYPENAME A::pointer, + BOOST_DEDUCED_TYPENAME A::reference > + { + public: + typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; + + private: + typedef hash_buckets<A, G> buckets; + typedef BOOST_DEDUCED_TYPENAME buckets::node node; + typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base base; + typedef hash_const_iterator<A, G> const_iterator; + friend class hash_const_iterator<A, G>; + base base_; + + public: + + hash_iterator() : base_() {} + explicit hash_iterator(base const& x) : base_(x) {} + BOOST_DEDUCED_TYPENAME A::reference operator*() const { + return *base_; + } + value_type* operator->() const { + return &*base_; + } + hash_iterator& operator++() { + base_.increment(); return *this; + } + hash_iterator operator++(int) { + hash_iterator tmp(base_); base_.increment(); return tmp; + } + bool operator==(hash_iterator const& x) const { + return base_ == x.base_; + } + bool operator==(const_iterator const& x) const { + return base_ == x.base_; + } + bool operator!=(hash_iterator const& x) const { + return base_ != x.base_; + } + bool operator!=(const_iterator const& x) const { + return base_ != x.base_; + } + }; + + template <class A, class G> + class hash_const_iterator + : public boost::iterator < + std::forward_iterator_tag, + BOOST_DEDUCED_TYPENAME A::value_type, + std::ptrdiff_t, + BOOST_DEDUCED_TYPENAME A::const_pointer, + BOOST_DEDUCED_TYPENAME A::const_reference > + { + public: + typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; + + private: + typedef hash_buckets<A, G> buckets; + typedef BOOST_DEDUCED_TYPENAME buckets::node node; + typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base base; + typedef hash_iterator<A, G> iterator; + friend class hash_iterator<A, G>; + friend class iterator_access; + base base_; + + public: + + hash_const_iterator() : base_() {} + explicit hash_const_iterator(base const& x) : base_(x) {} + hash_const_iterator(iterator const& x) : base_(x.base_) {} + BOOST_DEDUCED_TYPENAME A::const_reference operator*() const { + return *base_; + } + value_type const* operator->() const { + return &*base_; + } + hash_const_iterator& operator++() { + base_.increment(); return *this; + } + hash_const_iterator operator++(int) { + hash_const_iterator tmp(base_); base_.increment(); return tmp; + } + bool operator==(iterator const& x) const { + return base_ == x.base_; + } + bool operator==(hash_const_iterator const& x) const { + return base_ == x.base_; + } + bool operator!=(iterator const& x) const { + return base_ != x.base_; + } + bool operator!=(hash_const_iterator const& x) const { + return base_ != x.base_; + } + }; + + // types + + template <class K, class V, class H, class P, class A, class E, class G> + struct types + { + public: + typedef K key_type; + typedef V value_type; + typedef H hasher; + typedef P key_equal; + typedef A value_allocator; + typedef E extractor; + typedef G group_type; + + typedef hash_node_constructor<value_allocator, group_type> + node_constructor; + typedef hash_buckets<value_allocator, group_type> buckets; + typedef hash_buffered_functions<hasher, key_equal> buffered_functions; + + typedef BOOST_DEDUCED_TYPENAME buckets::node node; + typedef BOOST_DEDUCED_TYPENAME buckets::bucket bucket; + typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr; + typedef BOOST_DEDUCED_TYPENAME buckets::bucket_ptr bucket_ptr; + typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base iterator_base; + typedef BOOST_DEDUCED_TYPENAME buckets::node_allocator node_allocator; + + typedef std::pair<iterator_base, iterator_base> iterator_pair; + }; +}} + +#endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/move.hpp b/3rdParty/Boost/src/boost/unordered/detail/move.hpp new file mode 100644 index 0000000..16fd921 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/move.hpp @@ -0,0 +1,243 @@ +/* + Copyright 2005-2007 Adobe Systems Incorporated + + Use, modification and distribution are subject to 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_MOVE_HEADER +#define BOOST_UNORDERED_DETAIL_MOVE_HEADER + +#include <boost/config.hpp> +#include <boost/mpl/bool.hpp> +#include <boost/mpl/and.hpp> +#include <boost/mpl/or.hpp> +#include <boost/mpl/not.hpp> +#include <boost/type_traits/is_convertible.hpp> +#include <boost/type_traits/is_same.hpp> +#include <boost/type_traits/is_class.hpp> +#include <boost/utility/enable_if.hpp> +#include <boost/detail/workaround.hpp> + +/*************************************************************************************************/ + +#if defined(BOOST_NO_SFINAE) +# define BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN +#elif defined(__GNUC__) && \ + (__GNUC__ < 3 || __GNUC__ == 3 && __GNUC_MINOR__ <= 3) +# define BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN +#elif BOOST_WORKAROUND(BOOST_INTEL, < 900) || \ + BOOST_WORKAROUND(__EDG_VERSION__, < 304) || \ + BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x0593)) +# define BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN +#endif + +/*************************************************************************************************/ + +namespace boost { +namespace unordered_detail { + +/*************************************************************************************************/ + +namespace move_detail { + +/*************************************************************************************************/ + +#if !defined(BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN) + +/*************************************************************************************************/ + +template <typename T> +struct class_has_move_assign { + class type { + typedef T& (T::*E)(T t); + typedef char (&no_type)[1]; + typedef char (&yes_type)[2]; + template <E e> struct sfinae { typedef yes_type type; }; + template <class U> + static typename sfinae<&U::operator=>::type test(int); + template <class U> + static no_type test(...); + public: + enum {value = sizeof(test<T>(1)) == sizeof(yes_type)}; + }; + }; + +/*************************************************************************************************/ + +template<typename T> +struct has_move_assign : boost::mpl::and_<boost::is_class<T>, class_has_move_assign<T> > {}; + +/*************************************************************************************************/ + +class test_can_convert_anything { }; + +/*************************************************************************************************/ + +#endif // BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN + +/*************************************************************************************************/ + +/* + REVISIT (sparent@adobe.com): This is a work around for Boost 1.34.1 and VC++ 2008 where + boost::is_convertible<T, T> fails to compile. +*/ + +template <typename T, typename U> +struct is_convertible : boost::mpl::or_< + boost::is_same<T, U>, + boost::is_convertible<T, U> +> { }; + +/*************************************************************************************************/ + +} //namespace move_detail + + +/*************************************************************************************************/ + +/*! +\ingroup move_related +\brief move_from is used for move_ctors. +*/ + +template <typename T> +struct move_from +{ + explicit move_from(T& x) : source(x) { } + T& source; +private: + move_from& operator=(move_from const&); +}; + +/*************************************************************************************************/ + +#if !defined(BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN) + +/*************************************************************************************************/ + +/*! +\ingroup move_related +\brief The is_movable trait can be used to identify movable types. +*/ +template <typename T> +struct is_movable : boost::mpl::and_< + boost::is_convertible<move_from<T>, T>, + move_detail::has_move_assign<T>, + boost::mpl::not_<boost::is_convertible<move_detail::test_can_convert_anything, T> > + > { }; + +/*************************************************************************************************/ + +#else // BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN + +// On compilers which don't have adequate SFINAE support, treat most types as unmovable, +// unless the trait is specialized. + +template <typename T> +struct is_movable : boost::mpl::false_ { }; + +#endif + +/*************************************************************************************************/ + +#if !defined(BOOST_NO_SFINAE) + +/*************************************************************************************************/ + +/*! +\ingroup move_related +\brief copy_sink and move_sink are used to select between overloaded operations according to + whether type T is movable and convertible to type U. +\sa move +*/ + +template <typename T, + typename U = T, + typename R = void*> +struct copy_sink : boost::enable_if< + boost::mpl::and_< + boost::unordered_detail::move_detail::is_convertible<T, U>, + boost::mpl::not_<is_movable<T> > + >, + R + > +{ }; + +/*************************************************************************************************/ + +/*! +\ingroup move_related +\brief move_sink and copy_sink are used to select between overloaded operations according to + whether type T is movable and convertible to type U. + \sa move +*/ + +template <typename T, + typename U = T, + typename R = void*> +struct move_sink : boost::enable_if< + boost::mpl::and_< + boost::unordered_detail::move_detail::is_convertible<T, U>, + is_movable<T> + >, + R + > +{ }; + +/*************************************************************************************************/ + +/*! +\ingroup move_related +\brief This version of move is selected when T is_movable . It in turn calls the move +constructor. This call, with the help of the return value optimization, will cause x to be moved +instead of copied to its destination. See adobe/test/move/main.cpp for examples. + +*/ +template <typename T> +T move(T& x, typename move_sink<T>::type = 0) { return T(move_from<T>(x)); } + +/*************************************************************************************************/ + +/*! +\ingroup move_related +\brief This version of move is selected when T is not movable . The net result will be that +x gets copied. +*/ +template <typename T> +T& move(T& x, typename copy_sink<T>::type = 0) { return x; } + +/*************************************************************************************************/ + +#else // BOOST_NO_SFINAE + +// On compilers without SFINAE, define copy_sink to always use the copy function. + +template <typename T, + typename U = T, + typename R = void*> +struct copy_sink +{ + typedef R type; +}; + +// Always copy the element unless this is overloaded. + +template <typename T> +T& move(T& x) { + return x; +} + +#endif // BOOST_NO_SFINAE + +} // namespace unordered_detail +} // namespace boost + +/*************************************************************************************************/ + +#endif + +/*************************************************************************************************/ diff --git a/3rdParty/Boost/src/boost/unordered/detail/node.hpp b/3rdParty/Boost/src/boost/unordered/detail/node.hpp new file mode 100644 index 0000000..85a3141 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/node.hpp @@ -0,0 +1,226 @@ + +// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. +// Copyright (C) 2005-2009 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) + +// This contains the basic data structure, apart from the actual values. There's +// no construction or deconstruction here. So this only depends on the pointer +// type. + +#ifndef BOOST_UNORDERED_DETAIL_NODE_HPP_INCLUDED +#define BOOST_UNORDERED_DETAIL_NODE_HPP_INCLUDED + +#include <boost/config.hpp> +#include <boost/assert.hpp> +#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 { + + //////////////////////////////////////////////////////////////////////////// + // ungrouped node implementation + + template <class A> + inline BOOST_DEDUCED_TYPENAME ungrouped_node_base<A>::node_ptr& + ungrouped_node_base<A>::next_group(node_ptr ptr) + { + return ptr->next_; + } + + template <class A> + inline std::size_t ungrouped_node_base<A>::group_count(node_ptr) + { + return 1; + } + + template <class A> + inline void ungrouped_node_base<A>::add_to_bucket(node_ptr n, bucket& b) + { + n->next_ = b.next_; + b.next_ = n; + } + + template <class A> + inline void ungrouped_node_base<A>::add_after_node(node_ptr n, + node_ptr position) + { + n->next_ = position->next_; + position->next_ = position; + } + + template <class A> + inline void ungrouped_node_base<A>::unlink_nodes(bucket& b, + node_ptr begin, node_ptr end) + { + node_ptr* pos = &b.next_; + while(*pos != begin) pos = &(*pos)->next_; + *pos = end; + } + + template <class A> + inline void ungrouped_node_base<A>::unlink_nodes(bucket& b, node_ptr end) + { + b.next_ = end; + } + + template <class A> + inline void ungrouped_node_base<A>::unlink_node(bucket& b, node_ptr n) + { + unlink_nodes(b, n, n->next_); + } + + //////////////////////////////////////////////////////////////////////////// + // grouped node implementation + + // If ptr is the first element in a group, return pointer to next group. + // Otherwise returns a pointer to ptr. + template <class A> + inline BOOST_DEDUCED_TYPENAME grouped_node_base<A>::node_ptr& + grouped_node_base<A>::next_group(node_ptr ptr) + { + return get(ptr).group_prev_->next_; + } + + template <class A> + inline BOOST_DEDUCED_TYPENAME grouped_node_base<A>::node_ptr + grouped_node_base<A>::first_in_group(node_ptr ptr) + { + while(next_group(ptr) == ptr) + ptr = get(ptr).group_prev_; + return ptr; + } + + template <class A> + inline std::size_t grouped_node_base<A>::group_count(node_ptr ptr) + { + node_ptr start = ptr; + std::size_t size = 0; + do { + ++size; + ptr = get(ptr).group_prev_; + } while(ptr != start); + return size; + } + + template <class A> + inline void grouped_node_base<A>::add_to_bucket(node_ptr n, bucket& b) + { + n->next_ = b.next_; + get(n).group_prev_ = n; + b.next_ = n; + } + + template <class A> + inline void grouped_node_base<A>::add_after_node(node_ptr n, node_ptr pos) + { + n->next_ = next_group(pos); + get(n).group_prev_ = get(pos).group_prev_; + next_group(pos) = n; + get(pos).group_prev_ = n; + } + + // Break a ciruclar list into two, with split as the beginning + // of the second group (if split is at the beginning then don't + // split). + template <class A> + inline BOOST_DEDUCED_TYPENAME grouped_node_base<A>::node_ptr + grouped_node_base<A>::split_group(node_ptr split) + { + node_ptr first = first_in_group(split); + if(first == split) return split; + + node_ptr last = get(first).group_prev_; + get(first).group_prev_ = get(split).group_prev_; + get(split).group_prev_ = last; + + return first; + } + + template <class A> + void grouped_node_base<A>::unlink_node(bucket& b, node_ptr n) + { + node_ptr next = n->next_; + node_ptr* pos = &next_group(n); + + if(*pos != n) { + // The node is at the beginning of a group. + + // Find the previous node pointer: + pos = &b.next_; + while(*pos != n) pos = &next_group(*pos); + + // Remove from group + if(BOOST_UNORDERED_BORLAND_BOOL(next) && + get(next).group_prev_ == n) + { + get(next).group_prev_ = get(n).group_prev_; + } + } + else if(BOOST_UNORDERED_BORLAND_BOOL(next) && + get(next).group_prev_ == n) + { + // The deleted node is not at the end of the group, so + // change the link from the next node. + get(next).group_prev_ = get(n).group_prev_; + } + else { + // The deleted node is at the end of the group, so the + // first node in the group is pointing to it. + // Find that to change its pointer. + node_ptr x = get(n).group_prev_; + while(get(x).group_prev_ != n) { + x = get(x).group_prev_; + } + get(x).group_prev_ = get(n).group_prev_; + } + *pos = next; + } + + template <class A> + void grouped_node_base<A>::unlink_nodes(bucket& b, + node_ptr begin, node_ptr end) + { + node_ptr* pos = &next_group(begin); + + if(*pos != begin) { + // The node is at the beginning of a group. + + // Find the previous node pointer: + pos = &b.next_; + while(*pos != begin) pos = &next_group(*pos); + + // Remove from group + if(BOOST_UNORDERED_BORLAND_BOOL(end)) split_group(end); + } + else { + node_ptr group1 = split_group(begin); + if(BOOST_UNORDERED_BORLAND_BOOL(end)) { + node_ptr group2 = split_group(end); + + if(begin == group2) { + node_ptr end1 = get(group1).group_prev_; + node_ptr end2 = get(group2).group_prev_; + get(group1).group_prev_ = end2; + get(group2).group_prev_ = end1; + } + } + } + *pos = end; + } + + template <class A> + void grouped_node_base<A>::unlink_nodes(bucket& b, node_ptr end) + { + split_group(end); + b.next_ = end; + } +}} + +#endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/table.hpp b/3rdParty/Boost/src/boost/unordered/detail/table.hpp new file mode 100644 index 0000000..d37c015 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/table.hpp @@ -0,0 +1,778 @@ + +// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. +// Copyright (C) 2005-2009 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_ALL_HPP_INCLUDED +#define BOOST_UNORDERED_DETAIL_ALL_HPP_INCLUDED + +#include <cstddef> +#include <stdexcept> +#include <algorithm> +#include <boost/config/no_tr1/cmath.hpp> +#include <boost/iterator/iterator_categories.hpp> +#include <boost/throw_exception.hpp> + +#include <boost/unordered/detail/buckets.hpp> + +namespace boost { namespace unordered_detail { + + //////////////////////////////////////////////////////////////////////////// + // Helper methods + + // strong exception safety, no side effects + template <class T> + inline bool hash_table<T>::equal( + key_type const& k, value_type const& v) const + { + return this->key_eq()(k, get_key(v)); + } + + // 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 + { + node_ptr it = bucket->next_; + while (BOOST_UNORDERED_BORLAND_BOOL(it) && + !equal(k, node::get_value(it))) + { + it = node::next_group(it); + } + + return it; + } + + // strong exception safety, no side effects + // pre: this->buckets_ + template <class T> + inline BOOST_DEDUCED_TYPENAME T::node_ptr + hash_table<T>::find_iterator(key_type const& k) const + { + return find_iterator(this->get_bucket(this->bucket_index(k)), k); + } + + // strong exception safety, no side effects + template <class T> + inline BOOST_DEDUCED_TYPENAME T::node_ptr* + hash_table<T>::find_for_erase( + bucket_ptr bucket, key_type const& k) const + { + node_ptr* it = &bucket->next_; + while(BOOST_UNORDERED_BORLAND_BOOL(*it) && + !equal(k, node::get_value(*it))) + { + it = &node::next_group(*it); + } + + return it; + } + + //////////////////////////////////////////////////////////////////////////// + // Load methods + + // no throw + template <class T> + std::size_t hash_table<T>::max_size() const + { + using namespace std; + + // size < mlf_ * count + return double_to_size_t(ceil( + (double) this->mlf_ * this->max_bucket_count())) - 1; + } + + // strong safety + template <class T> + inline std::size_t hash_table<T>::bucket_index( + key_type const& k) const + { + // hash_function can throw: + return this->hash_function()(k) % this->bucket_count_; + } + + + // no throw + template <class T> + inline std::size_t hash_table<T>::calculate_max_load() + { + using namespace std; + + // From 6.3.1/13: + // Only resize when size >= mlf_ * count + return double_to_size_t(ceil((double) mlf_ * this->bucket_count_)); + } + + template <class T> + void hash_table<T>::max_load_factor(float z) + { + BOOST_ASSERT(z > 0); + mlf_ = (std::max)(z, minimum_max_load_factor); + this->max_load_ = this->calculate_max_load(); + } + + // no throw + template <class T> + inline std::size_t hash_table<T>::min_buckets_for_size( + std::size_t size) const + { + BOOST_ASSERT(this->mlf_ != 0); + + using namespace std; + + // From 6.3.1/13: + // size < mlf_ * count + // => count > size / mlf_ + // + // Or from rehash post-condition: + // count > size / mlf_ + return next_prime(double_to_size_t(floor(size / (double) mlf_)) + 1); + } + + //////////////////////////////////////////////////////////////////////////// + // recompute_begin_bucket + + // init_buckets + + template <class T> + inline void hash_table<T>::init_buckets() + { + if (this->size_) { + this->cached_begin_bucket_ = this->buckets_; + while (!this->cached_begin_bucket_->next_) + ++this->cached_begin_bucket_; + } else { + this->cached_begin_bucket_ = this->get_bucket(this->bucket_count_); + } + this->max_load_ = calculate_max_load(); + } + + // After an erase cached_begin_bucket_ might be left pointing to + // an empty bucket, so this is called to update it + // + // no throw + + template <class T> + inline void hash_table<T>::recompute_begin_bucket(bucket_ptr b) + { + BOOST_ASSERT(!(b < this->cached_begin_bucket_)); + + if(b == this->cached_begin_bucket_) + { + if (this->size_ != 0) { + while (!this->cached_begin_bucket_->next_) + ++this->cached_begin_bucket_; + } else { + this->cached_begin_bucket_ = + this->get_bucket(this->bucket_count_); + } + } + } + + // This is called when a range has been erased + // + // no throw + + template <class T> + inline void hash_table<T>::recompute_begin_bucket( + bucket_ptr b1, bucket_ptr b2) + { + BOOST_ASSERT(!(b1 < this->cached_begin_bucket_) && !(b2 < b1)); + BOOST_ASSERT(BOOST_UNORDERED_BORLAND_BOOL(b2->next_)); + + if(b1 == this->cached_begin_bucket_ && !b1->next_) + this->cached_begin_bucket_ = b2; + } + + // no throw + template <class T> + inline float hash_table<T>::load_factor() const + { + BOOST_ASSERT(this->bucket_count_ != 0); + return static_cast<float>(this->size_) + / static_cast<float>(this->bucket_count_); + } + + //////////////////////////////////////////////////////////////////////////// + // Constructors + + template <class T> + hash_table<T>::hash_table(std::size_t num_buckets, + hasher const& hf, key_equal const& eq, node_allocator const& a) + : buckets(a, next_prime(num_buckets)), + base(hf, eq), + size_(), + mlf_(1.0f), + cached_begin_bucket_(), + max_load_(0) + { + } + + // Copy Construct with allocator + + template <class T> + hash_table<T>::hash_table(hash_table const& x, + node_allocator const& a) + : buckets(a, x.min_buckets_for_size(x.size_)), + base(x), + size_(x.size_), + mlf_(x.mlf_), + cached_begin_bucket_(), + max_load_(0) + { + if(x.size_) { + x.copy_buckets_to(*this); + this->init_buckets(); + } + } + + // Move Construct + + template <class T> + hash_table<T>::hash_table(hash_table& x, move_tag) + : buckets(x.node_alloc(), x.bucket_count_), + base(x), + size_(0), + mlf_(1.0f), + cached_begin_bucket_(), + max_load_(0) + { + this->partial_swap(x); + } + + template <class T> + hash_table<T>::hash_table(hash_table& x, + node_allocator const& a, move_tag) + : buckets(a, x.bucket_count_), + base(x), + size_(0), + mlf_(x.mlf_), + cached_begin_bucket_(), + max_load_(0) + { + if(a == x.node_alloc()) { + this->partial_swap(x); + } + else if(x.size_) { + x.copy_buckets_to(*this); + this->size_ = x.size_; + this->init_buckets(); + } + } + + template <class T> + hash_table<T>& hash_table<T>::operator=( + hash_table const& x) + { + hash_table tmp(x, this->node_alloc()); + this->fast_swap(tmp); + return *this; + } + + //////////////////////////////////////////////////////////////////////////// + // Swap & Move + + // Swap + // + // Strong exception safety + // + // Can throw if hash or predicate object's copy constructor throws + // or if allocators are unequal. + + template <class T> + inline void hash_table<T>::partial_swap(hash_table& x) + { + this->buckets::swap(x); // No throw + std::swap(this->size_, x.size_); + std::swap(this->mlf_, x.mlf_); + std::swap(this->cached_begin_bucket_, x.cached_begin_bucket_); + std::swap(this->max_load_, x.max_load_); + } + + template <class T> + inline void hash_table<T>::fast_swap(hash_table& x) + { + // These can throw, but they only affect the function objects + // that aren't in use so it is strongly exception safe, via. + // double buffering. + { + set_hash_functions<hasher, key_equal> op1(*this, x); + set_hash_functions<hasher, key_equal> op2(x, *this); + op1.commit(); + op2.commit(); + } + this->buckets::swap(x); // No throw + std::swap(this->size_, x.size_); + std::swap(this->mlf_, x.mlf_); + std::swap(this->cached_begin_bucket_, x.cached_begin_bucket_); + std::swap(this->max_load_, x.max_load_); + } + + template <class T> + inline void hash_table<T>::slow_swap(hash_table& x) + { + if(this == &x) return; + + { + // These can throw, but they only affect the function objects + // that aren't in use so it is strongly exception safe, via. + // double buffering. + set_hash_functions<hasher, key_equal> op1(*this, x); + set_hash_functions<hasher, key_equal> op2(x, *this); + + // Create new buckets in separate hash_buckets objects + // which will clean up if anything throws an exception. + // (all can throw, but with no effect as these are new objects). + + buckets b1(this->node_alloc(), x.min_buckets_for_size(x.size_)); + if(x.size_) x.copy_buckets_to(b1); + + buckets b2(x.node_alloc(), this->min_buckets_for_size(this->size_)); + if(this->size_) copy_buckets_to(b2); + + // Modifying the data, so no throw from now on. + + b1.swap(*this); + b2.swap(x); + op1.commit(); + op2.commit(); + } + + std::swap(this->size_, x.size_); + + if(this->buckets_) this->init_buckets(); + if(x.buckets_) x.init_buckets(); + } + + template <class T> + void hash_table<T>::swap(hash_table& x) + { + if(this->node_alloc() == x.node_alloc()) { + if(this != &x) this->fast_swap(x); + } + else { + this->slow_swap(x); + } + } + + + // Move + // + // Strong exception safety (might change unused function objects) + // + // Can throw if hash or predicate object's copy constructor throws + // or if allocators are unequal. + + template <class T> + void hash_table<T>::move(hash_table& x) + { + // This can throw, but it only affects the function objects + // that aren't in use so it is strongly exception safe, via. + // double buffering. + set_hash_functions<hasher, key_equal> new_func_this(*this, x); + + if(this->node_alloc() == x.node_alloc()) { + this->buckets::move(x); // no throw + this->size_ = x.size_; + this->cached_begin_bucket_ = x.cached_begin_bucket_; + this->max_load_ = x.max_load_; + x.size_ = 0; + } + else { + // Create new buckets in separate HASH_TABLE_DATA objects + // which will clean up if anything throws an exception. + // (all can throw, but with no effect as these are new objects). + + buckets b(this->node_alloc(), x.min_buckets_for_size(x.size_)); + if(x.size_) x.copy_buckets_to(b); + + // Start updating the data here, no throw from now on. + this->size_ = x.size_; + b.swap(*this); + this->init_buckets(); + } + + // We've made it, the rest is no throw. + this->mlf_ = x.mlf_; + new_func_this.commit(); + } + + //////////////////////////////////////////////////////////////////////////// + // Reserve & Rehash + + // basic exception safety + template <class T> + inline void hash_table<T>::create_for_insert(std::size_t size) + { + this->bucket_count_ = (std::max)(this->bucket_count_, + this->min_buckets_for_size(size)); + this->create_buckets(); + this->init_buckets(); + } + + // basic exception safety + template <class T> + inline bool hash_table<T>::reserve_for_insert(std::size_t size) + { + if(size >= max_load_) { + std::size_t num_buckets + = this->min_buckets_for_size((std::max)(size, + this->size_ + (this->size_ >> 1))); + if(num_buckets != this->bucket_count_) { + rehash_impl(num_buckets); + return true; + } + } + + return false; + } + + // if hash function throws, basic exception safety + // strong otherwise. + + template <class T> + inline void hash_table<T>::rehash(std::size_t min_buckets) + { + using namespace std; + + if(!this->size_) { + if(this->buckets_) this->delete_buckets(); + this->bucket_count_ = next_prime(min_buckets); + } + else { + // no throw: + min_buckets = next_prime((std::max)(min_buckets, + double_to_size_t(floor(this->size_ / (double) mlf_)) + 1)); + if(min_buckets != this->bucket_count_) rehash_impl(min_buckets); + } + } + + // if hash function throws, basic exception safety + // strong otherwise + + template <class T> + void hash_table<T> + ::rehash_impl(std::size_t num_buckets) + { + hasher const& hf = this->hash_function(); + std::size_t size = this->size_; + bucket_ptr end = this->get_bucket(this->bucket_count_); + + buckets dst(this->node_alloc(), num_buckets); + dst.create_buckets(); + + buckets src(this->node_alloc(), this->bucket_count_); + src.swap(*this); + this->size_ = 0; + + for(bucket_ptr bucket = this->cached_begin_bucket_; + bucket != end; ++bucket) + { + node_ptr group = bucket->next_; + while(group) { + // Move the first group of equivalent nodes in bucket to dst. + + // This next line throws iff the hash function throws. + bucket_ptr dst_bucket = dst.bucket_ptr_from_hash( + hf(get_key_from_ptr(group))); + + node_ptr& next_group = node::next_group(group); + bucket->next_ = next_group; + next_group = dst_bucket->next_; + dst_bucket->next_ = group; + group = bucket->next_; + } + } + + // Swap the new nodes back into the container and setup the local + // variables. + this->size_ = size; + dst.swap(*this); // no throw + this->init_buckets(); + } + + //////////////////////////////////////////////////////////////////////////// + // copy_buckets_to + + // copy_buckets_to + // + // basic excpetion safety. If an exception is thrown this will + // leave dst partially filled. + + template <class T> + void hash_table<T> + ::copy_buckets_to(buckets& dst) const + { + BOOST_ASSERT(this->buckets_ && !dst.buckets_); + + hasher const& hf = this->hash_function(); + bucket_ptr end = this->get_bucket(this->bucket_count_); + + node_constructor a(dst); + dst.create_buckets(); + + // no throw: + for(bucket_ptr i = this->cached_begin_bucket_; i != end; ++i) { + // no throw: + for(node_ptr it = i->next_; it;) { + // hash function can throw. + bucket_ptr dst_bucket = dst.bucket_ptr_from_hash( + hf(get_key_from_ptr(it))); + // throws, strong + + node_ptr group_end = node::next_group(it); + + a.construct(node::get_value(it)); + node_ptr n = a.release(); + node::add_to_bucket(n, *dst_bucket); + + for(it = it->next_; it != group_end; it = it->next_) { + a.construct(node::get_value(it)); + node::add_after_node(a.release(), n); + } + } + } + } + + //////////////////////////////////////////////////////////////////////////// + // Misc. key methods + + // strong exception safety + + // count + // + // strong exception safety, no side effects + + template <class T> + std::size_t hash_table<T>::count(key_type const& k) const + { + if(!this->size_) return 0; + node_ptr it = find_iterator(k); // throws, strong + return BOOST_UNORDERED_BORLAND_BOOL(it) ? node::group_count(it) : 0; + } + + // find + // + // strong exception safety, no side effects + template <class T> + BOOST_DEDUCED_TYPENAME T::iterator_base + hash_table<T>::find(key_type const& k) const + { + if(!this->size_) return this->end(); + + bucket_ptr bucket = this->get_bucket(this->bucket_index(k)); + node_ptr it = find_iterator(bucket, k); + + if (BOOST_UNORDERED_BORLAND_BOOL(it)) + return iterator_base(bucket, it); + else + return this->end(); + } + + template <class T> + template <class Key, class Hash, class Pred> + BOOST_DEDUCED_TYPENAME T::iterator_base hash_table<T>::find(Key const& k, + Hash const& h, Pred const& eq) const + { + if(!this->size_) return this->end(); + + bucket_ptr bucket = this->get_bucket(h(k) % this->bucket_count_); + node_ptr it = find_iterator(bucket, k, eq); + + if (BOOST_UNORDERED_BORLAND_BOOL(it)) + return iterator_base(bucket, it); + else + return this->end(); + } + + template <class T> + BOOST_DEDUCED_TYPENAME T::value_type& + hash_table<T>::at(key_type const& k) const + { + if(!this->size_) + boost::throw_exception(std::out_of_range("Unable to find key in unordered_map.")); + + bucket_ptr bucket = this->get_bucket(this->bucket_index(k)); + node_ptr it = find_iterator(bucket, k); + + if (!it) + boost::throw_exception(std::out_of_range("Unable to find key in unordered_map.")); + + return node::get_value(it); + } + + // equal_range + // + // strong exception safety, no side effects + template <class T> + BOOST_DEDUCED_TYPENAME T::iterator_pair + hash_table<T>::equal_range(key_type const& k) const + { + if(!this->size_) + return iterator_pair(this->end(), this->end()); + + bucket_ptr bucket = this->get_bucket(this->bucket_index(k)); + node_ptr it = find_iterator(bucket, k); + if (BOOST_UNORDERED_BORLAND_BOOL(it)) { + iterator_base first(iterator_base(bucket, it)); + iterator_base second(first); + second.increment_bucket(node::next_group(second.node_)); + return iterator_pair(first, second); + } + else { + return iterator_pair(this->end(), this->end()); + } + } + + //////////////////////////////////////////////////////////////////////////// + // Erase methods + + template <class T> + void hash_table<T>::clear() + { + if(!this->size_) return; + + bucket_ptr end = this->get_bucket(this->bucket_count_); + for(bucket_ptr begin = this->buckets_; begin != end; ++begin) { + this->clear_bucket(begin); + } + + this->size_ = 0; + this->cached_begin_bucket_ = end; + } + + template <class T> + inline std::size_t hash_table<T>::erase_group( + node_ptr* it, bucket_ptr bucket) + { + node_ptr pos = *it; + node_ptr end = node::next_group(pos); + *it = end; + std::size_t count = this->delete_nodes(pos, end); + this->size_ -= count; + this->recompute_begin_bucket(bucket); + return count; + } + + template <class T> + std::size_t hash_table<T>::erase_key(key_type const& k) + { + if(!this->size_) return 0; + + // No side effects in initial section + bucket_ptr bucket = this->get_bucket(this->bucket_index(k)); + node_ptr* it = this->find_for_erase(bucket, k); + + // No throw. + return *it ? this->erase_group(it, bucket) : 0; + } + + template <class T> + void hash_table<T>::erase(iterator_base r) + { + BOOST_ASSERT(r.node_); + --this->size_; + node::unlink_node(*r.bucket_, r.node_); + this->delete_node(r.node_); + // r has been invalidated but its bucket is still valid + this->recompute_begin_bucket(r.bucket_); + } + + template <class T> + BOOST_DEDUCED_TYPENAME T::iterator_base + hash_table<T>::erase_return_iterator(iterator_base r) + { + BOOST_ASSERT(r.node_); + iterator_base next = r; + next.increment(); + --this->size_; + node::unlink_node(*r.bucket_, r.node_); + this->delete_node(r.node_); + // r has been invalidated but its bucket is still valid + this->recompute_begin_bucket(r.bucket_, next.bucket_); + return next; + } + + template <class T> + BOOST_DEDUCED_TYPENAME T::iterator_base + hash_table<T>::erase_range( + iterator_base r1, iterator_base r2) + { + if(r1 != r2) + { + BOOST_ASSERT(r1.node_); + if (r1.bucket_ == r2.bucket_) { + node::unlink_nodes(*r1.bucket_, r1.node_, r2.node_); + this->size_ -= this->delete_nodes(r1.node_, r2.node_); + + // No need to call recompute_begin_bucket because + // the nodes are only deleted from one bucket, which + // still contains r2 after the erase. + BOOST_ASSERT(r1.bucket_->next_); + } + else { + bucket_ptr end_bucket = r2.node_ ? + r2.bucket_ : this->get_bucket(this->bucket_count_); + BOOST_ASSERT(r1.bucket_ < end_bucket); + node::unlink_nodes(*r1.bucket_, r1.node_, node_ptr()); + this->size_ -= this->delete_nodes(r1.node_, node_ptr()); + + bucket_ptr i = r1.bucket_; + for(++i; i != end_bucket; ++i) { + this->size_ -= this->delete_nodes(i->next_, node_ptr()); + i->next_ = node_ptr(); + } + + if(r2.node_) { + node_ptr first = r2.bucket_->next_; + node::unlink_nodes(*r2.bucket_, r2.node_); + this->size_ -= this->delete_nodes(first, r2.node_); + } + + // r1 has been invalidated but its bucket is still + // valid. + this->recompute_begin_bucket(r1.bucket_, end_bucket); + } + } + + return r2; + } + + template <class T> + BOOST_DEDUCED_TYPENAME hash_table<T>::iterator_base + hash_table<T>::emplace_empty_impl_with_node( + node_constructor& a, std::size_t size) + { + key_type const& k = get_key(a.value()); + std::size_t hash_value = this->hash_function()(k); + if(this->buckets_) this->reserve_for_insert(size); + else this->create_for_insert(size); + bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value); + node_ptr n = a.release(); + node::add_to_bucket(n, *bucket); + ++this->size_; + this->cached_begin_bucket_ = bucket; + return iterator_base(bucket, n); + } +}} + +#endif 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 diff --git a/3rdParty/Boost/src/boost/unordered/detail/util.hpp b/3rdParty/Boost/src/boost/unordered/detail/util.hpp new file mode 100644 index 0000000..5540965 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/util.hpp @@ -0,0 +1,331 @@ + +// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. +// Copyright (C) 2005-2009 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_UTIL_HPP_INCLUDED +#define BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED + +#include <cstddef> +#include <utility> +#include <algorithm> +#include <boost/limits.hpp> +#include <boost/iterator/iterator_categories.hpp> +#include <boost/preprocessor/seq/size.hpp> +#include <boost/preprocessor/seq/enum.hpp> +#include <boost/unordered/detail/fwd.hpp> + +namespace boost { namespace unordered_detail { + + //////////////////////////////////////////////////////////////////////////// + // convert double to std::size_t + + inline std::size_t double_to_size_t(double f) + { + return f >= static_cast<double>( + (std::numeric_limits<std::size_t>::max)()) ? + (std::numeric_limits<std::size_t>::max)() : + static_cast<std::size_t>(f); + } + + //////////////////////////////////////////////////////////////////////////// + // primes + +#define BOOST_UNORDERED_PRIMES \ + (5ul)(11ul)(17ul)(29ul)(37ul)(53ul)(67ul)(79ul) \ + (97ul)(131ul)(193ul)(257ul)(389ul)(521ul)(769ul) \ + (1031ul)(1543ul)(2053ul)(3079ul)(6151ul)(12289ul)(24593ul) \ + (49157ul)(98317ul)(196613ul)(393241ul)(786433ul) \ + (1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul) \ + (50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul) \ + (1610612741ul)(3221225473ul)(4294967291ul) + + template<class T> struct prime_list_template + { + static std::size_t const value[]; + +#if !defined(SUNPRO_CC) + static std::ptrdiff_t const length; +#else + static std::ptrdiff_t const length + = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES); +#endif + }; + + template<class T> + std::size_t const prime_list_template<T>::value[] = { + BOOST_PP_SEQ_ENUM(BOOST_UNORDERED_PRIMES) + }; + +#if !defined(SUNPRO_CC) + template<class T> + std::ptrdiff_t const prime_list_template<T>::length + = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES); +#endif + +#undef BOOST_UNORDERED_PRIMES + + typedef prime_list_template<std::size_t> prime_list; + + // no throw + inline std::size_t next_prime(std::size_t num) { + std::size_t const* const prime_list_begin = prime_list::value; + std::size_t const* const prime_list_end = prime_list_begin + + prime_list::length; + std::size_t const* bound = + std::lower_bound(prime_list_begin, prime_list_end, num); + if(bound == prime_list_end) + bound--; + return *bound; + } + + // no throw + inline std::size_t prev_prime(std::size_t num) { + std::size_t const* const prime_list_begin = prime_list::value; + std::size_t const* const prime_list_end = prime_list_begin + + prime_list::length; + std::size_t const* bound = + std::upper_bound(prime_list_begin,prime_list_end, num); + if(bound != prime_list_begin) + bound--; + return *bound; + } + + //////////////////////////////////////////////////////////////////////////// + // pair_cast - because some libraries don't have the full pair constructors. + + template <class Dst1, class Dst2, class Src1, class Src2> + inline std::pair<Dst1, Dst2> pair_cast(std::pair<Src1, Src2> const& x) + { + return std::pair<Dst1, Dst2>(Dst1(x.first), Dst2(x.second)); + } + + //////////////////////////////////////////////////////////////////////////// + // insert_size/initial_size + +#if !defined(BOOST_NO_STD_DISTANCE) + using ::std::distance; +#else + template <class ForwardIterator> + inline std::size_t distance(ForwardIterator i, ForwardIterator j) { + std::size_t x; + std::distance(i, j, x); + return x; + } +#endif + + template <class I> + inline std::size_t insert_size(I i, I j, boost::forward_traversal_tag) + { + return std::distance(i, j); + } + + template <class I> + inline std::size_t insert_size(I, I, boost::incrementable_traversal_tag) + { + return 1; + } + + template <class I> + inline std::size_t insert_size(I i, I j) + { + BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type + iterator_traversal_tag; + return insert_size(i, j, iterator_traversal_tag); + } + + template <class I> + inline std::size_t initial_size(I i, I j, + std::size_t num_buckets = boost::unordered_detail::default_bucket_count) + { + return (std::max)(static_cast<std::size_t>(insert_size(i, j)) + 1, + num_buckets); + } + + //////////////////////////////////////////////////////////////////////////// + // Node Constructors + +#if defined(BOOST_UNORDERED_STD_FORWARD) + + template <class T, class... Args> + inline void construct_impl(T*, void* address, Args&&... args) + { + new(address) T(std::forward<Args>(args)...); + } + +#if defined(BOOST_UNORDERED_CPP0X_PAIR) + template <class First, class Second, class Key, class Arg0, class... Args> + inline void construct_impl(std::pair<First, Second>*, void* address, + Key&& k, Arg0&& arg0, Args&&... args) + ) + { + new(address) std::pair<First, Second>(k, + Second(arg0, std::forward<Args>(args)...); + } +#endif + +#else + +#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _) \ + template < \ + class T, \ + BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ + > \ + inline void construct_impl( \ + T*, void* address, \ + BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \ + ) \ + { \ + new(address) T( \ + BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \ + } \ + \ + template <class First, class Second, class Key, \ + BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ + > \ + inline void construct_impl( \ + std::pair<First, Second>*, void* address, \ + Key const& k, BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \ + { \ + new(address) std::pair<First, Second>(k, \ + Second(BOOST_UNORDERED_CALL_PARAMS(z, num_params))); \ + } + + BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, + BOOST_UNORDERED_CONSTRUCT_IMPL, _) + +#undef BOOST_UNORDERED_CONSTRUCT_IMPL +#endif + + // hash_node_constructor + // + // Used to construct nodes in an exception safe manner. + + template <class Alloc, class Grouped> + class hash_node_constructor + { + typedef hash_buckets<Alloc, Grouped> buckets; + typedef BOOST_DEDUCED_TYPENAME buckets::node node; + typedef BOOST_DEDUCED_TYPENAME buckets::real_node_ptr real_node_ptr; + typedef BOOST_DEDUCED_TYPENAME buckets::value_type value_type; + + buckets& buckets_; + real_node_ptr node_; + bool node_constructed_; + bool value_constructed_; + + public: + + hash_node_constructor(buckets& m) : + buckets_(m), + node_(), + node_constructed_(false), + value_constructed_(false) + { + } + + ~hash_node_constructor(); + void construct_preamble(); + +#if defined(BOOST_UNORDERED_STD_FORWARD) + template <class... Args> + void construct(Args&&... args) + { + construct_preamble(); + construct_impl((value_type*) 0, node_->address(), + std::forward<Args>(args)...); + value_constructed_ = true; + } +#else + +#define BOOST_UNORDERED_CONSTRUCT(z, num_params, _) \ + template < \ + BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ + > \ + void construct( \ + BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \ + ) \ + { \ + construct_preamble(); \ + construct_impl( \ + (value_type*) 0, node_->address(), \ + BOOST_UNORDERED_CALL_PARAMS(z, num_params) \ + ); \ + value_constructed_ = true; \ + } + + BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, + BOOST_UNORDERED_CONSTRUCT, _) + +#undef BOOST_UNORDERED_CONSTRUCT + +#endif + template <class K, class M> + void construct_pair(K const& k, M*) + { + construct_preamble(); + new(node_->address()) value_type(k, M()); + value_constructed_ = true; + } + + value_type& value() const + { + BOOST_ASSERT(node_); + return node_->value(); + } + + // no throw + BOOST_DEDUCED_TYPENAME buckets::node_ptr release() + { + real_node_ptr p = node_; + node_ = real_node_ptr(); + // node_ptr cast + return buckets_.bucket_alloc().address(*p); + } + + private: + hash_node_constructor(hash_node_constructor const&); + hash_node_constructor& operator=(hash_node_constructor const&); + }; + + // hash_node_constructor + + template <class Alloc, class Grouped> + inline hash_node_constructor<Alloc, Grouped>::~hash_node_constructor() + { + if (node_) { + if (value_constructed_) { +#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) + struct dummy { hash_node<Alloc, Grouped> x; }; +#endif + boost::unordered_detail::destroy(&node_->value()); + } + + if (node_constructed_) + buckets_.node_alloc().destroy(node_); + + buckets_.node_alloc().deallocate(node_, 1); + } + } + + template <class Alloc, class Grouped> + inline void hash_node_constructor<Alloc, Grouped>::construct_preamble() + { + if(!node_) { + node_constructed_ = false; + value_constructed_ = false; + + node_ = buckets_.node_alloc().allocate(1); + buckets_.node_alloc().construct(node_, node()); + node_constructed_ = true; + } + else { + BOOST_ASSERT(node_constructed_ && value_constructed_); + boost::unordered_detail::destroy(&node_->value()); + value_constructed_ = false; + } + } +}} + +#endif |