| ///////////////////////////////////////////////////////////////////////////// |
| // |
| // (C) Copyright Ion Gaztanaga 2006-2009 |
| // |
| // 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/detail/pointer_to_other.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/cstdint.hpp> |
| #include <cstddef> |
| #include <climits> |
| #include <iterator> |
| #include <boost/cstdint.hpp> |
| #include <boost/static_assert.hpp> |
| |
| namespace boost { |
| namespace intrusive { |
| 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); |
| }; |
| |
| template <class T> |
| struct internal_base_hook_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::boost_intrusive_tags::is_base_hook> test (int); |
| static const std::size_t value = sizeof(test<T>(0)); |
| }; |
| |
| template <class T> |
| struct internal_base_hook_bool_is_true |
| { |
| static const bool value = internal_base_hook_bool<T>::value > sizeof(one)*2; |
| }; |
| |
| template <class T> |
| struct internal_any_hook_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::is_any_hook> test (int); |
| static const std::size_t value = sizeof(test<T>(0)); |
| }; |
| |
| template <class T> |
| struct internal_any_hook_bool_is_true |
| { |
| static const bool value = internal_any_hook_bool<T>::value > sizeof(one)*2; |
| }; |
| |
| |
| template <class T> |
| struct external_value_traits_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::external_value_traits> test (int); |
| static const std::size_t value = sizeof(test<T>(0)); |
| }; |
| |
| template <class T> |
| struct external_bucket_traits_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::external_bucket_traits> test (int); |
| static const std::size_t value = sizeof(test<T>(0)); |
| }; |
| |
| template <class T> |
| struct external_value_traits_is_true |
| { |
| static const bool value = external_value_traits_bool<T>::value > sizeof(one)*2; |
| }; |
| |
| template<class Node, class Tag, link_mode_type LinkMode, int> |
| struct node_holder |
| : public Node |
| {}; |
| |
| template<class SmartPtr> |
| struct smart_ptr_type |
| { |
| typedef typename SmartPtr::value_type value_type; |
| typedef value_type *pointer; |
| static pointer get (const SmartPtr &smartptr) |
| { return smartptr.get();} |
| }; |
| |
| template<class T> |
| struct smart_ptr_type<T*> |
| { |
| typedef T value_type; |
| typedef value_type *pointer; |
| static pointer get (pointer ptr) |
| { return ptr;} |
| }; |
| |
| //!Overload for smart pointers to avoid ADL problems with boost_intrusive_get_pointer |
| template<class Ptr> |
| inline typename smart_ptr_type<Ptr>::pointer |
| boost_intrusive_get_pointer(const Ptr &ptr) |
| { return smart_ptr_type<Ptr>::get(ptr); } |
| |
| //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()(node_ptr p) |
| { NodeAlgorithms::init(p); } |
| }; |
| |
| template<bool ConstantSize, class SizeType> |
| 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_; } |
| |
| SizeType size_; |
| }; |
| |
| template<class SizeType> |
| struct size_holder<false, SizeType> |
| { |
| 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() |
| {} |
| }; |
| |
| template<class KeyValueCompare, class Container> |
| struct key_nodeptr_comp |
| : private detail::ebo_functor_holder<KeyValueCompare> |
| { |
| typedef typename Container::real_value_traits real_value_traits; |
| typedef typename real_value_traits::node_ptr node_ptr; |
| typedef typename real_value_traits::const_node_ptr const_node_ptr; |
| typedef detail::ebo_functor_holder<KeyValueCompare> base_t; |
| key_nodeptr_comp(KeyValueCompare kcomp, const Container *cont) |
| : base_t(kcomp), cont_(cont) |
| {} |
| |
| template<class KeyType> |
| bool operator()( const_node_ptr node, const KeyType &key |
| , typename enable_if_c |
| <!is_convertible<KeyType, const_node_ptr>::value>::type * = 0) const |
| { return base_t::get()(*cont_->get_real_value_traits().to_value_ptr(node), key); } |
| |
| template<class KeyType> |
| bool operator()(const KeyType &key, const_node_ptr node |
| , typename enable_if_c |
| <!is_convertible<KeyType, const_node_ptr>::value>::type * = 0) const |
| { return base_t::get()(key, *cont_->get_real_value_traits().to_value_ptr(node)); } |
| |
| bool operator()(const_node_ptr node1, const_node_ptr node2) const |
| { |
| return base_t::get() |
| ( *cont_->get_real_value_traits().to_value_ptr(node1) |
| , *cont_->get_real_value_traits().to_value_ptr(node2) |
| ); |
| } |
| |
| const Container *cont_; |
| }; |
| |
| template<class F, class Container> |
| struct node_cloner |
| : private detail::ebo_functor_holder<F> |
| { |
| typedef typename Container::real_value_traits real_value_traits; |
| typedef typename Container::node_algorithms node_algorithms; |
| typedef typename real_value_traits::value_type value_type; |
| typedef typename real_value_traits::pointer pointer; |
| typedef typename real_value_traits::node_traits::node node; |
| typedef typename real_value_traits::node_ptr node_ptr; |
| typedef typename real_value_traits::const_node_ptr const_node_ptr; |
| typedef detail::ebo_functor_holder<F> base_t; |
| enum { safemode_or_autounlink = |
| (int)real_value_traits::link_mode == (int)auto_unlink || |
| (int)real_value_traits::link_mode == (int)safe_link }; |
| |
| node_cloner(F f, const Container *cont) |
| : base_t(f), cont_(cont) |
| {} |
| |
| node_ptr operator()(node_ptr p) |
| { return this->operator()(*p); } |
| |
| node_ptr operator()(const node &to_clone) |
| { |
| const value_type &v = |
| *cont_->get_real_value_traits().to_value_ptr(const_node_ptr(&to_clone)); |
| node_ptr n = cont_->get_real_value_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 Container *cont_; |
| }; |
| |
| template<class F, class Container> |
| struct node_disposer |
| : private detail::ebo_functor_holder<F> |
| { |
| typedef typename Container::real_value_traits real_value_traits; |
| typedef typename real_value_traits::node_ptr node_ptr; |
| typedef detail::ebo_functor_holder<F> base_t; |
| typedef typename Container::node_algorithms node_algorithms; |
| enum { safemode_or_autounlink = |
| (int)real_value_traits::link_mode == (int)auto_unlink || |
| (int)real_value_traits::link_mode == (int)safe_link }; |
| |
| node_disposer(F f, const Container *cont) |
| : base_t(f), cont_(cont) |
| {} |
| |
| void operator()(node_ptr p) |
| { |
| if(safemode_or_autounlink) |
| node_algorithms::init(p); |
| base_t::get()(cont_->get_real_value_traits().to_value_ptr(p)); |
| } |
| const Container *cont_; |
| }; |
| |
| struct dummy_constptr |
| { |
| dummy_constptr(const void *) |
| {} |
| |
| const void *get_ptr() const |
| { return 0; } |
| }; |
| |
| template<class VoidPointer> |
| struct constptr |
| { |
| typedef typename boost::pointer_to_other |
| <VoidPointer, const void>::type ConstVoidPtr; |
| |
| constptr(const void *ptr) |
| : const_void_ptr_(ptr) |
| {} |
| |
| const void *get_ptr() const |
| { return detail::boost_intrusive_get_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 |
| >::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>) |
| {} |
| |
| template<class T, class NodeTraits, link_mode_type LinkMode, class Tag, int HookType> |
| struct base_hook_traits |
| { |
| public: |
| typedef detail::node_holder |
| <typename NodeTraits::node, Tag, LinkMode, HookType> node_holder; |
| typedef NodeTraits node_traits; |
| typedef T value_type; |
| typedef typename node_traits::node_ptr node_ptr; |
| typedef typename node_traits::const_node_ptr const_node_ptr; |
| typedef typename boost::pointer_to_other<node_ptr, T>::type pointer; |
| typedef typename boost::pointer_to_other<node_ptr, const T>::type const_pointer; |
| typedef typename std::iterator_traits<pointer>::reference reference; |
| typedef typename std::iterator_traits<const_pointer>::reference const_reference; |
| static const link_mode_type link_mode = LinkMode; |
| |
| static node_ptr to_node_ptr(reference value) |
| { return static_cast<node_holder*>(&value); } |
| |
| static const_node_ptr to_node_ptr(const_reference value) |
| { return static_cast<const node_holder*>(&value); } |
| |
| static pointer to_value_ptr(node_ptr n) |
| { return static_cast<T*>(static_cast<node_holder*>(&*n)); } |
| |
| static const_pointer to_value_ptr(const_node_ptr n) |
| { return static_cast<const T*>(static_cast<const node_holder*>(&*n)); } |
| }; |
| |
| template<class T, class Hook, Hook T::* P> |
| struct member_hook_traits |
| { |
| public: |
| typedef Hook hook_type; |
| typedef typename hook_type::boost_intrusive_tags::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 boost::pointer_to_other<node_ptr, T>::type pointer; |
| typedef typename boost::pointer_to_other<node_ptr, const T>::type const_pointer; |
| typedef typename std::iterator_traits<pointer>::reference reference; |
| typedef typename std::iterator_traits<const_pointer>::reference const_reference; |
| static const link_mode_type link_mode = Hook::boost_intrusive_tags::link_mode; |
| |
| static node_ptr to_node_ptr(reference value) |
| { return static_cast<node*>(&(value.*P)); } |
| |
| static const_node_ptr to_node_ptr(const_reference value) |
| { return static_cast<const node*>(&(value.*P)); } |
| |
| static pointer to_value_ptr(node_ptr n) |
| { |
| return detail::parent_from_member<T, Hook> |
| (static_cast<Hook*>(detail::boost_intrusive_get_pointer(n)), P); |
| } |
| |
| static const_pointer to_value_ptr(const_node_ptr n) |
| { |
| return detail::parent_from_member<T, Hook> |
| (static_cast<const Hook*>(detail::boost_intrusive_get_pointer(n)), P); |
| } |
| }; |
| |
| template<class Functor> |
| struct function_hook_traits |
| { |
| 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::boost_intrusive_tags::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 boost::pointer_to_other<node_ptr, value_type>::type pointer; |
| typedef typename boost::pointer_to_other<node_ptr, const value_type>::type const_pointer; |
| typedef typename std::iterator_traits<pointer>::reference reference; |
| typedef typename std::iterator_traits<const_pointer>::reference const_reference; |
| static const link_mode_type link_mode = hook_type::boost_intrusive_tags::link_mode; |
| |
| static node_ptr to_node_ptr(reference value) |
| { return static_cast<node*>(&*Functor::to_hook_ptr(value)); } |
| |
| static const_node_ptr to_node_ptr(const_reference value) |
| { return static_cast<const node*>(&*Functor::to_hook_ptr(value)); } |
| |
| static pointer to_value_ptr(node_ptr n) |
| { return Functor::to_value_ptr(to_hook_ptr(n)); } |
| |
| static const_pointer to_value_ptr(const_node_ptr n) |
| { return Functor::to_value_ptr(to_hook_ptr(n)); } |
| |
| private: |
| static hook_ptr to_hook_ptr(node_ptr n) |
| { return hook_ptr(&*static_cast<hook_type*>(&*n)); } |
| |
| static const_hook_ptr to_hook_ptr(const_node_ptr n) |
| { return const_hook_ptr(&*static_cast<const hook_type*>(&*n)); } |
| }; |
| |
| |
| //This function uses binary search to discover the |
| //highest set bit of the integer |
| inline std::size_t floor_log2 (std::size_t x) |
| { |
| const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT; |
| const bool Size_t_Bits_Power_2= !(Bits & (Bits-1)); |
| BOOST_STATIC_ASSERT(Size_t_Bits_Power_2); |
| |
| std::size_t n = x; |
| std::size_t log2 = 0; |
| |
| for(std::size_t shift = Bits >> 1; shift; shift >>= 1){ |
| std::size_t tmp = n >> shift; |
| if (tmp) |
| log2 += shift, n = tmp; |
| } |
| |
| return log2; |
| } |
| |
| 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 &= ~(255 << 23); |
| x += 127 << 23; |
| caster.x = x; |
| val = caster.val; |
| val = ((-1.0f/3) * val + 2) * val - 2.0f/3; |
| |
| return (val + log_2); |
| } |
| |
| inline std::size_t ceil_log2 (std::size_t x) |
| { |
| return ((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; |
| }; |
| |
| 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; |
| }; |
| |
| // 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 exception_array_disposer |
| { |
| Container *cont_; |
| Disposer &disp_; |
| typename Container::size_type &constructed_; |
| |
| exception_array_disposer(const exception_array_disposer&); |
| exception_array_disposer &operator=(const exception_array_disposer&); |
| |
| public: |
| typedef typename Container::size_type size_type; |
| exception_array_disposer |
| (Container &cont, Disposer &disp, size_type &constructed) |
| : cont_(&cont), disp_(disp), constructed_(constructed) |
| {} |
| |
| void release() |
| { cont_ = 0; } |
| |
| ~exception_array_disposer() |
| { |
| size_type n = constructed_; |
| if(cont_){ |
| while(n--){ |
| cont_[n].clear_and_dispose(disp_); |
| } |
| } |
| } |
| }; |
| |
| template<class ValueTraits, bool ExternalValueTraits> |
| struct store_cont_ptr_on_it_impl |
| { |
| static const bool value = is_stateful_value_traits<ValueTraits>::value; |
| }; |
| |
| template<class ValueTraits> |
| struct store_cont_ptr_on_it_impl<ValueTraits, true> |
| { |
| static const bool value = true; |
| }; |
| |
| template <class Container> |
| struct store_cont_ptr_on_it |
| { |
| typedef typename Container::value_traits value_traits; |
| static const bool value = store_cont_ptr_on_it_impl |
| <value_traits, external_value_traits_is_true<value_traits>::value>::value; |
| }; |
| |
| template<class Container, bool IsConst> |
| struct node_to_value |
| : public detail::select_constptr |
| < typename boost::pointer_to_other |
| <typename Container::pointer, void>::type |
| , detail::store_cont_ptr_on_it<Container>::value |
| >::type |
| { |
| static const bool store_container_ptr = |
| detail::store_cont_ptr_on_it<Container>::value; |
| |
| typedef typename Container::real_value_traits real_value_traits; |
| typedef typename real_value_traits::value_type value_type; |
| typedef typename detail::select_constptr |
| < typename boost::pointer_to_other |
| <typename Container::pointer, void>::type |
| , store_container_ptr >::type Base; |
| typedef typename real_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 boost::pointer_to_other |
| <typename Container::pointer, ntype>::type npointer; |
| |
| node_to_value(const Container *cont) |
| : Base(cont) |
| {} |
| |
| typedef vtype & result_type; |
| typedef ntype & first_argument_type; |
| |
| const Container *get_container() const |
| { |
| if(store_container_ptr) |
| return static_cast<const Container*>(Base::get_ptr()); |
| else |
| return 0; |
| } |
| |
| const real_value_traits *get_real_value_traits() const |
| { |
| if(store_container_ptr) |
| return &this->get_container()->get_real_value_traits(); |
| else |
| return 0; |
| } |
| |
| result_type operator()(first_argument_type arg) const |
| { return *(this->get_real_value_traits()->to_value_ptr(npointer(&arg))); } |
| }; |
| |
| //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; |
| try{ |
| for(; i != N; ++i){ |
| new(init_buf)T(init); |
| init_buf += sizeof(T); |
| } |
| } |
| catch(...){ |
| while(i--){ |
| init_buf -= sizeof(T); |
| ((T*)init_buf)->~T(); |
| } |
| throw; |
| } |
| } |
| |
| 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]; |
| }; |
| |
| } //namespace detail |
| } //namespace intrusive |
| } //namespace boost |
| |
| #include <boost/intrusive/detail/config_end.hpp> |
| |
| #endif //BOOST_INTRUSIVE_DETAIL_UTILITIES_HPP |