3 #ifndef __CDS_CONTAINER_ELLEN_BINTREE_BASE_H
4 #define __CDS_CONTAINER_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 cds::intrusive::ellen_bintree::update_desc
20 typedef cds::intrusive::ellen_bintree::update_desc update_desc;
22 /// Typedef for cds::intrusive::ellen_bintree::internal_node
23 typedef cds::intrusive::ellen_bintree::internal_node internal_node;
25 /// Typedef for cds::intrusive::ellen_bintree::key_extractor
26 typedef cds::intrusive::ellen_bintree::key_extractor key_extractor;
28 /// Typedef for cds::intrusive::ellen_bintree::update_desc_allocator
29 typedef cds::intrusive::ellen_bintree::update_desc_allocator update_desc_allocator;
31 /// Typedef for cds::intrusive::ellen_bintree::stat
32 typedef cds::intrusive::ellen_bintree::stat stat;
34 /// Typedef for cds::intrusive::ellen_bintree::empty_stat
35 typedef cds::intrusive::ellen_bintree::empty_stat empty_stat;
37 using cds::intrusive::ellen_bintree::update_desc;
38 using cds::intrusive::ellen_bintree::internal_node;
39 using cds::intrusive::ellen_bintree::key_extractor;
40 using cds::intrusive::ellen_bintree::update_desc_allocator;
41 using cds::intrusive::ellen_bintree::stat;
42 using cds::intrusive::ellen_bintree::empty_stat;
43 using cds::intrusive::ellen_bintree::node_types;
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, EllenBinTreeMap and EllenBinTreePriorityQueue
103 /// Key extracting functor (only for 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.
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 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 cds::opt::less option description for predicate interface.
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 counting feature (see cds::opt::item_counter).
140 Default is no item counter (\ref atomicity::empty_item_counter)
142 typedef atomicity::empty_item_counter item_counter;
144 /// C++ memory ordering model
146 List of available memory ordering see opt::memory_model
148 typedef opt::v::relaxed_ordering memory_model;
150 /// Allocator for update descriptors
152 The allocator type is used for \ref 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 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 \ref 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 Possible types: ellen_bintree::empty_stat (the default), ellen_bintree::stat or any
181 other with interface like \p %stat.
183 typedef empty_stat stat;
185 /// RCU deadlock checking policy (only for RCU-based EllenBinTree<i>XXX</i> classes)
187 List of available options see opt::rcu_check_deadlock
189 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
191 /// Key copy policy (for 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 EllenBinTreeMap. By default, assignment operator is used.
196 The copy functor interface is:
198 struct copy_functor {
199 void operator()( Key& dest, Key const& src );
203 typedef opt::none copy_policy;
207 /// Metafunction converting option list to EllenBinTreeSet traits
209 This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
210 \p Options list see \ref cds_container_EllenBinTreeSet "EllenBinTreeSet".
212 template <typename... Options>
213 struct make_set_traits {
214 # ifdef CDS_DOXYGEN_INVOKED
215 typedef implementation_defined type ; ///< Metafunction result
217 typedef typename cds::opt::make_options<
218 typename cds::opt::find_type_traits< type_traits, Options... >::type
224 /// Metafunction converting option list to EllenBinTreeMap traits
226 This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
227 \p Options list see \ref cds_container_EllenBinTreeMap "EllenBinTreeMap".
229 template <typename... Options>
230 struct make_map_traits {
231 # ifdef CDS_DOXYGEN_INVOKED
232 typedef implementation_defined type ; ///< Metafunction result
234 typedef typename cds::opt::make_options<
235 typename cds::opt::find_type_traits< type_traits, Options... >::type
244 template < class GC, typename Key, typename T, class Traits>
245 struct make_ellen_bintree_set
248 typedef Key key_type;
249 typedef T value_type;
250 typedef Traits original_type_traits;
252 typedef node< gc, value_type > leaf_node;
254 struct intrusive_key_extractor
256 void operator()( key_type& dest, leaf_node const& src ) const
258 typename original_type_traits::key_extractor()( dest, src.m_Value );
262 struct value_accessor
264 value_type const& operator()( leaf_node const& node ) const
270 typedef typename cds::opt::details::make_comparator< value_type, original_type_traits, false >::type key_comparator;
272 typedef cds::details::Allocator< leaf_node, typename original_type_traits::allocator> cxx_leaf_node_allocator;
273 struct leaf_deallocator
275 void operator()( leaf_node * p ) const
277 cxx_leaf_node_allocator().Delete( p );
281 struct intrusive_type_traits: public original_type_traits
283 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc > > hook;
284 typedef intrusive_key_extractor key_extractor;
285 typedef leaf_deallocator disposer;
286 typedef cds::details::compare_wrapper< leaf_node, key_comparator, value_accessor > compare;
289 // Metafunction result
290 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_type_traits > type;
293 template < class GC, typename Key, typename T, class Traits>
294 struct make_ellen_bintree_map
297 typedef Key key_type;
298 typedef T mapped_type;
299 typedef map_node< gc, key_type, mapped_type > leaf_node;
300 typedef typename leaf_node::value_type value_type;
302 typedef Traits original_type_traits;
304 struct assignment_copy_policy {
305 void operator()( key_type& dest, key_type const& src )
310 typedef typename std::conditional<
311 std::is_same< typename original_type_traits::copy_policy, opt::none >::value,
312 assignment_copy_policy,
313 typename original_type_traits::copy_policy
316 struct intrusive_key_extractor
318 void operator()( key_type& dest, leaf_node const& src ) const
320 copy_policy()( dest, src.m_Value.first );
326 key_type const& operator()( leaf_node const& node ) const
328 return node.m_Value.first;
332 typedef typename cds::opt::details::make_comparator< key_type, original_type_traits, false >::type key_comparator;
334 typedef cds::details::Allocator< leaf_node, typename original_type_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_type_traits: public original_type_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, key_accessor > compare;
351 // Metafunction result
352 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_type_traits > type;
355 } // namespace details
357 } // namespace ellen_bintree
359 // Forward declarations
361 template < class GC, typename Key, typename T, class Traits = ellen_bintree::type_traits >
362 class EllenBinTreeSet;
364 template < class GC, typename Key, typename T, class Traits = ellen_bintree::type_traits >
365 class EllenBinTreeMap;
368 }} // namespace cds::container
370 #endif // #ifndef __CDS_CONTAINER_ELLEN_BINTREE_BASE_H