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 < class RCU, 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
25 void operator()( mapped_type * p ) const
27 cxx_allocator().Delete( p );
32 // Metafunction result
33 typedef BronsonAVLTreeMap< RCU, Key, mapped_type *, traits > type;
35 } // namespace details
37 } // namespace bronson_avltree
39 /// Bronson et al AVL-tree (RCU specialization)
40 /** @ingroup cds_nonintrusive_map
41 @ingroup cds_nonintrusive_tree
42 @anchor cds_container_BronsonAVLTreeMap_rcu
45 - [2010] N.Bronson, J.Casper, H.Chafi, K.Olukotun "A Practical Concurrent Binary Search Tree"
49 <b>Template arguments</b>:
50 - \p RCU - one of \ref cds_urcu_gc "RCU type"
52 - \p T - value type to be stored in tree's nodes.
53 - \p Traits - tree traits, default is \p bronson_avltree::traits
54 It is possible to declare option-based tree with \p bronson_avltree::make_traits metafunction
55 instead of \p Traits template argument.
57 @note Before including <tt><cds/container/bronson_avltree_map_rcu.h></tt> you should include appropriate RCU header file,
58 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
64 # ifdef CDS_DOXYGEN_INVOKED
65 typename Traits = bronson_avltree::traits
70 class BronsonAVLTreeMap< cds::urcu::gc<RCU>, Key, T, Traits >
71 #ifdef CDS_DOXYGEN_INVOKED
72 : private BronsonAVLTreeMap< cds::urcu::gc<RCU>, Key, T*, Traits >
74 : private bronson_avltree::details::make_map< cds::urcu::gc<RCU>, Key, T, Traits >::type
78 typedef bronson_avltree::details::make_map< cds::urcu::gc<RCU>, Key, T, Traits > maker;
79 typedef typename maker::type base_class;
83 typedef cds::urcu::gc<RCU> gc; ///< RCU Garbage collector
84 typedef Key key_type; ///< type of a key stored in the map
85 typedef T mapped_type; ///< type of value stored in the map
86 typedef Traits traits; ///< Traits template parameter
88 typedef typename base_class::key_comparator key_comparator; ///< key compare functor based on \p Traits::compare and \p Traits::less
89 typedef typename traits::item_counter item_counter; ///< Item counting policy
90 typedef typename traits::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model option
91 typedef typename traits::allocator allocator_type; ///< allocator for value
92 typedef typename traits::node_allocator node_allocator_type;///< allocator for maintaining internal nodes
93 typedef typename traits::stat stat; ///< internal statistics
94 typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
95 typedef typename traits::back_off back_off; ///< Back-off strategy
96 typedef typename traits::sync_monitor sync_monitor; ///< @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
98 /// Enabled or disabled @ref bronson_avltree::relaxed_insert "relaxed insertion"
99 static bool const c_bRelaxedInsert = traits::relaxed_insert;
100 typedef typename base_class::rcu_lock rcu_lock; ///< RCU scoped lock
102 /// Returned pointer to \p mapped_type of extracted node
103 typedef typename base_class::exempt_ptr exempt_ptr;
107 typedef typename base_class::node_type node_type;
108 typedef typename base_class::node_scoped_lock node_scoped_lock;
109 typedef typename maker::cxx_allocator cxx_allocator;
111 typedef typename base_class::update_flags update_flags;
115 /// Creates empty map
123 /// Inserts new node with \p key and default value
125 The function creates a node with \p key and default value, and then inserts the node created into the map.
128 - The \p key_type should be constructible from a value of type \p K.
129 - The \p mapped_type should be default-constructible.
131 RCU \p synchronize() can be called. RCU should not be locked.
133 Returns \p true if inserting successful, \p false otherwise.
135 template <typename K>
136 bool insert( K const& key )
138 return base_class::do_update(key, key_comparator(),
139 []( node_type * pNode ) -> mapped_type*
141 assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
143 return cxx_allocator().New();
145 update_flags::allow_insert
146 ) == update_flags::result_inserted;
151 The function creates a node with copy of \p val value
152 and then inserts the node created into the map.
155 - The \p key_type should be constructible from \p key of type \p K.
156 - The \p mapped_type should be constructible from \p val of type \p V.
158 RCU \p synchronize() method can be called. RCU should not be locked.
160 Returns \p true if \p val is inserted into the map, \p false otherwise.
162 template <typename K, typename V>
163 bool insert( K const& key, V const& val )
165 return base_class::do_update( key, key_comparator(),
166 [&val]( node_type * pNode ) -> mapped_type*
168 assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
170 return cxx_allocator().New( val );
172 update_flags::allow_insert
173 ) == update_flags::result_inserted;
176 /// Inserts new node and initialize it by a functor
178 This function inserts new node with key \p key and if inserting is successful then it calls
179 \p func functor with signature
182 void operator()( key_type const& key, mapped_type& item );
186 The key_type should be constructible from value of type \p K.
188 The function allows to split creating of new item into two part:
189 - create item from \p key;
190 - insert new item into the map;
191 - if inserting is successful, initialize the value of item by calling \p func functor
193 This can be useful if complete initialization of object of \p value_type is heavyweight and
194 it is preferable that the initialization should be completed only if inserting is successful.
195 The functor is called under the node lock.
197 RCU \p synchronize() method can be called. RCU should not be locked.
199 template <typename K, typename Func>
200 bool insert_with( K const& key, Func func )
202 return base_class::do_update( key, key_comparator(),
203 [&func]( node_type * pNode ) -> mapped_type*
205 assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
206 mapped_type * pVal = cxx_allocator().New();
207 func( pNode->m_key, *pVal );
210 update_flags::allow_insert
211 ) == update_flags::result_inserted;
214 /// For key \p key inserts data of type \p mapped_type created in-place from \p args
216 Returns \p true if inserting successful, \p false otherwise.
218 RCU \p synchronize() method can be called. RCU should not be locked.
220 template <typename K, typename... Args>
221 bool emplace( K&& key, Args&&... args )
223 return base_class::do_update( key, key_comparator(),
224 [&]( node_type * pNode ) -> mapped_type*
226 assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
228 return cxx_allocator().New( std::forward<Args>(args)...);
230 update_flags::allow_insert
231 ) == update_flags::result_inserted;
234 /// Ensures that the \p key exists in the map
236 The operation performs inserting or changing data with lock-free manner.
238 If the \p key not found in the map, then the new item created from \p key
239 will be inserted into the map (note that in this case the \ref key_type should be
240 constructible from type \p K).
241 Otherwise, the functor \p func is called with item found.
242 The functor \p Func may be a functor:
245 void operator()( bool bNew, key_type const& key, mapped_type& item );
250 - \p bNew - \p true if the item has been inserted, \p false otherwise
253 The functor may change any fields of the \p item. The functor is called under the node lock.
255 RCU \p synchronize() method can be called. RCU should not be locked.
257 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
258 \p second is \p true if new item has been added or \p false if the item with \p key
261 template <typename K, typename Func>
262 std::pair<bool, bool> update( K const& key, Func func )
264 int result = base_class::do_update( key, key_comparator(),
265 [&func]( node_type * pNode ) -> mapped_type*
267 mapped_type * pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
269 pVal = cxx_allocator().New();
270 func( true, pNode->m_key, *pVal );
273 func( false, pNode->m_key, *pVal );
276 update_flags::allow_insert | update_flags::allow_update
278 return std::make_pair( result != 0, (result & update_flags::result_inserted) != 0 );
281 /// Delete \p key from the map
283 RCU \p synchronize() method can be called. RCU should not be locked.
285 Return \p true if \p key is found and deleted, \p false otherwise
287 template <typename K>
288 bool erase( K const& key )
290 return base_class::erase( key );
293 /// Deletes the item from the map using \p pred predicate for searching
295 The function is an analog of \p erase(K const&)
296 but \p pred is used for key comparing.
297 \p Less functor has the interface like \p std::less.
298 \p Less must imply the same element order as the comparator used for building the map.
300 template <typename K, typename Less>
301 bool erase_with( K const& key, Less pred )
303 return base_class::erase_with( key, pred );
306 /// Delete \p key from the map
307 /** \anchor cds_nonintrusive_BronsonAVLTreeMap_rcu_erase_func
309 The function searches an item with key \p key, calls \p f functor
310 and deletes the item. If \p key is not found, the functor is not called.
312 The functor \p Func interface:
315 void operator()(mapped_type& item) { ... }
319 RCU \p synchronize method can be called. RCU should not be locked.
321 Return \p true if key is found and deleted, \p false otherwise
323 template <typename K, typename Func>
324 bool erase( K const& key, Func f )
326 return base_class::erase( key, f );
329 /// Deletes the item from the map using \p pred predicate for searching
331 The function is an analog of \ref cds_nonintrusive_BronsonAVLTreeMap_rcu_erase_func "erase(K const&, Func)"
332 but \p pred is used for key comparing.
333 \p Less functor has the interface like \p std::less.
334 \p Less must imply the same element order as the comparator used for building the map.
336 template <typename K, typename Less, typename Func>
337 bool erase_with( K const& key, Less pred, Func f )
339 return base_class::erase_with( key, pred, f );
342 /// Extracts a value with minimal key from the map
344 Returns \p exempt_ptr pointer to the leftmost item.
345 If the set is empty, returns empty \p exempt_ptr.
347 Note that the function returns only the value for minimal key.
348 To retrieve its key use \p extract_min( Func ) member function.
350 @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
351 It means that the function gets leftmost leaf of the tree and tries to unlink it.
352 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
353 So, the function returns the item with minimum key at the moment of tree traversing.
355 RCU \p synchronize method can be called. RCU should NOT be locked.
356 The function does not free the item.
357 The deallocator will be implicitly invoked when the returned object is destroyed or when
358 its \p release() member function is called.
360 exempt_ptr extract_min()
362 return base_class::extract_min();
365 /// Extracts minimal key key and corresponding value
367 Returns \p exempt_ptr to the leftmost item.
368 If the tree is empty, returns empty \p exempt_ptr.
370 \p Func functor is used to store minimal key.
371 \p Func has the following signature:
374 void operator()( key_type const& key );
377 If the tree is empty, \p f is not called.
378 Otherwise, is it called with minimal key, the pointer to corresponding value is returned
381 @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
382 It means that the function gets leftmost leaf of the tree and tries to unlink it.
383 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
384 So, the function returns the item with minimum key at the moment of tree traversing.
386 RCU \p synchronize method can be called. RCU should NOT be locked.
387 The function does not free the item.
388 The deallocator will be implicitly invoked when the returned object is destroyed or when
389 its \p release() member function is called.
391 template <typename Func>
392 exempt_ptr extract_min( Func f )
394 return base_class::extract_min( f );
397 /// Extracts minimal key key and corresponding value
399 This function is a shortcut for the following call:
402 exempt_ptr xp = theTree.extract_min( [&key]( key_type const& k ) { key = k; } );
404 \p key_type should be copy-assignable. The copy of minimal key
405 is returned in \p min_key argument.
407 typename std::enable_if< std::is_copy_assignable<key_type>::value, exempt_ptr >::type
408 extract_min_key( key_type& min_key )
410 return base_class::extract_min_key( min_key );
413 /// Extracts an item with maximal key from the map
415 Returns \p exempt_ptr pointer to the rightmost item.
416 If the set is empty, returns empty \p exempt_ptr.
418 Note that the function returns only the value for maximal key.
419 To retrieve its key use \p extract_max( Func ) member function.
421 @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
422 It means that the function gets rightmost leaf of the tree and tries to unlink it.
423 During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
424 So, the function returns the item with maximum key at the moment of tree traversing.
426 RCU \p synchronize method can be called. RCU should NOT be locked.
427 The function does not free the item.
428 The deallocator will be implicitly invoked when the returned object is destroyed or when
429 its \p release() is called.
431 exempt_ptr extract_max()
433 return base_class::extract_max();
436 /// Extracts the maximal key and corresponding value
438 Returns \p exempt_ptr pointer to the rightmost item.
439 If the set is empty, returns empty \p exempt_ptr.
441 \p Func functor is used to store maximal key.
442 \p Func has the following signature:
445 void operator()( key_type const& key );
448 If the tree is empty, \p f is not called.
449 Otherwise, is it called with maximal key, the pointer to corresponding value is returned
452 @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
453 It means that the function gets rightmost leaf of the tree and tries to unlink it.
454 During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
455 So, the function returns the item with maximum key at the moment of tree traversing.
457 RCU \p synchronize method can be called. RCU should NOT be locked.
458 The function does not free the item.
459 The deallocator will be implicitly invoked when the returned object is destroyed or when
460 its \p release() is called.
462 template <typename Func>
463 exempt_ptr extract_max( Func f )
465 return base_class::extract_max( f );
468 /// Extracts the maximal key and corresponding value
470 This function is a shortcut for the following call:
473 exempt_ptr xp = theTree.extract_max( [&key]( key_type const& k ) { key = k; } );
475 \p key_type should be copy-assignable. The copy of maximal key
476 is returned in \p max_key argument.
478 typename std::enable_if< std::is_copy_assignable<key_type>::value, exempt_ptr >::type
479 extract_max_key( key_type& max_key )
481 return base_class::extract_max_key( max_key );
484 /// Extracts an item from the map
486 The function searches an item with key equal to \p key in the tree,
487 unlinks it, and returns \p exempt_ptr pointer to a value found.
488 If \p key is not found the function returns an empty \p exempt_ptr.
490 RCU \p synchronize method can be called. RCU should NOT be locked.
491 The function does not destroy the value found.
492 The dealloctor will be implicitly invoked when the returned object is destroyed or when
493 its \p release() member function is called.
495 template <typename Q>
496 exempt_ptr extract( Q const& key )
498 return base_class::extract( key );
501 /// Extracts an item from the map using \p pred for searching
503 The function is an analog of \p extract(Q const&)
504 but \p pred is used for key compare.
505 \p Less 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 exempt_ptr extract_with( Q const& key, Less pred )
511 return base_class::extract_with( key, pred );
514 /// Find the key \p key
516 The function searches the item with key equal to \p key and calls the functor \p f for item found.
517 The interface of \p Func functor is:
520 void operator()( key_type const& key, mapped_type& val );
523 where \p val is the item found for \p key
524 The functor is called under node-level lock.
526 The function applies RCU lock internally.
528 The function returns \p true if \p key is found, \p false otherwise.
530 template <typename K, typename Func>
531 bool find( K const& key, Func f )
533 return base_class::find( key, f );
536 /// Finds the key \p val using \p pred predicate for searching
538 The function is an analog of \p find(K const&, Func)
539 but \p pred is used for key comparing.
540 \p Less functor has the interface like \p std::less.
541 \p Less must imply the same element order as the comparator used for building the map.
543 template <typename K, typename Less, typename Func>
544 bool find_with( K const& key, Less pred, Func f )
546 return base_class::find_with( key, pred, f );
549 /// Find the key \p key
551 The function searches the item with key equal to \p key
552 and returns \p true if it is found, and \p false otherwise.
554 The function applies RCU lock internally.
556 template <typename K>
557 bool find( K const& key )
559 return base_class::find( key );
562 /// Finds the key \p val using \p pred predicate for searching
564 The function is an analog of \p find(K const&)
565 but \p pred is used for key comparing.
566 \p Less functor has the interface like \p std::less.
567 \p Less must imply the same element order as the comparator used for building the map.
569 template <typename K, typename Less>
570 bool find_with( K const& key, Less pred )
572 return base_class::find_with( key, pred );
581 /// Checks if the map is empty
584 return base_class::empty();
587 /// Returns item count in the map
589 Only leaf nodes containing user data are counted.
591 The value returned depends on item counter type provided by \p Traits template parameter.
592 If it is \p atomicity::empty_item_counter this function always returns 0.
594 The function is not suitable for checking the tree emptiness, use \p empty()
595 member function for this purpose.
599 return base_class::size();
602 /// Returns const reference to internal statistics
603 stat const& statistics() const
605 return base_class::statistics();
608 /// Checks internal consistency (not atomic, not thread-safe)
610 The debugging function to check internal consistency of the tree.
612 bool check_consistency() const
614 return base_class::check_consistency();
617 /// Checks internal consistency (not atomic, not thread-safe)
619 The debugging function to check internal consistency of the tree.
620 The functor \p Func is called if a violation of internal tree structure
624 void operator()( size_t nLevel, size_t hLeft, size_t hRight );
628 - \p nLevel - the level where the violation is found
629 - \p hLeft - the height of left subtree
630 - \p hRight - the height of right subtree
632 The functor is called for each violation found.
634 template <typename Func>
635 bool check_consistency( Func f ) const
637 return base_class::check_consistency( f );
640 }} // namespace cds::container
642 #endif // #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H