3 #ifndef CDSLIB_CONTAINER_BRONSON_AVLTREE_MAP_RCU_H
4 #define CDSLIB_CONTAINER_BRONSON_AVLTREE_MAP_RCU_H
6 #include <cds/container/impl/bronson_avltree_map_rcu.h>
8 namespace cds { namespace container {
10 namespace bronson_avltree {
13 template < typename Key, typename T, typename Traits>
17 typedef T mapped_type;
18 typedef Traits original_traits;
20 typedef cds::details::Allocator< mapped_type, typename original_traits::allocator > cxx_allocator;
22 struct traits : public original_traits
26 void operator()( mapped_type * p )
28 cxx_allocator().Delete( p );
33 // Metafunction result
34 typedef BronsonAVLTreeMap <
41 } // namespace details
43 } // namespace bronson_avltree
45 /// Bronson et al AVL-tree (RCU specialization)
46 /** @ingroup cds_nonintrusive_map
47 @ingroup cds_nonintrusive_tree
48 @anchor cds_container_BronsonAVLTreeMap_rcu
51 - [2010] N.Bronson, J.Casper, H.Chafi, K.Olukotun "A Practical Concurrent Binary Search Tree"
55 <b>Template arguments</b>:
56 - \p RCU - one of \ref cds_urcu_gc "RCU type"
58 - \p T - value type to be stored in tree's nodes.
59 - \p Traits - tree traits, default is \p bronson_avltree::traits
60 It is possible to declare option-based tree with \p bronson_avltree::make_traits metafunction
61 instead of \p Traits template argument.
63 @note Before including <tt><cds/container/bronson_avltree_map_rcu.h></tt> you should include appropriate RCU header file,
64 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
70 # ifdef CDS_DOXYGEN_INVOKED
71 typename Traits = bronson_avltree::traits
76 class BronsonAVLTreeMap< cds::urcu::gc<RCU>, Key, T, Traits >
77 #ifdef CDS_DOXYGEN_INVOKED
78 : private BronsonAVLTreeMap< cds::urcu::gc<RCU>, Key, T*, Traits >
80 : private bronson_avltree::details::make_map< Key, T, Traits >::type;
84 typedef bronson_avltree::details::make_map< Key, T, Traits > maker;
85 typedef typename maker::type base_class;
89 typedef cds::urcu::gc<RCU> gc; ///< RCU Garbage collector
90 typedef Key key_type; ///< type of a key stored in the map
91 typedef T mapped_type; ///< type of value stored in the map
92 typedef Traits traits; ///< Traits template parameter
94 typedef typename base_class::key_comparator key_comparator; ///< key compare functor based on \p Traits::compare and \p Traits::less
95 typedef typename traits::item_counter item_counter; ///< Item counting policy
96 typedef typename traits::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model option
97 typedef typename traits::allocator allocator_type; ///< allocator for value
98 typedef typename traits::node_allocator node_allocator_type;///< allocator for maintaining internal nodes
99 typedef typename traits::stat stat; ///< internal statistics
100 typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
101 typedef typename traits::back_off back_off; ///< Back-off strategy
102 typedef typename traits::lock_type lock_type; ///< Node lock type
104 /// Enabled or disabled @ref bronson_avltree::relaxed_insert "relaxed insertion"
105 static bool const c_bRelaxedInsert = traits::relaxed_insert;
107 /// Returned pointer to value of extracted node
108 typedef base_class::unique_ptr unique_ptr;
112 typedef typename base_class::node_type node_type;
113 typedef typename base_class::node_scoped_lock node_scoped_lock;
114 typedef typename maker::cxx_allocator cxx_allocator;
116 using base_class::update_flags;
120 /// Creates empty map
128 /// Inserts new node with \p key and default value
130 The function creates a node with \p key and default value, and then inserts the node created into the map.
133 - The \p key_type should be constructible from a value of type \p K.
134 - The \p mapped_type should be default-constructible.
136 RCU \p synchronize() can be called. RCU should not be locked.
138 Returns \p true if inserting successful, \p false otherwise.
140 template <typename K>
141 bool insert( K const& key )
143 return base_class::do_update(key, key_comparator(),
144 []( node_type * pNode ) -> mapped_type*
146 assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
147 return cxx_allocator().New();
149 update_flags::allow_insert
150 ) == update_flags::result_insert;
155 The function creates a node with copy of \p val value
156 and then inserts the node created into the map.
159 - The \p key_type should be constructible from \p key of type \p K.
160 - The \p mapped_type should be constructible from \p val of type \p V.
162 RCU \p synchronize() method can be called. RCU should not be locked.
164 Returns \p true if \p val is inserted into the map, \p false otherwise.
166 template <typename K, typename V>
167 bool insert( K const& key, V const& val )
169 return base_class::do_update( key, key_comparator(),
170 [&val]( node_type * pNode )
172 assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
173 return cxx_allocator().New( val );
175 update_flags::allow_insert
176 ) == update_flags::result_insert;
179 /// Inserts new node and initialize it by a functor
181 This function inserts new node with key \p key and if inserting is successful then it calls
182 \p func functor with signature
185 void operator()( mapped_type& item );
189 The key_type should be constructible from value of type \p K.
191 The function allows to split creating of new item into two part:
192 - create item from \p key;
193 - insert new item into the map;
194 - if inserting is successful, initialize the value of item by calling \p func functor
196 This can be useful if complete initialization of object of \p value_type is heavyweight and
197 it is preferable that the initialization should be completed only if inserting is successful.
198 The functor is called under the node lock.
200 RCU \p synchronize() method can be called. RCU should not be locked.
202 template <typename K, typename Func>
203 bool insert_with( K const& key, Func func )
205 return base_class::do_update( key, key_comparator(),
206 [&func]( node_type * pNode ) -> mapped_type*
208 assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
209 mapped_type * pVal = cxx_allocator().New();
213 update_flags::allow_insert
214 ) == update_flags::result_insert;
217 /// For key \p key inserts data of type \p mapped_type created in-place from \p args
219 Returns \p true if inserting successful, \p false otherwise.
221 RCU \p synchronize() method can be called. RCU should not be locked.
223 template <typename K, typename... Args>
224 bool emplace( K&& key, Args&&... args )
226 return base_class::do_update( key, key_comparator(),
227 [&]( node_type * pNode ) -> mapped_type*
229 assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
230 return cxx_allocator().New( std::forward<Args>(args)...);
232 update_flags::allow_insert
233 ) == update_flags::result_insert;
236 /// Ensures that the \p key exists in the map
238 The operation performs inserting or changing data with lock-free manner.
240 If the \p key not found in the map, then the new item created from \p key
241 is inserted into the map (note that in this case the \ref key_type should be
242 constructible from type \p K).
243 Otherwise, the functor \p func is called with item found.
244 The functor \p Func may be a functor:
247 void operator()( bool bNew, mapped_type& item );
252 - \p bNew - \p true if the item has been inserted, \p false otherwise
255 The functor may change any fields of the \p item. The functor is called under the node lock.
257 RCU \p synchronize() method can be called. RCU should not be locked.
259 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
260 \p second is \p true if new item has been added or \p false if the item with \p key
261 already is in the tree.
263 template <typename K, typename Func>
264 std::pair<bool, bool> update( K const& key, Func func )
266 int result = base_class::do_update( key, key_comparator(),
267 [&func]( node_type * pNode ) -> mapped_type*
269 mapped_type * pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed ));
271 pVal = cxx_allocator().New();
275 func( false, *pVal );
278 update_flags::allow_insert | update_flags::allow_update
280 return std::make_pair( result != 0, (result & update_flags::result_insert) != 0 );
283 /// Delete \p key from the map
285 RCU \p synchronize() method can be called. RCU should not be locked.
287 Return \p true if \p key is found and deleted, \p false otherwise
289 template <typename K>
290 bool erase( K const& key )
292 return base_class::erase( key );
295 /// Deletes the item from the map using \p pred predicate for searching
297 The function is an analog of \p erase(K const&)
298 but \p pred is used for key comparing.
299 \p Less functor has the interface like \p std::less.
300 \p Less must imply the same element order as the comparator used for building the map.
302 template <typename K, typename Less>
303 bool erase_with( K const& key, Less pred )
305 return base_class::erase_with( key, pred );
308 /// Delete \p key from the map
309 /** \anchor cds_nonintrusive_BronsonAVLTreeMap_rcu_erase_func
311 The function searches an item with key \p key, calls \p f functor
312 and deletes the item. If \p key is not found, the functor is not called.
314 The functor \p Func interface:
317 void operator()(mapped_type& item) { ... }
321 RCU \p synchronize method can be called. RCU should not be locked.
323 Return \p true if key is found and deleted, \p false otherwise
325 template <typename K, typename Func>
326 bool erase( K const& key, Func f )
328 return base_class::erase( key, f );
331 /// Deletes the item from the map using \p pred predicate for searching
333 The function is an analog of \ref cds_nonintrusive_BronsonAVLTreeMap_rcu_erase_func "erase(K const&, Func)"
334 but \p pred is used for key comparing.
335 \p Less functor has the interface like \p std::less.
336 \p Less must imply the same element order as the comparator used for building the map.
338 template <typename K, typename Less, typename Func>
339 bool erase_with( K const& key, Less pred, Func f )
341 return base_class::erase_with( key, pred, f );
344 /// Extracts an item with minimal key from the map
346 Returns \p std::unique_ptr pointer to the leftmost item.
347 If the set is empty, returns empty \p std::unique_ptr.
349 @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
350 It means that the function gets leftmost leaf of the tree and tries to unlink it.
351 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
352 So, the function returns the item with minimum key at the moment of tree traversing.
354 RCU \p synchronize method can be called. RCU should NOT be locked.
355 The function does not free the item.
356 The deallocator will be implicitly invoked when the returned object is destroyed or when
357 its \p reset(nullptr) member function is called.
359 unique_ptr extract_min()
361 return base_class::extract_min();
364 /// Extracts an item with maximal key from the map
366 Returns \std::unique_ptr pointer to the rightmost item.
367 If the set is empty, returns empty \p std::unique_ptr.
369 @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
370 It means that the function gets rightmost leaf of the tree and tries to unlink it.
371 During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
372 So, the function returns the item with maximum key at the moment of tree traversing.
374 RCU \p synchronize method can be called. RCU should NOT be locked.
375 The function does not free the item.
376 The deallocator will be implicitly invoked when the returned object is destroyed or when
377 its \p reset(nullptr) is called.
378 @note Before reusing \p result object you should call its \p release() method.
380 unique_ptr extract_max()
382 return base_class::extract_min();
385 /// Extracts an item from the map
387 The function searches an item with key equal to \p key in the tree,
388 unlinks it, and returns \p std::unique_ptr pointer to a value found.
389 If \p key is not found the function returns an empty \p std::unique_ptr.
391 RCU \p synchronize method can be called. RCU should NOT be locked.
392 The function does not destroy the value found.
393 The dealloctor will be implicitly invoked when the returned object is destroyed or when
394 its \p reset(nullptr) member function is called.
396 template <typename Q>
397 unique_ptr extract( Q const& key )
399 return base_class::extract( key );
402 /// Extracts an item from the map using \p pred for searching
404 The function is an analog of \p extract(Q const&)
405 but \p pred is used for key compare.
406 \p Less has the interface like \p std::less and should meet \ref cds_container_EllenBinTreeSet_rcu_less
407 "predicate requirements".
408 \p pred must imply the same element order as the comparator used for building the map.
410 template <typename Q, typename Less>
411 unique_ptr extract_with( Q const& key, Less pred )
413 return base_class::extract_with( key, pred );
416 /// Find the key \p key
418 The function searches the item with key equal to \p key and calls the functor \p f for item found.
419 The interface of \p Func functor is:
422 void operator()( mapped_type& item );
425 where \p item is the item found.
426 The functor is called under node-level lock.
428 The function applies RCU lock internally.
430 The function returns \p true if \p key is found, \p false otherwise.
432 template <typename K, typename Func>
433 bool find( K const& key, Func f )
435 return base_class::find( key, f );
438 /// Finds the key \p val using \p pred predicate for searching
440 The function is an analog of \p find(K const&, Func)
441 but \p pred is used for key comparing.
442 \p Less functor has the interface like \p std::less.
443 \p Less must imply the same element order as the comparator used for building the map.
445 template <typename K, typename Less, typename Func>
446 bool find_with( K const& key, Less pred, Func f )
448 return base_class::find_with( key, pred, f );
451 /// Find the key \p key
453 The function searches the item with key equal to \p key
454 and returns \p true if it is found, and \p false otherwise.
456 The function applies RCU lock internally.
458 template <typename K>
459 bool find( K const& key )
461 return base_class::find( key );
464 /// Finds the key \p val using \p pred predicate for searching
466 The function is an analog of \p find(K const&)
467 but \p pred is used for key comparing.
468 \p Less functor has the interface like \p std::less.
469 \p Less must imply the same element order as the comparator used for building the map.
471 template <typename K, typename Less>
472 bool find_with( K const& key, Less pred )
474 return base_class::find_with( key, pred );
483 /// Checks if the map is empty
486 return base_class::empty();
489 /// Returns item count in the map
491 Only leaf nodes containing user data are counted.
493 The value returned depends on item counter type provided by \p Traits template parameter.
494 If it is \p atomicity::empty_item_counter this function always returns 0.
496 The function is not suitable for checking the tree emptiness, use \p empty()
497 member function for this purpose.
501 return base_class::size();
504 /// Returns const reference to internal statistics
505 stat const& statistics() const
507 return base_class::statistics();
510 /// Checks internal consistency (not atomic, not thread-safe)
512 The debugging function to check internal consistency of the tree.
514 bool check_consistency() const
516 return base_class::check_consistency();
520 }} // namespace cds::container
522 #endif // #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H