Swift
summaryrefslogtreecommitdiffstats
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
parentb75cf274d8c3cf255fd1d8932a9f6a6cfa8cb9b4 (diff)
downloadswift-contrib-b734b6a5986703b6b10ea548c93af11f9df771bf.zip
swift-contrib-b734b6a5986703b6b10ea548c93af11f9df771bf.tar.bz2
Cache stringprep results for JIDs.
Diffstat
-rw-r--r--3rdParty/Boost/src/boost/compressed_pair.hpp24
-rw-r--r--3rdParty/Boost/src/boost/detail/allocator_utilities.hpp212
-rw-r--r--3rdParty/Boost/src/boost/detail/compressed_pair.hpp443
-rw-r--r--3rdParty/Boost/src/boost/detail/ob_compressed_pair.hpp510
-rw-r--r--3rdParty/Boost/src/boost/functional/hash_fwd.hpp7
-rw-r--r--3rdParty/Boost/src/boost/type_traits/object_traits.hpp33
-rw-r--r--3rdParty/Boost/src/boost/type_traits/same_traits.hpp15
-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
-rw-r--r--3rdParty/Boost/src/boost/unordered_map.hpp18
-rwxr-xr-x3rdParty/Boost/update.sh1
-rw-r--r--Swiften/JID/JID.cpp39
22 files changed, 6165 insertions, 1 deletions
diff --git a/3rdParty/Boost/src/boost/compressed_pair.hpp b/3rdParty/Boost/src/boost/compressed_pair.hpp
new file mode 100644
index 0000000..e6cd6a0
--- /dev/null
+++ b/3rdParty/Boost/src/boost/compressed_pair.hpp
@@ -0,0 +1,24 @@
+// (C) Copyright Steve Cleary, Beman Dawes, Howard Hinnant & John Maddock 2000.
+// 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).
+//
+// See http://www.boost.org/libs/utility for most recent version including documentation.
+
+// See boost/detail/compressed_pair.hpp and boost/detail/ob_compressed_pair.hpp
+// for full copyright notices.
+
+#ifndef BOOST_COMPRESSED_PAIR_HPP
+#define BOOST_COMPRESSED_PAIR_HPP
+
+#ifndef BOOST_CONFIG_HPP
+#include <boost/config.hpp>
+#endif
+
+#ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+#include <boost/detail/ob_compressed_pair.hpp>
+#else
+#include <boost/detail/compressed_pair.hpp>
+#endif
+
+#endif // BOOST_COMPRESSED_PAIR_HPP
diff --git a/3rdParty/Boost/src/boost/detail/allocator_utilities.hpp b/3rdParty/Boost/src/boost/detail/allocator_utilities.hpp
new file mode 100644
index 0000000..5d6ef48
--- /dev/null
+++ b/3rdParty/Boost/src/boost/detail/allocator_utilities.hpp
@@ -0,0 +1,212 @@
+/* Copyright 2003-2009 Joaquin M Lopez Munoz.
+ * 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 Boost website at http://www.boost.org/
+ */
+
+#ifndef BOOST_DETAIL_ALLOCATOR_UTILITIES_HPP
+#define BOOST_DETAIL_ALLOCATOR_UTILITIES_HPP
+
+#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
+#include <boost/detail/workaround.hpp>
+#include <boost/mpl/aux_/msvc_never_true.hpp>
+#include <boost/mpl/eval_if.hpp>
+#include <boost/type_traits/is_same.hpp>
+#include <cstddef>
+#include <memory>
+#include <new>
+
+namespace boost{
+
+namespace detail{
+
+/* Allocator adaption layer. Some stdlibs provide allocators without rebind
+ * and template ctors. These facilities are simulated with the external
+ * template class rebind_to and the aid of partial_std_allocator_wrapper.
+ */
+
+namespace allocator{
+
+/* partial_std_allocator_wrapper inherits the functionality of a std
+ * allocator while providing a templatized ctor and other bits missing
+ * in some stdlib implementation or another.
+ */
+
+template<typename Type>
+class partial_std_allocator_wrapper:public std::allocator<Type>
+{
+public:
+ /* Oddly enough, STLport does not define std::allocator<void>::value_type
+ * when configured to work without partial template specialization.
+ * No harm in supplying the definition here unconditionally.
+ */
+
+ typedef Type value_type;
+
+ partial_std_allocator_wrapper(){};
+
+ template<typename Other>
+ partial_std_allocator_wrapper(const partial_std_allocator_wrapper<Other>&){}
+
+ partial_std_allocator_wrapper(const std::allocator<Type>& x):
+ std::allocator<Type>(x)
+ {
+ };
+
+#if defined(BOOST_DINKUMWARE_STDLIB)
+ /* Dinkumware guys didn't provide a means to call allocate() without
+ * supplying a hint, in disagreement with the standard.
+ */
+
+ Type* allocate(std::size_t n,const void* hint=0)
+ {
+ std::allocator<Type>& a=*this;
+ return a.allocate(n,hint);
+ }
+#endif
+
+};
+
+/* Detects whether a given allocator belongs to a defective stdlib not
+ * having the required member templates.
+ * Note that it does not suffice to check the Boost.Config stdlib
+ * macros, as the user might have passed a custom, compliant allocator.
+ * The checks also considers partial_std_allocator_wrapper to be
+ * a standard defective allocator.
+ */
+
+#if defined(BOOST_NO_STD_ALLOCATOR)&&\
+ (defined(BOOST_HAS_PARTIAL_STD_ALLOCATOR)||defined(BOOST_DINKUMWARE_STDLIB))
+
+template<typename Allocator>
+struct is_partial_std_allocator
+{
+ BOOST_STATIC_CONSTANT(bool,
+ value=
+ (is_same<
+ std::allocator<BOOST_DEDUCED_TYPENAME Allocator::value_type>,
+ Allocator
+ >::value)||
+ (is_same<
+ partial_std_allocator_wrapper<
+ BOOST_DEDUCED_TYPENAME Allocator::value_type>,
+ Allocator
+ >::value));
+};
+
+#else
+
+template<typename Allocator>
+struct is_partial_std_allocator
+{
+ BOOST_STATIC_CONSTANT(bool,value=false);
+};
+
+#endif
+
+/* rebind operations for defective std allocators */
+
+template<typename Allocator,typename Type>
+struct partial_std_allocator_rebind_to
+{
+ typedef partial_std_allocator_wrapper<Type> type;
+};
+
+/* rebind operation in all other cases */
+
+#if BOOST_WORKAROUND(BOOST_MSVC,<1300)
+/* Workaround for a problem in MSVC with dependent template typedefs
+ * when doing rebinding of allocators.
+ * Modeled after <boost/mpl/aux_/msvc_dtw.hpp> (thanks, Aleksey!)
+ */
+
+template<typename Allocator>
+struct rebinder
+{
+ template<bool> struct fake_allocator:Allocator{};
+ template<> struct fake_allocator<true>
+ {
+ template<typename Type> struct rebind{};
+ };
+
+ template<typename Type>
+ struct result:
+ fake_allocator<mpl::aux::msvc_never_true<Allocator>::value>::
+ template rebind<Type>
+ {
+ };
+};
+#else
+template<typename Allocator>
+struct rebinder
+{
+ template<typename Type>
+ struct result
+ {
+ typedef typename Allocator::BOOST_NESTED_TEMPLATE
+ rebind<Type>::other other;
+ };
+};
+#endif
+
+template<typename Allocator,typename Type>
+struct compliant_allocator_rebind_to
+{
+ typedef typename rebinder<Allocator>::
+ BOOST_NESTED_TEMPLATE result<Type>::other type;
+};
+
+/* rebind front-end */
+
+template<typename Allocator,typename Type>
+struct rebind_to:
+ mpl::eval_if_c<
+ is_partial_std_allocator<Allocator>::value,
+ partial_std_allocator_rebind_to<Allocator,Type>,
+ compliant_allocator_rebind_to<Allocator,Type>
+ >
+{
+};
+
+/* allocator-independent versions of construct and destroy */
+
+template<typename Type>
+void construct(void* p,const Type& t)
+{
+ new (p) Type(t);
+}
+
+#if BOOST_WORKAROUND(BOOST_MSVC,BOOST_TESTED_AT(1500))
+/* MSVC++ issues spurious warnings about unreferencend formal parameters
+ * in destroy<Type> when Type is a class with trivial dtor.
+ */
+
+#pragma warning(push)
+#pragma warning(disable:4100)
+#endif
+
+template<typename Type>
+void destroy(const Type* p)
+{
+
+#if BOOST_WORKAROUND(__SUNPRO_CC,BOOST_TESTED_AT(0x590))
+ const_cast<Type*>(p)->~Type();
+#else
+ p->~Type();
+#endif
+
+}
+
+#if BOOST_WORKAROUND(BOOST_MSVC,BOOST_TESTED_AT(1500))
+#pragma warning(pop)
+#endif
+
+} /* namespace boost::detail::allocator */
+
+} /* namespace boost::detail */
+
+} /* namespace boost */
+
+#endif
diff --git a/3rdParty/Boost/src/boost/detail/compressed_pair.hpp b/3rdParty/Boost/src/boost/detail/compressed_pair.hpp
new file mode 100644
index 0000000..3f32645
--- /dev/null
+++ b/3rdParty/Boost/src/boost/detail/compressed_pair.hpp
@@ -0,0 +1,443 @@
+// (C) Copyright Steve Cleary, Beman Dawes, Howard Hinnant & John Maddock 2000.
+// 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).
+//
+// See http://www.boost.org/libs/utility for most recent version including documentation.
+
+// compressed_pair: pair that "compresses" empty members
+// (see libs/utility/compressed_pair.htm)
+//
+// JM changes 25 Jan 2004:
+// For the case where T1 == T2 and both are empty, then first() and second()
+// should return different objects.
+// JM changes 25 Jan 2000:
+// Removed default arguments from compressed_pair_switch to get
+// C++ Builder 4 to accept them
+// rewriten swap to get gcc and C++ builder to compile.
+// added partial specialisations for case T1 == T2 to avoid duplicate constructor defs.
+
+#ifndef BOOST_DETAIL_COMPRESSED_PAIR_HPP
+#define BOOST_DETAIL_COMPRESSED_PAIR_HPP
+
+#include <algorithm>
+
+#include <boost/type_traits/remove_cv.hpp>
+#include <boost/type_traits/is_empty.hpp>
+#include <boost/type_traits/is_same.hpp>
+#include <boost/call_traits.hpp>
+
+#ifdef BOOST_MSVC
+# pragma warning(push)
+# pragma warning(disable:4512)
+#endif
+namespace boost
+{
+
+template <class T1, class T2>
+class compressed_pair;
+
+
+// compressed_pair
+
+namespace details
+{
+ // JM altered 26 Jan 2000:
+ template <class T1, class T2, bool IsSame, bool FirstEmpty, bool SecondEmpty>
+ struct compressed_pair_switch;
+
+ template <class T1, class T2>
+ struct compressed_pair_switch<T1, T2, false, false, false>
+ {static const int value = 0;};
+
+ template <class T1, class T2>
+ struct compressed_pair_switch<T1, T2, false, true, true>
+ {static const int value = 3;};
+
+ template <class T1, class T2>
+ struct compressed_pair_switch<T1, T2, false, true, false>
+ {static const int value = 1;};
+
+ template <class T1, class T2>
+ struct compressed_pair_switch<T1, T2, false, false, true>
+ {static const int value = 2;};
+
+ template <class T1, class T2>
+ struct compressed_pair_switch<T1, T2, true, true, true>
+ {static const int value = 4;};
+
+ template <class T1, class T2>
+ struct compressed_pair_switch<T1, T2, true, false, false>
+ {static const int value = 5;};
+
+ template <class T1, class T2, int Version> class compressed_pair_imp;
+
+#ifdef __GNUC__
+ // workaround for GCC (JM):
+ using std::swap;
+#endif
+ //
+ // can't call unqualified swap from within classname::swap
+ // as Koenig lookup rules will find only the classname::swap
+ // member function not the global declaration, so use cp_swap
+ // as a forwarding function (JM):
+ template <typename T>
+ inline void cp_swap(T& t1, T& t2)
+ {
+#ifndef __GNUC__
+ using std::swap;
+#endif
+ swap(t1, t2);
+ }
+
+ // 0 derive from neither
+
+ template <class T1, class T2>
+ class compressed_pair_imp<T1, T2, 0>
+ {
+ public:
+ typedef T1 first_type;
+ typedef T2 second_type;
+ typedef typename call_traits<first_type>::param_type first_param_type;
+ typedef typename call_traits<second_type>::param_type second_param_type;
+ typedef typename call_traits<first_type>::reference first_reference;
+ typedef typename call_traits<second_type>::reference second_reference;
+ typedef typename call_traits<first_type>::const_reference first_const_reference;
+ typedef typename call_traits<second_type>::const_reference second_const_reference;
+
+ compressed_pair_imp() {}
+
+ compressed_pair_imp(first_param_type x, second_param_type y)
+ : first_(x), second_(y) {}
+
+ compressed_pair_imp(first_param_type x)
+ : first_(x) {}
+
+ compressed_pair_imp(second_param_type y)
+ : second_(y) {}
+
+ first_reference first() {return first_;}
+ first_const_reference first() const {return first_;}
+
+ second_reference second() {return second_;}
+ second_const_reference second() const {return second_;}
+
+ void swap(::boost::compressed_pair<T1, T2>& y)
+ {
+ cp_swap(first_, y.first());
+ cp_swap(second_, y.second());
+ }
+ private:
+ first_type first_;
+ second_type second_;
+ };
+
+ // 1 derive from T1
+
+ template <class T1, class T2>
+ class compressed_pair_imp<T1, T2, 1>
+ : protected ::boost::remove_cv<T1>::type
+ {
+ public:
+ typedef T1 first_type;
+ typedef T2 second_type;
+ typedef typename call_traits<first_type>::param_type first_param_type;
+ typedef typename call_traits<second_type>::param_type second_param_type;
+ typedef typename call_traits<first_type>::reference first_reference;
+ typedef typename call_traits<second_type>::reference second_reference;
+ typedef typename call_traits<first_type>::const_reference first_const_reference;
+ typedef typename call_traits<second_type>::const_reference second_const_reference;
+
+ compressed_pair_imp() {}
+
+ compressed_pair_imp(first_param_type x, second_param_type y)
+ : first_type(x), second_(y) {}
+
+ compressed_pair_imp(first_param_type x)
+ : first_type(x) {}
+
+ compressed_pair_imp(second_param_type y)
+ : second_(y) {}
+
+ first_reference first() {return *this;}
+ first_const_reference first() const {return *this;}
+
+ second_reference second() {return second_;}
+ second_const_reference second() const {return second_;}
+
+ void swap(::boost::compressed_pair<T1,T2>& y)
+ {
+ // no need to swap empty base class:
+ cp_swap(second_, y.second());
+ }
+ private:
+ second_type second_;
+ };
+
+ // 2 derive from T2
+
+ template <class T1, class T2>
+ class compressed_pair_imp<T1, T2, 2>
+ : protected ::boost::remove_cv<T2>::type
+ {
+ public:
+ typedef T1 first_type;
+ typedef T2 second_type;
+ typedef typename call_traits<first_type>::param_type first_param_type;
+ typedef typename call_traits<second_type>::param_type second_param_type;
+ typedef typename call_traits<first_type>::reference first_reference;
+ typedef typename call_traits<second_type>::reference second_reference;
+ typedef typename call_traits<first_type>::const_reference first_const_reference;
+ typedef typename call_traits<second_type>::const_reference second_const_reference;
+
+ compressed_pair_imp() {}
+
+ compressed_pair_imp(first_param_type x, second_param_type y)
+ : second_type(y), first_(x) {}
+
+ compressed_pair_imp(first_param_type x)
+ : first_(x) {}
+
+ compressed_pair_imp(second_param_type y)
+ : second_type(y) {}
+
+ first_reference first() {return first_;}
+ first_const_reference first() const {return first_;}
+
+ second_reference second() {return *this;}
+ second_const_reference second() const {return *this;}
+
+ void swap(::boost::compressed_pair<T1,T2>& y)
+ {
+ // no need to swap empty base class:
+ cp_swap(first_, y.first());
+ }
+
+ private:
+ first_type first_;
+ };
+
+ // 3 derive from T1 and T2
+
+ template <class T1, class T2>
+ class compressed_pair_imp<T1, T2, 3>
+ : protected ::boost::remove_cv<T1>::type,
+ protected ::boost::remove_cv<T2>::type
+ {
+ public:
+ typedef T1 first_type;
+ typedef T2 second_type;
+ typedef typename call_traits<first_type>::param_type first_param_type;
+ typedef typename call_traits<second_type>::param_type second_param_type;
+ typedef typename call_traits<first_type>::reference first_reference;
+ typedef typename call_traits<second_type>::reference second_reference;
+ typedef typename call_traits<first_type>::const_reference first_const_reference;
+ typedef typename call_traits<second_type>::const_reference second_const_reference;
+
+ compressed_pair_imp() {}
+
+ compressed_pair_imp(first_param_type x, second_param_type y)
+ : first_type(x), second_type(y) {}
+
+ compressed_pair_imp(first_param_type x)
+ : first_type(x) {}
+
+ compressed_pair_imp(second_param_type y)
+ : second_type(y) {}
+
+ first_reference first() {return *this;}
+ first_const_reference first() const {return *this;}
+
+ second_reference second() {return *this;}
+ second_const_reference second() const {return *this;}
+ //
+ // no need to swap empty bases:
+ void swap(::boost::compressed_pair<T1,T2>&) {}
+ };
+
+ // JM
+ // 4 T1 == T2, T1 and T2 both empty
+ // Originally this did not store an instance of T2 at all
+ // but that led to problems beause it meant &x.first() == &x.second()
+ // which is not true for any other kind of pair, so now we store an instance
+ // of T2 just in case the user is relying on first() and second() returning
+ // different objects (albeit both empty).
+ template <class T1, class T2>
+ class compressed_pair_imp<T1, T2, 4>
+ : protected ::boost::remove_cv<T1>::type
+ {
+ public:
+ typedef T1 first_type;
+ typedef T2 second_type;
+ typedef typename call_traits<first_type>::param_type first_param_type;
+ typedef typename call_traits<second_type>::param_type second_param_type;
+ typedef typename call_traits<first_type>::reference first_reference;
+ typedef typename call_traits<second_type>::reference second_reference;
+ typedef typename call_traits<first_type>::const_reference first_const_reference;
+ typedef typename call_traits<second_type>::const_reference second_const_reference;
+
+ compressed_pair_imp() {}
+
+ compressed_pair_imp(first_param_type x, second_param_type y)
+ : first_type(x), m_second(y) {}
+
+ compressed_pair_imp(first_param_type x)
+ : first_type(x), m_second(x) {}
+
+ first_reference first() {return *this;}
+ first_const_reference first() const {return *this;}
+
+ second_reference second() {return m_second;}
+ second_const_reference second() const {return m_second;}
+
+ void swap(::boost::compressed_pair<T1,T2>&) {}
+ private:
+ T2 m_second;
+ };
+
+ // 5 T1 == T2 and are not empty: //JM
+
+ template <class T1, class T2>
+ class compressed_pair_imp<T1, T2, 5>
+ {
+ public:
+ typedef T1 first_type;
+ typedef T2 second_type;
+ typedef typename call_traits<first_type>::param_type first_param_type;
+ typedef typename call_traits<second_type>::param_type second_param_type;
+ typedef typename call_traits<first_type>::reference first_reference;
+ typedef typename call_traits<second_type>::reference second_reference;
+ typedef typename call_traits<first_type>::const_reference first_const_reference;
+ typedef typename call_traits<second_type>::const_reference second_const_reference;
+
+ compressed_pair_imp() {}
+
+ compressed_pair_imp(first_param_type x, second_param_type y)
+ : first_(x), second_(y) {}
+
+ compressed_pair_imp(first_param_type x)
+ : first_(x), second_(x) {}
+
+ first_reference first() {return first_;}
+ first_const_reference first() const {return first_;}
+
+ second_reference second() {return second_;}
+ second_const_reference second() const {return second_;}
+
+ void swap(::boost::compressed_pair<T1, T2>& y)
+ {
+ cp_swap(first_, y.first());
+ cp_swap(second_, y.second());
+ }
+ private:
+ first_type first_;
+ second_type second_;
+ };
+
+} // details
+
+template <class T1, class T2>
+class compressed_pair
+ : private ::boost::details::compressed_pair_imp<T1, T2,
+ ::boost::details::compressed_pair_switch<
+ T1,
+ T2,
+ ::boost::is_same<typename remove_cv<T1>::type, typename remove_cv<T2>::type>::value,
+ ::boost::is_empty<T1>::value,
+ ::boost::is_empty<T2>::value>::value>
+{
+private:
+ typedef details::compressed_pair_imp<T1, T2,
+ ::boost::details::compressed_pair_switch<
+ T1,
+ T2,
+ ::boost::is_same<typename remove_cv<T1>::type, typename remove_cv<T2>::type>::value,
+ ::boost::is_empty<T1>::value,
+ ::boost::is_empty<T2>::value>::value> base;
+public:
+ typedef T1 first_type;
+ typedef T2 second_type;
+ typedef typename call_traits<first_type>::param_type first_param_type;
+ typedef typename call_traits<second_type>::param_type second_param_type;
+ typedef typename call_traits<first_type>::reference first_reference;
+ typedef typename call_traits<second_type>::reference second_reference;
+ typedef typename call_traits<first_type>::const_reference first_const_reference;
+ typedef typename call_traits<second_type>::const_reference second_const_reference;
+
+ compressed_pair() : base() {}
+ compressed_pair(first_param_type x, second_param_type y) : base(x, y) {}
+ explicit compressed_pair(first_param_type x) : base(x) {}
+ explicit compressed_pair(second_param_type y) : base(y) {}
+
+ first_reference first() {return base::first();}
+ first_const_reference first() const {return base::first();}
+
+ second_reference second() {return base::second();}
+ second_const_reference second() const {return base::second();}
+
+ void swap(compressed_pair& y) { base::swap(y); }
+};
+
+// JM
+// Partial specialisation for case where T1 == T2:
+//
+template <class T>
+class compressed_pair<T, T>
+ : private details::compressed_pair_imp<T, T,
+ ::boost::details::compressed_pair_switch<
+ T,
+ T,
+ ::boost::is_same<typename remove_cv<T>::type, typename remove_cv<T>::type>::value,
+ ::boost::is_empty<T>::value,
+ ::boost::is_empty<T>::value>::value>
+{
+private:
+ typedef details::compressed_pair_imp<T, T,
+ ::boost::details::compressed_pair_switch<
+ T,
+ T,
+ ::boost::is_same<typename remove_cv<T>::type, typename remove_cv<T>::type>::value,
+ ::boost::is_empty<T>::value,
+ ::boost::is_empty<T>::value>::value> base;
+public:
+ typedef T first_type;
+ typedef T second_type;
+ typedef typename call_traits<first_type>::param_type first_param_type;
+ typedef typename call_traits<second_type>::param_type second_param_type;
+ typedef typename call_traits<first_type>::reference first_reference;
+ typedef typename call_traits<second_type>::reference second_reference;
+ typedef typename call_traits<first_type>::const_reference first_const_reference;
+ typedef typename call_traits<second_type>::const_reference second_const_reference;
+
+ compressed_pair() : base() {}
+ compressed_pair(first_param_type x, second_param_type y) : base(x, y) {}
+#if !(defined(__SUNPRO_CC) && (__SUNPRO_CC <= 0x530))
+ explicit
+#endif
+ compressed_pair(first_param_type x) : base(x) {}
+
+ first_reference first() {return base::first();}
+ first_const_reference first() const {return base::first();}
+
+ second_reference second() {return base::second();}
+ second_const_reference second() const {return base::second();}
+
+ void swap(::boost::compressed_pair<T,T>& y) { base::swap(y); }
+};
+
+template <class T1, class T2>
+inline
+void
+swap(compressed_pair<T1, T2>& x, compressed_pair<T1, T2>& y)
+{
+ x.swap(y);
+}
+
+} // boost
+
+#ifdef BOOST_MSVC
+# pragma warning(pop)
+#endif
+
+#endif // BOOST_DETAIL_COMPRESSED_PAIR_HPP
+
diff --git a/3rdParty/Boost/src/boost/detail/ob_compressed_pair.hpp b/3rdParty/Boost/src/boost/detail/ob_compressed_pair.hpp
new file mode 100644
index 0000000..727acab
--- /dev/null
+++ b/3rdParty/Boost/src/boost/detail/ob_compressed_pair.hpp
@@ -0,0 +1,510 @@
+// (C) Copyright Steve Cleary, Beman Dawes, Howard Hinnant & John Maddock 2000.
+// 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).
+//
+// See http://www.boost.org/libs/utility for most recent version including documentation.
+// see libs/utility/compressed_pair.hpp
+//
+/* Release notes:
+ 20 Jan 2001:
+ Fixed obvious bugs (David Abrahams)
+ 07 Oct 2000:
+ Added better single argument constructor support.
+ 03 Oct 2000:
+ Added VC6 support (JM).
+ 23rd July 2000:
+ Additional comments added. (JM)
+ Jan 2000:
+ Original version: this version crippled for use with crippled compilers
+ - John Maddock Jan 2000.
+*/
+
+
+#ifndef BOOST_OB_COMPRESSED_PAIR_HPP
+#define BOOST_OB_COMPRESSED_PAIR_HPP
+
+#include <algorithm>
+#ifndef BOOST_OBJECT_TYPE_TRAITS_HPP
+#include <boost/type_traits/object_traits.hpp>
+#endif
+#ifndef BOOST_SAME_TRAITS_HPP
+#include <boost/type_traits/same_traits.hpp>
+#endif
+#ifndef BOOST_CALL_TRAITS_HPP
+#include <boost/call_traits.hpp>
+#endif
+
+namespace boost
+{
+#ifdef BOOST_MSVC6_MEMBER_TEMPLATES
+//
+// use member templates to emulate
+// partial specialisation. Note that due to
+// problems with overload resolution with VC6
+// each of the compressed_pair versions that follow
+// have one template single-argument constructor
+// in place of two specific constructors:
+//
+
+template <class T1, class T2>
+class compressed_pair;
+
+namespace detail{
+
+template <class A, class T1, class T2>
+struct best_conversion_traits
+{
+ typedef char one;
+ typedef char (&two)[2];
+ static A a;
+ static one test(T1);
+ static two test(T2);
+
+ enum { value = sizeof(test(a)) };
+};
+
+template <int>
+struct init_one;
+
+template <>
+struct init_one<1>
+{
+ template <class A, class T1, class T2>
+ static void init(const A& a, T1* p1, T2*)
+ {
+ *p1 = a;
+ }
+};
+
+template <>
+struct init_one<2>
+{
+ template <class A, class T1, class T2>
+ static void init(const A& a, T1*, T2* p2)
+ {
+ *p2 = a;
+ }
+};
+
+
+// T1 != T2, both non-empty
+template <class T1, class T2>
+class compressed_pair_0
+{
+private:
+ T1 _first;
+ T2 _second;
+public:
+ typedef T1 first_type;
+ typedef T2 second_type;
+ typedef typename call_traits<first_type>::param_type first_param_type;
+ typedef typename call_traits<second_type>::param_type second_param_type;
+ typedef typename call_traits<first_type>::reference first_reference;
+ typedef typename call_traits<second_type>::reference second_reference;
+ typedef typename call_traits<first_type>::const_reference first_const_reference;
+ typedef typename call_traits<second_type>::const_reference second_const_reference;
+
+ compressed_pair_0() : _first(), _second() {}
+ compressed_pair_0(first_param_type x, second_param_type y) : _first(x), _second(y) {}
+ template <class A>
+ explicit compressed_pair_0(const A& val)
+ {
+ init_one<best_conversion_traits<A, T1, T2>::value>::init(val, &_first, &_second);
+ }
+ compressed_pair_0(const ::boost::compressed_pair<T1,T2>& x)
+ : _first(x.first()), _second(x.second()) {}
+
+#if 0
+ compressed_pair_0& operator=(const compressed_pair_0& x) {
+ cout << "assigning compressed pair 0" << endl;
+ _first = x._first;
+ _second = x._second;
+ cout << "finished assigning compressed pair 0" << endl;
+ return *this;
+ }
+#endif
+
+ first_reference first() { return _first; }
+ first_const_reference first() const { return _first; }
+
+ second_reference second() { return _second; }
+ second_const_reference second() const { return _second; }
+
+ void swap(compressed_pair_0& y)
+ {
+ using std::swap;
+ swap(_first, y._first);
+ swap(_second, y._second);
+ }
+};
+
+// T1 != T2, T2 empty
+template <class T1, class T2>
+class compressed_pair_1 : T2
+{
+private:
+ T1 _first;
+public:
+ typedef T1 first_type;
+ typedef T2 second_type;
+ typedef typename call_traits<first_type>::param_type first_param_type;
+ typedef typename call_traits<second_type>::param_type second_param_type;
+ typedef typename call_traits<first_type>::reference first_reference;
+ typedef typename call_traits<second_type>::reference second_reference;
+ typedef typename call_traits<first_type>::const_reference first_const_reference;
+ typedef typename call_traits<second_type>::const_reference second_const_reference;
+
+ compressed_pair_1() : T2(), _first() {}
+ compressed_pair_1(first_param_type x, second_param_type y) : T2(y), _first(x) {}
+
+ template <class A>
+ explicit compressed_pair_1(const A& val)
+ {
+ init_one<best_conversion_traits<A, T1, T2>::value>::init(val, &_first, static_cast<T2*>(this));
+ }
+
+ compressed_pair_1(const ::boost::compressed_pair<T1,T2>& x)
+ : T2(x.second()), _first(x.first()) {}
+
+#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
+ // Total weirdness. If the assignment to _first is moved after
+ // the call to the inherited operator=, then this breaks graph/test/graph.cpp
+ // by way of iterator_adaptor.
+ compressed_pair_1& operator=(const compressed_pair_1& x) {
+ _first = x._first;
+ T2::operator=(x);
+ return *this;
+ }
+#endif
+
+ first_reference first() { return _first; }
+ first_const_reference first() const { return _first; }
+
+ second_reference second() { return *this; }
+ second_const_reference second() const { return *this; }
+
+ void swap(compressed_pair_1& y)
+ {
+ // no need to swap empty base class:
+ using std::swap;
+ swap(_first, y._first);
+ }
+};
+
+// T1 != T2, T1 empty
+template <class T1, class T2>
+class compressed_pair_2 : T1
+{
+private:
+ T2 _second;
+public:
+ typedef T1 first_type;
+ typedef T2 second_type;
+ typedef typename call_traits<first_type>::param_type first_param_type;
+ typedef typename call_traits<second_type>::param_type second_param_type;
+ typedef typename call_traits<first_type>::reference first_reference;
+ typedef typename call_traits<second_type>::reference second_reference;
+ typedef typename call_traits<first_type>::const_reference first_const_reference;
+ typedef typename call_traits<second_type>::const_reference second_const_reference;
+
+ compressed_pair_2() : T1(), _second() {}
+ compressed_pair_2(first_param_type x, second_param_type y) : T1(x), _second(y) {}
+ template <class A>
+ explicit compressed_pair_2(const A& val)
+ {
+ init_one<best_conversion_traits<A, T1, T2>::value>::init(val, static_cast<T1*>(this), &_second);
+ }
+ compressed_pair_2(const ::boost::compressed_pair<T1,T2>& x)
+ : T1(x.first()), _second(x.second()) {}
+
+#if 0
+ compressed_pair_2& operator=(const compressed_pair_2& x) {
+ cout << "assigning compressed pair 2" << endl;
+ T1::operator=(x);
+ _second = x._second;
+ cout << "finished assigning compressed pair 2" << endl;
+ return *this;
+ }
+#endif
+ first_reference first() { return *this; }
+ first_const_reference first() const { return *this; }
+
+ second_reference second() { return _second; }
+ second_const_reference second() const { return _second; }
+
+ void swap(compressed_pair_2& y)
+ {
+ // no need to swap empty base class:
+ using std::swap;
+ swap(_second, y._second);
+ }
+};
+
+// T1 != T2, both empty
+template <class T1, class T2>
+class compressed_pair_3 : T1, T2
+{
+public:
+ typedef T1 first_type;
+ typedef T2 second_type;
+ typedef typename call_traits<first_type>::param_type first_param_type;
+ typedef typename call_traits<second_type>::param_type second_param_type;
+ typedef typename call_traits<first_type>::reference first_reference;
+ typedef typename call_traits<second_type>::reference second_reference;
+ typedef typename call_traits<first_type>::const_reference first_const_reference;
+ typedef typename call_traits<second_type>::const_reference second_const_reference;
+
+ compressed_pair_3() : T1(), T2() {}
+ compressed_pair_3(first_param_type x, second_param_type y) : T1(x), T2(y) {}
+ template <class A>
+ explicit compressed_pair_3(const A& val)
+ {
+ init_one<best_conversion_traits<A, T1, T2>::value>::init(val, static_cast<T1*>(this), static_cast<T2*>(this));
+ }
+ compressed_pair_3(const ::boost::compressed_pair<T1,T2>& x)
+ : T1(x.first()), T2(x.second()) {}
+
+ first_reference first() { return *this; }
+ first_const_reference first() const { return *this; }
+
+ second_reference second() { return *this; }
+ second_const_reference second() const { return *this; }
+
+ void swap(compressed_pair_3& y)
+ {
+ // no need to swap empty base classes:
+ }
+};
+
+// T1 == T2, and empty
+template <class T1, class T2>
+class compressed_pair_4 : T1
+{
+public:
+ typedef T1 first_type;
+ typedef T2 second_type;
+ typedef typename call_traits<first_type>::param_type first_param_type;
+ typedef typename call_traits<second_type>::param_type second_param_type;
+ typedef typename call_traits<first_type>::reference first_reference;
+ typedef typename call_traits<second_type>::reference second_reference;
+ typedef typename call_traits<first_type>::const_reference first_const_reference;
+ typedef typename call_traits<second_type>::const_reference second_const_reference;
+
+ compressed_pair_4() : T1() {}
+ compressed_pair_4(first_param_type x, second_param_type y) : T1(x), m_second(y) {}
+ // only one single argument constructor since T1 == T2
+ explicit compressed_pair_4(first_param_type x) : T1(x), m_second(x) {}
+ compressed_pair_4(const ::boost::compressed_pair<T1,T2>& x)
+ : T1(x.first()), m_second(x.second()) {}
+
+ first_reference first() { return *this; }
+ first_const_reference first() const { return *this; }
+
+ second_reference second() { return m_second; }
+ second_const_reference second() const { return m_second; }
+
+ void swap(compressed_pair_4& y)
+ {
+ // no need to swap empty base classes:
+ }
+private:
+ T2 m_second;
+};
+
+// T1 == T2, not empty
+template <class T1, class T2>
+class compressed_pair_5
+{
+private:
+ T1 _first;
+ T2 _second;
+public:
+ typedef T1 first_type;
+ typedef T2 second_type;
+ typedef typename call_traits<first_type>::param_type first_param_type;
+ typedef typename call_traits<second_type>::param_type second_param_type;
+ typedef typename call_traits<first_type>::reference first_reference;
+ typedef typename call_traits<second_type>::reference second_reference;
+ typedef typename call_traits<first_type>::const_reference first_const_reference;
+ typedef typename call_traits<second_type>::const_reference second_const_reference;
+
+ compressed_pair_5() : _first(), _second() {}
+ compressed_pair_5(first_param_type x, second_param_type y) : _first(x), _second(y) {}
+ // only one single argument constructor since T1 == T2
+ explicit compressed_pair_5(first_param_type x) : _first(x), _second(x) {}
+ compressed_pair_5(const ::boost::compressed_pair<T1,T2>& c)
+ : _first(c.first()), _second(c.second()) {}
+
+ first_reference first() { return _first; }
+ first_const_reference first() const { return _first; }
+
+ second_reference second() { return _second; }
+ second_const_reference second() const { return _second; }
+
+ void swap(compressed_pair_5& y)
+ {
+ using std::swap;
+ swap(_first, y._first);
+ swap(_second, y._second);
+ }
+};
+
+template <bool e1, bool e2, bool same>
+struct compressed_pair_chooser
+{
+ template <class T1, class T2>
+ struct rebind
+ {
+ typedef compressed_pair_0<T1, T2> type;
+ };
+};
+
+template <>
+struct compressed_pair_chooser<false, true, false>
+{
+ template <class T1, class T2>
+ struct rebind
+ {
+ typedef compressed_pair_1<T1, T2> type;
+ };
+};
+
+template <>
+struct compressed_pair_chooser<true, false, false>
+{
+ template <class T1, class T2>
+ struct rebind
+ {
+ typedef compressed_pair_2<T1, T2> type;
+ };
+};
+
+template <>
+struct compressed_pair_chooser<true, true, false>
+{
+ template <class T1, class T2>
+ struct rebind
+ {
+ typedef compressed_pair_3<T1, T2> type;
+ };
+};
+
+template <>
+struct compressed_pair_chooser<true, true, true>
+{
+ template <class T1, class T2>
+ struct rebind
+ {
+ typedef compressed_pair_4<T1, T2> type;
+ };
+};
+
+template <>
+struct compressed_pair_chooser<false, false, true>
+{
+ template <class T1, class T2>
+ struct rebind
+ {
+ typedef compressed_pair_5<T1, T2> type;
+ };
+};
+
+template <class T1, class T2>
+struct compressed_pair_traits
+{
+private:
+ typedef compressed_pair_chooser<is_empty<T1>::value, is_empty<T2>::value, is_same<T1,T2>::value> chooser;
+ typedef typename chooser::template rebind<T1, T2> bound_type;
+public:
+ typedef typename bound_type::type type;
+};
+
+} // namespace detail
+
+template <class T1, class T2>
+class compressed_pair : public detail::compressed_pair_traits<T1, T2>::type
+{
+private:
+ typedef typename detail::compressed_pair_traits<T1, T2>::type base_type;
+public:
+ typedef T1 first_type;
+ typedef T2 second_type;
+ typedef typename call_traits<first_type>::param_type first_param_type;
+ typedef typename call_traits<second_type>::param_type second_param_type;
+ typedef typename call_traits<first_type>::reference first_reference;
+ typedef typename call_traits<second_type>::reference second_reference;
+ typedef typename call_traits<first_type>::const_reference first_const_reference;
+ typedef typename call_traits<second_type>::const_reference second_const_reference;
+
+ compressed_pair() : base_type() {}
+ compressed_pair(first_param_type x, second_param_type y) : base_type(x, y) {}
+ template <class A>
+ explicit compressed_pair(const A& x) : base_type(x){}
+
+ first_reference first() { return base_type::first(); }
+ first_const_reference first() const { return base_type::first(); }
+
+ second_reference second() { return base_type::second(); }
+ second_const_reference second() const { return base_type::second(); }
+};
+
+template <class T1, class T2>
+inline void swap(compressed_pair<T1, T2>& x, compressed_pair<T1, T2>& y)
+{
+ x.swap(y);
+}
+
+#else
+// no partial specialisation, no member templates:
+
+template <class T1, class T2>
+class compressed_pair
+{
+private:
+ T1 _first;
+ T2 _second;
+public:
+ typedef T1 first_type;
+ typedef T2 second_type;
+ typedef typename call_traits<first_type>::param_type first_param_type;
+ typedef typename call_traits<second_type>::param_type second_param_type;
+ typedef typename call_traits<first_type>::reference first_reference;
+ typedef typename call_traits<second_type>::reference second_reference;
+ typedef typename call_traits<first_type>::const_reference first_const_reference;
+ typedef typename call_traits<second_type>::const_reference second_const_reference;
+
+ compressed_pair() : _first(), _second() {}
+ compressed_pair(first_param_type x, second_param_type y) : _first(x), _second(y) {}
+ explicit compressed_pair(first_param_type x) : _first(x), _second() {}
+ // can't define this in case T1 == T2:
+ // explicit compressed_pair(second_param_type y) : _first(), _second(y) {}
+
+ first_reference first() { return _first; }
+ first_const_reference first() const { return _first; }
+
+ second_reference second() { return _second; }
+ second_const_reference second() const { return _second; }
+
+ void swap(compressed_pair& y)
+ {
+ using std::swap;
+ swap(_first, y._first);
+ swap(_second, y._second);
+ }
+};
+
+template <class T1, class T2>
+inline void swap(compressed_pair<T1, T2>& x, compressed_pair<T1, T2>& y)
+{
+ x.swap(y);
+}
+
+#endif
+
+} // boost
+
+#endif // BOOST_OB_COMPRESSED_PAIR_HPP
+
+
+
diff --git a/3rdParty/Boost/src/boost/functional/hash_fwd.hpp b/3rdParty/Boost/src/boost/functional/hash_fwd.hpp
new file mode 100644
index 0000000..b640988
--- /dev/null
+++ b/3rdParty/Boost/src/boost/functional/hash_fwd.hpp
@@ -0,0 +1,7 @@
+
+// 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)
+
+#include <boost/functional/hash/hash_fwd.hpp>
+
diff --git a/3rdParty/Boost/src/boost/type_traits/object_traits.hpp b/3rdParty/Boost/src/boost/type_traits/object_traits.hpp
new file mode 100644
index 0000000..c812a62
--- /dev/null
+++ b/3rdParty/Boost/src/boost/type_traits/object_traits.hpp
@@ -0,0 +1,33 @@
+// (C) Copyright Steve Cleary, Beman Dawes, Howard Hinnant & John Maddock 2000.
+// 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).
+//
+// See http://www.boost.org/libs/type_traits for most recent version including documentation.
+//
+// defines object traits classes:
+// is_object, is_scalar, is_class, is_compound, is_pod,
+// has_trivial_constructor, has_trivial_copy, has_trivial_assign,
+// has_trivial_destructor, is_empty.
+//
+
+#ifndef BOOST_TT_OBJECT_TRAITS_HPP_INLCUDED
+#define BOOST_TT_OBJECT_TRAITS_HPP_INLCUDED
+
+#include <boost/type_traits/has_trivial_assign.hpp>
+#include <boost/type_traits/has_trivial_constructor.hpp>
+#include <boost/type_traits/has_trivial_copy.hpp>
+#include <boost/type_traits/has_trivial_destructor.hpp>
+#include <boost/type_traits/has_nothrow_constructor.hpp>
+#include <boost/type_traits/has_nothrow_copy.hpp>
+#include <boost/type_traits/has_nothrow_assign.hpp>
+#include <boost/type_traits/is_base_and_derived.hpp>
+#include <boost/type_traits/is_class.hpp>
+#include <boost/type_traits/is_compound.hpp>
+#include <boost/type_traits/is_empty.hpp>
+#include <boost/type_traits/is_object.hpp>
+#include <boost/type_traits/is_pod.hpp>
+#include <boost/type_traits/is_scalar.hpp>
+#include <boost/type_traits/is_stateless.hpp>
+
+#endif // BOOST_TT_OBJECT_TRAITS_HPP_INLCUDED
diff --git a/3rdParty/Boost/src/boost/type_traits/same_traits.hpp b/3rdParty/Boost/src/boost/type_traits/same_traits.hpp
new file mode 100644
index 0000000..dab7dac
--- /dev/null
+++ b/3rdParty/Boost/src/boost/type_traits/same_traits.hpp
@@ -0,0 +1,15 @@
+// (C) Copyright Steve Cleary, Beman Dawes, Aleksey Gurtovoy, Howard Hinnant & John Maddock 2000.
+// 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).
+//
+// See http://www.boost.org/libs/type_traits for most recent version including documentation.
+//
+// defines is_same:
+
+#ifndef BOOST_TT_SAME_TRAITS_HPP_INCLUDED
+#define BOOST_TT_SAME_TRAITS_HPP_INCLUDED
+
+#include <boost/type_traits/is_same.hpp>
+
+#endif // BOOST_TT_SAME_TRAITS_HPP_INCLUDED
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
diff --git a/3rdParty/Boost/src/boost/unordered_map.hpp b/3rdParty/Boost/src/boost/unordered_map.hpp
new file mode 100644
index 0000000..00d3c91
--- /dev/null
+++ b/3rdParty/Boost/src/boost/unordered_map.hpp
@@ -0,0 +1,18 @@
+
+// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
+// Copyright (C) 2005-2008 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_MAP_HPP_INCLUDED
+#define BOOST_UNORDERED_MAP_HPP_INCLUDED
+
+#if defined(_MSC_VER) && (_MSC_VER >= 1020)
+# pragma once
+#endif
+
+#include <boost/unordered/unordered_map.hpp>
+
+#endif // BOOST_UNORDERED_MAP_HPP_INCLUDED
diff --git a/3rdParty/Boost/update.sh b/3rdParty/Boost/update.sh
index 49d55ba..5e5a9ef 100755
--- a/3rdParty/Boost/update.sh
+++ b/3rdParty/Boost/update.sh
@@ -30,6 +30,7 @@ fi
uuid/uuid_generators.hpp \
variant.hpp \
regex.hpp \
+ boost/unordered_map.hpp \
$TARGET_DIR
rm -rf $TARGET_DIR/libs/config
diff --git a/Swiften/JID/JID.cpp b/Swiften/JID/JID.cpp
index cf5317e..3ecd881 100644
--- a/Swiften/JID/JID.cpp
+++ b/Swiften/JID/JID.cpp
@@ -4,13 +4,28 @@
* See Documentation/Licenses/GPLv3.txt for more information.
*/
-#include <stringprep.h>
+#define SWIFTEN_CACHE_JID_PREP
+
#include <vector>
#include <iostream>
+#include <Swiften/Base/String.h>
+#ifdef SWIFTEN_CACHE_JID_PREP
+#include <boost/unordered_map.hpp>
+#endif
+#include <stringprep.h>
+
#include "Swiften/JID/JID.h"
#include "Swiften/IDN/StringPrep.h"
+#ifdef SWIFTEN_CACHE_JID_PREP
+typedef boost::unordered_map<std::string, Swift::String> PrepCache;
+
+static PrepCache nodePrepCache;
+static PrepCache domainPrepCache;
+static PrepCache resourcePrepCache;
+#endif
+
namespace Swift {
JID::JID(const char* jid) {
@@ -56,9 +71,31 @@ void JID::initializeFromString(const String& jid) {
void JID::nameprepAndSetComponents(const String& node, const String& domain, const String& resource) {
+#ifndef SWIFTEN_CACHE_JID_PREP
node_ = StringPrep::getPrepared(node, StringPrep::NamePrep);
domain_ = StringPrep::getPrepared(domain, StringPrep::XMPPNodePrep);
resource_ = StringPrep::getPrepared(resource, StringPrep::XMPPResourcePrep);
+#else
+ std::pair<PrepCache::iterator, bool> r;
+
+ r = nodePrepCache.insert(std::make_pair(node.getUTF8String(), String()));
+ if (r.second) {
+ r.first->second = StringPrep::getPrepared(node, StringPrep::NamePrep);
+ }
+ node_ = r.first->second;
+
+ r = domainPrepCache.insert(std::make_pair(domain.getUTF8String(), String()));
+ if (r.second) {
+ r.first->second = StringPrep::getPrepared(domain, StringPrep::XMPPNodePrep);
+ }
+ domain_ = r.first->second;
+
+ r = resourcePrepCache.insert(std::make_pair(resource.getUTF8String(), String()));
+ if (r.second) {
+ r.first->second = StringPrep::getPrepared(resource, StringPrep::XMPPResourcePrep);
+ }
+ resource_ = r.first->second;
+#endif
}
String JID::toString() const {