Swift
summaryrefslogtreecommitdiffstats
path: root/3rdParty/Boost/src/boost/unordered
diff options
context:
space:
mode:
authorRemko Tronçon <git@el-tramo.be>2011-02-12 13:54:17 (GMT)
committerRemko Tronçon <git@el-tramo.be>2011-02-12 14:27:05 (GMT)
commitb734b6a5986703b6b10ea548c93af11f9df771bf (patch)
treeb7cb4230b556fe4104e5901941e055a2beae51cd /3rdParty/Boost/src/boost/unordered
parentb75cf274d8c3cf255fd1d8932a9f6a6cfa8cb9b4 (diff)
downloadswift-b734b6a5986703b6b10ea548c93af11f9df771bf.zip
swift-b734b6a5986703b6b10ea548c93af11f9df771bf.tar.bz2
Cache stringprep results for JIDs.
Diffstat (limited to '3rdParty/Boost/src/boost/unordered')
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/allocator_helpers.hpp111
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/buckets.hpp183
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp304
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/extract_key.hpp148
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/fwd.hpp856
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/move.hpp243
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/node.hpp226
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/table.hpp778
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/unique.hpp513
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/util.hpp331
-rw-r--r--3rdParty/Boost/src/boost/unordered/unordered_map.hpp1118
-rw-r--r--3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp53
12 files changed, 4864 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
diff --git a/3rdParty/Boost/src/boost/unordered/unordered_map.hpp b/3rdParty/Boost/src/boost/unordered/unordered_map.hpp
new file mode 100644
index 0000000..5bad0eb
--- /dev/null
+++ b/3rdParty/Boost/src/boost/unordered/unordered_map.hpp
@@ -0,0 +1,1118 @@
+
+// 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)
+
+// See http://www.boost.org/libs/unordered for documentation
+
+#ifndef BOOST_UNORDERED_UNORDERED_MAP_HPP_INCLUDED
+#define BOOST_UNORDERED_UNORDERED_MAP_HPP_INCLUDED
+
+#if defined(_MSC_VER) && (_MSC_VER >= 1020)
+# pragma once
+#endif
+
+#include <boost/unordered/unordered_map_fwd.hpp>
+#include <boost/functional/hash.hpp>
+#include <boost/unordered/detail/allocator_helpers.hpp>
+#include <boost/unordered/detail/equivalent.hpp>
+#include <boost/unordered/detail/unique.hpp>
+
+#if defined(BOOST_NO_RVALUE_REFERENCES)
+#include <boost/unordered/detail/move.hpp>
+#endif
+
+#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
+#include <initializer_list>
+#endif
+
+#if defined(BOOST_MSVC)
+#pragma warning(push)
+#if BOOST_MSVC >= 1400
+#pragma warning(disable:4396) //the inline specifier cannot be used when a
+ // friend declaration refers to a specialization
+ // of a function template
+#endif
+#endif
+
+namespace boost
+{
+ template <class K, class T, class H, class P, class A>
+ class unordered_map
+ {
+ public:
+ typedef K key_type;
+ typedef std::pair<const K, T> value_type;
+ typedef T mapped_type;
+ typedef H hasher;
+ typedef P key_equal;
+ typedef A allocator_type;
+
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
+ private:
+#endif
+
+ typedef BOOST_DEDUCED_TYPENAME
+ boost::unordered_detail::rebind_wrap<
+ allocator_type, value_type>::type
+ value_allocator;
+
+ typedef boost::unordered_detail::map<K, H, P,
+ value_allocator> types;
+ typedef BOOST_DEDUCED_TYPENAME types::impl table;
+
+ typedef BOOST_DEDUCED_TYPENAME types::iterator_base iterator_base;
+
+ public:
+
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::pointer pointer;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::const_pointer const_pointer;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::reference reference;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::const_reference const_reference;
+
+ typedef std::size_t size_type;
+ typedef std::ptrdiff_t difference_type;
+
+ typedef boost::unordered_detail::hash_const_local_iterator<
+ value_allocator, boost::unordered_detail::ungrouped>
+ const_local_iterator;
+ typedef boost::unordered_detail::hash_local_iterator<
+ value_allocator, boost::unordered_detail::ungrouped>
+ local_iterator;
+ typedef boost::unordered_detail::hash_const_iterator<
+ value_allocator, boost::unordered_detail::ungrouped>
+ const_iterator;
+ typedef boost::unordered_detail::hash_iterator<
+ value_allocator, boost::unordered_detail::ungrouped>
+ iterator;
+
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
+ private:
+#endif
+
+ table table_;
+
+ BOOST_DEDUCED_TYPENAME types::iterator_base const&
+ get(const_iterator const& it)
+ {
+ return boost::unordered_detail::iterator_access::get(it);
+ }
+
+ public:
+
+ // construct/destroy/copy
+
+ explicit unordered_map(
+ size_type n = boost::unordered_detail::default_bucket_count,
+ const hasher &hf = hasher(),
+ const key_equal &eql = key_equal(),
+ const allocator_type &a = allocator_type())
+ : table_(n, hf, eql, a)
+ {
+ }
+
+ explicit unordered_map(allocator_type const& a)
+ : table_(boost::unordered_detail::default_bucket_count,
+ hasher(), key_equal(), a)
+ {
+ }
+
+ unordered_map(unordered_map const& other, allocator_type const& a)
+ : table_(other.table_, a)
+ {
+ }
+
+ template <class InputIt>
+ unordered_map(InputIt f, InputIt l)
+ : table_(boost::unordered_detail::initial_size(f, l),
+ hasher(), key_equal(), allocator_type())
+ {
+ table_.insert_range(f, l);
+ }
+
+ template <class InputIt>
+ unordered_map(InputIt f, InputIt l,
+ size_type n,
+ const hasher &hf = hasher(),
+ const key_equal &eql = key_equal())
+ : table_(boost::unordered_detail::initial_size(f, l, n),
+ hf, eql, allocator_type())
+ {
+ table_.insert_range(f, l);
+ }
+
+ template <class InputIt>
+ unordered_map(InputIt f, InputIt l,
+ size_type n,
+ const hasher &hf,
+ const key_equal &eql,
+ const allocator_type &a)
+ : table_(boost::unordered_detail::initial_size(f, l, n), hf, eql, a)
+ {
+ table_.insert_range(f, l);
+ }
+
+ ~unordered_map() {}
+
+#if !defined(BOOST_NO_RVALUE_REFERENCES)
+ unordered_map(unordered_map&& other)
+ : table_(other.table_, boost::unordered_detail::move_tag())
+ {
+ }
+
+ unordered_map(unordered_map&& other, allocator_type const& a)
+ : table_(other.table_, a, boost::unordered_detail::move_tag())
+ {
+ }
+
+ unordered_map& operator=(unordered_map&& x)
+ {
+ table_.move(x.table_);
+ return *this;
+ }
+#else
+ unordered_map(boost::unordered_detail::move_from<
+ unordered_map<K, T, H, P, A>
+ > other)
+ : table_(other.source.table_, boost::unordered_detail::move_tag())
+ {
+ }
+
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0593)
+ unordered_map& operator=(unordered_map x)
+ {
+ table_.move(x.table_);
+ return *this;
+ }
+#endif
+#endif
+
+#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
+ unordered_map(std::initializer_list<value_type> list,
+ size_type n = boost::unordered_detail::default_bucket_count,
+ const hasher &hf = hasher(),
+ const key_equal &eql = key_equal(),
+ const allocator_type &a = allocator_type())
+ : table_(boost::unordered_detail::initial_size(
+ list.begin(), list.end(), n),
+ hf, eql, a)
+ {
+ table_.insert_range(list.begin(), list.end());
+ }
+
+ unordered_map& operator=(std::initializer_list<value_type> list)
+ {
+ table_.clear();
+ table_.insert_range(list.begin(), list.end());
+ return *this;
+ }
+#endif
+
+ allocator_type get_allocator() const
+ {
+ return table_.node_alloc();
+ }
+
+ // size and capacity
+
+ bool empty() const
+ {
+ return table_.size_ == 0;
+ }
+
+ size_type size() const
+ {
+ return table_.size_;
+ }
+
+ size_type max_size() const
+ {
+ return table_.max_size();
+ }
+
+ // iterators
+
+ iterator begin()
+ {
+ return iterator(table_.begin());
+ }
+
+ const_iterator begin() const
+ {
+ return const_iterator(table_.begin());
+ }
+
+ iterator end()
+ {
+ return iterator(table_.end());
+ }
+
+ const_iterator end() const
+ {
+ return const_iterator(table_.end());
+ }
+
+ const_iterator cbegin() const
+ {
+ return const_iterator(table_.begin());
+ }
+
+ const_iterator cend() const
+ {
+ return const_iterator(table_.end());
+ }
+
+ // modifiers
+
+#if defined(BOOST_UNORDERED_STD_FORWARD)
+ template <class... Args>
+ std::pair<iterator, bool> emplace(Args&&... args)
+ {
+ return boost::unordered_detail::pair_cast<iterator, bool>(
+ table_.emplace(std::forward<Args>(args)...));
+ }
+
+ template <class... Args>
+ iterator emplace_hint(const_iterator, Args&&... args)
+ {
+ return iterator(table_.emplace(std::forward<Args>(args)...).first);
+ }
+#else
+
+ #if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100))
+ std::pair<iterator, bool> emplace(value_type const& v = value_type())
+ {
+ return boost::unordered_detail::pair_cast<iterator, bool>(
+ table_.emplace(v));
+ }
+
+ iterator emplace_hint(const_iterator,
+ value_type const& v = value_type())
+ {
+ return iterator(table_.emplace(v).first);
+ }
+ #endif
+
+#define BOOST_UNORDERED_EMPLACE(z, n, _) \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ std::pair<iterator, bool> emplace( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
+ ) \
+ { \
+ return boost::unordered_detail::pair_cast<iterator, bool>( \
+ table_.emplace( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n) \
+ )); \
+ } \
+ \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ iterator emplace_hint(const_iterator, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
+ ) \
+ { \
+ return iterator(table_.emplace( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n)).first); \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_EMPLACE, _)
+
+#undef BOOST_UNORDERED_EMPLACE
+
+#endif
+
+ std::pair<iterator, bool> insert(const value_type& obj)
+ {
+ return boost::unordered_detail::pair_cast<iterator, bool>(
+ table_.emplace(obj));
+ }
+
+ iterator insert(const_iterator, const value_type& obj)
+ {
+ return iterator(table_.emplace(obj).first);
+ }
+
+ template <class InputIt>
+ void insert(InputIt first, InputIt last)
+ {
+ table_.insert_range(first, last);
+ }
+
+#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
+ void insert(std::initializer_list<value_type> list)
+ {
+ table_.insert_range(list.begin(), list.end());
+ }
+#endif
+
+ iterator erase(const_iterator position)
+ {
+ return iterator(table_.erase_return_iterator(get(position)));
+ }
+
+ size_type erase(const key_type& k)
+ {
+ return table_.erase_key(k);
+ }
+
+ iterator erase(const_iterator first, const_iterator last)
+ {
+ return iterator(table_.erase_range(get(first), get(last)));
+ }
+
+ void quick_erase(const_iterator position)
+ {
+ table_.erase(get(position));
+ }
+
+ void erase_return_void(const_iterator position)
+ {
+ table_.erase(get(position));
+ }
+
+ void clear()
+ {
+ table_.clear();
+ }
+
+ void swap(unordered_map& other)
+ {
+ table_.swap(other.table_);
+ }
+
+ // observers
+
+ hasher hash_function() const
+ {
+ return table_.hash_function();
+ }
+
+ key_equal key_eq() const
+ {
+ return table_.key_eq();
+ }
+
+ mapped_type& operator[](const key_type &k)
+ {
+ return table_[k].second;
+ }
+
+ mapped_type& at(const key_type& k)
+ {
+ return table_.at(k).second;
+ }
+
+ mapped_type const& at(const key_type& k) const
+ {
+ return table_.at(k).second;
+ }
+
+ // lookup
+
+ iterator find(const key_type& k)
+ {
+ return iterator(table_.find(k));
+ }
+
+ const_iterator find(const key_type& k) const
+ {
+ return const_iterator(table_.find(k));
+ }
+
+ template <class CompatibleKey, class CompatibleHash,
+ class CompatiblePredicate>
+ iterator find(
+ CompatibleKey const& k,
+ CompatibleHash const& hash,
+ CompatiblePredicate const& eq)
+ {
+ return iterator(table_.find(k, hash, eq));
+ }
+
+ template <class CompatibleKey, class CompatibleHash,
+ class CompatiblePredicate>
+ const_iterator find(
+ CompatibleKey const& k,
+ CompatibleHash const& hash,
+ CompatiblePredicate const& eq) const
+ {
+ return iterator(table_.find(k, hash, eq));
+ }
+
+ size_type count(const key_type& k) const
+ {
+ return table_.count(k);
+ }
+
+ std::pair<iterator, iterator>
+ equal_range(const key_type& k)
+ {
+ return boost::unordered_detail::pair_cast<
+ iterator, iterator>(
+ table_.equal_range(k));
+ }
+
+ std::pair<const_iterator, const_iterator>
+ equal_range(const key_type& k) const
+ {
+ return boost::unordered_detail::pair_cast<
+ const_iterator, const_iterator>(
+ table_.equal_range(k));
+ }
+
+ // bucket interface
+
+ size_type bucket_count() const
+ {
+ return table_.bucket_count_;
+ }
+
+ size_type max_bucket_count() const
+ {
+ return table_.max_bucket_count();
+ }
+
+ size_type bucket_size(size_type n) const
+ {
+ return table_.bucket_size(n);
+ }
+
+ size_type bucket(const key_type& k) const
+ {
+ return table_.bucket_index(k);
+ }
+
+ local_iterator begin(size_type n)
+ {
+ return local_iterator(table_.bucket_begin(n));
+ }
+
+ const_local_iterator begin(size_type n) const
+ {
+ return const_local_iterator(table_.bucket_begin(n));
+ }
+
+ local_iterator end(size_type)
+ {
+ return local_iterator();
+ }
+
+ const_local_iterator end(size_type) const
+ {
+ return const_local_iterator();
+ }
+
+ const_local_iterator cbegin(size_type n) const
+ {
+ return const_local_iterator(table_.bucket_begin(n));
+ }
+
+ const_local_iterator cend(size_type) const
+ {
+ return const_local_iterator();
+ }
+
+ // hash policy
+
+ float load_factor() const
+ {
+ return table_.load_factor();
+ }
+
+ float max_load_factor() const
+ {
+ return table_.mlf_;
+ }
+
+ void max_load_factor(float m)
+ {
+ table_.max_load_factor(m);
+ }
+
+ void rehash(size_type n)
+ {
+ table_.rehash(n);
+ }
+
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
+ friend bool operator==<K, T, H, P, A>(
+ unordered_map const&, unordered_map const&);
+ friend bool operator!=<K, T, H, P, A>(
+ unordered_map const&, unordered_map const&);
+#endif
+ }; // class template unordered_map
+
+ template <class K, class T, class H, class P, class A>
+ inline bool operator==(unordered_map<K, T, H, P, A> const& m1,
+ unordered_map<K, T, H, P, A> const& m2)
+ {
+#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
+ struct dummy { unordered_map<K,T,H,P,A> x; };
+#endif
+ return m1.table_.equals(m2.table_);
+ }
+
+ template <class K, class T, class H, class P, class A>
+ inline bool operator!=(unordered_map<K, T, H, P, A> const& m1,
+ unordered_map<K, T, H, P, A> const& m2)
+ {
+#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
+ struct dummy { unordered_map<K,T,H,P,A> x; };
+#endif
+ return !m1.table_.equals(m2.table_);
+ }
+
+ template <class K, class T, class H, class P, class A>
+ inline void swap(unordered_map<K, T, H, P, A> &m1,
+ unordered_map<K, T, H, P, A> &m2)
+ {
+#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
+ struct dummy { unordered_map<K,T,H,P,A> x; };
+#endif
+ m1.swap(m2);
+ }
+
+ template <class K, class T, class H, class P, class A>
+ class unordered_multimap
+ {
+ public:
+
+ typedef K key_type;
+ typedef std::pair<const K, T> value_type;
+ typedef T mapped_type;
+ typedef H hasher;
+ typedef P key_equal;
+ typedef A allocator_type;
+
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
+ private:
+#endif
+
+ typedef BOOST_DEDUCED_TYPENAME
+ boost::unordered_detail::rebind_wrap<
+ allocator_type, value_type>::type
+ value_allocator;
+
+ typedef boost::unordered_detail::multimap<K, H, P,
+ value_allocator> types;
+ typedef BOOST_DEDUCED_TYPENAME types::impl table;
+
+ typedef BOOST_DEDUCED_TYPENAME types::iterator_base iterator_base;
+
+ public:
+
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::pointer pointer;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::const_pointer const_pointer;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::reference reference;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::const_reference const_reference;
+
+ typedef std::size_t size_type;
+ typedef std::ptrdiff_t difference_type;
+
+ typedef boost::unordered_detail::hash_const_local_iterator<
+ value_allocator, boost::unordered_detail::grouped>
+ const_local_iterator;
+ typedef boost::unordered_detail::hash_local_iterator<
+ value_allocator, boost::unordered_detail::grouped>
+ local_iterator;
+ typedef boost::unordered_detail::hash_const_iterator<
+ value_allocator, boost::unordered_detail::grouped>
+ const_iterator;
+ typedef boost::unordered_detail::hash_iterator<
+ value_allocator, boost::unordered_detail::grouped>
+ iterator;
+
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
+ private:
+#endif
+
+ table table_;
+
+ BOOST_DEDUCED_TYPENAME types::iterator_base const&
+ get(const_iterator const& it)
+ {
+ return boost::unordered_detail::iterator_access::get(it);
+ }
+
+ public:
+
+ // construct/destroy/copy
+
+ explicit unordered_multimap(
+ size_type n = boost::unordered_detail::default_bucket_count,
+ const hasher &hf = hasher(),
+ const key_equal &eql = key_equal(),
+ const allocator_type &a = allocator_type())
+ : table_(n, hf, eql, a)
+ {
+ }
+
+ explicit unordered_multimap(allocator_type const& a)
+ : table_(boost::unordered_detail::default_bucket_count,
+ hasher(), key_equal(), a)
+ {
+ }
+
+ unordered_multimap(unordered_multimap const& other,
+ allocator_type const& a)
+ : table_(other.table_, a)
+ {
+ }
+
+ template <class InputIt>
+ unordered_multimap(InputIt f, InputIt l)
+ : table_(boost::unordered_detail::initial_size(f, l),
+ hasher(), key_equal(), allocator_type())
+ {
+ table_.insert_range(f, l);
+ }
+
+ template <class InputIt>
+ unordered_multimap(InputIt f, InputIt l,
+ size_type n,
+ const hasher &hf = hasher(),
+ const key_equal &eql = key_equal())
+ : table_(boost::unordered_detail::initial_size(f, l, n),
+ hf, eql, allocator_type())
+ {
+ table_.insert_range(f, l);
+ }
+
+ template <class InputIt>
+ unordered_multimap(InputIt f, InputIt l,
+ size_type n,
+ const hasher &hf,
+ const key_equal &eql,
+ const allocator_type &a)
+ : table_(boost::unordered_detail::initial_size(f, l, n), hf, eql, a)
+ {
+ table_.insert_range(f, l);
+ }
+
+ ~unordered_multimap() {}
+
+#if !defined(BOOST_NO_RVALUE_REFERENCES)
+ unordered_multimap(unordered_multimap&& other)
+ : table_(other.table_, boost::unordered_detail::move_tag())
+ {
+ }
+
+ unordered_multimap(unordered_multimap&& other, allocator_type const& a)
+ : table_(other.table_, a, boost::unordered_detail::move_tag())
+ {
+ }
+
+ unordered_multimap& operator=(unordered_multimap&& x)
+ {
+ table_.move(x.table_);
+ return *this;
+ }
+#else
+ unordered_multimap(boost::unordered_detail::move_from<
+ unordered_multimap<K, T, H, P, A>
+ > other)
+ : table_(other.source.table_, boost::unordered_detail::move_tag())
+ {
+ }
+
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0593)
+ unordered_multimap& operator=(unordered_multimap x)
+ {
+ table_.move(x.table_);
+ return *this;
+ }
+#endif
+#endif
+
+#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
+ unordered_multimap(std::initializer_list<value_type> list,
+ size_type n = boost::unordered_detail::default_bucket_count,
+ const hasher &hf = hasher(),
+ const key_equal &eql = key_equal(),
+ const allocator_type &a = allocator_type())
+ : table_(boost::unordered_detail::initial_size(
+ list.begin(), list.end(), n),
+ hf, eql, a)
+ {
+ table_.insert_range(list.begin(), list.end());
+ }
+
+ unordered_multimap& operator=(std::initializer_list<value_type> list)
+ {
+ table_.clear();
+ table_.insert_range(list.begin(), list.end());
+ return *this;
+ }
+#endif
+
+ allocator_type get_allocator() const
+ {
+ return table_.node_alloc();
+ }
+
+ // size and capacity
+
+ bool empty() const
+ {
+ return table_.size_ == 0;
+ }
+
+ size_type size() const
+ {
+ return table_.size_;
+ }
+
+ size_type max_size() const
+ {
+ return table_.max_size();
+ }
+
+ // iterators
+
+ iterator begin()
+ {
+ return iterator(table_.begin());
+ }
+
+ const_iterator begin() const
+ {
+ return const_iterator(table_.begin());
+ }
+
+ iterator end()
+ {
+ return iterator(table_.end());
+ }
+
+ const_iterator end() const
+ {
+ return const_iterator(table_.end());
+ }
+
+ const_iterator cbegin() const
+ {
+ return const_iterator(table_.begin());
+ }
+
+ const_iterator cend() const
+ {
+ return const_iterator(table_.end());
+ }
+
+ // modifiers
+
+#if defined(BOOST_UNORDERED_STD_FORWARD)
+ template <class... Args>
+ iterator emplace(Args&&... args)
+ {
+ return iterator(table_.emplace(std::forward<Args>(args)...));
+ }
+
+ template <class... Args>
+ iterator emplace_hint(const_iterator, Args&&... args)
+ {
+ return iterator(table_.emplace(std::forward<Args>(args)...));
+ }
+#else
+
+ #if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100))
+ iterator emplace(value_type const& v = value_type())
+ {
+ return iterator(table_.emplace(v));
+ }
+
+ iterator emplace_hint(const_iterator,
+ value_type const& v = value_type())
+ {
+ return iterator(table_.emplace(v));
+ }
+ #endif
+
+#define BOOST_UNORDERED_EMPLACE(z, n, _) \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ iterator emplace( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
+ ) \
+ { \
+ return iterator( \
+ table_.emplace( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n) \
+ )); \
+ } \
+ \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ iterator emplace_hint(const_iterator, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
+ ) \
+ { \
+ return iterator(table_.emplace( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n) \
+ )); \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_EMPLACE, _)
+
+#undef BOOST_UNORDERED_EMPLACE
+
+#endif
+
+ iterator insert(const value_type& obj)
+ {
+ return iterator(table_.emplace(obj));
+ }
+
+ iterator insert(const_iterator, const value_type& obj)
+ {
+ return iterator(table_.emplace(obj));
+ }
+
+ template <class InputIt>
+ void insert(InputIt first, InputIt last)
+ {
+ table_.insert_range(first, last);
+ }
+
+#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
+ void insert(std::initializer_list<value_type> list)
+ {
+ table_.insert_range(list.begin(), list.end());
+ }
+#endif
+
+ iterator erase(const_iterator position)
+ {
+ return iterator(table_.erase_return_iterator(get(position)));
+ }
+
+ size_type erase(const key_type& k)
+ {
+ return table_.erase_key(k);
+ }
+
+ iterator erase(const_iterator first, const_iterator last)
+ {
+ return iterator(table_.erase_range(get(first), get(last)));
+ }
+
+ void quick_erase(const_iterator position)
+ {
+ table_.erase(get(position));
+ }
+
+ void erase_return_void(const_iterator position)
+ {
+ table_.erase(get(position));
+ }
+
+ void clear()
+ {
+ table_.clear();
+ }
+
+ void swap(unordered_multimap& other)
+ {
+ table_.swap(other.table_);
+ }
+
+ // observers
+
+ hasher hash_function() const
+ {
+ return table_.hash_function();
+ }
+
+ key_equal key_eq() const
+ {
+ return table_.key_eq();
+ }
+
+ // lookup
+
+ iterator find(const key_type& k)
+ {
+ return iterator(table_.find(k));
+ }
+
+ const_iterator find(const key_type& k) const
+ {
+ return const_iterator(table_.find(k));
+ }
+
+ template <class CompatibleKey, class CompatibleHash,
+ class CompatiblePredicate>
+ iterator find(
+ CompatibleKey const& k,
+ CompatibleHash const& hash,
+ CompatiblePredicate const& eq)
+ {
+ return iterator(table_.find(k, hash, eq));
+ }
+
+ template <class CompatibleKey, class CompatibleHash,
+ class CompatiblePredicate>
+ const_iterator find(
+ CompatibleKey const& k,
+ CompatibleHash const& hash,
+ CompatiblePredicate const& eq) const
+ {
+ return iterator(table_.find(k, hash, eq));
+ }
+
+ size_type count(const key_type& k) const
+ {
+ return table_.count(k);
+ }
+
+ std::pair<iterator, iterator>
+ equal_range(const key_type& k)
+ {
+ return boost::unordered_detail::pair_cast<
+ iterator, iterator>(
+ table_.equal_range(k));
+ }
+
+ std::pair<const_iterator, const_iterator>
+ equal_range(const key_type& k) const
+ {
+ return boost::unordered_detail::pair_cast<
+ const_iterator, const_iterator>(
+ table_.equal_range(k));
+ }
+
+ // bucket interface
+
+ size_type bucket_count() const
+ {
+ return table_.bucket_count_;
+ }
+
+ size_type max_bucket_count() const
+ {
+ return table_.max_bucket_count();
+ }
+
+ size_type bucket_size(size_type n) const
+ {
+ return table_.bucket_size(n);
+ }
+
+ size_type bucket(const key_type& k) const
+ {
+ return table_.bucket_index(k);
+ }
+
+ local_iterator begin(size_type n)
+ {
+ return local_iterator(table_.bucket_begin(n));
+ }
+
+ const_local_iterator begin(size_type n) const
+ {
+ return const_local_iterator(table_.bucket_begin(n));
+ }
+
+ local_iterator end(size_type)
+ {
+ return local_iterator();
+ }
+
+ const_local_iterator end(size_type) const
+ {
+ return const_local_iterator();
+ }
+
+ const_local_iterator cbegin(size_type n) const
+ {
+ return const_local_iterator(table_.bucket_begin(n));
+ }
+
+ const_local_iterator cend(size_type) const
+ {
+ return const_local_iterator();
+ }
+
+ // hash policy
+
+ float load_factor() const
+ {
+ return table_.load_factor();
+ }
+
+ float max_load_factor() const
+ {
+ return table_.mlf_;
+ }
+
+ void max_load_factor(float m)
+ {
+ table_.max_load_factor(m);
+ }
+
+ void rehash(size_type n)
+ {
+ table_.rehash(n);
+ }
+
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
+ friend bool operator==<K, T, H, P, A>(
+ unordered_multimap const&, unordered_multimap const&);
+ friend bool operator!=<K, T, H, P, A>(
+ unordered_multimap const&, unordered_multimap const&);
+#endif
+ }; // class template unordered_multimap
+
+ template <class K, class T, class H, class P, class A>
+ inline bool operator==(unordered_multimap<K, T, H, P, A> const& m1,
+ unordered_multimap<K, T, H, P, A> const& m2)
+ {
+#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
+ struct dummy { unordered_multimap<K,T,H,P,A> x; };
+#endif
+ return m1.table_.equals(m2.table_);
+ }
+
+ template <class K, class T, class H, class P, class A>
+ inline bool operator!=(unordered_multimap<K, T, H, P, A> const& m1,
+ unordered_multimap<K, T, H, P, A> const& m2)
+ {
+#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
+ struct dummy { unordered_multimap<K,T,H,P,A> x; };
+#endif
+ return !m1.table_.equals(m2.table_);
+ }
+
+ template <class K, class T, class H, class P, class A>
+ inline void swap(unordered_multimap<K, T, H, P, A> &m1,
+ unordered_multimap<K, T, H, P, A> &m2)
+ {
+#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
+ struct dummy { unordered_multimap<K,T,H,P,A> x; };
+#endif
+ m1.swap(m2);
+ }
+
+} // namespace boost
+
+#if defined(BOOST_MSVC)
+#pragma warning(pop)
+#endif
+
+#endif // BOOST_UNORDERED_UNORDERED_MAP_HPP_INCLUDED
diff --git a/3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp b/3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp
new file mode 100644
index 0000000..5e9bb07
--- /dev/null
+++ b/3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp
@@ -0,0 +1,53 @@
+
+// Copyright (C) 2008-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_MAP_FWD_HPP_INCLUDED
+#define BOOST_UNORDERED_MAP_FWD_HPP_INCLUDED
+
+#if defined(_MSC_VER) && (_MSC_VER >= 1020)
+# pragma once
+#endif
+
+#include <boost/config.hpp>
+#include <memory>
+#include <functional>
+#include <boost/functional/hash_fwd.hpp>
+
+namespace boost
+{
+ template <class K,
+ class T,
+ class H = hash<K>,
+ class P = std::equal_to<K>,
+ class A = std::allocator<std::pair<const K, T> > >
+ class unordered_map;
+ template <class K, class T, class H, class P, class A>
+ bool operator==(unordered_map<K, T, H, P, A> const&,
+ unordered_map<K, T, H, P, A> const&);
+ template <class K, class T, class H, class P, class A>
+ bool operator!=(unordered_map<K, T, H, P, A> const&,
+ unordered_map<K, T, H, P, A> const&);
+ template <class K, class T, class H, class P, class A>
+ void swap(unordered_map<K, T, H, P, A>&,
+ unordered_map<K, T, H, P, A>&);
+
+ template <class K,
+ class T,
+ class H = hash<K>,
+ class P = std::equal_to<K>,
+ class A = std::allocator<std::pair<const K, T> > >
+ class unordered_multimap;
+ template <class K, class T, class H, class P, class A>
+ bool operator==(unordered_multimap<K, T, H, P, A> const&,
+ unordered_multimap<K, T, H, P, A> const&);
+ template <class K, class T, class H, class P, class A>
+ bool operator!=(unordered_multimap<K, T, H, P, A> const&,
+ unordered_multimap<K, T, H, P, A> const&);
+ template <class K, class T, class H, class P, class A>
+ void swap(unordered_multimap<K, T, H, P, A>&,
+ unordered_multimap<K, T, H, P, A>&);
+}
+
+#endif