From ac84685693a458d098439506ee6b52a38f734bac Mon Sep 17 00:00:00 2001 From: khizmax Date: Sat, 31 Jan 2015 17:38:38 +0300 Subject: [PATCH] Bronson AVL-tree impl --- cds/container/bronson_avltree_map_rcu.h | 93 +++++++++++++------- cds/container/details/bronson_avltree_base.h | 11 +-- cds/container/impl/bronson_avltree_map_rcu.h | 28 ++---- 3 files changed, 72 insertions(+), 60 deletions(-) diff --git a/cds/container/bronson_avltree_map_rcu.h b/cds/container/bronson_avltree_map_rcu.h index cc5352e8..b1407c33 100644 --- a/cds/container/bronson_avltree_map_rcu.h +++ b/cds/container/bronson_avltree_map_rcu.h @@ -11,12 +11,6 @@ namespace cds { namespace container { //@cond namespace details { - template - struct value_node : public bronson_avltree::node< Key, T, Lock > - { - T m_data; // placeholder for data - }; - template struct pointer_oriented_traits: public Traits { @@ -30,6 +24,35 @@ namespace cds { namespace container { typedef value_node node_type; }; + + template < typename Key, typename T, typename Traits> + struct make_map + { + typedef Key key_type; + typedef T mapped_type; + typedef Traits original_traits; + + typedef cds::details::Allocator< mapped_type, typename original_traits::allocator > cxx_allocator; + + struct traits : public original_traits + { + struct disposer { + template + void operator()( mapped_type * p ) + { + cxx_allocator().Delete( p ); + } + }; + }; + + // Metafunction result + typedef BronsonAVLTreeMap < + cds::urcu::gc, + Key, + T *, + traits + > type; + }; } // namespace details //@endcond } // namespace bronson_avltree @@ -66,10 +89,15 @@ namespace cds { namespace container { #endif > class BronsonAVLTreeMap< cds::urcu::gc, Key, T, Traits > - : private BronsonAVLTreeMap< cds::urcu::gc, Key, T*, bronson_avltree::details::pointer_oriented_traits> +#ifdef CDS_DOXYGEN_INVOKED + : private BronsonAVLTreeMap< cds::urcu::gc, Key, T*, Traits > +#else + : private bronson_avltree::details::make_map< Key, T, Traits >::type; +#endif { //@cond - typedef BronsonAVLTreeMap< cds::urcu::gc, Key, T*, bronson_avltree::details::pointer_oriented_traits> base_class; + typedef bronson_avltree::details::make_map< Key, T, Traits > maker; + typedef typename maker::type base_class; //@endcond public: @@ -81,7 +109,8 @@ namespace cds { namespace container { typedef typename base_class::key_comparator key_comparator; ///< key compare functor based on \p Traits::compare and \p Traits::less typedef typename traits::item_counter item_counter; ///< Item counting policy typedef typename traits::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model option - typedef typename traits::allocator allocator_type; ///< allocator for maintaining internal node + typedef typename traits::allocator allocator_type; ///< allocator for value + typedef typename traits::node_allocator node_allocator_type;///< allocator for maintaining internal nodes typedef typename traits::stat stat; ///< internal statistics typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy typedef typename traits::back_off back_off; ///< Back-off strategy @@ -92,9 +121,9 @@ namespace cds { namespace container { protected: //@cond - typedef typename base_class::alloc_node_type node_type; - typedef typename base_class::node_type base_node_type; - typedef base_class::node_scoped_lock node_scoped_lock; + typedef typename base_class::node_type node_type; + typedef typename base_class::node_scoped_lock node_scoped_lock; + typedef typename maker::cxx_allocator cxx_allocator; using base_class::update_flags; //@endcond @@ -124,12 +153,10 @@ namespace cds { namespace container { bool insert( K const& key ) { return base_class::do_update(key, key_comparator(), - []( base_node_type * pNode ) -> mapped_type* + []( node_type * pNode ) -> mapped_type* { assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr ); - node_type * p = static_cast(pNode); - new (&p->m_data) mapped_type; - return &p->m_data; + return cxx_allocator().New(); }, update_flags::allow_insert ) == update_flags::result_insert; @@ -152,12 +179,10 @@ namespace cds { namespace container { bool insert( K const& key, V const& val ) { return base_class::do_update( key, key_comparator(), - [&val]( base_node_type * pNode ) + [&val]( node_type * pNode ) { assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr ); - node_type * p = static_cast(pNode); - new (&p->m_data) mapped_type( val ); - return &p->m_data; + return cxx_allocator().New( val ); }, update_flags::allow_insert ) == update_flags::result_insert; @@ -190,12 +215,12 @@ namespace cds { namespace container { bool insert_with( K const& key, Func func ) { return base_class::do_update( key, key_comparator(), - [&func]( base_node_type * pNode ) -> mapped_type* + [&func]( node_type * pNode ) -> mapped_type* { assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr ); - node_type * p = static_cast(pNode); - func( p->m_data ); - return &p->m_data; + mapped_type * pVal = cxx_allocator().New(); + func( *pVal ); + return pVal; }, update_flags::allow_insert ) == update_flags::result_insert; @@ -211,12 +236,10 @@ namespace cds { namespace container { bool emplace( K&& key, Args&&... args ) { return base_class::do_update( key, key_comparator(), - [&]( base_node_type * pNode ) -> mapped_type* + [&]( node_type * pNode ) -> mapped_type* { assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr ); - node_type * p = static_cast(pNode); - new (&p->m_data) mapped_type( std::forward(args)... ); - return &p->m_data; + return cxx_allocator().New( std::forward(args)...); }, update_flags::allow_insert ) == update_flags::result_insert; @@ -253,12 +276,16 @@ namespace cds { namespace container { std::pair update( K const& key, Func func ) { int result = base_class::do_update( key, key_comparator(), - [&func]( base_node_type * pNode ) -> mapped_type* + [&func]( node_type * pNode ) -> mapped_type* { - node_type * p = static_cast(pNode); - //new (&p->m_data) mapped_type; - func( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr, p->m_data ); - return &p->m_data; + mapped_type * pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed )); + if ( !pVal ) { + pVal = cxx_allocator().New(); + func( true, pVal ); + } + else + func( false, pVal ); + return pVal; }, update_flags::allow_insert | update_flags::allow_update ); diff --git a/cds/container/details/bronson_avltree_base.h b/cds/container/details/bronson_avltree_base.h index 621a38b9..77f77ef7 100644 --- a/cds/container/details/bronson_avltree_base.h +++ b/cds/container/details/bronson_avltree_base.h @@ -6,7 +6,7 @@ #include #include #include -#include +#include namespace cds { namespace container { @@ -252,7 +252,7 @@ namespace cds { namespace container { typedef opt::none less; /// Allocator for internal node - typedef CDS_DEFAULT_ALLOCATOR allocator; + typedef CDS_DEFAULT_ALLOCATOR node_allocator; /// Disposer (only for pointer-oriented tree specialization) /** @@ -302,11 +302,6 @@ namespace cds { namespace container { List of available options see \p opt::rcu_check_deadlock */ typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock; - - //@cond - // Internal traits, not for direct usage - typedef opt::none node_type; - //@endcond }; /// Metafunction converting option list to BronsonAVLTreeMap traits @@ -321,7 +316,7 @@ namespace cds { namespace container { - \p opt::compare - key compare functor. No default functor is provided. If the option is not specified, \p %opt::less is used. - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined. - - \p opt::allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR. + - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR. - \ref cds::intrusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values. The user-provided disposer is used only for pointer-oriented tree specialization like \p BronsonAVLTreeMap. When the node becomes the rounting node without value, diff --git a/cds/container/impl/bronson_avltree_map_rcu.h b/cds/container/impl/bronson_avltree_map_rcu.h index 98e113bd..ac594480 100644 --- a/cds/container/impl/bronson_avltree_map_rcu.h +++ b/cds/container/impl/bronson_avltree_map_rcu.h @@ -57,7 +57,7 @@ namespace cds { namespace container { #endif typedef typename traits::item_counter item_counter; ///< Item counting policy typedef typename traits::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model option - typedef typename traits::allocator allocator_type; ///< allocator for maintaining internal node + typedef typename traits::node_allocator node_allocator_type; ///< allocator for maintaining internal nodes typedef typename traits::stat stat; ///< internal statistics typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy typedef typename traits::back_off back_off; ///< Back-off strategy @@ -72,15 +72,7 @@ namespace cds { namespace container { typedef bronson_avltree::node< key_type, mapped_type, lock_type > node_type; typedef typename node_type::version_type version_type; - typedef typename std::conditional < - std::is_same< typename traits::node_type, opt::none >::value, - bronson_avltree::node< key_type, mapped_type, lock_type >, - typename traits::node_type - >::type alloc_node_type; - - typedef typename allocator_type::template rebind::other memory_allocator; - typedef cds::details::Allocator< alloc_node_type, memory_allocator > cxx_allocator; - + typedef cds::details::Allocator< node_type, node_allocator_type > cxx_allocator; typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock > check_deadlock_policy; enum class find_result @@ -131,14 +123,13 @@ namespace cds { namespace container { template static node_type * alloc_node( K&& key, int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight ) { - alloc_node_type * pNode = memory_allocator().allocate( 1 ); - return new (static_cast(pNode)) node_type( std::forward( key ), nHeight, version, pParent, pLeft, pRight ); + return cxx_allocator().New( std::forward( key ), nHeight, version, pParent, pLeft, pRight ); } - static void internal_free_node( node_type * pNode ) + static void free_node( node_type * pNode ) { // Free node without disposer - cxx_allocator().Delete( static_cast(pNode) ); + cxx_allocator().Delete( pNode ); } // RCU safe disposer @@ -171,10 +162,9 @@ namespace cds { namespace container { private: struct internal_disposer { - void operator()( alloc_node_type * p ) const + void operator()( node_type * p ) const { - static_cast(p)->~node_type(); - memory_allocator().deallocate( p, 1 ); + free_node( p ); } }; @@ -185,7 +175,7 @@ namespace cds { namespace container { for ( node_type * p = m_pRetiredList; p; ) { node_type * pNext = p->m_pNextRemoved; // Value already disposed - gc::template retire_ptr( static_cast(p) ); + gc::template retire_ptr( p ); p = pNext; } } @@ -793,7 +783,7 @@ namespace cds { namespace container { || pNode->child( nDir ).load( memory_model::memory_order_relaxed ) != nullptr ) { if ( c_RelaxedInsert ) { - internal_free_node( pNew ); + free_node( pNew ); m_stat.onRelaxedInsertFailed(); } -- 2.34.1