From 22fe7a8f0951a8672b2858de5d2a5827e62d8643 Mon Sep 17 00:00:00 2001 From: khizmax Date: Sun, 22 Feb 2015 21:57:34 +0300 Subject: [PATCH] Bronson AVL-tree: added check_consistency function --- cds/container/bronson_avltree_map_rcu.h | 23 ++++++++ cds/container/impl/bronson_avltree_map_rcu.h | 55 ++++++++++++++++++- tests/test-hdr/tree/hdr_bronson_avltree_map.h | 18 ++++++ 3 files changed, 95 insertions(+), 1 deletion(-) diff --git a/cds/container/bronson_avltree_map_rcu.h b/cds/container/bronson_avltree_map_rcu.h index f606ced0..532877ef 100644 --- a/cds/container/bronson_avltree_map_rcu.h +++ b/cds/container/bronson_avltree_map_rcu.h @@ -613,6 +613,29 @@ namespace cds { namespace container { { return base_class::check_consistency(); } + + /// Checks internal consistency (not atomic, not thread-safe) + /** + The debugging function to check internal consistency of the tree. + The functor \p Func is called if a violation of internal tree structure + is found: + \code + struct functor { + void operator()( size_t nLevel, size_t hLeft, size_t hRight ); + }; + \endcode + where + - \p nLevel - the level where the violation is found + - \p hLeft - the height of left subtree + - \p hRight - the height of right subtree + + The functor is called for each violation found. + */ + template + bool check_consistency( Func f ) const + { + return base_class::check_consistency( f ); + } }; }} // namespace cds::container diff --git a/cds/container/impl/bronson_avltree_map_rcu.h b/cds/container/impl/bronson_avltree_map_rcu.h index 50091ae1..5456b9e5 100644 --- a/cds/container/impl/bronson_avltree_map_rcu.h +++ b/cds/container/impl/bronson_avltree_map_rcu.h @@ -696,12 +696,65 @@ namespace cds { namespace container { */ bool check_consistency() const { - //TODO + return check_consistency([]( size_t /*nLevel*/, size_t /*hLeft*/, size_t /*hRight*/ ){} ); + } + + /// Checks internal consistency (not atomic, not thread-safe) + /** + The debugging function to check internal consistency of the tree. + The functor \p Func is called if a violation of internal tree structure + is found: + \code + struct functor { + void operator()( size_t nLevel, size_t hLeft, size_t hRight ); + }; + \endcode + where + - \p nLevel - the level where the violation is found + - \p hLeft - the height of left subtree + - \p hRight - the height of right subtree + + The functor is called for each violation found. + */ + template + bool check_consistency( Func f ) const + { + node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_relaxed ); + if ( pChild ) { + size_t nErrors = 0; + do_check_consistency( pChild, 1, f, nErrors ); + return nErrors == 0; + } return true; } protected: //@cond + template + size_t do_check_consistency( node_type * pNode, size_t nLevel, Func f, size_t& nErrors ) const + { + if ( pNode ) { + size_t hLeft = do_check_consistency( child( pNode, left_child, memory_model::memory_order_relaxed ), nLevel + 1, f, nErrors ); + size_t hRight = do_check_consistency( child( pNode, right_child, memory_model::memory_order_relaxed ), nLevel + 1, f, nErrors ); + + if ( hLeft >= hRight ) { + if ( hLeft - hRight > 1 ) { + f( nLevel, hLeft, hRight ); + ++nErrors; + } + return hLeft; + } + else { + if ( hRight - hLeft > 1 ) { + f( nLevel, hLeft, hRight ); + ++nErrors; + } + return hRight; + } + } + return 0; + } + template bool do_find( Q& key, Compare cmp, Func f ) const { diff --git a/tests/test-hdr/tree/hdr_bronson_avltree_map.h b/tests/test-hdr/tree/hdr_bronson_avltree_map.h index 6054555d..04f6ac7b 100644 --- a/tests/test-hdr/tree/hdr_bronson_avltree_map.h +++ b/tests/test-hdr/tree/hdr_bronson_avltree_map.h @@ -85,6 +85,7 @@ namespace tree { protected: static const size_t c_nItemCount = 10000; + /* class data_array { int * pFirst; @@ -113,6 +114,7 @@ namespace tree { return pFirst[i]; } }; + */ struct find_functor { @@ -167,6 +169,14 @@ namespace tree { } }; + struct check_functor + { + void operator()( size_t nLevel, size_t hLeft, size_t hRight ) + { + CPPUNIT_MSG("Consistency violation: level=" << nLevel << ", hLeft=" << hLeft << ", hRight=" << hRight ); + } + }; + protected: template void test_with( Set& s ) @@ -344,6 +354,7 @@ namespace tree { // extract_min for ( int i = 0; i < sizeof(keys) / sizeof(keys[0]); ++i ) CPPUNIT_ASSERT( s.emplace( keys[i], keys[i] * c_nStep )); + CPPUNIT_CHECK( s.check_consistency( check_functor() )); xp = s.extract_min(); CPPUNIT_ASSERT( xp ); @@ -361,6 +372,7 @@ namespace tree { // extract_min for ( int i = 0; i < sizeof(keys) / sizeof(keys[0]); ++i ) CPPUNIT_ASSERT( s.insert( keys[i], keys[i] * c_nStep )); + CPPUNIT_CHECK( s.check_consistency( check_functor() )); nCount = 1; xp = s.extract_min( [&keyPrev]( key_type k ){ keyPrev = k; }); @@ -382,6 +394,7 @@ namespace tree { // extract_min_key for ( int i = 0; i < sizeof(keys) / sizeof(keys[0]); ++i ) CPPUNIT_ASSERT( s.insert( keys[i], keys[i] * c_nStep )); + CPPUNIT_CHECK( s.check_consistency( check_functor() )); nCount = 1; xp = s.extract_min_key( keyPrev ); @@ -403,6 +416,7 @@ namespace tree { // extract_max for ( int i = 0; i < sizeof(keys) / sizeof(keys[0]); ++i ) CPPUNIT_ASSERT( s.emplace( keys[i], keys[i] * c_nStep )); + CPPUNIT_CHECK( s.check_consistency( check_functor() )); nCount = 1; xp = s.extract_max(); @@ -422,6 +436,7 @@ namespace tree { // extract_max for ( int i = 0; i < sizeof(keys) / sizeof(keys[0]); ++i ) CPPUNIT_ASSERT( s.emplace( keys[i], keys[i] * c_nStep )); + CPPUNIT_CHECK( s.check_consistency( check_functor() )); nCount = 1; xp = s.extract_max( [&keyPrev]( key_type k ){ keyPrev = k; }); @@ -445,6 +460,7 @@ namespace tree { // extract_max_key for ( int i = 0; i < sizeof(keys) / sizeof(keys[0]); ++i ) CPPUNIT_ASSERT( s.emplace( keys[i], keys[i] * c_nStep )); + CPPUNIT_CHECK( s.check_consistency( check_functor() )); nCount = 1; xp = s.extract_max_key( keyPrev ); @@ -468,6 +484,7 @@ namespace tree { // extract for ( int i = 0; i < sizeof(keys) / sizeof(keys[0]); ++i ) CPPUNIT_ASSERT( s.emplace( keys[i], keys[i] * c_nStep )); + CPPUNIT_CHECK( s.check_consistency( check_functor() )); for ( int i = 0; i < sizeof( keys ) / sizeof( keys[0] ); ++i ) { xp = s.extract(keys[i]); @@ -479,6 +496,7 @@ namespace tree { // extract_with for ( int i = 0; i < sizeof(keys) / sizeof(keys[0]); ++i ) CPPUNIT_ASSERT( s.emplace( keys[i], keys[i] * c_nStep )); + CPPUNIT_CHECK( s.check_consistency( check_functor() )); for ( int i = 0; i < sizeof( keys ) / sizeof( keys[0] ); ++i ) { xp = s.extract_with( wrapped_int(keys[i]), wrapped_less()); -- 2.34.1