Bronson's AVL-tree: add extract_min/max

[libcds.git] / cds / container / details / bronson_avltree_base.h

diff --git a/cds/container/details/bronson_avltree_base.h b/cds/container/details/bronson_avltree_base.h
index faa127eab9f5c75744512e16225f4dda9695e93a..4d64ce6598a6aa76ff0613e385524865ac1954c2 100644 (file)
--- a/cds/container/details/bronson_avltree_base.h
+++ b/cds/container/details/bronson_avltree_base.h
@@ -14,14 +14,15 @@ namespace cds { namespace container {
     /// BronsonAVLTree related declarations
     namespace bronson_avltree {
 
-        template <typename Key, typename T>
+        template <typename Key, typename T, typename SyncMonitor >
         struct node;
 
         //@cond
-        template <typename Node>
+        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
@@ -37,6 +38,8 @@ namespace cds { namespace container {
             atomics::atomic<node_type *>    m_pParent;  ///< Parent node
             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
@@ -46,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 )
@@ -54,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 )
@@ -108,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>
-        struct node<Key, T*>: public link_node< node<Key, T*>>
+        template <typename Key, typename T, typename SyncMonitor >
+        struct node<Key, T*, SyncMonitor>: public link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor >
         {
-            typedef link_node< node<Key, T*>> 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:
@@ -132,7 +147,6 @@ namespace cds { namespace container {
             node( Q&& key )
                 : base_class()
                 , m_key( std::forward<Q>( key ) )
-                , m_pValue( nullptr )
                 , m_pNextRemoved( nullptr )
             {}
 
@@ -140,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
         };
 
@@ -168,12 +172,22 @@ namespace cds { namespace container {
             event_counter   m_nInsertSuccess;       ///< Count of inserting data node
             event_counter   m_nRelaxedInsertFailed; ///< Count of false creating of data nodes (only if @ref bronson_avltree::relaxed_insert "relaxed insertion" is enabled)
             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_nUpdateWaitShrinking; ///< Count of waiting until shrinking completed during \p update() call
             event_counter   m_nUpdateRetry;         ///< Count of update retries via concurrent operations
             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_nDisposedNode;        ///< Count of disposed node
+            event_counter   m_nDisposedValue;       ///< Count of disposed value
+            event_counter   m_nExtractedValue;      ///< Count of extracted value
+            event_counter   m_nRemoveRetry;         ///< Count o erase/extract retries
+            event_counter   m_nRemoveWaitShrinking; ///< ount of waiting until shrinking completed during \p erase() or \p extract() call
+            event_counter   m_nRemoveRootWaitShrinking;  ///< Count of waiting until root shrinking completed duting \p erase() or \p extract() call
+
+            event_counter   m_nRightRotation;       ///< Count of single right rotation
+            event_counter   m_nLeftRotation;        ///< Count of single left rotation
+            event_counter   m_nLeftRightRotation;   ///< Count of double left-over-right rotation
+            event_counter   m_nRightLeftRotation;   ///< Count of double right-over-left rotation
 
             //@cond
             void onFindSuccess()        { ++m_nFindSuccess      ; }
@@ -190,7 +204,15 @@ namespace cds { namespace container {
             void onUpdateSuccess()          { ++m_nUpdateSuccess;  }
             void onUpdateUnlinked()         { ++m_nUpdateUnlinked; }
             void onDisposeNode()            { ++m_nDisposedNode; }
-
+            void onDisposeValue()           { ++m_nDisposedValue; }
+            void onExtractValue()           { ++m_nExtractedValue; }
+            void onRemoveRetry()            { ++m_nRemoveRetry; }
+            void onRemoveWaitShrinking()    { ++m_nRemoveWaitShrinking; }
+
+            void onRotateRight()            { ++m_nRightRotation; }
+            void onRotateLeft()             { ++m_nLeftRotation; }
+            void onRotateRightOverLeft()    { ++m_nRightLeftRotation; }
+            void onRotateLeftOverRight()    { ++m_nLeftRghtRotation; }
             //@endcond
         };
 
@@ -211,7 +233,16 @@ namespace cds { namespace container {
             void onUpdateSuccess()          const {}
             void onUpdateUnlinked()         const {}
             void onDisposeNode()            const {}
-
+            void onDisposeValue()           const {}
+            void onExtractValue()           const {}
+            void onRemoveRetry()            const {}
+            void onRemoveWaitShrinking()    const {}
+            void onRemoveRootWaitShrinking() const {}
+
+            void onRotateRight()            const {}
+            void onRotateLeft()             const {}
+            void onRotateRightOverLeft()    const {}
+            void onRotateLeftOverRight()    const {}
             //@endcond
         };