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 = memory_model::memory_order_relaxed )
 156         {
 157             return pNode->child( nDir ).load( order );
 158         }
 159
 160         static node_type * parent( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
 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 );
 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                 key_comparator cmp;
 766                 node_type * pLeft = child( pNode, left_child );
 767                 node_type * pRight = child( pNode, right_child );
 768                 if ( pLeft && cmp( pLeft->m_key, pNode->m_key ) > 0 )
 769                     ++nErrors;
 770                 if (  pRight && cmp( pNode->m_key, pRight->m_key ) > 0 )
 771                     ++nErrors;
 772
 773                 size_t hLeft = do_check_consistency( pLeft, nLevel + 1, f, nErrors );
 774                 size_t hRight = do_check_consistency( pRight, nLevel + 1, f, nErrors );
 775
 776                 if ( hLeft >= hRight ) {
 777                     if ( hLeft - hRight > 1 ) {
 778                         f( nLevel, hLeft, hRight );
 779                         ++nErrors;
 780                     }
 781                     return hLeft;
 782                 }
 783                 else {
 784                     if ( hRight - hLeft > 1 ) {
 785                         f( nLevel, hLeft, hRight );
 786                         ++nErrors;
 787                     }
 788                     return hRight;
 789                 }
 790             }
 791             return 0;
 792         }
 793
 794         template <typename Q, typename Compare, typename Func>
 795         bool do_find( Q& key, Compare cmp, Func f ) const
 796         {
 797             find_result result;
 798             {
 799                 rcu_lock l;
 800                 result = try_find( key, cmp, f, m_pRoot, 1, 0 );
 801             }
 802             assert( result != find_result::retry );
 803             return result == find_result::found;
 804         }
 805
 806         template <typename K, typename Compare, typename Func>
 807         int do_update( K const& key, Compare cmp, Func funcUpdate, int nFlags )
 808         {
 809             check_deadlock_policy::check();
 810
 811             rcu_disposer removed_list;
 812             {
 813                 rcu_lock l;
 814                 return try_update_root( key, cmp, nFlags, funcUpdate, removed_list );
 815             }
 816         }
 817
 818         template <typename K, typename Compare, typename Func>
 819         bool do_remove( K const& key, Compare cmp, Func func )
 820         {
 821             // Func must return true if the value was disposed
 822             //              or false if the value was extracted
 823
 824             check_deadlock_policy::check();
 825
 826             rcu_disposer removed_list;
 827             {
 828                 rcu_lock l;
 829                 return try_remove_root( key, cmp, func, removed_list );
 830             }
 831         }
 832
 833         template <typename Func>
 834         mapped_type do_extract_min( Func f )
 835         {
 836             mapped_type pExtracted = nullptr;
 837             do_extract_minmax(
 838                 left_child,
 839                 [&pExtracted, &f]( key_type const& key, mapped_type pVal, rcu_disposer& ) -> bool { f( key ); pExtracted = pVal; return false; }
 840             );
 841             return pExtracted;
 842         }
 843
 844         template <typename Func>
 845         mapped_type do_extract_max( Func f )
 846         {
 847             mapped_type pExtracted = nullptr;
 848             do_extract_minmax(
 849                 right_child,
 850                 [&pExtracted, &f]( key_type const& key, mapped_type pVal, rcu_disposer& ) -> bool { f( key ); pExtracted = pVal; return false; }
 851             );
 852             return pExtracted;
 853         }
 854
 855         template <typename Func>
 856         void do_extract_minmax( int nDir, Func func )
 857         {
 858             check_deadlock_policy::check();
 859
 860             rcu_disposer removed_list;
 861             {
 862                 rcu_lock l;
 863
 864                 int result = update_flags::failed;
 865                 do {
 866                     // get right child of root
 867                     node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
 868                     if ( pChild ) {
 869                         version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
 870                         if ( nChildVersion & node_type::shrinking ) {
 871                             m_stat.onRemoveRootWaitShrinking();
 872                             pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
 873                             result = update_flags::retry;
 874                         }
 875                         else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
 876                             result = try_extract_minmax( nDir, func, m_pRoot, pChild, nChildVersion, removed_list );
 877                         }
 878                     }
 879                 } while ( result == update_flags::retry );
 880             }
 881         }
 882
 883         template <typename Q>
 884         mapped_type do_extract( Q const& key )
 885         {
 886             mapped_type pExtracted = nullptr;
 887             do_remove(
 888                 key,
 889                 key_comparator(),
 890                 [&pExtracted]( key_type const&, mapped_type pVal, rcu_disposer& ) -> bool { pExtracted = pVal; return false; }
 891             );
 892             return pExtracted;
 893         }
 894
 895         template <typename Q, typename Less>
 896         mapped_type do_extract_with( Q const& key, Less pred )
 897         {
 898             CDS_UNUSED( pred );
 899             mapped_type pExtracted = nullptr;
 900             do_remove(
 901                 key,
 902                 cds::opt::details::make_comparator_from_less<Less>(),
 903                 [&pExtracted]( key_type const&, mapped_type pVal, rcu_disposer& ) -> bool { pExtracted = pVal; return false; }
 904             );
 905             return pExtracted;
 906         }
 907         //@endcond
 908
 909     private:
 910         //@cond
 911         static int height( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
 912         {
 913             assert( pNode );
 914             return pNode->m_nHeight.load( order );
 915         }
 916         static void set_height( node_type * pNode, int h, atomics::memory_order order = memory_model::memory_order_relaxed )
 917         {
 918             assert( pNode );
 919             pNode->m_nHeight.store( h, order );
 920         }
 921         static int height_null( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
 922         {
 923             return pNode ? height( pNode, order ) : 0;
 924         }
 925
 926         template <typename Q, typename Compare, typename Func>
 927         find_result try_find( Q const& key, Compare cmp, Func f, node_type * pNode, int nDir, version_type nVersion ) const
 928         {
 929             assert( gc::is_locked() );
 930             assert( pNode );
 931
 932             while ( true ) {
 933                 node_type * pChild = child( pNode, nDir );
 934                 if ( !pChild ) {
 935                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
 936                         m_stat.onFindRetry();
 937                         return find_result::retry;
 938                     }
 939
 940                     m_stat.onFindFailed();
 941                     return find_result::not_found;
 942                 }
 943
 944                 int nCmp = cmp( key, pChild->m_key );
 945                 if ( nCmp == 0 ) {
 946                     if ( pChild->is_valued( memory_model::memory_order_relaxed ) ) {
 947                         // key found
 948                         node_scoped_lock l( m_Monitor, *pChild );
 949                         if ( pChild->is_valued( memory_model::memory_order_relaxed )) {
 950                             if ( f( pChild ) ) {
 951                                 m_stat.onFindSuccess();
 952                                 return find_result::found;
 953                             }
 954                         }
 955                     }
 956
 957                     m_stat.onFindFailed();
 958                     return find_result::not_found;
 959                 }
 960
 961                 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
 962                 if ( nChildVersion & node_type::shrinking ) {
 963                     m_stat.onFindWaitShrinking();
 964                     pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
 965
 966                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
 967                         m_stat.onFindRetry();
 968                         return find_result::retry;
 969                     }
 970                 }
 971                 else if ( nChildVersion != node_type::unlinked ) {
 972                     if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
 973                         m_stat.onFindRetry();
 974                         return find_result::retry;
 975                     }
 976
 977                     find_result found = try_find( key, cmp, f, pChild, nCmp, nChildVersion );
 978                     if ( found != find_result::retry )
 979                         return found;
 980                 }
 981
 982                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
 983                     m_stat.onFindRetry();
 984                     return find_result::retry;
 985                 }
 986             }
 987         }
 988
 989         template <typename K, typename Compare, typename Func>
 990         int try_update_root( K const& key, Compare cmp, int nFlags, Func funcUpdate, rcu_disposer& disp )
 991         {
 992             assert( gc::is_locked() );
 993
 994             int result;
 995             do {
 996                 // get right child of root
 997                 node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
 998                 if ( pChild ) {
 999                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1000                     if ( nChildVersion & node_type::shrinking ) {
1001                         m_stat.onUpdateRootWaitShrinking();
1002                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1003                         result = update_flags::retry;
1004                     }
1005                     else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
1006                         result = try_update( key, cmp, nFlags, funcUpdate, pChild, nChildVersion, disp );
1007                     }
1008                     else
1009                         result = update_flags::retry;
1010                 }
1011                 else {
1012                     // the tree is empty
1013                     if ( nFlags & update_flags::allow_insert ) {
1014                         // insert into tree as right child of the root
1015                         {
1016                             node_scoped_lock l( m_Monitor, *m_pRoot );
1017                             if ( child( m_pRoot, right_child, memory_model::memory_order_acquire ) != nullptr ) {
1018                                 result = update_flags::retry;
1019                                 continue;
1020                             }
1021
1022                             node_type * pNew = alloc_node( key, 1, 0, m_pRoot, nullptr, nullptr );
1023                             mapped_type pVal = funcUpdate( pNew );
1024                             assert( pVal != nullptr );
1025                             pNew->m_pValue.store( pVal, memory_model::memory_order_release );
1026
1027                             m_pRoot->child( pNew, right_child, memory_model::memory_order_relaxed );
1028                             set_height( m_pRoot, 2 );
1029                         }
1030
1031                         ++m_ItemCounter;
1032                         m_stat.onInsertSuccess();
1033                         return update_flags::result_inserted;
1034                     }
1035
1036                     return update_flags::failed;
1037                 }
1038             } while ( result == update_flags::retry );
1039             return result;
1040         }
1041
1042         template <typename K, typename Compare, typename Func>
1043         bool try_remove_root( K const& key, Compare cmp, Func func, rcu_disposer& disp )
1044         {
1045             assert( gc::is_locked() );
1046
1047             int result;
1048             do {
1049                 // get right child of root
1050                 node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
1051                 if ( pChild ) {
1052                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1053                     if ( nChildVersion & node_type::shrinking ) {
1054                         m_stat.onRemoveRootWaitShrinking();
1055                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1056                         result = update_flags::retry;
1057                     }
1058                     else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
1059                         result = try_remove( key, cmp, func, m_pRoot, pChild, nChildVersion, disp );
1060                     }
1061                     else
1062                         result = update_flags::retry;
1063                 }
1064                 else
1065                     return false;
1066             } while ( result == update_flags::retry );
1067
1068             return result == update_flags::result_removed;
1069         }
1070
1071         template <typename K, typename Compare, typename Func>
1072         int try_update( K const& key, Compare cmp, int nFlags, Func funcUpdate, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1073         {
1074             assert( gc::is_locked() );
1075             assert( nVersion != node_type::unlinked );
1076
1077             int nCmp = cmp( key, pNode->m_key );
1078             if ( nCmp == 0 ) {
1079                 if ( nFlags & update_flags::allow_update ) {
1080                     return try_update_node( funcUpdate, pNode, nVersion, disp );
1081                 }
1082                 return update_flags::failed;
1083             }
1084
1085             int result;
1086             do {
1087                 node_type * pChild = child( pNode, nCmp );
1088                 if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1089                     m_stat.onUpdateRetry();
1090                     return update_flags::retry;
1091                 }
1092
1093                 if ( pChild == nullptr ) {
1094                     // insert new node
1095                     if ( nFlags & update_flags::allow_insert )
1096                         result = try_insert_node( key, funcUpdate, pNode, nCmp, nVersion, disp );
1097                     else
1098                         result = update_flags::failed;
1099                 }
1100                 else {
1101                     // update child
1102                     result = update_flags::retry;
1103                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1104                     if ( nChildVersion & node_type::shrinking ) {
1105                         m_stat.onUpdateWaitShrinking();
1106                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1107                         // retry
1108                     }
1109                     else if ( pChild == child( pNode, nCmp )) {
1110                         // this second read is important, because it is protected by nChildVersion
1111
1112                         // validate the read that our caller took to get to node
1113                         if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
1114                             m_stat.onUpdateRetry();
1115                             return update_flags::retry;
1116                         }
1117
1118                         // At this point we know that the traversal our parent took to get to node is still valid.
1119                         // The recursive implementation will validate the traversal from node to
1120                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
1121                         // This means that we are no longer vulnerable to node shrinks, and we don't need
1122                         // to validate node version any more.
1123                         result = try_update( key, cmp, nFlags, funcUpdate, pChild, nChildVersion, disp );
1124                     }
1125                 }
1126
1127                 if ( result == update_flags::retry && pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
1128                     m_stat.onUpdateRetry();
1129                     return update_flags::retry;
1130                 }
1131             } while ( result == update_flags::retry );
1132             return result;
1133         }
1134
1135         template <typename K, typename Compare, typename Func>
1136         int try_remove( K const& key, Compare cmp, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1137         {
1138             assert( gc::is_locked() );
1139             assert( nVersion != node_type::unlinked );
1140
1141             int nCmp = cmp( key, pNode->m_key );
1142             if ( nCmp == 0 )
1143                 return try_remove_node( pParent, pNode, nVersion, func, disp );
1144
1145             int result;
1146             do {
1147                 node_type * pChild = child( pNode, nCmp );
1148                 if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1149                     m_stat.onRemoveRetry();
1150                     return update_flags::retry;
1151                 }
1152
1153                 if ( pChild == nullptr ) {
1154                     return update_flags::failed;
1155                 }
1156                 else {
1157                     // update child
1158                     result = update_flags::retry;
1159                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1160                     if ( nChildVersion & node_type::shrinking ) {
1161                         m_stat.onRemoveWaitShrinking();
1162                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1163                         // retry
1164                     }
1165                     else if ( pChild == child( pNode, nCmp )) {
1166                         // this second read is important, because it is protected by nChildVersion
1167
1168                         // validate the read that our caller took to get to node
1169                         if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
1170                             m_stat.onRemoveRetry();
1171                             return update_flags::retry;
1172                         }
1173
1174                         // At this point we know that the traversal our parent took to get to node is still valid.
1175                         // The recursive implementation will validate the traversal from node to
1176                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
1177                         // This means that we are no longer vulnerable to node shrinks, and we don't need
1178                         // to validate node version any more.
1179                         result = try_remove( key, cmp, func, pNode, pChild, nChildVersion, disp );
1180                     }
1181                 }
1182
1183                 if ( result == update_flags::retry && pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
1184                     m_stat.onRemoveRetry();
1185                     return update_flags::retry;
1186                 }
1187             } while ( result == update_flags::retry );
1188             return result;
1189         }
1190
1191         template <typename Func>
1192         int try_extract_minmax( int nDir, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1193         {
1194             assert( gc::is_locked() );
1195             assert( nVersion != node_type::unlinked );
1196
1197             int result;
1198             do {
1199                 node_type * pChild = child( pNode, nDir );
1200                 if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1201                     m_stat.onRemoveRetry();
1202                     return update_flags::retry;
1203                 }
1204
1205                 if ( pChild == nullptr ) {
1206                     // Found min/max
1207                     return try_remove_node( pParent, pNode, nVersion, func, disp );
1208                 }
1209                 else {
1210                     result = update_flags::retry;
1211                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1212                     if ( nChildVersion & node_type::shrinking ) {
1213                         m_stat.onRemoveWaitShrinking();
1214                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1215                         // retry
1216                     }
1217                     else if ( pChild == child( pNode, nDir )) {
1218                         // this second read is important, because it is protected by nChildVersion
1219
1220                         // validate the read that our caller took to get to node
1221                         if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
1222                             m_stat.onRemoveRetry();
1223                             return update_flags::retry;
1224                         }
1225
1226                         // At this point we know that the traversal our parent took to get to node is still valid.
1227                         // The recursive implementation will validate the traversal from node to
1228                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
1229                         // This means that we are no longer vulnerable to node shrinks, and we don't need
1230                         // to validate node version any more.
1231                         result = try_extract_minmax( nDir, func, pNode, pChild, nChildVersion, disp );
1232                     }
1233                 }
1234
1235                 if ( result == update_flags::retry && pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
1236                     m_stat.onRemoveRetry();
1237                     return update_flags::retry;
1238                 }
1239             } while ( result == update_flags::retry );
1240             return result;
1241         }
1242
1243         template <typename K, typename Func>
1244         int try_insert_node( K const& key, Func funcUpdate, node_type * pNode, int nDir, version_type nVersion, rcu_disposer& disp )
1245         {
1246             node_type * pNew;
1247
1248             auto fnCreateNode = [&funcUpdate]( node_type * pNew ) {
1249                 mapped_type pVal = funcUpdate( pNew );
1250                 assert( pVal != nullptr );
1251                 pNew->m_pValue.store( pVal, memory_model::memory_order_relaxed );
1252             };
1253
1254             if ( c_bRelaxedInsert ) {
1255                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
1256                      || child( pNode, nDir ) != nullptr )
1257                 {
1258                     m_stat.onInsertRetry();
1259                     return update_flags::retry;
1260                 }
1261
1262                 fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
1263             }
1264
1265             node_type * pDamaged;
1266             {
1267                 assert( pNode != nullptr );
1268                 node_scoped_lock l( m_Monitor, *pNode );
1269
1270                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
1271                      || child( pNode, nDir ) != nullptr )
1272                 {
1273                     if ( c_bRelaxedInsert ) {
1274                         mapped_type pVal = pNew->m_pValue.load( memory_model::memory_order_relaxed );
1275                         pNew->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
1276                         free_value( pVal );
1277                         free_node( pNew );
1278                         m_stat.onRelaxedInsertFailed();
1279                     }
1280
1281                     m_stat.onInsertRetry();
1282                     return update_flags::retry;
1283                 }
1284
1285                 if ( !c_bRelaxedInsert )
1286                     fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
1287
1288                 pNode->child( pNew, nDir, memory_model::memory_order_relaxed );
1289                 pDamaged = fix_height_locked( pNode );
1290             }
1291
1292             ++m_ItemCounter;
1293             m_stat.onInsertSuccess();
1294
1295             if ( pDamaged ) {
1296                 fix_height_and_rebalance( pDamaged, disp );
1297                 m_stat.onInsertRebalanceRequired();
1298             }
1299
1300             return update_flags::result_inserted;
1301         }
1302
1303         template <typename Func>
1304         int try_update_node( Func funcUpdate, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1305         {
1306             mapped_type pOld;
1307             assert( pNode != nullptr );
1308             {
1309                 node_scoped_lock l( m_Monitor, *pNode );
1310
1311                 if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1312                     m_stat.onUpdateRetry();
1313                     return update_flags::retry;
1314                 }
1315
1316                 if ( pNode->is_unlinked( memory_model::memory_order_relaxed )) {
1317                     m_stat.onUpdateUnlinked();
1318                     return update_flags::retry;
1319                 }
1320
1321                 pOld = pNode->value( memory_model::memory_order_relaxed );
1322                 mapped_type pVal = funcUpdate( pNode );
1323                 if ( pVal == pOld )
1324                     pOld = nullptr;
1325                 else {
1326                     assert( pVal != nullptr );
1327                     pNode->m_pValue.store( pVal, memory_model::memory_order_relaxed );
1328                 }
1329             }
1330
1331             if ( pOld ) {
1332                 disp.dispose_value(pOld);
1333                 m_stat.onDisposeValue();
1334             }
1335
1336             m_stat.onUpdateSuccess();
1337             return update_flags::result_updated;
1338         }
1339
1340         template <typename Func>
1341         int try_remove_node( node_type * pParent, node_type * pNode, version_type nVersion, Func func, rcu_disposer& disp )
1342         {
1343             assert( pParent != nullptr );
1344             assert( pNode != nullptr );
1345
1346             if ( !pNode->is_valued( atomics::memory_order_relaxed ) )
1347                 return update_flags::failed;
1348
1349             if ( child( pNode, left_child ) == nullptr || child( pNode, right_child ) == nullptr ) {
1350                 node_type * pDamaged;
1351                 mapped_type pOld;
1352                 {
1353                     node_scoped_lock lp( m_Monitor, *pParent );
1354                     if ( pParent->is_unlinked( atomics::memory_order_relaxed ) || parent( pNode ) != pParent )
1355                         return update_flags::retry;
1356
1357                     {
1358                         node_scoped_lock ln( m_Monitor, *pNode );
1359                         pOld = pNode->value( memory_model::memory_order_relaxed );
1360                         if ( !( pNode->version( memory_model::memory_order_acquire ) == nVersion
1361                           && pOld
1362                           && try_unlink_locked( pParent, pNode, disp )))
1363                         {
1364                             return update_flags::retry;
1365                         }
1366                     }
1367                     pDamaged = fix_height_locked( pParent );
1368                 }
1369
1370                 --m_ItemCounter;
1371                 if ( func( pNode->m_key, pOld, disp ))   // calls pOld disposer inside
1372                     m_stat.onDisposeValue();
1373                 else
1374                     m_stat.onExtractValue();
1375
1376                 if ( pDamaged ) {
1377                     fix_height_and_rebalance( pDamaged, disp );
1378                     m_stat.onRemoveRebalanceRequired();
1379                 }
1380                 return update_flags::result_removed;
1381             }
1382             else {
1383                 int result = update_flags::retry;
1384                 mapped_type pOld;
1385                 {
1386                     node_scoped_lock ln( m_Monitor, *pNode );
1387                     pOld = pNode->value( atomics::memory_order_relaxed );
1388                     if ( pNode->version( atomics::memory_order_acquire ) == nVersion && pOld ) {
1389                         pNode->m_pValue.store( nullptr, atomics::memory_order_relaxed );
1390                         result = update_flags::result_removed;
1391                     }
1392                 }
1393
1394                 if ( result == update_flags::result_removed ) {
1395                     --m_ItemCounter;
1396                     if ( func( pNode->m_key, pOld, disp ))  // calls pOld disposer inside
1397                         m_stat.onDisposeValue();
1398                     else
1399                         m_stat.onExtractValue();
1400                 }
1401
1402                 return result;
1403             }
1404         }
1405
1406         bool try_unlink_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp )
1407         {
1408             // pParent and pNode must be locked
1409             assert( !pParent->is_unlinked(memory_model::memory_order_relaxed) );
1410
1411             node_type * pParentLeft = child( pParent, left_child );
1412             node_type * pParentRight = child( pParent, right_child );
1413             if ( pNode != pParentLeft && pNode != pParentRight ) {
1414                 // node is no longer a child of parent
1415                 return false;
1416             }
1417
1418             assert( !pNode->is_unlinked( memory_model::memory_order_relaxed ) );
1419             assert( pParent == parent( pNode ));
1420
1421             node_type * pLeft = child( pNode, left_child );
1422             node_type * pRight = child( pNode, right_child );
1423             if ( pLeft != nullptr && pRight != nullptr ) {
1424                 // splicing is no longer possible
1425                 return false;
1426             }
1427             node_type * pSplice = pLeft ? pLeft : pRight;
1428
1429             if ( pParentLeft == pNode )
1430                 pParent->m_pLeft.store( pSplice, memory_model::memory_order_relaxed );
1431             else
1432                 pParent->m_pRight.store( pSplice, memory_model::memory_order_relaxed );
1433
1434             if ( pSplice )
1435                 pSplice->m_pParent.store( pParent, memory_model::memory_order_release );
1436
1437             // Mark the node as unlinked
1438             pNode->version( node_type::unlinked, memory_model::memory_order_release );
1439
1440             // The value will be disposed by calling function
1441             pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
1442
1443             disp.dispose( pNode );
1444             m_stat.onDisposeNode();
1445
1446             return true;
1447         }
1448
1449         //@endcond
1450
1451     private: // rotations
1452         //@cond
1453         int estimate_node_condition( node_type * pNode )
1454         {
1455             node_type * pLeft = child( pNode, left_child );
1456             node_type * pRight = child( pNode, right_child );
1457
1458             if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_relaxed ))
1459                 return unlink_required;
1460
1461             int h = height( pNode );
1462             int hL = height_null( pLeft );
1463             int hR = height_null( pRight );
1464
1465             int hNew = 1 + std::max( hL, hR );
1466             int nBalance = hL - hR;
1467
1468             if ( nBalance < -1 || nBalance > 1 )
1469                 return rebalance_required;
1470
1471             return h != hNew ? hNew : nothing_required;
1472         }
1473
1474         node_type * fix_height( node_type * pNode )
1475         {
1476             assert( pNode != nullptr );
1477             node_scoped_lock l( m_Monitor, *pNode );
1478             return fix_height_locked( pNode );
1479         }
1480
1481         node_type * fix_height_locked( node_type * pNode )
1482         {
1483             // pNode must be locked!!!
1484             int h = estimate_node_condition( pNode );
1485             switch ( h ) {
1486                 case rebalance_required:
1487                 case unlink_required:
1488                     return pNode;
1489                 case nothing_required:
1490                     return nullptr;
1491                 default:
1492                     set_height( pNode, h );
1493                     return parent( pNode );
1494             }
1495         }
1496
1497         void fix_height_and_rebalance( node_type * pNode, rcu_disposer& disp )
1498         {
1499             while ( pNode && parent( pNode )) {
1500                 int nCond = estimate_node_condition( pNode );
1501                 if ( nCond == nothing_required || pNode->is_unlinked( memory_model::memory_order_relaxed ) )
1502                     return;
1503
1504                 if ( nCond != unlink_required && nCond != rebalance_required )
1505                     pNode = fix_height( pNode );
1506                 else {
1507                     node_type * pParent = parent( pNode );
1508                     assert( pParent != nullptr );
1509                     {
1510                         node_scoped_lock lp( m_Monitor, *pParent );
1511                         if ( !pParent->is_unlinked( memory_model::memory_order_relaxed ) && parent( pNode ) == pParent ) {
1512                             node_scoped_lock ln( m_Monitor, *pNode );
1513                             pNode = rebalance_locked( pParent, pNode, disp );
1514                         }
1515                     }
1516                 }
1517             }
1518         }
1519
1520         node_type * rebalance_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp )
1521         {
1522             // pParent and pNode should be locked.
1523             // Returns a damaged node, or nullptr if no more rebalancing is necessary
1524             assert( parent( pNode ) == pParent );
1525
1526             node_type * pLeft = child( pNode, left_child );
1527             node_type * pRight = child( pNode, right_child );
1528
1529             if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_relaxed )) {
1530                 if ( try_unlink_locked( pParent, pNode, disp ))
1531                     return fix_height_locked( pParent );
1532                 else {
1533                     // retry needed for pNode
1534                     return pNode;
1535                 }
1536             }
1537
1538             assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
1539
1540             int h = height( pNode );
1541             int hL = height_null( pLeft );
1542             int hR = height_null( pRight );
1543             int hNew = 1 + std::max( hL, hR );
1544             int balance = hL - hR;
1545
1546             if ( balance > 1 )
1547                 return rebalance_to_right_locked( pParent, pNode, pLeft, hR );
1548             else if ( balance < -1 )
1549                 return rebalance_to_left_locked( pParent, pNode, pRight, hL );
1550             else if ( hNew != h ) {
1551                 set_height( pNode, hNew );
1552
1553                 // pParent is already locked
1554                 return fix_height_locked( pParent );
1555             }
1556             else
1557                 return nullptr;
1558         }
1559
1560         node_type * rebalance_to_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR )
1561         {
1562             assert( parent( pNode ) == pParent );
1563             assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
1564
1565             // pParent and pNode is locked yet
1566             // pNode->pLeft is too large, we will rotate-right.
1567             // If pLeft->pRight is taller than pLeft->pLeft, then we will first rotate-left pLeft.
1568
1569             {
1570                 assert( pLeft != nullptr );
1571                 node_scoped_lock l( m_Monitor, *pLeft );
1572                 if ( pNode->m_pLeft.load( memory_model::memory_order_relaxed ) != pLeft )
1573                     return pNode; // retry for pNode
1574
1575                 int hL = height( pLeft );
1576                 if ( hL - hR <= 1 )
1577                     return pNode; // retry
1578
1579                 node_type * pLRight = child( pLeft, right_child );
1580                 int hLR = height_null( pLRight );
1581                 node_type * pLLeft = child( pLeft, left_child );
1582                 int hLL = height_null( pLLeft );
1583
1584                 if ( hLL > hLR ) {
1585                     // rotate right
1586                     return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
1587                 }
1588                 else {
1589                     assert( pLRight != nullptr );
1590                     {
1591                         node_scoped_lock lr( m_Monitor, *pLRight );
1592                         if ( pLeft->m_pRight.load( memory_model::memory_order_relaxed ) != pLRight )
1593                             return pNode; // retry
1594
1595                         hLR = height( pLRight );
1596                         if ( hLL > hLR )
1597                             return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
1598
1599                         int hLRL = height_null( child( pLRight, left_child ));
1600                         int balance = hLL - hLRL;
1601                         if ( balance >= -1 && balance <= 1 && !((hLL == 0 || hLRL == 0) && !pLeft->is_valued(memory_model::memory_order_relaxed))) {
1602                             // nParent.child.left won't be damaged after a double rotation
1603                             return rotate_right_over_left_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLRL );
1604                         }
1605                     }
1606
1607                     // focus on pLeft, if necessary pNode will be balanced later
1608                     return rebalance_to_left_locked( pNode, pLeft, pLRight, hLL );
1609                 }
1610             }
1611         }
1612
1613         node_type * rebalance_to_left_locked( node_type * pParent, node_type * pNode, node_type * pRight, int hL )
1614         {
1615             assert( parent( pNode ) == pParent );
1616             assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
1617
1618             // pParent and pNode is locked yet
1619             {
1620                 assert( pRight != nullptr );
1621                 node_scoped_lock l( m_Monitor, *pRight );
1622                 if ( pNode->m_pRight.load( memory_model::memory_order_relaxed ) != pRight )
1623                     return pNode; // retry for pNode
1624
1625                 int hR = height( pRight );
1626                 if ( hL - hR >= -1 )
1627                     return pNode; // retry
1628
1629                 node_type * pRLeft = child( pRight, left_child );
1630                 int hRL = height_null( pRLeft );
1631                 node_type * pRRight = child( pRight, right_child );
1632                 int hRR = height_null( pRRight );
1633                 if ( hRR > hRL )
1634                     return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
1635
1636                 {
1637                     assert( pRLeft != nullptr );
1638                     node_scoped_lock lrl( m_Monitor, *pRLeft );
1639                     if ( pRight->m_pLeft.load( memory_model::memory_order_relaxed ) != pRLeft )
1640                         return pNode; // retry
1641
1642                     hRL = height( pRLeft );
1643                     if ( hRR >= hRL )
1644                         return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
1645
1646                     node_type * pRLRight = child( pRLeft, right_child );
1647                     int hRLR = height_null( pRLRight );
1648                     int balance = hRR - hRLR;
1649                     if ( balance >= -1 && balance <= 1 && !((hRR == 0 || hRLR == 0) && !pRight->is_valued( memory_model::memory_order_relaxed )))
1650                          return rotate_left_over_right_locked( pParent, pNode, hL, pRight, pRLeft, hRR, hRLR );
1651                 }
1652                 return rebalance_to_right_locked( pNode, pRight, pRLeft, hRR );
1653             }
1654         }
1655
1656         static void begin_change( node_type * pNode, version_type version )
1657         {
1658             assert(pNode->version(memory_model::memory_order_acquire) == version );
1659             assert( (version & node_type::shrinking) == 0 );
1660             pNode->version( version | node_type::shrinking, memory_model::memory_order_release );
1661         }
1662         static void end_change( node_type * pNode, version_type version )
1663         {
1664             // Clear shrinking and unlinked flags and increment version
1665             pNode->version( (version | node_type::version_flags) + 1, memory_model::memory_order_release );
1666         }
1667
1668         node_type * rotate_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR, int hLL, node_type * pLRight, int hLR )
1669         {
1670             version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
1671             node_type * pParentLeft = child( pParent, left_child );
1672
1673             begin_change( pNode, nodeVersion );
1674
1675             pNode->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
1676             if ( pLRight != nullptr )
1677                 pLRight->m_pParent.store( pNode, memory_model::memory_order_relaxed  );
1678
1679             atomics::atomic_thread_fence( memory_model::memory_order_release );
1680
1681             pLeft->m_pRight.store( pNode, memory_model::memory_order_relaxed );
1682             pNode->m_pParent.store( pLeft, memory_model::memory_order_relaxed );
1683
1684             atomics::atomic_thread_fence( memory_model::memory_order_release );
1685
1686             if ( pParentLeft == pNode )
1687                 pParent->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
1688             else {
1689                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1690                 pParent->m_pRight.store( pLeft, memory_model::memory_order_relaxed );
1691             }
1692             pLeft->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1693
1694             atomics::atomic_thread_fence( memory_model::memory_order_release );
1695
1696             // fix up heights links
1697             int hNode = 1 + std::max( hLR, hR );
1698             set_height( pNode, hNode );
1699             set_height( pLeft, 1 + std::max( hLL, hNode ));
1700
1701             end_change( pNode, nodeVersion );
1702             m_stat.onRotateRight();
1703
1704             // We have damaged pParent, pNode (now parent.child.right), and pLeft (now
1705             // parent.child).  pNode is the deepest.  Perform as many fixes as we can
1706             // with the locks we've got.
1707
1708             // We've already fixed the height for pNode, but it might still be outside
1709             // our allowable balance range.  In that case a simple fix_height_locked()
1710             // won't help.
1711             int nodeBalance = hLR - hR;
1712             if ( nodeBalance < -1 || nodeBalance > 1 ) {
1713                 // we need another rotation at pNode
1714                 m_stat.onRotateAfterRightRotation();
1715                 return pNode;
1716             }
1717
1718             // we've fixed balance and height damage for pNode, now handle
1719             // extra-routing node damage
1720             if ( (pLRight == nullptr || hR == 0) && !pNode->is_valued(memory_model::memory_order_relaxed)) {
1721                 // we need to remove pNode and then repair
1722                 m_stat.onRemoveAfterRightRotation();
1723                 return pNode;
1724             }
1725
1726             // we've already fixed the height at pLeft, do we need a rotation here?
1727             int leftBalance = hLL - hNode;
1728             if ( leftBalance < -1 || leftBalance > 1 ) {
1729                 m_stat.onRotateAfterRightRotation();
1730                 return pLeft;
1731             }
1732
1733             // pLeft might also have routing node damage (if pLeft.left was null)
1734             if ( hLL == 0 && !pLeft->is_valued(memory_model::memory_order_relaxed) ) {
1735                 m_stat.onDamageAfterRightRotation();
1736                 return pLeft;
1737             }
1738
1739             // try to fix the parent height while we've still got the lock
1740             return fix_height_locked( pParent );
1741         }
1742
1743         node_type * rotate_left_locked( node_type * pParent, node_type * pNode, int hL, node_type * pRight, node_type * pRLeft, int hRL, int hRR )
1744         {
1745             version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
1746             node_type * pParentLeft = child( pParent, left_child );
1747
1748             begin_change( pNode, nodeVersion );
1749
1750             // fix up pNode links, careful to be compatible with concurrent traversal for all but pNode
1751             pNode->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
1752             if ( pRLeft != nullptr )
1753                 pRLeft->m_pParent.store( pNode, memory_model::memory_order_relaxed );
1754
1755             atomics::atomic_thread_fence( memory_model::memory_order_release );
1756
1757             pRight->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
1758             pNode->m_pParent.store( pRight, memory_model::memory_order_relaxed );
1759
1760             atomics::atomic_thread_fence( memory_model::memory_order_release );
1761
1762             if ( pParentLeft == pNode )
1763                 pParent->m_pLeft.store( pRight, memory_model::memory_order_relaxed );
1764             else {
1765                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1766                 pParent->m_pRight.store( pRight, memory_model::memory_order_relaxed );
1767             }
1768             pRight->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1769
1770             atomics::atomic_thread_fence( memory_model::memory_order_release );
1771
1772             // fix up heights
1773             int hNode = 1 + std::max( hL, hRL );
1774             set_height( pNode, hNode );
1775             set_height( pRight, 1 + std::max( hNode, hRR ));
1776
1777             end_change( pNode, nodeVersion );
1778             m_stat.onRotateLeft();
1779
1780             int nodeBalance = hRL - hL;
1781             if ( nodeBalance < -1 || nodeBalance > 1 ) {
1782                 m_stat.onRotateAfterLeftRotation();
1783                 return pNode;
1784             }
1785
1786             if ( (pRLeft == nullptr || hL == 0) && !pNode->is_valued(memory_model::memory_order_relaxed) ) {
1787                 m_stat.onRemoveAfterLeftRotation();
1788                 return pNode;
1789             }
1790
1791             int rightBalance = hRR - hNode;
1792             if ( rightBalance < -1 || rightBalance > 1 ) {
1793                 m_stat.onRotateAfterLeftRotation();
1794                 return pRight;
1795             }
1796
1797             if ( hRR == 0 && !pRight->is_valued(memory_model::memory_order_relaxed) ) {
1798                 m_stat.onDamageAfterLeftRotation();
1799                 return pRight;
1800             }
1801
1802             return fix_height_locked( pParent );
1803         }
1804
1805         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 )
1806         {
1807             version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
1808             version_type leftVersion = pLeft->version( memory_model::memory_order_acquire );
1809
1810             node_type * pPL = child( pParent, left_child );
1811             node_type * pLRL = child( pLRight, left_child );
1812             node_type * pLRR = child( pLRight, right_child );
1813             int hLRR = height_null( pLRR );
1814
1815             begin_change( pNode, nodeVersion );
1816             begin_change( pLeft, leftVersion );
1817
1818             // fix up pNode links, careful about the order!
1819             pNode->m_pLeft.store( pLRR, memory_model::memory_order_relaxed );
1820             if ( pLRR != nullptr )
1821                 pLRR->m_pParent.store( pNode, memory_model::memory_order_relaxed );
1822             atomics::atomic_thread_fence( memory_model::memory_order_release );
1823
1824             pLeft->m_pRight.store( pLRL, memory_model::memory_order_relaxed );
1825             if ( pLRL != nullptr )
1826                 pLRL->m_pParent.store( pLeft, memory_model::memory_order_relaxed );
1827             atomics::atomic_thread_fence( memory_model::memory_order_release );
1828
1829             pLRight->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
1830             pLeft->m_pParent.store( pLRight, memory_model::memory_order_relaxed );
1831             atomics::atomic_thread_fence( memory_model::memory_order_release );
1832
1833             pLRight->m_pRight.store( pNode, memory_model::memory_order_relaxed );
1834             pNode->m_pParent.store( pLRight, memory_model::memory_order_relaxed );
1835             atomics::atomic_thread_fence( memory_model::memory_order_release );
1836
1837             if ( pPL == pNode )
1838                 pParent->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
1839             else {
1840                 assert( child( pParent, right_child ) == pNode );
1841                 pParent->m_pRight.store( pLRight, memory_model::memory_order_relaxed );
1842             }
1843             pLRight->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1844             atomics::atomic_thread_fence( memory_model::memory_order_release );
1845
1846             // fix up heights
1847             int hNode = 1 + std::max( hLRR, hR );
1848             set_height( pNode, hNode );
1849             int hLeft = 1 + std::max( hLL, hLRL );
1850             set_height( pLeft, hLeft );
1851             set_height( pLRight, 1 + std::max( hLeft, hNode ));
1852
1853             end_change( pNode, nodeVersion );
1854             end_change( pLeft, leftVersion );
1855             m_stat.onRotateRightOverLeft();
1856
1857             // caller should have performed only a single rotation if pLeft was going
1858             // to end up damaged
1859             assert( hLL - hLRL <= 1 && hLRL - hLL <= 1 );
1860             assert( !((hLL == 0 || pLRL == nullptr) && !pLeft->is_valued( memory_model::memory_order_relaxed )));
1861
1862             // We have damaged pParent, pLR (now parent.child), and pNode (now
1863             // parent.child.right).  pNode is the deepest.  Perform as many fixes as we
1864             // can with the locks we've got.
1865
1866             // We've already fixed the height for pNode, but it might still be outside
1867             // our allowable balance range.  In that case a simple fix_height_locked()
1868             // won't help.
1869             int nodeBalance = hLRR - hR;
1870             if ( nodeBalance < -1 || nodeBalance > 1 ) {
1871                 // we need another rotation at pNode
1872                 m_stat.onRotateAfterRLRotation();
1873                 return pNode;
1874             }
1875
1876             // pNode might also be damaged by being an unnecessary routing node
1877             if ( (pLRR == nullptr || hR == 0) && !pNode->is_valued( memory_model::memory_order_relaxed )) {
1878                 // repair involves splicing out pNode and maybe more rotations
1879                 m_stat.onRemoveAfterRLRotation();
1880                 return pNode;
1881             }
1882
1883             // we've already fixed the height at pLRight, do we need a rotation here?
1884             int balanceLR = hLeft - hNode;
1885             if ( balanceLR < -1 || balanceLR > 1 ) {
1886                 m_stat.onRotateAfterRLRotation();
1887                 return pLRight;
1888             }
1889
1890             // try to fix the parent height while we've still got the lock
1891             return fix_height_locked( pParent );
1892         }
1893
1894         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 )
1895         {
1896             version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
1897             version_type rightVersion = pRight->version( memory_model::memory_order_acquire );
1898
1899             node_type * pPL = child( pParent, left_child );
1900             node_type * pRLL = child( pRLeft, left_child );
1901             node_type * pRLR = child( pRLeft, right_child );
1902             int hRLL = height_null( pRLL );
1903
1904             begin_change( pNode, nodeVersion );
1905             begin_change( pRight, rightVersion );
1906
1907             // fix up pNode links, careful about the order!
1908             pNode->m_pRight.store( pRLL, memory_model::memory_order_relaxed );
1909             if ( pRLL != nullptr )
1910                 pRLL->m_pParent.store( pNode, memory_model::memory_order_relaxed );
1911             atomics::atomic_thread_fence( memory_model::memory_order_release );
1912
1913             pRight->m_pLeft.store( pRLR, memory_model::memory_order_relaxed );
1914             if ( pRLR != nullptr )
1915                 pRLR->m_pParent.store( pRight, memory_model::memory_order_relaxed );
1916             atomics::atomic_thread_fence( memory_model::memory_order_release );
1917
1918             pRLeft->m_pRight.store( pRight, memory_model::memory_order_relaxed );
1919             pRight->m_pParent.store( pRLeft, memory_model::memory_order_relaxed );
1920             atomics::atomic_thread_fence( memory_model::memory_order_release );
1921
1922             pRLeft->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
1923             pNode->m_pParent.store( pRLeft, memory_model::memory_order_relaxed );
1924             atomics::atomic_thread_fence( memory_model::memory_order_release );
1925
1926             if ( pPL == pNode )
1927                 pParent->m_pLeft.store( pRLeft, memory_model::memory_order_relaxed );
1928             else {
1929                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1930                 pParent->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
1931             }
1932             pRLeft->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1933             atomics::atomic_thread_fence( memory_model::memory_order_release );
1934
1935             // fix up heights
1936             int hNode = 1 + std::max( hL, hRLL );
1937             set_height( pNode, hNode );
1938             int hRight = 1 + std::max( hRLR, hRR );
1939             set_height( pRight, hRight );
1940             set_height( pRLeft, 1 + std::max( hNode, hRight ));
1941
1942             end_change( pNode, nodeVersion );
1943             end_change( pRight, rightVersion );
1944             m_stat.onRotateLeftOverRight();
1945
1946             assert( hRR - hRLR <= 1 && hRLR - hRR <= 1 );
1947
1948             int nodeBalance = hRLL - hL;
1949             if ( nodeBalance < -1 || nodeBalance > 1 ) {
1950                 m_stat.onRotateAfterLRRotation();
1951                 return pNode;
1952             }
1953
1954             if ( (pRLL == nullptr || hL == 0) && !pNode->is_valued(memory_model::memory_order_relaxed) ) {
1955                 m_stat.onRemoveAfterLRRotation();
1956                 return pNode;
1957             }
1958
1959             int balRL = hRight - hNode;
1960             if ( balRL < -1 || balRL > 1 ) {
1961                 m_stat.onRotateAfterLRRotation();
1962                 return pRLeft;
1963             }
1964
1965             return fix_height_locked( pParent );
1966         }
1967
1968         //@endcond
1969     };
1970 }} // namespace cds::container
1971
1972 #endif // #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H