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