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 {
17 using cds::intrusive::ellen_bintree::implementation_tag;
20 #ifdef CDS_DOXYGEN_INVOKED
21 /// Typedef for \p cds::intrusive::ellen_bintree::update_desc
22 typedef cds::intrusive::ellen_bintree::update_desc update_desc;
24 /// Typedef for \p cds::intrusive::ellen_bintree::internal_node
25 typedef cds::intrusive::ellen_bintree::internal_node internal_node;
27 /// Typedef for \p cds::intrusive::ellen_bintree::key_extractor
28 typedef cds::intrusive::ellen_bintree::key_extractor key_extractor;
30 /// Typedef for \p cds::intrusive::ellen_bintree::update_desc_allocator
31 typedef cds::intrusive::ellen_bintree::update_desc_allocator update_desc_allocator;
33 using cds::intrusive::ellen_bintree::update_desc;
34 using cds::intrusive::ellen_bintree::internal_node;
35 using cds::intrusive::ellen_bintree::key_extractor;
36 using cds::intrusive::ellen_bintree::update_desc_allocator;
37 using cds::intrusive::ellen_bintree::node_types;
39 /// EllenBinTree internal statistics
40 template <typename Counter = cds::intrusive::ellen_bintree::stat<>::event_counter >
41 using stat = cds::intrusive::ellen_bintree::stat< Counter >;
43 /// EllenBinTree empty internal statistics
44 typedef cds::intrusive::ellen_bintree::empty_stat empty_stat;
46 /// EllenBinTree leaf node
47 template <typename GC, typename T>
48 struct node: public cds::intrusive::ellen_bintree::node<GC>
50 typedef T value_type ; ///< Value type
52 T m_Value ; ///< Value
65 template <typename... Args>
66 node( Args const&... args)
71 template <typename... Args>
73 : m_Value( std::forward<Args>(args)... )
77 /// EllenBinTreeMap leaf node
78 template <typename GC, typename Key, typename T>
79 struct map_node: public cds::intrusive::ellen_bintree::node< GC >
81 typedef Key key_type ; ///< key type
82 typedef T mapped_type ; ///< value type
83 typedef std::pair<key_type const, mapped_type> value_type ; ///< key-value pair stored in the map
85 value_type m_Value ; ///< Key-value pair stored in map leaf node
87 /// Initializes key field, value if default-constructed
89 map_node( K const& key )
90 : m_Value( std::make_pair( key_type(key), mapped_type() ))
93 /// Initializes key and value fields
94 template <typename K, typename Q>
95 map_node( K const& key, Q const& v )
96 : m_Value( std::make_pair(key_type(key), mapped_type(v) ))
100 /// Type traits for EllenBinTreeSet and EllenBinTreeMap
103 /// Key extracting functor (only for \p EllenBinTreeSet)
105 You should explicit define a valid functor.
106 The functor has the following prototype:
108 struct key_extractor {
109 void operator ()( Key& dest, T const& src );
112 It should initialize \p dest key from \p src data.
113 The functor is used to initialize internal nodes of \p EllenBinTreeSet
115 typedef opt::none key_extractor;
117 /// Key comparison functor
119 No default functor is provided. If the option is not specified, the \p less is used.
121 See \p cds::opt::compare option description for functor interface.
123 You should provide \p compare or \p less functor.
124 See \ref cds_container_EllenBinTreeSet_rcu_less "predicate requirements".
126 typedef opt::none compare;
128 /// Specifies binary predicate used for key compare.
130 See \p cds::opt::less option description.
132 You should provide \p compare or \p less functor.
133 See \ref cds_container_EllenBinTreeSet_rcu_less "predicate requirements".
135 typedef opt::none less;
139 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
140 To enable it use \p atomicity::item_counter
142 typedef atomicity::empty_item_counter item_counter;
144 /// C++ memory ordering model
146 List of available memory ordering see \p opt::memory_model
148 typedef opt::v::relaxed_ordering memory_model;
150 /// Allocator for update descriptors
152 The allocator type is used for \p ellen_bintree::update_desc.
154 Update descriptor is helping data structure with short lifetime and it is good candidate
155 for pooling. The number of simultaneously existing descriptors is a small number
156 limited the number of threads working with the tree.
157 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue
158 is good choice for the free-list of update descriptors,
159 see \p cds::memory::vyukov_queue_pool free-list implementation.
161 Also notice that size of update descriptor is not dependent on the type of data
162 stored in the tree so single free-list object can be used for several \p EllenBinTree object.
164 typedef CDS_DEFAULT_ALLOCATOR update_desc_allocator;
166 /// Allocator for internal nodes
168 The allocator type is used for \p ellen_bintree::internal_node.
170 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
172 /// Allocator for leaf nodes
174 Each leaf node contains data stored in the container.
176 typedef CDS_DEFAULT_ALLOCATOR allocator;
178 /// Internal statistics
180 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
181 To enable it use \p ellen_bintree::stat.
183 typedef empty_stat stat;
185 /// Back-off strategy
186 typedef cds::backoff::empty back_off;
188 /// RCU deadlock checking policy (only for RCU-based EllenBinTree<i>XXX</i> classes)
190 List of available options see \p opt::rcu_check_deadlock
192 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
194 /// Key copy policy (for \p EllenBinTreeMap)
196 The key copy policy defines a functor to copy leaf node's key to internal node.
197 This policy is used only in \p EllenBinTreeMap.
198 By default, assignment operator is used.
200 The copy functor interface is:
202 struct copy_functor {
203 void operator()( Key& dest, Key const& src );
207 typedef opt::none copy_policy;
211 /// Metafunction converting option list to \p EllenBinTreeSet traits
214 - \p ellen_bintree::key_extractor - key extracting functor, mandatory option. The functor has the following prototype:
216 struct key_extractor {
217 void operator ()( Key& dest, T const& src );
220 It should initialize \p dest key from \p src data. The functor is used to initialize internal nodes.
221 - \p opt::compare - key compare functor. No default functor is provided.
222 If the option is not specified, \p %opt::less is used.
223 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
224 - \p opt::item_counter - the type of item counter, default is disabled (\p atomicity::empty_item_counter).
225 To enable it use \p atomicity::item_counter
226 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
227 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
228 - \p opt::allocator - the allocator for \ref ellen_bintree::node "leaf nodes" which contains data.
229 Default is \ref CDS_DEFAULT_ALLOCATOR.
230 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
231 - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
232 default is \ref CDS_DEFAULT_ALLOCATOR.
233 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
234 The number of simultaneously existing descriptors is a relatively small number limited the number of threads
235 working with the tree and RCU buffer size.
236 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list
237 of update descriptors, see \p cds::memory::vyukov_queue_pool free-list implementation.
238 Also notice that size of update descriptor is not dependent on the type of data
239 stored in the tree so single free-list object can be used for several EllenBinTree-based object.
240 - \p opt::stat - internal statistics, by default disabled (\p ellen_bintree::empty_stat). To enable
241 it use \p ellen_bintree::stat.
242 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
243 - \p opt::rcu_check_deadlock - a deadlock checking policy, only for RCU-based tree.
244 Default is \p opt::v::rcu_throw_deadlock.
246 template <typename... Options>
247 struct make_set_traits {
248 # ifdef CDS_DOXYGEN_INVOKED
249 typedef implementation_defined type ; ///< Metafunction result
251 typedef typename cds::opt::make_options<
252 typename cds::opt::find_type_traits< traits, Options... >::type
258 /// Metafunction converting option list to \p EllenBinTreeMap traits
261 - \p opt::compare - key compare functor. No default functor is provided.
262 If the option is not specified, \p %opt::less is used.
263 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
264 - \p opt::item_counter - the type of item counter, default is disabled (\p atomicity::empty_item_counter).
265 To enable it use \p atomicity::item_counter
266 - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
267 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
268 - \p opt::allocator - the allocator used for \ref ellen_bintree::map_node "leaf nodes" which contains data.
269 Default is \ref CDS_DEFAULT_ALLOCATOR.
270 - \p opt::node_allocator - the allocator used for \ref ellen_bintree::internal_node "internal nodes".
271 Default is \ref CDS_DEFAULT_ALLOCATOR.
272 - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
273 default is \ref CDS_DEFAULT_ALLOCATOR.
274 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
275 The number of simultaneously existing descriptors is a relatively small number limited the number of threads
276 working with the tree and RCU buffer size.
277 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list
278 of update descriptors, see \p cds::memory::vyukov_queue_pool free-list implementation.
279 Also notice that size of update descriptor is not dependent on the type of data
280 stored in the tree so single free-list object can be used for several EllenBinTree-based object.
281 - \p opt::stat - internal statistics, by default disabled (\p ellen_bintree::empty_stat). To enable
282 it use \p ellen_bintree::stat.
283 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
284 - \p opt::rcu_check_deadlock - a deadlock checking policy, only for RCU-based tree. Default is \p opt::v::rcu_throw_deadlock
285 - opt::copy_policy - key copying policy defines a functor to copy leaf node's key to internal node.
286 By default, assignment operator is used.
287 The copy functor interface is:
289 struct copy_functor {
290 void operator()( Key& dest, Key const& src );
294 template <typename... Options>
295 struct make_map_traits {
296 # ifdef CDS_DOXYGEN_INVOKED
297 typedef implementation_defined type ; ///< Metafunction result
299 typedef typename cds::opt::make_options<
300 typename cds::opt::find_type_traits< traits, Options... >::type
309 template < class GC, typename Key, typename T, class Traits>
310 struct make_ellen_bintree_set
313 typedef Key key_type;
314 typedef T value_type;
315 typedef Traits original_traits;
317 typedef node< gc, value_type > leaf_node;
319 struct intrusive_key_extractor
321 void operator()( key_type& dest, leaf_node const& src ) const
323 typename original_traits::key_extractor()( dest, src.m_Value );
327 struct value_accessor
329 value_type const& operator()( leaf_node const& node ) const
335 typedef typename cds::opt::details::make_comparator< value_type, original_traits, false >::type key_comparator;
337 typedef cds::details::Allocator< leaf_node, typename original_traits::allocator> cxx_leaf_node_allocator;
338 struct leaf_deallocator
340 void operator()( leaf_node * p ) const
342 cxx_leaf_node_allocator().Delete( p );
346 struct intrusive_traits: public original_traits
348 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc > > hook;
349 typedef intrusive_key_extractor key_extractor;
350 typedef leaf_deallocator disposer;
351 typedef cds::details::compare_wrapper< leaf_node, key_comparator, value_accessor > compare;
354 // Metafunction result
355 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_traits > type;
358 template < class GC, typename Key, typename T, class Traits>
359 struct make_ellen_bintree_map
362 typedef Key key_type;
363 typedef T mapped_type;
364 typedef map_node< gc, key_type, mapped_type > leaf_node;
365 typedef typename leaf_node::value_type value_type;
367 typedef Traits original_traits;
369 struct assignment_copy_policy {
370 void operator()( key_type& dest, key_type const& src )
375 typedef typename std::conditional<
376 std::is_same< typename original_traits::copy_policy, opt::none >::value,
377 assignment_copy_policy,
378 typename original_traits::copy_policy
381 struct intrusive_key_extractor
383 void operator()( key_type& dest, leaf_node const& src ) const
385 copy_policy()( dest, src.m_Value.first );
391 key_type const& operator()( leaf_node const& node ) const
393 return node.m_Value.first;
397 typedef typename cds::opt::details::make_comparator< key_type, original_traits, false >::type key_comparator;
399 typedef cds::details::Allocator< leaf_node, typename original_traits::allocator> cxx_leaf_node_allocator;
400 struct leaf_deallocator
402 void operator()( leaf_node * p ) const
404 cxx_leaf_node_allocator().Delete( p );
408 struct intrusive_traits: public original_traits
410 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc > > hook;
411 typedef intrusive_key_extractor key_extractor;
412 typedef leaf_deallocator disposer;
413 typedef cds::details::compare_wrapper< leaf_node, key_comparator, key_accessor > compare;
416 // Metafunction result
417 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_traits > type;
420 } // namespace details
422 } // namespace ellen_bintree
424 // Forward declarations
426 template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
427 class EllenBinTreeSet;
429 template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
430 class EllenBinTreeMap;
433 }} // namespace cds::container
435 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H