boost/intrusive/options.hpp
///////////////////////////////////////////////////////////////////////////// // // (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