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 #ifdef CDS_DOXYGEN_INVOKED
18 /// Typedef for \p cds::intrusive::ellen_bintree::update_desc
19 typedef cds::intrusive::ellen_bintree::update_desc update_desc;
21 /// Typedef for \p cds::intrusive::ellen_bintree::internal_node
22 typedef cds::intrusive::ellen_bintree::internal_node internal_node;
24 /// Typedef for \p cds::intrusive::ellen_bintree::key_extractor
25 typedef cds::intrusive::ellen_bintree::key_extractor key_extractor;
27 /// Typedef for \p cds::intrusive::ellen_bintree::update_desc_allocator
28 typedef cds::intrusive::ellen_bintree::update_desc_allocator update_desc_allocator;
30 using cds::intrusive::ellen_bintree::update_desc;
31 using cds::intrusive::ellen_bintree::internal_node;
32 using cds::intrusive::ellen_bintree::key_extractor;
33 using cds::intrusive::ellen_bintree::update_desc_allocator;
34 using cds::intrusive::ellen_bintree::node_types;
36 /// EllenBinTree internal statistics
37 template <typename Counter = cds::intrusive::ellen_bintree::stat<>::event_counter >
38 using stat = cds::intrusive::ellen_bintree::stat< Counter >;
40 /// EllenBinTree empty internal statistics
41 typedef cds::intrusive::ellen_bintree::empty_stat empty_stat;
43 /// EllenBinTree leaf node
44 template <typename GC, typename T>
45 struct node: public cds::intrusive::ellen_bintree::node<GC>
47 typedef T value_type ; ///< Value type
49 T m_Value ; ///< Value
62 template <typename... Args>
63 node( Args const&... args)
68 template <typename... Args>
70 : m_Value( std::forward<Args>(args)... )
74 /// EllenBinTreeMap leaf node
75 template <typename GC, typename Key, typename T>
76 struct map_node: public cds::intrusive::ellen_bintree::node< GC >
78 typedef Key key_type ; ///< key type
79 typedef T mapped_type ; ///< value type
80 typedef std::pair<key_type const, mapped_type> value_type ; ///< key-value pair stored in the map
82 value_type m_Value ; ///< Key-value pair stored in map leaf node
84 /// Initializes key field, value if default-constructed
86 map_node( K const& key )
87 : m_Value( std::make_pair( key_type(key), mapped_type() ))
90 /// Initializes key and value fields
91 template <typename K, typename Q>
92 map_node( K const& key, Q const& v )
93 : m_Value( std::make_pair(key_type(key), mapped_type(v) ))
97 /// Type traits for \p EllenBinTreeSet and \p EllenBinTreeMap
100 /// Key extracting functor (only for \p EllenBinTreeSet)
102 You should explicit define a valid functor.
103 The functor has the following prototype:
105 struct key_extractor {
106 void operator ()( Key& dest, T const& src );
109 It should initialize \p dest key from \p src data.
110 The functor is used to initialize internal nodes of \p EllenBinTreeSet
112 typedef opt::none key_extractor;
114 /// Key comparison functor
116 No default functor is provided. If the option is not specified, the \p less is used.
118 See \p cds::opt::compare option description for functor interface.
120 You should provide \p compare or \p less functor.
121 See \ref cds_container_EllenBinTreeSet_rcu_less "predicate requirements".
123 typedef opt::none compare;
125 /// Specifies binary predicate used for key compare.
127 See \p cds::opt::less option description.
129 You should provide \p compare or \p less functor.
130 See \ref cds_container_EllenBinTreeSet_rcu_less "predicate requirements".
132 typedef opt::none less;
136 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
137 To enable it use \p atomicity::item_counter
139 typedef atomicity::empty_item_counter item_counter;
141 /// C++ memory ordering model
143 List of available memory ordering see \p opt::memory_model
145 typedef opt::v::relaxed_ordering memory_model;
147 /// Allocator for update descriptors
149 The allocator type is used for \p ellen_bintree::update_desc.
151 Update descriptor is helping data structure with short lifetime and it is good candidate
152 for pooling. The number of simultaneously existing descriptors is a small number
153 limited the number of threads working with the tree.
154 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue
155 is good choice for the free-list of update descriptors,
156 see \p cds::memory::vyukov_queue_pool free-list implementation.
158 Also notice that size of update descriptor is not dependent on the type of data
159 stored in the tree so single free-list object can be used for several \p EllenBinTree object.
161 typedef CDS_DEFAULT_ALLOCATOR update_desc_allocator;
163 /// Allocator for internal nodes
165 The allocator type is used for \p ellen_bintree::internal_node.
167 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
169 /// Allocator for leaf nodes
171 Each leaf node contains data stored in the container.
173 typedef CDS_DEFAULT_ALLOCATOR allocator;
175 /// Internal statistics
177 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
178 To enable it use \p ellen_bintree::stat.
180 typedef empty_stat stat;
182 /// Back-off strategy
183 typedef cds::backoff::empty back_off;
185 /// RCU deadlock checking policy (only for RCU-based EllenBinTree<i>XXX</i> classes)
187 List of available options see \p opt::rcu_check_deadlock
189 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
191 /// Key copy policy (for \p EllenBinTreeMap)
193 The key copy policy defines a functor to copy leaf node's key to internal node.
194 This policy is used only in \p EllenBinTreeMap.
195 By default, assignment operator is used.
197 The copy functor interface is:
199 struct copy_functor {
200 void operator()( Key& dest, Key const& src );
204 typedef opt::none copy_policy;
208 /// Metafunction converting option list to \p EllenBinTreeSet traits
211 - \p ellen_bintree::key_extractor - key extracting functor, mandatory option. The functor has the following prototype:
213 struct key_extractor {
214 void operator ()( Key& dest, T const& src );
217 It should initialize \p dest key from \p src data. The functor is used to initialize internal nodes.
218 - \p opt::compare - key compare functor. No default functor is provided.
219 If the option is not specified, \p %opt::less is used.
220 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
221 - \p opt::item_counter - the type of item counter, default is disabled (\p atomicity::empty_item_counter).
222 To enable it use \p atomicity::item_counter
223 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
224 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
225 - \p opt::allocator - the allocator for \ref ellen_bintree::node "leaf nodes" which contains data.
226 Default is \ref CDS_DEFAULT_ALLOCATOR.
227 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
228 - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
229 default is \ref CDS_DEFAULT_ALLOCATOR.
230 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
231 The number of simultaneously existing descriptors is a relatively small number limited the number of threads
232 working with the tree and RCU buffer size.
233 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list
234 of update descriptors, see \p cds::memory::vyukov_queue_pool free-list implementation.
235 Also notice that size of update descriptor is not dependent on the type of data
236 stored in the tree so single free-list object can be used for several EllenBinTree-based object.
237 - \p opt::stat - internal statistics, by default disabled (\p ellen_bintree::empty_stat). To enable
238 it use \p ellen_bintree::stat.
239 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
240 - \p opt::rcu_check_deadlock - a deadlock checking policy, only for RCU-based tree.
241 Default is \p opt::v::rcu_throw_deadlock.
243 template <typename... Options>
244 struct make_set_traits {
245 # ifdef CDS_DOXYGEN_INVOKED
246 typedef implementation_defined type ; ///< Metafunction result
248 typedef typename cds::opt::make_options<
249 typename cds::opt::find_type_traits< traits, Options... >::type
255 /// Metafunction converting option list to \p EllenBinTreeMap traits
258 - \p opt::compare - key compare functor. No default functor is provided.
259 If the option is not specified, \p %opt::less is used.
260 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
261 - \p opt::item_counter - the type of item counter, default is disabled (\p atomicity::empty_item_counter).
262 To enable it use \p atomicity::item_counter
263 - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
264 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
265 - \p opt::allocator - the allocator used for \ref ellen_bintree::map_node "leaf nodes" which contains data.
266 Default is \ref CDS_DEFAULT_ALLOCATOR.
267 - \p opt::node_allocator - the allocator used for \ref ellen_bintree::internal_node "internal nodes".
268 Default is \ref CDS_DEFAULT_ALLOCATOR.
269 - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
270 default is \ref CDS_DEFAULT_ALLOCATOR.
271 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
272 The number of simultaneously existing descriptors is a relatively small number limited the number of threads
273 working with the tree and RCU buffer size.
274 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list
275 of update descriptors, see \p cds::memory::vyukov_queue_pool free-list implementation.
276 Also notice that size of update descriptor is not dependent on the type of data
277 stored in the tree so single free-list object can be used for several EllenBinTree-based object.
278 - \p opt::stat - internal statistics, by default disabled (\p ellen_bintree::empty_stat). To enable
279 it use \p ellen_bintree::stat.
280 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
281 - \p opt::rcu_check_deadlock - a deadlock checking policy, only for RCU-based tree. Default is \p opt::v::rcu_throw_deadlock
282 - opt::copy_policy - key copying policy defines a functor to copy leaf node's key to internal node.
283 By default, assignment operator is used.
284 The copy functor interface is:
286 struct copy_functor {
287 void operator()( Key& dest, Key const& src );
291 template <typename... Options>
292 struct make_map_traits {
293 # ifdef CDS_DOXYGEN_INVOKED
294 typedef implementation_defined type ; ///< Metafunction result
296 typedef typename cds::opt::make_options<
297 typename cds::opt::find_type_traits< traits, Options... >::type
306 template < class GC, typename Key, typename T, class Traits>
307 struct make_ellen_bintree_set
310 typedef Key key_type;
311 typedef T value_type;
312 typedef Traits original_traits;
314 typedef node< gc, value_type > leaf_node;
316 struct intrusive_key_extractor
318 void operator()( key_type& dest, leaf_node const& src ) const
320 typename original_traits::key_extractor()( dest, src.m_Value );
324 struct value_accessor
326 value_type const& operator()( leaf_node const& node ) const
332 typedef typename cds::opt::details::make_comparator< value_type, original_traits, false >::type key_comparator;
334 typedef cds::details::Allocator< leaf_node, typename original_traits::allocator> cxx_leaf_node_allocator;
335 struct leaf_deallocator
337 void operator()( leaf_node * p ) const
339 cxx_leaf_node_allocator().Delete( p );
343 struct intrusive_traits: public original_traits
345 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc > > hook;
346 typedef intrusive_key_extractor key_extractor;
347 typedef leaf_deallocator disposer;
348 typedef cds::details::compare_wrapper< leaf_node, key_comparator, value_accessor > compare;
351 // Metafunction result
352 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_traits > type;
355 template < class GC, typename Key, typename T, class Traits>
356 struct make_ellen_bintree_map
359 typedef Key key_type;
360 typedef T mapped_type;
361 typedef map_node< gc, key_type, mapped_type > leaf_node;
362 typedef typename leaf_node::value_type value_type;
364 typedef Traits original_traits;
366 struct assignment_copy_policy {
367 void operator()( key_type& dest, key_type const& src )
372 typedef typename std::conditional<
373 std::is_same< typename original_traits::copy_policy, opt::none >::value,
374 assignment_copy_policy,
375 typename original_traits::copy_policy
378 struct intrusive_key_extractor
380 void operator()( key_type& dest, leaf_node const& src ) const
382 copy_policy()( dest, src.m_Value.first );
388 key_type const& operator()( leaf_node const& node ) const
390 return node.m_Value.first;
394 typedef typename cds::opt::details::make_comparator< key_type, original_traits, false >::type key_comparator;
396 typedef cds::details::Allocator< leaf_node, typename original_traits::allocator> cxx_leaf_node_allocator;
397 struct leaf_deallocator
399 void operator()( leaf_node * p ) const
401 cxx_leaf_node_allocator().Delete( p );
405 struct intrusive_traits: public original_traits
407 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc > > hook;
408 typedef intrusive_key_extractor key_extractor;
409 typedef leaf_deallocator disposer;
410 typedef cds::details::compare_wrapper< leaf_node, key_comparator, key_accessor > compare;
413 // Metafunction result
414 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_traits > type;
417 } // namespace details
419 } // namespace ellen_bintree
421 // Forward declarations
423 template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
424 class EllenBinTreeSet;
426 template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
427 class EllenBinTreeMap;
430 }} // namespace cds::container
432 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H