From 89c7ef78437282c134af800ea46aeaa7238019f8 Mon Sep 17 00:00:00 2001 From: khizmax Date: Thu, 5 Feb 2015 19:26:10 +0300 Subject: [PATCH] Bronson AVLtree impl --- cds/container/bronson_avltree_map_rcu.h | 57 ++- cds/container/details/bronson_avltree_base.h | 65 +-- cds/container/impl/bronson_avltree_map_rcu.h | 407 +++++++++++------- cds/sync/pool_monitor.h | 6 + projects/Win/vc12/hdr-test-tree.vcxproj | 12 +- tests/test-hdr/tree/hdr_bronson_avltree_map.h | 105 ++--- tests/unit/print_bronsonavltree_stat.h | 7 +- 7 files changed, 373 insertions(+), 286 deletions(-) diff --git a/cds/container/bronson_avltree_map_rcu.h b/cds/container/bronson_avltree_map_rcu.h index 5705bbd1..4532ee0a 100644 --- a/cds/container/bronson_avltree_map_rcu.h +++ b/cds/container/bronson_avltree_map_rcu.h @@ -10,7 +10,7 @@ namespace cds { namespace container { namespace bronson_avltree { //@cond namespace details { - template < typename Key, typename T, typename Traits> + template < class RCU, typename Key, typename T, typename Traits> struct make_map { typedef Key key_type; @@ -22,8 +22,7 @@ namespace cds { namespace container { struct traits : public original_traits { struct disposer { - template - void operator()( mapped_type * p ) + void operator()( mapped_type * p ) const { cxx_allocator().Delete( p ); } @@ -31,12 +30,7 @@ namespace cds { namespace container { }; // Metafunction result - typedef BronsonAVLTreeMap < - cds::urcu::gc, - Key, - T *, - traits - > type; + typedef BronsonAVLTreeMap< RCU, Key, T *, traits > type; }; } // namespace details //@endcond @@ -77,11 +71,11 @@ namespace cds { namespace container { #ifdef CDS_DOXYGEN_INVOKED : private BronsonAVLTreeMap< cds::urcu::gc, Key, T*, Traits > #else - : private bronson_avltree::details::make_map< Key, T, Traits >::type + : private bronson_avltree::details::make_map< cds::urcu::gc, Key, T, Traits >::type #endif { //@cond - typedef bronson_avltree::details::make_map< Key, T, Traits > maker; + typedef bronson_avltree::details::make_map< cds::urcu::gc, Key, T, Traits > maker; typedef typename maker::type base_class; //@endcond @@ -99,7 +93,7 @@ namespace cds { namespace container { typedef typename traits::stat stat; ///< internal statistics typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy typedef typename traits::back_off back_off; ///< Back-off strategy - typedef typename traits::lock_type lock_type; ///< Node lock type + typedef typename traits::sync_monitor sync_monitor; ///< @ref cds_sync_monitor "Synchronization monitor" type for node-level locking /// Enabled or disabled @ref bronson_avltree::relaxed_insert "relaxed insertion" static bool const c_bRelaxedInsert = traits::relaxed_insert; @@ -107,13 +101,15 @@ namespace cds { namespace container { /// 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_scoped_lock node_scoped_lock; typedef typename maker::cxx_allocator cxx_allocator; - using base_class::update_flags; + typedef typename base_class::update_flags update_flags; //@endcond public: @@ -144,10 +140,11 @@ namespace cds { namespace container { []( node_type * pNode ) -> mapped_type* { assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr ); + CDS_UNUSED( pNode ); return cxx_allocator().New(); }, - update_flags::allow_insert - ) == update_flags::result_insert; + static_cast(update_flags::allow_insert) + ) == static_cast(update_flags::result_inserted); } /// Inserts new node @@ -170,10 +167,11 @@ namespace cds { namespace container { [&val]( node_type * pNode ) { assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr ); + CDS_UNUSED( pNode ); return cxx_allocator().New( val ); }, - update_flags::allow_insert - ) == update_flags::result_insert; + static_cast(update_flags::allow_insert) + ) == static_cast(update_flags::result_inserted); } /// Inserts new node and initialize it by a functor @@ -182,7 +180,7 @@ namespace cds { namespace container { \p func functor with signature \code struct functor { - void operator()( mapped_type& item ); + void operator()( key_type const& key, mapped_type& item ); }; \endcode @@ -207,11 +205,11 @@ namespace cds { namespace container { { assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr ); mapped_type * pVal = cxx_allocator().New(); - func( *pVal ); + func( pNode->m_key, *pVal ); return pVal; }, - update_flags::allow_insert - ) == update_flags::result_insert; + static_cast(update_flags::allow_insert) + ) == static_cast(update_flags::result_inserted); } /// For key \p key inserts data of type \p mapped_type created in-place from \p args @@ -227,10 +225,11 @@ namespace cds { namespace container { [&]( node_type * pNode ) -> mapped_type* { assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr ); + CDS_UNUSED( pNode ); return cxx_allocator().New( std::forward(args)...); }, - update_flags::allow_insert - ) == update_flags::result_insert; + static_cast(update_flags::allow_insert) + ) == static_cast(update_flags::result_inserted); } /// Ensures that the \p key exists in the map @@ -244,7 +243,7 @@ namespace cds { namespace container { The functor \p Func may be a functor: \code struct my_functor { - void operator()( bool bNew, mapped_type& item ); + void operator()( bool bNew, key_type const& key, mapped_type& item ); }; \endcode @@ -266,18 +265,18 @@ namespace cds { namespace container { int result = base_class::do_update( key, key_comparator(), [&func]( node_type * pNode ) -> mapped_type* { - mapped_type * pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed )); + mapped_type * pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed ); if ( !pVal ) { pVal = cxx_allocator().New(); - func( true, *pVal ); + func( true, pNode->m_key, *pVal ); } else - func( false, *pVal ); + func( false, pNode->m_key, *pVal ); return pVal; }, update_flags::allow_insert | update_flags::allow_update ); - return std::make_pair( result != 0, (result & update_flags::result_insert) != 0 ); + return std::make_pair( result != 0, (result & update_flags::result_inserted) != 0 ); } /// Delete \p key from the map @@ -363,7 +362,7 @@ namespace cds { namespace container { /// Extracts an item with maximal key from the map /** - Returns \std::unique_ptr pointer to the rightmost item. + Returns \p std::unique_ptr pointer to the rightmost item. If the set is empty, returns empty \p std::unique_ptr. @note Due the concurrent nature of the map, the function extracts nearly maximal key. diff --git a/cds/container/details/bronson_avltree_base.h b/cds/container/details/bronson_avltree_base.h index 55c63d2c..faa127ea 100644 --- a/cds/container/details/bronson_avltree_base.h +++ b/cds/container/details/bronson_avltree_base.h @@ -18,11 +18,11 @@ namespace cds { namespace container { struct node; //@cond - template - struct link + template + struct link_node { - typedef node node_type; - typedef uint32_t version_type; + typedef Node node_type; + typedef uint32_t version_type; ///< version type (internal) enum { @@ -38,27 +38,25 @@ namespace cds { namespace container { atomics::atomic m_pLeft; ///< Left child atomics::atomic m_pRight; ///< Right child - node_type * m_pNextRemoved; ///< thread-local list o removed node - - link() + public: + //@cond + link_node() : m_nHeight( 0 ) , m_nVersion( 0 ) , m_pParent( nullptr ) , m_pLeft( nullptr ) , m_pRight( nullptr ) - , m_pNextRemoved( nullptr ) {} - link( int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight ) + link_node( int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight ) : m_nHeight( nHeight ) , m_nVersion( version ) , m_pParent( pParent ) , m_pLeft( pLeft ) , m_pRight( pRight ) - , m_pNextRemoved( nullptr ) {} - atomics::atomic& child( int nDirection ) const + atomics::atomic& child( int nDirection ) { assert( nDirection != 0 ); return nDirection < 0 ? m_pLeft : m_pRight; @@ -97,7 +95,7 @@ namespace cds { namespace container { void wait_until_shrink_completed( atomics::memory_order order ) const { BackOff bkoff; - while ( is_shrinking( order )) + while ( is_shrinking( order ) ) bkoff(); } @@ -110,31 +108,41 @@ namespace cds { namespace container { { return (m_nVersion.load( order ) & shrinking) != 0; } + //@endcond }; + //@endcond + // BronsonAVLTree internal node template - struct node : public link< Key, T > + struct node: public link_node< node> { - typedef Key key_type; - typedef T mapped_type; - typedef link< key_type, mapped_type > base_class; + typedef link_node< node> base_class; + + typedef Key key_type; ///< key type + typedef T mapped_type; ///< value type + typedef typename base_class::version_type version_type; - key_type const m_key; - atomics::atomic m_pValue; + key_type const m_key; ///< Key + atomics::atomic m_pValue; ///< Value + node * m_pNextRemoved; ///< thread-local list of removed node + public: + //@cond template node( Q&& key ) - : m_key( std::forward(key) ) + : base_class() + , m_key( std::forward( key ) ) , m_pValue( nullptr ) + , m_pNextRemoved( nullptr ) {} template - node( Q&& key, int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight ) + node( Q&& key, int nHeight, version_type version, node * pParent, node * pLeft, node * pRight ) : base_class( nHeight, version, pParent, pLeft, pRight ) , m_key( std::forward( key ) ) , m_pValue( nullptr ) + , m_pNextRemoved( nullptr ) {} - T * value( atomics::memory_order order ) const { return m_pValue.load( order ); @@ -144,8 +152,8 @@ namespace cds { namespace container { { return value( order ) != nullptr; } + //@endcond }; - //@endcond /// BronsonAVLTreeMap internal statistics template @@ -165,7 +173,7 @@ namespace cds { namespace container { event_counter m_nUpdateRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p update() call event_counter m_nUpdateSuccess; ///< Count of updating data node event_counter m_nUpdateUnlinked; ///< Count of updating of unlinked node attempts - event_counter m_nDisposedValue; ///< Count of disposed value + event_counter m_nDisposedNode; ///< Count of disposed node //@cond void onFindSuccess() { ++m_nFindSuccess ; } @@ -181,7 +189,7 @@ namespace cds { namespace container { void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; } void onUpdateSuccess() { ++m_nUpdateSuccess; } void onUpdateUnlinked() { ++m_nUpdateUnlinked; } - void onDisposeValue() { ++m_nDisposedValue; } + void onDisposeNode() { ++m_nDisposedNode; } //@endcond }; @@ -202,7 +210,7 @@ namespace cds { namespace container { void onUpdateRootWaitShrinking() const {} void onUpdateSuccess() const {} void onUpdateUnlinked() const {} - void onDisposeValue() const {} + void onDisposeNode() const {} //@endcond }; @@ -259,6 +267,9 @@ namespace cds { namespace container { /// Allocator for internal node typedef CDS_DEFAULT_ALLOCATOR node_allocator; + /// Allocator for node's value (not used in \p BronsonAVLTreeMap specialisation) + typedef CDS_DEFAULT_ALLOCATOR allocator; + /// Disposer (only for pointer-oriented tree specialization) /** The functor used for dispose removed values. @@ -322,6 +333,8 @@ namespace cds { namespace container { If the option is not specified, \p %opt::less is used. - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined. - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR. + - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR. + This option is not used in \p BronsonAVLTreeMap specialisation - \ref cds::intrusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values. The user-provided disposer is used only for pointer-oriented tree specialization like \p BronsonAVLTreeMap. When the node becomes the rounting node without value, @@ -329,7 +342,7 @@ namespace cds { namespace container { Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator. Due the nature of GC schema the disposer may be called asynchronously. - \p opt::sync_monitor - @ref cds_sync_monitor "synchronization monitor" type for node-level locking, - default is cds::sync::injecting_monitor + default is \p cds::sync::injecting_monitor - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default) @ref bronson_avltree::relaxed_insert "relaxed insertion" - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter) diff --git a/cds/container/impl/bronson_avltree_map_rcu.h b/cds/container/impl/bronson_avltree_map_rcu.h index ffbf2fd9..143152b1 100644 --- a/cds/container/impl/bronson_avltree_map_rcu.h +++ b/cds/container/impl/bronson_avltree_map_rcu.h @@ -69,11 +69,13 @@ namespace cds { namespace container { static CDS_CONSTEXPR bool const c_bRelaxedInsert = traits::relaxed_insert; /// Returned pointer to \p mapped_type of extracted node - typedef std::unique_ptr< mapped_type, disposer > unique_ptr; + typedef std::unique_ptr< T, disposer > unique_ptr; + + typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock protected: //@cond - typedef typename sync_monitor::node_injection< bronson_avltree::node< key_type, mapped_type >> node_type; + typedef typename sync_monitor::template node_injection< bronson_avltree::node< key_type, mapped_type >> node_type; typedef typename node_type::version_type version_type; typedef cds::details::Allocator< node_type, node_allocator_type > cxx_allocator; @@ -86,18 +88,20 @@ namespace cds { namespace container { retry }; - enum class update_flags + struct update_flags { - allow_insert = 1, - allow_update = 2, - allow_remove = 4, + enum { + allow_insert = 1, + allow_update = 2, + //allow_remove = 4, - retry = 1024, + retry = 1024, - failed = 0, - result_inserted = allow_insert, - result_updated = allow_update, - result_removed = allow_remove + failed = 0, + result_inserted = allow_insert, + result_updated = allow_update, + result_removed = 4 + }; }; enum node_condition @@ -124,6 +128,16 @@ namespace cds { namespace container { cxx_allocator().Delete( pNode ); } + static node_type * child( node_type * pNode, int nDir, atomics::memory_order order ) + { + return static_cast(pNode->child( nDir ).load( order )); + } + + static node_type * parent( node_type * pNode, atomics::memory_order order ) + { + return static_cast(pNode->m_pParent.load( order )); + } + // RCU safe disposer class rcu_disposer { @@ -141,7 +155,7 @@ namespace cds { namespace container { void dispose( node_type * pNode ) { - mapped_type * pVal = pNode->value( memory_model::memory_order_relaxed ); + mapped_type pVal = pNode->value( memory_model::memory_order_relaxed ); if ( pVal ) { pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed ); disposer()(pVal); @@ -165,7 +179,7 @@ namespace cds { namespace container { assert( !gc::is_locked() ); for ( node_type * p = m_pRetiredList; p; ) { - node_type * pNext = p->m_pNextRemoved; + node_type * pNext = static_cast( p->m_pNextRemoved ); // Value already disposed gc::template retire_ptr( p ); p = pNext; @@ -177,17 +191,17 @@ namespace cds { namespace container { protected: //@cond - typename node_type::base_class m_Root; - node_type * m_pRoot; - item_counter m_ItemCounter; - mutable sync_monitor m_Monitor; - mutable stat m_stat; + typename node_type::base_class m_Root; + node_type * m_pRoot; + item_counter m_ItemCounter; + mutable sync_monitor m_Monitor; + mutable stat m_stat; //@endcond public: /// Creates empty map BronsonAVLTreeMap() - : m_pRoot( static_cast(&m_Root) ) + : m_pRoot( static_cast( &m_Root )) {} /// Destroys the map @@ -205,15 +219,15 @@ namespace cds { namespace container { Returns \p true if inserting successful, \p false otherwise. */ template - bool insert( K const& key, mapped_type * pVal ) + bool insert( K const& key, mapped_type pVal ) { return do_update(key, key_comparator(), - [pVal]( node_type * pNode ) -> mapped_type* + [pVal]( node_type * pNode ) -> mapped_type { assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr ); return pVal; }, - update_flags::allow_insert + update_flags::allow_insert ) == update_flags::result_inserted; } @@ -234,10 +248,10 @@ namespace cds { namespace container { already is in the tree. */ template - std::pair update( K const& key, mapped_type * pVal, bool bInsert = true ) + std::pair update( K const& key, mapped_type pVal, bool bInsert = true ) { int result = do_update( key, key_comparator(), - [pVal]( node_type * ) -> mapped_type* + [pVal]( node_type * ) -> mapped_type { return pVal; }, @@ -255,12 +269,11 @@ namespace cds { namespace container { template bool erase( K const& key ) { - return do_update( - key, - key_comparator(), - []( mapped_type * pVal ) { disposer()(pVal); }, - update_flags::allow_remove - ) == update_flags::result_removed; + return do_remove( + key, + key_comparator(), + []( mapped_type pVal ) { disposer()(pVal); } + ); } /// Deletes the item from the map using \p pred predicate for searching @@ -274,12 +287,11 @@ namespace cds { namespace container { bool erase_with( K const& key, Less pred ) { CDS_UNUSED( pred ); - return do_update( + return do_remove( key, cds::details::predicate_wrapper(), - []( mapped_type * pVal ) { disposer()(pVal); }, - update_flags::allow_remove - ) == update_flags::result_removed; + []( mapped_type pVal ) { disposer()(pVal); } + ); } /// Delete \p key from the map @@ -301,12 +313,15 @@ namespace cds { namespace container { template bool erase( K const& key, Func f ) { - return do_update( + return do_remove( key, key_comparator(), - [&f]( mapped_type * pVal ) { f( *pVal ); disposer()(pVal); }, - update_flags::allow_remove - ) == update_flags::result_removed; + [&f]( mapped_type pVal ) { + assert( pVal ); + f( *pVal ); + disposer()(pVal); + } + ); } /// Deletes the item from the map using \p pred predicate for searching @@ -320,12 +335,15 @@ namespace cds { namespace container { bool erase_with( K const& key, Less pred, Func f ) { CDS_UNUSED( pred ); - return do_update( + return do_remove( key, cds::details::predicate_wrapper(), - [&f]( mapped_type * pVal ) { f( *pVal ); disposer()(pVal); }, - update_flags::allow_remove - ) == update_flags::result_removed; + [&f]( mapped_type pVal ) { + assert( pVal ); + f( *pVal ); + disposer()(pVal); + } + ); } /// Extracts an item with minimal key from the map @@ -346,6 +364,7 @@ namespace cds { namespace container { unique_ptr extract_min() { //TODO + return unique_ptr(); } /// Extracts an item with maximal key from the map @@ -367,6 +386,7 @@ namespace cds { namespace container { unique_ptr extract_max() { //TODO + return unique_ptr(); } /// Extracts an item from the map @@ -385,12 +405,11 @@ namespace cds { namespace container { { unique_ptr pExtracted; - do_update( + do_remove( key, key_comparator(), - [&pExtracted]( mapped_type * pVal ) { pExtracted.reset( pVal ); }, - update_flags::allow_remove - ); + [&pExtracted]( mapped_type pVal ) { pExtracted.reset( pVal ); } + ); return pExtracted; } @@ -407,12 +426,11 @@ namespace cds { namespace container { CDS_UNUSED( pred ); unique_ptr pExtracted; - do_update( + do_remove( key, cds::details::predicate_wrapper(), - [&pExtracted]( mapped_type * pVal ) { pExtracted.reset( pVal ); }, - update_flags::allow_remove - ); + [&pExtracted]( mapped_type pVal ) { pExtracted.reset( pVal ); } + ); return pExtracted; } @@ -422,7 +440,7 @@ 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& item ); }; \endcode where \p item is the item found. @@ -435,16 +453,18 @@ namespace cds { namespace container { template bool find( K const& key, Func f ) { - return do_find( key, key_comparator(), [&f]( sync_monitor& monitor, node_type * pNode ) -> bool { - assert( pNode != nullptr ); - node_scoped_lock l( monitor, *pNode ); - mapped_type * pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed ); - if ( pVal ) { - f( *pVal ); - return true; + return do_find( key, key_comparator(), + [&f]( sync_monitor& monitor, node_type * pNode ) -> bool { + assert( pNode != nullptr ); + node_scoped_lock l( monitor, *pNode ); + mapped_type pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed ); + if ( pVal ) { + f( pNode->m_key, *pVal ); + return true; + } + return false; } - return false; - }); + ); } /// Finds the key \p val using \p pred predicate for searching @@ -462,9 +482,9 @@ namespace cds { namespace container { [&f]( sync_monitor& monitor, node_type * pNode ) -> bool { assert( pNode != nullptr ); node_scoped_lock l( monitor, *pNode ); - mapped_type * pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed ); + mapped_type pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed ); if ( pVal ) { - f( *pVal ); + f( pNode->m_key, *pVal ); return true; } return false; @@ -482,7 +502,7 @@ namespace cds { namespace container { template bool find( K const& key ) { - return do_find( key, key_comparator(), []( node_type * ) -> bool { return true; }); + return do_find( key, key_comparator(), []( sync_monitor&, node_type * ) -> bool { return true; }); } /// Finds the key \p val using \p pred predicate for searching @@ -496,7 +516,7 @@ namespace cds { namespace container { bool find_with( K const& key, Less pred ) { CDS_UNUSED( pred ); - return do_find( key, opt::details::make_comparator_from_less(), []( node_type * ) -> bool { return true; } ); + return do_find( key, opt::details::make_comparator_from_less(), []( sync_monitor&, node_type * ) -> bool { return true; } ); } /// Clears the tree (thread safe, not atomic) @@ -516,11 +536,7 @@ namespace cds { namespace container { */ void clear() { - for ( ;; ) { - unique_ptr ep( extract_min() ); - if ( !ep ) - return; - } + while ( extract_min() ); } /// Clears the tree (not thread safe) @@ -592,7 +608,19 @@ namespace cds { namespace container { rcu_disposer removed_list; { rcu_lock l; - return try_udate_root( key, cmp, nFlags, funcUpdate, removed_list ); + return try_update_root( key, cmp, nFlags, funcUpdate, removed_list ); + } + } + + template + bool do_remove( K const& key, Compare cmp, Func func ) + { + check_deadlock_policy::check(); + + rcu_disposer removed_list; + { + rcu_lock l; + return try_remove_root( key, cmp, func, removed_list ); } } @@ -607,7 +635,7 @@ namespace cds { namespace container { assert( pNode ); while ( true ) { - node_type * pChild = pNode->child( nDir ).load( memory_model::memory_order_relaxed ); + node_type * pChild = child( pNode, nDir, memory_model::memory_order_relaxed ); if ( !pChild ) { if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) { m_stat.onFindRetry(); @@ -622,9 +650,9 @@ namespace cds { namespace container { if ( nCmp == 0 ) { if ( pChild->is_valued( memory_model::memory_order_relaxed ) ) { // key found - node_scoped_lock l( m_Monitor, pChild ); + node_scoped_lock l( m_Monitor, *pChild ); if ( pChild->is_valued( memory_model::memory_order_relaxed )) { - if ( f( *pChild ) ) { + if ( f( m_Monitor, pChild ) ) { m_stat.onFindSuccess(); return find_result::found; } @@ -660,14 +688,14 @@ namespace cds { namespace container { } template - int try_update_root( K const* key, Compare cmp, int nFlags, Func funcUpdate, rcu_disposer& disp ) + int try_update_root( K const& key, Compare cmp, int nFlags, Func funcUpdate, rcu_disposer& disp ) { assert( gc::is_locked() ); int result; do { // get right child of root - node_type * pChild = m_Root.child( 1, memory_model::memory_order_acquire ); + node_type * pChild = child( m_pRoot, 1, memory_model::memory_order_acquire ); if ( pChild ) { version_type nChildVersion = pChild->version( memory_model::memory_order_relaxed ); if ( nChildVersion & node_type::shrinking ) { @@ -675,7 +703,7 @@ namespace cds { namespace container { pChild->template wait_until_shrink_completed( memory_model::memory_order_relaxed ); result = update_flags::retry; } - else if ( pChild == m_Root.child( 1, memory_model::memory_order_acquire ) ) { + else if ( pChild == child( m_pRoot, 1, memory_model::memory_order_acquire )) { result = try_update( key, cmp, nFlags, funcUpdate, m_pRoot, pChild, nChildVersion, disp ); } } @@ -687,7 +715,7 @@ namespace cds { namespace container { node_scoped_lock l( m_Monitor, *m_pRoot ); node_type * pNew = alloc_node( key, 1, 0, m_pRoot, nullptr, nullptr ); - mapped_type * pVal = funcUpdate( pNew ); + mapped_type pVal = funcUpdate( pNew ); assert( pVal != nullptr ); pNew->m_pValue.store( pVal, memory_model::memory_order_release ); @@ -706,26 +734,51 @@ namespace cds { namespace container { return result; } + template + bool try_remove_root( K const& key, Compare cmp, Func func, rcu_disposer& disp ) + { + assert( gc::is_locked() ); + + int result; + do { + // get right child of root + node_type * pChild = child( m_pRoot, 1, memory_model::memory_order_acquire ); + if ( pChild ) { + version_type nChildVersion = pChild->version( memory_model::memory_order_relaxed ); + if ( nChildVersion & node_type::shrinking ) { + m_stat.onUpdateRootWaitShrinking(); + pChild->template wait_until_shrink_completed( memory_model::memory_order_relaxed ); + result = update_flags::retry; + } + else if ( pChild == child( m_pRoot, 1, memory_model::memory_order_acquire )) { + result = try_remove( key, cmp, func, m_pRoot, pChild, nChildVersion, disp ); + } + } + else + return false; + } while ( result == update_flags::retry ); + + return result == update_flags::result_removed; + } + template int try_update( K const& key, Compare cmp, int nFlags, Func funcUpdate, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp ) { assert( gc::is_locked() ); assert( nVersion != node_type::unlinked ); + CDS_UNUSED( pParent ); int nCmp = cmp( key, pNode->m_key ); if ( nCmp == 0 ) { if ( nFlags & update_flags::allow_update ) { return try_update_node( funcUpdate, pNode ); } - if ( nFlags & update_flags::allow_remove ) { - return try_remove_node( pParent, pNode, nVersion, funcUpdate, disp ); - } return update_flags::failed; } int result; do { - node_type * pChild = pNode->child( nCmp ).load( memory_model::memory_order_relaxed ); + node_type * pChild = child( pNode, nCmp, memory_model::memory_order_relaxed ); if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) return update_flags::retry; @@ -745,7 +798,7 @@ namespace cds { namespace container { pChild->template wait_until_shrink_completed( memory_model::memory_order_relaxed ); // retry } - else if ( pChild == pNode->child( nCmp ).load( memory_model::memory_order_relaxed ) ) { + else if ( pChild == child( pNode, nCmp, memory_model::memory_order_relaxed )) { // this second read is important, because it is protected by nChildVersion // validate the read that our caller took to get to node @@ -766,13 +819,62 @@ namespace cds { namespace container { return result; } + template + int try_remove( K const& key, Compare cmp, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp ) + { + assert( gc::is_locked() ); + assert( nVersion != node_type::unlinked ); + + int nCmp = cmp( key, pNode->m_key ); + if ( nCmp == 0 ) + return try_remove_node( pParent, pNode, nVersion, func, disp ); + + int result; + do { + node_type * pChild = child( pNode, nCmp, memory_model::memory_order_relaxed ); + if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) + return update_flags::retry; + + if ( pChild == nullptr ) { + return update_flags::failed; + } + else { + // update child + result = update_flags::retry; + version_type nChildVersion = pChild->version( memory_model::memory_order_acquire ); + if ( nChildVersion & node_type::shrinking ) { + m_stat.onUpdateWaitShrinking(); + pChild->template wait_until_shrink_completed( memory_model::memory_order_relaxed ); + // retry + } + else if ( pChild == child( pNode, nCmp, memory_model::memory_order_relaxed )) { + // this second read is important, because it is protected by nChildVersion + + // validate the read that our caller took to get to node + if ( pNode->version( memory_model::memory_order_relaxed ) != nVersion ) { + m_stat.onUpdateRetry(); + return update_flags::retry; + } + + // At this point we know that the traversal our parent took to get to node is still valid. + // The recursive implementation will validate the traversal from node to + // child, so just prior to the node nVersion validation both traversals were definitely okay. + // This means that we are no longer vulnerable to node shrinks, and we don't need + // to validate node version any more. + result = try_remove( key, cmp, func, pNode, pChild, nChildVersion, disp ); + } + } + } while ( result == update_flags::retry ); + return result; + } + template int try_insert_node( K const& key, Func funcUpdate, node_type * pNode, int nDir, version_type nVersion, rcu_disposer& disp ) { node_type * pNew; auto fnCreateNode = [&funcUpdate]( node_type * pNew ) { - mapped_type * pVal = funcUpdate( pNew ); + mapped_type pVal = funcUpdate( pNew ); assert( pVal != nullptr ); pNew->m_pValue.store( pVal, memory_model::memory_order_relaxed ); }; @@ -796,7 +898,7 @@ namespace cds { namespace container { if ( pNode->version( memory_model::memory_order_relaxed ) != nVersion || pNode->child( nDir ).load( memory_model::memory_order_relaxed ) != nullptr ) { - if ( c_RelaxedInsert ) { + if ( c_bRelaxedInsert ) { free_node( pNew ); m_stat.onRelaxedInsertFailed(); } @@ -821,7 +923,7 @@ namespace cds { namespace container { template int try_update_node( Func funcUpdate, node_type * pNode ) { - mapped_type * pOld; + mapped_type pOld; { assert( pNode != nullptr ); node_scoped_lock l( m_Monitor, *pNode ); @@ -832,14 +934,14 @@ namespace cds { namespace container { } pOld = pNode->value( memory_model::memory_order_relaxed ); - mapped_type * pVal = funcUpdate( *pNode ); + mapped_type pVal = funcUpdate( pNode ); assert( pVal != nullptr ); pNode->m_pValue.store( pVal, memory_model::memory_order_relaxed ); } if ( pOld ) { disposer()(pOld); - m_stat.onDisposeValue(); + m_stat.onDisposeNode(); } m_stat.onUpdateSuccess(); @@ -855,20 +957,20 @@ namespace cds { namespace container { if ( !pNode->is_valued( atomics::memory_order_relaxed ) ) return update_flags::failed; - if ( pNode->child( -1, atomics::memory_order_relaxed ) == nullptr - || pNode->child( 1, atomics::memory_order_relaxed ) == nullptr ) + if ( pNode->child( -1 ).load( atomics::memory_order_relaxed ) == nullptr + || pNode->child( 1 ).load( atomics::memory_order_relaxed ) == nullptr ) { node_type * pDamaged; - mapped_type * pOld; + mapped_type pOld; { node_scoped_lock lp( m_Monitor, *pParent ); - if ( pParent->is_unlinked( atomics::memory_order_relaxed ) || pNode->m_pParent.load( atomics::memory_order_relaxed ) != pParent ) + if ( pParent->is_unlinked( atomics::memory_order_relaxed ) || parent( pNode, memory_model::memory_order_relaxed ) != pParent ) return update_flags::retry; { node_scoped_lock ln( m_Monitor, *pNode ); - pOld = pNode->value( atomics::memory_order_relaxed ); - if ( pNode->version( atomics::memory_order_relaxed ) == nVersion + pOld = pNode->value( memory_model::memory_order_relaxed ); + if ( pNode->version( memory_model::memory_order_relaxed ) == nVersion && pOld && try_unlink_locked( pParent, pNode, disp ) ) { @@ -881,25 +983,26 @@ namespace cds { namespace container { } func( pOld ); // calls pOld disposer inside - m_stat.onDisposeValue(); + m_stat.onDisposeNode(); fix_height_and_rebalance( pDamaged, disp ); - return upfate_flags::result_removed; + return update_flags::result_removed; } else { int result = update_flags::retry; + mapped_type pOld; { node_scoped_lock ln( m_Monitor, *pNode ); - mapped_type * pOld = pNode->value( atomics::memory_order_relaxed ); + pOld = pNode->value( atomics::memory_order_relaxed ); if ( pNode->version( atomics::memory_order_relaxed ) == nVersion && pOld ) { pNode->m_pValue.store( nullptr, atomics::memory_order_relaxed ); - result = upfate_flags::result_removed; + result = update_flags::result_removed; } } - if ( result == upfate_flags::result_removed ) { - func( *pOld ); // calls pOld disposer inside - m_stat.onDisposeValue(); + if ( result == update_flags::result_removed ) { + func( pOld ); // calls pOld disposer inside + m_stat.onDisposeNode(); } return result; @@ -911,18 +1014,18 @@ namespace cds { namespace container { // pParent and pNode must be locked assert( !pParent->is_unlinked(memory_model::memory_order_relaxed) ); - node_type * pParentLeft = pParent->m_pLeft.load( memory_model::memory_order_relaxed ); - node_type * pParentRight = pParent->m_pRight.load( memory_model::memory_order_relaxed ); + node_type * pParentLeft = child( pParent, -1, memory_model::memory_order_relaxed ); + node_type * pParentRight = child( pParent, 1, memory_model::memory_order_relaxed ); if ( pNode != pParentLeft && pNode != pParentRight ) { // node is no longer a child of parent return false; } - assert( !pNode->is_unlinked()); - assert( pParent == pNode->m_pParent.load(memory_model::memory_order_relaxed)); + assert( !pNode->is_unlinked( memory_model::memory_order_relaxed ) ); + assert( pParent == parent( pNode, memory_model::memory_order_relaxed)); - node_type * pLeft = pNode->m_pLeft.load( memory_model::memory_order_relaxed ); - node_type * pRight = pNode->m_pRight.load( memory_model::memory_order_relaxed ); + node_type * pLeft = child( pNode, -1, memory_model::memory_order_relaxed ); + node_type * pRight = child( pNode, 1, memory_model::memory_order_relaxed ); if ( pLeft != nullptr && pRight != nullptr ) { // splicing is no longer possible return false; @@ -935,7 +1038,7 @@ namespace cds { namespace container { pParent->m_pRight.store( pSplice, memory_model::memory_order_relaxed ); if ( pSplice ) - pSplice->pParent.store( pParent, memory_model::memory_order_release ); + pSplice->m_pParent.store( pParent, memory_model::memory_order_release ); // Mark the node as unlinked pNode->version( node_type::unlinked, memory_model::memory_order_release ); @@ -950,8 +1053,8 @@ namespace cds { namespace container { //@cond int estimate_node_condition( node_type * pNode ) { - node_type * pLeft = pNode->m_pLeft.load( memory_model::memory_order_relaxed ); - node_type * pRight = pNode->m_pRight.load( memory_model::memory_order_relaxed ); + node_type * pLeft = child( pNode, -1, memory_model::memory_order_relaxed ); + node_type * pRight = child( pNode, 1, memory_model::memory_order_relaxed ); if ( (pLeft == nullptr || pRight == nullptr) && pNode->value( memory_model::memory_order_relaxed ) == nullptr ) return unlink_required; @@ -988,13 +1091,13 @@ namespace cds { namespace container { return nullptr; default: pNode->height( h, memory_model::memory_order_relaxed ); - return pNode->m_pParent.load( memory_model::memory_order_relaxed ); + return parent( pNode, memory_model::memory_order_relaxed ); } } void fix_height_and_rebalance( node_type * pNode, rcu_disposer& disp ) { - while ( pNode && pNode->m_pParent.load( memory_model::memory_order_relaxed ) ) { + while ( pNode && pNode->m_pParent.load( memory_model::memory_order_relaxed )) { int nCond = estimate_node_condition( pNode ); if ( nCond == nothing_required || pNode->is_unlinked( memory_model::memory_order_relaxed ) ) return; @@ -1002,12 +1105,12 @@ namespace cds { namespace container { if ( nCond != unlink_required && nCond != rebalance_required ) pNode = fix_height( pNode ); else { - node_type * pParent = pNode->m_pParent.load( memory_model::memry_order_relaxed ); + node_type * pParent = parent( pNode, memory_model::memory_order_relaxed ); assert( pParent != nullptr ); { node_scoped_lock lp( m_Monitor, *pParent ); if ( !pParent->is_unlinked( memory_model::memory_order_relaxed ) - && pNode->m_pParent.load( memory_model::memory_order_relaxed ) == pParent ) + && parent( pNode, memory_model::memory_order_relaxed ) == pParent ) { node_scoped_lock ln( m_Monitor, *pNode ); pNode = rebalance_locked( pParent, pNode, disp ); @@ -1021,12 +1124,12 @@ namespace cds { namespace container { { // pParent and pNode should be locked. // Returns a damaged node, or nullptr if no more rebalancing is necessary - assert( pNode->m_pParent.load( memory_model::memry_order_relaxed ) == pNode ); - assert( m_pParent->m_pLeft.load( memory_model::memory_order_relaxed ) == pNode - || m_pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode ); + assert( parent( pNode, memory_model::memory_order_relaxed ) == pParent ); + assert( child( pParent, -1, memory_model::memory_order_relaxed ) == pNode + || child( pParent, 1, memory_model::memory_order_relaxed ) == pNode ); - node_type * pLeft = pNode->m_pLeft.load( memory_model::memory_order_relaxed ); - node_type * pRight = pNode->m_pRight.load( memory_model::memory_order_relaxed ); + node_type * pLeft = child( pNode, -1, memory_model::memory_order_relaxed ); + node_type * pRight = child( pNode, 1, memory_model::memory_order_relaxed ); if ( (pLeft == nullptr || pRight == nullptr) && pNode->value( memory_model::memory_order_relaxed ) == nullptr ) { if ( try_unlink_locked( pParent, pNode, disp )) @@ -1059,9 +1162,9 @@ namespace cds { namespace container { node_type * rebalance_to_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR ) { - assert( pNode->m_pParent.load( memory_model::memry_order_relaxed ) == pNode ); - assert( m_pParent->m_pLeft.load( memory_model::memory_order_relaxed ) == pNode - || m_pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode ); + assert( parent( pNode, memory_model::memory_order_relaxed ) == pParent ); + assert( child( pParent, -1, memory_model::memory_order_relaxed ) == pNode + || child( pParent, 1, memory_model::memory_order_relaxed ) == pNode ); // pParent and pNode is locked yet // pNode->pLeft is too large, we will rotate-right. @@ -1077,9 +1180,9 @@ namespace cds { namespace container { if ( hL - hR <= 1 ) return pNode; // retry - node_type * pLRight = pLeft->m_pRight.load( memory_model::memory_order_relaxed ); + node_type * pLRight = child( pLeft, 1, memory_model::memory_order_relaxed ); int hLR = pLRight ? pLRight->height( memory_model::memory_order_relaxed ) : 0; - node_type * pLLeft = pLeft->m_pLeft.load( memory_model::memory_order_relaxed ); + node_type * pLLeft = child( pLeft, -1, memory_model::memory_order_relaxed ); int hLL = pLLeft ? pLLeft->height( memory_model::memory_order_relaxed ) : 0; if ( hLL > hLR ) { @@ -1097,7 +1200,7 @@ namespace cds { namespace container { if ( hLL > hLR ) return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR ); - node_type * pLRLeft = pLRight->m_pLeft.load( memory_model::memory_order_relaxed ); + node_type * pLRLeft = child( pLRight, -1, memory_model::memory_order_relaxed ); int hLRL = pLRLeft ? pLRLeft->height( memory_model::memory_order_relaxed ) : 0; int balance = hLL - hLRL; if ( balance >= -1 && balance <= 1 && !((hLL == 0 || hLRL == 0) && pLeft->value(memory_model::memory_order_relaxed) == nullptr) ) { @@ -1114,9 +1217,9 @@ namespace cds { namespace container { node_type * rebalance_to_left_locked( node_type * pParent, node_type * pNode, node_type * pRight, int hL ) { - assert( pNode->m_pParent.load( memory_model::memry_order_relaxed ) == pNode ); - assert( m_pParent->m_pLeft.load( memory_model::memory_order_relaxed ) == pNode - || m_pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode ); + assert( parent( pNode, memory_model::memory_order_relaxed ) == pParent ); + assert( child( pParent, -1, memory_model::memory_order_relaxed ) == pNode + || child( pParent, 1, memory_model::memory_order_relaxed ) == pNode ); // pParent and pNode is locked yet { @@ -1129,9 +1232,9 @@ namespace cds { namespace container { if ( hL - hR >= -1 ) return pNode; // retry - node_type * pRLeft = pRight->m_pLeft.load( memory_model::memory_order_relaxed ); - int hRL = pRLeft > pRLeft->height( memory_model::memory_order_relaxed ) : 0; - node_type * pRRight = pRight->m_pRight.load( memory_model::memory_order_relaxed ); + node_type * pRLeft = child( pRight, -1, memory_model::memory_order_relaxed ); + int hRL = pRLeft ? pRLeft->height( memory_model::memory_order_relaxed ) : 0; + node_type * pRRight = child( pRight, 1, memory_model::memory_order_relaxed ); int hRR = pRRight ? pRRight->height( memory_model::memory_order_relaxed ) : 0; if ( hRR > hRL ) return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR ); @@ -1146,10 +1249,10 @@ namespace cds { namespace container { if ( hRR >= hRL ) return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR ); - node_type * pRLRight = pRLeft->m_pRight.load( memory_model::memory_order_relaxed ); + node_type * pRLRight = child( pRLeft, 1, memory_model::memory_order_relaxed ); int hRLR = pRLRight ? pRLRight->height( memory_model::memory_order_relaxed ) : 0; int balance = hRR - hRLR; - if ( b >= -1 && b <= 1 && !((hRR == 0 || hRLR == 0) && pRight->value( memory_odel::memory_order_relaxed ) == nullptr) + if ( balance >= -1 && balance <= 1 && !((hRR == 0 || hRLR == 0) && pRight->value( memory_model::memory_order_relaxed ) == nullptr)) return rotate_left_over_right_locked( pParent, pNode, hL, pRight, pRLeft, hRR, hRLR ); } return rebalance_to_right_locked( pNode, pRight, pRLeft, hRR ); @@ -1169,7 +1272,7 @@ namespace cds { namespace container { node_type * rotate_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR, int hLL, node_type * pLRight, int hLR ) { version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed ); - node_type * pParentLeft = pParent->m_pLeft.load( memory_model::memory_order_relaxed ); + node_type * pParentLeft = child( pParent, -1, memory_model::memory_order_relaxed ); begin_change( pNode, nodeVersion ); @@ -1183,8 +1286,8 @@ namespace cds { namespace container { if ( pParentLeft == pNode ) pParent->m_pLeft.store( pLeft, memory_model::memory_order_relaxed ); else { - assert( pParent->m_pRight.load( memory_odel::memory_order_relaxed ) == pNode ); - pParent->m_pRight.store( pLeft, memory_mdel::memory_order_relaxed ); + assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode ); + pParent->m_pRight.store( pLeft, memory_model::memory_order_relaxed ); } pLeft->m_pParent.store( pParent, memory_model::memory_order_relaxed ); @@ -1231,12 +1334,12 @@ namespace cds { namespace container { node_type * rotate_left_locked( node_type * pParent, node_type * pNode, int hL, node_type * pRight, node_type * pRLeft, int hRL, int hRR ) { version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed ); - node_type * pParentLeft = pParent->m_pLeft.load( memory_odel::memory_order_relaxed ); + node_type * pParentLeft = child( pParent, -1, memory_model::memory_order_relaxed ); begin_change( pNode, nodeVersion ); // fix up pNode links, careful to be compatible with concurrent traversal for all but pNode - pNode->m_pRight.store( pRLeft, memory_nodel::memory_order_relaxed ); + pNode->m_pRight.store( pRLeft, memory_model::memory_order_relaxed ); if ( pRLeft != nullptr ) pRLeft->m_pParent.store( pNode, memory_model::memory_order_relaxed ); @@ -1246,8 +1349,8 @@ namespace cds { namespace container { if ( pParentLeft == pNode ) pParent->m_pLeft.store( pRight, memory_model::memory_order_relaxed ); else { - assert( pParent->m_pRight.load( memory_odel::memory_order_relaxed ) == pNode ); - pParent->m_pRight.store( pRight, memory_model::memory_model_relaxed ); + assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode ); + pParent->m_pRight.store( pRight, memory_model::memory_order_relaxed ); } pRight->m_pParent.store( pParent, memory_model::memory_order_relaxed ); @@ -1277,13 +1380,13 @@ namespace cds { namespace container { node_type * rotate_right_over_left_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR, int hLL, node_type * pLRight, int hLRL ) { - typename node_type::value_type nodeVersion = pNode->version( memory_model::memory_order_relaxed ); - typename node_type::value_type leftVersion = pLeft->version( memory_model::memory_order_relaxed ); + version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed ); + version_type leftVersion = pLeft->version( memory_model::memory_order_relaxed ); - node_type * pPL = pParent->m_pLeft.load( memory_model::memory_order_relaxed ); - node_type * pLRL = pLRight->m_pLeft.load( memory_model::memory_order_relaxed ); - node_type * pLRR = pLRight->m_pRight.load( memory_model::memory_order_relaxed ); - int hLRR = pLRR ? pLRR->hight( memory_model::memory_order_relaxed ) : 0; + node_type * pPL = child( pParent, -1, memory_model::memory_order_relaxed ); + node_type * pLRL = child( pLRight, -1, memory_model::memory_order_relaxed ); + node_type * pLRR = child( pLRight, 1, memory_model::memory_order_relaxed ); + int hLRR = pLRR ? pLRR->height( memory_model::memory_order_relaxed ) : 0; begin_change( pNode, nodeVersion ); begin_change( pLeft, leftVersion ); @@ -1305,7 +1408,7 @@ namespace cds { namespace container { if ( pPL == pNode ) pParent->m_pLeft.store( pLRight, memory_model::memory_order_relaxed ); else { - assert( Parent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode ); + assert( child( pParent, 1, memory_model::memory_order_relaxed ) == pNode ); pParent->m_pRight.store( pLRight, memory_model::memory_order_relaxed ); } pLRight->m_pParent.store( pParent, memory_model::memory_order_relaxed ); @@ -1345,9 +1448,9 @@ namespace cds { namespace container { } // we've already fixed the height at pLRight, do we need a rotation here? - final int balanceLR = hLeft - hNode; + int balanceLR = hLeft - hNode; if ( balanceLR < -1 || balanceLR > 1 ) - return pLR; + return pLRight; // try to fix the parent height while we've still got the lock return fix_height_locked( pParent ); @@ -1358,13 +1461,13 @@ namespace cds { namespace container { version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed ); version_type rightVersion = pRight->version( memory_model::memory_order_relaxed ); - node_type * pPL = pParent->m_pLeft.load( memory_model::memory_order_relaxed ); - node_type * pRLL = pRLeft->m_pLeft.load( memory_model::memory_order_relaxed ); - node_type * pRLR = pRLeft->m_pRight.load( memory_model::memory_order_relaxed ); + node_type * pPL = child( pParent, -1, memory_model::memory_order_relaxed ); + node_type * pRLL = child( pRLeft, -1, memory_model::memory_order_relaxed ); + node_type * pRLR = child( pRLeft, 1, memory_model::memory_order_relaxed ); int hRLL = pRLL ? pRLL->height( memory_model::memory_order_relaxed ) : 0; begin_change( pNode, nodeVersion ); - begin_change( pRight, ghtVersion ); + begin_change( pRight, rightVersion ); // fix up pNode links, careful about the order! pNode->m_pRight.store( pRLL, memory_model::memory_order_relaxed ); diff --git a/cds/sync/pool_monitor.h b/cds/sync/pool_monitor.h index 18190ad0..6e5fea63 100644 --- a/cds/sync/pool_monitor.h +++ b/cds/sync/pool_monitor.h @@ -63,6 +63,12 @@ namespace cds { namespace sync { : m_Access( 0 ) , m_pLock( nullptr ) {} + + ~injection() + { + assert( m_pLock == nullptr ); + assert( m_RefSpin.load( atomics::memory_order_relaxed ) == 0 ); + } }; //@endcond diff --git a/projects/Win/vc12/hdr-test-tree.vcxproj b/projects/Win/vc12/hdr-test-tree.vcxproj index ba868268..fee93a65 100644 --- a/projects/Win/vc12/hdr-test-tree.vcxproj +++ b/projects/Win/vc12/hdr-test-tree.vcxproj @@ -211,7 +211,7 @@ /bigobj /Zc:inline %(AdditionalOptions) Disabled $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\test-hdr;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0500;_SCL_SECURE=0;%(PreprocessorDefinitions) + WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0500;_SCL_SECURE=0;NOMINMAX;%(PreprocessorDefinitions) true EnableFastChecks MultiThreadedDebugDLL @@ -270,7 +270,7 @@ /bigobj /Zc:inline %(AdditionalOptions) Disabled $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\test-hdr;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0500;_SCL_SECURE=0;%(PreprocessorDefinitions) + WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0500;_SCL_SECURE=0;NOMINMAX;%(PreprocessorDefinitions) true EnableFastChecks MultiThreadedDebugDLL @@ -333,7 +333,7 @@ Speed false $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\test-hdr;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;NDEBUG;_CONSOLE;_WIN32_WINNT=0x0500;_SCL_SECURE=0;%(PreprocessorDefinitions) + WIN32;NDEBUG;_CONSOLE;NOMINMAX;_WIN32_WINNT=0x0500;_SCL_SECURE=0;%(PreprocessorDefinitions) true MultiThreadedDLL StreamingSIMDExtensions2 @@ -408,7 +408,7 @@ Speed false $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\test-hdr;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;NDEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + WIN32;NDEBUG;_CONSOLE;NOMINMAX;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) true MultiThreadedDLL @@ -480,7 +480,7 @@ /bigobj /Zc:inline %(AdditionalOptions) Disabled $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\test-hdr;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - CDS_USE_VLD;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0500;_SCL_SECURE=0;%(PreprocessorDefinitions) + CDS_USE_VLD;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0500;_SCL_SECURE=0;NOMINMAX;%(PreprocessorDefinitions) true EnableFastChecks MultiThreadedDebugDLL @@ -511,7 +511,7 @@ /bigobj /Zc:inline %(AdditionalOptions) Disabled $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\test-hdr;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - CDS_USE_VLD;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0500;_SCL_SECURE=0;%(PreprocessorDefinitions) + CDS_USE_VLD;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0500;_SCL_SECURE=0;NOMINMAX;%(PreprocessorDefinitions) true EnableFastChecks MultiThreadedDebugDLL diff --git a/tests/test-hdr/tree/hdr_bronson_avltree_map.h b/tests/test-hdr/tree/hdr_bronson_avltree_map.h index 199fd15f..4d6347ab 100644 --- a/tests/test-hdr/tree/hdr_bronson_avltree_map.h +++ b/tests/test-hdr/tree/hdr_bronson_avltree_map.h @@ -22,7 +22,6 @@ namespace tree { size_t nEnsureNewFuncCall; size_t nEraseFuncCall; size_t nFindFuncCall; - size_t nFindConstFuncCall; stat_data() : nInsertFuncCall( 0 ) @@ -30,7 +29,6 @@ namespace tree { , nEnsureNewFuncCall( 0 ) , nEraseFuncCall( 0 ) , nFindFuncCall( 0 ) - , nFindConstFuncCall( 0 ) {} }; @@ -110,15 +108,9 @@ namespace tree { struct find_functor { - template - void operator()( value_type& i, T& /*val*/ ) - { - ++i.stat.nFindFuncCall; - } - template - void operator()( value_type& i, T const& /*val*/ ) + void operator()( key_type, value_type& v ) const { - ++i.stat.nFindConstFuncCall; + ++v.stat.nFindFuncCall; } }; @@ -127,30 +119,29 @@ namespace tree { { Item m_found; - template - void operator()( Item& i, T& /*val*/ ) + void operator()( key_type const&, Item& v ) { - m_found = i; + m_found = v; } - void operator()( Item const& i ) + void operator()( Item& v ) { - m_found = i; + m_found = v; } }; struct insert_functor { template - void operator()( Item& i ) + void operator()( key_type key, Item& i ) { - i.nVal = i.nKey * 100; + i.nVal = key * 100; ++i.stat.nInsertFuncCall; } }; template - static void ensure_func( bool bNew, value_type& i, Q& /*val*/ ) + static void ensure_func( bool bNew, Q /*key*/, value_type& i ) { if ( bNew ) ++i.stat.nEnsureNewFuncCall; @@ -161,9 +152,9 @@ namespace tree { struct ensure_functor { template - void operator()( bool bNew, value_type& i, Q& val ) + void operator()( bool bNew, Q key, value_type& i ) { - ensure_func( bNew, i, val ); + ensure_func( bNew, key, i ); } }; @@ -171,10 +162,9 @@ namespace tree { { int nKey; - template - void operator()( Q&, value_type& v ) + void operator()( value_type& v ) { - nKey = v.nKey; + nKey = v.nVal; } }; @@ -196,58 +186,47 @@ namespace tree { CPPUNIT_ASSERT( !s.empty() ); CPPUNIT_ASSERT( check_size( s, 1 ) ); - CPPUNIT_ASSERT( !s.find_with( 20, less() ) ); - CPPUNIT_ASSERT( s.insert( std::make_pair( 20, 25 ) ) ); + CPPUNIT_ASSERT( !s.find_with( 20, std::less() ) ); + CPPUNIT_ASSERT( s.insert( 20, 25 ) ); CPPUNIT_ASSERT( !s.empty() ); CPPUNIT_ASSERT( check_size( s, 2 ) ); - CPPUNIT_ASSERT( s.find_with( 10, less() ) ); + CPPUNIT_ASSERT( s.find_with( 10, std::less() ) ); CPPUNIT_ASSERT( s.find( key = 20 ) ); - CPPUNIT_ASSERT( s.find_with( key, less(), find_functor() ) ); + CPPUNIT_ASSERT( s.find_with( key, std::less(), find_functor() ) ); { copy_found f; - f.m_found.nKey = 0; key = 20; CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) ); - CPPUNIT_ASSERT( f.m_found.nKey == 20 ); CPPUNIT_ASSERT( f.m_found.nVal == 25 ); CPPUNIT_ASSERT( f.m_found.stat.nFindFuncCall == 1 ); - CPPUNIT_ASSERT( f.m_found.stat.nFindConstFuncCall == 0 ); } CPPUNIT_ASSERT( s.find( key, find_functor() ) ); { copy_found f; - f.m_found.nKey = 0; key = 20; - CPPUNIT_ASSERT( s.find_with( key, less(), std::ref( f ) ) ); - CPPUNIT_ASSERT( f.m_found.nKey == 20 ); + CPPUNIT_ASSERT( s.find_with( key, std::less(), std::ref( f ) ) ); CPPUNIT_ASSERT( f.m_found.nVal == 25 ); CPPUNIT_ASSERT( f.m_found.stat.nFindFuncCall == 2 ); - CPPUNIT_ASSERT( f.m_found.stat.nFindConstFuncCall == 0 ); } CPPUNIT_ASSERT( s.find( 20, find_functor() ) ); { copy_found f; - f.m_found.nKey = 0; - CPPUNIT_ASSERT( s.find_with( 20, less(), std::ref( f ) ) ); - CPPUNIT_ASSERT( f.m_found.nKey == 20 ); + CPPUNIT_ASSERT( s.find_with( 20, std::less(), std::ref( f ) ) ); CPPUNIT_ASSERT( f.m_found.nVal == 25 ); - CPPUNIT_ASSERT( f.m_found.stat.nFindFuncCall == 2 ); - CPPUNIT_ASSERT( f.m_found.stat.nFindConstFuncCall == 1 ); + CPPUNIT_ASSERT( f.m_found.stat.nFindFuncCall == 3 ); } CPPUNIT_ASSERT( !s.empty() ); CPPUNIT_ASSERT( check_size( s, 2 ) ); CPPUNIT_ASSERT( !s.find( 25 ) ); - CPPUNIT_ASSERT( s.insert( std::make_pair( 25, -1 ), insert_functor() ) ); + CPPUNIT_ASSERT( s.insert_with( 25, insert_functor() ) ); CPPUNIT_ASSERT( !s.empty() ); CPPUNIT_ASSERT( check_size( s, 3 ) ); { copy_found f; - f.m_found.nKey = 0; key = 25; CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) ); - CPPUNIT_ASSERT( f.m_found.nKey == 25 ); CPPUNIT_ASSERT( f.m_found.nVal == 2500 ); CPPUNIT_ASSERT( f.m_found.stat.nInsertFuncCall == 1 ); } @@ -256,9 +235,7 @@ namespace tree { key = 10; { copy_found f; - f.m_found.nKey = 0; CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) ); - CPPUNIT_ASSERT( f.m_found.nKey == 10 ); CPPUNIT_ASSERT( f.m_found.nVal == 100 ); CPPUNIT_ASSERT( f.m_found.stat.nEnsureExistFuncCall == 0 ); CPPUNIT_ASSERT( f.m_found.stat.nEnsureNewFuncCall == 0 ); @@ -269,24 +246,24 @@ namespace tree { CPPUNIT_ASSERT( check_size( s, 3 ) ); { copy_found f; - f.m_found.nKey = 0; CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) ); - CPPUNIT_ASSERT( f.m_found.nKey == 10 ); CPPUNIT_ASSERT( f.m_found.nVal == 100 ); CPPUNIT_ASSERT( f.m_found.stat.nEnsureExistFuncCall == 1 ); CPPUNIT_ASSERT( f.m_found.stat.nEnsureNewFuncCall == 0 ); } - ensureResult = s.update( std::make_pair( 13, 1300 ), ensure_functor() ); + ensureResult = s.update( 13, []( bool /*bNew*/, key_type key, value_type& v ) + { + v.nVal = key * 100; + ++v.stat.nEnsureExistFuncCall; + }); CPPUNIT_ASSERT( ensureResult.first && ensureResult.second ); CPPUNIT_ASSERT( !s.empty() ); CPPUNIT_ASSERT( check_size( s, 4 ) ); { copy_found f; - f.m_found.nKey = 0; key = 13; CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) ); - CPPUNIT_ASSERT( f.m_found.nKey == 13 ); CPPUNIT_ASSERT( f.m_found.nVal == 1300 ); CPPUNIT_ASSERT( f.m_found.stat.nEnsureExistFuncCall == 0 ); CPPUNIT_ASSERT( f.m_found.stat.nEnsureNewFuncCall == 1 ); @@ -302,25 +279,22 @@ namespace tree { CPPUNIT_ASSERT( check_size( s, 3 ) ); CPPUNIT_ASSERT( s.find( 10 ) ); - CPPUNIT_ASSERT( s.erase_with( 10, less() ) ); + CPPUNIT_ASSERT( s.erase_with( 10, std::less() ) ); CPPUNIT_ASSERT( !s.find( 10 ) ); CPPUNIT_ASSERT( !s.empty() ); CPPUNIT_ASSERT( check_size( s, 2 ) ); - CPPUNIT_ASSERT( !s.erase_with( 10, less() ) ); + CPPUNIT_ASSERT( !s.erase_with( 10, std::less() ) ); CPPUNIT_ASSERT( !s.empty() ); CPPUNIT_ASSERT( check_size( s, 2 ) ); CPPUNIT_ASSERT( s.find( 20 ) ); { copy_found f; - f.m_found.nKey = 0; CPPUNIT_ASSERT( s.erase( 20, std::ref( f ) ) ); - CPPUNIT_ASSERT( f.m_found.nKey == 20 ); CPPUNIT_ASSERT( f.m_found.nVal == 25 ); - CPPUNIT_ASSERT( s.insert( 235 ) ) - CPPUNIT_ASSERT( s.erase_with( 235, less(), std::ref( f ) ) ); - CPPUNIT_ASSERT( f.m_found.nKey == 235 ); + CPPUNIT_ASSERT( s.insert( 235, 2350 ) ); + CPPUNIT_ASSERT( s.erase_with( 235, std::less(), std::ref( f ) ) ); CPPUNIT_ASSERT( f.m_found.nVal == 2350 ); } CPPUNIT_ASSERT( !s.find( 20 ) ); @@ -332,33 +306,24 @@ namespace tree { CPPUNIT_ASSERT( check_size( s, 0 ) ); // emplace test - CPPUNIT_ASSERT( s.emplace( 151 ) ); // key = 151, val = 1510 + CPPUNIT_ASSERT( s.emplace( 151 ) ); // key = 151, val=0 CPPUNIT_ASSERT( s.emplace( 174, 471 ) ); // key = 174, val = 471 - CPPUNIT_ASSERT( s.emplace( std::make_pair( 190, 91 ) ) ); // key == 190, val = 91 CPPUNIT_ASSERT( !s.empty() ); - CPPUNIT_ASSERT( check_size( s, 3 ) ); + CPPUNIT_ASSERT( check_size( s, 2 ) ); CPPUNIT_ASSERT( s.find( 151 ) ); - CPPUNIT_ASSERT( s.find_with( 174, less() ) ); - CPPUNIT_ASSERT( s.find( 190 ) ); + CPPUNIT_ASSERT( s.find_with( 174, std::less() ) ); + CPPUNIT_ASSERT( !s.find( 190 ) ); { copy_found f; - f.m_found.nKey = 0; key = 151; CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) ); - CPPUNIT_ASSERT( f.m_found.nKey == 151 ); - CPPUNIT_ASSERT( f.m_found.nVal == 1510 ); + CPPUNIT_ASSERT( f.m_found.nVal == 0 ); key = 174; CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) ); - CPPUNIT_ASSERT( f.m_found.nKey == 174 ); CPPUNIT_ASSERT( f.m_found.nVal == 471 ); - - key = 190; - CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) ); - CPPUNIT_ASSERT( f.m_found.nKey == 190 ); - CPPUNIT_ASSERT( f.m_found.nVal == 91 ); } s.clear(); diff --git a/tests/unit/print_bronsonavltree_stat.h b/tests/unit/print_bronsonavltree_stat.h index a8cdd121..5a489e60 100644 --- a/tests/unit/print_bronsonavltree_stat.h +++ b/tests/unit/print_bronsonavltree_stat.h @@ -6,6 +6,7 @@ #include namespace std { + static inline ostream& operator <<( ostream& o, cds::container::bronson_avltree::empty_stat const& /*s*/ ) { return o; @@ -23,11 +24,11 @@ namespace std { << "\t\t m_nInsertRetry: " << s.m_nInsertRetry.get() << "\n" << "\t\t m_nUpdateWaitShrinking: " << s.m_nUpdateWaitShrinking.get() << "\n" << "\t\t m_nUpdateRetry: " << s.m_nUpdateRetry.get() << "\n" - << "\t\t m_nUpdateRootWaitShinking: " << s.m_nUpdateRootWaitShinking.get() << "\n" + << "\t\tm_nUpdateRootWaitShrinking: " << s.m_nUpdateRootWaitShrinking.get() << "\n" << "\t\t m_nUpdateSuccess: " << s.m_nUpdateSuccess.get() << "\n" << "\t\t m_nUpdateUnlinked: " << s.m_nUpdateUnlinked.get() << "\n" - << "\t\t m_nDisposedValue: " << s.m_nDisposedValue.get() << "\n"; + << "\t\t m_nDisposedNode: " << s.m_nDisposedNode.get() << "\n"; } -} +} //namespace std #endif // #ifndef CDSUNIT_PRINT_ELLENBINTREE_STAT_H -- 2.34.1