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
25namespace boost {
26namespace intrusive {
27
28#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
29
30struct empty
31{};
32
33template<class Functor>
34struct fhtraits;
35
36template<class T, class Hook, Hook T::* P>
37struct mhtraits;
38
39struct dft_tag;
40struct member_tag;
41
42template<class SupposedValueTraits>
43struct 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.
50BOOST_INTRUSIVE_OPTION_CONSTANT(constant_time_size, bool, Enabled, constant_time_size)
51
52//!This option setter specifies a container header holder type
53BOOST_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.
57BOOST_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
61BOOST_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
70BOOST_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
79BOOST_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.
93BOOST_INTRUSIVE_OPTION_CONSTANT(floating_point, bool, Enabled, floating_point)
94
95//!This option setter specifies the equality
96//!functor for the value type
97BOOST_INTRUSIVE_OPTION_TYPE(equal, Equal, Equal, equal)
98
99//!This option setter specifies the priority comparison
100//!functor for the value type
101BOOST_INTRUSIVE_OPTION_TYPE(priority, Priority, Priority, priority)
102
103//!This option setter specifies the hash
104//!functor for the value type
105BOOST_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.
110BOOST_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.
129template< typename Parent
130 , typename MemberHook
131 , MemberHook Parent::* PtrToMember>
132struct 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.
160BOOST_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
164BOOST_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
170BOOST_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
176BOOST_INTRUSIVE_OPTION_TYPE(tag, Tag, Tag, tag)
177
178//!This option setter specifies the link mode
179//!(normal_link, safe_link or auto_unlink)
180BOOST_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.
184BOOST_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.
188BOOST_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().
193BOOST_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
198BOOST_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.
205BOOST_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.
213BOOST_INTRUSIVE_OPTION_CONSTANT(optimize_multikey, bool, Enabled, optimize_multikey)
214
215//!This option setter specifies if the length of the bucket array provided by
216//!the user will always be power of two.
217//!This allows using masks instead of the default modulo operation to determine
218//!the bucket number from the hash value, leading to better performance.
219//!In debug mode, the provided bucket array length will be checked with assertions.
220BOOST_INTRUSIVE_OPTION_CONSTANT(power_2_buckets, bool, Enabled, power_2_buckets)
221
222//!WARNING: this option is EXPERIMENTAL, don't use it in production code
223//!This option setter specifies if the length of the bucket array provided by
224//!the user will always be a value specified by the
225//!suggested_upper|lower_bucket_count call. This allows the use of some
226//!precomputed values and speeds hash to bucket index operations, leading
227//!to better performance.
228//!In debug mode, the provided bucket array length will be checked with assertions.
229BOOST_INTRUSIVE_OPTION_CONSTANT(fastmod_buckets, bool, Enabled, fastmod_buckets)
230
231//!This option setter specifies if the container will cache a pointer to the first
232//!non-empty bucket so that begin() is always constant-time.
233//!This is specially helpful when we can have containers with a few elements
234//!but with big bucket arrays (that is, hashtables with low load factors).
235BOOST_INTRUSIVE_OPTION_CONSTANT(cache_begin, bool, Enabled, cache_begin)
236
237//!This option setter specifies if the container will compare the hash value
238//!before comparing objects. This option can't be specified if store_hash<>
239//!is not true.
240//!This is specially helpful when we have containers with a high load factor.
241//!and the comparison function is much more expensive that comparing already
242//!stored hash values.
243BOOST_INTRUSIVE_OPTION_CONSTANT(compare_hash, bool, Enabled, compare_hash)
244
245//!This option setter specifies if the hash container will use incremental
246//!hashing. With incremental hashing the cost of hash table expansion is spread
247//!out across each hash table insertion operation, as opposed to be incurred all at once.
248//!Therefore linear hashing is well suited for interactive applications or real-time
249//!appplications where the worst-case insertion time of non-incremental hash containers
250//!(rehashing the whole bucket array) is not admisible.
251BOOST_INTRUSIVE_OPTION_CONSTANT(incremental, bool, Enabled, incremental)
252
253//!This option setter specifies if the buckets (which form a singly linked lists of nodes)
254//!are linear (true) or circular (false, default value). Linear buckets can improve performance
255//!in some cases, but the container loses some features like obtaining an iterator from a value.
256BOOST_INTRUSIVE_OPTION_CONSTANT(linear_buckets, bool, Enabled, linear_buckets)
257
258/// @cond
259
260struct hook_defaults
261{
262 typedef void* void_pointer;
263 static const link_mode_type link_mode = safe_link;
264 typedef dft_tag tag;
265 static const bool optimize_size = false;
266 static const bool store_hash = false;
267 static const bool linear = false;
268 static const bool optimize_multikey = false;
269};
270
271/// @endcond
272
273} //namespace intrusive {
274} //namespace boost {
275
276#include <boost/intrusive/detail/config_end.hpp>
277
278#endif //#ifndef BOOST_INTRUSIVE_OPTIONS_HPP
279

source code of boost/libs/intrusive/include/boost/intrusive/options.hpp