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