From f735e203b6ff079f3ab0854f7859f4ddd2ec1f21 Mon Sep 17 00:00:00 2001
From: khizmax <khizmax@gmail.com>
Date: Tue, 10 Feb 2015 20:03:24 +0300
Subject: [PATCH] Added possibility to remove node's value via RCU disposing
 cycle

---
 cds/container/details/bronson_avltree_base.h | 27 ++++++-
 cds/container/impl/bronson_avltree_map_rcu.h | 74 +++++++++++++++++++-
 2 files changed, 97 insertions(+), 4 deletions(-)

diff --git a/cds/container/details/bronson_avltree_base.h b/cds/container/details/bronson_avltree_base.h
index 4d64ce65..ca9540ec 100644
--- a/cds/container/details/bronson_avltree_base.h
+++ b/cds/container/details/bronson_avltree_base.h
@@ -128,11 +128,13 @@ namespace cds { namespace container {
         };
         //@endcond
 
-        // BronsonAVLTree internal node
+        /// BronsonAVLTree internal node
         template <typename Key, typename T, typename SyncMonitor >
         struct node<Key, T*, SyncMonitor>: public link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor >
         {
+            //@cond
             typedef link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor > base_class;
+            //@endcond
 
             typedef Key key_type;       ///< key type
             typedef T   mapped_type;    ///< value type
@@ -159,6 +161,29 @@ namespace cds { namespace container {
             //@endcond
         };
 
+        /// Base value type for BronsonAVLTreeMap
+        /**
+            If value type for \p BronsonAVLTreeMap is based on this struct,
+            the map will support some additional methods like \p BronsonAVLTreeMap::get().
+            Moreover, the disposer behaviour is different for ordinal values and
+            values based on \p %bronson_avltree::value:
+            - for ordinal value, its disposer is called immediately after removing
+              the node from the tree. It this case it is not possible to support
+              map's methods that return raw pointer to the tree's value.
+            - if the value type is based on \p %bronson_avltree::value, 
+              i.e. \p std::is_base_of( bronson_avltree::value, value_type )::value is \p true,
+              the disposer is called via full RCU cycle. It means that under 
+              RCU lock the methods returning raw pointer can be implemented.
+        */
+        struct value
+        {
+            value *     m_pNextRetired;
+            
+            value()
+                : m_pNextRetired(nullptr)
+            {}
+        };
+
         /// BronsonAVLTreeMap internal statistics
         template <typename Counter = cds::atomicity::event_counter>
         struct stat {
diff --git a/cds/container/impl/bronson_avltree_map_rcu.h b/cds/container/impl/bronson_avltree_map_rcu.h
index 5db8ec47..d13dd9bc 100644
--- a/cds/container/impl/bronson_avltree_map_rcu.h
+++ b/cds/container/impl/bronson_avltree_map_rcu.h
@@ -4,6 +4,7 @@
 #define CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H
 
 #include <memory> // unique_ptr
+#include <type_traits> // is_base_of
 #include <cds/container/details/bronson_avltree_base.h>
 #include <cds/urcu/details/check_deadlock.h>
 
@@ -78,6 +79,8 @@ namespace cds { namespace container {
 
         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;
+        
+        static CDS_CONSTEXPR bool const c_bRetiringValue = std::is_base_of< bronson_avltree::value, typename std::remove_pointer<mapped_type>::type>::value;
 
         enum class find_result
         {
@@ -146,10 +149,66 @@ namespace cds { namespace container {
             return pNode->m_pParent.load( order );
         }
 
-        // RCU safe disposer for node
+        
+        template <bool Enabled>
+        class rcu_value_disposer;
+        
+        template <>
+        class rcu_value_disposer<true>
+        {
+            bronson_avltree::value *    m_pValueRetiredList; ///< head of retired value list
+        public:
+            rcu_value_disposer()
+                : m_pValueRetiredList(nullptr)
+            {}
+            
+            ~rcu_value_disposer()
+            {
+                clean();
+            }
+            
+            void dispose( mapped_type pVal )
+            {
+                assert( pVal );
+                static_cast< bronson_avltree::value *>(pVal)->m_pNextRetired = m_pValueRetiredList;
+                m_pValueRetiredList = static_cast< bronson_avltree::value *>(pVal);
+            }
+            
+        private:
+            struct internal_disposer
+            {
+                void operator()( bronson_avltree::value * p ) const
+                {
+                    free_value( static_cast<mapped_type>( p ));
+                }
+            };
+            
+            void clean()
+            {
+                // TODO: use RCU::batch_retire
+                for ( auto p = m_pValueRetiredList; p; ) {
+                    auto pNext = p->m_pNextRetired;
+                    gc::template retire_ptr<internal_disposer>( p );
+                    p = pNext;
+                }
+            }
+        };
+        
+        template <>
+        class rcu_value_disposer<false>
+        {
+        public:
+            void dispose( mapped_type pVal )
+            {
+                free_value( pVal );
+            }
+        };
+        
+        // RCU safe disposer 
         class rcu_disposer
         {
-            node_type *     m_pRetiredList; ///< head of retired list
+            node_type *     m_pRetiredList; ///< head of retired node list
+            rcu_value_disposer< c_bRetiringValue > m_RetiredValueList;
 
         public:
             rcu_disposer()
@@ -167,7 +226,12 @@ namespace cds { namespace container {
                 pNode->m_pNextRemoved = m_pRetiredList;
                 m_pRetiredList = pNode;
             }
-
+            
+            void dispose_value( mapped_type pVal )
+            {
+                m_RetiredValueList.dispose( pVal );
+            }
+            
         private:
             struct internal_disposer
             {
@@ -180,7 +244,10 @@ namespace cds { namespace container {
             void clean()
             {
                 assert( !gc::is_locked() );
+                
+                // TODO: use RCU::batch_retire
 
+                // Dispose nodes
                 for ( node_type * p = m_pRetiredList; p; ) {
                     node_type * pNext = static_cast<node_type *>( p->m_pNextRemoved );
                     // Value already disposed
@@ -559,6 +626,7 @@ namespace cds { namespace container {
         */
         void unsafe_clear()
         {
+            clear(); // temp solution
             //TODO
         }
 
-- 
2.34.1