2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_CONTAINER_ELLEN_BINTREE_MAP_RCU_H
32 #define CDSLIB_CONTAINER_ELLEN_BINTREE_MAP_RCU_H
34 #include <cds/container/details/ellen_bintree_base.h>
35 #include <cds/intrusive/ellen_bintree_rcu.h>
37 namespace cds { namespace container {
39 /// Map based on Ellen's et al binary search tree (RCU specialization)
40 /** @ingroup cds_nonintrusive_map
41 @ingroup cds_nonintrusive_tree
42 @anchor cds_container_EllenBinTreeMap_rcu
45 - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
47 %EllenBinTreeMap is an unbalanced leaf-oriented binary search tree that implements the <i>map</i>
48 abstract data type. Nodes maintains child pointers but not parent pointers.
49 Every internal node has exactly two children, and all data of type <tt>std::pair<Key const, T></tt>
50 currently in the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find
51 operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
52 may or may not be in the map.
53 Unlike \ref cds_container_EllenBinTreeSet_rcu "EllenBinTreeSet" keys are not a part of \p T type.
54 The map can be represented as a set containing <tt>std::pair< Key const, T> </tt> values.
56 Due to \p extract_min and \p extract_max member functions the \p %EllenBinTreeMap can act as
57 a <i>priority queue</i>. In this case you should provide unique compound key, for example,
58 the priority value plus some uniformly distributed random value.
60 @warning Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
61 for uniformly distributed random keys, but in the worst case the complexity is <tt>O(N)</tt>.
63 @note In the current implementation we do not use helping technique described in original paper.
64 So, the current implementation is near to fine-grained lock-based tree.
65 Helping will be implemented in future release
67 <b>Template arguments</b> :
68 - \p RCU - one of \ref cds_urcu_gc "RCU type"
70 - \p T - value type to be stored in tree's leaf nodes.
71 - \p Traits - map traits, default is \p ellen_bintree::traits.
72 It is possible to declare option-based tree with \p ellen_bintree::make_map_traits metafunction
73 instead of \p Traits template argument.
75 @note Before including <tt><cds/container/ellen_bintree_map_rcu.h></tt> you should include appropriate RCU header file,
76 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
82 #ifdef CDS_DOXYGEN_INVOKED
83 class Traits = ellen_bintree::traits
88 class EllenBinTreeMap< cds::urcu::gc<RCU>, Key, T, Traits >
89 #ifdef CDS_DOXYGEN_INVOKED
90 : public cds::intrusive::EllenBinTree< cds::urcu::gc<RCU>, Key, T, Traits >
92 : public ellen_bintree::details::make_ellen_bintree_map< cds::urcu::gc<RCU>, Key, T, Traits >::type
96 typedef ellen_bintree::details::make_ellen_bintree_map< cds::urcu::gc<RCU>, Key, T, Traits > maker;
97 typedef typename maker::type base_class;
100 typedef cds::urcu::gc<RCU> gc; ///< RCU Garbage collector
101 typedef Key key_type; ///< type of a key stored in the map
102 typedef T mapped_type; ///< type of value stored in the map
103 typedef std::pair< key_type const, mapped_type > value_type; ///< Key-value pair stored in leaf node of the mp
104 typedef Traits traits; ///< Traits template parameter
106 static_assert( std::is_default_constructible<key_type>::value, "Key should be default constructible type" );
108 # ifdef CDS_DOXYGEN_INVOKED
109 typedef implementation_defined key_comparator ; ///< key compare functor based on \p Traits::compare and \p Traits::less
111 typedef typename maker::intrusive_traits::compare key_comparator;
113 typedef typename base_class::item_counter item_counter; ///< Item counting policy
114 typedef typename base_class::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model option
115 typedef typename base_class::node_allocator node_allocator_type; ///< allocator for maintaining internal node
116 typedef typename base_class::stat stat; ///< internal statistics
117 typedef typename base_class::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
118 typedef typename traits::copy_policy copy_policy; ///< key copy policy
119 typedef typename traits::back_off back_off; ///< Back-off strategy
121 typedef typename traits::allocator allocator_type; ///< Allocator for leaf nodes
122 typedef typename base_class::node_allocator node_allocator; ///< Internal node allocator
123 typedef typename base_class::update_desc_allocator update_desc_allocator; ///< Update descriptor allocator
125 static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions do not require external locking
129 typedef typename base_class::value_type leaf_node;
130 typedef typename base_class::internal_node internal_node;
131 typedef typename base_class::update_desc update_desc;
133 typedef typename maker::cxx_leaf_node_allocator cxx_leaf_node_allocator;
135 typedef std::unique_ptr< leaf_node, typename maker::leaf_deallocator > scoped_node_ptr;
139 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
141 /// pointer to extracted node
142 using exempt_ptr = cds::urcu::exempt_ptr < gc, leaf_node, value_type, typename maker::intrusive_traits::disposer,
143 cds::urcu::details::conventional_exempt_member_cast < leaf_node, value_type >
147 /// Default constructor
156 /// Inserts new node with key and default value
158 The function creates a node with \p key and default value, and then inserts the node created into the map.
161 - The \p key_type should be constructible from a value of type \p K.
162 - The \p mapped_type should be default-constructible.
164 RCU \p synchronize() can be called. RCU should not be locked.
166 Returns \p true if inserting successful, \p false otherwise.
168 template <typename K>
169 bool insert( K const& key )
171 return insert_with( 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 \p key_type should be constructible from \p key of type \p K.
181 - The \p value_type should be constructible from \p val of type \p V.
183 RCU \p synchronize() method can be called. RCU should not be locked.
185 Returns \p true if \p val is inserted into the map, \p false otherwise.
187 template <typename K, typename V>
188 bool insert( K const& key, V const& val )
190 scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key, val ));
191 if ( base_class::insert( *pNode ))
199 /// Inserts new node and initialize it by a functor
201 This function inserts new node with key \p key and if inserting is successful then it calls
202 \p func functor with signature
205 void operator()( value_type& item );
209 The argument \p item of user-defined functor \p func is the reference
210 to the map's item inserted:
211 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
212 - <tt>item.second</tt> is a reference to item's value that may be changed.
214 The key_type should be constructible from value of type \p K.
216 The function allows to split creating of new item into two part:
217 - create item from \p key;
218 - insert new item into the map;
219 - if inserting is successful, initialize the value of item by calling \p func functor
221 This can be useful if complete initialization of object of \p value_type is heavyweight and
222 it is preferable that the initialization should be completed only if inserting is successful.
224 RCU \p synchronize() method can be called. RCU should not be locked.
226 template <typename K, typename Func>
227 bool insert_with( K const& key, Func func )
229 scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key ));
230 if ( base_class::insert( *pNode, [&func]( leaf_node& item ) { func( item.m_Value ); } )) {
237 /// For key \p key inserts data of type \p value_type created in-place from \p args
239 Returns \p true if inserting successful, \p false otherwise.
241 RCU \p synchronize() method can be called. RCU should not be locked.
243 template <typename K, typename... Args>
244 bool emplace( K&& key, Args&&... args )
246 scoped_node_ptr pNode( cxx_leaf_node_allocator().MoveNew( key_type( std::forward<K>(key)), mapped_type( std::forward<Args>(args)... )));
247 if ( base_class::insert( *pNode )) {
256 The operation performs inserting or changing data with lock-free manner.
258 If the item \p val is not found in the map, then \p val is inserted iff \p bAllowInsert is \p true.
259 Otherwise, the functor \p func is called with item found.
260 The functor \p func signature is:
263 void operator()( bool bNew, value_type& item );
268 - \p bNew - \p true if the item has been inserted, \p false otherwise
269 - \p item - item of the map
271 The functor may change any fields of the \p item.second that is \p mapped_type;
272 however, \p func must guarantee that during changing no any other modifications
273 could be made on this item by concurrent threads.
275 RCU \p synchronize() method can be called. RCU should not be locked.
277 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
278 i.e. the node has been inserted or updated,
279 \p second is \p true if new item has been added or \p false if the item with \p key
282 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
284 template <typename K, typename Func>
285 std::pair<bool, bool> update( K const& key, Func func, bool bAllowInsert = true )
287 scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key ));
288 std::pair<bool, bool> res = base_class::update( *pNode,
289 [&func](bool bNew, leaf_node& item, leaf_node const& ){ func( bNew, item.m_Value ); },
292 if ( res.first && res.second )
297 template <typename K, typename Func>
298 CDS_DEPRECATED("ensure() is deprecated, use update()")
299 std::pair<bool, bool> ensure( K const& key, Func func )
301 return update( key, func, true );
305 /// Delete \p key from the map
306 /**\anchor cds_nonintrusive_EllenBinTreeMap_rcu_erase_val
308 RCU \p synchronize() method can be called. RCU should not be locked.
310 Return \p true if \p key is found and deleted, \p false otherwise
312 template <typename K>
313 bool erase( K const& key )
315 return base_class::erase(key);
318 /// Deletes the item from the map using \p pred predicate for searching
320 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_erase_val "erase(K const&)"
321 but \p pred is used for key comparing.
322 \p Less functor has the interface like \p std::less.
323 \p Less must imply the same element order as the comparator used for building the map.
325 template <typename K, typename Less>
326 bool erase_with( K const& key, Less pred )
329 return base_class::erase_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >());
332 /// Delete \p key from the map
333 /** \anchor cds_nonintrusive_EllenBinTreeMap_rcu_erase_func
335 The function searches an item with key \p key, calls \p f functor
336 and deletes the item. If \p key is not found, the functor is not called.
338 The functor \p Func interface:
341 void operator()(value_type& item) { ... }
345 RCU \p synchronize method can be called. RCU should not be locked.
347 Return \p true if key is found and deleted, \p false otherwise
349 template <typename K, typename Func>
350 bool erase( K const& key, Func f )
352 return base_class::erase( key, [&f]( leaf_node& node) { f( node.m_Value ); } );
355 /// Deletes the item from the map using \p pred predicate for searching
357 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_erase_func "erase(K const&, Func)"
358 but \p pred is used for key comparing.
359 \p Less functor has the interface like \p std::less.
360 \p Less must imply the same element order as the comparator used for building the map.
362 template <typename K, typename Less, typename Func>
363 bool erase_with( K const& key, Less pred, Func f )
366 return base_class::erase_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >(),
367 [&f]( leaf_node& node) { f( node.m_Value ); } );
370 /// Extracts an item with minimal key from the map
372 Returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the leftmost item.
373 If the set is empty, returns empty \p exempt_ptr.
375 @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
376 It means that the function gets leftmost leaf of the tree and tries to unlink it.
377 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
378 So, the function returns the item with minimum key at the moment of tree traversing.
380 RCU \p synchronize method can be called. RCU should NOT be locked.
381 The function does not free the item.
382 The deallocator will be implicitly invoked when the returned object is destroyed or when
383 its \p release() member function is called.
385 exempt_ptr extract_min()
387 return exempt_ptr( base_class::extract_min_());
390 /// Extracts an item with maximal key from the map
392 Returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the rightmost item.
393 If the set is empty, returns empty \p exempt_ptr.
395 @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
396 It means that the function gets rightmost leaf of the tree and tries to unlink it.
397 During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
398 So, the function returns the item with maximum key at the moment of tree traversing.
400 RCU \p synchronize method can be called. RCU should NOT be locked.
401 The function does not free the item.
402 The deallocator will be implicitly invoked when the returned object is destroyed or when
403 its \p release() is called.
404 @note Before reusing \p result object you should call its \p release() method.
406 exempt_ptr extract_max()
408 return exempt_ptr( base_class::extract_max_());
411 /// Extracts an item from the map
412 /** \anchor cds_nonintrusive_EllenBinTreeMap_rcu_extract
413 The function searches an item with key equal to \p key in the tree,
414 unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
415 If \p key is not found the function returns an empty \p exempt_ptr.
417 RCU \p synchronize method can be called. RCU should NOT be locked.
418 The function does not destroy the item found.
419 The dealloctor will be implicitly invoked when the returned object is destroyed or when
420 its \p release() member function is called.
422 template <typename Q>
423 exempt_ptr extract( Q const& key )
425 return exempt_ptr( base_class::extract_( key, typename base_class::node_compare()));
428 /// Extracts an item from the map using \p pred for searching
430 The function is an analog of \p extract(Q const&)
431 but \p pred is used for key compare.
432 \p Less has the interface like \p std::less and should meet \ref cds_container_EllenBinTreeSet_rcu_less
433 "predicate requirements".
434 \p pred must imply the same element order as the comparator used for building the map.
436 template <typename Q, typename Less>
437 exempt_ptr extract_with( Q const& key, Less pred )
440 return exempt_ptr( base_class::extract_with_( key,
441 cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >()));
444 /// Find the key \p key
445 /** \anchor cds_nonintrusive_EllenBinTreeMap_rcu_find_cfunc
447 The function searches the item with key equal to \p key and calls the functor \p f for item found.
448 The interface of \p Func functor is:
451 void operator()( value_type& item );
454 where \p item is the item found.
456 The functor may change \p item.second.
458 The function applies RCU lock internally.
460 The function returns \p true if \p key is found, \p false otherwise.
462 template <typename K, typename Func>
463 bool find( K const& key, Func f )
465 return base_class::find( key, [&f](leaf_node& item, K const& ) { f( item.m_Value );});
468 /// Finds the key \p val using \p pred predicate for searching
470 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_find_cfunc "find(K const&, Func)"
471 but \p pred is used for key comparing.
472 \p Less functor has the interface like \p std::less.
473 \p Less must imply the same element order as the comparator used for building the map.
475 template <typename K, typename Less, typename Func>
476 bool find_with( K const& key, Less pred, Func f )
479 return base_class::find_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >(),
480 [&f](leaf_node& item, K const& ) { f( item.m_Value );});
483 /// Checks whether the map contains \p key
485 The function searches the item with key equal to \p key
486 and returns \p true if it is found, and \p false otherwise.
488 The function applies RCU lock internally.
490 template <typename K>
491 bool contains( K const& key )
493 return base_class::contains( key );
496 template <typename K>
497 CDS_DEPRECATED("deprecated, use contains()")
498 bool find( K const& key )
500 return contains( key );
504 /// Checks whether the map contains \p key using \p pred predicate for searching
506 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
507 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
508 "Predicate requirements".
509 \p Less must imply the same element order as the comparator used for building the set.
511 template <typename K, typename Less>
512 bool contains( K const& key, Less pred )
515 return base_class::contains( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >());
518 template <typename K, typename Less>
519 CDS_DEPRECATED("deprecated, use contains()")
520 bool find_with( K const& key, Less pred )
522 return contains( key, pred );
526 /// Finds \p key and return the item found
527 /** \anchor cds_nonintrusive_EllenBinTreeMap_rcu_get
528 The function searches the item with key equal to \p key and returns the pointer to item found.
529 If \p key is not found it returns \p nullptr.
531 RCU should be locked before call the function.
532 Returned pointer is valid while RCU is locked.
534 template <typename Q>
535 value_type * get( Q const& key ) const
537 leaf_node * pNode = base_class::get( key );
538 return pNode ? &pNode->m_Value : nullptr;
541 /// Finds \p key with \p pred predicate and return the item found
543 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_get "get(Q const&)"
544 but \p pred is used for comparing the keys.
546 \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type
547 and \p Q in any order.
548 \p pred must imply the same element order as the comparator used for building the map.
550 template <typename Q, typename Less>
551 value_type * get_with( Q const& key, Less pred ) const
554 leaf_node * pNode = base_class::get_with( key,
555 cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >());
556 return pNode ? &pNode->m_Value : nullptr;
565 /// Checks if the map is empty
568 return base_class::empty();
571 /// Returns item count in the map
573 Only leaf nodes containing user data are counted.
575 The value returned depends on item counter type provided by \p Traits template parameter.
576 If it is \p atomicity::empty_item_counter this function always returns 0.
578 The function is not suitable for checking the tree emptiness, use \p empty()
579 member function for this purpose.
583 return base_class::size();
586 /// Returns const reference to internal statistics
587 stat const& statistics() const
589 return base_class::statistics();
592 /// Checks internal consistency (not atomic, not thread-safe)
594 The debugging function to check internal consistency of the tree.
596 bool check_consistency() const
598 return base_class::check_consistency();
601 }} // namespace cds::container
603 #endif //#ifndef CDSLIB_CONTAINER_ELLEN_BINTREE_MAP_RCU_H