1 ///////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2007-2014 4 // 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) 8 // 9 // See http://www.boost.org/libs/intrusive for documentation. 10 // 11 ///////////////////////////////////////////////////////////////////////////// 12 13 #ifndef BOOST_INTRUSIVE_OPTIONS_HPP 14 #define BOOST_INTRUSIVE_OPTIONS_HPP 15 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/pack_options.hpp> 20 21 #if defined(BOOST_HAS_PRAGMA_ONCE) 22 # pragma once 23 #endif 24 25 namespace boost { 26 namespace intrusive { 27 28 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 29 30 struct empty 31 {}; 32 33 template<class Functor> 34 struct fhtraits; 35 36 template<class T, class Hook, Hook T::* P> 37 struct mhtraits; 38 39 struct dft_tag; 40 struct member_tag; 41 42 template<class SupposedValueTraits> 43 struct is_default_hook_tag; 44 45 #endif //#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 46 47 //!This option setter specifies if the intrusive 48 //!container stores its size as a member to 49 //!obtain constant-time size() member. 50 BOOST_INTRUSIVE_OPTION_CONSTANT(constant_time_size, bool, Enabled, constant_time_size) 51 52 //!This option setter specifies a container header holder type 53 BOOST_INTRUSIVE_OPTION_TYPE(header_holder_type, HeaderHolder, HeaderHolder, header_holder_type) 54 55 //!This option setter specifies the type that 56 //!the container will use to store its size. 57 BOOST_INTRUSIVE_OPTION_TYPE(size_type, SizeType, SizeType, size_type) 58 59 //!This option setter specifies the strict weak ordering 60 //!comparison functor for the value type 61 BOOST_INTRUSIVE_OPTION_TYPE(compare, Compare, Compare, compare) 62 63 //!This option setter specifies a function object 64 //!that specifies the type of the key of an associative 65 //!container and an operator to obtain it from a value type. 66 //! 67 //!This function object must the define a `type` member typedef and 68 //!a member with signature `type [const&] operator()(const value_type &) const` 69 //!that will return the key from a value_type of an associative container 70 BOOST_INTRUSIVE_OPTION_TYPE(key_of_value, KeyOfValue, KeyOfValue, key_of_value) 71 72 //!This option setter specifies a function object 73 //!that specifies the type of the priority of a treap 74 //!container and an operator to obtain it from a value type. 75 //! 76 //!This function object must the define a `type` member typedef and 77 //!a member with signature `type [const&] operator()(const value_type &) const` 78 //!that will return the priority from a value_type of a treap container 79 BOOST_INTRUSIVE_OPTION_TYPE(priority_of_value, PrioOfValue, PrioOfValue, priority_of_value) 80 81 //!This option setter for scapegoat containers specifies if 82 //!the intrusive scapegoat container should use a non-variable 83 //!alpha value that does not need floating-point operations. 84 //! 85 //!If activated, the fixed alpha value is 1/sqrt(2). This 86 //!option also saves some space in the container since 87 //!the alpha value and some additional data does not need 88 //!to be stored in the container. 89 //! 90 //!If the user only needs an alpha value near 1/sqrt(2), this 91 //!option also improves performance since avoids logarithm 92 //!and division operations when rebalancing the tree. 93 BOOST_INTRUSIVE_OPTION_CONSTANT(floating_point, bool, Enabled, floating_point) 94 95 //!This option setter specifies the equality 96 //!functor for the value type 97 BOOST_INTRUSIVE_OPTION_TYPE(equal, Equal, Equal, equal) 98 99 //!This option setter specifies the priority comparison 100 //!functor for the value type 101 BOOST_INTRUSIVE_OPTION_TYPE(priority, Priority, Priority, priority) 102 103 //!This option setter specifies the hash 104 //!functor for the value type 105 BOOST_INTRUSIVE_OPTION_TYPE(hash, Hash, Hash, hash) 106 107 //!This option setter specifies the relationship between the type 108 //!to be managed by the container (the value type) and the node to be 109 //!used in the node algorithms. It also specifies the linking policy. 110 BOOST_INTRUSIVE_OPTION_TYPE(value_traits, ValueTraits, ValueTraits, proto_value_traits) 111 112 //#define BOOST_INTRUSIVE_COMMA , 113 //#define BOOST_INTRUSIVE_LESS < 114 //#define BOOST_INTRUSIVE_MORE > 115 //BOOST_INTRUSIVE_OPTION_TYPE (member_hook, Parent BOOST_INTRUSIVE_COMMA class MemberHook BOOST_INTRUSIVE_COMMA MemberHook Parent::* PtrToMember , mhtraits BOOST_INTRUSIVE_LESS Parent BOOST_INTRUSIVE_COMMA MemberHook BOOST_INTRUSIVE_COMMA PtrToMember BOOST_INTRUSIVE_MORE , proto_value_traits) 116 //template< class Parent , class MemberHook , MemberHook Parent::* PtrToMember> 117 //struct member_hook { 118 // template<class Base> struct pack : Base { 119 // typedef mhtraits < Parent , MemberHook , PtrToMember > proto_value_traits; 120 // }; 121 //}; 122 // 123 //#undef BOOST_INTRUSIVE_COMMA 124 //#undef BOOST_INTRUSIVE_LESS 125 //#undef BOOST_INTRUSIVE_MORE 126 127 //!This option setter specifies the member hook the 128 //!container must use. 129 template< typename Parent 130 , typename MemberHook 131 , MemberHook Parent::* PtrToMember> 132 struct member_hook 133 { 134 // @cond 135 // typedef typename MemberHook::hooktags::node_traits node_traits; 136 // typedef typename node_traits::node node_type; 137 // typedef node_type Parent::* Ptr2MemNode; 138 // typedef mhtraits 139 // < Parent 140 // , node_traits 141 // //This cast is really ugly but necessary to reduce template bloat. 142 // //Since we control the layout between the hook and the node, and there is 143 // //always single inheritance, the offset of the node is exactly the offset of 144 // //the hook. Since the node type is shared between all member hooks, this saves 145 // //quite a lot of symbol stuff. 146 // , (Ptr2MemNode)PtrToMember 147 // , MemberHook::hooktags::link_mode> member_value_traits; 148 typedef mhtraits <Parent, MemberHook, PtrToMember> member_value_traits; 149 template<class Base> 150 struct pack : Base 151 { 152 typedef member_value_traits proto_value_traits; 153 }; 154 /// @endcond 155 }; 156 157 //!This option setter specifies the function object that will 158 //!be used to convert between values to be inserted in a container 159 //!and the hook to be used for that purpose. 160 BOOST_INTRUSIVE_OPTION_TYPE(function_hook, Functor, fhtraits<Functor>, proto_value_traits) 161 162 //!This option setter specifies that the container 163 //!must use the specified base hook 164 BOOST_INTRUSIVE_OPTION_TYPE(base_hook, BaseHook, BaseHook, proto_value_traits) 165 166 //!This option setter specifies the type of 167 //!a void pointer. This will instruct the hook 168 //!to use this type of pointer instead of the 169 //!default one 170 BOOST_INTRUSIVE_OPTION_TYPE(void_pointer, VoidPointer, VoidPointer, void_pointer) 171 172 //!This option setter specifies the type of 173 //!the tag of a base hook. A type cannot have two 174 //!base hooks of the same type, so a tag can be used 175 //!to differentiate two base hooks with otherwise same type 176 BOOST_INTRUSIVE_OPTION_TYPE(tag, Tag, Tag, tag) 177 178 //!This option setter specifies the link mode 179 //!(normal_link, safe_link or auto_unlink) 180 BOOST_INTRUSIVE_OPTION_CONSTANT(link_mode, link_mode_type, LinkType, link_mode) 181 182 //!This option setter specifies if the hook 183 //!should be optimized for size instead of for speed. 184 BOOST_INTRUSIVE_OPTION_CONSTANT(optimize_size, bool, Enabled, optimize_size) 185 186 //!This option setter specifies if the slist container should 187 //!use a linear implementation instead of a circular one. 188 BOOST_INTRUSIVE_OPTION_CONSTANT(linear, bool, Enabled, linear) 189 190 //!If true, slist also stores a pointer to the last element of the singly linked list. 191 //!This allows O(1) swap and splice_after(iterator, slist &) for circular slists and makes 192 //!possible new functions like push_back(reference) and back(). 193 BOOST_INTRUSIVE_OPTION_CONSTANT(cache_last, bool, Enabled, cache_last) 194 195 //!This option setter specifies the bucket traits 196 //!class for unordered associative containers. When this option is specified, 197 //!instead of using the default bucket traits, a user defined holder will be defined 198 BOOST_INTRUSIVE_OPTION_TYPE(bucket_traits, BucketTraits, BucketTraits, bucket_traits) 199 200 //!This option setter specifies if the unordered hook 201 //!should offer room to store the hash value. 202 //!Storing the hash in the hook will speed up rehashing 203 //!processes in applications where rehashing is frequent, 204 //!rehashing might throw or the value is heavy to hash. 205 BOOST_INTRUSIVE_OPTION_CONSTANT(store_hash, bool, Enabled, store_hash) 206 207 //!This option setter specifies if the unordered hook 208 //!should offer room to store another link to another node 209 //!with the same key. 210 //!Storing this link will speed up lookups and insertions on 211 //!unordered_multiset containers with a great number of elements 212 //!with the same key. 213 BOOST_INTRUSIVE_OPTION_CONSTANT(optimize_multikey, bool, Enabled, optimize_multikey) 214 215 //!This option setter specifies if the bucket array will be always power of two. 216 //!This allows using masks instead of the default modulo operation to determine 217 //!the bucket number from the hash value, leading to better performance. 218 //!In debug mode, if power of two buckets mode is activated, the bucket length 219 //!will be checked with assertions. 220 BOOST_INTRUSIVE_OPTION_CONSTANT(power_2_buckets, bool, Enabled, power_2_buckets) 221 222 //!This option setter specifies if the container will cache a pointer to the first 223 //!non-empty bucket so that begin() is always constant-time. 224 //!This is specially helpful when we can have containers with a few elements 225 //!but with big bucket arrays (that is, hashtables with low load factors). 226 BOOST_INTRUSIVE_OPTION_CONSTANT(cache_begin, bool, Enabled, cache_begin) 227 228 //!This option setter specifies if the container will compare the hash value 229 //!before comparing objects. This option can't be specified if store_hash<> 230 //!is not true. 231 //!This is specially helpful when we have containers with a high load factor. 232 //!and the comparison function is much more expensive that comparing already 233 //!stored hash values. 234 BOOST_INTRUSIVE_OPTION_CONSTANT(compare_hash, bool, Enabled, compare_hash) 235 236 //!This option setter specifies if the hash container will use incremental 237 //!hashing. With incremental hashing the cost of hash table expansion is spread 238 //!out across each hash table insertion operation, as opposed to be incurred all at once. 239 //!Therefore linear hashing is well suited for interactive applications or real-time 240 //!appplications where the worst-case insertion time of non-incremental hash containers 241 //!(rehashing the whole bucket array) is not admisible. 242 BOOST_INTRUSIVE_OPTION_CONSTANT(incremental, bool, Enabled, incremental) 243 244 /// @cond 245 246 struct hook_defaults 247 { 248 typedef void* void_pointer; 249 static const link_mode_type link_mode = safe_link; 250 typedef dft_tag tag; 251 static const bool optimize_size = false; 252 static const bool store_hash = false; 253 static const bool linear = false; 254 static const bool optimize_multikey = false; 255 }; 256 257 /// @endcond 258 259 } //namespace intrusive { 260 } //namespace boost { 261 262 #include <boost/intrusive/detail/config_end.hpp> 263 264 #endif //#ifndef BOOST_INTRUSIVE_OPTIONS_HPP 265