3 #ifndef __CDS_CONTAINER_IMPL_ELLEN_BINTREE_MAP_H
4 #define __CDS_CONTAINER_IMPL_ELLEN_BINTREE_MAP_H
7 #include <cds/container/details/ellen_bintree_base.h>
8 #include <cds/intrusive/impl/ellen_bintree.h>
9 #include <cds/container/details/guarded_ptr_cast.h>
11 namespace cds { namespace container {
13 /// Map based on Ellen's et al binary search tree
14 /** @ingroup cds_nonintrusive_map
15 @ingroup cds_nonintrusive_tree
16 @anchor cds_container_EllenBinTreeMap
19 - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
21 %EllenBinTreeMap is an unbalanced leaf-oriented binary search tree that implements the <i>map</i>
22 abstract data type. Nodes maintains child pointers but not parent pointers.
23 Every internal node has exactly two children, and all data of type <tt>std::pair<Key const, T></tt>
24 currently in the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find
25 operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
26 may or may not be in the map.
27 Unlike \ref cds_container_EllenBinTreeSet "EllenBinTreeSet" keys are not a part of \p T type.
28 The map can be represented as a set containing <tt>std::pair< Key const, T> </tt> values.
30 Due to \p extract_min and \p extract_max member functions the \p %EllenBinTreeMap can act as
31 a <i>priority queue</i>. In this case you should provide unique compound key, for example,
32 the priority value plus some uniformly distributed random value.
34 @warning Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
35 for uniformly distributed random keys, but in worst case the complexity is <tt>O(N)</tt>.
37 @note In the current implementation we do not use helping technique described in original paper.
38 So, the current implementation is near to fine-grained lock-based tree.
39 Helping will be implemented in future release
41 <b>Template arguments</b> :
42 - \p GC - safe memory reclamation (i.e. light-weight garbage collector) type, like cds::gc::HP, cds::gc::PTB
43 Note that cds::gc::HRC is not supported.
45 - \p T - value type to be stored in tree's leaf nodes.
46 - \p Traits - type traits. See ellen_bintree::type_traits for explanation.
48 It is possible to declare option-based tree with ellen_bintree::make_map_traits metafunction
49 instead of \p Traits template argument.
50 Template argument list \p Options of ellen_bintree::make_map_traits metafunction are:
51 - opt::compare - key compare functor. No default functor is provided.
52 If the option is not specified, \p %opt::less is used.
53 - opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
54 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
55 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
56 or opt::v::sequential_consistent (sequentially consisnent memory model).
57 - opt::allocator - the allocator used for \ref ellen_bintree::map_node "leaf nodes" which contains data.
58 Default is \ref CDS_DEFAULT_ALLOCATOR.
59 - opt::node_allocator - the allocator used for \ref ellen_bintree::internal_node "internal nodes".
60 Default is \ref CDS_DEFAULT_ALLOCATOR.
61 - ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
62 default is \ref CDS_DEFAULT_ALLOCATOR.
63 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
64 The number of simultaneously existing descriptors is a relatively small number limited the number of threads
65 working with the tree and GC buffer size.
66 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list
67 of update descriptors, see cds::memory::vyukov_queue_pool free-list implementation.
68 Also notice that size of update descriptor is not dependent on the type of data
69 stored in the tree so single free-list object can be used for several EllenBinTree-based object.
70 - opt::stat - internal statistics. Available types: ellen_bintree::stat, ellen_bintree::empty_stat (the default)
71 - opt::copy_policy - key copy policy defines a functor to copy leaf node's key to internal node.
72 By default, assignment operator is used.
73 The copy functor interface is:
76 void operator()( Key& dest, Key const& src );
80 @note Do not include <tt><cds/container/impl/ellen_bintree_map.h></tt> header file directly.
81 There are header file for each GC type:
82 - <tt><cds/container/ellen_bintree_map_hp.h></tt> - for Hazard Pointer GC cds::gc::HP
83 - <tt><cds/container/ellen_bintree_map_ptb.h></tt> - for Pass-the-Buck GC cds::gc::PTB
84 - <tt><cds/container/ellen_bintree_map_rcu.h></tt> - for RCU GC
85 (see \ref cds_container_EllenBinTreeMap_rcu "RCU-based EllenBinTreeMap")
91 #ifdef CDS_DOXYGEN_INVOKED
92 class Traits = ellen_bintree::type_traits
98 #ifdef CDS_DOXYGEN_INVOKED
99 : public cds::intrusive::EllenBinTree< GC, Key, T, Traits >
101 : public ellen_bintree::details::make_ellen_bintree_map< GC, Key, T, Traits >::type
105 typedef ellen_bintree::details::make_ellen_bintree_map< GC, Key, T, Traits > maker;
106 typedef typename maker::type base_class;
109 typedef GC gc ; ///< Garbage collector
110 typedef Key key_type ; ///< type of a key stored in the map
111 typedef T mapped_type ; ///< type of value stored in the map
112 typedef std::pair< key_type const, mapped_type > value_type ; ///< Key-value pair stored in leaf node of the mp
113 typedef Traits options ; ///< Traits template parameter
115 # ifdef CDS_DOXYGEN_INVOKED
116 typedef implementation_defined key_comparator ; ///< key compare functor based on opt::compare and opt::less option setter.
118 typedef typename maker::intrusive_type_traits::compare key_comparator;
120 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
121 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
122 typedef typename base_class::node_allocator node_allocator_type ; ///< allocator for maintaining internal node
123 typedef typename base_class::stat stat ; ///< internal statistics type
124 typedef typename options::copy_policy copy_policy ; ///< key copy policy
126 typedef typename options::allocator allocator_type ; ///< Allocator for leaf nodes
127 typedef typename base_class::node_allocator node_allocator ; ///< Internal node allocator
128 typedef typename base_class::update_desc_allocator update_desc_allocator ; ///< Update descriptor allocator
132 typedef typename base_class::value_type leaf_node;
133 typedef typename base_class::internal_node internal_node;
134 typedef typename base_class::update_desc update_desc;
136 typedef typename maker::cxx_leaf_node_allocator cxx_leaf_node_allocator;
138 typedef std::unique_ptr< leaf_node, typename maker::leaf_deallocator > scoped_node_ptr;
143 typedef cds::gc::guarded_ptr< gc, leaf_node, value_type, details::guarded_ptr_cast_set<leaf_node, value_type> > guarded_ptr;
146 /// Default constructor
150 //static_assert( (std::is_same<gc, cds::gc::HP>::value || std::is_same<gc, cds::gc::PTB>::value), "GC must be cds::gc::HP or cds:gc::PTB" );
157 /// Inserts new node with key and default value
159 The function creates a node with \p key and default value, and then inserts the node created into the map.
162 - The \ref key_type should be constructible from a value of type \p K.
163 In trivial case, \p K is equal to \ref key_type.
164 - The \ref mapped_type should be default-constructible.
166 Returns \p true if inserting successful, \p false otherwise.
168 template <typename K>
169 bool insert( K const& key )
171 return insert_key( key, [](value_type&){} );
176 The function creates a node with copy of \p val value
177 and then inserts the node created into the map.
180 - The \ref key_type should be constructible from \p key of type \p K.
181 - The \ref value_type should be constructible from \p val of type \p V.
183 Returns \p true if \p val is inserted into the map, \p false otherwise.
185 template <typename K, typename V>
186 bool insert( K const& key, V const& val )
188 scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key, val ));
189 if ( base_class::insert( *pNode ))
197 /// Inserts new node and initialize it by a functor
199 This function inserts new node with key \p key and if inserting is successful then it calls
200 \p func functor with signature
203 void operator()( value_type& item );
207 The argument \p item of user-defined functor \p func is the reference
208 to the map's item inserted:
209 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
210 - <tt>item.second</tt> is a reference to item's value that may be changed.
212 The user-defined functor can be passed by reference using \p std::ref
213 and it is called only if inserting is successful.
215 The key_type should be constructible from value of type \p K.
217 The function allows to split creating of new item into two part:
218 - create item from \p key;
219 - insert new item into the map;
220 - if inserting is successful, initialize the value of item by calling \p func functor
222 This can be useful if complete initialization of object of \p value_type is heavyweight and
223 it is preferable that the initialization should be completed only if inserting is successful.
225 template <typename K, typename Func>
226 bool insert_key( const K& key, Func func )
228 scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key ));
229 if ( base_class::insert( *pNode, [&func]( leaf_node& item ) { func( item.m_Value ); } )) {
236 /// For key \p key inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
238 Returns \p true if inserting successful, \p false otherwise.
240 template <typename K, typename... Args>
241 bool emplace( K&& key, Args&&... args )
243 scoped_node_ptr pNode( cxx_leaf_node_allocator().New( std::forward<K>(key), std::forward<Args>(args)... ));
244 if ( base_class::insert( *pNode )) {
251 /// Ensures that the \p key exists in the map
253 The operation performs inserting or changing data with lock-free manner.
255 If the \p key not found in the map, then the new item created from \p key
256 is inserted into the map (note that in this case the \ref key_type should be
257 constructible from type \p K).
258 Otherwise, the functor \p func is called with item found.
259 The functor \p Func may be a function with signature:
261 void func( bool bNew, value_type& item );
266 void operator()( bool bNew, value_type& item );
271 - \p bNew - \p true if the item has been inserted, \p false otherwise
272 - \p item - item of the list
274 The functor may change any fields of the \p item.second that is \ref value_type.
276 You may pass \p func argument by reference using \p std::ref.
278 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
279 \p second is true if new item has been added or \p false if the item with \p key
280 already is in the list.
282 template <typename K, typename Func>
283 std::pair<bool, bool> ensure( K const& key, Func func )
285 scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key ));
286 std::pair<bool, bool> res = base_class::ensure( *pNode,
287 [&func](bool bNew, leaf_node& item, leaf_node const& ){ func( bNew, item.m_Value ); }
289 if ( res.first && res.second )
294 /// Delete \p key from the map
295 /**\anchor cds_nonintrusive_EllenBinTreeMap_erase_val
297 Return \p true if \p key is found and deleted, \p false otherwise
299 template <typename K>
300 bool erase( K const& key )
302 return base_class::erase(key);
305 /// Deletes the item from the map using \p pred predicate for searching
307 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_erase_val "erase(K const&)"
308 but \p pred is used for key comparing.
309 \p Less functor has the interface like \p std::less.
310 \p Less must imply the same element order as the comparator used for building the map.
312 template <typename K, typename Less>
313 bool erase_with( K const& key, Less pred )
315 return base_class::erase_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >());
318 /// Delete \p key from the map
319 /** \anchor cds_nonintrusive_EllenBinTreeMap_erase_func
321 The function searches an item with key \p key, calls \p f functor
322 and deletes the item. If \p key is not found, the functor is not called.
324 The functor \p Func interface:
327 void operator()(value_type& item) { ... }
330 The functor may be passed by reference using <tt>boost:ref</tt>
332 Return \p true if key is found and deleted, \p false otherwise
334 template <typename K, typename Func>
335 bool erase( K const& key, Func f )
337 return base_class::erase( key, [&f]( leaf_node& node) { f( node.m_Value ); } );
340 /// Deletes the item from the map using \p pred predicate for searching
342 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_erase_func "erase(K const&, Func)"
343 but \p pred is used for key comparing.
344 \p Less functor has the interface like \p std::less.
345 \p Less must imply the same element order as the comparator used for building the map.
347 template <typename K, typename Less, typename Func>
348 bool erase_with( K const& key, Less pred, Func f )
350 return base_class::erase_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >(),
351 [&f]( leaf_node& node) { f( node.m_Value ); } );
354 /// Extracts an item with minimal key from the map
356 If the map is not empty, the function returns \p true, \p result contains a pointer to minimum value.
357 If the map is empty, the function returns \p false, \p result is left unchanged.
359 @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
360 It means that the function gets leftmost leaf of the tree and tries to unlink it.
361 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
362 So, the function returns the item with minimum key at the moment of tree traversing.
364 The guarded pointer \p result prevents deallocation of returned item,
365 see cds::gc::guarded_ptr for explanation.
366 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
368 bool extract_min( guarded_ptr& result )
370 return base_class::extract_min_( result.guard() );
373 /// Extracts an item with maximal key from the map
375 If the map is not empty, the function returns \p true, \p result contains a pointer to maximal value.
376 If the map is empty, the function returns \p false, \p result is left unchanged.
378 @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
379 It means that the function gets rightmost leaf of the tree and tries to unlink it.
380 During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
381 So, the function returns the item with maximum key at the moment of tree traversing.
383 The guarded pointer \p result prevents deallocation of returned item,
384 see cds::gc::guarded_ptr for explanation.
385 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
387 bool extract_max( guarded_ptr& result )
389 return base_class::extract_max_( result.guard() );
392 /// Extracts an item from the tree
393 /** \anchor cds_nonintrusive_EllenBinTreeMap_extract
394 The function searches an item with key equal to \p key in the tree,
395 unlinks it, and returns pointer to an item found in \p result parameter.
396 If the item is not found the function returns \p false.
398 The guarded pointer \p result prevents deallocation of returned item,
399 see cds::gc::guarded_ptr for explanation.
400 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
402 template <typename Q>
403 bool extract( guarded_ptr& result, Q const& key )
405 return base_class::extract_( result.guard(), key );
408 /// Extracts an item from the map using \p pred for searching
410 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_extract "extract(guarded_ptr&, Q const&)"
411 but \p pred is used for key compare.
412 \p Less has the interface like \p std::less.
413 \p pred must imply the same element order as the comparator used for building the map.
415 template <typename Q, typename Less>
416 bool extract_with( guarded_ptr& result, Q const& key, Less pred )
418 return base_class::extract_with_( result.guard(), key,
419 cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >());
422 /// Find the key \p key
423 /** \anchor cds_nonintrusive_EllenBinTreeMap_find_cfunc
425 The function searches the item with key equal to \p key and calls the functor \p f for item found.
426 The interface of \p Func functor is:
429 void operator()( value_type& item );
432 where \p item is the item found.
434 You can pass \p f argument by reference using std::ref.
436 The functor may change \p item.second.
438 The function returns \p true if \p key is found, \p false otherwise.
440 template <typename K, typename Func>
441 bool find( K const& key, Func f )
443 return base_class::find( key, [&f](leaf_node& item, K const& ) { f( item.m_Value );});
446 /// Finds the key \p val using \p pred predicate for searching
448 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_find_cfunc "find(K const&, Func)"
449 but \p pred is used for key comparing.
450 \p Less functor has the interface like \p std::less.
451 \p Less must imply the same element order as the comparator used for building the map.
453 template <typename K, typename Less, typename Func>
454 bool find_with( K const& key, Less pred, Func f )
456 return base_class::find_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >(),
457 [&f](leaf_node& item, K const& ) { f( item.m_Value );});
460 /// Find the key \p key
461 /** \anchor cds_nonintrusive_EllenBinTreeMap_find_val
463 The function searches the item with key equal to \p key
464 and returns \p true if it is found, and \p false otherwise.
466 template <typename K>
467 bool find( K const& key )
469 return base_class::find( key );
472 /// Finds the key \p val using \p pred predicate for searching
474 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_find_val "find(K const&)"
475 but \p pred is used for key comparing.
476 \p Less functor has the interface like \p std::less.
477 \p Less must imply the same element order as the comparator used for building the map.
479 template <typename K, typename Less>
480 bool find_with( K const& key, Less pred )
482 return base_class::find_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >() );
485 /// Finds \p key and returns the item found
486 /** @anchor cds_nonintrusive_EllenBinTreeMap_get
487 The function searches the item with key equal to \p key and returns the item found in \p result parameter.
488 The function returns \p true if \p key is found, \p false otherwise.
490 The guarded pointer \p result prevents deallocation of returned item,
491 see cds::gc::guarded_ptr for explanation.
492 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
494 template <typename Q>
495 bool get( guarded_ptr& result, Q const& key )
497 return base_class::get_( result.guard(), key );
500 /// Finds \p key with predicate \p pred and returns the item found
502 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_get "get(guarded_ptr&, Q const&)"
503 but \p pred is used for key comparing.
504 \p Less functor has the interface like \p std::less.
505 \p pred must imply the same element order as the comparator used for building the map.
507 template <typename Q, typename Less>
508 bool get_with( guarded_ptr& result, Q const& key, Less pred )
510 return base_class::get_with_( result.guard(), key,
511 cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >() );
520 /// Checks if the map is empty
522 Emptiness is checked by item counting: if item count is zero then the map is empty.
526 return base_class::empty();
529 /// Returns item count in the map
532 return base_class::size();
535 /// Returns const reference to internal statistics
536 stat const& statistics() const
538 return base_class::statistics();
541 /// Checks internal consistency (not atomic, not thread-safe)
543 The debugging function to check internal consistency of the tree.
545 bool check_consistency() const
547 return base_class::check_consistency();
551 }} // namespace cds::container
553 #endif //#ifndef __CDS_CONTAINER_IMPL_ELLEN_BINTREE_MAP_H