projects / libcds.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
issue #76: added cds::atomicity::cache_friendly_item_counter to avoid false sharing
[libcds.git] / cds / intrusive / details / ellen_bintree_base.h
diff --git a/cds/intrusive/details/ellen_bintree_base.h b/cds/intrusive/details/ellen_bintree_base.h
index 551ef3e81319a75decaa8fd7696916d9ad174c81..ed03e3b8ca28196aa8df57596503789a432bd18e 100644 (file)
--- a/cds/intrusive/details/ellen_bintree_base.h
+++ b/cds/intrusive/details/ellen_bintree_base.h
@@ -1,7 +1,7 @@
 /*
     This file is a part of libcds - Concurrent Data Structures library
 
-    (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+    (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
@@ -105,7 +105,7 @@ namespace cds { namespace intrusive {
         };
 
         //@cond
-        struct basic_node
+        struct alignas( void* ) basic_node
         {
             enum flags {
                 internal        = 1,    ///< set for internal node
@@ -119,8 +119,9 @@ namespace cds { namespace intrusive {
 
             /// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node
             explicit basic_node( bool bInternal )
-                : m_nFlags( bInternal ? internal : 0 )
-            {}
+            {
+                m_nFlags.store( bInternal ? internal: 0, atomics::memory_order_release );
+            }
 
             /// Checks if the node is a leaf
             bool is_leaf() const
@@ -168,6 +169,7 @@ namespace cds { namespace intrusive {
             typedef basic_node base_class;
 
             typedef GC              gc       ;   ///< Garbage collector
+
             /// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node
             explicit base_node( bool bInternal )
                 : base_class( bInternal )
@@ -232,7 +234,7 @@ namespace cds { namespace intrusive {
             atomics::atomic<base_class *> m_pRight;  ///< Right subtree
             atomics::atomic<update_ptr>   m_pUpdate; ///< Update descriptor
             //@cond
-            uintptr_t  m_nEmptyUpdate; ///< ABA prevention for m_pUpdate, from 0..2^16 step 4
+            atomics::atomic<uintptr_t>    m_nEmptyUpdate; ///< ABA prevention for m_pUpdate, from 0..2^16 step 4
             //@endcond
 
             /// Default ctor
@@ -240,14 +242,15 @@ namespace cds { namespace intrusive {
                 : base_class( true )
                 , m_pLeft( nullptr )
                 , m_pRight( nullptr )
-                , m_pUpdate( update_ptr() )
-                , m_nEmptyUpdate(0)
-            {}
+                , m_pUpdate( update_ptr())
+            {
+                m_nEmptyUpdate.store( 0, atomics::memory_order_release );
+            }
 
             //@cond
             update_ptr null_update_desc()
             {
-                return update_ptr( reinterpret_cast<update_desc_type *>( (++m_nEmptyUpdate << 2) & 0xFFFF ) );
+                return update_ptr( reinterpret_cast<update_desc_type *>( ((m_nEmptyUpdate.fetch_add(1, atomics::memory_order_relaxed) + 1 ) << 2) & 0xFFFF ));
             }
 
             base_class * get_child( bool bRight, atomics::memory_order mo ) const
@@ -512,7 +515,7 @@ namespace cds { namespace intrusive {
             /// Item counter
             /**
                 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
-                To enable it use \p atomicity::item_counter
+                To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
             */
             typedef atomicity::empty_item_counter item_counter;
 
