1 /////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Ion Gaztanaga 2007-2009
5 // Distributed under the Boost Software License, Version 1.0.
6 // (See accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
9 // See http://www.boost.org/libs/intrusive for documentation.
11 /////////////////////////////////////////////////////////////////////////////
13 #ifndef BOOST_INTRUSIVE_OPTIONS_HPP
14 #define BOOST_INTRUSIVE_OPTIONS_HPP
16 #include <boost/intrusive/detail/config_begin.hpp>
17 #include <boost/intrusive/intrusive_fwd.hpp>
18 #include <boost/intrusive/link_mode.hpp>
19 #include <boost/intrusive/detail/mpl.hpp>
20 #include <boost/intrusive/detail/utilities.hpp>
21 #include <boost/static_assert.hpp>
34 struct default_hook_tag{};
36 #define BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER) \
37 struct BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER : public default_hook_tag\
41 { typedef typename T::BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER type; };\
44 BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_list_hook);
45 BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_slist_hook);
46 BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_set_hook);
47 BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_uset_hook);
48 BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_avl_set_hook);
49 BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_splay_set_hook);
50 BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_bs_set_hook);
52 #undef BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION
54 template <class ValueTraits>
55 struct eval_value_traits
57 typedef typename ValueTraits::value_traits type;
61 struct external_bucket_traits_is_true
63 static const bool value = external_bucket_traits_bool<T>::value == 3;
66 template <class BucketTraits>
67 struct eval_bucket_traits
69 typedef typename BucketTraits::bucket_traits type;
72 template <class T, class BaseHook>
73 struct concrete_hook_base_value_traits
75 typedef typename BaseHook::boost_intrusive_tags tags;
76 typedef detail::base_hook_traits
78 , typename tags::node_traits
81 , tags::hook_type> type;
84 template <class BaseHook>
85 struct concrete_hook_base_node_traits
86 { typedef typename BaseHook::boost_intrusive_tags::node_traits type; };
88 template <class T, class BaseHook>
89 struct any_hook_base_value_traits
91 typedef typename BaseHook::boost_intrusive_tags tags;
92 typedef detail::base_hook_traits
94 , typename BaseHook::node_traits
97 , tags::hook_type> type;
100 template <class BaseHook>
101 struct any_hook_base_node_traits
102 { typedef typename BaseHook::node_traits type; };
104 template<class T, class BaseHook>
105 struct get_base_value_traits
107 typedef typename detail::eval_if_c
108 < internal_any_hook_bool_is_true<BaseHook>::value
109 , any_hook_base_value_traits<T, BaseHook>
110 , concrete_hook_base_value_traits<T, BaseHook>
114 template<class BaseHook>
115 struct get_base_node_traits
117 typedef typename detail::eval_if_c
118 < internal_any_hook_bool_is_true<BaseHook>::value
119 , any_hook_base_node_traits<BaseHook>
120 , concrete_hook_base_node_traits<BaseHook>
124 template<class T, class MemberHook>
125 struct get_member_value_traits
127 typedef typename MemberHook::member_value_traits type;
130 template<class MemberHook>
131 struct get_member_node_traits
133 typedef typename MemberHook::member_value_traits::node_traits type;
136 template<class T, class SupposedValueTraits>
137 struct get_value_traits
139 typedef typename detail::eval_if_c
140 <detail::is_convertible<SupposedValueTraits*, detail::default_hook_tag*>::value
141 ,detail::apply<SupposedValueTraits, T>
142 ,detail::identity<SupposedValueTraits>
143 >::type supposed_value_traits;
144 //...if it's a default hook
145 typedef typename detail::eval_if_c
146 < internal_base_hook_bool_is_true<supposed_value_traits>::value
147 //...get it's internal value traits using
148 //the provided T value type.
149 , get_base_value_traits<T, supposed_value_traits>
150 //...else use it's internal value traits tag
151 //(member hooks and custom value traits are in this group)
153 < internal_member_value_traits<supposed_value_traits>::value
154 , get_member_value_traits<T, supposed_value_traits>
155 , detail::identity<supposed_value_traits>
160 template<class ValueTraits>
161 struct get_explicit_node_traits
163 typedef typename ValueTraits::node_traits type;
166 template<class SupposedValueTraits>
167 struct get_node_traits
169 typedef SupposedValueTraits supposed_value_traits;
170 //...if it's a base hook
171 typedef typename detail::eval_if_c
172 < internal_base_hook_bool_is_true<supposed_value_traits>::value
173 //...get it's internal value traits using
174 //the provided T value type.
175 , get_base_node_traits<supposed_value_traits>
176 //...else use it's internal value traits tag
177 //(member hooks and custom value traits are in this group)
179 < internal_member_value_traits<supposed_value_traits>::value
180 , get_member_node_traits<supposed_value_traits>
181 , get_explicit_node_traits<supposed_value_traits>
186 } //namespace detail{
189 //!This type indicates that no option is being used
190 //!and that the default options should be used
200 //!This option setter specifies if the intrusive
201 //!container stores its size as a member to
202 //!obtain constant-time size() member.
203 template<bool Enabled>
204 struct constant_time_size
210 static const bool constant_time_size = Enabled;
215 //!This option setter specifies the type that
216 //!the container will use to store its size.
217 template<class SizeType>
224 typedef SizeType size_type;
229 //!This option setter specifies the strict weak ordering
230 //!comparison functor for the value type
231 template<class Compare>
238 typedef Compare compare;
243 //!This option setter for scapegoat containers specifies if
244 //!the intrusive scapegoat container should use a non-variable
245 //!alpha value that does not need floating-point operations.
247 //!If activated, the fixed alpha value is 1/sqrt(2). This
248 //!option also saves some space in the container since
249 //!the alpha value and some additional data does not need
250 //!to be stored in the container.
252 //!If the user only needs an alpha value near 1/sqrt(2), this
253 //!option also improves performance since avoids logarithm
254 //!and division operations when rebalancing the tree.
255 template<bool Enabled>
256 struct floating_point
262 static const bool floating_point = Enabled;
267 //!This option setter specifies the equality
268 //!functor for the value type
269 template<class Equal>
281 //!This option setter specifies the equality
282 //!functor for the value type
283 template<class Priority>
290 typedef Priority priority;
295 //!This option setter specifies the hash
296 //!functor for the value type
309 //!This option setter specifies the relationship between the type
310 //!to be managed by the container (the value type) and the node to be
311 //!used in the node algorithms. It also specifies the linking policy.
312 template<typename ValueTraits>
319 typedef ValueTraits value_traits;
324 //!This option setter specifies the member hook the
325 //!container must use.
326 template< typename Parent
327 , typename MemberHook
328 , MemberHook Parent::* PtrToMember>
332 typedef detail::member_hook_traits
336 > member_value_traits;
340 typedef member_value_traits value_traits;
346 //!This option setter specifies the function object that will
347 //!be used to convert between values to be inserted in a container
348 //!and the hook to be used for that purpose.
349 template< typename Functor>
353 typedef detail::function_hook_traits
354 <Functor> function_value_traits;
358 typedef function_value_traits value_traits;
364 //!This option setter specifies that the container
365 //!must use the specified base hook
366 template<typename BaseHook>
373 typedef BaseHook value_traits;
378 //!This option setter specifies the type of
379 //!a void pointer. This will instruct the hook
380 //!to use this type of pointer instead of the
382 template<class VoidPointer>
389 typedef VoidPointer void_pointer;
394 //!This option setter specifies the type of
395 //!the tag of a base hook. A type cannot have two
396 //!base hooks of the same type, so a tag can be used
397 //!to differentiate two base hooks with otherwise same type
410 //!This option setter specifies the link mode
411 //!(normal_link, safe_link or auto_unlink)
412 template<link_mode_type LinkType>
419 static const link_mode_type link_mode = LinkType;
424 //!This option setter specifies if the hook
425 //!should be optimized for size instead of for speed.
426 template<bool Enabled>
433 static const bool optimize_size = Enabled;
438 //!This option setter specifies if the list container should
439 //!use a linear implementation instead of a circular one.
440 template<bool Enabled>
447 static const bool linear = Enabled;
452 //!This option setter specifies if the list container should
453 //!use a linear implementation instead of a circular one.
454 template<bool Enabled>
461 static const bool cache_last = Enabled;
466 //!This option setter specifies the bucket traits
467 //!class for unordered associative containers. When this option is specified,
468 //!instead of using the default bucket traits, a user defined holder will be defined
469 template<class BucketTraits>
476 typedef BucketTraits bucket_traits;
481 //!This option setter specifies if the unordered hook
482 //!should offer room to store the hash value.
483 //!Storing the hash in the hook will speed up rehashing
484 //!processes in applications where rehashing is frequent,
485 //!rehashing might throw or the value is heavy to hash.
486 template<bool Enabled>
493 static const bool store_hash = Enabled;
498 //!This option setter specifies if the unordered hook
499 //!should offer room to store another link to another node
500 //!with the same key.
501 //!Storing this link will speed up lookups and insertions on
502 //!unordered_multiset containers with a great number of elements
503 //!with the same key.
504 template<bool Enabled>
505 struct optimize_multikey
511 static const bool optimize_multikey = Enabled;
516 //!This option setter specifies if the bucket array will be always power of two.
517 //!This allows using masks instead of the default modulo operation to determine
518 //!the bucket number from the hash value, leading to better performance.
519 //!In debug mode, if power of two buckets mode is activated, the bucket length
520 //!will be checked to through assertions to assure the bucket length is power of two.
521 template<bool Enabled>
522 struct power_2_buckets
528 static const bool power_2_buckets = Enabled;
533 //!This option setter specifies if the container will cache a pointer to the first
534 //!non-empty bucket so that begin() is always constant-time.
535 //!This is specially helpful when we can have containers with a few elements
536 //!but with big bucket arrays (that is, hashtables with low load factors).
537 template<bool Enabled>
544 static const bool cache_begin = Enabled;
550 //!This option setter specifies if the container will compare the hash value
551 //!before comparing objects. This option can't be specified if store_hash<>
553 //!This is specially helpful when we have containers with a high load factor.
554 //!and the comparison function is much more expensive that comparing already
555 //!stored hash values.
556 template<bool Enabled>
563 static const bool compare_hash = Enabled;
568 //!This option setter specifies if the hash container will use incremental
569 //!hashing. With incremental hashing the cost of hash table expansion is spread
570 //!out across each hash table insertion operation, as opposed to be incurred all at once.
571 //!Therefore linear hashing is well suited for interactive applications or real-time
572 //!appplications where the worst-case insertion time of non-incremental hash containers
573 //!(rehashing the whole bucket array) is not admisible.
574 template<bool Enabled>
581 static const bool incremental = Enabled;
588 //To-do: pass to variadic templates
589 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
591 template<class Prev, class Next>
594 //Use "pack" member template to pack options
595 typedef typename Next::template pack<Prev> type;
599 struct do_pack<Prev, none>
601 //Avoid packing "none" to shorten template names
606 < class DefaultOptions
662 template<int... Indexes>
663 struct index_tuple{};
666 template<std::size_t Num, typename Tuple = index_tuple<> >
667 struct build_number_seq;
669 template<std::size_t Num, int... Indexes>
670 struct build_number_seq<Num, index_tuple<Indexes...> >
671 : build_number_seq<Num - 1, index_tuple<Indexes..., sizeof...(Indexes)> >
674 template<int... Indexes>
675 struct build_number_seq<0, index_tuple<Indexes...> >
676 { typedef index_tuple<Indexes...> type; };
678 template<class ...Types>
684 struct invert_typelist;
686 template<int I, typename Tuple>
687 struct typelist_element;
689 template<int I, typename Head, typename... Tail>
690 struct typelist_element<I, typelist<Head, Tail...> >
692 typedef typename typelist_element<I-1, typelist<Tail...> >::type type;
695 template<typename Head, typename... Tail>
696 struct typelist_element<0, typelist<Head, Tail...> >
701 template<int ...Ints, class ...Types>
702 typelist<typename typelist_element<(sizeof...(Types) - 1) - Ints, typelist<Types...> >::type...>
703 inverted_typelist(index_tuple<Ints...>, typelist<Types...>)
705 return typelist<typename typelist_element<(sizeof...(Types) - 1) - Ints, typelist<Types...> >::type...>();
709 template<class Typelist>
710 struct sizeof_typelist;
712 template<class ...Types>
713 struct sizeof_typelist< typelist<Types...> >
715 static const std::size_t value = sizeof...(Types);
718 //invert_typelist_impl
719 template<class Typelist, class Indexes>
720 struct invert_typelist_impl;
723 template<class Typelist, int ...Ints>
724 struct invert_typelist_impl< Typelist, index_tuple<Ints...> >
726 static const std::size_t last_idx = sizeof_typelist<Typelist>::value - 1;
728 <typename typelist_element<last_idx - Ints, Typelist>::type...> type;
731 template<class Typelist, int Int>
732 struct invert_typelist_impl< Typelist, index_tuple<Int> >
734 typedef Typelist type;
737 template<class Typelist>
738 struct invert_typelist_impl< Typelist, index_tuple<> >
740 typedef Typelist type;
744 template<class Typelist>
745 struct invert_typelist;
747 template<class ...Types>
748 struct invert_typelist< typelist<Types...> >
750 typedef typelist<Types...> typelist_t;
751 typedef typename build_number_seq<sizeof...(Types)>::type indexes_t;
752 typedef typename invert_typelist_impl<typelist_t, indexes_t>::type type;
756 template<class Typelist>
760 struct do_pack<typelist<> >;
763 struct do_pack<typelist<Prev> >
768 template<class Prev, class Last>
769 struct do_pack<typelist<Prev, Last> >
771 typedef typename Prev::template pack<Last> type;
774 template<class Prev, class ...Others>
775 struct do_pack<typelist<Prev, Others...> >
777 typedef typename Prev::template pack
778 <typename do_pack<typelist<Others...> >::type> type;
782 template<class ...Options>
785 typedef typelist<Options...> typelist_t;
786 typedef typename invert_typelist<typelist_t>::type inverted_typelist;
787 typedef typename do_pack<inverted_typelist>::type type;
793 : public pack_options
795 , void_pointer<void*>
796 , link_mode<safe_link>
798 , optimize_size<false>
801 , optimize_multikey<false>
807 } //namespace intrusive {
808 } //namespace boost {
810 #include <boost/intrusive/detail/config_end.hpp>
812 #endif //#ifndef BOOST_INTRUSIVE_OPTIONS_HPP