Swift
summaryrefslogtreecommitdiffstats
path: root/3rdParty/Boost/src/boost/intrusive/detail/utilities.hpp
diff options
context:
space:
mode:
authorTobias Markmann <tm@ayena.de>2014-10-19 20:22:58 (GMT)
committerTobias Markmann <tm@ayena.de>2014-10-20 13:49:33 (GMT)
commit6b22dfcf59474dd016a0355a3102a1dd3692d92c (patch)
tree2b1fd33be433a91e81fee84fdc2bf1b52575d934 /3rdParty/Boost/src/boost/intrusive/detail/utilities.hpp
parent38b0cb785fea8eae5e48fae56440695fdfd10ee1 (diff)
downloadswift-contrib-6b22dfcf59474dd016a0355a3102a1dd3692d92c.zip
swift-contrib-6b22dfcf59474dd016a0355a3102a1dd3692d92c.tar.bz2
Update Boost in 3rdParty to version 1.56.0.
This updates Boost in our 3rdParty directory to version 1.56.0. Updated our update.sh script to stop on error. Changed error reporting in SwiftTools/CrashReporter.cpp to SWIFT_LOG due to missing include of <iostream> with newer Boost. Change-Id: I4b35c77de951333979a524097f35f5f83d325edc
Diffstat (limited to '3rdParty/Boost/src/boost/intrusive/detail/utilities.hpp')
-rw-r--r--3rdParty/Boost/src/boost/intrusive/detail/utilities.hpp1279
1 files changed, 1279 insertions, 0 deletions
diff --git a/3rdParty/Boost/src/boost/intrusive/detail/utilities.hpp b/3rdParty/Boost/src/boost/intrusive/detail/utilities.hpp
new file mode 100644
index 0000000..b893d22
--- /dev/null
+++ b/3rdParty/Boost/src/boost/intrusive/detail/utilities.hpp
@@ -0,0 +1,1279 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2006-2013
+//
+// 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/intrusive for documentation.
+//
+/////////////////////////////////////////////////////////////////////////////
+
+#ifndef BOOST_INTRUSIVE_DETAIL_UTILITIES_HPP
+#define BOOST_INTRUSIVE_DETAIL_UTILITIES_HPP
+
+#include <boost/intrusive/detail/config_begin.hpp>
+#include <boost/intrusive/pointer_traits.hpp>
+#include <boost/intrusive/detail/parent_from_member.hpp>
+#include <boost/intrusive/detail/ebo_functor_holder.hpp>
+#include <boost/intrusive/link_mode.hpp>
+#include <boost/intrusive/detail/mpl.hpp>
+#include <boost/intrusive/detail/assert.hpp>
+#include <boost/intrusive/detail/is_stateful_value_traits.hpp>
+#include <boost/intrusive/detail/memory_util.hpp>
+#include <boost/cstdint.hpp>
+#include <cstddef>
+#include <climits>
+#include <iterator>
+#include <boost/cstdint.hpp>
+#include <boost/static_assert.hpp>
+#include <boost/detail/no_exceptions_support.hpp>
+#include <functional>
+#include <boost/functional/hash.hpp>
+#include <boost/tti/tti.hpp>
+
+namespace boost {
+namespace intrusive {
+
+enum algo_types
+{
+ CircularListAlgorithms,
+ CircularSListAlgorithms,
+ LinearSListAlgorithms,
+ BsTreeAlgorithms,
+ RbTreeAlgorithms,
+ AvlTreeAlgorithms,
+ SgTreeAlgorithms,
+ SplayTreeAlgorithms,
+ TreapAlgorithms
+};
+
+template<algo_types AlgoType, class NodeTraits>
+struct get_algo;
+
+template <link_mode_type link_mode>
+struct is_safe_autounlink
+{
+ static const bool value =
+ (int)link_mode == (int)auto_unlink ||
+ (int)link_mode == (int)safe_link;
+};
+
+namespace detail {
+
+template <class T>
+struct internal_member_value_traits
+{
+ template <class U> static detail::one test(...);
+ template <class U> static detail::two test(typename U::member_value_traits* = 0);
+ static const bool value = sizeof(test<T>(0)) == sizeof(detail::two);
+};
+
+#define BOOST_INTRUSIVE_INTERNAL_STATIC_BOOL_IS_TRUE(TRAITS_PREFIX, TYPEDEF_TO_FIND) \
+template <class T>\
+struct TRAITS_PREFIX##_bool\
+{\
+ template<bool Add>\
+ struct two_or_three {one _[2 + Add];};\
+ template <class U> static one test(...);\
+ template <class U> static two_or_three<U::TYPEDEF_TO_FIND> test (int);\
+ static const std::size_t value = sizeof(test<T>(0));\
+};\
+\
+template <class T>\
+struct TRAITS_PREFIX##_bool_is_true\
+{\
+ static const bool value = TRAITS_PREFIX##_bool<T>::value > sizeof(one)*2;\
+};\
+//
+
+BOOST_INTRUSIVE_INTERNAL_STATIC_BOOL_IS_TRUE(internal_base_hook, hooktags::is_base_hook)
+BOOST_INTRUSIVE_INTERNAL_STATIC_BOOL_IS_TRUE(internal_any_hook, is_any_hook)
+BOOST_INTRUSIVE_INTERNAL_STATIC_BOOL_IS_TRUE(resizable, resizable)
+
+template <class T>
+inline T* to_raw_pointer(T* p)
+{ return p; }
+
+template <class Pointer>
+inline typename boost::intrusive::pointer_traits<Pointer>::element_type*
+to_raw_pointer(const Pointer &p)
+{ return boost::intrusive::detail::to_raw_pointer(p.operator->()); }
+
+//This functor compares a stored value
+//and the one passed as an argument
+template<class ConstReference>
+class equal_to_value
+{
+ ConstReference t_;
+
+ public:
+ equal_to_value(ConstReference t)
+ : t_(t)
+ {}
+
+ bool operator()(ConstReference t)const
+ { return t_ == t; }
+};
+
+class null_disposer
+{
+ public:
+ template <class Pointer>
+ void operator()(Pointer)
+ {}
+};
+
+template<class NodeAlgorithms>
+class init_disposer
+{
+ typedef typename NodeAlgorithms::node_ptr node_ptr;
+
+ public:
+ void operator()(const node_ptr & p)
+ { NodeAlgorithms::init(p); }
+};
+
+template<bool ConstantSize, class SizeType, class Tag = void>
+struct size_holder
+{
+ static const bool constant_time_size = ConstantSize;
+ typedef SizeType size_type;
+
+ SizeType get_size() const
+ { return size_; }
+
+ void set_size(SizeType size)
+ { size_ = size; }
+
+ void decrement()
+ { --size_; }
+
+ void increment()
+ { ++size_; }
+
+ void increase(SizeType n)
+ { size_ += n; }
+
+ void decrease(SizeType n)
+ { size_ -= n; }
+
+ SizeType size_;
+};
+
+template<class SizeType, class Tag>
+struct size_holder<false, SizeType, Tag>
+{
+ static const bool constant_time_size = false;
+ typedef SizeType size_type;
+
+ size_type get_size() const
+ { return 0; }
+
+ void set_size(size_type)
+ {}
+
+ void decrement()
+ {}
+
+ void increment()
+ {}
+
+ void increase(SizeType)
+ {}
+
+ void decrease(SizeType)
+ {}
+};
+
+template<class KeyValueCompare, class ValueTraits>
+struct key_nodeptr_comp
+ : private detail::ebo_functor_holder<KeyValueCompare>
+{
+ typedef ValueTraits value_traits;
+ typedef typename value_traits::value_type value_type;
+ typedef typename value_traits::node_ptr node_ptr;
+ typedef typename value_traits::const_node_ptr const_node_ptr;
+ typedef detail::ebo_functor_holder<KeyValueCompare> base_t;
+ key_nodeptr_comp(KeyValueCompare kcomp, const ValueTraits *traits)
+ : base_t(kcomp), traits_(traits)
+ {}
+
+ template<class T>
+ struct is_node_ptr
+ {
+ static const bool value = is_same<T, const_node_ptr>::value || is_same<T, node_ptr>::value;
+ };
+
+ template<class T>
+ const value_type & key_forward
+ (const T &node, typename enable_if_c<is_node_ptr<T>::value>::type * = 0) const
+ { return *traits_->to_value_ptr(node); }
+
+ template<class T>
+ const T & key_forward(const T &key, typename enable_if_c<!is_node_ptr<T>::value>::type* = 0) const
+ { return key; }
+
+
+ template<class KeyType, class KeyType2>
+ bool operator()(const KeyType &key1, const KeyType2 &key2) const
+ { return base_t::get()(this->key_forward(key1), this->key_forward(key2)); }
+
+ const ValueTraits *const traits_;
+};
+
+template<class F, class ValueTraits, algo_types AlgoType>
+struct node_cloner
+ : private detail::ebo_functor_holder<F>
+{
+ typedef ValueTraits value_traits;
+ typedef typename value_traits::node_traits node_traits;
+ typedef typename node_traits::node_ptr node_ptr;
+ typedef detail::ebo_functor_holder<F> base_t;
+ typedef typename get_algo< AlgoType
+ , node_traits>::type node_algorithms;
+ static const bool safemode_or_autounlink =
+ is_safe_autounlink<value_traits::link_mode>::value;
+ typedef typename value_traits::value_type value_type;
+ typedef typename value_traits::pointer pointer;
+ typedef typename node_traits::node node;
+ typedef typename value_traits::const_node_ptr const_node_ptr;
+ typedef typename value_traits::reference reference;
+ typedef typename value_traits::const_reference const_reference;
+
+ node_cloner(F f, const ValueTraits *traits)
+ : base_t(f), traits_(traits)
+ {}
+
+ // tree-based containers use this method, which is proxy-reference friendly
+ node_ptr operator()(const node_ptr & p)
+ {
+ const_reference v = *traits_->to_value_ptr(p);
+ node_ptr n = traits_->to_node_ptr(*base_t::get()(v));
+ //Cloned node must be in default mode if the linking mode requires it
+ if(safemode_or_autounlink)
+ BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(n));
+ return n;
+ }
+
+ // hashtables use this method, which is proxy-reference unfriendly
+ node_ptr operator()(const node &to_clone)
+ {
+ const value_type &v =
+ *traits_->to_value_ptr
+ (pointer_traits<const_node_ptr>::pointer_to(to_clone));
+ node_ptr n = traits_->to_node_ptr(*base_t::get()(v));
+ //Cloned node must be in default mode if the linking mode requires it
+ if(safemode_or_autounlink)
+ BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(n));
+ return n;
+ }
+
+ const ValueTraits * const traits_;
+};
+
+template<class F, class ValueTraits, algo_types AlgoType>
+struct node_disposer
+ : private detail::ebo_functor_holder<F>
+{
+ typedef ValueTraits value_traits;
+ typedef typename value_traits::node_traits node_traits;
+ typedef typename node_traits::node_ptr node_ptr;
+ typedef detail::ebo_functor_holder<F> base_t;
+ typedef typename get_algo< AlgoType
+ , node_traits>::type node_algorithms;
+ static const bool safemode_or_autounlink =
+ is_safe_autounlink<value_traits::link_mode>::value;
+
+ node_disposer(F f, const ValueTraits *cont)
+ : base_t(f), traits_(cont)
+ {}
+
+ void operator()(const node_ptr & p)
+ {
+ if(safemode_or_autounlink)
+ node_algorithms::init(p);
+ base_t::get()(traits_->to_value_ptr(p));
+ }
+ const ValueTraits * const traits_;
+};
+
+template<class VoidPointer>
+struct dummy_constptr
+{
+ typedef typename boost::intrusive::pointer_traits<VoidPointer>::
+ template rebind_pointer<const void>::type ConstVoidPtr;
+
+ explicit dummy_constptr(ConstVoidPtr)
+ {}
+
+ dummy_constptr()
+ {}
+
+ ConstVoidPtr get_ptr() const
+ { return ConstVoidPtr(); }
+};
+
+template<class VoidPointer>
+struct constptr
+{
+ typedef typename boost::intrusive::pointer_traits<VoidPointer>::
+ template rebind_pointer<const void>::type ConstVoidPtr;
+
+ constptr()
+ {}
+
+ explicit constptr(const ConstVoidPtr &ptr)
+ : const_void_ptr_(ptr)
+ {}
+
+ const void *get_ptr() const
+ { return boost::intrusive::detail::to_raw_pointer(const_void_ptr_); }
+
+ ConstVoidPtr const_void_ptr_;
+};
+
+template <class VoidPointer, bool store_ptr>
+struct select_constptr
+{
+ typedef typename detail::if_c
+ < store_ptr
+ , constptr<VoidPointer>
+ , dummy_constptr<VoidPointer>
+ >::type type;
+};
+
+template<class T, bool Add>
+struct add_const_if_c
+{
+ typedef typename detail::if_c
+ < Add
+ , typename detail::add_const<T>::type
+ , T
+ >::type type;
+};
+
+template <link_mode_type LinkMode>
+struct link_dispatch
+{};
+
+template<class Hook>
+void destructor_impl(Hook &hook, detail::link_dispatch<safe_link>)
+{ //If this assertion raises, you might have destroyed an object
+ //while it was still inserted in a container that is alive.
+ //If so, remove the object from the container before destroying it.
+ (void)hook; BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT(!hook.is_linked());
+}
+
+template<class Hook>
+void destructor_impl(Hook &hook, detail::link_dispatch<auto_unlink>)
+{ hook.unlink(); }
+
+template<class Hook>
+void destructor_impl(Hook &, detail::link_dispatch<normal_link>)
+{}
+
+///////////////////////////
+// floor_log2 Dispatcher
+////////////////////////////
+
+#if defined(_MSC_VER) && (_MSC_VER >= 1300)
+
+ }}} //namespace boost::intrusive::detail
+
+ //Use _BitScanReverseXX intrinsics
+
+ #if defined(_M_X64) || defined(_M_AMD64) || defined(_M_IA64) //64 bit target
+ #define BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT
+ #endif
+
+ #ifndef __INTRIN_H_ // Avoid including any windows system header
+ #ifdef __cplusplus
+ extern "C" {
+ #endif // __cplusplus
+
+ #if defined(BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT) //64 bit target
+ unsigned char _BitScanReverse64(unsigned long *index, unsigned __int64 mask);
+ #pragma intrinsic(_BitScanReverse64)
+ #else //32 bit target
+ unsigned char _BitScanReverse(unsigned long *index, unsigned long mask);
+ #pragma intrinsic(_BitScanReverse)
+ #endif
+
+ #ifdef __cplusplus
+ }
+ #endif // __cplusplus
+ #endif // __INTRIN_H_
+
+ #ifdef BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT
+ #define BOOST_INTRUSIVE_BSR_INTRINSIC _BitScanReverse64
+ #undef BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT
+ #else
+ #define BOOST_INTRUSIVE_BSR_INTRINSIC _BitScanReverse
+ #endif
+
+ namespace boost {
+ namespace intrusive {
+ namespace detail {
+
+ inline std::size_t floor_log2 (std::size_t x)
+ {
+ unsigned long log2;
+ BOOST_INTRUSIVE_BSR_INTRINSIC( &log2, (unsigned long)x );
+ return log2;
+ }
+
+ #undef BOOST_INTRUSIVE_BSR_INTRINSIC
+
+#elif defined(__GNUC__) && ((__GNUC__ >= 4) || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) //GCC >=3.4
+
+ //Compile-time error in case of missing specialization
+ template<class Uint>
+ struct builtin_clz_dispatch;
+
+ #if defined(BOOST_HAS_LONG_LONG)
+ template<>
+ struct builtin_clz_dispatch<unsigned long long>
+ {
+ static unsigned long long call(unsigned long long n)
+ { return __builtin_clzll(n); }
+ };
+ #endif
+
+ template<>
+ struct builtin_clz_dispatch<unsigned long>
+ {
+ static unsigned long call(unsigned long n)
+ { return __builtin_clzl(n); }
+ };
+
+ template<>
+ struct builtin_clz_dispatch<unsigned int>
+ {
+ static unsigned int call(unsigned int n)
+ { return __builtin_clz(n); }
+ };
+
+ inline std::size_t floor_log2(std::size_t n)
+ {
+ return sizeof(std::size_t)*CHAR_BIT - std::size_t(1) - builtin_clz_dispatch<std::size_t>::call(n);
+ }
+
+#else //Portable methods
+
+////////////////////////////
+// Generic method
+////////////////////////////
+
+ inline std::size_t floor_log2_get_shift(std::size_t n, true_ )//power of two size_t
+ { return n >> 1; }
+
+ inline std::size_t floor_log2_get_shift(std::size_t n, false_ )//non-power of two size_t
+ { return (n >> 1) + ((n & 1u) & (n != 1)); }
+
+ template<std::size_t N>
+ inline std::size_t floor_log2 (std::size_t x, integer<std::size_t, N>)
+ {
+ const std::size_t Bits = N;
+ const bool Size_t_Bits_Power_2= !(Bits & (Bits-1));
+
+ std::size_t n = x;
+ std::size_t log2 = 0;
+
+ std::size_t remaining_bits = Bits;
+ std::size_t shift = floor_log2_get_shift(remaining_bits, bool_<Size_t_Bits_Power_2>());
+ while(shift){
+ std::size_t tmp = n >> shift;
+ if (tmp){
+ log2 += shift, n = tmp;
+ }
+ shift = floor_log2_get_shift(shift, bool_<Size_t_Bits_Power_2>());
+ }
+
+ return log2;
+ }
+
+ ////////////////////////////
+ // DeBruijn method
+ ////////////////////////////
+
+ //Taken from:
+ //http://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers
+ //Thanks to Desmond Hume
+
+ inline std::size_t floor_log2 (std::size_t v, integer<std::size_t, 32>)
+ {
+ static const int MultiplyDeBruijnBitPosition[32] =
+ {
+ 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
+ 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
+ };
+
+ v |= v >> 1;
+ v |= v >> 2;
+ v |= v >> 4;
+ v |= v >> 8;
+ v |= v >> 16;
+
+ return MultiplyDeBruijnBitPosition[(std::size_t)(v * 0x07C4ACDDU) >> 27];
+ }
+
+ inline std::size_t floor_log2 (std::size_t v, integer<std::size_t, 64>)
+ {
+ static const std::size_t MultiplyDeBruijnBitPosition[64] = {
+ 63, 0, 58, 1, 59, 47, 53, 2,
+ 60, 39, 48, 27, 54, 33, 42, 3,
+ 61, 51, 37, 40, 49, 18, 28, 20,
+ 55, 30, 34, 11, 43, 14, 22, 4,
+ 62, 57, 46, 52, 38, 26, 32, 41,
+ 50, 36, 17, 19, 29, 10, 13, 21,
+ 56, 45, 25, 31, 35, 16, 9, 12,
+ 44, 24, 15, 8, 23, 7, 6, 5};
+
+ v |= v >> 1;
+ v |= v >> 2;
+ v |= v >> 4;
+ v |= v >> 8;
+ v |= v >> 16;
+ v |= v >> 32;
+ return MultiplyDeBruijnBitPosition[((std::size_t)((v - (v >> 1))*0x07EDD5E59A4E28C2ULL)) >> 58];
+ }
+
+
+ inline std::size_t floor_log2 (std::size_t x)
+ {
+ const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT;
+ return floor_log2(x, integer<std::size_t, Bits>());
+ }
+
+#endif
+
+//Thanks to Laurent de Soras in
+//http://www.flipcode.com/archives/Fast_log_Function.shtml
+inline float fast_log2 (float val)
+{
+ union caster_t
+ {
+ boost::uint32_t x;
+ float val;
+ } caster;
+
+ caster.val = val;
+ boost::uint32_t x = caster.x;
+ const int log_2 = int((x >> 23) & 255) - 128;
+ x &= ~(boost::uint32_t(255u) << 23u);
+ x += boost::uint32_t(127) << 23u;
+ caster.x = x;
+ val = caster.val;
+ //1+log2(m), m ranging from 1 to 2
+ //3rd degree polynomial keeping first derivate continuity.
+ //For less precision the line can be commented out
+ val = ((-1.f/3.f) * val + 2.f) * val - (2.f/3.f);
+ return (val + log_2);
+}
+
+inline std::size_t ceil_log2 (std::size_t x)
+{
+ return static_cast<std::size_t>((x & (x-1)) != 0) + floor_log2(x);
+}
+
+template<class SizeType, std::size_t N>
+struct numbits_eq
+{
+ static const bool value = sizeof(SizeType)*CHAR_BIT == N;
+};
+
+template<class SizeType, class Enabler = void >
+struct sqrt2_pow_max;
+
+template <class SizeType>
+struct sqrt2_pow_max<SizeType, typename enable_if< numbits_eq<SizeType, 32> >::type>
+{
+ static const boost::uint32_t value = 0xb504f334;
+ static const std::size_t pow = 31;
+};
+
+#ifndef BOOST_NO_INT64_T
+
+template <class SizeType>
+struct sqrt2_pow_max<SizeType, typename enable_if< numbits_eq<SizeType, 64> >::type>
+{
+ static const boost::uint64_t value = 0xb504f333f9de6484ull;
+ static const std::size_t pow = 63;
+};
+
+#endif //BOOST_NO_INT64_T
+
+// Returns floor(pow(sqrt(2), x * 2 + 1)).
+// Defined for X from 0 up to the number of bits in size_t minus 1.
+inline std::size_t sqrt2_pow_2xplus1 (std::size_t x)
+{
+ const std::size_t value = (std::size_t)sqrt2_pow_max<std::size_t>::value;
+ const std::size_t pow = (std::size_t)sqrt2_pow_max<std::size_t>::pow;
+ return (value >> (pow - x)) + 1;
+}
+
+template<class Container, class Disposer>
+class exception_disposer
+{
+ Container *cont_;
+ Disposer &disp_;
+
+ exception_disposer(const exception_disposer&);
+ exception_disposer &operator=(const exception_disposer&);
+
+ public:
+ exception_disposer(Container &cont, Disposer &disp)
+ : cont_(&cont), disp_(disp)
+ {}
+
+ void release()
+ { cont_ = 0; }
+
+ ~exception_disposer()
+ {
+ if(cont_){
+ cont_->clear_and_dispose(disp_);
+ }
+ }
+};
+
+template<class Container, class Disposer, class SizeType>
+class exception_array_disposer
+{
+ Container *cont_;
+ Disposer &disp_;
+ SizeType &constructed_;
+
+ exception_array_disposer(const exception_array_disposer&);
+ exception_array_disposer &operator=(const exception_array_disposer&);
+
+ public:
+
+ exception_array_disposer
+ (Container &cont, Disposer &disp, SizeType &constructed)
+ : cont_(&cont), disp_(disp), constructed_(constructed)
+ {}
+
+ void release()
+ { cont_ = 0; }
+
+ ~exception_array_disposer()
+ {
+ SizeType n = constructed_;
+ if(cont_){
+ while(n--){
+ cont_[n].clear_and_dispose(disp_);
+ }
+ }
+ }
+};
+
+template<class ValueTraits, bool IsConst>
+struct node_to_value
+ : public detail::select_constptr
+ < typename pointer_traits
+ <typename ValueTraits::pointer>::template rebind_pointer<void>::type
+ , is_stateful_value_traits<ValueTraits>::value
+ >::type
+{
+ static const bool stateful_value_traits = is_stateful_value_traits<ValueTraits>::value;
+ typedef typename detail::select_constptr
+ < typename pointer_traits
+ <typename ValueTraits::pointer>::
+ template rebind_pointer<void>::type
+ , stateful_value_traits >::type Base;
+
+ typedef ValueTraits value_traits;
+ typedef typename value_traits::value_type value_type;
+ typedef typename value_traits::node_traits::node node;
+ typedef typename detail::add_const_if_c
+ <value_type, IsConst>::type vtype;
+ typedef typename detail::add_const_if_c
+ <node, IsConst>::type ntype;
+ typedef typename pointer_traits
+ <typename ValueTraits::pointer>::
+ template rebind_pointer<ntype>::type npointer;
+ typedef typename pointer_traits<npointer>::
+ template rebind_pointer<const ValueTraits>::type const_value_traits_ptr;
+
+ node_to_value(const const_value_traits_ptr &ptr)
+ : Base(ptr)
+ {}
+
+ typedef vtype & result_type;
+ typedef ntype & first_argument_type;
+
+ const_value_traits_ptr get_value_traits() const
+ { return pointer_traits<const_value_traits_ptr>::static_cast_from(Base::get_ptr()); }
+
+ result_type to_value(first_argument_type arg, false_) const
+ { return *(value_traits::to_value_ptr(pointer_traits<npointer>::pointer_to(arg))); }
+
+ result_type to_value(first_argument_type arg, true_) const
+ { return *(this->get_value_traits()->to_value_ptr(pointer_traits<npointer>::pointer_to(arg))); }
+
+ result_type operator()(first_argument_type arg) const
+ { return this->to_value(arg, bool_<stateful_value_traits>()); }
+};
+
+//This is not standard, but should work with all compilers
+union max_align
+{
+ char char_;
+ short short_;
+ int int_;
+ long long_;
+ #ifdef BOOST_HAS_LONG_LONG
+ long long long_long_;
+ #endif
+ float float_;
+ double double_;
+ long double long_double_;
+ void * void_ptr_;
+};
+
+template<class T, std::size_t N>
+class array_initializer
+{
+ public:
+ template<class CommonInitializer>
+ array_initializer(const CommonInitializer &init)
+ {
+ char *init_buf = (char*)rawbuf;
+ std::size_t i = 0;
+ BOOST_TRY{
+ for(; i != N; ++i){
+ new(init_buf)T(init);
+ init_buf += sizeof(T);
+ }
+ }
+ BOOST_CATCH(...){
+ while(i--){
+ init_buf -= sizeof(T);
+ ((T*)init_buf)->~T();
+ }
+ BOOST_RETHROW;
+ }
+ BOOST_CATCH_END
+ }
+
+ operator T* ()
+ { return (T*)(rawbuf); }
+
+ operator const T*() const
+ { return (const T*)(rawbuf); }
+
+ ~array_initializer()
+ {
+ char *init_buf = (char*)rawbuf + N*sizeof(T);
+ for(std::size_t i = 0; i != N; ++i){
+ init_buf -= sizeof(T);
+ ((T*)init_buf)->~T();
+ }
+ }
+
+ private:
+ detail::max_align rawbuf[(N*sizeof(T)-1)/sizeof(detail::max_align)+1];
+};
+
+
+
+
+template<class It>
+class reverse_iterator
+ : public std::iterator<
+ typename std::iterator_traits<It>::iterator_category,
+ typename std::iterator_traits<It>::value_type,
+ typename std::iterator_traits<It>::difference_type,
+ typename std::iterator_traits<It>::pointer,
+ typename std::iterator_traits<It>::reference>
+{
+ public:
+ typedef typename std::iterator_traits<It>::pointer pointer;
+ typedef typename std::iterator_traits<It>::reference reference;
+ typedef typename std::iterator_traits<It>::difference_type difference_type;
+ typedef It iterator_type;
+
+ reverse_iterator(){}
+
+ explicit reverse_iterator(It r)
+ : m_current(r)
+ {}
+
+ template<class OtherIt>
+ reverse_iterator(const reverse_iterator<OtherIt>& r)
+ : m_current(r.base())
+ {}
+
+ It base() const
+ { return m_current; }
+
+ reference operator*() const
+ { It temp(m_current); --temp; return *temp; }
+
+ pointer operator->() const
+ { It temp(m_current); --temp; return temp.operator->(); }
+
+ reference operator[](difference_type off) const
+ { return this->m_current[-off]; }
+
+ reverse_iterator& operator++()
+ { --m_current; return *this; }
+
+ reverse_iterator operator++(int)
+ {
+ reverse_iterator temp = *this;
+ --m_current;
+ return temp;
+ }
+
+ reverse_iterator& operator--()
+ {
+ ++m_current;
+ return *this;
+ }
+
+ reverse_iterator operator--(int)
+ {
+ reverse_iterator temp(*this);
+ ++m_current;
+ return temp;
+ }
+
+ friend bool operator==(const reverse_iterator& l, const reverse_iterator& r)
+ { return l.m_current == r.m_current; }
+
+ friend bool operator!=(const reverse_iterator& l, const reverse_iterator& r)
+ { return l.m_current != r.m_current; }
+
+ friend bool operator<(const reverse_iterator& l, const reverse_iterator& r)
+ { return l.m_current < r.m_current; }
+
+ friend bool operator<=(const reverse_iterator& l, const reverse_iterator& r)
+ { return l.m_current <= r.m_current; }
+
+ friend bool operator>(const reverse_iterator& l, const reverse_iterator& r)
+ { return l.m_current > r.m_current; }
+
+ friend bool operator>=(const reverse_iterator& l, const reverse_iterator& r)
+ { return l.m_current >= r.m_current; }
+
+ reverse_iterator& operator+=(difference_type off)
+ { m_current -= off; return *this; }
+
+ friend reverse_iterator operator+(const reverse_iterator & l, difference_type off)
+ {
+ reverse_iterator tmp(l.m_current);
+ tmp.m_current -= off;
+ return tmp;
+ }
+
+ reverse_iterator& operator-=(difference_type off)
+ { m_current += off; return *this; }
+
+ friend reverse_iterator operator-(const reverse_iterator & l, difference_type off)
+ {
+ reverse_iterator tmp(l.m_current);
+ tmp.m_current += off;
+ return tmp;
+ }
+
+ friend difference_type operator-(const reverse_iterator& l, const reverse_iterator& r)
+ { return r.m_current - l.m_current; }
+
+ private:
+ It m_current; // the wrapped iterator
+};
+
+template<class ConstNodePtr>
+struct uncast_types
+{
+ typedef typename pointer_traits<ConstNodePtr>::element_type element_type;
+ typedef typename remove_const<element_type>::type non_const_type;
+ typedef typename pointer_traits<ConstNodePtr>::
+ template rebind_pointer<non_const_type>::type non_const_pointer;
+ typedef pointer_traits<non_const_pointer> non_const_traits;
+};
+
+template<class ConstNodePtr>
+static typename uncast_types<ConstNodePtr>::non_const_pointer
+ uncast(const ConstNodePtr & ptr)
+{
+ return uncast_types<ConstNodePtr>::non_const_traits::const_cast_from(ptr);
+}
+
+// trivial header node holder
+template < typename NodeTraits >
+struct default_header_holder : public NodeTraits::node
+{
+ typedef NodeTraits node_traits;
+ typedef typename node_traits::node node;
+ typedef typename node_traits::node_ptr node_ptr;
+ typedef typename node_traits::const_node_ptr const_node_ptr;
+
+ default_header_holder() : node() {}
+
+ const_node_ptr get_node() const
+ { return pointer_traits< const_node_ptr >::pointer_to(*static_cast< const node* >(this)); }
+
+ node_ptr get_node()
+ { return pointer_traits< node_ptr >::pointer_to(*static_cast< node* >(this)); }
+
+ // (unsafe) downcast used to implement container-from-iterator
+ static default_header_holder* get_holder(const node_ptr &p)
+ { return static_cast< default_header_holder* >(boost::intrusive::detail::to_raw_pointer(p)); }
+};
+
+// type function producing the header node holder
+template < typename Value_Traits, typename HeaderHolder >
+struct get_header_holder_type
+{
+ typedef HeaderHolder type;
+};
+template < typename Value_Traits >
+struct get_header_holder_type< Value_Traits, void >
+{
+ typedef default_header_holder< typename Value_Traits::node_traits > type;
+};
+
+} //namespace detail
+
+template<class Node, class Tag, unsigned int>
+struct node_holder
+ : public Node
+{};
+
+template<class T, class NodePtr, class Tag, unsigned int Type>
+struct bhtraits_base
+{
+ public:
+ typedef NodePtr node_ptr;
+ typedef typename pointer_traits<node_ptr>::element_type node;
+ typedef node_holder<node, Tag, Type> node_holder_type;
+ typedef T value_type;
+ typedef typename pointer_traits<node_ptr>::
+ template rebind_pointer<const node>::type const_node_ptr;
+ typedef typename pointer_traits<node_ptr>::
+ template rebind_pointer<T>::type pointer;
+ typedef typename pointer_traits<node_ptr>::
+ template rebind_pointer<const T>::type const_pointer;
+ //typedef typename pointer_traits<pointer>::reference reference;
+ //typedef typename pointer_traits<const_pointer>::reference const_reference;
+ typedef T & reference;
+ typedef const T & const_reference;
+ typedef node_holder_type & node_holder_reference;
+ typedef const node_holder_type & const_node_holder_reference;
+ typedef node& node_reference;
+ typedef const node & const_node_reference;
+
+ static pointer to_value_ptr(const node_ptr & n)
+ {
+ return pointer_traits<pointer>::pointer_to
+ (static_cast<reference>(static_cast<node_holder_reference>(*n)));
+ }
+
+ static const_pointer to_value_ptr(const const_node_ptr & n)
+ {
+ return pointer_traits<const_pointer>::pointer_to
+ (static_cast<const_reference>(static_cast<const_node_holder_reference>(*n)));
+ }
+
+ static node_ptr to_node_ptr(reference value)
+ {
+ return pointer_traits<node_ptr>::pointer_to
+ (static_cast<node_reference>(static_cast<node_holder_reference>(value)));
+ }
+
+ static const_node_ptr to_node_ptr(const_reference value)
+ {
+ return pointer_traits<const_node_ptr>::pointer_to
+ (static_cast<const_node_reference>(static_cast<const_node_holder_reference>(value)));
+ }
+};
+
+template<class T, class NodeTraits, link_mode_type LinkMode, class Tag, unsigned int Type>
+struct bhtraits
+ : public bhtraits_base<T, typename NodeTraits::node_ptr, Tag, Type>
+{
+ static const link_mode_type link_mode = LinkMode;
+ typedef NodeTraits node_traits;
+};
+
+/*
+template<class T, class NodePtr, typename pointer_traits<NodePtr>::element_type T::* P>
+struct mhtraits_base
+{
+ public:
+ typedef typename pointer_traits<NodePtr>::element_type node;
+ typedef T value_type;
+ typedef NodePtr node_ptr;
+ typedef typename pointer_traits<node_ptr>::
+ template rebind_pointer<const node>::type const_node_ptr;
+ typedef typename pointer_traits<node_ptr>::
+ template rebind_pointer<T>::type pointer;
+ typedef typename pointer_traits<node_ptr>::
+ template rebind_pointer<const T>::type const_pointer;
+ typedef T & reference;
+ typedef const T & const_reference;
+ typedef node& node_reference;
+ typedef const node & const_node_reference;
+
+ static node_ptr to_node_ptr(reference value)
+ {
+ return pointer_traits<node_ptr>::pointer_to
+ (static_cast<node_reference>(value.*P));
+ }
+
+ static const_node_ptr to_node_ptr(const_reference value)
+ {
+ return pointer_traits<const_node_ptr>::pointer_to
+ (static_cast<const_node_reference>(value.*P));
+ }
+
+ static pointer to_value_ptr(const node_ptr & n)
+ {
+ return pointer_traits<pointer>::pointer_to
+ (*detail::parent_from_member<T, node>
+ (boost::intrusive::detail::to_raw_pointer(n), P));
+ }
+
+ static const_pointer to_value_ptr(const const_node_ptr & n)
+ {
+ return pointer_traits<const_pointer>::pointer_to
+ (*detail::parent_from_member<T, node>
+ (boost::intrusive::detail::to_raw_pointer(n), P));
+ }
+};
+
+
+template<class T, class NodeTraits, typename NodeTraits::node T::* P, link_mode_type LinkMode>
+struct mhtraits
+ : public mhtraits_base<T, typename NodeTraits::node_ptr, P>
+{
+ static const link_mode_type link_mode = LinkMode;
+ typedef NodeTraits node_traits;
+};
+*/
+
+
+template<class T, class Hook, Hook T::* P>
+struct mhtraits
+{
+ public:
+ typedef Hook hook_type;
+ typedef typename hook_type::hooktags::node_traits node_traits;
+ typedef typename node_traits::node node;
+ typedef T value_type;
+ typedef typename node_traits::node_ptr node_ptr;
+ typedef typename node_traits::const_node_ptr const_node_ptr;
+ typedef typename pointer_traits<node_ptr>::
+ template rebind_pointer<T>::type pointer;
+ typedef typename pointer_traits<node_ptr>::
+ template rebind_pointer<const T>::type const_pointer;
+ typedef T & reference;
+ typedef const T & const_reference;
+ typedef node& node_reference;
+ typedef const node & const_node_reference;
+ typedef hook_type& hook_reference;
+ typedef const hook_type & const_hook_reference;
+
+ static const link_mode_type link_mode = Hook::hooktags::link_mode;
+
+ static node_ptr to_node_ptr(reference value)
+ {
+ return pointer_traits<node_ptr>::pointer_to
+ (static_cast<node_reference>(static_cast<hook_reference>(value.*P)));
+ }
+
+ static const_node_ptr to_node_ptr(const_reference value)
+ {
+ return pointer_traits<const_node_ptr>::pointer_to
+ (static_cast<const_node_reference>(static_cast<const_hook_reference>(value.*P)));
+ }
+
+ static pointer to_value_ptr(const node_ptr & n)
+ {
+ return pointer_traits<pointer>::pointer_to
+ (*detail::parent_from_member<T, Hook>
+ (static_cast<Hook*>(boost::intrusive::detail::to_raw_pointer(n)), P));
+ }
+
+ static const_pointer to_value_ptr(const const_node_ptr & n)
+ {
+ return pointer_traits<const_pointer>::pointer_to
+ (*detail::parent_from_member<T, Hook>
+ (static_cast<const Hook*>(boost::intrusive::detail::to_raw_pointer(n)), P));
+ }
+};
+
+
+template<class Functor>
+struct fhtraits
+{
+ public:
+ typedef typename Functor::hook_type hook_type;
+ typedef typename Functor::hook_ptr hook_ptr;
+ typedef typename Functor::const_hook_ptr const_hook_ptr;
+ typedef typename hook_type::hooktags::node_traits node_traits;
+ typedef typename node_traits::node node;
+ typedef typename Functor::value_type value_type;
+ typedef typename node_traits::node_ptr node_ptr;
+ typedef typename node_traits::const_node_ptr const_node_ptr;
+ typedef typename pointer_traits<node_ptr>::
+ template rebind_pointer<value_type>::type pointer;
+ typedef typename pointer_traits<node_ptr>::
+ template rebind_pointer<const value_type>::type const_pointer;
+ typedef value_type & reference;
+ typedef const value_type & const_reference;
+ static const link_mode_type link_mode = hook_type::hooktags::link_mode;
+
+ static node_ptr to_node_ptr(reference value)
+ { return static_cast<node*>(boost::intrusive::detail::to_raw_pointer(Functor::to_hook_ptr(value))); }
+
+ static const_node_ptr to_node_ptr(const_reference value)
+ { return static_cast<const node*>(boost::intrusive::detail::to_raw_pointer(Functor::to_hook_ptr(value))); }
+
+ static pointer to_value_ptr(const node_ptr & n)
+ { return Functor::to_value_ptr(to_hook_ptr(n)); }
+
+ static const_pointer to_value_ptr(const const_node_ptr & n)
+ { return Functor::to_value_ptr(to_hook_ptr(n)); }
+
+ private:
+ static hook_ptr to_hook_ptr(const node_ptr & n)
+ { return hook_ptr(&*static_cast<hook_type*>(&*n)); }
+
+ static const_hook_ptr to_hook_ptr(const const_node_ptr & n)
+ { return const_hook_ptr(&*static_cast<const hook_type*>(&*n)); }
+};
+
+template<class ValueTraits>
+struct value_traits_pointers
+{
+ typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT
+ (boost::intrusive::detail::
+ , ValueTraits, value_traits_ptr
+ , typename pointer_traits<typename ValueTraits::node_traits::node_ptr>::template
+ rebind_pointer<ValueTraits>::type) value_traits_ptr;
+
+ typedef typename pointer_traits<value_traits_ptr>::template
+ rebind_pointer<ValueTraits const>::type const_value_traits_ptr;
+};
+
+template<class ValueTraits, bool IsConst, class Category>
+struct iiterator
+{
+ typedef ValueTraits value_traits;
+ typedef typename value_traits::node_traits node_traits;
+ typedef typename node_traits::node node;
+ typedef typename node_traits::node_ptr node_ptr;
+ typedef ::boost::intrusive::pointer_traits<node_ptr> nodepointer_traits_t;
+ typedef typename nodepointer_traits_t::template
+ rebind_pointer<void>::type void_pointer;
+ typedef typename ValueTraits::value_type value_type;
+ typedef typename ValueTraits::pointer nonconst_pointer;
+ typedef typename ValueTraits::const_pointer yesconst_pointer;
+ typedef typename ::boost::intrusive::pointer_traits
+ <nonconst_pointer>::reference nonconst_reference;
+ typedef typename ::boost::intrusive::pointer_traits
+ <yesconst_pointer>::reference yesconst_reference;
+ typedef typename nodepointer_traits_t::difference_type difference_type;
+ typedef typename detail::if_c
+ <IsConst, yesconst_pointer, nonconst_pointer>::type pointer;
+ typedef typename detail::if_c
+ <IsConst, yesconst_reference, nonconst_reference>::type reference;
+ typedef std::iterator
+ < Category
+ , value_type
+ , difference_type
+ , pointer
+ , reference
+ > iterator_traits;
+ typedef typename value_traits_pointers
+ <ValueTraits>::value_traits_ptr value_traits_ptr;
+ typedef typename value_traits_pointers
+ <ValueTraits>::const_value_traits_ptr const_value_traits_ptr;
+ static const bool stateful_value_traits =
+ detail::is_stateful_value_traits<value_traits>::value;
+};
+
+template<class NodePtr, class StoredPointer, bool StatefulValueTraits = true>
+struct iiterator_members
+{
+
+ iiterator_members()
+ {}
+
+ iiterator_members(const NodePtr &n_ptr, const StoredPointer &data)
+ : nodeptr_(n_ptr), ptr_(data)
+ {}
+
+ StoredPointer get_ptr() const
+ { return ptr_; }
+
+ NodePtr nodeptr_;
+ StoredPointer ptr_;
+};
+
+template<class NodePtr, class StoredPointer>
+struct iiterator_members<NodePtr, StoredPointer, false>
+{
+ iiterator_members()
+ {}
+
+ iiterator_members(const NodePtr &n_ptr, const StoredPointer &)
+ : nodeptr_(n_ptr)
+ {}
+
+ StoredPointer get_ptr() const
+ { return StoredPointer(); }
+
+ NodePtr nodeptr_;
+};
+
+template<class Less, class T>
+struct get_less
+{
+ typedef Less type;
+};
+
+template<class T>
+struct get_less<void, T>
+{
+ typedef ::std::less<T> type;
+};
+
+template<class EqualTo, class T>
+struct get_equal_to
+{
+ typedef EqualTo type;
+};
+
+template<class T>
+struct get_equal_to<void, T>
+{
+ typedef ::std::equal_to<T> type;
+};
+
+template<class Hash, class T>
+struct get_hash
+{
+ typedef Hash type;
+};
+
+template<class T>
+struct get_hash<void, T>
+{
+ typedef ::boost::hash<T> type;
+};
+
+struct empty{};
+
+} //namespace intrusive
+} //namespace boost
+
+#include <boost/intrusive/detail/config_end.hpp>
+
+#endif //BOOST_INTRUSIVE_DETAIL_UTILITIES_HPP