3 #ifndef __CDS_CONTAINER_ELLEN_BINTREE_MAP_IMPL_H
4 #define __CDS_CONTAINER_ELLEN_BINTREE_MAP_IMPL_H
7 #include <cds/container/details/ellen_bintree_base.h>
8 #include <cds/intrusive/impl/ellen_bintree.h>
9 #include <cds/details/functor_wrapper.h>
10 #include <cds/container/details/guarded_ptr_cast.h>
12 namespace cds { namespace container {
14 /// Map based on Ellen's et al binary search tree
15 /** @ingroup cds_nonintrusive_map
16 @ingroup cds_nonintrusive_tree
17 @anchor cds_container_EllenBinTreeMap
20 - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
22 %EllenBinTreeMap is an unbalanced leaf-oriented binary search tree that implements the <i>map</i>
23 abstract data type. Nodes maintains child pointers but not parent pointers.
24 Every internal node has exactly two children, and all data of type <tt>std::pair<Key const, T></tt>
25 currently in the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find
26 operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
27 may or may not be in the map.
28 Unlike \ref cds_container_EllenBinTreeSet "EllenBinTreeSet" keys are not a part of \p T type.
29 The map can be represented as a set containing <tt>std::pair< Key const, T> </tt> values.
31 Due to \p extract_min and \p extract_max member functions the \p %EllenBinTreeMap can act as
32 a <i>priority queue</i>. In this case you should provide unique compound key, for example,
33 the priority value plus some uniformly distributed random value.
35 @warning Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
36 for uniformly distributed random keys, but in worst case the complexity is <tt>O(N)</tt>.
38 @note In the current implementation we do not use helping technique described in original paper.
39 So, the current implementation is near to fine-grained lock-based tree.
40 Helping will be implemented in future release
42 <b>Template arguments</b> :
43 - \p GC - safe memory reclamation (i.e. light-weight garbage collector) type, like cds::gc::HP, cds::gc::PTB
44 Note that cds::gc::HRC is not supported.
46 - \p T - value type to be stored in tree's leaf nodes.
47 - \p Traits - type traits. See ellen_bintree::type_traits for explanation.
49 It is possible to declare option-based tree with ellen_bintree::make_map_traits metafunction
50 instead of \p Traits template argument.
51 Template argument list \p Options of ellen_bintree::make_map_traits metafunction are:
52 - opt::compare - key compare functor. No default functor is provided.
53 If the option is not specified, \p %opt::less is used.
54 - opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
55 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
56 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
57 or opt::v::sequential_consistent (sequentially consisnent memory model).
58 - opt::allocator - the allocator used for \ref ellen_bintree::map_node "leaf nodes" which contains data.
59 Default is \ref CDS_DEFAULT_ALLOCATOR.
60 - opt::node_allocator - the allocator used for \ref ellen_bintree::internal_node "internal nodes".
61 Default is \ref CDS_DEFAULT_ALLOCATOR.
62 - ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
63 default is \ref CDS_DEFAULT_ALLOCATOR.
64 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
65 The number of simultaneously existing descriptors is a relatively small number limited the number of threads
66 working with the tree and GC buffer size.
67 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list
68 of update descriptors, see cds::memory::vyukov_queue_pool free-list implementation.
69 Also notice that size of update descriptor is not dependent on the type of data
70 stored in the tree so single free-list object can be used for several EllenBinTree-based object.
71 - opt::stat - internal statistics. Available types: ellen_bintree::stat, ellen_bintree::empty_stat (the default)
72 - opt::copy_policy - key copy policy defines a functor to copy leaf node's key to internal node.
73 By default, assignment operator is used.
74 The copy functor interface is:
77 void operator()( Key& dest, Key const& src );
81 @note Do not include <tt><cds/container/ellen_bintree_map_impl.h></tt> header file directly.
82 There are header file for each GC type:
83 - <tt><cds/container/ellen_bintree_map_hp.h></tt> - for Hazard Pointer GC cds::gc::HP
84 - <tt><cds/container/ellen_bintree_map_ptb.h></tt> - for Pass-the-Buck GC cds::gc::PTB
85 - <tt><cds/container/ellen_bintree_map_rcu.h></tt> - for RCU GC
86 (see \ref cds_container_EllenBinTreeMap_rcu "RCU-based EllenBinTreeMap")
92 #ifdef CDS_DOXYGEN_INVOKED
93 class Traits = ellen_bintree::type_traits
99 #ifdef CDS_DOXYGEN_INVOKED
100 : public cds::intrusive::EllenBinTree< GC, Key, T, Traits >
102 : public ellen_bintree::details::make_ellen_bintree_map< GC, Key, T, Traits >::type
106 typedef ellen_bintree::details::make_ellen_bintree_map< GC, Key, T, Traits > maker;
107 typedef typename maker::type base_class;
110 typedef GC gc ; ///< Garbage collector
111 typedef Key key_type ; ///< type of a key stored in the map
112 typedef T mapped_type ; ///< type of value stored in the map
113 typedef std::pair< key_type const, mapped_type > value_type ; ///< Key-value pair stored in leaf node of the mp
114 typedef Traits options ; ///< Traits template parameter
116 # ifdef CDS_DOXYGEN_INVOKED
117 typedef implementation_defined key_comparator ; ///< key compare functor based on opt::compare and opt::less option setter.
119 typedef typename maker::intrusive_type_traits::compare key_comparator;
121 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
122 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
123 typedef typename base_class::node_allocator node_allocator_type ; ///< allocator for maintaining internal node
124 typedef typename base_class::stat stat ; ///< internal statistics type
125 typedef typename options::copy_policy copy_policy ; ///< key copy policy
127 typedef typename options::allocator allocator_type ; ///< Allocator for leaf nodes
128 typedef typename base_class::node_allocator node_allocator ; ///< Internal node allocator
129 typedef typename base_class::update_desc_allocator update_desc_allocator ; ///< Update descriptor allocator
133 typedef typename base_class::value_type leaf_node;
134 typedef typename base_class::internal_node internal_node;
135 typedef typename base_class::update_desc update_desc;
137 typedef typename maker::cxx_leaf_node_allocator cxx_leaf_node_allocator;
139 typedef std::unique_ptr< leaf_node, typename maker::leaf_deallocator > scoped_node_ptr;
144 typedef cds::gc::guarded_ptr< gc, leaf_node, value_type, details::guarded_ptr_cast_set<leaf_node, value_type> > guarded_ptr;
147 /// Default constructor
151 //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" );
158 /// Inserts new node with key and default value
160 The function creates a node with \p key and default value, and then inserts the node created into the map.
163 - The \ref key_type should be constructible from a value of type \p K.
164 In trivial case, \p K is equal to \ref key_type.
165 - The \ref mapped_type should be default-constructible.
167 Returns \p true if inserting successful, \p false otherwise.
169 template <typename K>
170 bool insert( K const& key )
172 return insert_key( key, [](value_type&){} );
177 The function creates a node with copy of \p val value
178 and then inserts the node created into the map.
181 - The \ref key_type should be constructible from \p key of type \p K.
182 - The \ref value_type should be constructible from \p val of type \p V.
184 Returns \p true if \p val is inserted into the map, \p false otherwise.
186 template <typename K, typename V>
187 bool insert( K const& key, V const& val )
189 scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key, val ));
190 if ( base_class::insert( *pNode ))
198 /// Inserts new node and initialize it by a functor
200 This function inserts new node with key \p key and if inserting is successful then it calls
201 \p func functor with signature
204 void operator()( value_type& item );
208 The argument \p item of user-defined functor \p func is the reference
209 to the map's item inserted:
210 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
211 - <tt>item.second</tt> is a reference to item's value that may be changed.
213 The user-defined functor can be passed by reference using <tt>boost::ref</tt>
214 and it is called only if inserting is successful.
216 The key_type should be constructible from value of type \p K.
218 The function allows to split creating of new item into two part:
219 - create item from \p key;
220 - insert new item into the map;
221 - if inserting is successful, initialize the value of item by calling \p func functor
223 This can be useful if complete initialization of object of \p value_type is heavyweight and
224 it is preferable that the initialization should be completed only if inserting is successful.
226 template <typename K, typename Func>
227 bool insert_key( const K& key, Func func )
229 scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key ));
230 if ( base_class::insert( *pNode, [&func]( leaf_node& item ) { cds::unref(func)( item.m_Value ); } )) {
237 /// For key \p key inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
239 Returns \p true if inserting successful, \p false otherwise.
241 template <typename K, typename... Args>
242 bool emplace( K&& key, Args&&... args )
244 scoped_node_ptr pNode( cxx_leaf_node_allocator().New( std::forward<K>(key), std::forward<Args>(args)... ));
245 if ( base_class::insert( *pNode )) {
252 /// Ensures that the \p key exists in the map
254 The operation performs inserting or changing data with lock-free manner.
256 If the \p key not found in the map, then the new item created from \p key
257 is inserted into the map (note that in this case the \ref key_type should be
258 constructible from type \p K).
259 Otherwise, the functor \p func is called with item found.
260 The functor \p Func may be a function with signature:
262 void func( bool bNew, value_type& item );
267 void operator()( bool bNew, value_type& item );
272 - \p bNew - \p true if the item has been inserted, \p false otherwise
273 - \p item - item of the list
275 The functor may change any fields of the \p item.second that is \ref value_type.
277 You may pass \p func argument by reference using <tt>boost::ref</tt>.
279 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
280 \p second is true if new item has been added or \p false if the item with \p key
281 already is in the list.
283 template <typename K, typename Func>
284 std::pair<bool, bool> ensure( K const& key, Func func )
286 scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key ));
287 std::pair<bool, bool> res = base_class::ensure( *pNode,
288 [&func](bool bNew, leaf_node& item, leaf_node const& ){ cds::unref(func)( bNew, item.m_Value ); }
290 if ( res.first && res.second )
295 /// Delete \p key from the map
296 /**\anchor cds_nonintrusive_EllenBinTreeMap_erase_val
298 Return \p true if \p key is found and deleted, \p false otherwise
300 template <typename K>
301 bool erase( K const& key )
303 return base_class::erase(key);
306 /// Deletes the item from the map using \p pred predicate for searching
308 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_erase_val "erase(K const&)"
309 but \p pred is used for key comparing.
310 \p Less functor has the interface like \p std::less.
311 \p Less must imply the same element order as the comparator used for building the map.
313 template <typename K, typename Less>
314 bool erase_with( K const& key, Less pred )
316 return base_class::erase_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >());
319 /// Delete \p key from the map
320 /** \anchor cds_nonintrusive_EllenBinTreeMap_erase_func
322 The function searches an item with key \p key, calls \p f functor
323 and deletes the item. If \p key is not found, the functor is not called.
325 The functor \p Func interface:
328 void operator()(value_type& item) { ... }
331 The functor may be passed by reference using <tt>boost:ref</tt>
333 Return \p true if key is found and deleted, \p false otherwise
335 template <typename K, typename Func>
336 bool erase( K const& key, Func f )
338 return base_class::erase( key, [&f]( leaf_node& node) { cds::unref(f)( node.m_Value ); } );
341 /// Deletes the item from the map using \p pred predicate for searching
343 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_erase_func "erase(K const&, Func)"
344 but \p pred is used for key comparing.
345 \p Less functor has the interface like \p std::less.
346 \p Less must imply the same element order as the comparator used for building the map.
348 template <typename K, typename Less, typename Func>
349 bool erase_with( K const& key, Less pred, Func f )
351 return base_class::erase_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >(),
352 [&f]( leaf_node& node) { cds::unref(f)( node.m_Value ); } );
355 /// Extracts an item with minimal key from the map
357 If the map is not empty, the function returns \p true, \p result contains a pointer to minimum value.
358 If the map is empty, the function returns \p false, \p result is left unchanged.
360 @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
361 It means that the function gets leftmost leaf of the tree and tries to unlink it.
362 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
363 So, the function returns the item with minimum key at the moment of tree traversing.
365 The guarded pointer \p result prevents deallocation of returned item,
366 see cds::gc::guarded_ptr for explanation.
367 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
369 bool extract_min( guarded_ptr& result )
371 return base_class::extract_min_( result.guard() );
374 /// Extracts an item with maximal key from the map
376 If the map is not empty, the function returns \p true, \p result contains a pointer to maximal value.
377 If the map is empty, the function returns \p false, \p result is left unchanged.
379 @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
380 It means that the function gets rightmost leaf of the tree and tries to unlink it.
381 During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
382 So, the function returns the item with maximum key at the moment of tree traversing.
384 The guarded pointer \p result prevents deallocation of returned item,
385 see cds::gc::guarded_ptr for explanation.
386 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
388 bool extract_max( guarded_ptr& result )
390 return base_class::extract_max_( result.guard() );
393 /// Extracts an item from the tree
394 /** \anchor cds_nonintrusive_EllenBinTreeMap_extract
395 The function searches an item with key equal to \p key in the tree,
396 unlinks it, and returns pointer to an item found in \p result parameter.
397 If the item is not found the function returns \p false.
399 The guarded pointer \p result prevents deallocation of returned item,
400 see cds::gc::guarded_ptr for explanation.
401 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
403 template <typename Q>
404 bool extract( guarded_ptr& result, Q const& key )
406 return base_class::extract_( result.guard(), key );
409 /// Extracts an item from the map using \p pred for searching
411 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_extract "extract(guarded_ptr&, Q const&)"
412 but \p pred is used for key compare.
413 \p Less has the interface like \p std::less.
414 \p pred must imply the same element order as the comparator used for building the map.
416 template <typename Q, typename Less>
417 bool extract_with( guarded_ptr& result, Q const& key, Less pred )
419 return base_class::extract_with_( result.guard(), key,
420 cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >());
423 /// Find the key \p key
424 /** \anchor cds_nonintrusive_EllenBinTreeMap_find_cfunc
426 The function searches the item with key equal to \p key and calls the functor \p f for item found.
427 The interface of \p Func functor is:
430 void operator()( value_type& item );
433 where \p item is the item found.
435 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
437 The functor may change \p item.second.
439 The function returns \p true if \p key is found, \p false otherwise.
441 template <typename K, typename Func>
442 bool find( K const& key, Func f )
444 return base_class::find( key, [&f](leaf_node& item, K const& ) { cds::unref(f)( item.m_Value );});
447 /// Finds the key \p val using \p pred predicate for searching
449 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_find_cfunc "find(K const&, Func)"
450 but \p pred is used for key comparing.
451 \p Less functor has the interface like \p std::less.
452 \p Less must imply the same element order as the comparator used for building the map.
454 template <typename K, typename Less, typename Func>
455 bool find_with( K const& key, Less pred, Func f )
457 return base_class::find_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >(),
458 [&f](leaf_node& item, K const& ) { cds::unref(f)( item.m_Value );});
461 /// Find the key \p key
462 /** \anchor cds_nonintrusive_EllenBinTreeMap_find_val
464 The function searches the item with key equal to \p key
465 and returns \p true if it is found, and \p false otherwise.
467 template <typename K>
468 bool find( K const& key )
470 return base_class::find( key );
473 /// Finds the key \p val using \p pred predicate for searching
475 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_find_val "find(K const&)"
476 but \p pred is used for key comparing.
477 \p Less functor has the interface like \p std::less.
478 \p Less must imply the same element order as the comparator used for building the map.
480 template <typename K, typename Less>
481 bool find_with( K const& key, Less pred )
483 return base_class::find_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >() );
486 /// Finds \p key and returns the item found
487 /** @anchor cds_nonintrusive_EllenBinTreeMap_get
488 The function searches the item with key equal to \p key and returns the item found in \p result parameter.
489 The function returns \p true if \p key is found, \p false otherwise.
491 The guarded pointer \p result prevents deallocation of returned item,
492 see cds::gc::guarded_ptr for explanation.
493 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
495 template <typename Q>
496 bool get( guarded_ptr& result, Q const& key )
498 return base_class::get_( result.guard(), key );
501 /// Finds \p key with predicate \p pred and returns the item found
503 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_get "get(guarded_ptr&, Q const&)"
504 but \p pred is used for key comparing.
505 \p Less functor has the interface like \p std::less.
506 \p pred must imply the same element order as the comparator used for building the map.
508 template <typename Q, typename Less>
509 bool get_with( guarded_ptr& result, Q const& key, Less pred )
511 return base_class::get_with_( result.guard(), key,
512 cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >() );
521 /// Checks if the map is empty
523 Emptiness is checked by item counting: if item count is zero then the map is empty.
527 return base_class::empty();
530 /// Returns item count in the map
533 return base_class::size();
536 /// Returns const reference to internal statistics
537 stat const& statistics() const
539 return base_class::statistics();
542 /// Checks internal consistency (not atomic, not thread-safe)
544 The debugging function to check internal consistency of the tree.
546 bool check_consistency() const
548 return base_class::check_consistency();
552 }} // namespace cds::container
554 #endif //#ifndef __CDS_CONTAINER_ELLEN_BINTREE_MAP_IMPL_H