From e17103319485dd2bceae63a19a8383f0691f8177 Mon Sep 17 00:00:00 2001 From: khizmax Date: Wed, 4 Feb 2015 23:44:42 +0300 Subject: [PATCH] Bronson AVL-tree impl --- cds/container/bronson_avltree_map_rcu.h | 7 +- cds/container/details/bronson_avltree_base.h | 8 +- cds/container/impl/bronson_avltree_map_rcu.h | 6 +- cds/sync/monitor.h | 4 +- cds/sync/pool_monitor.h | 4 +- projects/Win/vc12/cds.sln | 3 +- projects/Win/vc12/hdr-test-tree.vcxproj | 2 + .../Win/vc12/hdr-test-tree.vcxproj.filters | 6 + projects/source.test-hdr.mk | 1 + tests/test-hdr/tree/hdr_bronson_avltree_map.h | 421 ++++++++++++++++++ .../tree/hdr_bronson_avltree_map_rcu_gpb.cpp | 36 ++ .../tree/hdr_ellenbintree_map_rcu_gpb.cpp | 1 - tests/test-hdr/tree/hdr_tree_reg.cpp | 2 + tests/unit/print_bronsonavltree_stat.h | 33 ++ 14 files changed, 517 insertions(+), 17 deletions(-) create mode 100644 tests/test-hdr/tree/hdr_bronson_avltree_map.h create mode 100644 tests/test-hdr/tree/hdr_bronson_avltree_map_rcu_gpb.cpp create mode 100644 tests/unit/print_bronsonavltree_stat.h diff --git a/cds/container/bronson_avltree_map_rcu.h b/cds/container/bronson_avltree_map_rcu.h index 1aa1b38c..5705bbd1 100644 --- a/cds/container/bronson_avltree_map_rcu.h +++ b/cds/container/bronson_avltree_map_rcu.h @@ -7,7 +7,7 @@ namespace cds { namespace container { - namespace bronson_avltree { + namespace bronson_avltree { //@cond namespace details { template < typename Key, typename T, typename Traits> @@ -77,7 +77,7 @@ 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< Key, T, Traits >::type #endif { //@cond @@ -105,7 +105,7 @@ namespace cds { namespace container { static bool const c_bRelaxedInsert = traits::relaxed_insert; /// Returned pointer to value of extracted node - typedef base_class::unique_ptr unique_ptr; + typedef typename base_class::unique_ptr unique_ptr; protected: //@cond @@ -515,7 +515,6 @@ namespace cds { namespace container { { return base_class::check_consistency(); } - }; }} // namespace cds::container diff --git a/cds/container/details/bronson_avltree_base.h b/cds/container/details/bronson_avltree_base.h index 26231d97..55c63d2c 100644 --- a/cds/container/details/bronson_avltree_base.h +++ b/cds/container/details/bronson_avltree_base.h @@ -7,6 +7,7 @@ #include #include #include +#include namespace cds { namespace container { @@ -87,9 +88,10 @@ namespace cds { namespace container { return m_nHeight.load( order ); } - void height( int h, atomics::memory_order order ) + void height( int h, atomics::memory_order order ) { m_nHeight.store( h, order ); + } template void wait_until_shrink_completed( atomics::memory_order order ) const @@ -160,7 +162,7 @@ namespace cds { namespace container { 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_nUpdateRetry; ///< Count of update retries via concurrent operations - event_counter m_nUpdateRootWaitShinking; ///< Count of waiting until root shrinking completed duting \p update() call + 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 @@ -350,8 +352,6 @@ namespace cds { namespace container { >::type type; # endif }; - - } // namespace bronson_avltree // Forwards diff --git a/cds/container/impl/bronson_avltree_map_rcu.h b/cds/container/impl/bronson_avltree_map_rcu.h index 55aaefac..ffbf2fd9 100644 --- a/cds/container/impl/bronson_avltree_map_rcu.h +++ b/cds/container/impl/bronson_avltree_map_rcu.h @@ -66,14 +66,14 @@ namespace cds { namespace container { 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; + 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; protected: //@cond - typedef typename sync_monitor::template node_injection< bronson_avltree::node< key_type, mapped_type >> node_type; + typedef typename sync_monitor::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; @@ -834,7 +834,7 @@ namespace cds { namespace container { pOld = pNode->value( memory_model::memory_order_relaxed ); mapped_type * pVal = funcUpdate( *pNode ); assert( pVal != nullptr ); - pNode->m_pValue.store( pVal, memory_model::memory_order_relaxed )); + pNode->m_pValue.store( pVal, memory_model::memory_order_relaxed ); } if ( pOld ) { diff --git a/cds/sync/monitor.h b/cds/sync/monitor.h index 2ce48846..896e5a9b 100644 --- a/cds/sync/monitor.h +++ b/cds/sync/monitor.h @@ -101,7 +101,7 @@ namespace cds { namespace sync { public: /// Makes exclusive access to the node \p p by \p monitor - scoped_lock( monitor_type& monitor, node_type const& p ) + monitor_scoped_lock( monitor_type& monitor, node_type const& p ) : m_Monitor( monitor ) , m_Node( p ) { @@ -109,7 +109,7 @@ namespace cds { namespace sync { } /// Unlocks the node - ~scoped_lock() + ~monitor_scoped_lock() { m_Monitor.unlock( m_Node ); } diff --git a/cds/sync/pool_monitor.h b/cds/sync/pool_monitor.h index cf877166..18190ad0 100644 --- a/cds/sync/pool_monitor.h +++ b/cds/sync/pool_monitor.h @@ -51,8 +51,8 @@ namespace cds { namespace sync { { //@cond typedef unsigned int refspin_type; - constexpr refspin_type const c_nSpinBit = 1; - constexpr refspin_type const c_nRefIncrement = 2; + static CDS_CONSTEXPR refspin_type const c_nSpinBit = 1; + static CDS_CONSTEXPR refspin_type const c_nRefIncrement = 2; struct injection { diff --git a/projects/Win/vc12/cds.sln b/projects/Win/vc12/cds.sln index 7bead727..8f42ac09 100644 --- a/projects/Win/vc12/cds.sln +++ b/projects/Win/vc12/cds.sln @@ -1,11 +1,12 @@ Microsoft Visual Studio Solution File, Format Version 12.00 # Visual Studio Express 2013 for Windows Desktop -VisualStudioVersion = 12.0.31010.0 +VisualStudioVersion = 12.0.31101.0 MinimumVisualStudioVersion = 10.0.40219.1 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "cds", "cds.vcxproj", "{408FE9BC-44F0-4E6A-89FA-D6F952584239}" EndProject Project("{2150E333-8FDC-42A3-9474-1A3956D46DE8}") = "unit-test", "unit-test", "{B30CA283-1796-4763-92C3-2E4848D443F7}" ProjectSection(SolutionItems) = preProject + ..\..\..\tests\unit\print_bronsonavltree_stat.h = ..\..\..\tests\unit\print_bronsonavltree_stat.h ..\..\..\tests\unit\print_cuckoo_stat.h = ..\..\..\tests\unit\print_cuckoo_stat.h ..\..\..\tests\unit\print_ellenbintree_stat.h = ..\..\..\tests\unit\print_ellenbintree_stat.h ..\..\..\tests\unit\print_mspriorityqueue_stat.h = ..\..\..\tests\unit\print_mspriorityqueue_stat.h diff --git a/projects/Win/vc12/hdr-test-tree.vcxproj b/projects/Win/vc12/hdr-test-tree.vcxproj index 33ee01bb..ba868268 100644 --- a/projects/Win/vc12/hdr-test-tree.vcxproj +++ b/projects/Win/vc12/hdr-test-tree.vcxproj @@ -535,6 +535,7 @@ + @@ -543,6 +544,7 @@ + diff --git a/projects/Win/vc12/hdr-test-tree.vcxproj.filters b/projects/Win/vc12/hdr-test-tree.vcxproj.filters index fcdd4712..84e36904 100644 --- a/projects/Win/vc12/hdr-test-tree.vcxproj.filters +++ b/projects/Win/vc12/hdr-test-tree.vcxproj.filters @@ -27,6 +27,9 @@ intrusive + + container + @@ -114,5 +117,8 @@ container + + container + \ No newline at end of file diff --git a/projects/source.test-hdr.mk b/projects/source.test-hdr.mk index 5b3e829b..ac20800c 100644 --- a/projects/source.test-hdr.mk +++ b/projects/source.test-hdr.mk @@ -225,6 +225,7 @@ CDS_TESTHDR_STACK := \ CDS_TESTHDR_TREE := \ tests/test-hdr/tree/hdr_tree_reg.cpp \ + tests/test-hdr/tree/hdr_bronson_avltree_map_rcu_gpb.cpp \ tests/test-hdr/tree/hdr_intrusive_ellen_bintree_hp.cpp \ tests/test-hdr/tree/hdr_intrusive_ellen_bintree_dhp.cpp \ tests/test-hdr/tree/hdr_intrusive_ellen_bintree_rcu_gpb.cpp \ diff --git a/tests/test-hdr/tree/hdr_bronson_avltree_map.h b/tests/test-hdr/tree/hdr_bronson_avltree_map.h new file mode 100644 index 00000000..199fd15f --- /dev/null +++ b/tests/test-hdr/tree/hdr_bronson_avltree_map.h @@ -0,0 +1,421 @@ +//$$CDS-header$$ + +#ifndef CDSTEST_HDR_BRONSON_AVLTREE_MAP_H +#define CDSTEST_HDR_BRONSON_AVLTREE_MAP_H + +#include "cppunit/cppunit_proxy.h" +#include "size_check.h" +#include // ref +#include + +namespace tree { + using misc::check_size; + + class BronsonAVLTreeHdrTest : public CppUnitMini::TestCase + { + public: + typedef int key_type; + + struct stat_data { + size_t nInsertFuncCall; + size_t nEnsureExistFuncCall; + size_t nEnsureNewFuncCall; + size_t nEraseFuncCall; + size_t nFindFuncCall; + size_t nFindConstFuncCall; + + stat_data() + : nInsertFuncCall( 0 ) + , nEnsureExistFuncCall( 0 ) + , nEnsureNewFuncCall( 0 ) + , nEraseFuncCall( 0 ) + , nFindFuncCall( 0 ) + , nFindConstFuncCall( 0 ) + {} + }; + + struct value_type { + int nVal; + stat_data stat; + + value_type() + {} + + value_type( int v ) + : nVal( v ) + {} + }; + + struct wrapped_int { + int nKey; + + wrapped_int( int n ) + : nKey( n ) + {} + }; + + struct wrapped_less + { + bool operator()( wrapped_int const& w, int n ) const + { + return w.nKey < n; + } + bool operator()( int n, wrapped_int const& w ) const + { + return n < w.nKey; + } + template + bool operator()( wrapped_int const& w, T const& v ) const + { + return w.nKey < v.nKey; + } + template + bool operator()( T const& v, wrapped_int const& w ) const + { + return v.nKey < w.nKey; + } + }; + + protected: + static const size_t c_nItemCount = 10000; + + class data_array + { + int * pFirst; + int * pLast; + + public: + data_array() + : pFirst( new int[c_nItemCount] ) + , pLast( pFirst + c_nItemCount ) + { + int i = 0; + for ( int * p = pFirst; p != pLast; ++p, ++i ) + *p = i; + + std::random_shuffle( pFirst, pLast ); + } + + ~data_array() + { + delete[] pFirst; + } + + int operator[]( size_t i ) const + { + assert( i < size_t( pLast - pFirst ) ); + return pFirst[i]; + } + }; + + struct find_functor + { + template + void operator()( value_type& i, T& /*val*/ ) + { + ++i.stat.nFindFuncCall; + } + template + void operator()( value_type& i, T const& /*val*/ ) + { + ++i.stat.nFindConstFuncCall; + } + }; + + template + struct copy_found + { + Item m_found; + + template + void operator()( Item& i, T& /*val*/ ) + { + m_found = i; + } + + void operator()( Item const& i ) + { + m_found = i; + } + }; + + struct insert_functor + { + template + void operator()( Item& i ) + { + i.nVal = i.nKey * 100; + ++i.stat.nInsertFuncCall; + } + }; + + template + static void ensure_func( bool bNew, value_type& i, Q& /*val*/ ) + { + if ( bNew ) + ++i.stat.nEnsureNewFuncCall; + else + ++i.stat.nEnsureExistFuncCall; + } + + struct ensure_functor + { + template + void operator()( bool bNew, value_type& i, Q& val ) + { + ensure_func( bNew, i, val ); + } + }; + + struct extract_functor + { + int nKey; + + template + void operator()( Q&, value_type& v ) + { + nKey = v.nKey; + } + }; + + protected: + template + void test_with( Set& s ) + { + value_type itm; + int key; + + // insert/find test + CPPUNIT_ASSERT( !s.find( 10 ) ); + CPPUNIT_ASSERT( s.insert( 10 ) ); + CPPUNIT_ASSERT( !s.empty() ); + CPPUNIT_ASSERT( check_size( s, 1 ) ); + CPPUNIT_ASSERT( s.find( 10 ) ); + + CPPUNIT_ASSERT( !s.insert( 10 ) ); + 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.empty() ); + CPPUNIT_ASSERT( check_size( s, 2 ) ); + CPPUNIT_ASSERT( s.find_with( 10, less() ) ); + CPPUNIT_ASSERT( s.find( key = 20 ) ); + CPPUNIT_ASSERT( s.find_with( key, 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( 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( f.m_found.nVal == 25 ); + CPPUNIT_ASSERT( f.m_found.stat.nFindFuncCall == 2 ); + CPPUNIT_ASSERT( f.m_found.stat.nFindConstFuncCall == 1 ); + } + + 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.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 ); + } + + // update test + 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 ); + } + std::pair ensureResult = s.update( key, ensure_functor() ); + CPPUNIT_ASSERT( ensureResult.first && !ensureResult.second ); + CPPUNIT_ASSERT( !s.empty() ); + 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() ); + 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 ); + } + + // erase test + CPPUNIT_ASSERT( s.erase( 13 ) ); + CPPUNIT_ASSERT( !s.find( 13 ) ); + CPPUNIT_ASSERT( !s.empty() ); + CPPUNIT_ASSERT( check_size( s, 3 ) ); + CPPUNIT_ASSERT( !s.erase( 13 ) ); + CPPUNIT_ASSERT( !s.empty() ); + CPPUNIT_ASSERT( check_size( s, 3 ) ); + + CPPUNIT_ASSERT( s.find( 10 ) ); + CPPUNIT_ASSERT( s.erase_with( 10, 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.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( f.m_found.nVal == 2350 ); + } + CPPUNIT_ASSERT( !s.find( 20 ) ); + CPPUNIT_ASSERT( !s.empty() ); + CPPUNIT_ASSERT( check_size( s, 1 ) ); + + s.clear(); + CPPUNIT_ASSERT( s.empty() ); + CPPUNIT_ASSERT( check_size( s, 0 ) ); + + // emplace test + CPPUNIT_ASSERT( s.emplace( 151 ) ); // key = 151, val = 1510 + 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( s.find( 151 ) ); + CPPUNIT_ASSERT( s.find_with( 174, 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 ); + + 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(); + CPPUNIT_ASSERT( s.empty() ); + CPPUNIT_ASSERT( check_size( s, 0 ) ); + } + + template + void fill_set( Set& s, data_array& a ) + { + CPPUNIT_ASSERT( s.empty() ); + for ( size_t i = 0; i < c_nItemCount; ++i ) { + CPPUNIT_ASSERT( s.insert( a[i] ) ); + } + CPPUNIT_ASSERT( !s.empty() ); + CPPUNIT_ASSERT( check_size( s, c_nItemCount ) ); + } + + template + void test() + { + typedef Set set_type; + + set_type s; + + test_with( s ); + + s.clear(); + CPPUNIT_ASSERT( s.empty() ); + CPPUNIT_ASSERT( check_size( s, 0 ) ); + + + + PrintStat()(s); + } + + + void BronsonAVLTree_rcu_gpb_less(); + void BronsonAVLTree_rcu_gpb_cmp(); + void BronsonAVLTree_rcu_gpb_cmpless(); + void BronsonAVLTree_rcu_gpb_less_ic(); + void BronsonAVLTree_rcu_gpb_cmp_ic(); + void BronsonAVLTree_rcu_gpb_less_stat(); + void BronsonAVLTree_rcu_gpb_cmp_ic_stat(); + void BronsonAVLTree_rcu_gpb_cmp_ic_stat_yield(); + + CPPUNIT_TEST_SUITE( BronsonAVLTreeHdrTest ) + CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_less ) + CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_cmp ) + CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_cmpless ) + CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_less_ic ) + CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_cmp_ic ) + CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_less_stat ) + CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_cmp_ic_stat ) + CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_cmp_ic_stat_yield ) + CPPUNIT_TEST_SUITE_END() + }; +} // namespace tree + +#endif // #ifndef CDSTEST_HDR_BRONSON_AVLTREE_MAP_H diff --git a/tests/test-hdr/tree/hdr_bronson_avltree_map_rcu_gpb.cpp b/tests/test-hdr/tree/hdr_bronson_avltree_map_rcu_gpb.cpp new file mode 100644 index 00000000..c33a555c --- /dev/null +++ b/tests/test-hdr/tree/hdr_bronson_avltree_map_rcu_gpb.cpp @@ -0,0 +1,36 @@ +//$$CDS-header$$ + +#include "tree/hdr_bronson_avltree_map.h" +#include +#include + +#include "unit/print_bronsonavltree_stat.h" + +namespace tree { + namespace cc = cds::container; + namespace co = cds::opt; + namespace { + typedef cds::urcu::gc< cds::urcu::general_buffered<> > rcu_type; + + struct print_stat { + template + void operator()( Tree const& t ) + { + std::cout << t.statistics(); + } + }; + } // namespace + + void BronsonAVLTreeHdrTest::BronsonAVLTree_rcu_gpb_less() + { + typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, + cc::bronson_avltree::make_traits< + co::less< std::less > + >::type + > map_type; + + test(); + + } + +} // namespace tree diff --git a/tests/test-hdr/tree/hdr_ellenbintree_map_rcu_gpb.cpp b/tests/test-hdr/tree/hdr_ellenbintree_map_rcu_gpb.cpp index babea28d..46ef480c 100644 --- a/tests/test-hdr/tree/hdr_ellenbintree_map_rcu_gpb.cpp +++ b/tests/test-hdr/tree/hdr_ellenbintree_map_rcu_gpb.cpp @@ -24,7 +24,6 @@ namespace tree { std::cout << t.statistics(); } }; - } void EllenBinTreeMapHdrTest::EllenBinTree_rcu_gpb_less() diff --git a/tests/test-hdr/tree/hdr_tree_reg.cpp b/tests/test-hdr/tree/hdr_tree_reg.cpp index b9d57eab..b7dd1176 100644 --- a/tests/test-hdr/tree/hdr_tree_reg.cpp +++ b/tests/test-hdr/tree/hdr_tree_reg.cpp @@ -7,6 +7,7 @@ #include "tree/hdr_ellenbintree_set.h" #include "tree/hdr_ellenbintree_map.h" +#include "tree/hdr_bronson_avltree_map.h" namespace tree { namespace ellen_bintree_rcu { @@ -27,3 +28,4 @@ namespace tree { CPPUNIT_TEST_SUITE_REGISTRATION_(tree::IntrusiveBinTreeHdrTest, s_IntrusiveBinTreeHdrTest); CPPUNIT_TEST_SUITE_REGISTRATION_(tree::EllenBinTreeSetHdrTest, s_EllenBinTreeSetHdrTest); CPPUNIT_TEST_SUITE_REGISTRATION_(tree::EllenBinTreeMapHdrTest, s_EllenBinTreeMapHdrTest); +CPPUNIT_TEST_SUITE_REGISTRATION_( tree::BronsonAVLTreeHdrTest, s_BronsonAVLTreeHdrTest ); diff --git a/tests/unit/print_bronsonavltree_stat.h b/tests/unit/print_bronsonavltree_stat.h new file mode 100644 index 00000000..a8cdd121 --- /dev/null +++ b/tests/unit/print_bronsonavltree_stat.h @@ -0,0 +1,33 @@ +//$$CDS-header$$ + +#ifndef CDSUNIT_PRINT_BRONSONAVLTREE_STAT_H +#define CDSUNIT_PRINT_BRONSONAVLTREE_STAT_H + +#include + +namespace std { + static inline ostream& operator <<( ostream& o, cds::container::bronson_avltree::empty_stat const& /*s*/ ) + { + return o; + } + + static inline ostream& operator <<(ostream& o, cds::container::bronson_avltree::stat<> const& s) + { + return o << "\nBronsonAVLTree statistics [cds::container::bronson_avltree::stat]:\n" + << "\t\t m_nFindSuccess: " << s.m_nFindSuccess.get() << "\n" + << "\t\t m_nFindFailed: " << s.m_nFindFailed.get() << "\n" + << "\t\t m_nFindRetry: " << s.m_nFindRetry.get() << "\n" + << "\t\t m_nFindWaitShrinking: " << s.m_nFindWaitShrinking.get() << "\n" + << "\t\t m_nInsertSuccess: " << s.m_nInsertSuccess.get() << "\n" + << "\t\t m_nRelaxedInsertFailed: " << s.m_nRelaxedInsertFailed.get() << "\n" + << "\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\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"; + } +} + +#endif // #ifndef CDSUNIT_PRINT_ELLENBINTREE_STAT_H -- 2.34.1