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