cds/container/impl/bronson_avltree_map_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H
   4 #define CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H
   5
   6 #include <type_traits> // is_base_of
   7 #include <cds/container/details/bronson_avltree_base.h>
   8 #include <cds/urcu/details/check_deadlock.h>
   9 #include <cds/urcu/exempt_ptr.h>
  10
  11 namespace cds { namespace container {
  12
  13     /// Bronson et al AVL-tree (RCU specialization for storing pointer to values)
  14     /** @ingroup cds_nonintrusive_map
  15         @ingroup cds_nonintrusive_tree
  16         @headerfile cds/container/bronson_avltree_map_rcu.h
  17         @anchor cds_container_BronsonAVLTreeMap_rcu_ptr
  18
  19         This is the specialization of \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based Bronson et al AVL-tree"
  20         for "key -> value pointer" map. This specialization stores the pointer to user-allocated values instead of the copy
  21         of the value. When a tree node is removed, the algorithm does not free the value pointer directly, instead, it call
  22         the disposer functor provided by \p Traits template parameter.
  23
  24         <b>Template arguments</b>:
  25         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  26         - \p Key - key type
  27         - \p T - value type to be stored in tree's nodes. Note, the specialization stores the pointer to user-allocated
  28             value, not the copy.
  29         - \p Traits - tree traits, default is \p bronson_avltree::traits
  30             It is possible to declare option-based tree with \p bronson_avltree::make_traits metafunction
  31             instead of \p Traits template argument.
  32
  33         @note Before including <tt><cds/container/bronson_avltree_map_rcu.h></tt> you should include appropriate RCU header file,
  34         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  35     */
  36     template <
  37         typename RCU,
  38         typename Key,
  39         typename T,
  40 #   ifdef CDS_DOXYGEN_INVOKED
  41         typename Traits = bronson_avltree::traits
  42 #else
  43         typename Traits
  44 #endif
  45     >
  46     class BronsonAVLTreeMap< cds::urcu::gc<RCU>, Key, T*, Traits >
  47     {
  48     public:
  49         typedef cds::urcu::gc<RCU>  gc;   ///< RCU Garbage collector
  50         typedef Key     key_type;    ///< type of a key stored in the map
  51         typedef T *     mapped_type; ///< type of value stored in the map
  52         typedef Traits  traits;      ///< Traits template parameter
  53
  54 #   ifdef CDS_DOXYGEN_INVOKED
  55         typedef implementation_defined key_comparator;    ///< key compare functor based on \p Traits::compare and \p Traits::less
  56 #   else
  57         typedef typename opt::details::make_comparator< key_type, traits >::type key_comparator;
  58 #endif
  59         typedef typename traits::item_counter           item_counter;       ///< Item counting policy
  60         typedef typename traits::memory_model           memory_model;       ///< Memory ordering, see \p cds::opt::memory_model option
  61         typedef typename traits::node_allocator         node_allocator_type; ///< allocator for maintaining internal nodes
  62         typedef typename traits::stat                   stat;               ///< internal statistics
  63         typedef typename traits::rcu_check_deadlock     rcu_check_deadlock; ///< Deadlock checking policy
  64         typedef typename traits::back_off               back_off;           ///< Back-off strategy
  65         typedef typename traits::disposer               disposer;           ///< Value disposer
  66         typedef typename traits::sync_monitor           sync_monitor;       ///< @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
  67
  68         /// Enabled or disabled @ref bronson_avltree::relaxed_insert "relaxed insertion"
  69         static CDS_CONSTEXPR bool const c_bRelaxedInsert = traits::relaxed_insert;
  70
  71 #   ifdef CDS_DOXYGEN_INVOKED
  72         /// Returned pointer to \p mapped_type of extracted node
  73         typedef cds::urcu::exempt_ptr< gc, T, T, disposer, void > exempt_ptr;
  74 #   else
  75         typedef cds::urcu::exempt_ptr< gc,
  76             typename std::remove_pointer<mapped_type>::type,
  77             typename std::remove_pointer<mapped_type>::type,
  78             disposer,
  79             void
  80         > exempt_ptr;
  81 #   endif
  82
  83         typedef typename gc::scoped_lock    rcu_lock;  ///< RCU scoped lock
  84
  85     protected:
  86         //@cond
  87         typedef bronson_avltree::node< key_type, mapped_type, sync_monitor > node_type;
  88         typedef typename node_type::version_type version_type;
  89
  90         typedef cds::details::Allocator< node_type, node_allocator_type > cxx_allocator;
  91         typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock >   check_deadlock_policy;
  92
  93         enum class find_result
  94         {
  95             not_found,
  96             found,
  97             retry
  98         };
  99
 100         struct update_flags
 101         {
 102             enum {
 103                 allow_insert = 1,
 104                 allow_update = 2,
 105                 //allow_remove = 4,
 106
 107                 retry = 1024,
 108
 109                 failed = 0,
 110                 result_inserted = allow_insert,
 111                 result_updated = allow_update,
 112                 result_removed = 4
 113             };
 114         };
 115
 116         enum node_condition
 117         {
 118             nothing_required = -3,
 119             rebalance_required = -2,
 120             unlink_required = -1
 121         };
 122
 123         enum direction {
 124             left_child = -1,
 125             right_child = 1
 126         };
 127
 128         typedef typename sync_monitor::template scoped_lock<node_type> node_scoped_lock;
 129         //@endcond
 130
 131     protected:
 132         //@cond
 133         template <typename K>
 134         static node_type * alloc_node( K&& key, int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight )
 135         {
 136             return cxx_allocator().New( std::forward<K>( key ), nHeight, version, pParent, pLeft, pRight );
 137         }
 138
 139         static void free_node( node_type * pNode )
 140         {
 141             // Free node without disposer
 142             cxx_allocator().Delete( pNode );
 143         }
 144
 145         static void free_value( mapped_type pVal )
 146         {
 147             disposer()(pVal);
 148         }
 149
 150         static node_type * child( node_type * pNode, int nDir, atomics::memory_order order )
 151         {
 152             return pNode->child( nDir ).load( order );
 153         }
 154
 155         static node_type * parent( node_type * pNode, atomics::memory_order order )
 156         {
 157             return pNode->m_pParent.load( order );
 158         }
 159
 160         // RCU safe disposer
 161         class rcu_disposer
 162         {
 163             node_type *     m_pRetiredList;     ///< head of retired node list
 164             mapped_type     m_pRetiredValue;    ///< value retired
 165
 166         public:
 167             rcu_disposer()
 168                 : m_pRetiredList( nullptr )
 169                 , m_pRetiredValue( nullptr )
 170             {}
 171
 172             ~rcu_disposer()
 173             {
 174                 clean();
 175             }
 176
 177             void dispose( node_type * pNode )
 178             {
 179                 assert( !pNode->is_valued( memory_model::memory_order_relaxed ));
 180                 pNode->m_pNextRemoved = m_pRetiredList;
 181                 m_pRetiredList = pNode;
 182             }
 183
 184             void dispose_value( mapped_type pVal )
 185             {
 186                 assert( m_pRetiredValue == nullptr );
 187                 m_pRetiredValue = pVal;
 188             }
 189
 190         private:
 191             struct internal_disposer
 192             {
 193                 void operator()( node_type * p ) const
 194                 {
 195                     free_node( p );
 196                 }
 197             };
 198
 199             void clean()
 200             {
 201                 assert( !gc::is_locked() );
 202
 203                 // TODO: use RCU::batch_retire
 204
 205                 // Dispose nodes
 206                 for ( node_type * p = m_pRetiredList; p; ) {
 207                     node_type * pNext = static_cast<node_type *>( p->m_pNextRemoved );
 208                     // Value already disposed
 209                     gc::template retire_ptr<internal_disposer>( p );
 210                     p = pNext;
 211                 }
 212
 213                 // Dispose value
 214                 if ( m_pRetiredValue  )
 215                     gc::template retire_ptr<disposer>( m_pRetiredValue );
 216             }
 217         };
 218
 219         //@endcond
 220
 221     protected:
 222         //@cond
 223         typename node_type::base_class m_Root;
 224         node_type *             m_pRoot;
 225         item_counter            m_ItemCounter;
 226         mutable sync_monitor    m_Monitor;
 227         mutable stat            m_stat;
 228         //@endcond
 229
 230     public:
 231         /// Creates empty map
 232         BronsonAVLTreeMap()
 233             : m_pRoot( static_cast<node_type *>( &m_Root ))
 234         {}
 235
 236         /// Destroys the map
 237         ~BronsonAVLTreeMap()
 238         {
 239             unsafe_clear();
 240         }
 241
 242         /// Inserts new node
 243         /**
 244             The \p key_type should be constructible from a value of type \p K.
 245
 246             RCU \p synchronize() can be called. RCU should not be locked.
 247
 248             Returns \p true if inserting successful, \p false otherwise.
 249         */
 250         template <typename K>
 251         bool insert( K const& key, mapped_type pVal )
 252         {
 253             return do_update(key, key_comparator(),
 254                 [pVal]( node_type * pNode ) -> mapped_type
 255                 {
 256                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 257                     return pVal;
 258                 },
 259                 update_flags::allow_insert
 260             ) == update_flags::result_inserted;
 261         }
 262
 263         /// Updates the value for \p key
 264         /**
 265             The operation performs inserting or updating the value for \p key with lock-free manner.
 266             If \p bInsert is \p false, only updating of existing node is possible.
 267
 268             If \p key is not found and inserting is allowed (i.e. \p bInsert is \p true),
 269             then the new node created from \p key will be inserted into the map; note that in this case the \ref key_type should be
 270             constructible from type \p K.
 271             Otherwise, the value for \p key will be changed to \p pVal.
 272
 273             RCU \p synchronize() method can be called. RCU should not be locked.
 274
 275             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
 276             \p second is \p true if new node has been added or \p false if the node with \p key
 277             already exists.
 278         */
 279         template <typename K, typename Func>
 280         std::pair<bool, bool> update( K const& key, mapped_type pVal, bool bInsert = true )
 281         {
 282             int result = do_update( key, key_comparator(),
 283                 [pVal]( node_type * ) -> mapped_type
 284                 {
 285                     return pVal;
 286                 },
 287                 update_flags::allow_update | (bInsert ? update_flags::allow_insert : 0)
 288             );
 289             return std::make_pair( result != 0, (result & update_flags::result_inserted) != 0 );
 290         }
 291
 292         /// Delete \p key from the map
 293         /**
 294             RCU \p synchronize() method can be called. RCU should not be locked.
 295
 296             Return \p true if \p key is found and deleted, \p false otherwise
 297         */
 298         template <typename K>
 299         bool erase( K const& key )
 300         {
 301             return do_remove(
 302                 key,
 303                 key_comparator(),
 304                 []( key_type const&, mapped_type pVal, rcu_disposer& disp ) -> bool { disp.dispose_value( pVal ); return true; }
 305             );
 306         }
 307
 308         /// Deletes the item from the map using \p pred predicate for searching
 309         /**
 310             The function is an analog of \p erase(K const&)
 311             but \p pred is used for key comparing.
 312             \p Less functor has the interface like \p std::less.
 313             \p Less must imply the same element order as the comparator used for building the map.
 314         */
 315         template <typename K, typename Less>
 316         bool erase_with( K const& key, Less pred )
 317         {
 318             CDS_UNUSED( pred );
 319             return do_remove(
 320                 key,
 321                 cds::opt::details::make_comparator_from_less<Less>(),
 322                 []( key_type const&, mapped_type pVal, rcu_disposer& disp ) -> bool { disp.dispose_value( pVal ); return true;  }
 323             );
 324         }
 325
 326         /// Delete \p key from the map
 327         /**
 328             The function searches an item with key \p key, calls \p f functor
 329             and deletes the item. If \p key is not found, the functor is not called.
 330
 331             The functor \p Func interface:
 332             \code
 333             struct extractor {
 334                 void operator()(mapped_type& item) { ... }
 335             };
 336             \endcode
 337
 338             RCU \p synchronize method can be called. RCU should not be locked.
 339
 340             Return \p true if key is found and deleted, \p false otherwise
 341         */
 342         template <typename K, typename Func>
 343         bool erase( K const& key, Func f )
 344         {
 345             return do_remove(
 346                 key,
 347                 key_comparator(),
 348                 [&f]( key_type const&, mapped_type pVal, rcu_disposer& disp ) -> bool {
 349                     assert( pVal );
 350                     f( *pVal );
 351                     disp.dispose_value(pVal);
 352                     return true;
 353                 }
 354             );
 355         }
 356
 357         /// Deletes the item from the map using \p pred predicate for searching
 358         /**
 359             The function is an analog of \p erase(K const&, Func)
 360             but \p pred is used for key comparing.
 361             \p Less functor has the interface like \p std::less.
 362             \p Less must imply the same element order as the comparator used for building the map.
 363         */
 364         template <typename K, typename Less, typename Func>
 365         bool erase_with( K const& key, Less pred, Func f )
 366         {
 367             CDS_UNUSED( pred );
 368             return do_remove(
 369                 key,
 370                 cds::opt::details::make_comparator_from_less<Less>(),
 371                 [&f]( key_type const&, mapped_type pVal, rcu_disposer& disp ) -> bool {
 372                     assert( pVal );
 373                     f( *pVal );
 374                     disp.dispose_value(pVal);
 375                     return true;
 376                 }
 377             );
 378         }
 379
 380         /// Extracts a value with minimal key from the map
 381         /**
 382             Returns \p exempt_ptr to the leftmost item.
 383             If the tree is empty, returns empty \p exempt_ptr.
 384
 385             Note that the function returns only the value for minimal key.
 386             To retrieve its key use \p extract_min( Func ) member function.
 387
 388             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
 389             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 390             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 391             So, the function returns the item with minimum key at the moment of tree traversing.
 392
 393             RCU \p synchronize method can be called. RCU should NOT be locked.
 394             The function does not free the item.
 395             The deallocator will be implicitly invoked when the returned object is destroyed or when
 396             its \p release() member function is called.
 397         */
 398         exempt_ptr extract_min()
 399         {
 400             return exempt_ptr(do_extract_min( []( key_type const& ) {}));
 401         }
 402
 403         /// Extracts minimal key key and corresponding value
 404         /**
 405             Returns \p exempt_ptr to the leftmost item.
 406             If the tree is empty, returns empty \p exempt_ptr.
 407
 408             \p Func functor is used to store minimal key.
 409             \p Func has the following signature:
 410             \code
 411             struct functor {
 412                 void operator()( key_type const& key );
 413             };
 414             \endcode
 415             If the tree is empty, \p f is not called.
 416             Otherwise, is it called with minimal key, the pointer to corresponding value is returned
 417             as \p exempt_ptr.
 418
 419             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
 420             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 421             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 422             So, the function returns the item with minimum key at the moment of tree traversing.
 423
 424             RCU \p synchronize method can be called. RCU should NOT be locked.
 425             The function does not free the item.
 426             The deallocator will be implicitly invoked when the returned object is destroyed or when
 427             its \p release() member function is called.
 428         */
 429         template <typename Func>
 430         exempt_ptr extract_min( Func f )
 431         {
 432             return exempt_ptr(do_extract_min( [&f]( key_type const& key ) { f(key); }));
 433         }
 434
 435         /// Extracts minimal key key and corresponding value
 436         /**
 437             This function is a shortcut for the following call:
 438             \code
 439             key_type key;
 440             exempt_ptr xp = theTree.extract_min( [&key]( key_type const& k ) { key = k; } );
 441             \endode
 442             \p key_type should be copy-assignable. The copy of minimal key
 443             is returned in \p min_key argument.
 444         */
 445         typename std::enable_if< std::is_copy_assignable<key_type>::value, exempt_ptr >::type
 446         extract_min_key( key_type& min_key )
 447         {
 448             return exempt_ptr(do_extract_min( [&min_key]( key_type const& key ) { min_key = key; }));
 449         }
 450
 451         /// Extracts a value with maximal key from the tree
 452         /**
 453             Returns \p exempt_ptr pointer to the rightmost item.
 454             If the set is empty, returns empty \p exempt_ptr.
 455
 456             Note that the function returns only the value for maximal key.
 457             To retrieve its key use \p extract_max( Func ) member function.
 458
 459             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
 460             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 461             During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
 462             So, the function returns the item with maximum key at the moment of tree traversing.
 463
 464             RCU \p synchronize method can be called. RCU should NOT be locked.
 465             The function does not free the item.
 466             The deallocator will be implicitly invoked when the returned object is destroyed or when
 467             its \p release() is called.
 468         */
 469         exempt_ptr extract_max()
 470         {
 471             return exempt_ptr(do_extract_max( []( key_type const& ) {}));
 472         }
 473
 474         /// Extracts the maximal key and corresponding value
 475         /**
 476             Returns \p exempt_ptr pointer to the rightmost item.
 477             If the set is empty, returns empty \p exempt_ptr.
 478
 479             \p Func functor is used to store maximal key.
 480             \p Func has the following signature:
 481             \code
 482                 struct functor {
 483                     void operator()( key_type const& key );
 484                 };
 485             \endcode
 486             If the tree is empty, \p f is not called.
 487             Otherwise, is it called with maximal key, the pointer to corresponding value is returned
 488             as \p exempt_ptr.
 489
 490             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
 491             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 492             During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
 493             So, the function returns the item with maximum key at the moment of tree traversing.
 494
 495             RCU \p synchronize method can be called. RCU should NOT be locked.
 496             The function does not free the item.
 497             The deallocator will be implicitly invoked when the returned object is destroyed or when
 498             its \p release() is called.
 499         */
 500         template <typename Func>
 501         exempt_ptr extract_max( Func f )
 502         {
 503             return exempt_ptr(do_extract_max( [&f]( key_type const& key ) { f(key); }));
 504         }
 505
 506         /// Extracts the maximal key and corresponding value
 507         /**
 508             This function is a shortcut for the following call:
 509             \code
 510                 key_type key;
 511                 exempt_ptr xp = theTree.extract_max( [&key]( key_type const& k ) { key = k; } );
 512             \endode
 513             \p key_type should be copy-assignable. The copy of maximal key
 514             is returned in \p max_key argument.
 515         */
 516         typename std::enable_if< std::is_copy_assignable<key_type>::value, exempt_ptr >::type
 517         extract_max_key( key_type& max_key )
 518         {
 519             return exempt_ptr(do_extract_max( [&max_key]( key_type const& key ) { max_key = key; }));
 520         }
 521
 522         /// Extracts an item from the map
 523         /**
 524             The function searches an item with key equal to \p key in the tree,
 525             unlinks it, and returns \p exempt_ptr pointer to a value found.
 526             If \p key is not found the function returns an empty \p exempt_ptr.
 527
 528             RCU \p synchronize method can be called. RCU should NOT be locked.
 529             The function does not destroy the value found.
 530             The disposer will be implicitly invoked when the returned object is destroyed or when
 531             its \p release() member function is called.
 532         */
 533         template <typename Q>
 534         exempt_ptr extract( Q const& key )
 535         {
 536             return exempt_ptr(do_extract( key ));
 537         }
 538
 539
 540         /// Extracts an item from the map using \p pred for searching
 541         /**
 542             The function is an analog of \p extract(Q const&)
 543             but \p pred is used for key compare.
 544             \p Less has the interface like \p std::less.
 545             \p pred must imply the same element order as the comparator used for building the tree.
 546         */
 547         template <typename Q, typename Less>
 548         exempt_ptr extract_with( Q const& key, Less pred )
 549         {
 550             return exempt_ptr(do_extract_with( key, pred ));
 551         }
 552
 553         /// Find the key \p key
 554         /**
 555             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 556             The interface of \p Func functor is:
 557             \code
 558             struct functor {
 559                 void operator()( key_type const& key, mapped_type& item );
 560             };
 561             \endcode
 562             where \p item is the item found.
 563             The functor is called under node-level lock.
 564
 565             The function applies RCU lock internally.
 566
 567             The function returns \p true if \p key is found, \p false otherwise.
 568         */
 569         template <typename K, typename Func>
 570         bool find( K const& key, Func f )
 571         {
 572             return do_find( key, key_comparator(),
 573                 [&f]( node_type * pNode ) -> bool {
 574                     assert( pNode != nullptr );
 575                     mapped_type pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
 576                     if ( pVal ) {
 577                         f( pNode->m_key, *pVal );
 578                         return true;
 579                     }
 580                     return false;
 581                 }
 582             );
 583         }
 584
 585         /// Finds the key \p val using \p pred predicate for searching
 586         /**
 587             The function is an analog of \p find(K const&, Func)
 588             but \p pred is used for key comparing.
 589             \p Less functor has the interface like \p std::less.
 590             \p Less must imply the same element order as the comparator used for building the map.
 591         */
 592         template <typename K, typename Less, typename Func>
 593         bool find_with( K const& key, Less pred, Func f )
 594         {
 595             CDS_UNUSED( pred );
 596             return do_find( key, cds::opt::details::make_comparator_from_less<Less>(),
 597                 [&f]( node_type * pNode ) -> bool {
 598                     assert( pNode != nullptr );
 599                     mapped_type pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
 600                     if ( pVal ) {
 601                         f( pNode->m_key, *pVal );
 602                         return true;
 603                     }
 604                     return false;
 605                 }
 606             );
 607         }
 608
 609         /// Find the key \p key
 610         /**
 611             The function searches the item with key equal to \p key
 612             and returns \p true if it is found, and \p false otherwise.
 613
 614             The function applies RCU lock internally.
 615         */
 616         template <typename K>
 617         bool find( K const& key )
 618         {
 619             return do_find( key, key_comparator(), []( node_type * ) -> bool { return true; });
 620         }
 621
 622         /// Finds the key \p val using \p pred predicate for searching
 623         /**
 624             The function is an analog of \p find(K const&)
 625             but \p pred is used for key comparing.
 626             \p Less functor has the interface like \p std::less.
 627             \p Less must imply the same element order as the comparator used for building the map.
 628         */
 629         template <typename K, typename Less>
 630         bool find_with( K const& key, Less pred )
 631         {
 632             CDS_UNUSED( pred );
 633             return do_find( key, cds::opt::details::make_comparator_from_less<Less>(), []( node_type * ) -> bool { return true; } );
 634         }
 635
 636         /// Clears the tree (thread safe, not atomic)
 637         /**
 638             The function unlink all items from the tree.
 639             The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
 640             this sequence
 641             \code
 642             set.clear();
 643             assert( set.empty() );
 644             \endcode
 645             the assertion could be raised.
 646
 647             For each node the \ref disposer will be called after unlinking.
 648
 649             RCU \p synchronize method can be called. RCU should not be locked.
 650         */
 651         void clear()
 652         {
 653             while ( extract_min() );
 654         }
 655
 656         /// Clears the tree (not thread safe)
 657         /**
 658             This function is not thread safe and may be called only when no other thread deals with the tree.
 659             The function is used in the tree destructor.
 660         */
 661         void unsafe_clear()
 662         {
 663             clear(); // temp solution
 664             //TODO
 665         }
 666
 667         /// Checks if the map is empty
 668         bool empty() const
 669         {
 670             return m_Root.m_pRight.load( memory_model::memory_order_relaxed ) == nullptr;
 671         }
 672
 673         /// Returns item count in the map
 674         /**
 675             Only leaf nodes containing user data are counted.
 676
 677             The value returned depends on item counter type provided by \p Traits template parameter.
 678             If it is \p atomicity::empty_item_counter this function always returns 0.
 679
 680             The function is not suitable for checking the tree emptiness, use \p empty()
 681             member function for this purpose.
 682         */
 683         size_t size() const
 684         {
 685             return m_ItemCounter;
 686         }
 687
 688         /// Returns const reference to internal statistics
 689         stat const& statistics() const
 690         {
 691             return m_stat;
 692         }
 693
 694         /// Checks internal consistency (not atomic, not thread-safe)
 695         /**
 696             The debugging function to check internal consistency of the tree.
 697         */
 698         bool check_consistency() const
 699         {
 700             return check_consistency([]( size_t /*nLevel*/, size_t /*hLeft*/, size_t /*hRight*/ ){} );
 701         }
 702
 703         /// Checks internal consistency (not atomic, not thread-safe)
 704         /**
 705             The debugging function to check internal consistency of the tree.
 706             The functor \p Func is called if a violation of internal tree structure
 707             is found:
 708             \code
 709             struct functor {
 710                 void operator()( size_t nLevel, size_t hLeft, size_t hRight );
 711             };
 712             \endcode
 713             where
 714             - \p nLevel - the level where the violation is found
 715             - \p hLeft - the height of left subtree
 716             - \p hRight - the height of right subtree
 717
 718             The functor is called for each violation found.
 719         */
 720         template <typename Func>
 721         bool check_consistency( Func f ) const
 722         {
 723             node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_relaxed );
 724             if ( pChild ) {
 725                 size_t nErrors = 0;
 726                 do_check_consistency( pChild, 1, f, nErrors );
 727                 return nErrors == 0;
 728             }
 729             return true;
 730         }
 731
 732     protected:
 733         //@cond
 734         template <typename Func>
 735         size_t do_check_consistency( node_type * pNode, size_t nLevel, Func f, size_t& nErrors ) const
 736         {
 737             if ( pNode ) {
 738                 size_t hLeft = do_check_consistency( child( pNode, left_child, memory_model::memory_order_relaxed ), nLevel + 1, f, nErrors );
 739                 size_t hRight = do_check_consistency( child( pNode, right_child, memory_model::memory_order_relaxed ), nLevel + 1, f, nErrors );
 740
 741                 if ( hLeft >= hRight ) {
 742                     if ( hLeft - hRight > 1 ) {
 743                         f( nLevel, hLeft, hRight );
 744                         ++nErrors;
 745                     }
 746                     return hLeft;
 747                 }
 748                 else {
 749                     if ( hRight - hLeft > 1 ) {
 750                         f( nLevel, hLeft, hRight );
 751                         ++nErrors;
 752                     }
 753                     return hRight;
 754                 }
 755             }
 756             return 0;
 757         }
 758
 759         template <typename Q, typename Compare, typename Func>
 760         bool do_find( Q& key, Compare cmp, Func f ) const
 761         {
 762             find_result result;
 763             {
 764                 rcu_lock l;
 765                 result = try_find( key, cmp, f, m_pRoot, 1, 0 );
 766             }
 767             assert( result != find_result::retry );
 768             return result == find_result::found;
 769         }
 770
 771         template <typename K, typename Compare, typename Func>
 772         int do_update( K const& key, Compare cmp, Func funcUpdate, int nFlags )
 773         {
 774             check_deadlock_policy::check();
 775
 776             rcu_disposer removed_list;
 777             {
 778                 rcu_lock l;
 779                 return try_update_root( key, cmp, nFlags, funcUpdate, removed_list );
 780             }
 781         }
 782
 783         template <typename K, typename Compare, typename Func>
 784         bool do_remove( K const& key, Compare cmp, Func func )
 785         {
 786             // Func must return true if the value was disposed
 787             //              or false if the value was extracted
 788
 789             check_deadlock_policy::check();
 790
 791             rcu_disposer removed_list;
 792             {
 793                 rcu_lock l;
 794                 return try_remove_root( key, cmp, func, removed_list );
 795             }
 796         }
 797
 798         template <typename Func>
 799         mapped_type do_extract_min( Func f )
 800         {
 801             mapped_type pExtracted = nullptr;
 802             do_extract_minmax(
 803                 left_child,
 804                 [&pExtracted, &f]( key_type const& key, mapped_type pVal, rcu_disposer& ) -> bool { f( key ); pExtracted = pVal; return false; }
 805             );
 806             return pExtracted;
 807         }
 808
 809         template <typename Func>
 810         mapped_type do_extract_max( Func f )
 811         {
 812             mapped_type pExtracted = nullptr;
 813             do_extract_minmax(
 814                 right_child,
 815                 [&pExtracted, &f]( key_type const& key, mapped_type pVal, rcu_disposer& ) -> bool { f( key ); pExtracted = pVal; return false; }
 816             );
 817             return pExtracted;
 818         }
 819
 820         template <typename Func>
 821         void do_extract_minmax( int nDir, Func func )
 822         {
 823             check_deadlock_policy::check();
 824
 825             rcu_disposer removed_list;
 826             {
 827                 rcu_lock l;
 828
 829                 int result = update_flags::failed;
 830                 do {
 831                     // get right child of root
 832                     node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
 833                     if ( pChild ) {
 834                         version_type nChildVersion = pChild->version( memory_model::memory_order_relaxed );
 835                         if ( nChildVersion & node_type::shrinking ) {
 836                             m_stat.onRemoveRootWaitShrinking();
 837                             pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
 838                             result = update_flags::retry;
 839                         }
 840                         else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
 841                             result = try_extract_minmax( nDir, func, m_pRoot, pChild, nChildVersion, removed_list );
 842                         }
 843                     }
 844                 } while ( result == update_flags::retry );
 845             }
 846         }
 847
 848         template <typename Q>
 849         mapped_type do_extract( Q const& key )
 850         {
 851             mapped_type pExtracted = nullptr;
 852             do_remove(
 853                 key,
 854                 key_comparator(),
 855                 [&pExtracted]( key_type const&, mapped_type pVal, rcu_disposer& ) -> bool { pExtracted = pVal; return false; }
 856             );
 857             return pExtracted;
 858         }
 859
 860         template <typename Q, typename Less>
 861         mapped_type do_extract_with( Q const& key, Less pred )
 862         {
 863             CDS_UNUSED( pred );
 864             mapped_type pExtracted = nullptr;
 865             do_remove(
 866                 key,
 867                 cds::opt::details::make_comparator_from_less<Less>(),
 868                 [&pExtracted]( key_type const&, mapped_type pVal, rcu_disposer& ) -> bool { pExtracted = pVal; return false; }
 869             );
 870             return pExtracted;
 871         }
 872
 873         //@endcond
 874
 875     private:
 876         //@cond
 877         template <typename Q, typename Compare, typename Func>
 878         find_result try_find( Q const& key, Compare cmp, Func f, node_type * pNode, int nDir, version_type nVersion ) const
 879         {
 880             assert( gc::is_locked() );
 881             assert( pNode );
 882
 883             while ( true ) {
 884                 node_type * pChild = child( pNode, nDir, memory_model::memory_order_relaxed );
 885                 if ( !pChild ) {
 886                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
 887                         m_stat.onFindRetry();
 888                         return find_result::retry;
 889                     }
 890
 891                     m_stat.onFindFailed();
 892                     return find_result::not_found;
 893                 }
 894
 895                 int nCmp = cmp( key, pChild->m_key );
 896                 if ( nCmp == 0 ) {
 897                     if ( pChild->is_valued( memory_model::memory_order_relaxed ) ) {
 898                         // key found
 899                         node_scoped_lock l( m_Monitor, *pChild );
 900                         if ( pChild->is_valued( memory_model::memory_order_relaxed )) {
 901                             if ( f( pChild ) ) {
 902                                 m_stat.onFindSuccess();
 903                                 return find_result::found;
 904                             }
 905                         }
 906                     }
 907
 908                     m_stat.onFindFailed();
 909                     return find_result::not_found;
 910                 }
 911
 912                 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
 913                 if ( nChildVersion & node_type::shrinking ) {
 914                     m_stat.onFindWaitShrinking();
 915                     pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
 916
 917                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
 918                         m_stat.onFindRetry();
 919                         return find_result::retry;
 920                     }
 921                 }
 922                 else if ( nChildVersion != node_type::unlinked ) {
 923
 924                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
 925                         m_stat.onFindRetry();
 926                         return find_result::retry;
 927                     }
 928
 929                     find_result found = try_find( key, cmp, f, pChild, nCmp, nChildVersion );
 930                     if ( found != find_result::retry )
 931                         return found;
 932                 }
 933             }
 934         }
 935
 936         template <typename K, typename Compare, typename Func>
 937         int try_update_root( K const& key, Compare cmp, int nFlags, Func funcUpdate, rcu_disposer& disp )
 938         {
 939             assert( gc::is_locked() );
 940
 941             int result;
 942             do {
 943                 // get right child of root
 944                 node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
 945                 if ( pChild ) {
 946                     version_type nChildVersion = pChild->version( memory_model::memory_order_relaxed );
 947                     if ( nChildVersion & node_type::shrinking ) {
 948                         m_stat.onUpdateRootWaitShrinking();
 949                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
 950                         result = update_flags::retry;
 951                     }
 952                     else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
 953                         result = try_update( key, cmp, nFlags, funcUpdate, m_pRoot, pChild, nChildVersion, disp );
 954                     }
 955                 }
 956                 else {
 957                     // the tree is empty
 958                     if ( nFlags & update_flags::allow_insert ) {
 959                         // insert into tree as right child of the root
 960                         {
 961                             node_scoped_lock l( m_Monitor, *m_pRoot );
 962                             if ( child( m_pRoot, right_child, memory_model::memory_order_acquire ) != nullptr ) {
 963                                 result = result == update_flags::retry;
 964                                 continue;
 965                             }
 966
 967                             node_type * pNew = alloc_node( key, 1, 0, m_pRoot, nullptr, nullptr );
 968                             mapped_type pVal = funcUpdate( pNew );
 969                             assert( pVal != nullptr );
 970                             pNew->m_pValue.store( pVal, memory_model::memory_order_release );
 971
 972                             m_pRoot->child( pNew, right_child, memory_model::memory_order_relaxed );
 973                             m_pRoot->height( 2, memory_model::memory_order_relaxed );
 974                         }
 975
 976                         ++m_ItemCounter;
 977                         m_stat.onInsertSuccess();
 978                         return update_flags::result_inserted;
 979                     }
 980
 981                     return update_flags::failed;
 982                 }
 983             } while ( result == update_flags::retry );
 984             return result;
 985         }
 986
 987         template <typename K, typename Compare, typename Func>
 988         bool try_remove_root( K const& key, Compare cmp, Func func, rcu_disposer& disp )
 989         {
 990             assert( gc::is_locked() );
 991
 992             int result;
 993             do {
 994                 // get right child of root
 995                 node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
 996                 if ( pChild ) {
 997                     version_type nChildVersion = pChild->version( memory_model::memory_order_relaxed );
 998                     if ( nChildVersion & node_type::shrinking ) {
 999                         m_stat.onRemoveRootWaitShrinking();
1000                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1001                         result = update_flags::retry;
1002                     }
1003                     else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
1004                         result = try_remove( key, cmp, func, m_pRoot, pChild, nChildVersion, disp );
1005                     }
1006                 }
1007                 else
1008                     return false;
1009             } while ( result == update_flags::retry );
1010
1011             return result == update_flags::result_removed;
1012         }
1013
1014         template <typename K, typename Compare, typename Func>
1015         int try_update( K const& key, Compare cmp, int nFlags, Func funcUpdate, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1016         {
1017             assert( gc::is_locked() );
1018             assert( nVersion != node_type::unlinked );
1019             CDS_UNUSED( pParent );
1020
1021             int nCmp = cmp( key, pNode->m_key );
1022             if ( nCmp == 0 ) {
1023                 if ( nFlags & update_flags::allow_update ) {
1024                     return try_update_node( funcUpdate, pNode, disp );
1025                 }
1026                 return update_flags::failed;
1027             }
1028
1029             int result;
1030             do {
1031                 node_type * pChild = child( pNode, nCmp, memory_model::memory_order_relaxed );
1032                 if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1033                     m_stat.onUpdateRetry();
1034                     return update_flags::retry;
1035                 }
1036
1037                 if ( pChild == nullptr ) {
1038                     // insert new node
1039                     if ( nFlags & update_flags::allow_insert )
1040                         result = try_insert_node( key, funcUpdate, pNode, nCmp, nVersion, disp );
1041                     else
1042                         result = update_flags::failed;
1043                 }
1044                 else {
1045                     // update child
1046                     result = update_flags::retry;
1047                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1048                     if ( nChildVersion & node_type::shrinking ) {
1049                         m_stat.onUpdateWaitShrinking();
1050                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1051                         // retry
1052                     }
1053                     else if ( pChild == child( pNode, nCmp, memory_model::memory_order_relaxed )) {
1054                         // this second read is important, because it is protected by nChildVersion
1055
1056                         // validate the read that our caller took to get to node
1057                         if ( pNode->version( memory_model::memory_order_relaxed ) != nVersion ) {
1058                             m_stat.onUpdateRetry();
1059                             return update_flags::retry;
1060                         }
1061
1062                         // At this point we know that the traversal our parent took to get to node is still valid.
1063                         // The recursive implementation will validate the traversal from node to
1064                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
1065                         // This means that we are no longer vulnerable to node shrinks, and we don't need
1066                         // to validate node version any more.
1067                         result = try_update( key, cmp, nFlags, funcUpdate, pNode, pChild, nChildVersion, disp );
1068                     }
1069                 }
1070             } while ( result == update_flags::retry );
1071             return result;
1072         }
1073
1074         template <typename K, typename Compare, typename Func>
1075         int try_remove( K const& key, Compare cmp, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1076         {
1077             assert( gc::is_locked() );
1078             assert( nVersion != node_type::unlinked );
1079
1080             int nCmp = cmp( key, pNode->m_key );
1081             if ( nCmp == 0 )
1082                 return try_remove_node( pParent, pNode, nVersion, func, disp );
1083
1084             int result;
1085             do {
1086                 node_type * pChild = child( pNode, nCmp, memory_model::memory_order_relaxed );
1087                 if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1088                     m_stat.onRemoveRetry();
1089                     return update_flags::retry;
1090                 }
1091
1092                 if ( pChild == nullptr ) {
1093                     return update_flags::failed;
1094                 }
1095                 else {
1096                     // update child
1097                     result = update_flags::retry;
1098                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1099                     if ( nChildVersion & node_type::shrinking ) {
1100                         m_stat.onRemoveWaitShrinking();
1101                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1102                         // retry
1103                     }
1104                     else if ( pChild == child( pNode, nCmp, memory_model::memory_order_relaxed )) {
1105                         // this second read is important, because it is protected by nChildVersion
1106
1107                         // validate the read that our caller took to get to node
1108                         if ( pNode->version( memory_model::memory_order_relaxed ) != nVersion ) {
1109                             m_stat.onRemoveRetry();
1110                             return update_flags::retry;
1111                         }
1112
1113                         // At this point we know that the traversal our parent took to get to node is still valid.
1114                         // The recursive implementation will validate the traversal from node to
1115                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
1116                         // This means that we are no longer vulnerable to node shrinks, and we don't need
1117                         // to validate node version any more.
1118                         result = try_remove( key, cmp, func, pNode, pChild, nChildVersion, disp );
1119                     }
1120                 }
1121             } while ( result == update_flags::retry );
1122             return result;
1123         }
1124
1125         template <typename Func>
1126         int try_extract_minmax( int nDir, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1127         {
1128             assert( gc::is_locked() );
1129             assert( nVersion != node_type::unlinked );
1130
1131             int result;
1132             do {
1133                 node_type * pChild = child( pNode, nDir, memory_model::memory_order_relaxed );
1134                 if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1135                     m_stat.onRemoveRetry();
1136                     return update_flags::retry;
1137                 }
1138
1139                 if ( pChild == nullptr ) {
1140                     // Found min/max
1141                     return try_remove_node( pParent, pNode, nVersion, func, disp );
1142                 }
1143                 else {
1144                     result = update_flags::retry;
1145                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1146                     if ( nChildVersion & node_type::shrinking ) {
1147                         m_stat.onRemoveWaitShrinking();
1148                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1149                         // retry
1150                     }
1151                     else if ( pChild == child( pNode, nDir, memory_model::memory_order_relaxed )) {
1152                         // this second read is important, because it is protected by nChildVersion
1153
1154                         // validate the read that our caller took to get to node
1155                         if ( pNode->version( memory_model::memory_order_relaxed ) != nVersion ) {
1156                             m_stat.onRemoveRetry();
1157                             return update_flags::retry;
1158                         }
1159
1160                         // At this point we know that the traversal our parent took to get to node is still valid.
1161                         // The recursive implementation will validate the traversal from node to
1162                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
1163                         // This means that we are no longer vulnerable to node shrinks, and we don't need
1164                         // to validate node version any more.
1165                         result = try_extract_minmax( nDir, func, pNode, pChild, nChildVersion, disp );
1166                     }
1167                 }
1168             } while ( result == update_flags::retry );
1169             return result;
1170         }
1171
1172         template <typename K, typename Func>
1173         int try_insert_node( K const& key, Func funcUpdate, node_type * pNode, int nDir, version_type nVersion, rcu_disposer& disp )
1174         {
1175             node_type * pNew;
1176
1177             auto fnCreateNode = [&funcUpdate]( node_type * pNew ) {
1178                 mapped_type pVal = funcUpdate( pNew );
1179                 assert( pVal != nullptr );
1180                 pNew->m_pValue.store( pVal, memory_model::memory_order_relaxed );
1181             };
1182
1183             if ( c_bRelaxedInsert ) {
1184                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
1185                      || child( pNode, nDir, memory_model::memory_order_relaxed ) != nullptr )
1186                 {
1187                     m_stat.onInsertRetry();
1188                     return update_flags::retry;
1189                 }
1190
1191                 fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
1192             }
1193
1194             node_type * pDamaged;
1195             {
1196                 assert( pNode != nullptr );
1197                 node_scoped_lock l( m_Monitor, *pNode );
1198
1199                 if ( pNode->version( memory_model::memory_order_relaxed ) != nVersion
1200                      || child( pNode, nDir, memory_model::memory_order_relaxed ) != nullptr )
1201                 {
1202                     if ( c_bRelaxedInsert ) {
1203                         free_node( pNew );
1204                         m_stat.onRelaxedInsertFailed();
1205                     }
1206
1207                     m_stat.onInsertRetry();
1208                     return update_flags::retry;
1209                 }
1210
1211                 if ( !c_bRelaxedInsert )
1212                     fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
1213
1214                 pNode->child( pNew, nDir, memory_model::memory_order_relaxed );
1215                 pDamaged = fix_height_locked( pNode );
1216             }
1217
1218             ++m_ItemCounter;
1219             m_stat.onInsertSuccess();
1220
1221             fix_height_and_rebalance( pDamaged, disp );
1222
1223             return update_flags::result_inserted;
1224         }
1225
1226         template <typename Func>
1227         int try_update_node( Func funcUpdate, node_type * pNode, rcu_disposer& disp )
1228         {
1229             mapped_type pOld;
1230             assert( pNode != nullptr );
1231             {
1232                 node_scoped_lock l( m_Monitor, *pNode );
1233
1234                 if ( pNode->is_unlinked( memory_model::memory_order_relaxed )) {
1235                     m_stat.onUpdateUnlinked();
1236                     return update_flags::retry;
1237                 }
1238
1239                 pOld = pNode->value( memory_model::memory_order_relaxed );
1240                 mapped_type pVal = funcUpdate( pNode );
1241                 if ( pVal == pOld )
1242                     pOld = nullptr;
1243                 else {
1244                     assert( pVal != nullptr );
1245                     pNode->m_pValue.store( pVal, memory_model::memory_order_relaxed );
1246                 }
1247             }
1248
1249             if ( pOld ) {
1250                 disp.dispose_value(pOld);
1251                 m_stat.onDisposeValue();
1252             }
1253
1254             m_stat.onUpdateSuccess();
1255             return update_flags::result_updated;
1256         }
1257
1258         template <typename Func>
1259         int try_remove_node( node_type * pParent, node_type * pNode, version_type nVersion, Func func, rcu_disposer& disp )
1260         {
1261             assert( pParent != nullptr );
1262             assert( pNode != nullptr );
1263
1264             if ( !pNode->is_valued( atomics::memory_order_relaxed ) )
1265                 return update_flags::failed;
1266
1267             if ( child( pNode, left_child, memory_model::memory_order_relaxed ) == nullptr
1268               || child( pNode, right_child, memory_model::memory_order_relaxed ) == nullptr )
1269             {
1270                 node_type * pDamaged;
1271                 mapped_type pOld;
1272                 {
1273                     node_scoped_lock lp( m_Monitor, *pParent );
1274                     if ( pParent->is_unlinked( atomics::memory_order_relaxed ) || parent( pNode, memory_model::memory_order_relaxed ) != pParent )
1275                         return update_flags::retry;
1276
1277                     {
1278                         node_scoped_lock ln( m_Monitor, *pNode );
1279                         pOld = pNode->value( memory_model::memory_order_relaxed );
1280                         if ( !( pNode->version( memory_model::memory_order_relaxed ) == nVersion
1281                           && pOld
1282                           && try_unlink_locked( pParent, pNode, disp )))
1283                         {
1284                             return update_flags::retry;
1285                         }
1286                     }
1287                     pDamaged = fix_height_locked( pParent );
1288                 }
1289
1290                 --m_ItemCounter;
1291                 if ( func( pNode->m_key, pOld, disp ))   // calls pOld disposer inside
1292                     m_stat.onDisposeValue();
1293                 else
1294                     m_stat.onExtractValue();
1295
1296                 fix_height_and_rebalance( pDamaged, disp );
1297                 return update_flags::result_removed;
1298             }
1299             else {
1300                 int result = update_flags::retry;
1301                 mapped_type pOld;
1302                 {
1303                     node_scoped_lock ln( m_Monitor, *pNode );
1304                     pOld = pNode->value( atomics::memory_order_relaxed );
1305                     if ( pNode->version( atomics::memory_order_relaxed ) == nVersion && pOld ) {
1306                         pNode->m_pValue.store( nullptr, atomics::memory_order_relaxed );
1307                         result = update_flags::result_removed;
1308                     }
1309                 }
1310
1311                 if ( result == update_flags::result_removed ) {
1312                     --m_ItemCounter;
1313                     if ( func( pNode->m_key, pOld, disp ))  // calls pOld disposer inside
1314                         m_stat.onDisposeValue();
1315                     else
1316                         m_stat.onExtractValue();
1317                 }
1318
1319                 return result;
1320             }
1321         }
1322
1323         bool try_unlink_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp )
1324         {
1325             // pParent and pNode must be locked
1326             assert( !pParent->is_unlinked(memory_model::memory_order_relaxed) );
1327
1328             node_type * pParentLeft = child( pParent, left_child, memory_model::memory_order_relaxed );
1329             node_type * pParentRight = child( pParent, right_child, memory_model::memory_order_relaxed );
1330             if ( pNode != pParentLeft && pNode != pParentRight ) {
1331                 // node is no longer a child of parent
1332                 return false;
1333             }
1334
1335             assert( !pNode->is_unlinked( memory_model::memory_order_relaxed ) );
1336             assert( pParent == parent( pNode, memory_model::memory_order_relaxed));
1337
1338             node_type * pLeft = child( pNode, left_child, memory_model::memory_order_relaxed );
1339             node_type * pRight = child( pNode, right_child, memory_model::memory_order_relaxed );
1340             if ( pLeft != nullptr && pRight != nullptr ) {
1341                 // splicing is no longer possible
1342                 return false;
1343             }
1344             node_type * pSplice = pLeft ? pLeft : pRight;
1345
1346             if ( pParentLeft == pNode )
1347                 pParent->m_pLeft.store( pSplice, memory_model::memory_order_relaxed );
1348             else
1349                 pParent->m_pRight.store( pSplice, memory_model::memory_order_relaxed );
1350
1351             if ( pSplice )
1352                 pSplice->m_pParent.store( pParent, memory_model::memory_order_release );
1353
1354             // Mark the node as unlinked
1355             pNode->version( node_type::unlinked, memory_model::memory_order_release );
1356
1357             // The value will be disposed by calling function
1358             pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
1359
1360             disp.dispose( pNode );
1361             m_stat.onDisposeNode();
1362
1363             return true;
1364         }
1365
1366         //@endcond
1367
1368     private: // rotations
1369         //@cond
1370         int estimate_node_condition( node_type * pNode )
1371         {
1372             node_type * pLeft = child( pNode, left_child, memory_model::memory_order_relaxed );
1373             node_type * pRight = child( pNode, right_child, memory_model::memory_order_relaxed );
1374
1375             if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_relaxed ))
1376                 return unlink_required;
1377
1378             int h = pNode->height( memory_model::memory_order_relaxed );
1379             int hL = pLeft ? pLeft->height( memory_model::memory_order_relaxed ) : 0;
1380             int hR = pRight ? pRight->height( memory_model::memory_order_relaxed ) : 0;
1381
1382             int hNew = 1 + std::max( hL, hR );
1383             int nBalance = hL - hR;
1384
1385             if ( nBalance < -1 || nBalance > 1 )
1386                 return rebalance_required;
1387
1388             return h != hNew ? hNew : nothing_required;
1389         }
1390
1391         node_type * fix_height( node_type * pNode )
1392         {
1393             assert( pNode != nullptr );
1394             node_scoped_lock l( m_Monitor, *pNode );
1395             return fix_height_locked( pNode );
1396         }
1397
1398         node_type * fix_height_locked( node_type * pNode )
1399         {
1400             // pNode must be locked!!!
1401             int h = estimate_node_condition( pNode );
1402             switch ( h ) {
1403                 case rebalance_required:
1404                 case unlink_required:
1405                     return pNode;
1406                 case nothing_required:
1407                     return nullptr;
1408                 default:
1409                     pNode->height( h, memory_model::memory_order_relaxed );
1410                     return parent( pNode, memory_model::memory_order_relaxed );
1411             }
1412         }
1413
1414         void fix_height_and_rebalance( node_type * pNode, rcu_disposer& disp )
1415         {
1416             while ( pNode && parent( pNode, memory_model::memory_order_relaxed )) {
1417                 int nCond = estimate_node_condition( pNode );
1418                 if ( nCond == nothing_required || pNode->is_unlinked( memory_model::memory_order_relaxed ) )
1419                     return;
1420
1421                 if ( nCond != unlink_required && nCond != rebalance_required )
1422                     pNode = fix_height( pNode );
1423                 else {
1424                     node_type * pParent = parent( pNode, memory_model::memory_order_relaxed );
1425                     assert( pParent != nullptr );
1426                     {
1427                         node_scoped_lock lp( m_Monitor, *pParent );
1428                         if ( !pParent->is_unlinked( memory_model::memory_order_relaxed )
1429                              && parent( pNode, memory_model::memory_order_relaxed ) == pParent )
1430                         {
1431                             node_scoped_lock ln( m_Monitor, *pNode );
1432                             pNode = rebalance_locked( pParent, pNode, disp );
1433                         }
1434                     }
1435                 }
1436             }
1437         }
1438
1439         node_type * rebalance_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp )
1440         {
1441             // pParent and pNode should be locked.
1442             // Returns a damaged node, or nullptr if no more rebalancing is necessary
1443             assert( parent( pNode, memory_model::memory_order_relaxed ) == pParent );
1444             assert( child( pParent, left_child, memory_model::memory_order_relaxed ) == pNode
1445                  || child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
1446
1447             node_type * pLeft = child( pNode, left_child, memory_model::memory_order_relaxed );
1448             node_type * pRight = child( pNode, right_child, memory_model::memory_order_relaxed );
1449
1450             if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_relaxed )) {
1451                 if ( try_unlink_locked( pParent, pNode, disp ))
1452                     return fix_height_locked( pParent );
1453                 else {
1454                     // retry needed for pNode
1455                     return pNode;
1456                 }
1457             }
1458
1459             int h = pNode->height( memory_model::memory_order_relaxed );
1460             int hL = pLeft ? pLeft->height( memory_model::memory_order_relaxed ) : 0;
1461             int hR = pRight ? pRight->height( memory_model::memory_order_relaxed ) : 0;
1462             int hNew = 1 + std::max( hL, hR );
1463             int balance = hL - hR;
1464
1465             if ( balance > 1 )
1466                 return rebalance_to_right_locked( pParent, pNode, pLeft, hR );
1467             else if ( balance < -1 )
1468                 return rebalance_to_left_locked( pParent, pNode, pRight, hL );
1469             else if ( hNew != h ) {
1470                 pNode->height( hNew, memory_model::memory_order_relaxed );
1471
1472                 // pParent is already locked
1473                 return fix_height_locked( pParent );
1474             }
1475             else
1476                 return nullptr;
1477         }
1478
1479         node_type * rebalance_to_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR )
1480         {
1481             assert( parent( pNode, memory_model::memory_order_relaxed ) == pParent );
1482             assert( child( pParent, left_child, memory_model::memory_order_relaxed ) == pNode
1483                  || child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
1484
1485             // pParent and pNode is locked yet
1486             // pNode->pLeft is too large, we will rotate-right.
1487             // If pLeft->pRight is taller than pLeft->pLeft, then we will first rotate-left pLeft.
1488
1489             {
1490                 assert( pLeft != nullptr );
1491                 node_scoped_lock l( m_Monitor, *pLeft );
1492                 if ( pNode->m_pLeft.load( memory_model::memory_order_relaxed ) != pLeft )
1493                     return pNode; // retry for pNode
1494
1495                 int hL = pLeft->height( memory_model::memory_order_relaxed );
1496                 if ( hL - hR <= 1 )
1497                     return pNode; // retry
1498
1499                 node_type * pLRight = child( pLeft, right_child, memory_model::memory_order_relaxed );
1500                 int hLR = pLRight ? pLRight->height( memory_model::memory_order_relaxed ) : 0;
1501                 node_type * pLLeft = child( pLeft, left_child, memory_model::memory_order_relaxed );
1502                 int hLL = pLLeft ? pLLeft->height( memory_model::memory_order_relaxed ) : 0;
1503
1504                 if ( hLL > hLR ) {
1505                     // rotate right
1506                     return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
1507                 }
1508                 else {
1509                     assert( pLRight != nullptr );
1510                     {
1511                         node_scoped_lock lr( m_Monitor, *pLRight );
1512                         if ( pLeft->m_pRight.load( memory_model::memory_order_relaxed ) != pLRight )
1513                             return pNode; // retry
1514
1515                         hLR = pLRight->height( memory_model::memory_order_relaxed );
1516                         if ( hLL > hLR )
1517                             return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
1518
1519                         node_type * pLRLeft = child( pLRight, left_child, memory_model::memory_order_relaxed );
1520                         int hLRL = pLRLeft ? pLRLeft->height( memory_model::memory_order_relaxed  ) : 0;
1521                         int balance = hLL - hLRL;
1522                         if ( balance >= -1 && balance <= 1 && !((hLL == 0 || hLRL == 0) && !pLeft->is_valued(memory_model::memory_order_relaxed))) {
1523                             // nParent.child.left won't be damaged after a double rotation
1524                             return rotate_right_over_left_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLRL );
1525                         }
1526                     }
1527
1528                     // focus on pLeft, if necessary pNode will be balanced later
1529                     return rebalance_to_left_locked( pNode, pLeft, pLRight, hLL );
1530                 }
1531             }
1532         }
1533
1534         node_type * rebalance_to_left_locked( node_type * pParent, node_type * pNode, node_type * pRight, int hL )
1535         {
1536             assert( parent( pNode, memory_model::memory_order_relaxed ) == pParent );
1537             assert( child( pParent, left_child, memory_model::memory_order_relaxed ) == pNode
1538                  || child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
1539
1540             // pParent and pNode is locked yet
1541             {
1542                 assert( pRight != nullptr );
1543                 node_scoped_lock l( m_Monitor, *pRight );
1544                 if ( pNode->m_pRight.load( memory_model::memory_order_relaxed ) != pRight )
1545                     return pNode; // retry for pNode
1546
1547                 int hR = pRight->height( memory_model::memory_order_relaxed );
1548                 if ( hL - hR >= -1 )
1549                     return pNode; // retry
1550
1551                 node_type * pRLeft = child( pRight, left_child, memory_model::memory_order_relaxed );
1552                 int hRL = pRLeft ? pRLeft->height( memory_model::memory_order_relaxed ) : 0;
1553                 node_type * pRRight = child( pRight, right_child, memory_model::memory_order_relaxed );
1554                 int hRR = pRRight ? pRRight->height( memory_model::memory_order_relaxed ) : 0;
1555                 if ( hRR > hRL )
1556                     return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
1557
1558                 {
1559                     assert( pRLeft != nullptr );
1560                     node_scoped_lock lrl( m_Monitor, *pRLeft );
1561                     if ( pRight->m_pLeft.load( memory_model::memory_order_relaxed ) != pRLeft )
1562                         return pNode; // retry
1563
1564                     hRL = pRLeft->height( memory_model::memory_order_relaxed );
1565                     if ( hRR >= hRL )
1566                         return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
1567
1568                     node_type * pRLRight = child( pRLeft, right_child, memory_model::memory_order_relaxed );
1569                     int hRLR = pRLRight ? pRLRight->height( memory_model::memory_order_relaxed ) : 0;
1570                     int balance = hRR - hRLR;
1571                     if ( balance >= -1 && balance <= 1 && !((hRR == 0 || hRLR == 0) && !pRight->is_valued( memory_model::memory_order_relaxed )))
1572                          return rotate_left_over_right_locked( pParent, pNode, hL, pRight, pRLeft, hRR, hRLR );
1573                 }
1574                 return rebalance_to_right_locked( pNode, pRight, pRLeft, hRR );
1575             }
1576         }
1577
1578         static void begin_change( node_type * pNode, version_type version )
1579         {
1580             pNode->version( version | node_type::shrinking, memory_model::memory_order_release );
1581         }
1582         static void end_change( node_type * pNode, version_type version )
1583         {
1584             // Clear shrinking and unlinked flags and increment version
1585             pNode->version( (version | node_type::version_flags) + 1, memory_model::memory_order_release );
1586         }
1587
1588         node_type * rotate_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR, int hLL, node_type * pLRight, int hLR )
1589         {
1590             version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
1591             node_type * pParentLeft = child( pParent, left_child, memory_model::memory_order_relaxed );
1592
1593             begin_change( pNode, nodeVersion );
1594
1595             pNode->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
1596             if ( pLRight != nullptr )
1597                 pLRight->m_pParent.store( pNode, memory_model::memory_order_relaxed  );
1598
1599             pLeft->m_pRight.store( pNode, memory_model::memory_order_relaxed );
1600             pNode->m_pParent.store( pLeft, memory_model::memory_order_relaxed );
1601
1602             if ( pParentLeft == pNode )
1603                 pParent->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
1604             else {
1605                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1606                 pParent->m_pRight.store( pLeft, memory_model::memory_order_relaxed );
1607             }
1608             pLeft->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1609
1610             // fix up heights links
1611             int hNode = 1 + std::max( hLR, hR );
1612             pNode->height( hNode, memory_model::memory_order_relaxed );
1613             pLeft->height( 1 + std::max( hLL, hNode ), memory_model::memory_order_relaxed );
1614
1615             end_change( pNode, nodeVersion );
1616             m_stat.onRotateRight();
1617
1618             // We have damaged pParent, pNode (now parent.child.right), and pLeft (now
1619             // parent.child).  pNode is the deepest.  Perform as many fixes as we can
1620             // with the locks we've got.
1621
1622             // We've already fixed the height for pNode, but it might still be outside
1623             // our allowable balance range.  In that case a simple fix_height_locked()
1624             // won't help.
1625             int nodeBalance = hLR - hR;
1626             if ( nodeBalance < -1 || nodeBalance > 1 ) {
1627                 // we need another rotation at pNode
1628                 return pNode;
1629             }
1630
1631             // we've fixed balance and height damage for pNode, now handle
1632             // extra-routing node damage
1633             if ( (pLRight == nullptr || hR == 0) && !pNode->is_valued(memory_model::memory_order_relaxed)) {
1634                 // we need to remove pNode and then repair
1635                 return pNode;
1636             }
1637
1638             // we've already fixed the height at pLeft, do we need a rotation here?
1639             int leftBalance = hLL - hNode;
1640             if ( leftBalance < -1 || leftBalance > 1 )
1641                 return pLeft;
1642
1643             // pLeft might also have routing node damage (if pLeft.left was null)
1644             if ( hLL == 0 && !pLeft->is_valued( memory_model::memory_order_relaxed ))
1645                 return pLeft;
1646
1647             // try to fix the parent height while we've still got the lock
1648             return fix_height_locked( pParent );
1649         }
1650
1651         node_type * rotate_left_locked( node_type * pParent, node_type * pNode, int hL, node_type * pRight, node_type * pRLeft, int hRL, int hRR )
1652         {
1653             version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
1654             node_type * pParentLeft = child( pParent, left_child, memory_model::memory_order_relaxed );
1655
1656             begin_change( pNode, nodeVersion );
1657
1658             // fix up pNode links, careful to be compatible with concurrent traversal for all but pNode
1659             pNode->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
1660             if ( pRLeft != nullptr )
1661                 pRLeft->m_pParent.store( pNode, memory_model::memory_order_relaxed );
1662
1663             pRight->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
1664             pNode->m_pParent.store( pRight, memory_model::memory_order_relaxed );
1665
1666             if ( pParentLeft == pNode )
1667                 pParent->m_pLeft.store( pRight, memory_model::memory_order_relaxed );
1668             else {
1669                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1670                 pParent->m_pRight.store( pRight, memory_model::memory_order_relaxed );
1671             }
1672             pRight->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1673
1674             // fix up heights
1675             int hNode = 1 + std::max( hL, hRL );
1676             pNode->height( hNode, memory_model::memory_order_relaxed );
1677             pRight->height( 1 + std::max( hNode, hRR ), memory_model::memory_order_relaxed );
1678
1679             end_change( pNode, nodeVersion );
1680             m_stat.onRotateLeft();
1681
1682             int nodeBalance = hRL - hL;
1683             if ( nodeBalance < -1 || nodeBalance > 1 )
1684                 return pNode;
1685
1686             if ( (pRLeft == nullptr || hL == 0) && !pNode->is_valued( memory_model::memory_order_relaxed ))
1687                 return pNode;
1688
1689             int rightBalance = hRR - hNode;
1690             if ( rightBalance < -1 || rightBalance > 1 )
1691                 return pRight;
1692
1693             if ( hRR == 0 && !pRight->is_valued( memory_model::memory_order_relaxed ))
1694                 return pRight;
1695
1696             return fix_height_locked( pParent );
1697         }
1698
1699         node_type * rotate_right_over_left_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR, int hLL, node_type * pLRight, int hLRL )
1700         {
1701             version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
1702             version_type leftVersion = pLeft->version( memory_model::memory_order_relaxed );
1703
1704             node_type * pPL = child( pParent, left_child, memory_model::memory_order_relaxed );
1705             node_type * pLRL = child( pLRight, left_child, memory_model::memory_order_relaxed );
1706             node_type * pLRR = child( pLRight, right_child, memory_model::memory_order_relaxed );
1707             int hLRR = pLRR ? pLRR->height( memory_model::memory_order_relaxed ) : 0;
1708
1709             begin_change( pNode, nodeVersion );
1710             begin_change( pLeft, leftVersion );
1711
1712             // fix up pNode links, careful about the order!
1713             pNode->m_pLeft.store( pLRR, memory_model::memory_order_relaxed );
1714             if ( pLRR != nullptr )
1715                 pLRR->m_pParent.store( pNode, memory_model::memory_order_relaxed );
1716
1717             pLeft->m_pRight.store( pLRL, memory_model::memory_order_relaxed );
1718             if ( pLRL != nullptr )
1719                 pLRL->m_pParent.store( pLeft, memory_model::memory_order_relaxed );
1720
1721             pLRight->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
1722             pLeft->m_pParent.store( pLRight, memory_model::memory_order_relaxed );
1723             pLRight->m_pRight.store( pNode, memory_model::memory_order_relaxed );
1724             pNode->m_pParent.store( pLRight, memory_model::memory_order_relaxed );
1725
1726             if ( pPL == pNode )
1727                 pParent->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
1728             else {
1729                 assert( child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
1730                 pParent->m_pRight.store( pLRight, memory_model::memory_order_relaxed );
1731             }
1732             pLRight->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1733
1734             // fix up heights
1735             int hNode = 1 + std::max( hLRR, hR );
1736             pNode->height( hNode, memory_model::memory_order_relaxed );
1737             int hLeft = 1 + std::max( hLL, hLRL );
1738             pLeft->height( hLeft, memory_model::memory_order_relaxed );
1739             pLRight->height( 1 + std::max( hLeft, hNode ), memory_model::memory_order_relaxed );
1740
1741             end_change( pNode, nodeVersion );
1742             end_change( pLeft, leftVersion );
1743             m_stat.onRotateRightOverLeft();
1744
1745             // caller should have performed only a single rotation if pLeft was going
1746             // to end up damaged
1747             assert( hLL - hLRL <= 1 && hLRL - hLL <= 1 );
1748             assert( !((hLL == 0 || pLRL == nullptr) && !pLeft->is_valued( memory_model::memory_order_relaxed )));
1749
1750             // We have damaged pParent, pLR (now parent.child), and pNode (now
1751             // parent.child.right).  pNode is the deepest.  Perform as many fixes as we
1752             // can with the locks we've got.
1753
1754             // We've already fixed the height for pNode, but it might still be outside
1755             // our allowable balance range.  In that case a simple fix_height_locked()
1756             // won't help.
1757             int nodeBalance = hLRR - hR;
1758             if ( nodeBalance < -1 || nodeBalance > 1 ) {
1759                 // we need another rotation at pNode
1760                 return pNode;
1761             }
1762
1763             // pNode might also be damaged by being an unnecessary routing node
1764             if ( (pLRR == nullptr || hR == 0) && !pNode->is_valued( memory_model::memory_order_relaxed )) {
1765                 // repair involves splicing out pNode and maybe more rotations
1766                 return pNode;
1767             }
1768
1769             // we've already fixed the height at pLRight, do we need a rotation here?
1770             int balanceLR = hLeft - hNode;
1771             if ( balanceLR < -1 || balanceLR > 1 )
1772                 return pLRight;
1773
1774             // try to fix the parent height while we've still got the lock
1775             return fix_height_locked( pParent );
1776         }
1777
1778         node_type * rotate_left_over_right_locked( node_type * pParent, node_type * pNode, int hL, node_type * pRight, node_type * pRLeft, int hRR, int hRLR )
1779         {
1780             version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
1781             version_type rightVersion = pRight->version( memory_model::memory_order_relaxed );
1782
1783             node_type * pPL = child( pParent, left_child, memory_model::memory_order_relaxed );
1784             node_type * pRLL = child( pRLeft, left_child, memory_model::memory_order_relaxed );
1785             node_type * pRLR = child( pRLeft, right_child, memory_model::memory_order_relaxed );
1786             int hRLL = pRLL ? pRLL->height( memory_model::memory_order_relaxed ) : 0;
1787
1788             begin_change( pNode, nodeVersion );
1789             begin_change( pRight, rightVersion );
1790
1791             // fix up pNode links, careful about the order!
1792             pNode->m_pRight.store( pRLL, memory_model::memory_order_relaxed );
1793             if ( pRLL != nullptr )
1794                 pRLL->m_pParent.store( pNode, memory_model::memory_order_relaxed );
1795
1796             pRight->m_pLeft.store( pRLR, memory_model::memory_order_relaxed );
1797             if ( pRLR != nullptr )
1798                 pRLR->m_pParent.store( pRight, memory_model::memory_order_relaxed );
1799
1800             pRLeft->m_pRight.store( pRight, memory_model::memory_order_relaxed );
1801             pRight->m_pParent.store( pRLeft, memory_model::memory_order_relaxed );
1802             pRLeft->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
1803             pNode->m_pParent.store( pRLeft, memory_model::memory_order_relaxed );
1804
1805             if ( pPL == pNode )
1806                 pParent->m_pLeft.store( pRLeft, memory_model::memory_order_relaxed );
1807             else {
1808                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1809                 pParent->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
1810             }
1811             pRLeft->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1812
1813             // fix up heights
1814             int hNode = 1 + std::max( hL, hRLL );
1815             pNode->height( hNode, memory_model::memory_order_relaxed );
1816             int hRight = 1 + std::max( hRLR, hRR );
1817             pRight->height( hRight, memory_model::memory_order_relaxed );
1818             pRLeft->height( 1 + std::max( hNode, hRight ), memory_model::memory_order_relaxed );
1819
1820             end_change( pNode, nodeVersion );
1821             end_change( pRight, rightVersion );
1822             m_stat.onRotateLeftOverRight();
1823
1824             assert( hRR - hRLR <= 1 && hRLR - hRR <= 1 );
1825
1826             int nodeBalance = hRLL - hL;
1827             if ( nodeBalance < -1 || nodeBalance > 1 )
1828                 return pNode;
1829             if ( (pRLL == nullptr || hL == 0) && !pNode->is_valued( memory_model::memory_order_relaxed ))
1830                 return pNode;
1831
1832             int balRL = hRight - hNode;
1833             if ( balRL < -1 || balRL > 1 )
1834                 return pRLeft;
1835
1836             return fix_height_locked( pParent );
1837         }
1838
1839         //@endcond
1840     };
1841 }} // namespace cds::container
1842
1843 #endif // #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H