diff options
Diffstat (limited to 'src/third_party/boost/boost/intrusive/options.hpp')
-rw-r--r-- | src/third_party/boost/boost/intrusive/options.hpp | 812 |
1 files changed, 0 insertions, 812 deletions
diff --git a/src/third_party/boost/boost/intrusive/options.hpp b/src/third_party/boost/boost/intrusive/options.hpp deleted file mode 100644 index 4cdeccdeaa7..00000000000 --- a/src/third_party/boost/boost/intrusive/options.hpp +++ /dev/null @@ -1,812 +0,0 @@ -///////////////////////////////////////////////////////////////////////////// -// -// (C) Copyright Ion Gaztanaga 2007-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_OPTIONS_HPP -#define BOOST_INTRUSIVE_OPTIONS_HPP - -#include <boost/intrusive/detail/config_begin.hpp> -#include <boost/intrusive/intrusive_fwd.hpp> -#include <boost/intrusive/link_mode.hpp> -#include <boost/intrusive/detail/mpl.hpp> -#include <boost/intrusive/detail/utilities.hpp> -#include <boost/static_assert.hpp> - - -namespace boost { -namespace intrusive { - -/// @cond - -struct default_tag; -struct member_tag; - -namespace detail{ - -struct default_hook_tag{}; - -#define BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER) \ -struct BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER : public default_hook_tag\ -{\ - template <class T>\ - struct apply\ - { typedef typename T::BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER type; };\ -}\ - -BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_list_hook); -BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_slist_hook); -BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_set_hook); -BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_uset_hook); -BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_avl_set_hook); -BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_splay_set_hook); -BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_bs_set_hook); - -#undef BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION - -template <class ValueTraits> -struct eval_value_traits -{ - typedef typename ValueTraits::value_traits type; -}; - -template <class T> -struct external_bucket_traits_is_true -{ - static const bool value = external_bucket_traits_bool<T>::value == 3; -}; - -template <class BucketTraits> -struct eval_bucket_traits -{ - typedef typename BucketTraits::bucket_traits type; -}; - -template <class T, class BaseHook> -struct concrete_hook_base_value_traits -{ - typedef typename BaseHook::boost_intrusive_tags tags; - typedef detail::base_hook_traits - < T - , typename tags::node_traits - , tags::link_mode - , typename tags::tag - , tags::hook_type> type; -}; - -template <class BaseHook> -struct concrete_hook_base_node_traits -{ typedef typename BaseHook::boost_intrusive_tags::node_traits type; }; - -template <class T, class BaseHook> -struct any_hook_base_value_traits -{ - typedef typename BaseHook::boost_intrusive_tags tags; - typedef detail::base_hook_traits - < T - , typename BaseHook::node_traits - , tags::link_mode - , typename tags::tag - , tags::hook_type> type; -}; - -template <class BaseHook> -struct any_hook_base_node_traits -{ typedef typename BaseHook::node_traits type; }; - -template<class T, class BaseHook> -struct get_base_value_traits -{ - typedef typename detail::eval_if_c - < internal_any_hook_bool_is_true<BaseHook>::value - , any_hook_base_value_traits<T, BaseHook> - , concrete_hook_base_value_traits<T, BaseHook> - >::type type; -}; - -template<class BaseHook> -struct get_base_node_traits -{ - typedef typename detail::eval_if_c - < internal_any_hook_bool_is_true<BaseHook>::value - , any_hook_base_node_traits<BaseHook> - , concrete_hook_base_node_traits<BaseHook> - >::type type; -}; - -template<class T, class MemberHook> -struct get_member_value_traits -{ - typedef typename MemberHook::member_value_traits type; -}; - -template<class MemberHook> -struct get_member_node_traits -{ - typedef typename MemberHook::member_value_traits::node_traits type; -}; - -template<class T, class SupposedValueTraits> -struct get_value_traits -{ - typedef typename detail::eval_if_c - <detail::is_convertible<SupposedValueTraits*, detail::default_hook_tag*>::value - ,detail::apply<SupposedValueTraits, T> - ,detail::identity<SupposedValueTraits> - >::type supposed_value_traits; - //...if it's a default hook - typedef typename detail::eval_if_c - < internal_base_hook_bool_is_true<supposed_value_traits>::value - //...get it's internal value traits using - //the provided T value type. - , get_base_value_traits<T, supposed_value_traits> - //...else use it's internal value traits tag - //(member hooks and custom value traits are in this group) - , detail::eval_if_c - < internal_member_value_traits<supposed_value_traits>::value - , get_member_value_traits<T, supposed_value_traits> - , detail::identity<supposed_value_traits> - > - >::type type; -}; - -template<class ValueTraits> -struct get_explicit_node_traits -{ - typedef typename ValueTraits::node_traits type; -}; - -template<class SupposedValueTraits> -struct get_node_traits -{ - typedef SupposedValueTraits supposed_value_traits; - //...if it's a base hook - typedef typename detail::eval_if_c - < internal_base_hook_bool_is_true<supposed_value_traits>::value - //...get it's internal value traits using - //the provided T value type. - , get_base_node_traits<supposed_value_traits> - //...else use it's internal value traits tag - //(member hooks and custom value traits are in this group) - , detail::eval_if_c - < internal_member_value_traits<supposed_value_traits>::value - , get_member_node_traits<supposed_value_traits> - , get_explicit_node_traits<supposed_value_traits> - > - >::type type; -}; - -} //namespace detail{ - - -//!This type indicates that no option is being used -//!and that the default options should be used -struct none -{ - template<class Base> - struct pack : Base - { }; -}; - -/// @endcond - -//!This option setter specifies if the intrusive -//!container stores its size as a member to -//!obtain constant-time size() member. -template<bool Enabled> -struct constant_time_size -{ -/// @cond - template<class Base> - struct pack : Base - { - static const bool constant_time_size = Enabled; - }; -/// @endcond -}; - -//!This option setter specifies the type that -//!the container will use to store its size. -template<class SizeType> -struct size_type -{ -/// @cond - template<class Base> - struct pack : Base - { - typedef SizeType size_type; - }; -/// @endcond -}; - -//!This option setter specifies the strict weak ordering -//!comparison functor for the value type -template<class Compare> -struct compare -{ -/// @cond - template<class Base> - struct pack : Base - { - typedef Compare compare; - }; -/// @endcond -}; - -//!This option setter for scapegoat containers specifies if -//!the intrusive scapegoat container should use a non-variable -//!alpha value that does not need floating-point operations. -//! -//!If activated, the fixed alpha value is 1/sqrt(2). This -//!option also saves some space in the container since -//!the alpha value and some additional data does not need -//!to be stored in the container. -//! -//!If the user only needs an alpha value near 1/sqrt(2), this -//!option also improves performance since avoids logarithm -//!and division operations when rebalancing the tree. -template<bool Enabled> -struct floating_point -{ -/// @cond - template<class Base> - struct pack : Base - { - static const bool floating_point = Enabled; - }; -/// @endcond -}; - -//!This option setter specifies the equality -//!functor for the value type -template<class Equal> -struct equal -{ -/// @cond - template<class Base> - struct pack : Base - { - typedef Equal equal; - }; -/// @endcond -}; - -//!This option setter specifies the equality -//!functor for the value type -template<class Priority> -struct priority -{ -/// @cond - template<class Base> - struct pack : Base - { - typedef Priority priority; - }; -/// @endcond -}; - -//!This option setter specifies the hash -//!functor for the value type -template<class Hash> -struct hash -{ -/// @cond - template<class Base> - struct pack : Base - { - typedef Hash hash; - }; -/// @endcond -}; - -//!This option setter specifies the relationship between the type -//!to be managed by the container (the value type) and the node to be -//!used in the node algorithms. It also specifies the linking policy. -template<typename ValueTraits> -struct value_traits -{ -/// @cond - template<class Base> - struct pack : Base - { - typedef ValueTraits value_traits; - }; -/// @endcond -}; - -//!This option setter specifies the member hook the -//!container must use. -template< typename Parent - , typename MemberHook - , MemberHook Parent::* PtrToMember> -struct member_hook -{ -/// @cond - typedef detail::member_hook_traits - < Parent - , MemberHook - , PtrToMember - > member_value_traits; - template<class Base> - struct pack : Base - { - typedef member_value_traits value_traits; - }; -/// @endcond -}; - - -//!This option setter specifies the function object that will -//!be used to convert between values to be inserted in a container -//!and the hook to be used for that purpose. -template< typename Functor> -struct function_hook -{ -/// @cond - typedef detail::function_hook_traits - <Functor> function_value_traits; - template<class Base> - struct pack : Base - { - typedef function_value_traits value_traits; - }; -/// @endcond -}; - - -//!This option setter specifies that the container -//!must use the specified base hook -template<typename BaseHook> -struct base_hook -{ -/// @cond - template<class Base> - struct pack : Base - { - typedef BaseHook value_traits; - }; -/// @endcond -}; - -//!This option setter specifies the type of -//!a void pointer. This will instruct the hook -//!to use this type of pointer instead of the -//!default one -template<class VoidPointer> -struct void_pointer -{ -/// @cond - template<class Base> - struct pack : Base - { - typedef VoidPointer void_pointer; - }; -/// @endcond -}; - -//!This option setter specifies the type of -//!the tag of a base hook. A type cannot have two -//!base hooks of the same type, so a tag can be used -//!to differentiate two base hooks with otherwise same type -template<class Tag> -struct tag -{ -/// @cond - template<class Base> - struct pack : Base - { - typedef Tag tag; - }; -/// @endcond -}; - -//!This option setter specifies the link mode -//!(normal_link, safe_link or auto_unlink) -template<link_mode_type LinkType> -struct link_mode -{ -/// @cond - template<class Base> - struct pack : Base - { - static const link_mode_type link_mode = LinkType; - }; -/// @endcond -}; - -//!This option setter specifies if the hook -//!should be optimized for size instead of for speed. -template<bool Enabled> -struct optimize_size -{ -/// @cond - template<class Base> - struct pack : Base - { - static const bool optimize_size = Enabled; - }; -/// @endcond -}; - -//!This option setter specifies if the list container should -//!use a linear implementation instead of a circular one. -template<bool Enabled> -struct linear -{ -/// @cond - template<class Base> - struct pack : Base - { - static const bool linear = Enabled; - }; -/// @endcond -}; - -//!This option setter specifies if the list container should -//!use a linear implementation instead of a circular one. -template<bool Enabled> -struct cache_last -{ -/// @cond - template<class Base> - struct pack : Base - { - static const bool cache_last = Enabled; - }; -/// @endcond -}; - -//!This option setter specifies the bucket traits -//!class for unordered associative containers. When this option is specified, -//!instead of using the default bucket traits, a user defined holder will be defined -template<class BucketTraits> -struct bucket_traits -{ -/// @cond - template<class Base> - struct pack : Base - { - typedef BucketTraits bucket_traits; - }; -/// @endcond -}; - -//!This option setter specifies if the unordered hook -//!should offer room to store the hash value. -//!Storing the hash in the hook will speed up rehashing -//!processes in applications where rehashing is frequent, -//!rehashing might throw or the value is heavy to hash. -template<bool Enabled> -struct store_hash -{ -/// @cond - template<class Base> - struct pack : Base - { - static const bool store_hash = Enabled; - }; -/// @endcond -}; - -//!This option setter specifies if the unordered hook -//!should offer room to store another link to another node -//!with the same key. -//!Storing this link will speed up lookups and insertions on -//!unordered_multiset containers with a great number of elements -//!with the same key. -template<bool Enabled> -struct optimize_multikey -{ -/// @cond - template<class Base> - struct pack : Base - { - static const bool optimize_multikey = Enabled; - }; -/// @endcond -}; - -//!This option setter specifies if the bucket array will be always power of two. -//!This allows using masks instead of the default modulo operation to determine -//!the bucket number from the hash value, leading to better performance. -//!In debug mode, if power of two buckets mode is activated, the bucket length -//!will be checked to through assertions to assure the bucket length is power of two. -template<bool Enabled> -struct power_2_buckets -{ -/// @cond - template<class Base> - struct pack : Base - { - static const bool power_2_buckets = Enabled; - }; -/// @endcond -}; - -//!This option setter specifies if the container will cache a pointer to the first -//!non-empty bucket so that begin() is always constant-time. -//!This is specially helpful when we can have containers with a few elements -//!but with big bucket arrays (that is, hashtables with low load factors). -template<bool Enabled> -struct cache_begin -{ -/// @cond - template<class Base> - struct pack : Base - { - static const bool cache_begin = Enabled; - }; -/// @endcond -}; - - -//!This option setter specifies if the container will compare the hash value -//!before comparing objects. This option can't be specified if store_hash<> -//!is not true. -//!This is specially helpful when we have containers with a high load factor. -//!and the comparison function is much more expensive that comparing already -//!stored hash values. -template<bool Enabled> -struct compare_hash -{ -/// @cond - template<class Base> - struct pack : Base - { - static const bool compare_hash = Enabled; - }; -/// @endcond -}; - -//!This option setter specifies if the hash container will use incremental -//!hashing. With incremental hashing the cost of hash table expansion is spread -//!out across each hash table insertion operation, as opposed to be incurred all at once. -//!Therefore linear hashing is well suited for interactive applications or real-time -//!appplications where the worst-case insertion time of non-incremental hash containers -//!(rehashing the whole bucket array) is not admisible. -template<bool Enabled> -struct incremental -{ - /// @cond - template<class Base> - struct pack : Base - { - static const bool incremental = Enabled; - }; - /// @endcond -}; - -/// @cond - -//To-do: pass to variadic templates -#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) - -template<class Prev, class Next> -struct do_pack -{ - //Use "pack" member template to pack options - typedef typename Next::template pack<Prev> type; -}; - -template<class Prev> -struct do_pack<Prev, none> -{ - //Avoid packing "none" to shorten template names - typedef Prev type; -}; - -template - < class DefaultOptions - , class O1 = none - , class O2 = none - , class O3 = none - , class O4 = none - , class O5 = none - , class O6 = none - , class O7 = none - , class O8 = none - , class O9 = none - , class O10 = none - , class O11 = none - > -struct pack_options -{ - // join options - typedef - typename do_pack - < typename do_pack - < typename do_pack - < typename do_pack - < typename do_pack - < typename do_pack - < typename do_pack - < typename do_pack - < typename do_pack - < typename do_pack - < typename do_pack - < DefaultOptions - , O1 - >::type - , O2 - >::type - , O3 - >::type - , O4 - >::type - , O5 - >::type - , O6 - >::type - , O7 - >::type - , O8 - >::type - , O9 - >::type - , O10 - >::type - , O11 - >::type - type; -}; -#else - -//index_tuple -template<int... Indexes> -struct index_tuple{}; - -//build_number_seq -template<std::size_t Num, typename Tuple = index_tuple<> > -struct build_number_seq; - -template<std::size_t Num, int... Indexes> -struct build_number_seq<Num, index_tuple<Indexes...> > - : build_number_seq<Num - 1, index_tuple<Indexes..., sizeof...(Indexes)> > -{}; - -template<int... Indexes> -struct build_number_seq<0, index_tuple<Indexes...> > -{ typedef index_tuple<Indexes...> type; }; - -template<class ...Types> -struct typelist -{}; - -//invert_typelist -template<class T> -struct invert_typelist; - -template<int I, typename Tuple> -struct typelist_element; - -template<int I, typename Head, typename... Tail> -struct typelist_element<I, typelist<Head, Tail...> > -{ - typedef typename typelist_element<I-1, typelist<Tail...> >::type type; -}; - -template<typename Head, typename... Tail> -struct typelist_element<0, typelist<Head, Tail...> > -{ - typedef Head type; -}; - -template<int ...Ints, class ...Types> -typelist<typename typelist_element<(sizeof...(Types) - 1) - Ints, typelist<Types...> >::type...> - inverted_typelist(index_tuple<Ints...>, typelist<Types...>) -{ - return typelist<typename typelist_element<(sizeof...(Types) - 1) - Ints, typelist<Types...> >::type...>(); -} - -//sizeof_typelist -template<class Typelist> -struct sizeof_typelist; - -template<class ...Types> -struct sizeof_typelist< typelist<Types...> > -{ - static const std::size_t value = sizeof...(Types); -}; - -//invert_typelist_impl -template<class Typelist, class Indexes> -struct invert_typelist_impl; - - -template<class Typelist, int ...Ints> -struct invert_typelist_impl< Typelist, index_tuple<Ints...> > -{ - static const std::size_t last_idx = sizeof_typelist<Typelist>::value - 1; - typedef typelist - <typename typelist_element<last_idx - Ints, Typelist>::type...> type; -}; - -template<class Typelist, int Int> -struct invert_typelist_impl< Typelist, index_tuple<Int> > -{ - typedef Typelist type; -}; - -template<class Typelist> -struct invert_typelist_impl< Typelist, index_tuple<> > -{ - typedef Typelist type; -}; - -//invert_typelist -template<class Typelist> -struct invert_typelist; - -template<class ...Types> -struct invert_typelist< typelist<Types...> > -{ - typedef typelist<Types...> typelist_t; - typedef typename build_number_seq<sizeof...(Types)>::type indexes_t; - typedef typename invert_typelist_impl<typelist_t, indexes_t>::type type; -}; - -//Do pack -template<class Typelist> -struct do_pack; - -template<> -struct do_pack<typelist<> >; - -template<class Prev> -struct do_pack<typelist<Prev> > -{ - typedef Prev type; -}; - -template<class Prev, class Last> -struct do_pack<typelist<Prev, Last> > -{ - typedef typename Prev::template pack<Last> type; -}; - -template<class Prev, class ...Others> -struct do_pack<typelist<Prev, Others...> > -{ - typedef typename Prev::template pack - <typename do_pack<typelist<Others...> >::type> type; -}; - - -template<class ...Options> -struct pack_options -{ - typedef typelist<Options...> typelist_t; - typedef typename invert_typelist<typelist_t>::type inverted_typelist; - typedef typename do_pack<inverted_typelist>::type type; -}; - -#endif - -struct hook_defaults - : public pack_options - < none - , void_pointer<void*> - , link_mode<safe_link> - , tag<default_tag> - , optimize_size<false> - , store_hash<false> - , linear<false> - , optimize_multikey<false> - >::type -{}; - -/// @endcond - -} //namespace intrusive { -} //namespace boost { - -#include <boost/intrusive/detail/config_end.hpp> - -#endif //#ifndef BOOST_INTRUSIVE_OPTIONS_HPP |