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 <memory> // unique_ptr
   7 #include <cds/container/details/bronson_avltree_base.h>
   8 #include <cds/urcu/details/check_deadlock.h>
   9 #include <cds/details/binary_functor_wrapper.h>
  10
  11
  12 namespace cds { namespace container {
  13
  14     /// Bronson et al AVL-tree (RCU specialization for storing pointer to values)
  15     /** @ingroup cds_nonintrusive_map
  16         @ingroup cds_nonintrusive_tree
  17         @headerfile cds/container/bronson_avltree_map_rcu.h
  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         /// Returned pointer to \p mapped_type of extracted node
  72         typedef std::unique_ptr< mapped_type, disposer > unique_ptr;
  73
  74     protected:
  75         //@cond
  76         typedef typename sync_monitor::node_injection< bronson_avltree::node< key_type, mapped_type >> node_type;
  77         typedef typename node_type::version_type version_type;
  78
  79         typedef cds::details::Allocator< node_type, node_allocator_type > cxx_allocator;
  80         typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock >   check_deadlock_policy;
  81
  82         enum class find_result
  83         {
  84             not_found,
  85             found,
  86             retry
  87         };
  88
  89         enum class update_flags
  90         {
  91             allow_insert = 1,
  92             allow_update = 2,
  93             allow_remove = 4,
  94
  95             retry = 1024,
  96
  97             failed = 0,
  98             result_inserted = allow_insert,
  99             result_updated  = allow_update,
 100             result_removed  = allow_remove
 101         };
 102
 103         enum node_condition
 104         {
 105             nothing_required = -3,
 106             rebalance_required = -2,
 107             unlink_required = -1
 108         };
 109
 110         typedef typename sync_monitor::template scoped_lock<node_type> node_scoped_lock;
 111         //@endcond
 112
 113     protected:
 114         //@cond
 115         template <typename K>
 116         static node_type * alloc_node( K&& key, int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight )
 117         {
 118             return cxx_allocator().New( std::forward<K>( key ), nHeight, version, pParent, pLeft, pRight );
 119         }
 120
 121         static void free_node( node_type * pNode )
 122         {
 123             // Free node without disposer
 124             cxx_allocator().Delete( pNode );
 125         }
 126
 127         // RCU safe disposer
 128         class rcu_disposer
 129         {
 130             node_type *     m_pRetiredList; ///< head of retired list
 131
 132         public:
 133             rcu_disposer()
 134                 : m_pRetiredList( nullptr )
 135             {}
 136
 137             ~rcu_disposer()
 138             {
 139                 clean();
 140             }
 141
 142             void dispose( node_type * pNode )
 143             {
 144                 mapped_type * pVal = pNode->value( memory_model::memory_order_relaxed );
 145                 if ( pVal ) {
 146                     pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
 147                     disposer()(pVal);
 148                 }
 149
 150                 pNode->m_pNextRemoved = m_pRetiredList;
 151                 m_pRetiredList = pNode;
 152             }
 153
 154         private:
 155             struct internal_disposer
 156             {
 157                 void operator()( node_type * p ) const
 158                 {
 159                     free_node( p );
 160                 }
 161             };
 162
 163             void clean()
 164             {
 165                 assert( !gc::is_locked() );
 166
 167                 for ( node_type * p = m_pRetiredList; p; ) {
 168                     node_type * pNext = p->m_pNextRemoved;
 169                     // Value already disposed
 170                     gc::template retire_ptr<internal_disposer>( p );
 171                     p = pNext;
 172                 }
 173             }
 174         };
 175
 176         //@endcond
 177
 178     protected:
 179         //@cond
 180         typename node_type::base_class      m_Root;
 181         node_type *                         m_pRoot;
 182         item_counter                        m_ItemCounter;
 183         mutable sync_monitor                m_Monitor;
 184         mutable stat                        m_stat;
 185         //@endcond
 186
 187     public:
 188         /// Creates empty map
 189         BronsonAVLTreeMap()
 190             : m_pRoot( static_cast<node_type *>(&m_Root) )
 191         {}
 192
 193         /// Destroys the map
 194         ~BronsonAVLTreeMap()
 195         {
 196             unsafe_clear();
 197         }
 198
 199         /// Inserts new node
 200         /**
 201             The \p key_type should be constructible from a value of type \p K.
 202
 203             RCU \p synchronize() can be called. RCU should not be locked.
 204
 205             Returns \p true if inserting successful, \p false otherwise.
 206         */
 207         template <typename K>
 208         bool insert( K const& key, mapped_type * pVal )
 209         {
 210             return do_update(key, key_comparator(),
 211                 [pVal]( node_type * pNode ) -> mapped_type*
 212                 {
 213                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 214                     return pVal;
 215                 },
 216                 update_flags::allow_insert
 217             ) == update_flags::result_inserted;
 218         }
 219
 220         /// Updates the value for \p key
 221         /**
 222             The operation performs inserting or updating the value for \p key with lock-free manner.
 223             If \p bInsert is \p false, only updating of existing node is possible.
 224
 225             If \p key is not found and inserting is allowed (i.e. \p bInsert is \p true),
 226             then the new node created from \p key is inserted into the map; note that in this case the \ref key_type should be
 227             constructible from type \p K.
 228             Otherwise, the value is changed to \p pVal.
 229
 230             RCU \p synchronize() method can be called. RCU should not be locked.
 231
 232             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
 233             \p second is \p true if new node has been added or \p false if the node with \p key
 234             already is in the tree.
 235         */
 236         template <typename K, typename Func>
 237         std::pair<bool, bool> update( K const& key, mapped_type * pVal, bool bInsert = true )
 238         {
 239             int result = do_update( key, key_comparator(),
 240                 [pVal]( node_type * ) -> mapped_type*
 241                 {
 242                     return pVal;
 243                 },
 244                 update_flags::allow_update | (bInsert ? update_flags::allow_insert : 0)
 245             );
 246             return std::make_pair( result != 0, (result & update_flags::result_inserted) != 0 );
 247         }
 248
 249         /// Delete \p key from the map
 250         /**
 251             RCU \p synchronize() method can be called. RCU should not be locked.
 252
 253             Return \p true if \p key is found and deleted, \p false otherwise
 254         */
 255         template <typename K>
 256         bool erase( K const& key )
 257         {
 258             return do_update(
 259                 key,
 260                 key_comparator(),
 261                 []( mapped_type * pVal ) { disposer()(pVal); },
 262                 update_flags::allow_remove
 263             ) == update_flags::result_removed;
 264         }
 265
 266         /// Deletes the item from the map using \p pred predicate for searching
 267         /**
 268             The function is an analog of \p erase(K const&)
 269             but \p pred is used for key comparing.
 270             \p Less functor has the interface like \p std::less.
 271             \p Less must imply the same element order as the comparator used for building the map.
 272         */
 273         template <typename K, typename Less>
 274         bool erase_with( K const& key, Less pred )
 275         {
 276             CDS_UNUSED( pred );
 277             return do_update(
 278                 key,
 279                 cds::details::predicate_wrapper<key_type, Less, cds::details::trivial_accessor >(),
 280                 []( mapped_type * pVal ) { disposer()(pVal); },
 281                 update_flags::allow_remove
 282             ) == update_flags::result_removed;
 283         }
 284
 285         /// Delete \p key from the map
 286         /**
 287             The function searches an item with key \p key, calls \p f functor
 288             and deletes the item. If \p key is not found, the functor is not called.
 289
 290             The functor \p Func interface:
 291             \code
 292             struct extractor {
 293                 void operator()(mapped_type& item) { ... }
 294             };
 295             \endcode
 296
 297             RCU \p synchronize method can be called. RCU should not be locked.
 298
 299             Return \p true if key is found and deleted, \p false otherwise
 300         */
 301         template <typename K, typename Func>
 302         bool erase( K const& key, Func f )
 303         {
 304             return do_update(
 305                 key,
 306                 key_comparator(),
 307                 [&f]( mapped_type * pVal ) { f( *pVal ); disposer()(pVal); },
 308                 update_flags::allow_remove
 309             ) == update_flags::result_removed;
 310         }
 311
 312         /// Deletes the item from the map using \p pred predicate for searching
 313         /**
 314             The function is an analog of \p erase(K const&, Func)
 315             but \p pred is used for key comparing.
 316             \p Less functor has the interface like \p std::less.
 317             \p Less must imply the same element order as the comparator used for building the map.
 318         */
 319         template <typename K, typename Less, typename Func>
 320         bool erase_with( K const& key, Less pred, Func f )
 321         {
 322             CDS_UNUSED( pred );
 323             return do_update(
 324                 key,
 325                 cds::details::predicate_wrapper<key_type, Less, cds::details::trivial_accessor >(),
 326                 [&f]( mapped_type * pVal ) { f( *pVal ); disposer()(pVal); },
 327                 update_flags::allow_remove
 328             ) == update_flags::result_removed;
 329         }
 330
 331         /// Extracts an item with minimal key from the map
 332         /**
 333             Returns \p std::unique_ptr to the leftmost item.
 334             If the set is empty, returns empty \p std::unique_ptr.
 335
 336             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
 337             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 338             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 339             So, the function returns the item with minimum key at the moment of tree traversing.
 340
 341             RCU \p synchronize method can be called. RCU should NOT be locked.
 342             The function does not free the item.
 343             The deallocator will be implicitly invoked when the returned object is destroyed or when
 344             its \p reset(nullptr) member function is called.
 345         */
 346         unique_ptr extract_min()
 347         {
 348             //TODO
 349         }
 350
 351         /// Extracts an item with maximal key from the map
 352         /**
 353             Returns \p std::unique_ptr pointer to the rightmost item.
 354             If the set is empty, returns empty \p std::unique_ptr.
 355
 356             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
 357             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 358             During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
 359             So, the function returns the item with maximum key at the moment of tree traversing.
 360
 361             RCU \p synchronize method can be called. RCU should NOT be locked.
 362             The function does not free the item.
 363             The deallocator will be implicitly invoked when the returned object is destroyed or when
 364             its \p reset(nullptr) is called.
 365             @note Before reusing \p result object you should call its \p release() method.
 366         */
 367         unique_ptr extract_max()
 368         {
 369             //TODO
 370         }
 371
 372         /// Extracts an item from the map
 373         /**
 374             The function searches an item with key equal to \p key in the tree,
 375             unlinks it, and returns \p std::unique_ptr pointer to a value found.
 376             If \p key is not found the function returns an empty \p std::unique_ptr.
 377
 378             RCU \p synchronize method can be called. RCU should NOT be locked.
 379             The function does not destroy the value found.
 380             The disposer will be implicitly invoked when the returned object is destroyed or when
 381             its \p reset(nullptr) member function is called.
 382         */
 383         template <typename Q>
 384         unique_ptr extract( Q const& key )
 385         {
 386             unique_ptr pExtracted;
 387
 388             do_update(
 389                 key,
 390                 key_comparator(),
 391                 [&pExtracted]( mapped_type * pVal ) { pExtracted.reset( pVal ); },
 392                 update_flags::allow_remove
 393                 );
 394             return pExtracted;
 395         }
 396
 397         /// Extracts an item from the map using \p pred for searching
 398         /**
 399             The function is an analog of \p extract(Q const&)
 400             but \p pred is used for key compare.
 401             \p Less has the interface like \p std::less.
 402             \p pred must imply the same element order as the comparator used for building the tree.
 403         */
 404         template <typename Q, typename Less>
 405         unique_ptr extract_with( Q const& key, Less pred )
 406         {
 407             CDS_UNUSED( pred );
 408             unique_ptr pExtracted;
 409
 410             do_update(
 411                 key,
 412                 cds::details::predicate_wrapper<key_type, Less, cds::details::trivial_accessor >(),
 413                 [&pExtracted]( mapped_type * pVal ) { pExtracted.reset( pVal ); },
 414                 update_flags::allow_remove
 415                 );
 416             return pExtracted;
 417         }
 418
 419         /// Find the key \p key
 420         /**
 421             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 422             The interface of \p Func functor is:
 423             \code
 424             struct functor {
 425                 void operator()( mapped_type& item );
 426             };
 427             \endcode
 428             where \p item is the item found.
 429             The functor is called under node-level lock.
 430
 431             The function applies RCU lock internally.
 432
 433             The function returns \p true if \p key is found, \p false otherwise.
 434         */
 435         template <typename K, typename Func>
 436         bool find( K const& key, Func f )
 437         {
 438             return do_find( key, key_comparator(), [&f]( sync_monitor& monitor, node_type * pNode ) -> bool {
 439                 assert( pNode != nullptr );
 440                 node_scoped_lock l( monitor, *pNode );
 441                 mapped_type * pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
 442                 if ( pVal ) {
 443                     f( *pVal );
 444                     return true;
 445                 }
 446                 return false;
 447             });
 448         }
 449
 450         /// Finds the key \p val using \p pred predicate for searching
 451         /**
 452             The function is an analog of \p find(K const&, Func)
 453             but \p pred is used for key comparing.
 454             \p Less functor has the interface like \p std::less.
 455             \p Less must imply the same element order as the comparator used for building the map.
 456         */
 457         template <typename K, typename Less, typename Func>
 458         bool find_with( K const& key, Less pred, Func f )
 459         {
 460             CDS_UNUSED( pred );
 461             return do_find( key, opt::details::make_comparator_from_less<Less>(),
 462                 [&f]( sync_monitor& monitor, node_type * pNode ) -> bool {
 463                     assert( pNode != nullptr );
 464                     node_scoped_lock l( monitor, *pNode );
 465                     mapped_type * pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
 466                     if ( pVal ) {
 467                         f( *pVal );
 468                         return true;
 469                     }
 470                     return false;
 471                 }
 472             );
 473         }
 474
 475         /// Find the key \p key
 476         /**
 477             The function searches the item with key equal to \p key
 478             and returns \p true if it is found, and \p false otherwise.
 479
 480             The function applies RCU lock internally.
 481         */
 482         template <typename K>
 483         bool find( K const& key )
 484         {
 485             return do_find( key, key_comparator(), []( node_type * ) -> bool { return true; });
 486         }
 487
 488         /// Finds the key \p val using \p pred predicate for searching
 489         /**
 490             The function is an analog of \p find(K const&)
 491             but \p pred is used for key comparing.
 492             \p Less functor has the interface like \p std::less.
 493             \p Less must imply the same element order as the comparator used for building the map.
 494         */
 495         template <typename K, typename Less>
 496         bool find_with( K const& key, Less pred )
 497         {
 498             CDS_UNUSED( pred );
 499             return do_find( key, opt::details::make_comparator_from_less<Less>(), []( node_type * ) -> bool { return true; } );
 500         }
 501
 502         /// Clears the tree (thread safe, not atomic)
 503         /**
 504             The function unlink all items from the tree.
 505             The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
 506             this sequence
 507             \code
 508             set.clear();
 509             assert( set.empty() );
 510             \endcode
 511             the assertion could be raised.
 512
 513             For each node the \ref disposer will be called after unlinking.
 514
 515             RCU \p synchronize method can be called. RCU should not be locked.
 516         */
 517         void clear()
 518         {
 519             for ( ;; ) {
 520                 unique_ptr ep( extract_min() );
 521                 if ( !ep )
 522                     return;
 523             }
 524         }
 525
 526         /// Clears the tree (not thread safe)
 527         /**
 528             This function is not thread safe and may be called only when no other thread deals with the tree.
 529             The function is used in the tree destructor.
 530         */
 531         void unsafe_clear()
 532         {
 533             //TODO
 534         }
 535
 536         /// Checks if the map is empty
 537         bool empty() const
 538         {
 539             return m_Root.m_pRight.load( memory_model::memory_order_relaxed ) == nullptr;
 540         }
 541
 542         /// Returns item count in the map
 543         /**
 544             Only leaf nodes containing user data are counted.
 545
 546             The value returned depends on item counter type provided by \p Traits template parameter.
 547             If it is \p atomicity::empty_item_counter this function always returns 0.
 548
 549             The function is not suitable for checking the tree emptiness, use \p empty()
 550             member function for this purpose.
 551         */
 552         size_t size() const
 553         {
 554             return m_ItemCounter;
 555         }
 556
 557         /// Returns const reference to internal statistics
 558         stat const& statistics() const
 559         {
 560             return m_stat;
 561         }
 562
 563         /// Checks internal consistency (not atomic, not thread-safe)
 564         /**
 565             The debugging function to check internal consistency of the tree.
 566         */
 567         bool check_consistency() const
 568         {
 569             //TODO
 570             return true;
 571         }
 572
 573     protected:
 574         //@cond
 575         template <typename Q, typename Compare, typename Func>
 576         bool do_find( Q& key, Compare cmp, Func f ) const
 577         {
 578             find_result result;
 579             {
 580                 rcu_lock l;
 581                 result = try_find( key, cmp, f, m_pRoot, 1, 0 );
 582             }
 583             assert( result != find_result::retry );
 584             return result == find_result::found;
 585         }
 586
 587         template <typename K, typename Compare, typename Func>
 588         int do_update( K const& key, Compare cmp, Func funcUpdate, int nFlags )
 589         {
 590             check_deadlock_policy::check();
 591
 592             rcu_disposer removed_list;
 593             {
 594                 rcu_lock l;
 595                 return try_udate_root( key, cmp, nFlags, funcUpdate, removed_list );
 596             }
 597         }
 598
 599         //@endcond
 600
 601     private:
 602         //@cond
 603         template <typename Q, typename Compare, typename Func>
 604         find_result try_find( Q const& key, Compare cmp, Func f, node_type * pNode, int nDir, version_type nVersion ) const
 605         {
 606             assert( gc::is_locked() );
 607             assert( pNode );
 608
 609             while ( true ) {
 610                 node_type * pChild = pNode->child( nDir ).load( memory_model::memory_order_relaxed );
 611                 if ( !pChild ) {
 612                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
 613                         m_stat.onFindRetry();
 614                         return find_result::retry;
 615                     }
 616
 617                     m_stat.onFindFailed();
 618                     return find_result::not_found;
 619                 }
 620
 621                 int nCmp = cmp( key, pChild->m_key );
 622                 if ( nCmp == 0 ) {
 623                     if ( pChild->is_valued( memory_model::memory_order_relaxed ) ) {
 624                         // key found
 625                         node_scoped_lock l( m_Monitor, pChild );
 626                         if ( pChild->is_valued( memory_model::memory_order_relaxed )) {
 627                             if ( f( *pChild ) ) {
 628                                 m_stat.onFindSuccess();
 629                                 return find_result::found;
 630                             }
 631                         }
 632                     }
 633
 634                     m_stat.onFindFailed();
 635                     return find_result::not_found;
 636                 }
 637
 638                 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
 639                 if ( nChildVersion & node_type::shrinking ) {
 640                     m_stat.onFindWaitShrinking();
 641                     pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
 642
 643                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
 644                         m_stat.onFindRetry();
 645                         return find_result::retry;
 646                     }
 647                 }
 648                 else if ( nChildVersion != node_type::unlinked ) {
 649
 650                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
 651                         m_stat.onFindRetry();
 652                         return find_result::retry;
 653                     }
 654
 655                     find_result found = try_find( key, cmp, f, pChild, nCmp, nChildVersion );
 656                     if ( found != find_result::retry )
 657                         return found;
 658                 }
 659             }
 660         }
 661
 662         template <typename K, typename Compare, typename Func>
 663         int try_update_root( K const* key, Compare cmp, int nFlags, Func funcUpdate, rcu_disposer& disp )
 664         {
 665             assert( gc::is_locked() );
 666
 667             int result;
 668             do {
 669                 // get right child of root
 670                 node_type * pChild = m_Root.child( 1, memory_model::memory_order_acquire );
 671                 if ( pChild ) {
 672                     version_type nChildVersion = pChild->version( memory_model::memory_order_relaxed );
 673                     if ( nChildVersion & node_type::shrinking ) {
 674                         m_stat.onUpdateRootWaitShrinking();
 675                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
 676                         result = update_flags::retry;
 677                     }
 678                     else if ( pChild == m_Root.child( 1, memory_model::memory_order_acquire ) ) {
 679                         result = try_update( key, cmp, nFlags, funcUpdate, m_pRoot, pChild, nChildVersion, disp );
 680                     }
 681                 }
 682                 else {
 683                     // the tree is empty
 684                     if ( nFlags & update_flags::allow_insert ) {
 685                         // insert into tree as right child of the root
 686                         {
 687                             node_scoped_lock l( m_Monitor, *m_pRoot );
 688
 689                             node_type * pNew = alloc_node( key, 1, 0, m_pRoot, nullptr, nullptr );
 690                             mapped_type * pVal = funcUpdate( pNew );
 691                             assert( pVal != nullptr );
 692                             pNew->m_pValue.store( pVal, memory_model::memory_order_release );
 693
 694                             m_pRoot->child( pNew, 1, memory_model::memory_order_relaxed );
 695                             m_pRoot->height( 2, memory_model::memory_order_relaxed );
 696                         }
 697
 698                         ++m_ItemCounter;
 699                         m_stat.onInsertSuccess();
 700                         return update_flags::result_inserted;
 701                     }
 702
 703                     return update_flags::failed;
 704                 }
 705             } while ( result == update_flags::retry );
 706             return result;
 707         }
 708
 709         template <typename K, typename Compare, typename Func>
 710         int try_update( K const& key, Compare cmp, int nFlags, Func funcUpdate, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
 711         {
 712             assert( gc::is_locked() );
 713             assert( nVersion != node_type::unlinked );
 714
 715             int nCmp = cmp( key, pNode->m_key );
 716             if ( nCmp == 0 ) {
 717                 if ( nFlags & update_flags::allow_update ) {
 718                     return try_update_node( funcUpdate, pNode );
 719                 }
 720                 if ( nFlags & update_flags::allow_remove ) {
 721                     return try_remove_node( pParent, pNode, nVersion, funcUpdate, disp );
 722                 }
 723                 return update_flags::failed;
 724             }
 725
 726             int result;
 727             do {
 728                 node_type * pChild = pNode->child( nCmp ).load( memory_model::memory_order_relaxed );
 729                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
 730                     return update_flags::retry;
 731
 732                 if ( pChild == nullptr ) {
 733                     // insert new node
 734                     if ( nFlags & update_flags::allow_insert )
 735                         result = try_insert_node( key, funcUpdate, pNode, nCmp, nVersion, disp );
 736                     else
 737                         result = update_flags::failed;
 738                 }
 739                 else {
 740                     // update child
 741                     result = update_flags::retry;
 742                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
 743                     if ( nChildVersion & node_type::shrinking ) {
 744                         m_stat.onUpdateWaitShrinking();
 745                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
 746                         // retry
 747                     }
 748                     else if ( pChild == pNode->child( nCmp ).load( memory_model::memory_order_relaxed ) ) {
 749                         // this second read is important, because it is protected by nChildVersion
 750
 751                         // validate the read that our caller took to get to node
 752                         if ( pNode->version( memory_model::memory_order_relaxed ) != nVersion ) {
 753                             m_stat.onUpdateRetry();
 754                             return update_flags::retry;
 755                         }
 756
 757                         // At this point we know that the traversal our parent took to get to node is still valid.
 758                         // The recursive implementation will validate the traversal from node to
 759                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
 760                         // This means that we are no longer vulnerable to node shrinks, and we don't need
 761                         // to validate node version any more.
 762                         result = try_update( key, cmp, nFlags, funcUpdate, pNode, pChild, nChildVersion, disp );
 763                     }
 764                 }
 765             } while ( result == update_flags::retry );
 766             return result;
 767         }
 768
 769         template <typename K, typename Func>
 770         int try_insert_node( K const& key, Func funcUpdate, node_type * pNode, int nDir, version_type nVersion, rcu_disposer& disp )
 771         {
 772             node_type * pNew;
 773
 774             auto fnCreateNode = [&funcUpdate]( node_type * pNew ) {
 775                 mapped_type * pVal = funcUpdate( pNew );
 776                 assert( pVal != nullptr );
 777                 pNew->m_pValue.store( pVal, memory_model::memory_order_relaxed );
 778             };
 779
 780             if ( c_bRelaxedInsert ) {
 781                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
 782                      || pNode->child( nDir ).load( memory_model::memory_order_relaxed ) != nullptr )
 783                 {
 784                     m_stat.onInsertRetry();
 785                     return update_flags::retry;
 786                 }
 787
 788                 fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
 789             }
 790
 791             node_type * pDamaged;
 792             {
 793                 assert( pNode != nullptr );
 794                 node_scoped_lock l( m_Monitor, *pNode );
 795
 796                 if ( pNode->version( memory_model::memory_order_relaxed ) != nVersion
 797                      || pNode->child( nDir ).load( memory_model::memory_order_relaxed ) != nullptr )
 798                 {
 799                     if ( c_RelaxedInsert ) {
 800                         free_node( pNew );
 801                         m_stat.onRelaxedInsertFailed();
 802                     }
 803
 804                     m_stat.onInsertRetry();
 805                     return update_flags::retry;
 806                 }
 807
 808                 if ( !c_bRelaxedInsert )
 809                     fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
 810
 811                 pNode->child( pNew, nDir, memory_model::memory_order_relaxed );
 812                 pDamaged = fix_height_locked( pNode );
 813             }
 814             m_stat.onInsertSuccess();
 815
 816             fix_height_and_rebalance( pDamaged, disp );
 817
 818             return update_flags::result_inserted;
 819         }
 820
 821         template <typename Func>
 822         int try_update_node( Func funcUpdate, node_type * pNode )
 823         {
 824             mapped_type * pOld;
 825             {
 826                 assert( pNode != nullptr );
 827                 node_scoped_lock l( m_Monitor, *pNode );
 828
 829                 if ( pNode->is_unlinked( memory_model::memory_order_relaxed )) {
 830                     m_stat.onUpdateUnlinked();
 831                     return update_flags::retry;
 832                 }
 833
 834                 pOld = pNode->value( memory_model::memory_order_relaxed );
 835                 mapped_type * pVal = funcUpdate( *pNode );
 836                 assert( pVal != nullptr );
 837                 pNode->m_pValue.store( pVal, memory_model::memory_order_relaxed );
 838             }
 839
 840             if ( pOld ) {
 841                 disposer()(pOld);
 842                 m_stat.onDisposeValue();
 843             }
 844
 845             m_stat.onUpdateSuccess();
 846             return update_flags::result_updated;
 847         }
 848
 849         template <typename Func>
 850         int try_remove_node( node_type * pParent, node_type * pNode, version_type nVersion, Func func, rcu_disposer& disp )
 851         {
 852             assert( pParent != nullptr );
 853             assert( pNode != nullptr );
 854
 855             if ( !pNode->is_valued( atomics::memory_order_relaxed ) )
 856                 return update_flags::failed;
 857
 858             if ( pNode->child( -1, atomics::memory_order_relaxed ) == nullptr
 859               || pNode->child( 1, atomics::memory_order_relaxed ) == nullptr )
 860             {
 861                 node_type * pDamaged;
 862                 mapped_type * pOld;
 863                 {
 864                     node_scoped_lock lp( m_Monitor, *pParent );
 865                     if ( pParent->is_unlinked( atomics::memory_order_relaxed ) || pNode->m_pParent.load( atomics::memory_order_relaxed ) != pParent )
 866                         return update_flags::retry;
 867
 868                     {
 869                         node_scoped_lock ln( m_Monitor, *pNode );
 870                         pOld = pNode->value( atomics::memory_order_relaxed );
 871                         if ( pNode->version( atomics::memory_order_relaxed ) == nVersion
 872                           && pOld
 873                           && try_unlink_locked( pParent, pNode, disp ) )
 874                         {
 875                             pNode->m_pValue.store( nullptr, atomics::memory_order_relaxed );
 876                         }
 877                         else
 878                             return update_flags::retry;
 879                     }
 880                     pDamaged = fix_height_locked( pParent );
 881                 }
 882
 883                 func( pOld );   // calls pOld disposer inside
 884                 m_stat.onDisposeValue();
 885
 886                 fix_height_and_rebalance( pDamaged, disp );
 887                 return upfate_flags::result_removed;
 888             }
 889             else {
 890                 int result = update_flags::retry;
 891                 {
 892                     node_scoped_lock ln( m_Monitor, *pNode );
 893                     mapped_type * pOld = pNode->value( atomics::memory_order_relaxed );
 894                     if ( pNode->version( atomics::memory_order_relaxed ) == nVersion && pOld ) {
 895                         pNode->m_pValue.store( nullptr, atomics::memory_order_relaxed );
 896                         result = upfate_flags::result_removed;
 897                     }
 898                 }
 899
 900                 if ( result == upfate_flags::result_removed ) {
 901                     func( *pOld );  // calls pOld disposer inside
 902                     m_stat.onDisposeValue();
 903                 }
 904
 905                 return result;
 906             }
 907         }
 908
 909         bool try_unlink_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp )
 910         {
 911             // pParent and pNode must be locked
 912             assert( !pParent->is_unlinked(memory_model::memory_order_relaxed) );
 913
 914             node_type * pParentLeft = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
 915             node_type * pParentRight = pParent->m_pRight.load( memory_model::memory_order_relaxed );
 916             if ( pNode != pParentLeft && pNode != pParentRight ) {
 917                 // node is no longer a child of parent
 918                 return false;
 919             }
 920
 921             assert( !pNode->is_unlinked());
 922             assert( pParent == pNode->m_pParent.load(memory_model::memory_order_relaxed));
 923
 924             node_type * pLeft = pNode->m_pLeft.load( memory_model::memory_order_relaxed );
 925             node_type * pRight = pNode->m_pRight.load( memory_model::memory_order_relaxed );
 926             if ( pLeft != nullptr && pRight != nullptr ) {
 927                 // splicing is no longer possible
 928                 return false;
 929             }
 930             node_type * pSplice = pLeft ? pLeft : pRight;
 931
 932             if ( pParentLeft == pNode )
 933                 pParent->m_pLeft.store( pSplice, memory_model::memory_order_relaxed );
 934             else
 935                 pParent->m_pRight.store( pSplice, memory_model::memory_order_relaxed );
 936
 937             if ( pSplice )
 938                 pSplice->pParent.store( pParent, memory_model::memory_order_release );
 939
 940             // Mark the node as unlinked
 941             pNode->version( node_type::unlinked, memory_model::memory_order_release );
 942             disp.dispose( pNode );
 943
 944             return true;
 945         }
 946
 947         //@endcond
 948
 949     private: // rotations
 950         //@cond
 951         int estimate_node_condition( node_type * pNode )
 952         {
 953             node_type * pLeft = pNode->m_pLeft.load( memory_model::memory_order_relaxed );
 954             node_type * pRight = pNode->m_pRight.load( memory_model::memory_order_relaxed );
 955
 956             if ( (pLeft == nullptr || pRight == nullptr) && pNode->value( memory_model::memory_order_relaxed ) == nullptr )
 957                 return unlink_required;
 958
 959             int h = pNode->height( memory_model::memory_order_relaxed );
 960             int hL = pLeft ? pLeft->height( memory_model::memory_order_relaxed ) : 0;
 961             int hR = pRight ? pRight->height( memory_model::memory_order_relaxed ) : 0;
 962
 963             int hNew = 1 + std::max( hL, hR );
 964             int nBalance = hL - hR;
 965
 966             if ( nBalance < -1 || nBalance > 1 )
 967                 return rebalance_required;
 968
 969             return h != hNew ? hNew : nothing_required;
 970         }
 971
 972         node_type * fix_height( node_type * pNode )
 973         {
 974             assert( pNode != nullptr );
 975             node_scoped_lock l( m_Monitor, *pNode );
 976             return fix_height_locked( pNode );
 977         }
 978
 979         node_type * fix_height_locked( node_type * pNode )
 980         {
 981             // pNode must be locked!!!
 982             int h = estimate_node_condition( pNode );
 983             switch ( h ) {
 984                 case rebalance_required:
 985                 case unlink_required:
 986                     return pNode;
 987                 case nothing_required:
 988                     return nullptr;
 989                 default:
 990                     pNode->height( h, memory_model::memory_order_relaxed );
 991                     return pNode->m_pParent.load( memory_model::memory_order_relaxed );
 992             }
 993         }
 994
 995         void fix_height_and_rebalance( node_type * pNode, rcu_disposer& disp )
 996         {
 997             while ( pNode && pNode->m_pParent.load( memory_model::memory_order_relaxed ) ) {
 998                 int nCond = estimate_node_condition( pNode );
 999                 if ( nCond == nothing_required || pNode->is_unlinked( memory_model::memory_order_relaxed ) )
1000                     return;
1001
1002                 if ( nCond != unlink_required && nCond != rebalance_required )
1003                     pNode = fix_height( pNode );
1004                 else {
1005                     node_type * pParent = pNode->m_pParent.load( memory_model::memry_order_relaxed );
1006                     assert( pParent != nullptr );
1007                     {
1008                         node_scoped_lock lp( m_Monitor, *pParent );
1009                         if ( !pParent->is_unlinked( memory_model::memory_order_relaxed )
1010                              && pNode->m_pParent.load( memory_model::memory_order_relaxed ) == pParent )
1011                         {
1012                             node_scoped_lock ln( m_Monitor, *pNode );
1013                             pNode = rebalance_locked( pParent, pNode, disp );
1014                         }
1015                     }
1016                 }
1017             }
1018         }
1019
1020         node_type * rebalance_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp )
1021         {
1022             // pParent and pNode should be locked.
1023             // Returns a damaged node, or nullptr if no more rebalancing is necessary
1024             assert( pNode->m_pParent.load( memory_model::memry_order_relaxed ) == pNode );
1025             assert( m_pParent->m_pLeft.load( memory_model::memory_order_relaxed ) == pNode
1026                  || m_pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1027
1028             node_type * pLeft = pNode->m_pLeft.load( memory_model::memory_order_relaxed );
1029             node_type * pRight = pNode->m_pRight.load( memory_model::memory_order_relaxed );
1030
1031             if ( (pLeft == nullptr || pRight == nullptr) && pNode->value( memory_model::memory_order_relaxed ) == nullptr ) {
1032                 if ( try_unlink_locked( pParent, pNode, disp ))
1033                     return fix_height_locked( pParent );
1034                 else {
1035                     // retry needed for pNode
1036                     return pNode;
1037                 }
1038             }
1039
1040             int h = pNode->height( memory_model::memory_order_relaxed );
1041             int hL = pLeft ? pLeft->height( memory_model::memory_order_relaxed ) : 0;
1042             int hR = pRight ? pRight->height( memory_model::memory_order_relaxed ) : 0;
1043             int hNew = 1 + std::max( hL, hR );
1044             int balance = hL - hR;
1045
1046             if ( balance > 1 )
1047                 return rebalance_to_right_locked( pParent, pNode, pLeft, hR );
1048             else if ( balance < -1 )
1049                 return rebalance_to_left_locked( pParent, pNode, pRight, hL );
1050             else if ( hNew != h ) {
1051                 pNode->height( hNew, memory_model::memory_order_relaxed );
1052
1053                 // pParent is already locked
1054                 return fix_height_locked( pParent );
1055             }
1056             else
1057                 return nullptr;
1058         }
1059
1060         node_type * rebalance_to_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR )
1061         {
1062             assert( pNode->m_pParent.load( memory_model::memry_order_relaxed ) == pNode );
1063             assert( m_pParent->m_pLeft.load( memory_model::memory_order_relaxed ) == pNode
1064                  || m_pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1065
1066             // pParent and pNode is locked yet
1067             // pNode->pLeft is too large, we will rotate-right.
1068             // If pLeft->pRight is taller than pLeft->pLeft, then we will first rotate-left pLeft.
1069
1070             {
1071                 assert( pLeft != nullptr );
1072                 node_scoped_lock l( m_Monitor, *pLeft );
1073                 if ( pNode->m_pLeft.load( memory_model::memory_order_relaxed ) != pLeft )
1074                     return pNode; // retry for pNode
1075
1076                 int hL = pLeft->height( memory_model::memory_order_relaxed );
1077                 if ( hL - hR <= 1 )
1078                     return pNode; // retry
1079
1080                 node_type * pLRight = pLeft->m_pRight.load( memory_model::memory_order_relaxed );
1081                 int hLR = pLRight ? pLRight->height( memory_model::memory_order_relaxed ) : 0;
1082                 node_type * pLLeft = pLeft->m_pLeft.load( memory_model::memory_order_relaxed );
1083                 int hLL = pLLeft ? pLLeft->height( memory_model::memory_order_relaxed ) : 0;
1084
1085                 if ( hLL > hLR ) {
1086                     // rotate right
1087                     return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
1088                 }
1089                 else {
1090                     assert( pLRight != nullptr );
1091                     {
1092                         node_scoped_lock lr( m_Monitor, *pLRight );
1093                         if ( pLeft->m_pRight.load( memory_model::memory_order_relaxed ) != pLRight )
1094                             return pNode; // retry
1095
1096                         hLR = pLRight->height( memory_model::memory_order_relaxed );
1097                         if ( hLL > hLR )
1098                             return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
1099
1100                         node_type * pLRLeft = pLRight->m_pLeft.load( memory_model::memory_order_relaxed );
1101                         int hLRL = pLRLeft ? pLRLeft->height( memory_model::memory_order_relaxed  ) : 0;
1102                         int balance = hLL - hLRL;
1103                         if ( balance >= -1 && balance <= 1 && !((hLL == 0 || hLRL == 0) && pLeft->value(memory_model::memory_order_relaxed) == nullptr) ) {
1104                             // nParent.child.left won't be damaged after a double rotation
1105                             return rotate_right_over_left_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLRL );
1106                         }
1107                     }
1108
1109                     // focus on pLeft, if necessary pNode will be balanced later
1110                     return rebalance_to_left_locked( pNode, pLeft, pLRight, hLL );
1111                 }
1112             }
1113         }
1114
1115         node_type * rebalance_to_left_locked( node_type * pParent, node_type * pNode, node_type * pRight, int hL )
1116         {
1117             assert( pNode->m_pParent.load( memory_model::memry_order_relaxed ) == pNode );
1118             assert( m_pParent->m_pLeft.load( memory_model::memory_order_relaxed ) == pNode
1119                     || m_pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1120
1121             // pParent and pNode is locked yet
1122             {
1123                 assert( pRight != nullptr );
1124                 node_scoped_lock l( m_Monitor, *pRight );
1125                 if ( pNode->m_pRight.load( memory_model::memory_order_relaxed ) != pRight )
1126                     return pNode; // retry for pNode
1127
1128                 int hR = pRight->height( memory_model::memory_order_relaxed );
1129                 if ( hL - hR >= -1 )
1130                     return pNode; // retry
1131
1132                 node_type * pRLeft = pRight->m_pLeft.load( memory_model::memory_order_relaxed );
1133                 int hRL = pRLeft > pRLeft->height( memory_model::memory_order_relaxed ) : 0;
1134                 node_type * pRRight = pRight->m_pRight.load( memory_model::memory_order_relaxed );
1135                 int hRR = pRRight ? pRRight->height( memory_model::memory_order_relaxed ) : 0;
1136                 if ( hRR > hRL )
1137                     return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
1138
1139                 {
1140                     assert( pRLeft != nullptr );
1141                     node_scoped_lock lrl( m_Monitor, *pRLeft );
1142                     if ( pRight->m_pLeft.load( memory_model::memory_order_relaxed ) != pRLeft )
1143                         return pNode; // retry
1144
1145                     hRL = pRLeft->height( memory_model::memory_order_relaxed );
1146                     if ( hRR >= hRL )
1147                         return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
1148
1149                     node_type * pRLRight = pRLeft->m_pRight.load( memory_model::memory_order_relaxed );
1150                     int hRLR = pRLRight ? pRLRight->height( memory_model::memory_order_relaxed ) : 0;
1151                     int balance = hRR - hRLR;
1152                     if ( b >= -1 && b <= 1 && !((hRR == 0 || hRLR == 0) && pRight->value( memory_odel::memory_order_relaxed ) == nullptr)
1153                          return rotate_left_over_right_locked( pParent, pNode, hL, pRight, pRLeft, hRR, hRLR );
1154                 }
1155                 return rebalance_to_right_locked( pNode, pRight, pRLeft, hRR );
1156             }
1157         }
1158
1159         static void begin_change( node_type * pNode, version_type version )
1160         {
1161             pNode->version( version | node_type::shrinking, memory_model::memory_order_release );
1162         }
1163         static void end_change( node_type * pNode, version_type version )
1164         {
1165             // Clear shrinking and unlinked flags and increment version
1166             pNode->version( (version | node_type::version_flags) + 1, memory_model::memory_order_release );
1167         }
1168
1169         node_type * rotate_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR, int hLL, node_type * pLRight, int hLR )
1170         {
1171             version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
1172             node_type * pParentLeft = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1173
1174             begin_change( pNode, nodeVersion );
1175
1176             pNode->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
1177             if ( pLRight != nullptr )
1178                 pLRight->m_pParent.store( pNode, memory_model::memory_order_relaxed  );
1179
1180             pLeft->m_pRight.store( pNode, memory_model::memory_order_relaxed );
1181             pNode->m_pParent.store( pLeft, memory_model::memory_order_relaxed );
1182
1183             if ( pParentLeft == pNode )
1184                 pParent->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
1185             else {
1186                 assert( pParent->m_pRight.load( memory_odel::memory_order_relaxed ) == pNode );
1187                 pParent->m_pRight.store( pLeft, memory_mdel::memory_order_relaxed );
1188             }
1189             pLeft->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1190
1191             // fix up heights links
1192             int hNode = 1 + std::max( hLR, hR );
1193             pNode->height( hNode, memory_model::memory_order_relaxed );
1194             pLeft->height( 1 + std::max( hLL, hNode ), memory_model::memory_order_relaxed );
1195
1196             end_change( pNode, nodeVersion );
1197
1198             // We have damaged pParent, pNode (now parent.child.right), and pLeft (now
1199             // parent.child).  pNode is the deepest.  Perform as many fixes as we can
1200             // with the locks we've got.
1201
1202             // We've already fixed the height for pNode, but it might still be outside
1203             // our allowable balance range.  In that case a simple fix_height_locked()
1204             // won't help.
1205             int nodeBalance = hLR - hR;
1206             if ( nodeBalance < -1 || nodeBalance > 1 ) {
1207                 // we need another rotation at pNode
1208                 return pNode;
1209             }
1210
1211             // we've fixed balance and height damage for pNode, now handle
1212             // extra-routing node damage
1213             if ( (pLRight == nullptr || hR == 0) && pNode->value(memory_model::memory_order_relaxed) == nullptr ) {
1214                 // we need to remove pNode and then repair
1215                 return pNode;
1216             }
1217
1218             // we've already fixed the height at pLeft, do we need a rotation here?
1219             int leftBalance = hLL - hNode;
1220             if ( leftBalance < -1 || leftBalance > 1 )
1221                 return pLeft;
1222
1223             // pLeft might also have routing node damage (if pLeft.left was null)
1224             if ( hLL == 0 && pLeft->value( memory_model::memory_order_relaxed ) == nullptr )
1225                 return pLeft;
1226
1227             // try to fix the parent height while we've still got the lock
1228             return fix_height_locked( pParent );
1229         }
1230
1231         node_type * rotate_left_locked( node_type * pParent, node_type * pNode, int hL, node_type * pRight, node_type * pRLeft, int hRL, int hRR )
1232         {
1233             version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
1234             node_type * pParentLeft = pParent->m_pLeft.load( memory_odel::memory_order_relaxed );
1235
1236             begin_change( pNode, nodeVersion );
1237
1238             // fix up pNode links, careful to be compatible with concurrent traversal for all but pNode
1239             pNode->m_pRight.store( pRLeft, memory_nodel::memory_order_relaxed );
1240             if ( pRLeft != nullptr )
1241                 pRLeft->m_pParent.store( pNode, memory_model::memory_order_relaxed );
1242
1243             pRight->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
1244             pNode->m_pParent.store( pRight, memory_model::memory_order_relaxed );
1245
1246             if ( pParentLeft == pNode )
1247                 pParent->m_pLeft.store( pRight, memory_model::memory_order_relaxed );
1248             else {
1249                 assert( pParent->m_pRight.load( memory_odel::memory_order_relaxed ) == pNode );
1250                 pParent->m_pRight.store( pRight, memory_model::memory_model_relaxed );
1251             }
1252             pRight->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1253
1254             // fix up heights
1255             int hNode = 1 + std::max( hL, hRL );
1256             pNode->height( hNode, memory_model::memory_order_relaxed );
1257             pRight->height( 1 + std::max( hNode, hRR ), memory_model::memory_order_relaxed );
1258
1259             end_change( pNode, nodeVersion );
1260
1261             int nodeBalance = hRL - hL;
1262             if ( nodeBalance < -1 || nodeBalance > 1 )
1263                 return pNode;
1264
1265             if ( (pRLeft == nullptr || hL == 0) && pNode->value( memory_model::memory_order_relaxed ) == nullptr )
1266                 return pNode;
1267
1268             int rightBalance = hRR - hNode;
1269             if ( rightBalance < -1 || rightBalance > 1 )
1270                 return pRight;
1271
1272             if ( hRR == 0 && pRight->value( memory_model::memory_order_relaxed ) == nullptr )
1273                 return pRight;
1274
1275             return fix_height_locked( pParent );
1276         }
1277
1278         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 )
1279         {
1280             typename node_type::value_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
1281             typename node_type::value_type leftVersion = pLeft->version( memory_model::memory_order_relaxed );
1282
1283             node_type * pPL = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1284             node_type * pLRL = pLRight->m_pLeft.load( memory_model::memory_order_relaxed );
1285             node_type * pLRR = pLRight->m_pRight.load( memory_model::memory_order_relaxed );
1286             int hLRR = pLRR ? pLRR->hight( memory_model::memory_order_relaxed ) : 0;
1287
1288             begin_change( pNode, nodeVersion );
1289             begin_change( pLeft, leftVersion );
1290
1291             // fix up pNode links, careful about the order!
1292             pNode->m_pLeft.store( pLRR, memory_model::memory_order_relaxed );
1293             if ( pLRR != nullptr )
1294                 pLRR->m_pParent.store( pNode, memory_model::memory_order_relaxed );
1295
1296             pLeft->m_pRight.store( pLRL, memory_model::memory_order_relaxed );
1297             if ( pLRL != nullptr )
1298                 pLRL->m_pParent.store( pLeft, memory_model::memory_order_relaxed );
1299
1300             pLRight->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
1301             pLeft->m_pParent.store( pLRight, memory_model::memory_order_relaxed );
1302             pLRight->m_pRight.store( pNode, memory_model::memory_order_relaxed );
1303             pNode->m_pParent.store( pLRight, memory_model::memory_order_relaxed );
1304
1305             if ( pPL == pNode )
1306                 pParent->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
1307             else {
1308                 assert( Parent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1309                 pParent->m_pRight.store( pLRight, memory_model::memory_order_relaxed );
1310             }
1311             pLRight->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1312
1313             // fix up heights
1314             int hNode = 1 + std::max( hLRR, hR );
1315             pNode->height( hNode, memory_model::memory_order_relaxed );
1316             int hLeft = 1 + std::max( hLL, hLRL );
1317             pLeft->height( hLeft, memory_model::memory_order_relaxed );
1318             pLRight->height( 1 + std::max( hLeft, hNode ), memory_model::memory_order_relaxed );
1319
1320             end_change( pNode, nodeVersion );
1321             end_change( pLeft, leftVersion );
1322
1323             // caller should have performed only a single rotation if pLeft was going
1324             // to end up damaged
1325             assert( hLL - hLRL <= 1 && hLRL - hLL <= 1 );
1326             assert( !((hLL == 0 || pLRL == nullptr) && pLeft->value( memory_model::memory_order_relaxed ) == nullptr ));
1327
1328             // We have damaged pParent, pLR (now parent.child), and pNode (now
1329             // parent.child.right).  pNode is the deepest.  Perform as many fixes as we
1330             // can with the locks we've got.
1331
1332             // We've already fixed the height for pNode, but it might still be outside
1333             // our allowable balance range.  In that case a simple fix_height_locked()
1334             // won't help.
1335             int nodeBalance = hLRR - hR;
1336             if ( nodeBalance < -1 || nodeBalance > 1 ) {
1337                 // we need another rotation at pNode
1338                 return pNode;
1339             }
1340
1341             // pNode might also be damaged by being an unnecessary routing node
1342             if ( (pLRR == nullptr || hR == 0) && pNode->value( memory_model::memory_order_relaxed ) == nullptr ) {
1343                 // repair involves splicing out pNode and maybe more rotations
1344                 return pNode;
1345             }
1346
1347             // we've already fixed the height at pLRight, do we need a rotation here?
1348             final int balanceLR = hLeft - hNode;
1349             if ( balanceLR < -1 || balanceLR > 1 )
1350                 return pLR;
1351
1352             // try to fix the parent height while we've still got the lock
1353             return fix_height_locked( pParent );
1354         }
1355
1356         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 )
1357         {
1358             version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
1359             version_type rightVersion = pRight->version( memory_model::memory_order_relaxed );
1360
1361             node_type * pPL = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1362             node_type * pRLL = pRLeft->m_pLeft.load( memory_model::memory_order_relaxed );
1363             node_type * pRLR = pRLeft->m_pRight.load( memory_model::memory_order_relaxed );
1364             int hRLL = pRLL ? pRLL->height( memory_model::memory_order_relaxed ) : 0;
1365
1366             begin_change( pNode, nodeVersion );
1367             begin_change( pRight, ghtVersion );
1368
1369             // fix up pNode links, careful about the order!
1370             pNode->m_pRight.store( pRLL, memory_model::memory_order_relaxed );
1371             if ( pRLL != nullptr )
1372                 pRLL->m_pParent.store( pNode, memory_model::memory_order_relaxed );
1373
1374             pRight->m_pLeft.store( pRLR, memory_model::memory_order_relaxed );
1375             if ( pRLR != nullptr )
1376                 pRLR->m_pParent.store( pRight, memory_model::memory_order_relaxed );
1377
1378             pRLeft->m_pRight.store( pRight, memory_model::memory_order_relaxed );
1379             pRight->m_pParent.store( pRLeft, memory_model::memory_order_relaxed );
1380             pRLeft->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
1381             pNode->m_pParent.store( pRLeft, memory_model::memory_order_relaxed );
1382
1383             if ( pPL == pNode )
1384                 pParent->m_pLeft.store( pRLeft, memory_model::memory_order_relaxed );
1385             else {
1386                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1387                 pParent->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
1388             }
1389             pRLeft->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1390
1391             // fix up heights
1392             int hNode = 1 + std::max( hL, hRLL );
1393             pNode->height( hNode, memory_model::memory_order_relaxed );
1394             int hRight = 1 + std::max( hRLR, hRR );
1395             pRight->height( hRight, memory_model::memory_order_relaxed );
1396             pRLeft->height( 1 + std::max( hNode, hRight ), memory_model::memory_order_relaxed );
1397
1398             end_change( pNode, nodeVersion );
1399             end_change( pRight, rightVersion );
1400
1401             assert( hRR - hRLR <= 1 && hRLR - hRR <= 1 );
1402
1403             int nodeBalance = hRLL - hL;
1404             if ( nodeBalance < -1 || nodeBalance > 1 )
1405                 return pNode;
1406             if ( (pRLL == nullptr || hL == 0) && pNode->value( memory_model::memory_order_relaxed ) == nullptr )
1407                 return pNode;
1408
1409             int balRL = hRight - hNode;
1410             if ( balRL < -1 || balRL > 1 )
1411                 return pRLeft;
1412
1413             return fix_height_locked( pParent );
1414         }
1415
1416         //@endcond
1417     };
1418 }} // namespace cds::container
1419
1420 #endif // #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H