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