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