cds/container/impl/bronson_avltree_map_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H
   4 #define __CDS_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H
   5
   6 #include <cds/container/details/bronson_avltree_base.h>
   7 #include <cds/urcu/details/check_deadlock.h>
   8
   9 namespace cds { namespace container {
  10
  11     /// Bronson et al AVL-tree (RCU specialization for storing pointer to values)
  12     /** @ingroup cds_nonintrusive_map
  13         @ingroup cds_nonintrusive_tree
  14         @headerfile cds/container/bronson_avltree_map_rcu.h
  15
  16         This is the specialization of \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based Bronson et al AVL-tree"
  17         for "key -> value pointer" map. This specialization stores the pointer to user-allocated values instead of the copy
  18         of the value. When a tree node is removed, the algorithm does not free the value pointer directly, instead, it call
  19         the disposer functor provided by \p Traits template parameter.
  20
  21         The set of available member functions is differ from classic map.
  22
  23         <b>Template arguments</b>:
  24         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  25         - \p Key - key type
  26         - \p T - value type to be stored in tree's nodes. Note, the specialization stores the pointer to user-allocated
  27             value, not the copy.
  28         - \p Traits - tree traits, default is \p bronson_avltree::traits
  29             It is possible to declare option-based tree with \p bronson_avltree::make_traits metafunction
  30             instead of \p Traits template argument.
  31
  32         @note Before including <tt><cds/container/bronson_avltree_map_rcu.h></tt> you should include appropriate RCU header file,
  33         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  34     */
  35     template <
  36         typename RCU,
  37         typename Key,
  38         typename T,
  39 #   ifdef CDS_DOXYGEN_INVOKED
  40         typename Traits = bronson_avltree::traits
  41 #else
  42         typename Traits
  43 #endif
  44     >
  45     class BronsonAVLTreeMap< cds::urcu::gc<RCU>, Key, T*, Traits >
  46     {
  47     public:
  48         typedef cds::urcu::gc<RCU>  gc;   ///< RCU Garbage collector
  49         typedef Key     key_type;    ///< type of a key stored in the map
  50         typedef T *     mapped_type; ///< type of value stored in the map
  51         typedef Traits  traits;      ///< Traits template parameter
  52
  53 #   ifdef CDS_DOXYGEN_INVOKED
  54         typedef implementation_defined key_comparator;    ///< key compare functor based on \p Traits::compare and \p Traits::less
  55 #   else
  56         typedef typename opt::details::make_comparator< key_type, traits >::type key_comparator;
  57 #endif
  58         typedef typename traits::item_counter           item_counter;       ///< Item counting policy
  59         typedef typename traits::memory_model           memory_model;       ///< Memory ordering, see \p cds::opt::memory_model option
  60         typedef typename traits::allocator              allocator_type;     ///< allocator for maintaining internal node
  61         typedef typename traits::stat                   stat;               ///< internal statistics
  62         typedef typename traits::rcu_check_deadlock     rcu_check_deadlock; ///< Deadlock checking policy
  63         typedef typename traits::back_off               back_off;           ///< Back-off strategy
  64         typedef typename traits::disposer               disposer;           ///< Value disposer
  65         typedef typename traits::lock_type              lock_type;          ///< Node lock type
  66
  67         /// Enabled or disabled @ref bronson_avltree::relaxed_insert "relaxed insertion"
  68         static bool const c_bRelaxedInsert = traits::relaxed_insert;
  69
  70     protected:
  71         //@cond
  72         typedef bronson_avltree::node< key_type, mapped_type, lock_type > node_type;
  73
  74         typedef typename std::conditional <
  75             std::is_same< typename traits::node_type, opt::none >::value,
  76             bronson_avltree::node< key_type, mapped_type, lock_type >,
  77             typename traits::node_type
  78         >::type alloc_node_type;
  79
  80         typedef typename allocator_type::template rebind<alloc_node_type>::other memory_allocator;
  81         typedef cds::details::Allocator< alloc_node_type, memory_allocator > cxx_allocator;
  82
  83         typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock >   check_deadlock_policy;
  84
  85         enum class find_result
  86         {
  87             not_found,
  88             found,
  89             retry
  90         };
  91
  92         enum class update_flags
  93         {
  94             allow_insert = 1,
  95             allow_update = 2,
  96             retry = 4,
  97
  98             failed = 0,
  99             result_insert = allow_insert,
 100             result_update = allow_update
 101         };
 102
 103         enum node_condition
 104         {
 105             nothing_required = -3,
 106             rebalance_required = -2,
 107             unlink_required = -1
 108         };
 109
 110         class node_scoped_lock
 111         {
 112             node_type *     m_pNode;
 113         public:
 114             node_scoped_lock( node_type * pNode )
 115                 : m_pNode( pNode )
 116             {
 117                 pNode->m_Lock.lock();
 118             }
 119
 120             ~node_scoped_lock()
 121             {
 122                 m_pNode->m_Lock.unlock();
 123             }
 124         };
 125
 126         //@endcond
 127
 128     protected:
 129         //@cond
 130         template <typename K>
 131         static node_type * alloc_node( K&& key, int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight )
 132         {
 133             alloc_node_type * pNode = memory_allocator().allocate( 1 );
 134             return new (static_cast<node_type *>(pNode)) node_type( std::forward<K>( key ), nHeight, version, pParent, pLeft, pRight );
 135         }
 136
 137         static void internal_free_node( node_type * pNode )
 138         {
 139             // Free node without disposer
 140             cxx_allocator().Delete( static_cast<alloc_node_type *>(pNode) );
 141         }
 142
 143         static void dispose_node( node_type * pNode )
 144         {
 145             mapped_type * pVal = pNode->value( memory_model::memory_order_relaxed );
 146             if ( pVal ) {
 147                 pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
 148                 disposer()(pVal);
 149             }
 150             //TODO: deallocate pNode in safe manner
 151         }
 152
 153         //@endcond
 154
 155     protected:
 156         //@cond
 157         typename node_type::base_class      m_Root;
 158         node_type *                         m_pRoot;
 159         item_counter                        m_ItemCounter;
 160         mutable stat                        m_stat;
 161         //@endcond
 162
 163     public:
 164         /// Creates empty map
 165         BronsonAVLTreeMap()
 166             : m_pRoot( static_cast<node_type *>(&m_Root) )
 167         {}
 168
 169         /// Destroys the map
 170         ~BronsonAVLTreeMap()
 171         {
 172             unsafe_clear();
 173         }
 174
 175         /// Inserts new node
 176         /**
 177             The \p key_type should be constructible from a value of type \p K.
 178
 179             RCU \p synchronize() can be called. RCU should not be locked.
 180
 181             Returns \p true if inserting successful, \p false otherwise.
 182         */
 183         template <typename K>
 184         bool insert( K const& key, mapped_type * pVal )
 185         {
 186             return do_update( key,
 187                 [pVal]( node_type * pNode ) -> mapped_type*
 188                 {
 189                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 190                     return pVal;
 191                 },
 192                 update_flags::allow_insert
 193             ) == update_flags::result_insert;
 194         }
 195
 196         /// Updates the value for \p key
 197         /**
 198             The operation performs inserting or updating the value for \p key with lock-free manner.
 199             If \p bInsert is \p false, only updating of existing node is possible.
 200
 201             If \p key is not found and inserting is allowed (i.e. \p bInsert is \p true),
 202             then the new node created from \p key is inserted into the map; note that in this case the \ref key_type should be
 203             constructible from type \p K.
 204             Otherwise, the value is changed to \p pVal.
 205
 206             RCU \p synchronize() method can be called. RCU should not be locked.
 207
 208             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
 209             \p second is \p true if new node has been added or \p false if the node with \p key
 210             already is in the tree.
 211         */
 212         template <typename K, typename Func>
 213         std::pair<bool, bool> update( K const& key, mapped_type * pVal, bool bInsert = true )
 214         {
 215             int result = do_update( key,
 216                 [pVal]( node_type * ) -> mapped_type*
 217                 {
 218                     return pVal;
 219                 },
 220                 update_flags::allow_update | (bInsert ? update_flags::allow_insert : 0)
 221             );
 222             return std::make_pair( result != 0, (result & update_flags::result_insert) != 0 );
 223         }
 224
 225         /// Delete \p key from the map
 226         /**
 227             RCU \p synchronize() method can be called. RCU should not be locked.
 228
 229             Return \p true if \p key is found and deleted, \p false otherwise
 230         */
 231         template <typename K>
 232         bool erase( K const& key )
 233         {
 234             //TODO
 235         }
 236
 237         /// Deletes the item from the map using \p pred predicate for searching
 238         /**
 239             The function is an analog of \p erase(K const&)
 240             but \p pred is used for key comparing.
 241             \p Less functor has the interface like \p std::less.
 242             \p Less must imply the same element order as the comparator used for building the map.
 243         */
 244         template <typename K, typename Less>
 245         bool erase_with( K const& key, Less pred )
 246         {
 247             CDS_UNUSED( pred );
 248             //TODO
 249         }
 250
 251         /// Delete \p key from the map
 252         /**
 253             The function searches an item with key \p key, calls \p f functor
 254             and deletes the item. If \p key is not found, the functor is not called.
 255
 256             The functor \p Func interface:
 257             \code
 258             struct extractor {
 259                 void operator()(mapped_type& item) { ... }
 260             };
 261             \endcode
 262
 263             RCU \p synchronize method can be called. RCU should not be locked.
 264
 265             Return \p true if key is found and deleted, \p false otherwise
 266         */
 267         template <typename K, typename Func>
 268         bool erase( K const& key, Func f )
 269         {
 270             //TODO
 271         }
 272
 273         /// Deletes the item from the map using \p pred predicate for searching
 274         /**
 275             The function is an analog of \p erase(K const&, Func)
 276             but \p pred is used for key comparing.
 277             \p Less functor has the interface like \p std::less.
 278             \p Less must imply the same element order as the comparator used for building the map.
 279         */
 280         template <typename K, typename Less, typename Func>
 281         bool erase_with( K const& key, Less pred, Func f )
 282         {
 283             CDS_UNUSED( pred );
 284             //TODO
 285         }
 286
 287         /// Extracts an item with minimal key from the map
 288         /**
 289             Returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the leftmost item.
 290             If the set is empty, returns empty \p exempt_ptr.
 291
 292             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
 293             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 294             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 295             So, the function returns the item with minimum key at the moment of tree traversing.
 296
 297             RCU \p synchronize method can be called. RCU should NOT be locked.
 298             The function does not free the item.
 299             The deallocator will be implicitly invoked when the returned object is destroyed or when
 300             its \p release() member function is called.
 301         */
 302         exempt_ptr extract_min()
 303         {
 304             //TODO
 305         }
 306
 307         /// Extracts an item with maximal key from the map
 308         /**
 309             Returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the rightmost item.
 310             If the set is empty, returns empty \p exempt_ptr.
 311
 312             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
 313             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 314             During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
 315             So, the function returns the item with maximum key at the moment of tree traversing.
 316
 317             RCU \p synchronize method can be called. RCU should NOT be locked.
 318             The function does not free the item.
 319             The deallocator will be implicitly invoked when the returned object is destroyed or when
 320             its \p release() is called.
 321             @note Before reusing \p result object you should call its \p release() method.
 322         */
 323         exempt_ptr extract_max()
 324         {
 325             //TODO
 326         }
 327
 328         /// Extracts an item from the map
 329         /**
 330             The function searches an item with key equal to \p key in the tree,
 331             unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
 332             If \p key is not found the function returns an empty \p exempt_ptr.
 333
 334             RCU \p synchronize method can be called. RCU should NOT be locked.
 335             The function does not destroy the item found.
 336             The dealloctor will be implicitly invoked when the returned object is destroyed or when
 337             its \p release() member function is called.
 338         */
 339         template <typename Q>
 340         exempt_ptr extract( Q const& key )
 341         {
 342             //TODO
 343         }
 344
 345         /// Extracts an item from the map using \p pred for searching
 346         /**
 347             The function is an analog of \p extract(exempt_ptr&, Q const&)
 348             but \p pred is used for key compare.
 349             \p Less has the interface like \p std::less and should meet \ref cds_container_EllenBinTreeSet_rcu_less
 350             "predicate requirements".
 351             \p pred must imply the same element order as the comparator used for building the map.
 352         */
 353         template <typename Q, typename Less>
 354         exempt_ptr extract_with( Q const& val, Less pred )
 355         {
 356             CDS_UNUSED( pred );
 357             //TODO
 358         }
 359
 360         /// Find the key \p key
 361         /**
 362             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 363             The interface of \p Func functor is:
 364             \code
 365             struct functor {
 366                 void operator()( mapped_type& item );
 367             };
 368             \endcode
 369             where \p item is the item found.
 370             The functor is called under node-level lock.
 371
 372             The function applies RCU lock internally.
 373
 374             The function returns \p true if \p key is found, \p false otherwise.
 375         */
 376         template <typename K, typename Func>
 377         bool find( K const& key, Func f )
 378         {
 379             return do_find( key, key_comparator(), [&f]( node_type * pNode ) -> bool {
 380                 node_scoped_lock l( pNode );
 381                 mapped_type * pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
 382                 if ( pVal ) {
 383                     f( *pVal );
 384                     return true;
 385                 }
 386                 return false;
 387             });
 388         }
 389
 390         /// Finds the key \p val using \p pred predicate for searching
 391         /**
 392             The function is an analog of \p find(K const&, Func)
 393             but \p pred is used for key comparing.
 394             \p Less functor has the interface like \p std::less.
 395             \p Less must imply the same element order as the comparator used for building the map.
 396         */
 397         template <typename K, typename Less, typename Func>
 398         bool find_with( K const& key, Less pred, Func f )
 399         {
 400             CDS_UNUSED( pred );
 401             return do_find( key, opt::details::make_comparator_from_less<Less>(), [&f]( node_type * pNode ) -> bool {
 402                 node_scoped_lock l( pNode );
 403                 mapped_type * pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
 404                 if ( pVal ) {
 405                     f( *pVal );
 406                     return true;
 407                 }
 408                 return false;
 409             } );
 410         }
 411
 412         /// Find the key \p key
 413         /**
 414             The function searches the item with key equal to \p key
 415             and returns \p true if it is found, and \p false otherwise.
 416
 417             The function applies RCU lock internally.
 418         */
 419         template <typename K>
 420         bool find( K const& key )
 421         {
 422             return do_find( key, key_comparator(), []( node_type * ) -> bool { return true; });
 423         }
 424
 425         /// Finds the key \p val using \p pred predicate for searching
 426         /**
 427             The function is an analog of \p find(K const&)
 428             but \p pred is used for key comparing.
 429             \p Less functor has the interface like \p std::less.
 430             \p Less must imply the same element order as the comparator used for building the map.
 431         */
 432         template <typename K, typename Less>
 433         bool find_with( K const& key, Less pred )
 434         {
 435             CDS_UNUSED( pred );
 436             return do_find( key, opt::details::make_comparator_from_less<Less>(), []( node_type * ) -> bool { return true; } );
 437         }
 438
 439         /// Finds \p key and return the item found
 440         /**
 441             The function searches the item with key equal to \p key and returns the pointer to item found.
 442             If \p key is not found it returns \p nullptr.
 443
 444             RCU should be locked before call the function.
 445             Returned pointer is valid while RCU is locked.
 446         */
 447         template <typename Q>
 448         mapped_type * get( Q const& key ) const
 449         {
 450             //TODO
 451         }
 452
 453         /// Finds \p key with \p pred predicate and return the item found
 454         /**
 455             The function is an analog of \p get(Q const&)
 456             but \p pred is used for comparing the keys.
 457
 458             \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type
 459             and \p Q in any order.
 460             \p pred must imply the same element order as the comparator used for building the map.
 461         */
 462         template <typename Q, typename Less>
 463         mapped_type * get_with( Q const& key, Less pred ) const
 464         {
 465             CDS_UNUSED( pred );
 466             //TODO
 467         }
 468
 469         /// Clears the tree (thread safe, not atomic)
 470         /**
 471             The function unlink all items from the tree.
 472             The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
 473             this sequence
 474             \code
 475             set.clear();
 476             assert( set.empty() );
 477             \endcode
 478             the assertion could be raised.
 479
 480             For each node the \ref disposer will be called after unlinking.
 481
 482             RCU \p synchronize method can be called. RCU should not be locked.
 483         */
 484         void clear()
 485         {
 486             for ( exempt_ptr ep = extract_min(); !ep.empty(); ep = extract_min() )
 487                 ep.release();
 488         }
 489
 490         /// Clears the tree (not thread safe)
 491         /**
 492             This function is not thread safe and may be called only when no other thread deals with the tree.
 493             The function is used in the tree destructor.
 494         */
 495         void unsafe_clear()
 496         {
 497             //TODO
 498         }
 499
 500         /// Checks if the map is empty
 501         bool empty() const
 502         {
 503             return m_Root.m_pRight.load( memory_model::memory_order_relaxed ) == nullptr;
 504         }
 505
 506         /// Returns item count in the map
 507         /**
 508             Only leaf nodes containing user data are counted.
 509
 510             The value returned depends on item counter type provided by \p Traits template parameter.
 511             If it is \p atomicity::empty_item_counter this function always returns 0.
 512
 513             The function is not suitable for checking the tree emptiness, use \p empty()
 514             member function for this purpose.
 515         */
 516         size_t size() const
 517         {
 518             return m_ItemCounter;
 519         }
 520
 521         /// Returns const reference to internal statistics
 522         stat const& statistics() const
 523         {
 524             return m_Stat;
 525         }
 526
 527         /// Checks internal consistency (not atomic, not thread-safe)
 528         /**
 529             The debugging function to check internal consistency of the tree.
 530         */
 531         bool check_consistency() const
 532         {
 533             //TODO
 534         }
 535
 536     protected:
 537         //@cond
 538         template <typename Q, typename Compare, typename Func>
 539         bool do_find( Q& key, Compare cmp, Func f ) const
 540         {
 541             find_result result;
 542             {
 543                 rcu_lock l;
 544                 result = try_find( key, cmp, f, m_pRoot, 1, 0 );
 545             }
 546             assert( result != find_result::retry );
 547             return result == find_result::found;
 548         }
 549
 550         template <typename K, typename Func>
 551         int do_update( K const& key, Func funcUpdate, int nFlags )
 552         {
 553             check_deadlock_policy::check();
 554
 555             rcu_lock l;
 556             return try_udate( key, pVal, nFlags, m_pRoot, 1, 0 );
 557         }
 558
 559         //@endcond
 560
 561     private:
 562         //@cond
 563         template <typename Q, typename Compare, typename Func>
 564         find_result try_find( Q const& key, Compare cmp, Func f, node_type * pNode, int nDir, typename node_type::version_type nVersion ) const
 565         {
 566             assert( gc::is_locked() );
 567             assert( pNode );
 568
 569             while ( true ) {
 570                 node_type * pChild = pNode->child( nDir ).load( memory_model::memory_order_relaxed );
 571                 if ( !pChild ) {
 572                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
 573                         m_stat.onFindRetry();
 574                         return find_result::retry;
 575                     }
 576
 577                     m_stat.onFindFailed();
 578                     return find_result::not_found;
 579                 }
 580
 581                 int nCmp = cmp( key, pChild->m_key );
 582                 if ( nCmp == 0 ) {
 583                     if ( pChild->is_valued( memory_model::memory_order_relaxed ) ) {
 584                         // key found
 585                         if ( f( pChild ) ) {
 586                             m_stat.onFindSuccess();
 587                             return find_result::found;
 588                         }
 589                     }
 590
 591                     m_stat.onFindFailed();
 592                     return find_result::not_found;
 593                 }
 594
 595                 typename node_type::version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
 596                 if ( nChildVersion & node_type::shrinking ) {
 597                     m_stat.onFindWaitShrinking();
 598                     pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
 599
 600                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
 601                         m_stat.onFindRetry();
 602                         return find_result::retry;
 603                     }
 604                 }
 605                 else if ( nChildVersion != node_type::unlinked ) {
 606
 607                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
 608                         m_stat.onFindRetry();
 609                         return find_result::retry;
 610                     }
 611
 612                     find_result found = try_find( key, cmp, f, pChild, nCmp, nChildVersion );
 613                     if ( found != find_result::retry )
 614                         return found;
 615                 }
 616             }
 617         }
 618
 619         template <typename K, typename Func>
 620         int try_update( K const& key, Func funcUpdate, int nFlags, node_type * pNode, int nDir, typename node_type::version_type nVersion )
 621         {
 622             int result;
 623             do {
 624                 node_type * pChild = pNode->child( nDir ).load( memory_model::memory_order_relaxed );
 625                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
 626                     return update_flags::retry;
 627
 628                 if ( pChild == nullptr ) {
 629                     // insert new node
 630                     if ( nFlags & update_flags::allow_insert )
 631                         result = try_insert_node( key, funcUpdate, pNode, nDir, nVersion );
 632                     else
 633                         result = update_flags::failed;
 634                 }
 635                 else {
 636                     //TODO
 637                 }
 638             } while ( result == update_flags::retry );
 639             return result;
 640         }
 641
 642         template <typename K, typename Func>
 643         int try_insert_node( K const& key, Func funcUpdate, node_type * pNode, int nDir, typename node_type::version_type nVersion )
 644         {
 645             node_type * pNew;
 646
 647             auto fnCreateNode = [&funcUpdate]( node_type * pNew ) {
 648                 mapped_type * pVal = funcUpdate( pNew );
 649                 assert( pVal != nullptr );
 650                 pNew->m_pValue.store( pVal, memory_model::memory_order_relaxed );
 651             };
 652
 653             if ( c_bRelaxedInsert ) {
 654                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
 655                      || pNode->child( nDir ).load( memory_model::memory_order_relaxed ) != nullptr )
 656                 {
 657                     m_stat.onInsertRetry();
 658                     return update_flags::retry;
 659                 }
 660
 661                 fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
 662             }
 663
 664             node_type * pDamaged;
 665             {
 666                 node_scoped_lock l( pNode );
 667
 668                 if ( pNode->version( memory_model::memory_order_relaxed ) != nVersion
 669                      || pNode->child( nDir ).load( memory_model::memory_order_relaxed ) != nullptr )
 670                 {
 671                     if ( c_RelaxedInsert ) {
 672                         internal_free_node( pNew );
 673                         m_stat.onRelaxedInsertFailed();
 674                     }
 675
 676                     m_stat.onInsertRetry();
 677                     return update_flags::retry;
 678                 }
 679
 680                 if ( !c_bRelaxedInsert )
 681                     fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
 682
 683                 pNode->child( pNew, nDir, memory_model::memory_order_relaxed );
 684                 pDamaged = fix_height_locked( pNode );
 685             }
 686             m_stat.onInsertSuccess();
 687
 688             fix_height_and_rebalance( pDamaged );
 689
 690             return update_flags::result_insert;
 691         }
 692
 693         bool try_unlink_locked( node_type * pParent, node_type * pNode )
 694         {
 695             // pParent and pNode must be locked
 696             assert( !pParent->is_unlinked(memory_model::memory_order_relaxed) );
 697
 698             node_type * pParentLeft = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
 699             node_type * pParentRight = pParent->m_pRight.load( memory_model::memory_order_relaxed );
 700             if ( pNode != pParentLeft && pNode != pParentRight ) {
 701                 // node is no longer a child of parent
 702                 return false;
 703             }
 704
 705             assert( !pNode->is_unlinked());
 706             assert( pParent == pNode->m_pParent.load(memory_model::memory_order_relaxed));
 707
 708             node_type * pLeft = pNode->m_pLeft.load( memory_model::memory_order_relaxed );
 709             node_type * pRight = pNode->m_pRight.load( memory_model::memory_order_relaxed );
 710             if ( pLeft != nullptr && pRight != nullptr ) {
 711                 // splicing is no longer possible
 712                 return false;
 713             }
 714             node_type * pSplice = pLeft ? pLeft : pRight;
 715
 716             if ( pParentLeft == pNode )
 717                 pParent->m_pLeft.store( pSplice, memory_model::memory_order_relaxed );
 718             else
 719                 pParent->m_pRight.store( pSplice, memory_model::memory_order_relaxed );
 720
 721             if ( pSplice )
 722                 pSplice->pParent.store( pParent, memory_model::memory_order_release );
 723
 724             pNode->version( node_type::unlinked, memory_model::memory_order_release );
 725             dispose_node( pNode );
 726
 727             return true;
 728         }
 729
 730         //@endcond
 731     private: // rotations
 732         //@cond
 733         int estimate_node_condition( node_type * pNode )
 734         {
 735             node_type * pLeft = pNode->m_pLeft.load( memory_model::memory_order_relaxed );
 736             node_type * pRight = pNode->m_pRight.load( memory_model::memory_order_relaxed );
 737
 738             if ( (pLeft == nullptr || pRight == nullptr) && pNode->value( memory_model::memory_order_relaxed ) == nullptr )
 739                 return unlink_required;
 740
 741             int h = pNode->height( memory_model::memory_order_relaxed );
 742             int hL = pLeft ? pLeft->height( memory_model::memory_order_relaxed ) : 0;
 743             int hR = pRight ? pRight->height( memory_model::memory_order_relaxed ) : 0;
 744
 745             int hNew = 1 + std::max( hL, hR );
 746             int nBalance = hL - hR;
 747
 748             if ( nBalance < -1 || nBalance > 1 )
 749                 return rebalance_required;
 750
 751             return h != hNew ? hNew : nothing_required;
 752         }
 753
 754         node_type * fix_height( node_type * pNode )
 755         {
 756             node_scoped_lock l( pNode );
 757             return fix_height_locked( pNode );
 758         }
 759
 760         node_type * fix_height_locked( node_type * pNode )
 761         {
 762             // pNode must be locked!!!
 763             int h = estimate_node_condition( pNode );
 764             switch ( h ) {
 765                 case rebalance_required:
 766                 case unlink_required:
 767                     return pNode;
 768                 case nothing_required:
 769                     return nullptr;
 770                 default:
 771                     pNode->height( h, memory_model::memory_order_relaxed );
 772                     return pNode->m_pParent.load( memory_model::memory_order_relaxed );
 773             }
 774         }
 775
 776         void fix_height_and_rebalance( node_type * pNode )
 777         {
 778             while ( pNode && pNode->m_pParent.load( memory_model::memory_order_relaxed ) ) {
 779                 int nCond = estimate_node_condition( pNode );
 780                 if ( nCond == nothing_required || pNode->is_unlinked( memory_model::memory_order_relaxed ) )
 781                     return;
 782
 783                 if ( nCond != unlink_required && nCond != rebalance_required )
 784                     pNode = fix_height( pNode );
 785                 else {
 786                     node_type * pParent = pNode->m_pParent.load( memory_model::memry_order_relaxed );
 787                     assert( pParent != nullptr );
 788                     {
 789                         node_scoped_lock lp( pParent );
 790                         if ( !pParent->is_unlinked( memory_model::memory_order_relaxed )
 791                              && pNode->m_pParent.load( memory_model::memory_order_relaxed ) == pParent )
 792                         {
 793                             node_scoped_lock ln( pNode );
 794                             pNode = rebalance_locked( pParent, pNode );
 795                         }
 796                     }
 797                 }
 798             }
 799         }
 800
 801         node_type * rebalance_locked( node_type * pParent, node_type * pNode )
 802         {
 803             // pParent and pNode shlould be locked.
 804             // Returns a damaged node, or nullptr if no more rebalancing is necessary
 805             assert( pNode->m_pParent.load( memory_model::memry_order_relaxed ) == pNode );
 806             assert( m_pParent->m_pLeft.load( memory_model::memory_order_relaxed ) == pNode
 807                  || m_pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
 808
 809             node_type * pLeft = pNode->m_pLeft.load( memory_model::memory_order_relaxed );
 810             node_type * pRight = pNode->m_pRight.load( memory_model::memory_order_relaxed );
 811
 812             if ( (pLeft == nullptr || pRight == nullptr) && pNode->value( memory_model::memory_order_relaxed ) == nullptr ) {
 813                 if ( try_unlink_locked( pParent, pNode ))
 814                     return fix_height_locked( pParent );
 815                 else {
 816                     // retry needed for pNode
 817                     return pNode;
 818                 }
 819             }
 820
 821             int h = pNode->height( memory_model::memory_order_relaxed );
 822             int hL = pLeft ? pLeft->height( memory_model::memory_order_relaxed ) : 0;
 823             int hR = pRight ? pRight->height( memory_model::memory_order_relaxed ) : 0;
 824             int hNew = 1 + std::max( hL, hR );
 825             int balance = hL - hR;
 826
 827             if ( balance > 1 )
 828                 return rebalance_to_right_locked( pParent, pNode, pLeft, hR );
 829             else if ( balance < -1 )
 830                 return rebalance_to_left_locked( pParent, pNode, pRight, hL );
 831             else if ( hNew != h ) {
 832                 pNode->height( hNew, memory_model::memory_order_relaxed );
 833
 834                 // pParent is already locked
 835                 return fix_height_locked( pParent );
 836             }
 837             else
 838                 return nullptr;
 839         }
 840
 841         node_type * rebalance_to_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR )
 842         {
 843             assert( pNode->m_pParent.load( memory_model::memry_order_relaxed ) == pNode );
 844             assert( m_pParent->m_pLeft.load( memory_model::memory_order_relaxed ) == pNode
 845                  || m_pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
 846
 847             // pParent and pNode is locked yet
 848             // pNode->pLeft is too large, we will rotate-right.
 849             // If pLeft->pRight is taller than pLeft->pLeft, then we will first rotate-left pLeft.
 850
 851             {
 852                 node_scoped_lock l( pLeft );
 853                 if ( pNode->m_pLeft.load( memory_model::memory_order_relaxed ) != pLeft )
 854                     return pNode; // retry for pNode
 855
 856                 int hL = pLeft->height( memory_model::memory_order_relaxed );
 857                 if ( hL - hR <= 1 )
 858                     return pNode; // retry
 859
 860                 node_type * pLRight = pLeft->m_pRight.load( memory_model::memory_order_relaxed );
 861                 int hLR = pLRight ? pLRight->height( memory_model::memory_order_relaxed ) : 0;
 862                 node_type * pLLeft = pLeft->m_pLeft.load( memory_model::memory_order_relaxed );
 863                 int hLL = pLLeft ? pLLeft->height( memory_model::memory_order_relaxed ) : 0;
 864
 865                 if ( hLL > hLR ) {
 866                     // rotate right
 867                     return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
 868                 }
 869                 else {
 870                     assert( pLRight != nullptr );
 871                     {
 872                         node_scoped_lock lr( pLRight );
 873                         if ( pLeft->m_pRight.load( memory_model::memory_order_relaxed ) != pLRight )
 874                             return pNode; // retry
 875
 876                         hLR = pLRight->height( memory_model::memory_order_relaxed );
 877                         if ( hLL > hLR )
 878                             return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
 879
 880                         node_type * pLRLeft = pLRight->m_pLeft.load( memory_model::memory_order_relaxed );
 881                         int hLRL = pLRLeft ? pLRLeft->height( memory_model::memory_order_relaxed  ) : 0;
 882                         int balance = hLL - hLRL;
 883                         if ( balance >= -1 && balance <= 1 && !((hLL == 0 || hLRL == 0) && pLeft->value(memory_model::memory_order_relaxed) == nullptr) ) {
 884                             // nParent.child.left won't be damaged after a double rotation
 885                             return rotate_right_over_left_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLRL );
 886                         }
 887                     }
 888
 889                     // focus on pLeft, if necessary pNode will be balanced later
 890                     return rebalance_to_left_locked( pNode, pLeft, pLRight, hLL );
 891                 }
 892             }
 893         }
 894
 895         node_type * rebalance_to_left_locked( node_type * pParent, node_type * pNode, node_type * pRight, int hL )
 896         {
 897             assert( pNode->m_pParent.load( memory_model::memry_order_relaxed ) == pNode );
 898             assert( m_pParent->m_pLeft.load( memory_model::memory_order_relaxed ) == pNode
 899                     || m_pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
 900
 901             // pParent and pNode is locked yet
 902             {
 903                 node_scoped_lock l( pRight );
 904                 if ( pNode->m_pRight.load( memory_model::memory_order_relaxed ) != pRight )
 905                     return pNode; // retry for pNode
 906
 907                 int hR = pRight->height( memory_model::memory_order_relaxed );
 908                 if ( hL - hR >= -1 )
 909                     return pNode; // retry
 910
 911                 node_type * pRLeft = pRight->m_pLeft.load( memory_model::memory_order_relaxed );
 912                 int hRL = pRLeft > pRLeft->height( memory_model::memory_order_relaxed ) : 0;
 913                 node_type * pRRight = pRight->m_pRight.load( memory_model::memory_order_relaxed );
 914                 int hRR = pRRight ? pRRight->height( memory_model::memory_order_relaxed ) : 0;
 915                 if ( hRR > hRL )
 916                     return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
 917
 918                 {
 919                     assert( pRLeft != nullptr );
 920                     node_scoped_lock lrl( pRLeft );
 921                     if ( pRight->m_pLeft.load( memory_model::memory_order_relaxed ) != pRLeft )
 922                         return pNode; // retry
 923
 924                     hRL = pRLeft->height( memory_model::memory_order_relaxed );
 925                     if ( hRR >= hRL )
 926                         return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
 927
 928                     node_type * pRLRight = pRLeft->m_pRight.load( memory_model::memory_order_relaxed );
 929                     int hRLR = pRLRight ? pRLRight->height( memory_model::memory_order_relaxed ) : 0;
 930                     int balance = hRR - hRLR;
 931                     if ( b >= -1 && b <= 1 && !((hRR == 0 || hRLR == 0) && pRight->value( memory_odel::memory_order_relaxed ) == nullptr)
 932                          return rotate_left_over_right_locked( pParent, pNode, hL, pRight, pRLeft, hRR, hRLR );
 933                 }
 934                 return rebalance_to_right_locked( pNode, pRight, pRLeft, hRR );
 935             }
 936         }
 937
 938         static void begin_change( node_type * pNode, typename node_type::version_type version )
 939         {
 940             pNode->version( version | node_type::shrinking, memory_model::memory_order_release );
 941         }
 942         static void end_change( node_type * pNode, tpename node_type::version_type version )
 943         {
 944             // Clear shrinking nd unlinked flags and increment version
 945             pNode->version( (version | node_type::version_flags) + 1, memory_model::memory_order_release );
 946         }
 947
 948         node_type * rotate_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR, int hLL, node_type * pLRight, int hLR )
 949         {
 950             node_type::version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
 951             node_type * pParentLeft = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
 952
 953             begin_change( pNode, nodeVersion );
 954
 955             pNode->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
 956             if ( pLRight != nullptr )
 957                 pLRight->m_pParent.store( pNode, memory_model::memory_order_relaxed  );
 958
 959             pLeft->m_pRight.store( pNode, memory_model::memory_order_relaxed );
 960             pNode->m_pParent.store( pLeft, memory_model::memory_order_relaxed );
 961
 962             if ( pParentLeft == pNode )
 963                 pParent->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
 964             else {
 965                 assert( pParent->m_pRight.load( memory_odel::memory_order_relaxed ) == pNode );
 966                 pParent->m_pRight.store( pLeft, memory_mdel::memory_order_relaxed );
 967             }
 968             pLeft->m_pParent.store( pParent, memory_model::memory_order_relaxed );
 969
 970             // fix up heights links
 971             int hNode = 1 + std::max( hLR, hR );
 972             pNode->height( hNode, memory_model::memory_order_relaxed );
 973             pLeft->height( 1 + std::max( hLL, hNode ), memory_model::memory_order_relaxed );
 974
 975             end_change( pNode, nodeVersion );
 976
 977             // We have damaged pParent, pNode (now parent.child.right), and pLeft (now
 978             // parent.child).  pNode is the deepest.  Perform as many fixes as we can
 979             // with the locks we've got.
 980
 981             // We've already fixed the height for pNode, but it might still be outside
 982             // our allowable balance range.  In that case a simple fix_height_locked()
 983             // won't help.
 984             int nodeBalance = hLR - hR;
 985             if ( nodeBalance < -1 || nodeBalance > 1 ) {
 986                 // we need another rotation at pNode
 987                 return pNode;
 988             }
 989
 990             // we've fixed balance and height damage for pNode, now handle
 991             // extra-routing node damage
 992             if ( (pLRight == nullptr || hR == 0) && pNode->value(memory_model::memory_order_relaxed) == nullptr ) {
 993                 // we need to remove pNode and then repair
 994                 return pNode;
 995             }
 996
 997             // we've already fixed the height at pLeft, do we need a rotation here?
 998             int leftBalance = hLL - hNode;
 999             if ( leftBalance < -1 || leftBalance > 1 )
1000                 return pLeft;
1001
1002             // pLeft might also have routing node damage (if pLeft.left was null)
1003             if ( hLL == 0 && pLeft->value( memory_model::memory_order_relaxed ) == nullptr )
1004                 return pLeft;
1005
1006             // try to fix the parent height while we've still got the lock
1007             return fix_height_locked( pParent );
1008         }
1009
1010         node_type * rotate_left_locked( node_type * pParent, node_type * pNode, int hL, node_type * pRight, node_type * pRLeft, int hRL, int hRR )
1011         {
1012             typename node_type::version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
1013             node_type * pParentLeft = pParent->m_pLeft.load( memory_odel::memory_order_relaxed );
1014
1015             begin_change( pNode, nodeVersion );
1016
1017             // fix up pNode links, careful to be compatible with concurrent traversal for all but pNode
1018             pNode->m_pRight.store( pRLeft, memory_nodel::memory_order_relaxed );
1019             if ( pRLeft != nullptr )
1020                 pRLeft->m_pParent.store( pNode, memory_model::memory_order_relaxed );
1021
1022             pRight->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
1023             pNode->m_pParent.store( pRight, memory_model::memory_order_relaxed );
1024
1025             if ( pParentLeft == pNode )
1026                 pParent->m_pLeft.store( pRight, memory_model::memory_order_relaxed );
1027             else {
1028                 assert( pParent->m_pRight.load( memory_odel::memory_order_relaxed ) == pNode );
1029                 pParent->m_pRight.store( pRight, memory_model::memory_model_relaxed );
1030             }
1031             pRight->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1032
1033             // fix up heights
1034             int hNode = 1 + std::max( hL, hRL );
1035             pNode->height( hNode, memory_model::memory_order_relaxed );
1036             pRight->height( 1 + std::max( hNode, hRR ), memory_model::memory_order_relaxed );
1037
1038             end_change( pNode, nodeVersion );
1039
1040             int nodeBalance = hRL - hL;
1041             if ( nodeBalance < -1 || nodeBalance > 1 )
1042                 return pNode;
1043
1044             if ( (pRLeft == nullptr || hL == 0) && pNode->value( memory_model::memory_order_relaxed ) == nullptr )
1045                 return pNode;
1046
1047             int rightBalance = hRR - hNode;
1048             if ( rightBalance < -1 || rightBalance > 1 )
1049                 return pRight;
1050
1051             if ( hRR == 0 && pRight->value( memory_model::memory_order_relaxed ) == nullptr )
1052                 return pRight;
1053
1054             return fix_height_locked( pParent );
1055         }
1056
1057         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 )
1058         {
1059             typename node_type::value_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
1060             typename node_type::value_type leftVersion = pLeft->version( memory_model::memory_order_relaxed );
1061
1062             node_type * pPL = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1063             node_type * pLRL = pLRight->m_pLeft.load( memory_model::memory_order_relaxed );
1064             node_type * pLRR = pLRight->m_pRight.load( memory_model::memory_order_relaxed );
1065             int hLRR = pLRR ? pLRR->hight( memory_model::memory_order_relaxed ) : 0;
1066
1067             begin_change( pNode, nodeVersion );
1068             begin_change( pLeft, leftVersion );
1069
1070             // fix up pNode links, careful about the order!
1071             pNode->m_pLeft.store( pLRR, memory_model::memory_order_relaxed );
1072             if ( pLRR != nullptr )
1073                 pLRR->m_pParent.store( pNode, memory_model::memory_order_relaxed );
1074
1075             pLeft->m_pRight.store( pLRL, memory_model::memory_order_relaxed );
1076             if ( pLRL != nullptr )
1077                 pLRL->m_pParent.store( pLeft, memory_model::memory_order_relaxed );
1078
1079             pLRight->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
1080             pLeft->m_pParent.store( pLRight, memory_model::memory_order_relaxed );
1081             pLRight->m_pRight.store( pNode, memory_model::memory_order_relaxed );
1082             pNode->m_pParent.store( pLRight, memory_model::memory_order_relaxed );
1083
1084             if ( pPL == pNode )
1085                 pParent->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
1086             else {
1087                 assert( Parent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1088                 pParent->m_pRight.store( pLRight, memory_model::memory_order_relaxed );
1089             }
1090             pLRight->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1091
1092             // fix up heights
1093             int hNode = 1 + std::max( hLRR, hR );
1094             pNode->height( hNode, memory_model::memory_order_relaxed );
1095             int hLeft = 1 + std::max( hLL, hLRL );
1096             pLeft->height( hLeft, memory_model::memory_order_relaxed );
1097             pLRight->height( 1 + std::max( hLeft, hNode ), memory_model::memory_order_relaxed );
1098
1099             end_change( pNode, nodeVersion );
1100             end_change( pLeft, leftVersion );
1101
1102             // caller should have performed only a single rotation if pLeft was going
1103             // to end up damaged
1104             assert( hLL - hLRL <= 1 && hLRL - hLL <= 1 );
1105             assert( !((hLL == 0 || pLRL == nullptr) && pLeft->value( memory_model::memory_order_relaxed ) == nullptr ));
1106
1107             // We have damaged pParent, pLR (now parent.child), and pNode (now
1108             // parent.child.right).  pNode is the deepest.  Perform as many fixes as we
1109             // can with the locks we've got.
1110
1111             // We've already fixed the height for pNode, but it might still be outside
1112             // our allowable balance range.  In that case a simple fix_height_locked()
1113             // won't help.
1114             int nodeBalance = hLRR - hR;
1115             if ( nodeBalance < -1 || nodeBalance > 1 ) {
1116                 // we need another rotation at pNode
1117                 return pNode;
1118             }
1119
1120             // pNode might also be damaged by being an unnecessary routing node
1121             if ( (pLRR == nullptr || hR == 0) && pNode->value( memory_model::memory_order_relaxed ) == nullptr ) {
1122                 // repair involves splicing out pNode and maybe more rotations
1123                 return pNode;
1124             }
1125
1126             // we've already fixed the height at pLRight, do we need a rotation here?
1127             final int balanceLR = hLeft - hNode;
1128             if ( balanceLR < -1 || balanceLR > 1 )
1129                 return pLR;
1130
1131             // try to fix the parent height while we've still got the lock
1132             return fix_height_locked( pParent );
1133         }
1134
1135         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 )
1136         {
1137             typename node_type::version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
1138             typename node_type::version_type rightVersion = pRight->version( memory_model::memory_order_relaxed );
1139
1140             node_type * pPL = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1141             node_type * pRLL = pRLeft->m_pLeft.load( memory_model::memory_order_relaxed );
1142             node_type * pRLR = pRLeft->m_pRight.load( memory_model::memory_order_relaxed );
1143             int hRLL = pRLL ? pRLL->height( memory_model::memory_order_relaxed ) : 0;
1144
1145             begin_change( pNode, nodeVersion );
1146             begin_change( pRight, ghtVersion );
1147
1148             // fix up pNode links, careful about the order!
1149             pNode->m_pRight.store( pRLL, memory_model::memory_order_relaxed );
1150             if ( pRLL != nullptr )
1151                 pRLL->m_pParent.store( pNode, memory_model::memory_order_relaxed );
1152
1153             pRight->m_pLeft.store( pRLR, memory_model::memory_order_relaxed );
1154             if ( pRLR != nullptr )
1155                 pRLR->m_pParent.store( pRight, memory_model::memory_order_relaxed );
1156
1157             pRLeft->m_pRight.store( pRight, memory_model::memory_order_relaxed );
1158             pRight->m_pParent.store( pRLeft, memory_model::memory_order_relaxed );
1159             pRLeft->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
1160             pNode->m_pParent.store( pRLeft, memory_model::memory_order_relaxed );
1161
1162             if ( pPL == pNode )
1163                 pParent->m_pLeft.store( pRLeft, memory_model::memory_order_relaxed );
1164             else {
1165                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1166                 pParent->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
1167             }
1168             pRLeft->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1169
1170             // fix up heights
1171             int hNode = 1 + std::max( hL, hRLL );
1172             pNode->height( hNode, memory_model::memory_order_relaxed );
1173             int hRight = 1 + std::max( hRLR, hRR );
1174             pRight->height( hRight, memory_model::memory_order_relaxed );
1175             pRLeft->height( 1 + std::max( hNode, hRight ), memory_model::memory_order_relaxed );
1176
1177             end_change( pNode, nodeVersion );
1178             end_change( pRight, rightVersion );
1179
1180             assert( hRR - hRLR <= 1 && hRLR - hRR <= 1 );
1181
1182             int nodeBalance = hRLL - hL;
1183             if ( nodeBalance < -1 || nodeBalance > 1 )
1184                 return pNode;
1185             if ( (pRLL == nullptr || hL == 0) && pNode->value( memory_model::memory_order_relaxed ) == nullptr )
1186                 return pNode;
1187
1188             int balRL = hRight - hNode;
1189             if ( balRL < -1 || balRL > 1 )
1190                 return pRLeft;
1191
1192             return fix_height_locked( pParent );
1193         }
1194
1195         //@endcond
1196     };
1197 }} // namespace cds::container
1198
1199 #endif // #ifndef __CDS_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H