3 #ifndef CDSLIB_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H
4 #define CDSLIB_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H
6 #include <cds/intrusive/details/ellen_bintree_base.h>
7 #include <cds/container/details/base.h>
8 #include <cds/opt/compare.h>
9 #include <cds/details/binary_functor_wrapper.h>
12 namespace cds { namespace container {
13 /// EllenBinTree related definitions
14 /** @ingroup cds_nonintrusive_helper
16 namespace ellen_bintree {
18 #ifdef CDS_DOXYGEN_INVOKED
19 /// Typedef for \p cds::intrusive::ellen_bintree::update_desc
20 typedef cds::intrusive::ellen_bintree::update_desc update_desc;
22 /// Typedef for \p cds::intrusive::ellen_bintree::internal_node
23 typedef cds::intrusive::ellen_bintree::internal_node internal_node;
25 /// Typedef for \p cds::intrusive::ellen_bintree::key_extractor
26 typedef cds::intrusive::ellen_bintree::key_extractor key_extractor;
28 /// Typedef for \p cds::intrusive::ellen_bintree::update_desc_allocator
29 typedef cds::intrusive::ellen_bintree::update_desc_allocator update_desc_allocator;
31 using cds::intrusive::ellen_bintree::update_desc;
32 using cds::intrusive::ellen_bintree::internal_node;
33 using cds::intrusive::ellen_bintree::key_extractor;
34 using cds::intrusive::ellen_bintree::update_desc_allocator;
35 using cds::intrusive::ellen_bintree::node_types;
37 /// EllenBinTree internal statistics
38 template <typename Counter = cds::intrusive::ellen_bintree::stat<>::event_counter >
39 using stat = cds::intrusive::ellen_bintree::stat< Counter >;
41 /// EllenBinTree empty internal statistics
42 typedef cds::intrusive::ellen_bintree::empty_stat empty_stat;
44 /// EllenBinTree leaf node
45 template <typename GC, typename T>
46 struct node: public cds::intrusive::ellen_bintree::node<GC>
48 typedef T value_type ; ///< Value type
50 T m_Value ; ///< Value
63 template <typename... Args>
64 node( Args const&... args)
69 template <typename... Args>
71 : m_Value( std::forward<Args>(args)... )
75 /// EllenBinTreeMap leaf node
76 template <typename GC, typename Key, typename T>
77 struct map_node: public cds::intrusive::ellen_bintree::node< GC >
79 typedef Key key_type ; ///< key type
80 typedef T mapped_type ; ///< value type
81 typedef std::pair<key_type const, mapped_type> value_type ; ///< key-value pair stored in the map
83 value_type m_Value ; ///< Key-value pair stored in map leaf node
85 /// Initializes key field, value if default-constructed
87 map_node( K const& key )
88 : m_Value( std::make_pair( key_type(key), mapped_type() ))
91 /// Initializes key and value fields
92 template <typename K, typename Q>
93 map_node( K const& key, Q const& v )
94 : m_Value( std::make_pair(key_type(key), mapped_type(v) ))
98 /// Type traits for EllenBinTreeSet and EllenBinTreeMap
101 /// Key extracting functor (only for \p EllenBinTreeSet)
103 You should explicit define a valid functor.
104 The functor has the following prototype:
106 struct key_extractor {
107 void operator ()( Key& dest, T const& src );
110 It should initialize \p dest key from \p src data.
111 The functor is used to initialize internal nodes of \p EllenBinTreeSet
113 typedef opt::none key_extractor;
115 /// Key comparison functor
117 No default functor is provided. If the option is not specified, the \p less is used.
119 See \p cds::opt::compare option description for functor interface.
121 You should provide \p compare or \p less functor.
122 See \ref cds_container_EllenBinTreeSet_rcu_less "predicate requirements".
124 typedef opt::none compare;
126 /// Specifies binary predicate used for key compare.
128 See \p cds::opt::less option description.
130 You should provide \p compare or \p less functor.
131 See \ref cds_container_EllenBinTreeSet_rcu_less "predicate requirements".
133 typedef opt::none less;
137 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
138 To enable it use \p atomicity::item_counter
140 typedef atomicity::empty_item_counter item_counter;
142 /// C++ memory ordering model
144 List of available memory ordering see \p opt::memory_model
146 typedef opt::v::relaxed_ordering memory_model;
148 /// Allocator for update descriptors
150 The allocator type is used for \p ellen_bintree::update_desc.
152 Update descriptor is helping data structure with short lifetime and it is good candidate
153 for pooling. The number of simultaneously existing descriptors is a small number
154 limited the number of threads working with the tree.
155 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue
156 is good choice for the free-list of update descriptors,
157 see \p cds::memory::vyukov_queue_pool free-list implementation.
159 Also notice that size of update descriptor is not dependent on the type of data
160 stored in the tree so single free-list object can be used for several \p EllenBinTree object.
162 typedef CDS_DEFAULT_ALLOCATOR update_desc_allocator;
164 /// Allocator for internal nodes
166 The allocator type is used for \p ellen_bintree::internal_node.
168 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
170 /// Allocator for leaf nodes
172 Each leaf node contains data stored in the container.
174 typedef CDS_DEFAULT_ALLOCATOR allocator;
176 /// Internal statistics
178 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
179 To enable it use \p ellen_bintree::stat.
181 typedef empty_stat stat;
183 /// Back-off strategy
184 typedef cds::backoff::empty back_off;
186 /// RCU deadlock checking policy (only for RCU-based EllenBinTree<i>XXX</i> classes)
188 List of available options see \p opt::rcu_check_deadlock
190 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
192 /// Key copy policy (for \p EllenBinTreeMap)
194 The key copy policy defines a functor to copy leaf node's key to internal node.
195 This policy is used only in \p EllenBinTreeMap.
196 By default, assignment operator is used.
198 The copy functor interface is:
200 struct copy_functor {
201 void operator()( Key& dest, Key const& src );
205 typedef opt::none copy_policy;
209 /// Metafunction converting option list to \p EllenBinTreeSet traits
212 - \p ellen_bintree::key_extractor - key extracting functor, mandatory option. The functor has the following prototype:
214 struct key_extractor {
215 void operator ()( Key& dest, T const& src );
218 It should initialize \p dest key from \p src data. The functor is used to initialize internal nodes.
219 - \p opt::compare - key compare functor. No default functor is provided.
220 If the option is not specified, \p %opt::less is used.
221 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
222 - \p opt::item_counter - the type of item counter, default is disabled (\p atomicity::empty_item_counter).
223 To enable it use \p atomicity::item_counter
224 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
225 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
226 - \p opt::allocator - the allocator for \ref ellen_bintree::node "leaf nodes" which contains data.
227 Default is \ref CDS_DEFAULT_ALLOCATOR.
228 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
229 - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
230 default is \ref CDS_DEFAULT_ALLOCATOR.
231 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
232 The number of simultaneously existing descriptors is a relatively small number limited the number of threads
233 working with the tree and RCU buffer size.
234 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list
235 of update descriptors, see \p cds::memory::vyukov_queue_pool free-list implementation.
236 Also notice that size of update descriptor is not dependent on the type of data
237 stored in the tree so single free-list object can be used for several EllenBinTree-based object.
238 - \p opt::stat - internal statistics, by default disabled (\p ellen_bintree::empty_stat). To enable
239 it use \p ellen_bintree::stat.
240 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
241 - \p opt::rcu_check_deadlock - a deadlock checking policy, only for RCU-based tree.
242 Default is \p opt::v::rcu_throw_deadlock.
244 template <typename... Options>
245 struct make_set_traits {
246 # ifdef CDS_DOXYGEN_INVOKED
247 typedef implementation_defined type ; ///< Metafunction result
249 typedef typename cds::opt::make_options<
250 typename cds::opt::find_type_traits< traits, Options... >::type
256 /// Metafunction converting option list to \p EllenBinTreeMap traits
259 - \p opt::compare - key compare functor. No default functor is provided.
260 If the option is not specified, \p %opt::less is used.
261 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
262 - \p opt::item_counter - the type of item counter, default is disabled (\p atomicity::empty_item_counter).
263 To enable it use \p atomicity::item_counter
264 - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
265 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
266 - \p opt::allocator - the allocator used for \ref ellen_bintree::map_node "leaf nodes" which contains data.
267 Default is \ref CDS_DEFAULT_ALLOCATOR.
268 - \p opt::node_allocator - the allocator used for \ref ellen_bintree::internal_node "internal nodes".
269 Default is \ref CDS_DEFAULT_ALLOCATOR.
270 - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
271 default is \ref CDS_DEFAULT_ALLOCATOR.
272 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
273 The number of simultaneously existing descriptors is a relatively small number limited the number of threads
274 working with the tree and RCU buffer size.
275 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list
276 of update descriptors, see \p cds::memory::vyukov_queue_pool free-list implementation.
277 Also notice that size of update descriptor is not dependent on the type of data
278 stored in the tree so single free-list object can be used for several EllenBinTree-based object.
279 - \p opt::stat - internal statistics, by default disabled (\p ellen_bintree::empty_stat). To enable
280 it use \p ellen_bintree::stat.
281 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
282 - \p opt::rcu_check_deadlock - a deadlock checking policy, only for RCU-based tree. Default is \p opt::v::rcu_throw_deadlock
283 - opt::copy_policy - key copying policy defines a functor to copy leaf node's key to internal node.
284 By default, assignment operator is used.
285 The copy functor interface is:
287 struct copy_functor {
288 void operator()( Key& dest, Key const& src );
292 template <typename... Options>
293 struct make_map_traits {
294 # ifdef CDS_DOXYGEN_INVOKED
295 typedef implementation_defined type ; ///< Metafunction result
297 typedef typename cds::opt::make_options<
298 typename cds::opt::find_type_traits< traits, Options... >::type
307 template < class GC, typename Key, typename T, class Traits>
308 struct make_ellen_bintree_set
311 typedef Key key_type;
312 typedef T value_type;
313 typedef Traits original_traits;
315 typedef node< gc, value_type > leaf_node;
317 struct intrusive_key_extractor
319 void operator()( key_type& dest, leaf_node const& src ) const
321 typename original_traits::key_extractor()( dest, src.m_Value );
325 struct value_accessor
327 value_type const& operator()( leaf_node const& node ) const
333 typedef typename cds::opt::details::make_comparator< value_type, original_traits, false >::type key_comparator;
335 typedef cds::details::Allocator< leaf_node, typename original_traits::allocator> cxx_leaf_node_allocator;
336 struct leaf_deallocator
338 void operator()( leaf_node * p ) const
340 cxx_leaf_node_allocator().Delete( p );
344 struct intrusive_traits: public original_traits
346 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc > > hook;
347 typedef intrusive_key_extractor key_extractor;
348 typedef leaf_deallocator disposer;
349 typedef cds::details::compare_wrapper< leaf_node, key_comparator, value_accessor > compare;
352 // Metafunction result
353 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_traits > type;
356 template < class GC, typename Key, typename T, class Traits>
357 struct make_ellen_bintree_map
360 typedef Key key_type;
361 typedef T mapped_type;
362 typedef map_node< gc, key_type, mapped_type > leaf_node;
363 typedef typename leaf_node::value_type value_type;
365 typedef Traits original_traits;
367 struct assignment_copy_policy {
368 void operator()( key_type& dest, key_type const& src )
373 typedef typename std::conditional<
374 std::is_same< typename original_traits::copy_policy, opt::none >::value,
375 assignment_copy_policy,
376 typename original_traits::copy_policy
379 struct intrusive_key_extractor
381 void operator()( key_type& dest, leaf_node const& src ) const
383 copy_policy()( dest, src.m_Value.first );
389 key_type const& operator()( leaf_node const& node ) const
391 return node.m_Value.first;
395 typedef typename cds::opt::details::make_comparator< key_type, original_traits, false >::type key_comparator;
397 typedef cds::details::Allocator< leaf_node, typename original_traits::allocator> cxx_leaf_node_allocator;
398 struct leaf_deallocator
400 void operator()( leaf_node * p ) const
402 cxx_leaf_node_allocator().Delete( p );
406 struct intrusive_traits: public original_traits
408 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc > > hook;
409 typedef intrusive_key_extractor key_extractor;
410 typedef leaf_deallocator disposer;
411 typedef cds::details::compare_wrapper< leaf_node, key_comparator, key_accessor > compare;
414 // Metafunction result
415 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_traits > type;
418 } // namespace details
420 } // namespace ellen_bintree
422 // Forward declarations
424 template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
425 class EllenBinTreeSet;
427 template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
428 class EllenBinTreeMap;
431 }} // namespace cds::container
433 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H