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 bool const c_bRelaxedInsert = traits::relaxed_insert;
  70
  71         /// Pointer to removed value object
  72         typedef std::unique_ptr< mapped_type, disposer > exempt_ptr;
  73
  74     protected:
  75         //@cond
  76         typedef typename sync_monitor::template 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 \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the leftmost item.
 334             If the set is empty, returns empty \p exempt_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 release() member function is called.
 345         */
 346         exempt_ptr extract_min()
 347         {
 348             //TODO
 349         }
 350
 351         /// Extracts an item with maximal key from the map
 352         /**
 353             Returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the rightmost item.
 354             If the set is empty, returns empty \p exempt_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 release() is called.
 365             @note Before reusing \p result object you should call its \p release() method.
 366         */
 367         exempt_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 exempt_ptr pointer to a value found.
 376             If \p key is not found the function returns an empty \p exempt_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         exempt_ptr extract( Q const& key )
 385         {
 386             exempt_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         exempt_ptr extract_with( Q const& key, Less pred )
 406         {
 407             CDS_UNUSED( pred );
 408             exempt_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         /// Finds \p key and return the item found
 503         /**
 504             The function searches the item with key equal to \p key and returns the pointer to item found.
 505             If \p key is not found it returns \p nullptr.
 506
 507             RCU should be locked before call the function.
 508             Returned pointer is valid while RCU is locked.
 509         */
 510         template <typename Q>
 511         mapped_type * get( Q const& key ) const
 512         {
 513             //TODO
 514         }
 515
 516         /// Finds \p key with \p pred predicate and return the item found
 517         /**
 518             The function is an analog of \p get(Q const&)
 519             but \p pred is used for comparing the keys.
 520
 521             \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type
 522             and \p Q in any order.
 523             \p pred must imply the same element order as the comparator used for building the map.
 524         */
 525         template <typename Q, typename Less>
 526         mapped_type * get_with( Q const& key, Less pred ) const
 527         {
 528             CDS_UNUSED( pred );
 529             //TODO
 530         }
 531
 532         /// Clears the tree (thread safe, not atomic)
 533         /**
 534             The function unlink all items from the tree.
 535             The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
 536             this sequence
 537             \code
 538             set.clear();
 539             assert( set.empty() );
 540             \endcode
 541             the assertion could be raised.
 542
 543             For each node the \ref disposer will be called after unlinking.
 544
 545             RCU \p synchronize method can be called. RCU should not be locked.
 546         */
 547         void clear()
 548         {
 549             for ( exempt_ptr ep = extract_min(); !ep.empty(); ep = extract_min() )
 550                 ep.release();
 551         }
 552
 553         /// Clears the tree (not thread safe)
 554         /**
 555             This function is not thread safe and may be called only when no other thread deals with the tree.
 556             The function is used in the tree destructor.
 557         */
 558         void unsafe_clear()
 559         {
 560             //TODO
 561         }
 562
 563         /// Checks if the map is empty
 564         bool empty() const
 565         {
 566             return m_Root.m_pRight.load( memory_model::memory_order_relaxed ) == nullptr;
 567         }
 568
 569         /// Returns item count in the map
 570         /**
 571             Only leaf nodes containing user data are counted.
 572
 573             The value returned depends on item counter type provided by \p Traits template parameter.
 574             If it is \p atomicity::empty_item_counter this function always returns 0.
 575
 576             The function is not suitable for checking the tree emptiness, use \p empty()
 577             member function for this purpose.
 578         */
 579         size_t size() const
 580         {
 581             return m_ItemCounter;
 582         }
 583
 584         /// Returns const reference to internal statistics
 585         stat const& statistics() const
 586         {
 587             return m_stat;
 588         }
 589
 590         /// Checks internal consistency (not atomic, not thread-safe)
 591         /**
 592             The debugging function to check internal consistency of the tree.
 593         */
 594         bool check_consistency() const
 595         {
 596             //TODO
 597         }
 598
 599     protected:
 600         //@cond
 601         template <typename Q, typename Compare, typename Func>
 602         bool do_find( Q& key, Compare cmp, Func f ) const
 603         {
 604             find_result result;
 605             {
 606                 rcu_lock l;
 607                 result = try_find( key, cmp, f, m_pRoot, 1, 0 );
 608             }
 609             assert( result != find_result::retry );
 610             return result == find_result::found;
 611         }
 612
 613         template <typename K, typename Compare, typename Func>
 614         int do_update( K const& key, Compare cmp, Func funcUpdate, int nFlags )
 615         {
 616             check_deadlock_policy::check();
 617
 618             rcu_disposer removed_list;
 619             {
 620                 rcu_lock l;
 621                 return try_udate_root( key, cmp, nFlags, funcUpdate, removed_list );
 622             }
 623         }
 624
 625         //@endcond
 626
 627     private:
 628         //@cond
 629         template <typename Q, typename Compare, typename Func>
 630         find_result try_find( Q const& key, Compare cmp, Func f, node_type * pNode, int nDir, version_type nVersion ) const
 631         {
 632             assert( gc::is_locked() );
 633             assert( pNode );
 634
 635             while ( true ) {
 636                 node_type * pChild = pNode->child( nDir ).load( memory_model::memory_order_relaxed );
 637                 if ( !pChild ) {
 638                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
 639                         m_stat.onFindRetry();
 640                         return find_result::retry;
 641                     }
 642
 643                     m_stat.onFindFailed();
 644                     return find_result::not_found;
 645                 }
 646
 647                 int nCmp = cmp( key, pChild->m_key );
 648                 if ( nCmp == 0 ) {
 649                     if ( pChild->is_valued( memory_model::memory_order_relaxed ) ) {
 650                         // key found
 651                         node_scoped_lock l( m_Monitor, pChild );
 652                         if ( pChild->is_valued( memory_model::memory_order_relaxed )) {
 653                             if ( f( *pChild ) ) {
 654                                 m_stat.onFindSuccess();
 655                                 return find_result::found;
 656                             }
 657                         }
 658                     }
 659
 660                     m_stat.onFindFailed();
 661                     return find_result::not_found;
 662                 }
 663
 664                 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
 665                 if ( nChildVersion & node_type::shrinking ) {
 666                     m_stat.onFindWaitShrinking();
 667                     pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
 668
 669                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
 670                         m_stat.onFindRetry();
 671                         return find_result::retry;
 672                     }
 673                 }
 674                 else if ( nChildVersion != node_type::unlinked ) {
 675
 676                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
 677                         m_stat.onFindRetry();
 678                         return find_result::retry;
 679                     }
 680
 681                     find_result found = try_find( key, cmp, f, pChild, nCmp, nChildVersion );
 682                     if ( found != find_result::retry )
 683                         return found;
 684                 }
 685             }
 686         }
 687
 688         template <typename K, typename Compare, typename Func>
 689         int try_update_root( K const* key, Compare cmp, int nFlags, Func funcUpdate, rcu_disposer& disp )
 690         {
 691             assert( gc::is_locked() );
 692
 693             int result;
 694             do {
 695                 // get right child of root
 696                 node_type * pChild = m_Root.child( 1, memory_model::memory_order_acquire );
 697                 if ( pChild ) {
 698                     version_type nChildVersion = pChild->version( memory_model::memory_order_relaxed );
 699                     if ( nChildVersion & node_type::shrinking ) {
 700                         m_stat.onUpdateRootWaitShrinking();
 701                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
 702                         result = update_flags::retry;
 703                     }
 704                     else if ( pChild == m_Root.child( 1, memory_model::memory_order_acquire ) ) {
 705                         result = try_update( key, cmp, nFlags, funcUpdate, m_pRoot, pChild, nChildVersion, disp );
 706                     }
 707                 }
 708                 else {
 709                     // the tree is empty
 710                     if ( nFlags & update_flags::allow_insert ) {
 711                         // insert into tree as right child of the root
 712                         {
 713                             node_scoped_lock l( m_Monitor, *m_pRoot );
 714
 715                             node_type * pNew = alloc_node( key, 1, 0, m_pRoot, nullptr, nullptr );
 716                             mapped_type * pVal = funcUpdate( pNew );
 717                             assert( pVal != nullptr );
 718                             pNew->m_pValue.store( pVal, memory_model::memory_order_release );
 719
 720                             m_pRoot->child( pNew, 1, memory_model::memory_order_relaxed );
 721                             m_pRoot->height( 2, memory_model::memory_order_relaxed );
 722                         }
 723
 724                         ++m_ItemCounter;
 725                         m_stat.onInsertSuccess();
 726                         return update_flags::result_inserted;
 727                     }
 728
 729                     return update_flags::failed;
 730                 }
 731             } while ( result == update_flags::retry );
 732             return result;
 733         }
 734
 735         template <typename K, typename Compare, typename Func>
 736         int try_update( K const& key, Compare cmp, int nFlags, Func funcUpdate, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
 737         {
 738             assert( gc::is_locked() );
 739             assert( nVersion != node_type::unlinked );
 740
 741             int nCmp = cmp( key, pNode->m_key );
 742             if ( nCmp == 0 ) {
 743                 if ( nFlags & update_flags::allow_update ) {
 744                     return try_update_node( funcUpdate, pNode );
 745                 }
 746                 if ( nFlags & update_flags::allow_remove ) {
 747                     return try_remove_node( pParent, pNode, nVersion, funcUpdate, disp );
 748                 }
 749                 return update_flags::failed;
 750             }
 751
 752             int result;
 753             do {
 754                 node_type * pChild = pNode->child( nCmp ).load( memory_model::memory_order_relaxed );
 755                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
 756                     return update_flags::retry;
 757
 758                 if ( pChild == nullptr ) {
 759                     // insert new node
 760                     if ( nFlags & update_flags::allow_insert )
 761                         result = try_insert_node( key, funcUpdate, pNode, nCmp, nVersion, disp );
 762                     else
 763                         result = update_flags::failed;
 764                 }
 765                 else {
 766                     // update child
 767                     result = update_flags::retry;
 768                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
 769                     if ( nChildVersion & node_type::shrinking ) {
 770                         m_stat.onUpdateWaitShrinking();
 771                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
 772                         // retry
 773                     }
 774                     else if ( pChild == pNode->child( nCmp ).load( memory_model::memory_order_relaxed ) ) {
 775                         // this second read is important, because it is protected by nChildVersion
 776
 777                         // validate the read that our caller took to get to node
 778                         if ( pNode->version( memory_model::memory_order_relaxed ) != nVersion ) {
 779                             m_stat.onUpdateRetry();
 780                             return update_flags::retry;
 781                         }
 782
 783                         // At this point we know that the traversal our parent took to get to node is still valid.
 784                         // The recursive implementation will validate the traversal from node to
 785                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
 786                         // This means that we are no longer vulnerable to node shrinks, and we don't need
 787                         // to validate node version any more.
 788                         result = try_update( key, cmp, nFlags, funcUpdate, pNode, pChild, nChildVersion, disp );
 789                     }
 790                 }
 791             } while ( result == update_flags::retry );
 792             return result;
 793         }
 794
 795         template <typename K, typename Func>
 796         int try_insert_node( K const& key, Func funcUpdate, node_type * pNode, int nDir, version_type nVersion, rcu_disposer& disp )
 797         {
 798             node_type * pNew;
 799
 800             auto fnCreateNode = [&funcUpdate]( node_type * pNew ) {
 801                 mapped_type * pVal = funcUpdate( pNew );
 802                 assert( pVal != nullptr );
 803                 pNew->m_pValue.store( pVal, memory_model::memory_order_relaxed );
 804             };
 805
 806             if ( c_bRelaxedInsert ) {
 807                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
 808                      || pNode->child( nDir ).load( memory_model::memory_order_relaxed ) != nullptr )
 809                 {
 810                     m_stat.onInsertRetry();
 811                     return update_flags::retry;
 812                 }
 813
 814                 fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
 815             }
 816
 817             node_type * pDamaged;
 818             {
 819                 assert( pNode != nullptr );
 820                 node_scoped_lock l( m_Monitor, *pNode );
 821
 822                 if ( pNode->version( memory_model::memory_order_relaxed ) != nVersion
 823                      || pNode->child( nDir ).load( memory_model::memory_order_relaxed ) != nullptr )
 824                 {
 825                     if ( c_RelaxedInsert ) {
 826                         free_node( pNew );
 827                         m_stat.onRelaxedInsertFailed();
 828                     }
 829
 830                     m_stat.onInsertRetry();
 831                     return update_flags::retry;
 832                 }
 833
 834                 if ( !c_bRelaxedInsert )
 835                     fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
 836
 837                 pNode->child( pNew, nDir, memory_model::memory_order_relaxed );
 838                 pDamaged = fix_height_locked( pNode );
 839             }
 840             m_stat.onInsertSuccess();
 841
 842             fix_height_and_rebalance( pDamaged, disp );
 843
 844             return update_flags::result_inserted;
 845         }
 846
 847         template <typename Func>
 848         int try_update_node( Func funcUpdate, node_type * pNode )
 849         {
 850             mapped_type * pOld;
 851             {
 852                 assert( pNode != nullptr );
 853                 node_scoped_lock l( m_Monitor, *pNode );
 854
 855                 if ( pNode->is_unlinked( memory_model::memory_order_relaxed )) {
 856                     m_stat.onUpdateUnlinked();
 857                     return update_flags::retry;
 858                 }
 859
 860                 pOld = pNode->value( memory_model::memory_order_relaxed );
 861                 mapped_type * pVal = funcUpdate( *pNode );
 862                 assert( pVal != nullptr );
 863                 pNode->m_pValue.store( pVal, memory_model::memory_order_relaxed ));
 864             }
 865
 866             if ( pOld ) {
 867                 disposer()(pOld);
 868                 m_stat.onDisposeValue();
 869             }
 870
 871             m_stat.onUpdateSuccess();
 872             return update_flags::result_updated;
 873         }
 874
 875         template <typename Func>
 876         int try_remove_node( node_type * pParent, node_type * pNode, version_type nVersion, Func func, rcu_disposer& disp )
 877         {
 878             assert( pParent != nullptr );
 879             assert( pNode != nullptr );
 880
 881             if ( !pNode->is_valued( atomics::memory_order_relaxed ) )
 882                 return update_flags::failed;
 883
 884             if ( pNode->child( -1, atomics::memory_order_relaxed ) == nullptr
 885               || pNode->child( 1, atomics::memory_order_relaxed ) == nullptr )
 886             {
 887                 node_type * pDamaged;
 888                 mapped_type * pOld;
 889                 {
 890                     node_scoped_lock lp( m_Monitor, *pParent );
 891                     if ( pParent->is_unlinked( atomics::memory_order_relaxed ) || pNode->m_pParent.load( atomics::memory_order_relaxed ) != pParent )
 892                         return update_flags::retry;
 893
 894                     {
 895                         node_scoped_lock ln( m_Monitor, *pNode );
 896                         pOld = pNode->value( atomics::memory_order_relaxed );
 897                         if ( pNode->version( atomics::memory_order_relaxed ) == nVersion
 898                           && pOld
 899                           && try_unlink_locked( pParent, pNode, disp ) )
 900                         {
 901                             pNode->m_pValue.store( nullptr, atomics::memory_order_relaxed );
 902                         }
 903                         else
 904                             return update_flags::retry;
 905                     }
 906                     pDamaged = fix_height_locked( pParent );
 907                 }
 908
 909                 func( pOld );   // calls pOld disposer inside
 910                 m_stat.onDisposeValue();
 911
 912                 fix_height_and_rebalance( pDamaged, disp );
 913                 return upfate_flags::result_removed;
 914             }
 915             else {
 916                 int result = update_flags::retry;
 917                 {
 918                     node_scoped_lock ln( m_Monitor, *pNode );
 919                     mapped_type * pOld = pNode->value( atomics::memory_order_relaxed );
 920                     if ( pNode->version( atomics::memory_order_relaxed ) == nVersion && pOld ) {
 921                         pNode->m_pValue.store( nullptr, atomics::memory_order_relaxed );
 922                         result = upfate_flags::result_removed;
 923                     }
 924                 }
 925
 926                 if ( result == upfate_flags::result_removed ) {
 927                     func( *pOld );  // calls pOld disposer inside
 928                     m_stat.onDisposeValue();
 929                 }
 930
 931                 return result;
 932             }
 933         }
 934
 935         bool try_unlink_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp )
 936         {
 937             // pParent and pNode must be locked
 938             assert( !pParent->is_unlinked(memory_model::memory_order_relaxed) );
 939
 940             node_type * pParentLeft = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
 941             node_type * pParentRight = pParent->m_pRight.load( memory_model::memory_order_relaxed );
 942             if ( pNode != pParentLeft && pNode != pParentRight ) {
 943                 // node is no longer a child of parent
 944                 return false;
 945             }
 946
 947             assert( !pNode->is_unlinked());
 948             assert( pParent == pNode->m_pParent.load(memory_model::memory_order_relaxed));
 949
 950             node_type * pLeft = pNode->m_pLeft.load( memory_model::memory_order_relaxed );
 951             node_type * pRight = pNode->m_pRight.load( memory_model::memory_order_relaxed );
 952             if ( pLeft != nullptr && pRight != nullptr ) {
 953                 // splicing is no longer possible
 954                 return false;
 955             }
 956             node_type * pSplice = pLeft ? pLeft : pRight;
 957
 958             if ( pParentLeft == pNode )
 959                 pParent->m_pLeft.store( pSplice, memory_model::memory_order_relaxed );
 960             else
 961                 pParent->m_pRight.store( pSplice, memory_model::memory_order_relaxed );
 962
 963             if ( pSplice )
 964                 pSplice->pParent.store( pParent, memory_model::memory_order_release );
 965
 966             // Mark the node as unlinked
 967             pNode->version( node_type::unlinked, memory_model::memory_order_release );
 968             disp.dispose( pNode );
 969
 970             return true;
 971         }
 972
 973         //@endcond
 974     private: // rotations
 975         //@cond
 976         int estimate_node_condition( node_type * pNode )
 977         {
 978             node_type * pLeft = pNode->m_pLeft.load( memory_model::memory_order_relaxed );
 979             node_type * pRight = pNode->m_pRight.load( memory_model::memory_order_relaxed );
 980
 981             if ( (pLeft == nullptr || pRight == nullptr) && pNode->value( memory_model::memory_order_relaxed ) == nullptr )
 982                 return unlink_required;
 983
 984             int h = pNode->height( memory_model::memory_order_relaxed );
 985             int hL = pLeft ? pLeft->height( memory_model::memory_order_relaxed ) : 0;
 986             int hR = pRight ? pRight->height( memory_model::memory_order_relaxed ) : 0;
 987
 988             int hNew = 1 + std::max( hL, hR );
 989             int nBalance = hL - hR;
 990
 991             if ( nBalance < -1 || nBalance > 1 )
 992                 return rebalance_required;
 993
 994             return h != hNew ? hNew : nothing_required;
 995         }
 996
 997         node_type * fix_height( node_type * pNode )
 998         {
 999             assert( pNode != nullptr );
1000             node_scoped_lock l( m_Monitor, *pNode );
1001             return fix_height_locked( pNode );
1002         }
1003
1004         node_type * fix_height_locked( node_type * pNode )
1005         {
1006             // pNode must be locked!!!
1007             int h = estimate_node_condition( pNode );
1008             switch ( h ) {
1009                 case rebalance_required:
1010                 case unlink_required:
1011                     return pNode;
1012                 case nothing_required:
1013                     return nullptr;
1014                 default:
1015                     pNode->height( h, memory_model::memory_order_relaxed );
1016                     return pNode->m_pParent.load( memory_model::memory_order_relaxed );
1017             }
1018         }
1019
1020         void fix_height_and_rebalance( node_type * pNode, rcu_disposer& disp )
1021         {
1022             while ( pNode && pNode->m_pParent.load( memory_model::memory_order_relaxed ) ) {
1023                 int nCond = estimate_node_condition( pNode );
1024                 if ( nCond == nothing_required || pNode->is_unlinked( memory_model::memory_order_relaxed ) )
1025                     return;
1026
1027                 if ( nCond != unlink_required && nCond != rebalance_required )
1028                     pNode = fix_height( pNode );
1029                 else {
1030                     node_type * pParent = pNode->m_pParent.load( memory_model::memry_order_relaxed );
1031                     assert( pParent != nullptr );
1032                     {
1033                         node_scoped_lock lp( m_Monitor, *pParent );
1034                         if ( !pParent->is_unlinked( memory_model::memory_order_relaxed )
1035                              && pNode->m_pParent.load( memory_model::memory_order_relaxed ) == pParent )
1036                         {
1037                             node_scoped_lock ln( m_Monitor, *pNode );
1038                             pNode = rebalance_locked( pParent, pNode, disp );
1039                         }
1040                     }
1041                 }
1042             }
1043         }
1044
1045         node_type * rebalance_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp )
1046         {
1047             // pParent and pNode shlould be locked.
1048             // Returns a damaged node, or nullptr if no more rebalancing is necessary
1049             assert( pNode->m_pParent.load( memory_model::memry_order_relaxed ) == pNode );
1050             assert( m_pParent->m_pLeft.load( memory_model::memory_order_relaxed ) == pNode
1051                  || m_pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1052
1053             node_type * pLeft = pNode->m_pLeft.load( memory_model::memory_order_relaxed );
1054             node_type * pRight = pNode->m_pRight.load( memory_model::memory_order_relaxed );
1055
1056             if ( (pLeft == nullptr || pRight == nullptr) && pNode->value( memory_model::memory_order_relaxed ) == nullptr ) {
1057                 if ( try_unlink_locked( pParent, pNode, disp ))
1058                     return fix_height_locked( pParent );
1059                 else {
1060                     // retry needed for pNode
1061                     return pNode;
1062                 }
1063             }
1064
1065             int h = pNode->height( memory_model::memory_order_relaxed );
1066             int hL = pLeft ? pLeft->height( memory_model::memory_order_relaxed ) : 0;
1067             int hR = pRight ? pRight->height( memory_model::memory_order_relaxed ) : 0;
1068             int hNew = 1 + std::max( hL, hR );
1069             int balance = hL - hR;
1070
1071             if ( balance > 1 )
1072                 return rebalance_to_right_locked( pParent, pNode, pLeft, hR );
1073             else if ( balance < -1 )
1074                 return rebalance_to_left_locked( pParent, pNode, pRight, hL );
1075             else if ( hNew != h ) {
1076                 pNode->height( hNew, memory_model::memory_order_relaxed );
1077
1078                 // pParent is already locked
1079                 return fix_height_locked( pParent );
1080             }
1081             else
1082                 return nullptr;
1083         }
1084
1085         node_type * rebalance_to_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR )
1086         {
1087             assert( pNode->m_pParent.load( memory_model::memry_order_relaxed ) == pNode );
1088             assert( m_pParent->m_pLeft.load( memory_model::memory_order_relaxed ) == pNode
1089                  || m_pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1090
1091             // pParent and pNode is locked yet
1092             // pNode->pLeft is too large, we will rotate-right.
1093             // If pLeft->pRight is taller than pLeft->pLeft, then we will first rotate-left pLeft.
1094
1095             {
1096                 assert( pLeft != nullptr );
1097                 node_scoped_lock l( m_Monitor, *pLeft );
1098                 if ( pNode->m_pLeft.load( memory_model::memory_order_relaxed ) != pLeft )
1099                     return pNode; // retry for pNode
1100
1101                 int hL = pLeft->height( memory_model::memory_order_relaxed );
1102                 if ( hL - hR <= 1 )
1103                     return pNode; // retry
1104
1105                 node_type * pLRight = pLeft->m_pRight.load( memory_model::memory_order_relaxed );
1106                 int hLR = pLRight ? pLRight->height( memory_model::memory_order_relaxed ) : 0;
1107                 node_type * pLLeft = pLeft->m_pLeft.load( memory_model::memory_order_relaxed );
1108                 int hLL = pLLeft ? pLLeft->height( memory_model::memory_order_relaxed ) : 0;
1109
1110                 if ( hLL > hLR ) {
1111                     // rotate right
1112                     return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
1113                 }
1114                 else {
1115                     assert( pLRight != nullptr );
1116                     {
1117                         node_scoped_lock lr( m_Monitor, *pLRight );
1118                         if ( pLeft->m_pRight.load( memory_model::memory_order_relaxed ) != pLRight )
1119                             return pNode; // retry
1120
1121                         hLR = pLRight->height( memory_model::memory_order_relaxed );
1122                         if ( hLL > hLR )
1123                             return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
1124
1125                         node_type * pLRLeft = pLRight->m_pLeft.load( memory_model::memory_order_relaxed );
1126                         int hLRL = pLRLeft ? pLRLeft->height( memory_model::memory_order_relaxed  ) : 0;
1127                         int balance = hLL - hLRL;
1128                         if ( balance >= -1 && balance <= 1 && !((hLL == 0 || hLRL == 0) && pLeft->value(memory_model::memory_order_relaxed) == nullptr) ) {
1129                             // nParent.child.left won't be damaged after a double rotation
1130                             return rotate_right_over_left_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLRL );
1131                         }
1132                     }
1133
1134                     // focus on pLeft, if necessary pNode will be balanced later
1135                     return rebalance_to_left_locked( pNode, pLeft, pLRight, hLL );
1136                 }
1137             }
1138         }
1139
1140         node_type * rebalance_to_left_locked( node_type * pParent, node_type * pNode, node_type * pRight, int hL )
1141         {
1142             assert( pNode->m_pParent.load( memory_model::memry_order_relaxed ) == pNode );
1143             assert( m_pParent->m_pLeft.load( memory_model::memory_order_relaxed ) == pNode
1144                     || m_pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1145
1146             // pParent and pNode is locked yet
1147             {
1148                 assert( pRight != nullptr );
1149                 node_scoped_lock l( m_Monitor, *pRight );
1150                 if ( pNode->m_pRight.load( memory_model::memory_order_relaxed ) != pRight )
1151                     return pNode; // retry for pNode
1152
1153                 int hR = pRight->height( memory_model::memory_order_relaxed );
1154                 if ( hL - hR >= -1 )
1155                     return pNode; // retry
1156
1157                 node_type * pRLeft = pRight->m_pLeft.load( memory_model::memory_order_relaxed );
1158                 int hRL = pRLeft > pRLeft->height( memory_model::memory_order_relaxed ) : 0;
1159                 node_type * pRRight = pRight->m_pRight.load( memory_model::memory_order_relaxed );
1160                 int hRR = pRRight ? pRRight->height( memory_model::memory_order_relaxed ) : 0;
1161                 if ( hRR > hRL )
1162                     return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
1163
1164                 {
1165                     assert( pRLeft != nullptr );
1166                     node_scoped_lock lrl( m_Monitor, *pRLeft );
1167                     if ( pRight->m_pLeft.load( memory_model::memory_order_relaxed ) != pRLeft )
1168                         return pNode; // retry
1169
1170                     hRL = pRLeft->height( memory_model::memory_order_relaxed );
1171                     if ( hRR >= hRL )
1172                         return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
1173
1174                     node_type * pRLRight = pRLeft->m_pRight.load( memory_model::memory_order_relaxed );
1175                     int hRLR = pRLRight ? pRLRight->height( memory_model::memory_order_relaxed ) : 0;
1176                     int balance = hRR - hRLR;
1177                     if ( b >= -1 && b <= 1 && !((hRR == 0 || hRLR == 0) && pRight->value( memory_odel::memory_order_relaxed ) == nullptr)
1178                          return rotate_left_over_right_locked( pParent, pNode, hL, pRight, pRLeft, hRR, hRLR );
1179                 }
1180                 return rebalance_to_right_locked( pNode, pRight, pRLeft, hRR );
1181             }
1182         }
1183
1184         static void begin_change( node_type * pNode, version_type version )
1185         {
1186             pNode->version( version | node_type::shrinking, memory_model::memory_order_release );
1187         }
1188         static void end_change( node_type * pNode, version_type version )
1189         {
1190             // Clear shrinking and unlinked flags and increment version
1191             pNode->version( (version | node_type::version_flags) + 1, memory_model::memory_order_release );
1192         }
1193
1194         node_type * rotate_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR, int hLL, node_type * pLRight, int hLR )
1195         {
1196             version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
1197             node_type * pParentLeft = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1198
1199             begin_change( pNode, nodeVersion );
1200
1201             pNode->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
1202             if ( pLRight != nullptr )
1203                 pLRight->m_pParent.store( pNode, memory_model::memory_order_relaxed  );
1204
1205             pLeft->m_pRight.store( pNode, memory_model::memory_order_relaxed );
1206             pNode->m_pParent.store( pLeft, memory_model::memory_order_relaxed );
1207
1208             if ( pParentLeft == pNode )
1209                 pParent->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
1210             else {
1211                 assert( pParent->m_pRight.load( memory_odel::memory_order_relaxed ) == pNode );
1212                 pParent->m_pRight.store( pLeft, memory_mdel::memory_order_relaxed );
1213             }
1214             pLeft->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1215
1216             // fix up heights links
1217             int hNode = 1 + std::max( hLR, hR );
1218             pNode->height( hNode, memory_model::memory_order_relaxed );
1219             pLeft->height( 1 + std::max( hLL, hNode ), memory_model::memory_order_relaxed );
1220
1221             end_change( pNode, nodeVersion );
1222
1223             // We have damaged pParent, pNode (now parent.child.right), and pLeft (now
1224             // parent.child).  pNode is the deepest.  Perform as many fixes as we can
1225             // with the locks we've got.
1226
1227             // We've already fixed the height for pNode, but it might still be outside
1228             // our allowable balance range.  In that case a simple fix_height_locked()
1229             // won't help.
1230             int nodeBalance = hLR - hR;
1231             if ( nodeBalance < -1 || nodeBalance > 1 ) {
1232                 // we need another rotation at pNode
1233                 return pNode;
1234             }
1235
1236             // we've fixed balance and height damage for pNode, now handle
1237             // extra-routing node damage
1238             if ( (pLRight == nullptr || hR == 0) && pNode->value(memory_model::memory_order_relaxed) == nullptr ) {
1239                 // we need to remove pNode and then repair
1240                 return pNode;
1241             }
1242
1243             // we've already fixed the height at pLeft, do we need a rotation here?
1244             int leftBalance = hLL - hNode;
1245             if ( leftBalance < -1 || leftBalance > 1 )
1246                 return pLeft;
1247
1248             // pLeft might also have routing node damage (if pLeft.left was null)
1249             if ( hLL == 0 && pLeft->value( memory_model::memory_order_relaxed ) == nullptr )
1250                 return pLeft;
1251
1252             // try to fix the parent height while we've still got the lock
1253             return fix_height_locked( pParent );
1254         }
1255
1256         node_type * rotate_left_locked( node_type * pParent, node_type * pNode, int hL, node_type * pRight, node_type * pRLeft, int hRL, int hRR )
1257         {
1258             version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
1259             node_type * pParentLeft = pParent->m_pLeft.load( memory_odel::memory_order_relaxed );
1260
1261             begin_change( pNode, nodeVersion );
1262
1263             // fix up pNode links, careful to be compatible with concurrent traversal for all but pNode
1264             pNode->m_pRight.store( pRLeft, memory_nodel::memory_order_relaxed );
1265             if ( pRLeft != nullptr )
1266                 pRLeft->m_pParent.store( pNode, memory_model::memory_order_relaxed );
1267
1268             pRight->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
1269             pNode->m_pParent.store( pRight, memory_model::memory_order_relaxed );
1270
1271             if ( pParentLeft == pNode )
1272                 pParent->m_pLeft.store( pRight, memory_model::memory_order_relaxed );
1273             else {
1274                 assert( pParent->m_pRight.load( memory_odel::memory_order_relaxed ) == pNode );
1275                 pParent->m_pRight.store( pRight, memory_model::memory_model_relaxed );
1276             }
1277             pRight->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1278
1279             // fix up heights
1280             int hNode = 1 + std::max( hL, hRL );
1281             pNode->height( hNode, memory_model::memory_order_relaxed );
1282             pRight->height( 1 + std::max( hNode, hRR ), memory_model::memory_order_relaxed );
1283
1284             end_change( pNode, nodeVersion );
1285
1286             int nodeBalance = hRL - hL;
1287             if ( nodeBalance < -1 || nodeBalance > 1 )
1288                 return pNode;
1289
1290             if ( (pRLeft == nullptr || hL == 0) && pNode->value( memory_model::memory_order_relaxed ) == nullptr )
1291                 return pNode;
1292
1293             int rightBalance = hRR - hNode;
1294             if ( rightBalance < -1 || rightBalance > 1 )
1295                 return pRight;
1296
1297             if ( hRR == 0 && pRight->value( memory_model::memory_order_relaxed ) == nullptr )
1298                 return pRight;
1299
1300             return fix_height_locked( pParent );
1301         }
1302
1303         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 )
1304         {
1305             typename node_type::value_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
1306             typename node_type::value_type leftVersion = pLeft->version( memory_model::memory_order_relaxed );
1307
1308             node_type * pPL = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1309             node_type * pLRL = pLRight->m_pLeft.load( memory_model::memory_order_relaxed );
1310             node_type * pLRR = pLRight->m_pRight.load( memory_model::memory_order_relaxed );
1311             int hLRR = pLRR ? pLRR->hight( memory_model::memory_order_relaxed ) : 0;
1312
1313             begin_change( pNode, nodeVersion );
1314             begin_change( pLeft, leftVersion );
1315
1316             // fix up pNode links, careful about the order!
1317             pNode->m_pLeft.store( pLRR, memory_model::memory_order_relaxed );
1318             if ( pLRR != nullptr )
1319                 pLRR->m_pParent.store( pNode, memory_model::memory_order_relaxed );
1320
1321             pLeft->m_pRight.store( pLRL, memory_model::memory_order_relaxed );
1322             if ( pLRL != nullptr )
1323                 pLRL->m_pParent.store( pLeft, memory_model::memory_order_relaxed );
1324
1325             pLRight->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
1326             pLeft->m_pParent.store( pLRight, memory_model::memory_order_relaxed );
1327             pLRight->m_pRight.store( pNode, memory_model::memory_order_relaxed );
1328             pNode->m_pParent.store( pLRight, memory_model::memory_order_relaxed );
1329
1330             if ( pPL == pNode )
1331                 pParent->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
1332             else {
1333                 assert( Parent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1334                 pParent->m_pRight.store( pLRight, memory_model::memory_order_relaxed );
1335             }
1336             pLRight->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1337
1338             // fix up heights
1339             int hNode = 1 + std::max( hLRR, hR );
1340             pNode->height( hNode, memory_model::memory_order_relaxed );
1341             int hLeft = 1 + std::max( hLL, hLRL );
1342             pLeft->height( hLeft, memory_model::memory_order_relaxed );
1343             pLRight->height( 1 + std::max( hLeft, hNode ), memory_model::memory_order_relaxed );
1344
1345             end_change( pNode, nodeVersion );
1346             end_change( pLeft, leftVersion );
1347
1348             // caller should have performed only a single rotation if pLeft was going
1349             // to end up damaged
1350             assert( hLL - hLRL <= 1 && hLRL - hLL <= 1 );
1351             assert( !((hLL == 0 || pLRL == nullptr) && pLeft->value( memory_model::memory_order_relaxed ) == nullptr ));
1352
1353             // We have damaged pParent, pLR (now parent.child), and pNode (now
1354             // parent.child.right).  pNode is the deepest.  Perform as many fixes as we
1355             // can with the locks we've got.
1356
1357             // We've already fixed the height for pNode, but it might still be outside
1358             // our allowable balance range.  In that case a simple fix_height_locked()
1359             // won't help.
1360             int nodeBalance = hLRR - hR;
1361             if ( nodeBalance < -1 || nodeBalance > 1 ) {
1362                 // we need another rotation at pNode
1363                 return pNode;
1364             }
1365
1366             // pNode might also be damaged by being an unnecessary routing node
1367             if ( (pLRR == nullptr || hR == 0) && pNode->value( memory_model::memory_order_relaxed ) == nullptr ) {
1368                 // repair involves splicing out pNode and maybe more rotations
1369                 return pNode;
1370             }
1371
1372             // we've already fixed the height at pLRight, do we need a rotation here?
1373             final int balanceLR = hLeft - hNode;
1374             if ( balanceLR < -1 || balanceLR > 1 )
1375                 return pLR;
1376
1377             // try to fix the parent height while we've still got the lock
1378             return fix_height_locked( pParent );
1379         }
1380
1381         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 )
1382         {
1383             version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
1384             version_type rightVersion = pRight->version( memory_model::memory_order_relaxed );
1385
1386             node_type * pPL = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1387             node_type * pRLL = pRLeft->m_pLeft.load( memory_model::memory_order_relaxed );
1388             node_type * pRLR = pRLeft->m_pRight.load( memory_model::memory_order_relaxed );
1389             int hRLL = pRLL ? pRLL->height( memory_model::memory_order_relaxed ) : 0;
1390
1391             begin_change( pNode, nodeVersion );
1392             begin_change( pRight, ghtVersion );
1393
1394             // fix up pNode links, careful about the order!
1395             pNode->m_pRight.store( pRLL, memory_model::memory_order_relaxed );
1396             if ( pRLL != nullptr )
1397                 pRLL->m_pParent.store( pNode, memory_model::memory_order_relaxed );
1398
1399             pRight->m_pLeft.store( pRLR, memory_model::memory_order_relaxed );
1400             if ( pRLR != nullptr )
1401                 pRLR->m_pParent.store( pRight, memory_model::memory_order_relaxed );
1402
1403             pRLeft->m_pRight.store( pRight, memory_model::memory_order_relaxed );
1404             pRight->m_pParent.store( pRLeft, memory_model::memory_order_relaxed );
1405             pRLeft->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
1406             pNode->m_pParent.store( pRLeft, memory_model::memory_order_relaxed );
1407
1408             if ( pPL == pNode )
1409                 pParent->m_pLeft.store( pRLeft, memory_model::memory_order_relaxed );
1410             else {
1411                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1412                 pParent->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
1413             }
1414             pRLeft->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1415
1416             // fix up heights
1417             int hNode = 1 + std::max( hL, hRLL );
1418             pNode->height( hNode, memory_model::memory_order_relaxed );
1419             int hRight = 1 + std::max( hRLR, hRR );
1420             pRight->height( hRight, memory_model::memory_order_relaxed );
1421             pRLeft->height( 1 + std::max( hNode, hRight ), memory_model::memory_order_relaxed );
1422
1423             end_change( pNode, nodeVersion );
1424             end_change( pRight, rightVersion );
1425
1426             assert( hRR - hRLR <= 1 && hRLR - hRR <= 1 );
1427
1428             int nodeBalance = hRLL - hL;
1429             if ( nodeBalance < -1 || nodeBalance > 1 )
1430                 return pNode;
1431             if ( (pRLL == nullptr || hL == 0) && pNode->value( memory_model::memory_order_relaxed ) == nullptr )
1432                 return pNode;
1433
1434             int balRL = hRight - hNode;
1435             if ( balRL < -1 || balRL > 1 )
1436                 return pRLeft;
1437
1438             return fix_height_locked( pParent );
1439         }
1440
1441         //@endcond
1442     };
1443 }} // namespace cds::container
1444
1445 #endif // #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H