@@ -528,9 +531,9 @@ namespace cds { namespace intrusive {
 
                 Update descriptor is helping data structure with short lifetime and it is good candidate
                 for pooling. The number of simultaneously existing descriptors is bounded and it is
-                limited the number of threads working with the tree.
+                limited by number of threads working with the tree.
                 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue
-                is good choice for the free-list of update descriptors,
+                is a good choice for the free-list of update descriptors,
                 see \p cds::memory::vyukov_queue_pool free-list implementation.
 
                 Also notice that size of update descriptor is constant and not dependent on the type of data
@@ -579,7 +582,7 @@ namespace cds { namespace intrusive {
             - \p opt::disposer - the functor used for dispose removed nodes. Default is \p opt::v::empty_disposer. Due the nature
                 of GC schema the disposer may be called asynchronously. The disposer is used only for leaf nodes.
             - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
-                To enable it use \p atomicity::item_counter
+                To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
             - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
@@ -629,9 +632,9 @@ namespace cds { namespace intrusive {
                 template <typename LeafNode>
                 int operator()( internal_node<key_type, LeafNode> const& n1, internal_node<key_type, LeafNode> const& n2 ) const
                 {
-                    if ( n1.infinite_key() )
+                    if ( n1.infinite_key())
                         return n2.infinite_key() ? n1.infinite_key() - n2.infinite_key() : 1;
-                    else if ( n2.infinite_key() )
+                    else if ( n2.infinite_key())
                         return -1;
                     return operator()( n1.m_Key, n2.m_Key );
                 }
@@ -639,7 +642,7 @@ namespace cds { namespace intrusive {
                 template <typename LeafNode, typename Q>
                 int operator()( internal_node<key_type, LeafNode> const& n, Q const& v ) const
                 {
-                    if ( n.infinite_key() )
+                    if ( n.infinite_key())
                         return 1;
                     return operator()( n.m_Key, v );
                 }
@@ -647,7 +650,7 @@ namespace cds { namespace intrusive {
                 template <typename LeafNode, typename Q>
                 int operator()( Q const& v, internal_node<key_type, LeafNode> const& n ) const
                 {
-                    if ( n.infinite_key() )
+                    if ( n.infinite_key())
                         return -1;
                     return operator()( v, n.m_Key );
                 }
@@ -655,7 +658,7 @@ namespace cds { namespace intrusive {
                 template <typename GC, typename Tag>
                 int operator()( node<GC, Tag> const& n1, node<GC, Tag> const& n2 ) const
                 {
-                    if ( n1.infinite_key() != n2.infinite_key() )
+                    if ( n1.infinite_key() != n2.infinite_key())
                         return n1.infinite_key() - n2.infinite_key();
                     return operator()( *node_traits::to_value_ptr( n1 ), *node_traits::to_value_ptr( n2 ));
                 }
@@ -663,7 +666,7 @@ namespace cds { namespace intrusive {
                 template <typename GC, typename Tag, typename Q>
                 int operator()( node<GC, Tag> const& n, Q const& v ) const
                 {
-                    if ( n.infinite_key() )
+                    if ( n.infinite_key())
                         return 1;
                     return operator()( *node_traits::to_value_ptr( n ), v );
                 }
@@ -671,24 +674,24 @@ namespace cds { namespace intrusive {
                 template <typename GC, typename Tag, typename Q>
                 int operator()( Q const& v, node<GC, Tag> const& n ) const
                 {
-                    if ( n.infinite_key() )
+                    if ( n.infinite_key())
                         return -1;
-                    return operator()( v, *node_traits::to_value_ptr( n ) );
+                    return operator()( v, *node_traits::to_value_ptr( n ));
                 }
 
                 template <typename GC>
                 int operator()( base_node<GC> const& n1, base_node<GC> const& n2 ) const
                 {
-                    if ( n1.infinite_key() != n2.infinite_key() )
+                    if ( n1.infinite_key() != n2.infinite_key())
                         return n1.infinite_key() - n2.infinite_key();
-                    if ( n1.is_leaf() ) {
-                        if ( n2.is_leaf() )
+                    if ( n1.is_leaf()) {
+                        if ( n2.is_leaf())
                             return operator()( node_traits::to_leaf_node( n1 ), node_traits::to_leaf_node( n2 ));
                         else
                             return operator()( node_traits::to_leaf_node( n1 ), node_traits::to_internal_node( n2 ));
                     }
 
-                    if ( n2.is_leaf() )
+                    if ( n2.is_leaf())
                         return operator()( node_traits::to_internal_node( n1 ), node_traits::to_leaf_node( n2 ));
                     else
                         return operator()( node_traits::to_internal_node( n1 ), node_traits::to_internal_node( n2 ));
@@ -699,7 +702,7 @@ namespace cds { namespace intrusive {
                 {
                     if ( n.infinite_key())
                         return 1;
-                    if ( n.is_leaf() )
+                    if ( n.is_leaf())
                         return operator()( node_traits::to_leaf_node( n ), v );
                     return operator()( node_traits::to_internal_node( n ), v );
                 }
@@ -713,7 +716,7 @@ namespace cds { namespace intrusive {
                 template <typename GC, typename LeafNode >
                 int operator()( base_node<GC> const& i, internal_node<key_type, LeafNode> const& n ) const
                 {
-                    if ( i.is_leaf() )
+                    if ( i.is_leaf())
                         return operator()( static_cast<LeafNode const&>(i), n );
                     return operator()( static_cast<internal_node<key_type, LeafNode> const&>(i), n );
                 }
@@ -727,8 +730,8 @@ namespace cds { namespace intrusive {
                 template <typename GC, typename Tag >
                 int operator()( node<GC, Tag> const& n, internal_node<key_type, node<GC, Tag> > const& i ) const
                 {
-                    if ( !n.infinite_key() ) {
-                        if ( i.infinite_key() )
+                    if ( !n.infinite_key()) {
+                        if ( i.infinite_key())
                             return -1;
                         return operator()( n, i.m_Key );
                     }
Unnamed repository; edit this file 'description' to name the repository.