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