Bronson's AVL-tree impl

diff --git a/cds/container/bronson_avltree_map_rcu.h b/cds/container/bronson_avltree_map_rcu.h
index 4532ee0a7dd4dceb5acd96ffb66f40bc202f0f0d..c963723288048a5467f7a2f83a4923d2264f42ed 100644 (file)
--- a/cds/container/bronson_avltree_map_rcu.h
+++ b/cds/container/bronson_avltree_map_rcu.h
@@ -143,8 +143,8 @@ namespace cds { namespace container {
                     CDS_UNUSED( pNode );
                     return cxx_allocator().New();
                 },
-                    static_cast<int>(update_flags::allow_insert)
-            ) == static_cast<int>(update_flags::result_inserted);
+                update_flags::allow_insert
+            ) == update_flags::result_inserted;
         }
 
         /// Inserts new node
@@ -170,8 +170,8 @@ namespace cds { namespace container {
                     CDS_UNUSED( pNode );
                     return cxx_allocator().New( val );
                 },
-                static_cast<int>(update_flags::allow_insert)
-            ) == static_cast<int>(update_flags::result_inserted);
+                update_flags::allow_insert
+            ) == update_flags::result_inserted;
         }
 
         /// Inserts new node and initialize it by a functor
@@ -208,8 +208,8 @@ namespace cds { namespace container {
                     func( pNode->m_key, *pVal );
                     return pVal;
                 },
-                static_cast<int>(update_flags::allow_insert)
-            ) == static_cast<int>(update_flags::result_inserted);
+                update_flags::allow_insert
+            ) == update_flags::result_inserted;
         }
 
         /// For key \p key inserts data of type \p mapped_type created in-place from \p args
@@ -228,8 +228,8 @@ namespace cds { namespace container {
                     CDS_UNUSED( pNode );
                     return cxx_allocator().New( std::forward<Args>(args)...);
                 },
-                static_cast<int>(update_flags::allow_insert)
-            ) == static_cast<int>(update_flags::result_inserted);
+                update_flags::allow_insert
+            ) == update_flags::result_inserted;
         }
 
         /// Ensures that the \p key exists in the map

