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