From b1f6d4198129f6dde6e51e8df0ea21b2953a027b Mon Sep 17 00:00:00 2001 From: khizmax Date: Sat, 7 Feb 2015 18:58:59 +0300 Subject: [PATCH] Bronson's AVL-tree: add extract_min/max --- cds/container/details/bronson_avltree_base.h | 10 +- cds/container/impl/bronson_avltree_map_rcu.h | 107 +++++++++++++++++-- tests/unit/print_bronsonavltree_stat.h | 3 + 3 files changed, 110 insertions(+), 10 deletions(-) diff --git a/cds/container/details/bronson_avltree_base.h b/cds/container/details/bronson_avltree_base.h index bbb15e7a..4d64ce65 100644 --- a/cds/container/details/bronson_avltree_base.h +++ b/cds/container/details/bronson_avltree_base.h @@ -172,7 +172,7 @@ namespace cds { namespace container { event_counter m_nInsertSuccess; ///< Count of inserting data node event_counter m_nRelaxedInsertFailed; ///< Count of false creating of data nodes (only if @ref bronson_avltree::relaxed_insert "relaxed insertion" is enabled) event_counter m_nInsertRetry; ///< Count of insert retries via concurrent operations - event_counter m_nUpdateWaitShrinking; ///< Count of waiting until shrinking completed duting \p update() call + event_counter m_nUpdateWaitShrinking; ///< Count of waiting until shrinking completed during \p update() call event_counter m_nUpdateRetry; ///< Count of update retries via concurrent operations event_counter m_nUpdateRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p update() call event_counter m_nUpdateSuccess; ///< Count of updating data node @@ -180,6 +180,9 @@ namespace cds { namespace container { event_counter m_nDisposedNode; ///< Count of disposed node event_counter m_nDisposedValue; ///< Count of disposed value event_counter m_nExtractedValue; ///< Count of extracted value + event_counter m_nRemoveRetry; ///< Count o erase/extract retries + event_counter m_nRemoveWaitShrinking; ///< ount of waiting until shrinking completed during \p erase() or \p extract() call + event_counter m_nRemoveRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p erase() or \p extract() call event_counter m_nRightRotation; ///< Count of single right rotation event_counter m_nLeftRotation; ///< Count of single left rotation @@ -203,6 +206,8 @@ namespace cds { namespace container { void onDisposeNode() { ++m_nDisposedNode; } void onDisposeValue() { ++m_nDisposedValue; } void onExtractValue() { ++m_nExtractedValue; } + void onRemoveRetry() { ++m_nRemoveRetry; } + void onRemoveWaitShrinking() { ++m_nRemoveWaitShrinking; } void onRotateRight() { ++m_nRightRotation; } void onRotateLeft() { ++m_nLeftRotation; } @@ -230,6 +235,9 @@ namespace cds { namespace container { void onDisposeNode() const {} void onDisposeValue() const {} void onExtractValue() const {} + void onRemoveRetry() const {} + void onRemoveWaitShrinking() const {} + void onRemoveRootWaitShrinking() const {} void onRotateRight() const {} void onRotateLeft() const {} diff --git a/cds/container/impl/bronson_avltree_map_rcu.h b/cds/container/impl/bronson_avltree_map_rcu.h index ebcb83a2..5db8ec47 100644 --- a/cds/container/impl/bronson_avltree_map_rcu.h +++ b/cds/container/impl/bronson_avltree_map_rcu.h @@ -368,8 +368,13 @@ namespace cds { namespace container { */ unique_ptr extract_min() { - //TODO - return unique_ptr(); + unique_ptr pExtracted; + + do_extract_minmax( + left_child, + [&pExtracted]( mapped_type pVal ) -> bool { pExtracted.reset( pVal ); return false; } + ); + return pExtracted; } /// Extracts an item with maximal key from the map @@ -390,8 +395,13 @@ namespace cds { namespace container { */ unique_ptr extract_max() { - //TODO - return unique_ptr(); + unique_ptr pExtracted; + + do_extract_minmax( + right_child, + [&pExtracted]( mapped_type pVal ) -> bool { pExtracted.reset( pVal ); return false; } + ); + return pExtracted; } /// Extracts an item from the map @@ -630,6 +640,34 @@ namespace cds { namespace container { } } + template + void do_extract_minmax( int nDir, Func func ) + { + check_deadlock_policy::check(); + + rcu_disposer removed_list; + { + rcu_lock l; + + int result; + do { + // get right child of root + node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire ); + if ( pChild ) { + version_type nChildVersion = pChild->version( memory_model::memory_order_relaxed ); + if ( nChildVersion & node_type::shrinking ) { + m_stat.onRemoveRootWaitShrinking(); + pChild->template wait_until_shrink_completed( memory_model::memory_order_relaxed ); + result = update_flags::retry; + } + else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) { + result = try_extract_minmax( nDir, func, m_pRoot, pChild, nChildVersion, removed_list ); + } + } + } while ( result == update_flags::retry ); + } + } + //@endcond private: @@ -756,7 +794,7 @@ namespace cds { namespace container { if ( pChild ) { version_type nChildVersion = pChild->version( memory_model::memory_order_relaxed ); if ( nChildVersion & node_type::shrinking ) { - m_stat.onUpdateRootWaitShrinking(); + m_stat.onRemoveRootWaitShrinking(); pChild->template wait_until_shrink_completed( memory_model::memory_order_relaxed ); result = update_flags::retry; } @@ -789,8 +827,10 @@ namespace cds { namespace container { int result; do { node_type * pChild = child( pNode, nCmp, memory_model::memory_order_relaxed ); - if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) + if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) { + m_stat.onUpdateRetry(); return update_flags::retry; + } if ( pChild == nullptr ) { // insert new node @@ -842,8 +882,10 @@ namespace cds { namespace container { int result; do { node_type * pChild = child( pNode, nCmp, memory_model::memory_order_relaxed ); - if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) + if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) { + m_stat.onRemoveRetry(); return update_flags::retry; + } if ( pChild == nullptr ) { return update_flags::failed; @@ -853,7 +895,7 @@ namespace cds { namespace container { result = update_flags::retry; version_type nChildVersion = pChild->version( memory_model::memory_order_acquire ); if ( nChildVersion & node_type::shrinking ) { - m_stat.onUpdateWaitShrinking(); + m_stat.onRemoveWaitShrinking(); pChild->template wait_until_shrink_completed( memory_model::memory_order_relaxed ); // retry } @@ -862,7 +904,7 @@ namespace cds { namespace container { // validate the read that our caller took to get to node if ( pNode->version( memory_model::memory_order_relaxed ) != nVersion ) { - m_stat.onUpdateRetry(); + m_stat.onRemoveRetry(); return update_flags::retry; } @@ -878,6 +920,53 @@ namespace cds { namespace container { return result; } + template + int try_extract_minmax( int nDir, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp ) + { + assert( gc::is_locked() ); + assert( nVersion != node_type::unlinked ); + + int result; + do { + node_type * pChild = child( pNode, nDir, memory_model::memory_order_relaxed ); + if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) { + m_stat.onRemoveRetry(); + return update_flags::retry; + } + + if ( pChild == nullptr ) { + // Found min/max + return try_remove_node( pParent, pNode, nVersion, func, disp ); + } + else { + result = update_flags::retry; + version_type nChildVersion = pChild->version( memory_model::memory_order_acquire ); + if ( nChildVersion & node_type::shrinking ) { + m_stat.onRemoveWaitShrinking(); + pChild->template wait_until_shrink_completed( memory_model::memory_order_relaxed ); + // retry + } + else if ( pChild == child( pNode, nDir, 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.onRemoveRetry(); + 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_extract_minmax( nDir, 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 ) { diff --git a/tests/unit/print_bronsonavltree_stat.h b/tests/unit/print_bronsonavltree_stat.h index 1da6f6e1..e34c491d 100644 --- a/tests/unit/print_bronsonavltree_stat.h +++ b/tests/unit/print_bronsonavltree_stat.h @@ -27,6 +27,9 @@ namespace std { << "\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_nRemoveRetry: " << s.m_nRemoveRetry.get() << "\n" + << "\t\t m_nRemoveWaitShrinking: " << s.m_nRemoveWaitShrinking.get() << "\n" + << "\t\tm_nRemoveRootWaitShrinking: " << s.m_nRemoveRootWaitShrinking.get() << "\n" << "\t\t m_nDisposedValue: " << s.m_nDisposedValue.get() << "\n" << "\t\t m_nDisposedNode: " << s.m_nDisposedNode.get() << "\n" << "\t\t m_nExtractedValue: " << s.m_nExtractedValue.get() << "\n" -- 2.34.1