diff --git a/cds/container/details/bronson_avltree_base.h b/cds/container/details/bronson_avltree_base.h
index 0d99b66047cd1072606f680a5ef77334241a1b22..bbb15e7a33e0857789588fef8bfdaa6df5086ed8 100644 (file)
--- a/cds/container/details/bronson_avltree_base.h
+++ b/cds/container/details/bronson_avltree_base.h
@@ -18,10 +18,11 @@ namespace cds { namespace container {
         struct node;
 
         //@cond
-        template <typename Node, typename SyncMonitor>
+        template <typename Node, typename T, typename SyncMonitor>
         struct link_node
         {
-            typedef Node node_type;
+            typedef Node     node_type;
+            typedef T        mapped_type;
             typedef uint32_t version_type;  ///< version type (internal)
 
             enum
@@ -38,6 +39,7 @@ namespace cds { namespace container {
             atomics::atomic<node_type *>    m_pLeft;    ///< Left child
             atomics::atomic<node_type *>    m_pRight;   ///< Right child
             typename SyncMonitor::node_injection m_SyncMonitorInjection;    ///< @ref cds_sync_monitor "synchronization monitor" injected data
+            atomics::atomic<mapped_type *>  m_pValue;   ///< Value
 
         public:
             //@cond
@@ -47,6 +49,7 @@ namespace cds { namespace container {
                 , m_pParent( nullptr )
                 , m_pLeft( nullptr )
                 , m_pRight( nullptr )
+                , m_pValue( nullptr )
             {}
 
             link_node( int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight )
@@ -55,6 +58,7 @@ namespace cds { namespace container {
                 , m_pParent( pParent )
                 , m_pLeft( pLeft )
                 , m_pRight( pRight )
+                , m_pValue( nullptr )
             {}
 
             atomics::atomic<node_type *>& child( int nDirection )
@@ -109,22 +113,32 @@ namespace cds { namespace container {
             {
                 return (m_nVersion.load( order ) & shrinking) != 0;
             }
+
+            mapped_type * value( atomics::memory_order order ) const
+            {
+                return m_pValue.load( order );
+            }
+
+            bool is_valued( atomics::memory_order order ) const
+            {
+                return value( order ) != nullptr;
+            }
+
             //@endcond
         };
         //@endcond
 
         // BronsonAVLTree internal node
         template <typename Key, typename T, typename SyncMonitor >
-        struct node<Key, T*, SyncMonitor>: public link_node< node<Key, T*, SyncMonitor>, SyncMonitor >
+        struct node<Key, T*, SyncMonitor>: public link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor >
         {
-            typedef link_node< node<Key, T*, SyncMonitor>, SyncMonitor > base_class;
+            typedef link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor > 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;      ///< Key
-            atomics::atomic<mapped_type *>  m_pValue;   ///< Value
             node *                          m_pNextRemoved; ///< thread-local list of removed node
 
         public:
@@ -133,7 +147,6 @@ namespace cds { namespace container {
             node( Q&& key )
                 : base_class()
                 , m_key( std::forward<Q>( key ) )
-                , m_pValue( nullptr )
                 , m_pNextRemoved( nullptr )
             {}
 
@@ -141,18 +154,8 @@ namespace cds { namespace container {
             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<Q>( key ) )
-                , m_pValue( nullptr )
                 , m_pNextRemoved( nullptr )
             {}
-            T * value( atomics::memory_order order ) const
-            {
-                return m_pValue.load( order );
-            }
-
-            bool is_valued( atomics::memory_order order ) const
-            {
-                return value( order ) != nullptr;
-            }
             //@endcond
         };
 

diff --git a/cds/container/impl/bronson_avltree_map_rcu.h b/cds/container/impl/bronson_avltree_map_rcu.h
index f162dc08cb402f54929f51d6523ecf169826ace4..ebcb83a2531bcc328557095e5783c2d19cebf2a7 100644 (file)
--- a/cds/container/impl/bronson_avltree_map_rcu.h
+++ b/cds/container/impl/bronson_avltree_map_rcu.h
@@ -6,8 +6,6 @@
 #include <memory> // unique_ptr
 #include <cds/container/details/bronson_avltree_base.h>
 #include <cds/urcu/details/check_deadlock.h>
-#include <cds/details/binary_functor_wrapper.h>
-
 
 namespace cds { namespace container {
 
@@ -294,7 +292,7 @@ namespace cds { namespace container {
             CDS_UNUSED( pred );
             return do_remove( 
                 key, 
-                cds::details::predicate_wrapper<key_type, Less, cds::details::trivial_accessor >(),
+                cds::opt::details::make_comparator_from_less<Less>(),
                 []( mapped_type pVal ) -> bool { free_value( pVal ); return true;  }
             );
         }
@@ -343,7 +341,7 @@ namespace cds { namespace container {
             CDS_UNUSED( pred );
             return do_remove( 
                 key, 
-                cds::details::predicate_wrapper<key_type, Less, cds::details::trivial_accessor >(),
+                cds::opt::details::make_comparator_from_less<Less>(),
                 [&f]( mapped_type pVal ) -> bool { 
                     assert( pVal );
                     f( *pVal ); 
@@ -435,7 +433,7 @@ namespace cds { namespace container {
 
             do_remove(
                 key,
-                cds::details::predicate_wrapper<key_type, Less, cds::details::trivial_accessor >(),
+                cds::opt::details::make_comparator_from_less<Less>(),
                 [&pExtracted]( mapped_type pVal ) -> bool { pExtracted.reset( pVal ); return false; }
             );
             return pExtracted;
@@ -461,9 +459,8 @@ namespace cds { namespace container {
         bool find( K const& key, Func f )
         {
             return do_find( key, key_comparator(), 
-                [&f]( sync_monitor& monitor, node_type * pNode ) -> bool {
+                [&f]( 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 );
@@ -485,10 +482,9 @@ namespace cds { namespace container {
         bool find_with( K const& key, Less pred, Func f )
         {
             CDS_UNUSED( pred );
-            return do_find( key, opt::details::make_comparator_from_less<Less>(), 
-                [&f]( sync_monitor& monitor, node_type * pNode ) -> bool {
+            return do_find( key, cds::opt::details::make_comparator_from_less<Less>(), 
+                [&f]( 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 );
@@ -509,7 +505,7 @@ namespace cds { namespace container {
         template <typename K>
         bool find( K const& key )
         {
-            return do_find( key, key_comparator(), []( sync_monitor&, node_type * ) -> bool { return true; });
+            return do_find( key, key_comparator(), []( node_type * ) -> bool { return true; });
         }
 
         /// Finds the key \p val using \p pred predicate for searching
@@ -523,7 +519,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<Less>(), []( sync_monitor&, node_type * ) -> bool { return true; } );
+            return do_find( key, cds::opt::details::make_comparator_from_less<Less>(), []( node_type * ) -> bool { return true; } );
         }
 
         /// Clears the tree (thread safe, not atomic)
@@ -662,7 +658,7 @@ namespace cds { namespace container {
                         // key found
                         node_scoped_lock l( m_Monitor, *pChild );
                         if ( pChild->is_valued( memory_model::memory_order_relaxed )) {
-                            if ( f( m_Monitor, pChild ) ) {
+                            if ( f( pChild ) ) {
                                 m_stat.onFindSuccess();
                                 return find_result::found;
                             }
@@ -940,8 +936,8 @@ namespace cds { namespace container {
         int try_update_node( Func funcUpdate, node_type * pNode )
         {
             mapped_type pOld;
+            assert( pNode != nullptr );
             {
-                assert( pNode != nullptr );
                 node_scoped_lock l( m_Monitor, *pNode );
 
                 if ( pNode->is_unlinked( memory_model::memory_order_relaxed )) {
@@ -951,8 +947,12 @@ 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 );
+                if ( pVal == pOld )
+                    pOld = nullptr;
+                else {
+                    assert( pVal != nullptr );
+                    pNode->m_pValue.store( pVal, memory_model::memory_order_relaxed );
+                }
             }
 
             if ( pOld ) {
@@ -1062,12 +1062,10 @@ namespace cds { namespace container {
 
             // Mark the node as unlinked
             pNode->version( node_type::unlinked, memory_model::memory_order_release );
-            mapped_type pVal = pNode->value( memory_model::memory_order_relaxed );
-            if ( pVal ) {
-                free_value( pVal );
-                m_stat.onDisposeValue();
-                pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
-            }
+
+            // The value will be disposed by calling function
+            pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
+
             disp.dispose( pNode );
             m_stat.onDisposeNode();
 

diff --git a/tests/test-hdr/tree/hdr_bronson_avltree_map.h b/tests/test-hdr/tree/hdr_bronson_avltree_map.h
index 4d6347ab8e7b4d8ec523758504ad024cb120baad..88523d42b27027329365e06c04b7ac1942c4b721 100644 (file)
--- a/tests/test-hdr/tree/hdr_bronson_avltree_map.h
+++ b/tests/test-hdr/tree/hdr_bronson_avltree_map.h
@@ -37,6 +37,7 @@ namespace tree {
             stat_data   stat;
 
             value_type()
+                : nVal(0)
             {}
 
             value_type( int v )
@@ -141,8 +142,9 @@ namespace tree {
         };
 
         template <typename Q>
-        static void ensure_func( bool bNew, Q /*key*/, value_type& i )
+        static void ensure_func( bool bNew, Q key, value_type& i )
         {
+            i.nVal = key * 100;
             if ( bNew )
                 ++i.stat.nEnsureNewFuncCall;
             else
@@ -236,7 +238,7 @@ namespace tree {
             {
                 copy_found<value_type> f;
                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
-                CPPUNIT_ASSERT( f.m_found.nVal == 100 );
+                CPPUNIT_ASSERT( f.m_found.nVal == 0 );
                 CPPUNIT_ASSERT( f.m_found.stat.nEnsureExistFuncCall == 0 );
                 CPPUNIT_ASSERT( f.m_found.stat.nEnsureNewFuncCall == 0 );
             }
@@ -247,15 +249,15 @@ namespace tree {
             {
                 copy_found<value_type> f;
                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
-                CPPUNIT_ASSERT( f.m_found.nVal == 100 );
+                CPPUNIT_ASSERT( f.m_found.nVal == 1000 );
                 CPPUNIT_ASSERT( f.m_found.stat.nEnsureExistFuncCall == 1 );
                 CPPUNIT_ASSERT( f.m_found.stat.nEnsureNewFuncCall == 0 );
             }
 
             ensureResult = s.update( 13, []( bool /*bNew*/, key_type key, value_type& v ) 
                 { 
-                    v.nVal = key * 100; 
-                    ++v.stat.nEnsureExistFuncCall; 
+                    v.nVal = key * 1000; 
+                    ++v.stat.nEnsureNewFuncCall; 
                 });
             CPPUNIT_ASSERT( ensureResult.first && ensureResult.second );
             CPPUNIT_ASSERT( !s.empty() );
@@ -264,7 +266,7 @@ namespace tree {
                 copy_found<value_type> f;
                 key = 13;
                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
-                CPPUNIT_ASSERT( f.m_found.nVal == 1300 );
+                CPPUNIT_ASSERT( f.m_found.nVal == 13000 );
                 CPPUNIT_ASSERT( f.m_found.stat.nEnsureExistFuncCall == 0 );
                 CPPUNIT_ASSERT( f.m_found.stat.nEnsureNewFuncCall == 1 );
             }
@@ -372,13 +374,13 @@ namespace tree {
 
         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( 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

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
index c33a555c0f606f992a07bcd2e5746e1ac6785670..5b3875ce88906085e44f8529116b563baed56b70 100644 (file)
--- a/tests/test-hdr/tree/hdr_bronson_avltree_map_rcu_gpb.cpp
+++ b/tests/test-hdr/tree/hdr_bronson_avltree_map_rcu_gpb.cpp
@@ -23,14 +23,13 @@ namespace tree {
 
     void BronsonAVLTreeHdrTest::BronsonAVLTree_rcu_gpb_less()
     {
-        typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type,
+        struct traits: public 
             cc::bronson_avltree::make_traits<
                 co::less< std::less<key_type> >
             >::type
-        > map_type;
-
+        {};
+        typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, traits > map_type;
         test<map_type, print_stat>();
-
     }
 
 } // namespace tree