cds/container/impl/bronson_avltree_map_rcu.h

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