From 319c5ae4f25d496470289648839e29838a6fd0d9 Mon Sep 17 00:00:00 2001 From: khizmax Date: Fri, 20 Mar 2015 00:30:01 +0300 Subject: [PATCH] Improved checking of internal consistency for BronsonAVLTree --- cds/container/impl/bronson_avltree_map_rcu.h | 12 ++++++++++-- tests/unit/map2/map_types.h | 3 ++- 2 files changed, 12 insertions(+), 3 deletions(-) diff --git a/cds/container/impl/bronson_avltree_map_rcu.h b/cds/container/impl/bronson_avltree_map_rcu.h index 0439e7df..775f6319 100644 --- a/cds/container/impl/bronson_avltree_map_rcu.h +++ b/cds/container/impl/bronson_avltree_map_rcu.h @@ -762,8 +762,16 @@ namespace cds { namespace container { 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 ); + key_comparator cmp; + node_type * pLeft = child( pNode, left_child, memory_model::memory_order_relaxed ); + node_type * pRight = child( pNode, right_child, memory_model::memory_order_relaxed ); + if ( pLeft && cmp( pLeft->m_key, pNode->m_key ) > 0 ) + ++nErrors; + if ( pRight && cmp( pNode->m_key, pRight->m_key ) > 0 ) + ++nErrors; + + size_t hLeft = do_check_consistency( pLeft, nLevel + 1, f, nErrors ); + size_t hRight = do_check_consistency( pRight, nLevel + 1, f, nErrors ); if ( hLeft >= hRight ) { if ( hLeft - hRight > 1 ) { diff --git a/tests/unit/map2/map_types.h b/tests/unit/map2/map_types.h index 4417b028..e898f82c 100644 --- a/tests/unit/map2/map_types.h +++ b/tests/unit/map2/map_types.h @@ -1938,10 +1938,11 @@ namespace map2 { static inline void check_before_cleanup( cc::BronsonAVLTreeMap& m ) { CPPUNIT_MSG( " Check internal consistency (single-threaded)..." ); - m.check_consistency([]( size_t nLevel, size_t hLeft, size_t hRight ) + bool bOk = m.check_consistency([]( size_t nLevel, size_t hLeft, size_t hRight ) { CPPUNIT_MSG( "Tree violation on level=" << nLevel << ": hLeft=" << hLeft << ", hRight=" << hRight ) }); + CPPUNIT_CHECK_CURRENT_EX( bOk, "check_consistency failed"); } template -- 2.34.1