From 40ed14f058de6251c63b5323c9aa7bd363758868 Mon Sep 17 00:00:00 2001 From: khizmax Date: Fri, 13 Feb 2015 23:45:20 +0300 Subject: [PATCH] changed std::unique_ptr to more restrictive cds::urcu::exempt_ptr --- cds/container/bronson_avltree_map_rcu.h | 117 +++++++++++------- cds/container/details/bronson_avltree_base.h | 6 +- cds/container/impl/bronson_avltree_map_rcu.h | 122 +++++++++++-------- cds/urcu/exempt_ptr.h | 2 +- 4 files changed, 151 insertions(+), 96 deletions(-) diff --git a/cds/container/bronson_avltree_map_rcu.h b/cds/container/bronson_avltree_map_rcu.h index c9637232..40768ab0 100644 --- a/cds/container/bronson_avltree_map_rcu.h +++ b/cds/container/bronson_avltree_map_rcu.h @@ -17,12 +17,30 @@ namespace cds { namespace container { typedef T mapped_type; typedef Traits original_traits; - typedef cds::details::Allocator< mapped_type, typename original_traits::allocator > cxx_allocator; + struct internal_mapped_type : public bronson_avltree::value + { + mapped_type m_val; + + template + internal_mapped_type( Args&&... args ) + : m_val( std::forward(args)...) + {} + }; + + typedef cds::details::Allocator< internal_mapped_type, typename original_traits::allocator > cxx_allocator; + + struct cast_mapped_type + { + mapped_type * operator()( internal_mapped_type * p ) const + { + return &(p->m_val); + } + }; struct traits : public original_traits { struct disposer { - void operator()( mapped_type * p ) const + void operator()( internal_mapped_type * p ) const { cxx_allocator().Delete( p ); } @@ -30,7 +48,7 @@ namespace cds { namespace container { }; // Metafunction result - typedef BronsonAVLTreeMap< RCU, Key, T *, traits > type; + typedef BronsonAVLTreeMap< RCU, Key, internal_mapped_type *, traits > type; }; } // namespace details //@endcond @@ -97,21 +115,32 @@ namespace cds { namespace container { /// Enabled or disabled @ref bronson_avltree::relaxed_insert "relaxed insertion" static bool const c_bRelaxedInsert = traits::relaxed_insert; - - /// Returned pointer to value of extracted node - typedef typename base_class::unique_ptr unique_ptr; - typedef typename base_class::rcu_lock rcu_lock; ///< RCU scoped lock protected: //@cond - typedef typename base_class::node_type node_type; + typedef typename base_class::node_type node_type; + typedef typename maker::internal_mapped_type internal_mapped_type; typedef typename base_class::node_scoped_lock node_scoped_lock; - typedef typename maker::cxx_allocator cxx_allocator; + typedef typename maker::cxx_allocator cxx_allocator; typedef typename base_class::update_flags update_flags; //@endcond + public: +# ifdef CDSDOXYGEN_INVOKED + /// Returned pointer to \p mapped_type of extracted node + typedef cds::urcu::exempt_ptr< gc, implementation_defined, mapped_type, implementation_defined, implementation_defined > exempt_ptr; +# else + typedef cds::urcu::exempt_ptr< gc, + internal_mapped_type, + mapped_type, + typename maker::traits::disposer, + typename maker::cast_mapped_type + > exempt_ptr; +# endif + + public: /// Creates empty map BronsonAVLTreeMap() @@ -137,7 +166,7 @@ namespace cds { namespace container { bool insert( K const& key ) { return base_class::do_update(key, key_comparator(), - []( node_type * pNode ) -> mapped_type* + []( node_type * pNode ) -> internal_mapped_type* { assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr ); CDS_UNUSED( pNode ); @@ -164,7 +193,7 @@ namespace cds { namespace container { bool insert( K const& key, V const& val ) { return base_class::do_update( key, key_comparator(), - [&val]( node_type * pNode ) + [&val]( node_type * pNode ) -> internal_mapped_type* { assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr ); CDS_UNUSED( pNode ); @@ -201,11 +230,11 @@ namespace cds { namespace container { bool insert_with( K const& key, Func func ) { return base_class::do_update( key, key_comparator(), - [&func]( node_type * pNode ) -> mapped_type* + [&func]( node_type * pNode ) -> internal_mapped_type* { assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr ); - mapped_type * pVal = cxx_allocator().New(); - func( pNode->m_key, *pVal ); + internal_mapped_type * pVal = cxx_allocator().New(); + func( pNode->m_key, pVal->m_val ); return pVal; }, update_flags::allow_insert @@ -222,7 +251,7 @@ namespace cds { namespace container { bool emplace( K&& key, Args&&... args ) { return base_class::do_update( key, key_comparator(), - [&]( node_type * pNode ) -> mapped_type* + [&]( node_type * pNode ) -> internal_mapped_type* { assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr ); CDS_UNUSED( pNode ); @@ -263,15 +292,15 @@ namespace cds { namespace container { std::pair update( K const& key, Func func ) { int result = base_class::do_update( key, key_comparator(), - [&func]( node_type * pNode ) -> mapped_type* + [&func]( node_type * pNode ) -> internal_mapped_type* { - mapped_type * pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed ); + internal_mapped_type * pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed ); if ( !pVal ) { pVal = cxx_allocator().New(); - func( true, pNode->m_key, *pVal ); + func( true, pNode->m_key, pVal->m_val ); } else - func( false, pNode->m_key, *pVal ); + func( false, pNode->m_key, pVal->m_val ); return pVal; }, update_flags::allow_insert | update_flags::allow_update @@ -324,7 +353,7 @@ namespace cds { namespace container { template bool erase( K const& key, Func f ) { - return base_class::erase( key, f ); + return base_class::erase( key, [&f]( internal_mapped_type& v) { f( v.m_val ); }); } /// Deletes the item from the map using \p pred predicate for searching @@ -337,13 +366,13 @@ namespace cds { namespace container { template bool erase_with( K const& key, Less pred, Func f ) { - return base_class::erase_with( key, pred, f ); + return base_class::erase_with( key, pred, [&f]( internal_mapped_type& v) { f( v.m_val ); } ); } /// Extracts an item with minimal key from the map /** - Returns \p std::unique_ptr pointer to the leftmost item. - If the set is empty, returns empty \p std::unique_ptr. + Returns \p exempt_ptr pointer to the leftmost item. + If the set is empty, returns empty \p exempt_ptr. @note Due the concurrent nature of the map, the function extracts nearly minimum key. It means that the function gets leftmost leaf of the tree and tries to unlink it. @@ -353,17 +382,17 @@ namespace cds { namespace container { RCU \p synchronize method can be called. RCU should NOT be locked. The function does not free the item. The deallocator will be implicitly invoked when the returned object is destroyed or when - its \p reset(nullptr) member function is called. + its \p release() member function is called. */ - unique_ptr extract_min() + exempt_ptr extract_min() { - return base_class::extract_min(); + return exempt_ptr( base_class::do_extract_min()); } /// Extracts an item with maximal key from the map /** - Returns \p std::unique_ptr pointer to the rightmost item. - If the set is empty, returns empty \p std::unique_ptr. + Returns \p exempt_ptr pointer to the rightmost item. + If the set is empty, returns empty \p exempt_ptr. @note Due the concurrent nature of the map, the function extracts nearly maximal key. It means that the function gets rightmost leaf of the tree and tries to unlink it. @@ -373,43 +402,41 @@ namespace cds { namespace container { RCU \p synchronize method can be called. RCU should NOT be locked. The function does not free the item. The deallocator will be implicitly invoked when the returned object is destroyed or when - its \p reset(nullptr) is called. - @note Before reusing \p result object you should call its \p release() method. + its \p release() is called. */ - unique_ptr extract_max() + exempt_ptr extract_max() { - return base_class::extract_min(); + return exempt_ptr( base_class::do_extract_min()); } /// Extracts an item from the map /** The function searches an item with key equal to \p key in the tree, - unlinks it, and returns \p std::unique_ptr pointer to a value found. - If \p key is not found the function returns an empty \p std::unique_ptr. + unlinks it, and returns \p exempt_ptr pointer to a value found. + If \p key is not found the function returns an empty \p exempt_ptr. RCU \p synchronize method can be called. RCU should NOT be locked. The function does not destroy the value found. The dealloctor will be implicitly invoked when the returned object is destroyed or when - its \p reset(nullptr) member function is called. + its \p release() member function is called. */ template - unique_ptr extract( Q const& key ) + exempt_ptr extract( Q const& key ) { - return base_class::extract( key ); + return exempt_ptr( base_class::do_extract( key )); } /// Extracts an item from the map using \p pred for searching /** The function is an analog of \p extract(Q const&) but \p pred is used for key compare. - \p Less has the interface like \p std::less and should meet \ref cds_container_EllenBinTreeSet_rcu_less - "predicate requirements". + \p Less has the interface like \p std::less. \p pred must imply the same element order as the comparator used for building the map. */ template - unique_ptr extract_with( Q const& key, Less pred ) + exempt_ptr extract_with( Q const& key, Less pred ) { - return base_class::extract_with( key, pred ); + return exempt_ptr( base_class::do_extract_with( key, pred )); } /// Find the key \p key @@ -418,10 +445,10 @@ namespace cds { namespace container { The interface of \p Func functor is: \code struct functor { - void operator()( mapped_type& item ); + void operator()( key_type const& key, mapped_type& val ); }; \endcode - where \p item is the item found. + where \p val is the item found for \p key The functor is called under node-level lock. The function applies RCU lock internally. @@ -431,7 +458,7 @@ namespace cds { namespace container { template bool find( K const& key, Func f ) { - return base_class::find( key, f ); + return base_class::find( key, [&f]( key_type const& key, internal_mapped_type& v) { f( key, v.m_val ); }); } /// Finds the key \p val using \p pred predicate for searching @@ -444,7 +471,7 @@ namespace cds { namespace container { template bool find_with( K const& key, Less pred, Func f ) { - return base_class::find_with( key, pred, f ); + return base_class::find_with( key, pred, [&f]( key_type const& key, internal_mapped_type& v) { f( key, v.m_val ); } ); } /// Find the key \p key diff --git a/cds/container/details/bronson_avltree_base.h b/cds/container/details/bronson_avltree_base.h index ca9540ec..91166c1e 100644 --- a/cds/container/details/bronson_avltree_base.h +++ b/cds/container/details/bronson_avltree_base.h @@ -171,17 +171,19 @@ namespace cds { namespace container { the node from the tree. It this case it is not possible to support map's methods that return raw pointer to the tree's value. - if the value type is based on \p %bronson_avltree::value, - i.e. \p std::is_base_of( bronson_avltree::value, value_type )::value is \p true, + i.e. std::is_base_of( bronson_avltree::value, value_type )::value is \p true, the disposer is called via full RCU cycle. It means that under RCU lock the methods returning raw pointer can be implemented. */ struct value { + //@cond value * m_pNextRetired; value() : m_pNextRetired(nullptr) {} + //@endcond }; /// BronsonAVLTreeMap internal statistics @@ -279,7 +281,7 @@ namespace cds { namespace container { that can lead to lock contention. When this option is enabled, the new node is created before locking the parent node. - After that, the parent is locked and checked whether the new node can be attached to the parent. + After that, the parent is locked and checked whether the new node may be attached to the parent. In this case, false node creating can be performed, but locked section can be significantly small. */ template diff --git a/cds/container/impl/bronson_avltree_map_rcu.h b/cds/container/impl/bronson_avltree_map_rcu.h index d6d0025e..923f5fbf 100644 --- a/cds/container/impl/bronson_avltree_map_rcu.h +++ b/cds/container/impl/bronson_avltree_map_rcu.h @@ -3,10 +3,10 @@ #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H #define CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H -#include // unique_ptr #include // is_base_of #include #include +#include namespace cds { namespace container { @@ -67,8 +67,17 @@ namespace cds { namespace container { /// Enabled or disabled @ref bronson_avltree::relaxed_insert "relaxed insertion" static CDS_CONSTEXPR bool const c_bRelaxedInsert = traits::relaxed_insert; +# ifdef CDSDOXYGEN_INVOKED /// Returned pointer to \p mapped_type of extracted node - typedef std::unique_ptr< T, disposer > unique_ptr; + typedef cds::urcu::exempt_ptr< gc, T, T, disposer, void > exempt_ptr; +# else + typedef cds::urcu::exempt_ptr< gc, + typename std::remove_pointer::type, + typename std::remove_pointer::type, + disposer, + void + > exempt_ptr; +# endif typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock @@ -420,8 +429,8 @@ namespace cds { namespace container { /// Extracts an item with minimal key from the map /** - Returns \p std::unique_ptr to the leftmost item. - If the set is empty, returns empty \p std::unique_ptr. + Returns \p exempt_ptr to the leftmost item. + If the set is empty, returns empty \p exempt_ptr. @note Due the concurrent nature of the map, the function extracts nearly minimum key. It means that the function gets leftmost leaf of the tree and tries to unlink it. @@ -431,23 +440,17 @@ namespace cds { namespace container { RCU \p synchronize method can be called. RCU should NOT be locked. The function does not free the item. The deallocator will be implicitly invoked when the returned object is destroyed or when - its \p reset(nullptr) member function is called. + its \p release() member function is called. */ - unique_ptr extract_min() + exempt_ptr extract_min() { - unique_ptr pExtracted; - - do_extract_minmax( - left_child, - [&pExtracted]( mapped_type pVal, rcu_disposer& ) -> bool { pExtracted.reset( pVal ); return false; } - ); - return pExtracted; + return exempt_ptr(do_extract_min()); } /// Extracts an item with maximal key from the map /** - Returns \p std::unique_ptr pointer to the rightmost item. - If the set is empty, returns empty \p std::unique_ptr. + Returns \p exempt_ptr pointer to the rightmost item. + If the set is empty, returns empty \p exempt_ptr. @note Due the concurrent nature of the map, the function extracts nearly maximal key. It means that the function gets rightmost leaf of the tree and tries to unlink it. @@ -457,42 +460,28 @@ namespace cds { namespace container { RCU \p synchronize method can be called. RCU should NOT be locked. The function does not free the item. The deallocator will be implicitly invoked when the returned object is destroyed or when - its \p reset(nullptr) is called. - @note Before reusing \p result object you should call its \p release() method. + its \p release() is called. */ - unique_ptr extract_max() + exempt_ptr extract_max() { - unique_ptr pExtracted; - - do_extract_minmax( - right_child, - [&pExtracted]( mapped_type pVal, rcu_disposer& ) -> bool { pExtracted.reset( pVal ); return false; } - ); - return pExtracted; + return exempt_ptr(do_extract_max()); } /// Extracts an item from the map /** The function searches an item with key equal to \p key in the tree, - unlinks it, and returns \p std::unique_ptr pointer to a value found. - If \p key is not found the function returns an empty \p std::unique_ptr. + unlinks it, and returns \p exempt_ptr pointer to a value found. + If \p key is not found the function returns an empty \p exempt_ptr. RCU \p synchronize method can be called. RCU should NOT be locked. The function does not destroy the value found. The disposer will be implicitly invoked when the returned object is destroyed or when - its \p reset(nullptr) member function is called. + its \p release() member function is called. */ template - unique_ptr extract( Q const& key ) + exempt_ptr extract( Q const& key ) { - unique_ptr pExtracted; - - do_remove( - key, - key_comparator(), - [&pExtracted]( mapped_type pVal, rcu_disposer& ) -> bool { pExtracted.reset( pVal ); return false; } - ); - return pExtracted; + return exempt_ptr(do_extract( key )); } /// Extracts an item from the map using \p pred for searching @@ -503,17 +492,9 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the tree. */ template - unique_ptr extract_with( Q const& key, Less pred ) + exempt_ptr extract_with( Q const& key, Less pred ) { - CDS_UNUSED( pred ); - unique_ptr pExtracted; - - do_remove( - key, - cds::opt::details::make_comparator_from_less(), - [&pExtracted]( mapped_type pVal, rcu_disposer& ) -> bool { pExtracted.reset( pVal ); return false; } - ); - return pExtracted; + return exempt_ptr(do_extract_with( key, pred )); } /// Find the key \p key @@ -708,6 +689,26 @@ namespace cds { namespace container { } } + mapped_type do_extract_min() + { + mapped_type pExtracted = nullptr; + do_extract_minmax( + left_child, + [&pExtracted]( mapped_type pVal, rcu_disposer& ) -> bool { pExtracted = pVal; return false; } + ); + return pExtracted; + } + + mapped_type do_extract_max() + { + mapped_type pExtracted = nullptr; + do_extract_minmax( + right_child, + [&pExtracted]( mapped_type pVal, rcu_disposer& ) -> bool { pExtracted = pVal; return false; } + ); + return pExtracted; + } + template void do_extract_minmax( int nDir, Func func ) { @@ -717,7 +718,7 @@ namespace cds { namespace container { { rcu_lock l; - int result; + int result = update_flags::failed; do { // get right child of root node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire ); @@ -736,6 +737,31 @@ namespace cds { namespace container { } } + template + mapped_type do_extract( Q const& key ) + { + mapped_type pExtracted = nullptr; + do_remove( + key, + key_comparator(), + [&pExtracted]( mapped_type pVal, rcu_disposer& ) -> bool { pExtracted = pVal; return false; } + ); + return pExtracted; + } + + template + mapped_type do_extract_with( Q const& key, Less pred ) + { + CDS_UNUSED( pred ); + mapped_type pExtracted = nullptr; + do_remove( + key, + cds::opt::details::make_comparator_from_less(), + [&pExtracted]( mapped_type pVal, rcu_disposer& ) -> bool { pExtracted = pVal; return false; } + ); + return pExtracted; + } + //@endcond private: diff --git a/cds/urcu/exempt_ptr.h b/cds/urcu/exempt_ptr.h index e7d7942a..05e96eca 100644 --- a/cds/urcu/exempt_ptr.h +++ b/cds/urcu/exempt_ptr.h @@ -108,7 +108,7 @@ namespace cds { namespace urcu { /// The exempt pointer is not copy-constructible exempt_ptr( exempt_ptr const& ) = delete; - /// Releases the pointer + /// Releases the pointer, see \p release() ~exempt_ptr() { release(); -- 2.34.1