cds/container/impl/bronson_avltree_map_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H
   4 #define CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H
   5
   6 #include <type_traits> // is_base_of
   7 #include <cds/container/details/bronson_avltree_base.h>
   8 #include <cds/urcu/details/check_deadlock.h>
   9 #include <cds/urcu/exempt_ptr.h>
  10
  11 namespace cds { namespace container {
  12
  13     /// Bronson et al AVL-tree (RCU specialization for storing pointer to values)
  14     /** @ingroup cds_nonintrusive_map
  15         @ingroup cds_nonintrusive_tree
  16         @headerfile cds/container/bronson_avltree_map_rcu.h
  17         @anchor cds_container_BronsonAVLTreeMap_rcu_ptr
  18
  19         This is the specialization of \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based Bronson et al AVL-tree"
  20         for "key -> value pointer" map. This specialization stores the pointer to user-allocated values instead of the copy
  21         of the value. When a tree node is removed, the algorithm does not free the value pointer directly, instead, it call
  22         the disposer functor provided by \p Traits template parameter.
  23
  24         <b>Template arguments</b>:
  25         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  26         - \p Key - key type
  27         - \p T - value type to be stored in tree's nodes. Note, the specialization stores the pointer to user-allocated
  28             value, not the copy.
  29         - \p Traits - tree traits, default is \p bronson_avltree::traits
  30             It is possible to declare option-based tree with \p bronson_avltree::make_traits metafunction
  31             instead of \p Traits template argument.
  32
  33         @note Before including <tt><cds/container/bronson_avltree_map_rcu.h></tt> you should include appropriate RCU header file,
  34         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  35     */
  36     template <
  37         typename RCU,
  38         typename Key,
  39         typename T,
  40 #   ifdef CDS_DOXYGEN_INVOKED
  41         typename Traits = bronson_avltree::traits
  42 #else
  43         typename Traits
  44 #endif
  45     >
  46     class BronsonAVLTreeMap< cds::urcu::gc<RCU>, Key, T*, Traits >
  47     {
  48     public:
  49         typedef cds::urcu::gc<RCU>  gc;   ///< RCU Garbage collector
  50         typedef Key     key_type;    ///< type of a key stored in the map
  51         typedef T *     mapped_type; ///< type of value stored in the map
  52         typedef Traits  traits;      ///< Traits template parameter
  53
  54 #   ifdef CDS_DOXYGEN_INVOKED
  55         typedef implementation_defined key_comparator;    ///< key compare functor based on \p Traits::compare and \p Traits::less
  56 #   else
  57         typedef typename opt::details::make_comparator< key_type, traits >::type key_comparator;
  58 #endif
  59         typedef typename traits::item_counter           item_counter;       ///< Item counting policy
  60         typedef typename traits::memory_model           memory_model;       ///< Memory ordering, see \p cds::opt::memory_model option
  61         typedef typename traits::node_allocator         node_allocator_type; ///< allocator for maintaining internal nodes
  62         typedef typename traits::stat                   stat;               ///< internal statistics
  63         typedef typename traits::rcu_check_deadlock     rcu_check_deadlock; ///< Deadlock checking policy
  64         typedef typename traits::back_off               back_off;           ///< Back-off strategy
  65         typedef typename traits::disposer               disposer;           ///< Value disposer
  66         typedef typename traits::sync_monitor           sync_monitor;       ///< @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
  67
  68         /// Enabled or disabled @ref bronson_avltree::relaxed_insert "relaxed insertion"
  69         static CDS_CONSTEXPR bool const c_bRelaxedInsert = traits::relaxed_insert;
  70
  71         /// Group of \p extract_xxx functions does not require external locking
  72         static CDS_CONSTEXPR const bool c_bExtractLockExternal = false;
  73
  74 #   ifdef CDS_DOXYGEN_INVOKED
  75         /// Returned pointer to \p mapped_type of extracted node
  76         typedef cds::urcu::exempt_ptr< gc, T, T, disposer, void > exempt_ptr;
  77 #   else
  78         typedef cds::urcu::exempt_ptr< gc,
  79             typename std::remove_pointer<mapped_type>::type,
  80             typename std::remove_pointer<mapped_type>::type,
  81             disposer,
  82             void
  83         > exempt_ptr;
  84 #   endif
  85
  86         typedef typename gc::scoped_lock    rcu_lock;  ///< RCU scoped lock
  87
  88     protected:
  89         //@cond
  90         typedef bronson_avltree::node< key_type, mapped_type, sync_monitor > node_type;
  91         typedef typename node_type::version_type version_type;
  92
  93         typedef cds::details::Allocator< node_type, node_allocator_type > cxx_allocator;
  94         typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock >   check_deadlock_policy;
  95
  96         enum class find_result
  97         {
  98             not_found,
  99             found,
 100             retry
 101         };
 102
 103         struct update_flags
 104         {
 105             enum {
 106                 allow_insert = 1,
 107                 allow_update = 2,
 108                 //allow_remove = 4,
 109
 110                 retry = 1024,
 111
 112                 failed = 0,
 113                 result_inserted = allow_insert,
 114                 result_updated = allow_update,
 115                 result_removed = 4
 116             };
 117         };
 118
 119         enum node_condition
 120         {
 121             nothing_required = -3,
 122             rebalance_required = -2,
 123             unlink_required = -1
 124         };
 125
 126         enum direction {
 127             left_child = -1,
 128             right_child = 1
 129         };
 130
 131         typedef typename sync_monitor::template scoped_lock<node_type> node_scoped_lock;
 132         //@endcond
 133
 134     protected:
 135         //@cond
 136         template <typename K>
 137         static node_type * alloc_node( K&& key, int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight )
 138         {
 139             return cxx_allocator().New( std::forward<K>( key ), nHeight, version, pParent, pLeft, pRight );
 140         }
 141
 142         static void free_node( node_type * pNode )
 143         {
 144             // Free node without disposer
 145             assert( !pNode->is_valued( memory_model::memory_order_relaxed ));
 146             assert( pNode->m_SyncMonitorInjection.check_free());
 147             cxx_allocator().Delete( pNode );
 148         }
 149
 150         static void free_value( mapped_type pVal )
 151         {
 152             disposer()(pVal);
 153         }
 154
 155         static node_type * child( node_type * pNode, int nDir, atomics::memory_order order = memory_model::memory_order_relaxed )
 156         {
 157             return pNode->child( nDir ).load( order );
 158         }
 159
 160         static node_type * parent( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
 161         {
 162             return pNode->parent( order );
 163         }
 164
 165         // RCU safe disposer
 166         class rcu_disposer
 167         {
 168             node_type *     m_pRetiredList;     ///< head of retired node list
 169             mapped_type     m_pRetiredValue;    ///< value retired
 170
 171         public:
 172             rcu_disposer()
 173                 : m_pRetiredList( nullptr )
 174                 , m_pRetiredValue( nullptr )
 175             {}
 176
 177             ~rcu_disposer()
 178             {
 179                 clean();
 180             }
 181
 182             void dispose( node_type * pNode )
 183             {
 184                 assert( !pNode->is_valued( memory_model::memory_order_relaxed ));
 185                 pNode->m_pNextRemoved = m_pRetiredList;
 186                 m_pRetiredList = pNode;
 187             }
 188
 189             void dispose_value( mapped_type pVal )
 190             {
 191                 assert( m_pRetiredValue == nullptr );
 192                 m_pRetiredValue = pVal;
 193             }
 194
 195         private:
 196             struct internal_disposer
 197             {
 198                 void operator()( node_type * p ) const
 199                 {
 200                     free_node( p );
 201                 }
 202             };
 203
 204             void clean()
 205             {
 206                 assert( !gc::is_locked() );
 207
 208                 // TODO: use RCU::batch_retire
 209
 210                 // Dispose nodes
 211                 for ( node_type * p = m_pRetiredList; p; ) {
 212                     node_type * pNext = static_cast<node_type *>( p->m_pNextRemoved );
 213                     // Value already disposed
 214                     gc::template retire_ptr<internal_disposer>( p );
 215                     p = pNext;
 216                 }
 217
 218                 // Dispose value
 219                 if ( m_pRetiredValue  )
 220                     gc::template retire_ptr<disposer>( m_pRetiredValue );
 221             }
 222         };
 223
 224         //@endcond
 225
 226     protected:
 227         //@cond
 228         typename node_type::base_class m_Root;
 229         node_type *             m_pRoot;
 230         item_counter            m_ItemCounter;
 231         mutable sync_monitor    m_Monitor;
 232         mutable stat            m_stat;
 233         //@endcond
 234
 235     public:
 236         /// Creates empty map
 237         BronsonAVLTreeMap()
 238             : m_pRoot( static_cast<node_type *>( &m_Root ))
 239         {}
 240
 241         /// Destroys the map
 242         ~BronsonAVLTreeMap()
 243         {
 244             unsafe_clear();
 245         }
 246
 247         /// Inserts new node
 248         /**
 249             The \p key_type should be constructible from a value of type \p K.
 250
 251             RCU \p synchronize() can be called. RCU should not be locked.
 252
 253             Returns \p true if inserting successful, \p false otherwise.
 254         */
 255         template <typename K>
 256         bool insert( K const& key, mapped_type pVal )
 257         {
 258             return do_update(key, key_comparator(),
 259                 [pVal]( node_type * pNode ) -> mapped_type
 260                 {
 261                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 262                     CDS_UNUSED( pNode );
 263                     return pVal;
 264                 },
 265                 update_flags::allow_insert
 266             ) == update_flags::result_inserted;
 267         }
 268
 269         /// Updates the value for \p key
 270         /**
 271             The operation performs inserting or updating the value for \p key with lock-free manner.
 272             If \p bInsert is \p false, only updating of existing node is possible.
 273
 274             If \p key is not found and inserting is allowed (i.e. \p bInsert is \p true),
 275             then the new node created from \p key will be inserted into the map; note that in this case the \ref key_type should be
 276             constructible from type \p K.
 277             Otherwise, the value for \p key will be changed to \p pVal.
 278
 279             RCU \p synchronize() method can be called. RCU should not be locked.
 280
 281             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
 282             \p second is \p true if new node has been added or \p false if the node with \p key
 283             already exists.
 284         */
 285         template <typename K>
 286         std::pair<bool, bool> update( K const& key, mapped_type pVal, bool bInsert = true )
 287         {
 288             int result = do_update( key, key_comparator(),
 289                 [pVal]( node_type * ) -> mapped_type
 290                 {
 291                     return pVal;
 292                 },
 293                 update_flags::allow_update | (bInsert ? update_flags::allow_insert : 0)
 294             );
 295             return std::make_pair( result != 0, (result & update_flags::result_inserted) != 0 );
 296         }
 297
 298         //@cond
 299         template <typename K>
 300         std::pair<bool, bool> ensure( K const& key, mapped_type pVal )
 301         {
 302             return update( key, pVal, true );
 303         }
 304
 305         //@endcond
 306
 307         /// Delete \p key from the map
 308         /**
 309             RCU \p synchronize() method can be called. RCU should not be locked.
 310
 311             Return \p true if \p key is found and deleted, \p false otherwise
 312         */
 313         template <typename K>
 314         bool erase( K const& key )
 315         {
 316             return do_remove(
 317                 key,
 318                 key_comparator(),
 319                 []( key_type const&, mapped_type pVal, rcu_disposer& disp ) -> bool { disp.dispose_value( pVal ); return true; }
 320             );
 321         }
 322
 323         /// Deletes the item from the map using \p pred predicate for searching
 324         /**
 325             The function is an analog of \p erase(K const&)
 326             but \p pred is used for key comparing.
 327             \p Less functor has the interface like \p std::less.
 328             \p Less must imply the same element order as the comparator used for building the map.
 329         */
 330         template <typename K, typename Less>
 331         bool erase_with( K const& key, Less pred )
 332         {
 333             CDS_UNUSED( pred );
 334             return do_remove(
 335                 key,
 336                 cds::opt::details::make_comparator_from_less<Less>(),
 337                 []( key_type const&, mapped_type pVal, rcu_disposer& disp ) -> bool { disp.dispose_value( pVal ); return true;  }
 338             );
 339         }
 340
 341         /// Delete \p key from the map
 342         /**
 343             The function searches an item with key \p key, calls \p f functor
 344             and deletes the item. If \p key is not found, the functor is not called.
 345
 346             The functor \p Func interface:
 347             \code
 348             struct extractor {
 349                 void operator()( key_type const& key, std::remove_pointer<mapped_type>::type& val) { ... }
 350             };
 351             \endcode
 352
 353             RCU \p synchronize method can be called. RCU should not be locked.
 354
 355             Return \p true if key is found and deleted, \p false otherwise
 356         */
 357         template <typename K, typename Func>
 358         bool erase( K const& key, Func f )
 359         {
 360             return do_remove(
 361                 key,
 362                 key_comparator(),
 363                 [&f]( key_type const& key, mapped_type pVal, rcu_disposer& disp ) -> bool {
 364                     assert( pVal );
 365                     f( key, *pVal );
 366                     disp.dispose_value(pVal);
 367                     return true;
 368                 }
 369             );
 370         }
 371
 372         /// Deletes the item from the map using \p pred predicate for searching
 373         /**
 374             The function is an analog of \p erase(K const&, Func)
 375             but \p pred is used for key comparing.
 376             \p Less functor has the interface like \p std::less.
 377             \p Less must imply the same element order as the comparator used for building the map.
 378         */
 379         template <typename K, typename Less, typename Func>
 380         bool erase_with( K const& key, Less pred, Func f )
 381         {
 382             CDS_UNUSED( pred );
 383             return do_remove(
 384                 key,
 385                 cds::opt::details::make_comparator_from_less<Less>(),
 386                 [&f]( key_type const& key, mapped_type pVal, rcu_disposer& disp ) -> bool {
 387                     assert( pVal );
 388                     f( key, *pVal );
 389                     disp.dispose_value(pVal);
 390                     return true;
 391                 }
 392             );
 393         }
 394
 395         /// Extracts a value with minimal key from the map
 396         /**
 397             Returns \p exempt_ptr to the leftmost item.
 398             If the tree is empty, returns empty \p exempt_ptr.
 399
 400             Note that the function returns only the value for minimal key.
 401             To retrieve its key use \p extract_min( Func ) member function.
 402
 403             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
 404             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 405             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 406             So, the function returns the item with minimum key at the moment of tree traversing.
 407
 408             RCU \p synchronize method can be called. RCU should NOT be locked.
 409             The function does not free the item.
 410             The deallocator will be implicitly invoked when the returned object is destroyed or when
 411             its \p release() member function is called.
 412         */
 413         exempt_ptr extract_min()
 414         {
 415             return exempt_ptr(do_extract_min( []( key_type const& ) {}));
 416         }
 417
 418         /// Extracts minimal key key and corresponding value
 419         /**
 420             Returns \p exempt_ptr to the leftmost item.
 421             If the tree is empty, returns empty \p exempt_ptr.
 422
 423             \p Func functor is used to store minimal key.
 424             \p Func has the following signature:
 425             \code
 426             struct functor {
 427                 void operator()( key_type const& key );
 428             };
 429             \endcode
 430             If the tree is empty, \p f is not called.
 431             Otherwise, is it called with minimal key, the pointer to corresponding value is returned
 432             as \p exempt_ptr.
 433
 434             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
 435             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 436             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 437             So, the function returns the item with minimum key at the moment of tree traversing.
 438
 439             RCU \p synchronize method can be called. RCU should NOT be locked.
 440             The function does not free the item.
 441             The deallocator will be implicitly invoked when the returned object is destroyed or when
 442             its \p release() member function is called.
 443         */
 444         template <typename Func>
 445         exempt_ptr extract_min( Func f )
 446         {
 447             return exempt_ptr(do_extract_min( [&f]( key_type const& key ) { f(key); }));
 448         }
 449
 450         /// Extracts minimal key key and corresponding value
 451         /**
 452             This function is a shortcut for the following call:
 453             \code
 454             key_type key;
 455             exempt_ptr xp = theTree.extract_min( [&key]( key_type const& k ) { key = k; } );
 456             \endode
 457             \p key_type should be copy-assignable. The copy of minimal key
 458             is returned in \p min_key argument.
 459         */
 460         typename std::enable_if< std::is_copy_assignable<key_type>::value, exempt_ptr >::type
 461         extract_min_key( key_type& min_key )
 462         {
 463             return exempt_ptr(do_extract_min( [&min_key]( key_type const& key ) { min_key = key; }));
 464         }
 465
 466         /// Extracts a value with maximal key from the tree
 467         /**
 468             Returns \p exempt_ptr pointer to the rightmost item.
 469             If the set is empty, returns empty \p exempt_ptr.
 470
 471             Note that the function returns only the value for maximal key.
 472             To retrieve its key use \p extract_max( Func ) member function.
 473
 474             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
 475             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 476             During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
 477             So, the function returns the item with maximum key at the moment of tree traversing.
 478
 479             RCU \p synchronize method can be called. RCU should NOT be locked.
 480             The function does not free the item.
 481             The deallocator will be implicitly invoked when the returned object is destroyed or when
 482             its \p release() is called.
 483         */
 484         exempt_ptr extract_max()
 485         {
 486             return exempt_ptr(do_extract_max( []( key_type const& ) {}));
 487         }
 488
 489         /// Extracts the maximal key and corresponding value
 490         /**
 491             Returns \p exempt_ptr pointer to the rightmost item.
 492             If the set is empty, returns empty \p exempt_ptr.
 493
 494             \p Func functor is used to store maximal key.
 495             \p Func has the following signature:
 496             \code
 497                 struct functor {
 498                     void operator()( key_type const& key );
 499                 };
 500             \endcode
 501             If the tree is empty, \p f is not called.
 502             Otherwise, is it called with maximal key, the pointer to corresponding value is returned
 503             as \p exempt_ptr.
 504
 505             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
 506             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 507             During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
 508             So, the function returns the item with maximum key at the moment of tree traversing.
 509
 510             RCU \p synchronize method can be called. RCU should NOT be locked.
 511             The function does not free the item.
 512             The deallocator will be implicitly invoked when the returned object is destroyed or when
 513             its \p release() is called.
 514         */
 515         template <typename Func>
 516         exempt_ptr extract_max( Func f )
 517         {
 518             return exempt_ptr(do_extract_max( [&f]( key_type const& key ) { f(key); }));
 519         }
 520
 521         /// Extracts the maximal key and corresponding value
 522         /**
 523             This function is a shortcut for the following call:
 524             \code
 525                 key_type key;
 526                 exempt_ptr xp = theTree.extract_max( [&key]( key_type const& k ) { key = k; } );
 527             \endode
 528             \p key_type should be copy-assignable. The copy of maximal key
 529             is returned in \p max_key argument.
 530         */
 531         typename std::enable_if< std::is_copy_assignable<key_type>::value, exempt_ptr >::type
 532         extract_max_key( key_type& max_key )
 533         {
 534             return exempt_ptr(do_extract_max( [&max_key]( key_type const& key ) { max_key = key; }));
 535         }
 536
 537         /// Extracts an item from the map
 538         /**
 539             The function searches an item with key equal to \p key in the tree,
 540             unlinks it, and returns \p exempt_ptr pointer to a value found.
 541             If \p key is not found the function returns an empty \p exempt_ptr.
 542
 543             RCU \p synchronize method can be called. RCU should NOT be locked.
 544             The function does not destroy the value found.
 545             The disposer will be implicitly invoked when the returned object is destroyed or when
 546             its \p release() member function is called.
 547         */
 548         template <typename Q>
 549         exempt_ptr extract( Q const& key )
 550         {
 551             return exempt_ptr(do_extract( key ));
 552         }
 553
 554
 555         /// Extracts an item from the map using \p pred for searching
 556         /**
 557             The function is an analog of \p extract(Q const&)
 558             but \p pred is used for key compare.
 559             \p Less has the interface like \p std::less.
 560             \p pred must imply the same element order as the comparator used for building the tree.
 561         */
 562         template <typename Q, typename Less>
 563         exempt_ptr extract_with( Q const& key, Less pred )
 564         {
 565             return exempt_ptr(do_extract_with( key, pred ));
 566         }
 567
 568         /// Find the key \p key
 569         /**
 570             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 571             The interface of \p Func functor is:
 572             \code
 573             struct functor {
 574                 void operator()( key_type const& key, mapped_type& item );
 575             };
 576             \endcode
 577             where \p item is the item found.
 578             The functor is called under node-level lock.
 579
 580             The function applies RCU lock internally.
 581
 582             The function returns \p true if \p key is found, \p false otherwise.
 583         */
 584         template <typename K, typename Func>
 585         bool find( K const& key, Func f )
 586         {
 587             return do_find( key, key_comparator(),
 588                 [&f]( node_type * pNode ) -> bool {
 589                     assert( pNode != nullptr );
 590                     mapped_type pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
 591                     if ( pVal ) {
 592                         f( pNode->m_key, *pVal );
 593                         return true;
 594                     }
 595                     return false;
 596                 }
 597             );
 598         }
 599
 600         /// Finds the key \p val using \p pred predicate for searching
 601         /**
 602             The function is an analog of \p find(K const&, Func)
 603             but \p pred is used for key comparing.
 604             \p Less functor has the interface like \p std::less.
 605             \p Less must imply the same element order as the comparator used for building the map.
 606         */
 607         template <typename K, typename Less, typename Func>
 608         bool find_with( K const& key, Less pred, Func f )
 609         {
 610             CDS_UNUSED( pred );
 611             return do_find( key, cds::opt::details::make_comparator_from_less<Less>(),
 612                 [&f]( node_type * pNode ) -> bool {
 613                     assert( pNode != nullptr );
 614                     mapped_type pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
 615                     if ( pVal ) {
 616                         f( pNode->m_key, *pVal );
 617                         return true;
 618                     }
 619                     return false;
 620                 }
 621             );
 622         }
 623
 624         /// Find the key \p key
 625         /**
 626             The function searches the item with key equal to \p key
 627             and returns \p true if it is found, and \p false otherwise.
 628
 629             The function applies RCU lock internally.
 630         */
 631         template <typename K>
 632         bool find( K const& key )
 633         {
 634             return do_find( key, key_comparator(), []( node_type * ) -> bool { return true; });
 635         }
 636
 637         /// Finds the key \p val using \p pred predicate for searching
 638         /**
 639             The function is an analog of \p find(K const&)
 640             but \p pred is used for key comparing.
 641             \p Less functor has the interface like \p std::less.
 642             \p Less must imply the same element order as the comparator used for building the map.
 643         */
 644         template <typename K, typename Less>
 645         bool find_with( K const& key, Less pred )
 646         {
 647             CDS_UNUSED( pred );
 648             return do_find( key, cds::opt::details::make_comparator_from_less<Less>(), []( node_type * ) -> bool { return true; } );
 649         }
 650
 651         /// Clears the tree (thread safe, not atomic)
 652         /**
 653             The function unlink all items from the tree.
 654             The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
 655             this sequence
 656             \code
 657             set.clear();
 658             assert( set.empty() );
 659             \endcode
 660             the assertion could be raised.
 661
 662             For each node the \ref disposer will be called after unlinking.
 663
 664             RCU \p synchronize method can be called. RCU should not be locked.
 665         */
 666         void clear()
 667         {
 668             while ( extract_min() );
 669         }
 670
 671         /// Clears the tree (not thread safe)
 672         /**
 673             This function is not thread safe and may be called only when no other thread deals with the tree.
 674             The function is used in the tree destructor.
 675         */
 676         void unsafe_clear()
 677         {
 678             clear(); // temp solution
 679             //TODO
 680         }
 681
 682         /// Checks if the map is empty
 683         bool empty() const
 684         {
 685             return m_Root.m_pRight.load( memory_model::memory_order_relaxed ) == nullptr;
 686         }
 687
 688         /// Returns item count in the map
 689         /**
 690             Only leaf nodes containing user data are counted.
 691
 692             The value returned depends on item counter type provided by \p Traits template parameter.
 693             If it is \p atomicity::empty_item_counter this function always returns 0.
 694
 695             The function is not suitable for checking the tree emptiness, use \p empty()
 696             member function for this purpose.
 697         */
 698         size_t size() const
 699         {
 700             return m_ItemCounter;
 701         }
 702
 703         /// Returns const reference to internal statistics
 704         stat const& statistics() const
 705         {
 706             return m_stat;
 707         }
 708
 709         /// Returns reference to \p sync_monitor object
 710         sync_monitor& monitor()
 711         {
 712             return m_Monitor;
 713         }
 714         //@cond
 715         sync_monitor const& monitor() const
 716         {
 717             return m_Monitor;
 718         }
 719         //@endcond
 720
 721         /// Checks internal consistency (not atomic, not thread-safe)
 722         /**
 723             The debugging function to check internal consistency of the tree.
 724         */
 725         bool check_consistency() const
 726         {
 727             return check_consistency([]( size_t /*nLevel*/, size_t /*hLeft*/, size_t /*hRight*/ ){} );
 728         }
 729
 730         /// Checks internal consistency (not atomic, not thread-safe)
 731         /**
 732             The debugging function to check internal consistency of the tree.
 733             The functor \p Func is called if a violation of internal tree structure
 734             is found:
 735             \code
 736             struct functor {
 737                 void operator()( size_t nLevel, size_t hLeft, size_t hRight );
 738             };
 739             \endcode
 740             where
 741             - \p nLevel - the level where the violation is found
 742             - \p hLeft - the height of left subtree
 743             - \p hRight - the height of right subtree
 744
 745             The functor is called for each violation found.
 746         */
 747         template <typename Func>
 748         bool check_consistency( Func f ) const
 749         {
 750             node_type * pChild = child( m_pRoot, right_child );
 751             if ( pChild ) {
 752                 size_t nErrors = 0;
 753                 do_check_consistency( pChild, 1, f, nErrors );
 754                 return nErrors == 0;
 755             }
 756             return true;
 757         }
 758
 759     protected:
 760         //@cond
 761         template <typename Func>
 762         size_t do_check_consistency( node_type * pNode, size_t nLevel, Func f, size_t& nErrors ) const
 763         {
 764             if ( pNode ) {
 765                 key_comparator cmp;
 766                 node_type * pLeft = child( pNode, left_child );
 767                 node_type * pRight = child( pNode, right_child );
 768                 if ( pLeft && cmp( pLeft->m_key, pNode->m_key ) > 0 )
 769                     ++nErrors;
 770                 if (  pRight && cmp( pNode->m_key, pRight->m_key ) > 0 )
 771                     ++nErrors;
 772
 773                 size_t hLeft = do_check_consistency( pLeft, nLevel + 1, f, nErrors );
 774                 size_t hRight = do_check_consistency( pRight, nLevel + 1, f, nErrors );
 775
 776                 if ( hLeft >= hRight ) {
 777                     if ( hLeft - hRight > 1 ) {
 778                         f( nLevel, hLeft, hRight );
 779                         ++nErrors;
 780                     }
 781                     return hLeft;
 782                 }
 783                 else {
 784                     if ( hRight - hLeft > 1 ) {
 785                         f( nLevel, hLeft, hRight );
 786                         ++nErrors;
 787                     }
 788                     return hRight;
 789                 }
 790             }
 791             return 0;
 792         }
 793
 794         template <typename Q, typename Compare, typename Func>
 795         bool do_find( Q& key, Compare cmp, Func f ) const
 796         {
 797             find_result result;
 798             {
 799                 rcu_lock l;
 800                 result = try_find( key, cmp, f, m_pRoot, right_child, 0 );
 801             }
 802             assert( result != find_result::retry );
 803             return result == find_result::found;
 804         }
 805
 806         template <typename K, typename Compare, typename Func>
 807         int do_update( K const& key, Compare cmp, Func funcUpdate, int nFlags )
 808         {
 809             check_deadlock_policy::check();
 810
 811             rcu_disposer removed_list;
 812             {
 813                 rcu_lock l;
 814                 return try_update_root( key, cmp, nFlags, funcUpdate, removed_list );
 815             }
 816         }
 817
 818         template <typename K, typename Compare, typename Func>
 819         bool do_remove( K const& key, Compare cmp, Func func )
 820         {
 821             // Func must return true if the value was disposed
 822             //              or false if the value was extracted
 823
 824             check_deadlock_policy::check();
 825
 826             rcu_disposer removed_list;
 827             {
 828                 rcu_lock l;
 829                 return try_remove_root( key, cmp, func, removed_list );
 830             }
 831         }
 832
 833         template <typename Func>
 834         mapped_type do_extract_min( Func f )
 835         {
 836             mapped_type pExtracted = nullptr;
 837             do_extract_minmax(
 838                 left_child,
 839                 [&pExtracted, &f]( key_type const& key, mapped_type pVal, rcu_disposer& ) -> bool { f( key ); pExtracted = pVal; return false; }
 840             );
 841             return pExtracted;
 842         }
 843
 844         template <typename Func>
 845         mapped_type do_extract_max( Func f )
 846         {
 847             mapped_type pExtracted = nullptr;
 848             do_extract_minmax(
 849                 right_child,
 850                 [&pExtracted, &f]( key_type const& key, mapped_type pVal, rcu_disposer& ) -> bool { f( key ); pExtracted = pVal; return false; }
 851             );
 852             return pExtracted;
 853         }
 854
 855         template <typename Func>
 856         void do_extract_minmax( int nDir, Func func )
 857         {
 858             check_deadlock_policy::check();
 859
 860             rcu_disposer removed_list;
 861             {
 862                 rcu_lock l;
 863
 864                 while ( true ) {
 865                     int result;
 866
 867                     // get right child of root
 868                     node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
 869                     if ( pChild ) {
 870                         version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
 871                         if ( nChildVersion & node_type::shrinking ) {
 872                             m_stat.onRemoveRootWaitShrinking();
 873                             pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
 874                             result = update_flags::retry;
 875                         }
 876                         else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
 877                             result = try_extract_minmax( nDir, func, m_pRoot, pChild, nChildVersion, removed_list );
 878                         }
 879                         else
 880                             result = update_flags::retry;
 881                     }
 882                     else
 883                         return;
 884
 885                     if ( result == update_flags::retry )
 886                         m_stat.onRemoveRetry();
 887                     else {
 888                         m_stat.onExtract( result == update_flags::result_removed );
 889                         return;
 890                     }
 891                 }
 892             }
 893         }
 894
 895         template <typename Q>
 896         mapped_type do_extract( Q const& key )
 897         {
 898             mapped_type pExtracted = nullptr;
 899             do_remove(
 900                 key,
 901                 key_comparator(),
 902                 [&pExtracted]( key_type const&, mapped_type pVal, rcu_disposer& ) -> bool { pExtracted = pVal; return false; }
 903             );
 904             m_stat.onExtract( pExtracted != nullptr );
 905             return pExtracted;
 906         }
 907
 908         template <typename Q, typename Less>
 909         mapped_type do_extract_with( Q const& key, Less pred )
 910         {
 911             CDS_UNUSED( pred );
 912             mapped_type pExtracted = nullptr;
 913             do_remove(
 914                 key,
 915                 cds::opt::details::make_comparator_from_less<Less>(),
 916                 [&pExtracted]( key_type const&, mapped_type pVal, rcu_disposer& ) -> bool { pExtracted = pVal; return false; }
 917             );
 918             m_stat.onExtract( pExtracted != nullptr );
 919             return pExtracted;
 920         }
 921         //@endcond
 922
 923     private:
 924         //@cond
 925         static int height( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
 926         {
 927             assert( pNode );
 928             return pNode->m_nHeight.load( order );
 929         }
 930         static void set_height( node_type * pNode, int h, atomics::memory_order order = memory_model::memory_order_relaxed )
 931         {
 932             assert( pNode );
 933             pNode->m_nHeight.store( h, order );
 934         }
 935         static int height_null( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
 936         {
 937             return pNode ? height( pNode, order ) : 0;
 938         }
 939
 940         static CDS_CONSTEXPR int const c_stackSize = 64;
 941
 942         template <typename Q, typename Compare, typename Func>
 943         find_result try_find( Q const& key, Compare cmp, Func f, node_type * pNode, int nDir, version_type nVersion ) const
 944         {
 945             assert( gc::is_locked() );
 946             assert( pNode );
 947
 948             struct stack_record
 949             {
 950                 node_type * pNode;
 951                 version_type nVersion;
 952                 int nDir;
 953             };
 954
 955             stack_record stack[c_stackSize];
 956             int pos = 0;
 957             stack[0].pNode = pNode;
 958             stack[0].nVersion = nVersion;
 959             stack[0].nDir = nDir;
 960
 961             while ( pos >= 0 ) {
 962                 pNode = stack[pos].pNode;
 963                 nVersion = stack[pos].nVersion;
 964                 nDir = stack[pos].nDir;
 965
 966                 while ( true ) {
 967                     node_type * pChild = child( pNode, nDir );
 968                     if ( !pChild ) {
 969                         if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
 970                             --pos;
 971                             m_stat.onFindRetry();
 972                             break; // retry
 973                         }
 974                         m_stat.onFindFailed();
 975                         return find_result::not_found;
 976                     }
 977
 978                     int nCmp = cmp( key, pChild->m_key );
 979                     if ( nCmp == 0 ) {
 980                         if ( pChild->is_valued( memory_model::memory_order_relaxed ) ) {
 981                             // key found
 982                             node_scoped_lock l( m_Monitor, *pChild );
 983                             if ( child(pNode, nDir) == pChild ) {
 984                                 if ( pChild->is_valued( memory_model::memory_order_relaxed )) {
 985                                     if ( f( pChild ) ) {
 986                                         m_stat.onFindSuccess();
 987                                         return find_result::found;
 988                                     }
 989                                 }
 990                             }
 991                             else {
 992                                 m_stat.onFindRetry();
 993                                 continue;
 994                             }
 995                         }
 996                         m_stat.onFindFailed();
 997                         return find_result::not_found;
 998                     }
 999                     else {
1000                         version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1001                         if ( nChildVersion & node_type::shrinking ) {
1002                             m_stat.onFindWaitShrinking();
1003                             pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1004
1005                             if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1006                                 --pos;
1007                                 m_stat.onFindRetry();
1008                                 break; // retry
1009                             }
1010                         }
1011                         else if ( nChildVersion != node_type::unlinked && child( pNode, nDir ) == pChild )
1012                         {
1013                             if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1014                                 --pos;
1015                                 m_stat.onFindRetry();
1016                                 break; // retry
1017                             }
1018
1019                             ++pos;
1020                             assert(pos < c_stackSize);
1021                             stack[pos].pNode = pChild;
1022                             stack[pos].nVersion = nChildVersion;
1023                             stack[pos].nDir = nCmp;
1024                             break; // child iteration
1025                         }
1026
1027                         if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1028                             --pos;
1029                             m_stat.onFindRetry();
1030                             break; // retry
1031                         }
1032                     }
1033                     m_stat.onFindRetry();
1034                 }
1035             }
1036             return find_result::retry;
1037         }
1038
1039 #if 0
1040         template <typename Q, typename Compare, typename Func>
1041         find_result try_find( Q const& key, Compare cmp, Func f, node_type * pNode, int nDir, version_type nVersion ) const
1042         {
1043             assert( gc::is_locked() );
1044             assert( pNode );
1045
1046             while ( true ) {
1047                 node_type * pChild = child( pNode, nDir );
1048                 if ( !pChild ) {
1049                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1050                         return find_result::retry;
1051
1052                     m_stat.onFindFailed();
1053                     return find_result::not_found;
1054                 }
1055
1056                 int nCmp = cmp( key, pChild->m_key );
1057                 if ( nCmp == 0 ) {
1058                     if ( pChild->is_valued( memory_model::memory_order_relaxed ) ) {
1059                         // key found
1060                         node_scoped_lock l( m_Monitor, *pChild );
1061                         if ( pChild->is_valued( memory_model::memory_order_relaxed )) {
1062                             if ( f( pChild ) ) {
1063                                 m_stat.onFindSuccess();
1064                                 return find_result::found;
1065                             }
1066                         }
1067                     }
1068
1069                     m_stat.onFindFailed();
1070                     return find_result::not_found;
1071                 }
1072
1073                 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1074                 if ( nChildVersion & node_type::shrinking ) {
1075                     m_stat.onFindWaitShrinking();
1076                     pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1077
1078                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1079                         return find_result::retry;
1080                 }
1081                 else if ( nChildVersion != node_type::unlinked && child( pNode, nDir ) == pChild )
1082                 {
1083                     if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
1084                         return find_result::retry;
1085
1086                     find_result found = try_find( key, cmp, f, pChild, nCmp, nChildVersion );
1087                     if ( found != find_result::retry )
1088                         return found;
1089                 }
1090
1091                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1092                     return find_result::retry;
1093
1094                 m_stat.onFindRetry();
1095             }
1096         }
1097 #endif
1098
1099         template <typename K, typename Compare, typename Func>
1100         int try_update_root( K const& key, Compare cmp, int nFlags, Func funcUpdate, rcu_disposer& disp )
1101         {
1102             assert( gc::is_locked() );
1103
1104             while ( true ) {
1105                 int result;
1106
1107                 // get right child of root
1108                 node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
1109                 if ( pChild ) {
1110                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1111                     if ( nChildVersion & node_type::shrinking ) {
1112                         m_stat.onUpdateRootWaitShrinking();
1113                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1114                         result = update_flags::retry;
1115                     }
1116                     else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire ))
1117                         result = try_update( key, cmp, nFlags, funcUpdate, pChild, nChildVersion, disp );
1118                     else
1119                         result = update_flags::retry;
1120                 }
1121                 else {
1122                     // the tree is empty
1123                     if ( nFlags & update_flags::allow_insert ) {
1124                         // insert into tree as right child of the root
1125                         {
1126                             node_scoped_lock l( m_Monitor, *m_pRoot );
1127                             if ( child( m_pRoot, right_child, memory_model::memory_order_acquire ) != nullptr ) {
1128                                 result = update_flags::retry;
1129                                 continue;
1130                             }
1131
1132                             node_type * pNew = alloc_node( key, 1, 0, m_pRoot, nullptr, nullptr );
1133                             mapped_type pVal = funcUpdate( pNew );
1134                             assert( pVal != nullptr );
1135                             pNew->m_pValue.store( pVal, memory_model::memory_order_release );
1136
1137                             m_pRoot->child( pNew, right_child, memory_model::memory_order_relaxed );
1138                             set_height( m_pRoot, 2 );
1139                         }
1140
1141                         ++m_ItemCounter;
1142                         m_stat.onInsertSuccess();
1143                         return update_flags::result_inserted;
1144                     }
1145
1146                     return update_flags::failed;
1147                 }
1148
1149                 if ( result != update_flags::retry )
1150                     return result;
1151             }
1152         }
1153
1154         template <typename K, typename Compare, typename Func>
1155         bool try_remove_root( K const& key, Compare cmp, Func func, rcu_disposer& disp )
1156         {
1157             assert( gc::is_locked() );
1158
1159             while ( true ) {
1160                 int result;
1161
1162                 // get right child of root
1163                 node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
1164                 if ( pChild ) {
1165                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1166                     if ( nChildVersion & node_type::shrinking ) {
1167                         m_stat.onRemoveRootWaitShrinking();
1168                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1169                         result = update_flags::retry;
1170                     }
1171                     else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
1172                         result = try_remove( key, cmp, func, m_pRoot, pChild, nChildVersion, disp );
1173                     }
1174                     else
1175                         result = update_flags::retry;
1176                 }
1177                 else
1178                     return false;
1179
1180                 if ( result == update_flags::retry )
1181                     m_stat.onRemoveRetry();
1182                 else {
1183                     m_stat.onRemove( result == update_flags::result_removed );
1184                     return result == update_flags::result_removed;
1185                 }
1186             }
1187         }
1188
1189         template <typename K, typename Compare, typename Func>
1190         int try_update( K const& key, Compare cmp, int nFlags, Func funcUpdate, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1191         {
1192             assert( gc::is_locked() );
1193             assert( nVersion != node_type::unlinked );
1194
1195             struct stack_record
1196             {
1197                 node_type * pNode;
1198                 version_type nVersion;
1199             };
1200
1201             stack_record stack[c_stackSize];
1202             int pos = 0;
1203             stack[0].pNode = pNode;
1204             stack[0].nVersion = nVersion;
1205
1206             while ( pos >= 0 ) {
1207                 pNode = stack[pos].pNode;
1208                 nVersion = stack[pos].nVersion;
1209
1210                 int nCmp = cmp( key, pNode->m_key );
1211                 if ( nCmp == 0 ) {
1212                     int result = try_update_node( nFlags, funcUpdate, pNode, nVersion, disp );
1213                     if ( result != update_flags::retry )
1214                         return result;
1215                     --pos;
1216                     m_stat.onUpdateRetry();
1217                     continue;
1218                 }
1219
1220                 while ( true ) {
1221                     node_type * pChild = child( pNode, nCmp );
1222                     if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1223                         --pos;
1224                         m_stat.onUpdateRetry();
1225                         break;
1226                     }
1227
1228                     if ( pChild == nullptr ) {
1229                         // insert new node
1230                         if ( nFlags & update_flags::allow_insert ) {
1231                             int result = try_insert_node( key, funcUpdate, pNode, nCmp, nVersion, disp );
1232                             if ( result != update_flags::retry )
1233                                 return result;
1234                             --pos;
1235                             m_stat.onUpdateRetry();
1236                             break;
1237                         }
1238                         else
1239                             return update_flags::failed;
1240                     }
1241                     else {
1242                         // update child
1243                         version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1244                         if ( nChildVersion & node_type::shrinking ) {
1245                             m_stat.onUpdateWaitShrinking();
1246                             pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1247                             // retry
1248                         }
1249                         else if ( pChild == child( pNode, nCmp )) {
1250                             // this second read is important, because it is protected by nChildVersion
1251
1252                             // validate the read that our caller took to get to node
1253                             if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
1254                                 --pos;
1255                                 m_stat.onUpdateRetry();
1256                                 break; // retry
1257                             }
1258                             // At this point we know that the traversal our parent took to get to node is still valid.
1259                             // The recursive implementation will validate the traversal from node to
1260                             // child, so just prior to the node nVersion validation both traversals were definitely okay.
1261                             // This means that we are no longer vulnerable to node shrinks, and we don't need
1262                             // to validate node version any more.
1263                             ++pos;
1264                             assert( pos < c_stackSize );
1265                             stack[pos].pNode = pChild;
1266                             stack[pos].nVersion = nChildVersion;
1267                             assert( nChildVersion != node_type::unlinked );
1268                             break; // child iteration
1269                         }
1270                         m_stat.onUpdateRetry();
1271                     }
1272                 }
1273             }
1274             return update_flags::retry;
1275         }
1276
1277 #if 0
1278         template <typename K, typename Compare, typename Func>
1279         int try_update( K const& key, Compare cmp, int nFlags, Func funcUpdate, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1280         {
1281             assert( gc::is_locked() );
1282             assert( nVersion != node_type::unlinked );
1283
1284             int nCmp = cmp( key, pNode->m_key );
1285             if ( nCmp == 0 )
1286                 return try_update_node( nFlags, funcUpdate, pNode, nVersion, disp );
1287
1288             while ( true ) {
1289                 int result;
1290                 node_type * pChild = child( pNode, nCmp );
1291                 if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
1292                     return update_flags::retry;
1293
1294                 if ( pChild == nullptr ) {
1295                     // insert new node
1296                     if ( nFlags & update_flags::allow_insert )
1297                         result = try_insert_node( key, funcUpdate, pNode, nCmp, nVersion, disp );
1298                     else
1299                         result = update_flags::failed;
1300                 }
1301                 else {
1302                     // update child
1303                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1304                     if ( nChildVersion & node_type::shrinking ) {
1305                         m_stat.onUpdateWaitShrinking();
1306                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1307                         // retry
1308                         result = update_flags::retry;
1309                     }
1310                     else if ( pChild == child( pNode, nCmp )) {
1311                         // this second read is important, because it is protected by nChildVersion
1312
1313                         // validate the read that our caller took to get to node
1314                         if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1315                             return update_flags::retry;
1316
1317                         // At this point we know that the traversal our parent took to get to node is still valid.
1318                         // The recursive implementation will validate the traversal from node to
1319                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
1320                         // This means that we are no longer vulnerable to node shrinks, and we don't need
1321                         // to validate node version any more.
1322                         result = try_update( key, cmp, nFlags, funcUpdate, pChild, nChildVersion, disp );
1323                     }
1324                     else
1325                         result = update_flags::retry;
1326                 }
1327
1328                 if ( result == update_flags::retry ) {
1329                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1330                         return update_flags::retry;
1331                     m_stat.onUpdateRetry();
1332                 }
1333                 else
1334                     return result;
1335             }
1336         }
1337 #endif
1338
1339         template <typename K, typename Compare, typename Func>
1340         int try_remove( K const& key, Compare cmp, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1341         {
1342             assert( gc::is_locked() );
1343             assert( nVersion != node_type::unlinked );
1344
1345             struct stack_record
1346             {
1347                 node_type * pParent;
1348                 node_type * pNode;
1349                 version_type nVersion;
1350             };
1351
1352             stack_record stack[c_stackSize];
1353             int pos = 0;
1354             stack[0].pParent = pParent;
1355             stack[0].pNode = pNode;
1356             stack[0].nVersion = nVersion;
1357
1358             while ( pos >= 0 ) {
1359                 pParent = stack[pos].pParent;
1360                 pNode = stack[pos].pNode;
1361                 nVersion = stack[pos].nVersion;
1362
1363                 int nCmp = cmp( key, pNode->m_key );
1364                 if ( nCmp == 0 ) {
1365                     int result = try_remove_node( pParent, pNode, nVersion, func, disp );
1366                     if ( result != update_flags::retry )
1367                         return result;
1368                     --pos;
1369                     m_stat.onRemoveRetry();
1370                     continue;
1371                 }
1372
1373                 while ( true ) {
1374                     node_type * pChild = child( pNode, nCmp );
1375                     if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1376                         --pos;
1377                         m_stat.onRemoveRetry();
1378                         break;
1379                     }
1380
1381                     if ( pChild == nullptr )
1382                         return update_flags::failed;
1383
1384                     // update child
1385                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1386                     if ( nChildVersion & node_type::shrinking ) {
1387                         m_stat.onRemoveWaitShrinking();
1388                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1389                         // retry
1390                     }
1391                     else if ( pChild == child( pNode, nCmp )) {
1392                         // this second read is important, because it is protected by nChildVersion
1393
1394                         // validate the read that our caller took to get to node
1395                         if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1396                             --pos;
1397                             m_stat.onRemoveRetry();
1398                             break;
1399                         }
1400
1401                         // At this point we know that the traversal our parent took to get to node is still valid.
1402                         // The recursive implementation will validate the traversal from node to
1403                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
1404                         // This means that we are no longer vulnerable to node shrinks, and we don't need
1405                         // to validate node version any more.
1406                         ++pos;
1407                         assert( pos < c_stackSize );
1408                         stack[pos].pParent = pNode;
1409                         stack[pos].pNode = pChild;
1410                         stack[pos].nVersion = nChildVersion;
1411                         break; // child iteration
1412                     }
1413                     m_stat.onRemoveRetry();
1414                 }
1415             }
1416             return update_flags::retry;
1417         }
1418
1419 #if 0
1420         template <typename K, typename Compare, typename Func>
1421         int try_remove( K const& key, Compare cmp, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1422         {
1423             assert( gc::is_locked() );
1424             assert( nVersion != node_type::unlinked );
1425
1426             int nCmp = cmp( key, pNode->m_key );
1427             if ( nCmp == 0 )
1428                 return try_remove_node( pParent, pNode, nVersion, func, disp );
1429
1430             while ( true ) {
1431                 int result;
1432
1433                 node_type * pChild = child( pNode, nCmp );
1434                 if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
1435                     return update_flags::retry;
1436
1437                 if ( pChild == nullptr )
1438                     return update_flags::failed;
1439                 else {
1440                     // update child
1441                     result = update_flags::retry;
1442                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1443                     if ( nChildVersion & node_type::shrinking ) {
1444                         m_stat.onRemoveWaitShrinking();
1445                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1446                         // retry
1447                     }
1448                     else if ( pChild == child( pNode, nCmp )) {
1449                         // this second read is important, because it is protected by nChildVersion
1450
1451                         // validate the read that our caller took to get to node
1452                         if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1453                             return update_flags::retry;
1454
1455                         // At this point we know that the traversal our parent took to get to node is still valid.
1456                         // The recursive implementation will validate the traversal from node to
1457                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
1458                         // This means that we are no longer vulnerable to node shrinks, and we don't need
1459                         // to validate node version any more.
1460                         result = try_remove( key, cmp, func, pNode, pChild, nChildVersion, disp );
1461                     }
1462                     else
1463                         result = update_flags::retry;
1464                 }
1465
1466                 if ( result == update_flags::retry ) {
1467                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1468                         return update_flags::retry;
1469                     m_stat.onRemoveRetry();
1470                 }
1471                 else
1472                     return result;
1473             }
1474         }
1475 #endif
1476
1477         template <typename Func>
1478         int try_extract_minmax( int nDir, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1479         {
1480             assert( gc::is_locked() );
1481             assert( nVersion != node_type::unlinked );
1482
1483             struct stack_record
1484             {
1485                 node_type * pParent;
1486                 node_type * pNode;
1487                 version_type nVersion;
1488             };
1489
1490             stack_record stack[c_stackSize];
1491             int pos = 0;
1492             stack[0].pParent = pParent;
1493             stack[0].pNode = pNode;
1494             stack[0].nVersion = nVersion;
1495
1496             while ( pos >= 0 ) {
1497                 pParent = stack[pos].pParent;
1498                 pNode = stack[pos].pNode;
1499                 nVersion = stack[pos].nVersion;
1500
1501                 while ( true ) {
1502                     node_type * pChild = child( pNode, nDir );
1503                     if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1504                         --pos;
1505                         m_stat.onRemoveRetry();
1506                         break;
1507                     }
1508
1509                     if ( pChild == nullptr ) {
1510                         // Found min/max
1511                         assert(pNode->is_valued( memory_model::memory_order_relaxed ));
1512                         int result = try_remove_node( pParent, pNode, nVersion, func, disp );
1513                         if ( result != update_flags::retry )
1514                             return result;
1515                         --pos;
1516                         m_stat.onRemoveRetry();
1517                         break;
1518                     }
1519
1520                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1521                     if ( nChildVersion & node_type::shrinking ) {
1522                         m_stat.onRemoveWaitShrinking();
1523                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1524                         // retry
1525                     }
1526                     else if ( pChild == child( pNode, nDir )) {
1527                         // this second read is important, because it is protected by nChildVersion
1528
1529                         // validate the read that our caller took to get to node
1530                         if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
1531                             --pos;
1532                             m_stat.onRemoveRetry();
1533                             break;
1534                         }
1535
1536                         // At this point we know that the traversal our parent took to get to node is still valid.
1537                         // The recursive implementation will validate the traversal from node to
1538                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
1539                         // This means that we are no longer vulnerable to node shrinks, and we don't need
1540                         // to validate node version any more.
1541                         ++pos;
1542                         assert( pos < c_stackSize );
1543                         stack[pos].pParent = pNode;
1544                         stack[pos].pNode = pChild;
1545                         stack[pos].nVersion = nChildVersion;
1546                         break; // child iteration
1547                     }
1548                     m_stat.onRemoveRetry();
1549                 }
1550             }
1551             return update_flags::retry;
1552         }
1553
1554 #if 0
1555         template <typename Func>
1556         int try_extract_minmax( int nDir, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1557         {
1558             assert( gc::is_locked() );
1559             assert( nVersion != node_type::unlinked );
1560
1561             while ( true ) {
1562                 int result;
1563                 node_type * pChild = child( pNode, nDir );
1564                 if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
1565                     return update_flags::retry;
1566
1567                 if ( pChild == nullptr ) {
1568                     // Found min/max
1569                     assert(pNode->is_valued( memory_model::memory_order_relaxed ));
1570                     return try_remove_node( pParent, pNode, nVersion, func, disp );
1571                 }
1572                 else {
1573                     //result = update_flags::retry;
1574                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1575                     if ( nChildVersion & node_type::shrinking ) {
1576                         m_stat.onRemoveWaitShrinking();
1577                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1578                         // retry
1579                         result = update_flags::retry;
1580                     }
1581                     else if ( pChild == child( pNode, nDir )) {
1582                         // this second read is important, because it is protected by nChildVersion
1583
1584                         // validate the read that our caller took to get to node
1585                         if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1586                             return update_flags::retry;
1587
1588                         // At this point we know that the traversal our parent took to get to node is still valid.
1589                         // The recursive implementation will validate the traversal from node to
1590                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
1591                         // This means that we are no longer vulnerable to node shrinks, and we don't need
1592                         // to validate node version any more.
1593                         result = try_extract_minmax( nDir, func, pNode, pChild, nChildVersion, disp );
1594                     }
1595                     else
1596                         result = update_flags::retry;
1597                 }
1598
1599                 if ( result == update_flags::retry ) {
1600                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1601                         return update_flags::retry;
1602                     m_stat.onRemoveRetry();
1603                 }
1604                 else
1605                     return result;
1606             }
1607         }
1608 #endif
1609
1610         template <typename K, typename Func>
1611         int try_insert_node( K const& key, Func funcUpdate, node_type * pNode, int nDir, version_type nVersion, rcu_disposer& disp )
1612         {
1613             node_type * pNew;
1614
1615             auto fnCreateNode = [&funcUpdate]( node_type * pNew ) {
1616                 mapped_type pVal = funcUpdate( pNew );
1617                 assert( pVal != nullptr );
1618                 pNew->m_pValue.store( pVal, memory_model::memory_order_relaxed );
1619             };
1620
1621             if ( c_bRelaxedInsert ) {
1622                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
1623                      || child( pNode, nDir ) != nullptr )
1624                 {
1625                     m_stat.onInsertRetry();
1626                     return update_flags::retry;
1627                 }
1628
1629                 fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
1630             }
1631
1632             node_type * pDamaged;
1633             {
1634                 assert( pNode != nullptr );
1635                 node_scoped_lock l( m_Monitor, *pNode );
1636
1637                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
1638                      || child( pNode, nDir ) != nullptr )
1639                 {
1640                     if ( c_bRelaxedInsert ) {
1641                         mapped_type pVal = pNew->m_pValue.load( memory_model::memory_order_relaxed );
1642                         pNew->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
1643                         free_value( pVal );
1644                         free_node( pNew );
1645                         m_stat.onRelaxedInsertFailed();
1646                     }
1647
1648                     m_stat.onInsertRetry();
1649                     return update_flags::retry;
1650                 }
1651
1652                 if ( !c_bRelaxedInsert )
1653                     fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
1654
1655                 pNode->child( pNew, nDir, memory_model::memory_order_relaxed );
1656                 pDamaged = fix_height_locked( pNode );
1657             }
1658
1659             ++m_ItemCounter;
1660             m_stat.onInsertSuccess();
1661
1662             if ( pDamaged ) {
1663                 fix_height_and_rebalance( pDamaged, disp );
1664                 m_stat.onInsertRebalanceRequired();
1665             }
1666
1667             return update_flags::result_inserted;
1668         }
1669
1670         template <typename Func>
1671         int try_update_node( int nFlags, Func funcUpdate, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1672         {
1673             mapped_type pOld;
1674             bool bInserted;
1675             assert( pNode != nullptr );
1676             {
1677                 node_scoped_lock l( m_Monitor, *pNode );
1678
1679                 if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
1680                     return update_flags::retry;
1681
1682                 if ( pNode->is_unlinked( memory_model::memory_order_relaxed )) {
1683                     m_stat.onUpdateUnlinked();
1684                     return update_flags::retry;
1685                 }
1686
1687                 if ( pNode->is_valued( memory_model::memory_order_relaxed ) && !(nFlags & update_flags::allow_update) ) {
1688                     m_stat.onInsertFailed();
1689                     return update_flags::failed;
1690                 }
1691
1692                 pOld = pNode->value( memory_model::memory_order_relaxed );
1693                 bInserted = pOld == nullptr;
1694                 mapped_type pVal = funcUpdate( pNode );
1695                 if ( pVal == pOld )
1696                     pOld = nullptr;
1697                 else {
1698                     assert( pVal != nullptr );
1699                     pNode->m_pValue.store( pVal, memory_model::memory_order_relaxed );
1700                 }
1701             }
1702
1703             if ( pOld ) {
1704                 disp.dispose_value(pOld);
1705                 m_stat.onDisposeValue();
1706             }
1707
1708             if ( bInserted ) {
1709                 m_stat.onInsertSuccess();
1710                 return update_flags::result_inserted;
1711             }
1712
1713             m_stat.onUpdateSuccess();
1714             return update_flags::result_updated;
1715         }
1716
1717         template <typename Func>
1718         int try_remove_node( node_type * pParent, node_type * pNode, version_type nVersion, Func func, rcu_disposer& disp )
1719         {
1720             assert( pParent != nullptr );
1721             assert( pNode != nullptr );
1722
1723             if ( !pNode->is_valued( memory_model::memory_order_relaxed ) )
1724                 return update_flags::failed;
1725
1726             if ( child( pNode, left_child ) == nullptr || child( pNode, right_child ) == nullptr ) {
1727                 // pNode can be replaced with its child
1728
1729                 node_type * pDamaged;
1730                 mapped_type pOld;
1731                 {
1732                     node_scoped_lock lp( m_Monitor, *pParent );
1733                     if ( pParent->is_unlinked( memory_model::memory_order_relaxed ) || parent( pNode ) != pParent )
1734                         return update_flags::retry;
1735
1736                     {
1737                         node_scoped_lock ln( m_Monitor, *pNode );
1738                         if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1739                             return update_flags::retry;
1740
1741                         pOld = pNode->value( memory_model::memory_order_relaxed );
1742                         if ( !pOld )
1743                             return update_flags::failed;
1744
1745                         if ( !try_unlink_locked( pParent, pNode, disp ))
1746                             return update_flags::retry;
1747                     }
1748                     pDamaged = fix_height_locked( pParent );
1749                 }
1750
1751                 --m_ItemCounter;
1752                 if ( func( pNode->m_key, pOld, disp ))   // calls pOld disposer inside
1753                     m_stat.onDisposeValue();
1754                 else
1755                     m_stat.onExtractValue();
1756
1757                 if ( pDamaged ) {
1758                     fix_height_and_rebalance( pDamaged, disp );
1759                     m_stat.onRemoveRebalanceRequired();
1760                 }
1761             }
1762             else {
1763                 // pNode is an internal with two children
1764
1765                 mapped_type pOld;
1766                 {
1767                     node_scoped_lock ln( m_Monitor, *pNode );
1768                     pOld = pNode->value( memory_model::memory_order_relaxed );
1769                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1770                         return update_flags::retry;
1771                     if ( !pOld )
1772                         return update_flags::failed;
1773
1774                     pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
1775                     m_stat.onMakeRoutingNode();
1776                 }
1777
1778                 --m_ItemCounter;
1779                 if ( func( pNode->m_key, pOld, disp ))  // calls pOld disposer inside
1780                     m_stat.onDisposeValue();
1781                 else
1782                     m_stat.onExtractValue();
1783             }
1784             return update_flags::result_removed;
1785         }
1786
1787         bool try_unlink_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp )
1788         {
1789             // pParent and pNode must be locked
1790             assert( !pParent->is_unlinked(memory_model::memory_order_relaxed) );
1791
1792             node_type * pParentLeft = child( pParent, left_child );
1793             node_type * pParentRight = child( pParent, right_child );
1794             if ( pNode != pParentLeft && pNode != pParentRight ) {
1795                 // node is no longer a child of parent
1796                 return false;
1797             }
1798
1799             assert( !pNode->is_unlinked( memory_model::memory_order_relaxed ));
1800             assert( pParent == parent( pNode ));
1801
1802             node_type * pLeft = child( pNode, left_child );
1803             node_type * pRight = child( pNode, right_child );
1804             if ( pLeft != nullptr && pRight != nullptr ) {
1805                 // splicing is no longer possible
1806                 return false;
1807             }
1808             node_type * pSplice = pLeft ? pLeft : pRight;
1809
1810             if ( pParentLeft == pNode )
1811                 pParent->m_pLeft.store( pSplice, memory_model::memory_order_relaxed );
1812             else
1813                 pParent->m_pRight.store( pSplice, memory_model::memory_order_relaxed );
1814
1815             if ( pSplice )
1816                 pSplice->parent( pParent, memory_model::memory_order_relaxed );
1817
1818             // Mark the node as unlinked
1819             pNode->version( node_type::unlinked, memory_model::memory_order_release );
1820
1821             // The value will be disposed by calling function
1822             pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
1823
1824             disp.dispose( pNode );
1825             m_stat.onDisposeNode();
1826
1827             return true;
1828         }
1829
1830         //@endcond
1831
1832     private: // rotations
1833         //@cond
1834         int estimate_node_condition( node_type * pNode )
1835         {
1836             node_type * pLeft = child( pNode, left_child );
1837             node_type * pRight = child( pNode, right_child );
1838
1839             if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_relaxed ))
1840                 return unlink_required;
1841
1842             int h = height( pNode );
1843             int hL = height_null( pLeft );
1844             int hR = height_null( pRight );
1845
1846             int hNew = 1 + std::max( hL, hR );
1847             int nBalance = hL - hR;
1848
1849             if ( nBalance < -1 || nBalance > 1 )
1850                 return rebalance_required;
1851
1852             return h != hNew ? hNew : nothing_required;
1853         }
1854
1855         node_type * fix_height( node_type * pNode )
1856         {
1857             assert( pNode != nullptr );
1858             node_scoped_lock l( m_Monitor, *pNode );
1859             return fix_height_locked( pNode );
1860         }
1861
1862         node_type * fix_height_locked( node_type * pNode )
1863         {
1864             // pNode must be locked!!!
1865             int h = estimate_node_condition( pNode );
1866             switch ( h ) {
1867                 case rebalance_required:
1868                 case unlink_required:
1869                     return pNode;
1870                 case nothing_required:
1871                     return nullptr;
1872                 default:
1873                     set_height( pNode, h );
1874                     return parent( pNode );
1875             }
1876         }
1877
1878         void fix_height_and_rebalance( node_type * pNode, rcu_disposer& disp )
1879         {
1880             while ( pNode && parent( pNode )) {
1881                 int nCond = estimate_node_condition( pNode );
1882                 if ( nCond == nothing_required || pNode->is_unlinked( memory_model::memory_order_relaxed ) )
1883                     return;
1884
1885                 if ( nCond != unlink_required && nCond != rebalance_required )
1886                     pNode = fix_height( pNode );
1887                 else {
1888                     node_type * pParent = parent( pNode );
1889                     assert( pParent != nullptr );
1890                     {
1891                         node_scoped_lock lp( m_Monitor, *pParent );
1892                         if ( !pParent->is_unlinked( memory_model::memory_order_relaxed ) && parent( pNode ) == pParent ) {
1893                             node_scoped_lock ln( m_Monitor, *pNode );
1894                             pNode = rebalance_locked( pParent, pNode, disp );
1895                         }
1896                     }
1897                 }
1898             }
1899         }
1900
1901         node_type * rebalance_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp )
1902         {
1903             // pParent and pNode should be locked.
1904             // Returns a damaged node, or nullptr if no more rebalancing is necessary
1905             assert( parent( pNode ) == pParent );
1906
1907             node_type * pLeft = child( pNode, left_child );
1908             node_type * pRight = child( pNode, right_child );
1909
1910             if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_relaxed )) {
1911                 if ( try_unlink_locked( pParent, pNode, disp ))
1912                     return fix_height_locked( pParent );
1913                 else {
1914                     // retry needed for pNode
1915                     return pNode;
1916                 }
1917             }
1918
1919             assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
1920
1921             int h = height( pNode );
1922             int hL = height_null( pLeft );
1923             int hR = height_null( pRight );
1924             int hNew = 1 + std::max( hL, hR );
1925             int balance = hL - hR;
1926
1927             if ( balance > 1 )
1928                 return rebalance_to_right_locked( pParent, pNode, pLeft, hR );
1929             else if ( balance < -1 )
1930                 return rebalance_to_left_locked( pParent, pNode, pRight, hL );
1931             else if ( hNew != h ) {
1932                 set_height( pNode, hNew );
1933
1934                 // pParent is already locked
1935                 return fix_height_locked( pParent );
1936             }
1937             else
1938                 return nullptr;
1939         }
1940
1941         node_type * rebalance_to_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR )
1942         {
1943             assert( parent( pNode ) == pParent );
1944             assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
1945
1946             // pParent and pNode is locked yet
1947             // pNode->pLeft is too large, we will rotate-right.
1948             // If pLeft->pRight is taller than pLeft->pLeft, then we will first rotate-left pLeft.
1949
1950             {
1951                 assert( pLeft != nullptr );
1952                 node_scoped_lock l( m_Monitor, *pLeft );
1953                 if ( pNode->m_pLeft.load( memory_model::memory_order_relaxed ) != pLeft )
1954                     return pNode; // retry for pNode
1955
1956                 int hL = height( pLeft );
1957                 if ( hL - hR <= 1 )
1958                     return pNode; // retry
1959
1960                 node_type * pLRight = child( pLeft, right_child );
1961                 int hLR = height_null( pLRight );
1962                 node_type * pLLeft = child( pLeft, left_child );
1963                 int hLL = height_null( pLLeft );
1964
1965                 if ( hLL > hLR ) {
1966                     // rotate right
1967                     return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
1968                 }
1969                 else {
1970                     assert( pLRight != nullptr );
1971                     {
1972                         node_scoped_lock lr( m_Monitor, *pLRight );
1973                         if ( pLeft->m_pRight.load( memory_model::memory_order_relaxed ) != pLRight )
1974                             return pNode; // retry
1975
1976                         hLR = height( pLRight );
1977                         if ( hLL > hLR )
1978                             return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
1979
1980                         int hLRL = height_null( child( pLRight, left_child ));
1981                         int balance = hLL - hLRL;
1982                         if ( balance >= -1 && balance <= 1 && !((hLL == 0 || hLRL == 0) && !pLeft->is_valued(memory_model::memory_order_relaxed))) {
1983                             // nParent.child.left won't be damaged after a double rotation
1984                             return rotate_right_over_left_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLRL );
1985                         }
1986                     }
1987
1988                     // focus on pLeft, if necessary pNode will be balanced later
1989                     return rebalance_to_left_locked( pNode, pLeft, pLRight, hLL );
1990                 }
1991             }
1992         }
1993
1994         node_type * rebalance_to_left_locked( node_type * pParent, node_type * pNode, node_type * pRight, int hL )
1995         {
1996             assert( parent( pNode ) == pParent );
1997             assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
1998
1999             // pParent and pNode is locked yet
2000             {
2001                 assert( pRight != nullptr );
2002                 node_scoped_lock l( m_Monitor, *pRight );
2003                 if ( pNode->m_pRight.load( memory_model::memory_order_relaxed ) != pRight )
2004                     return pNode; // retry for pNode
2005
2006                 int hR = height( pRight );
2007                 if ( hL - hR >= -1 )
2008                     return pNode; // retry
2009
2010                 node_type * pRLeft = child( pRight, left_child );
2011                 int hRL = height_null( pRLeft );
2012                 node_type * pRRight = child( pRight, right_child );
2013                 int hRR = height_null( pRRight );
2014                 if ( hRR > hRL )
2015                     return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
2016
2017                 {
2018                     assert( pRLeft != nullptr );
2019                     node_scoped_lock lrl( m_Monitor, *pRLeft );
2020                     if ( pRight->m_pLeft.load( memory_model::memory_order_relaxed ) != pRLeft )
2021                         return pNode; // retry
2022
2023                     hRL = height( pRLeft );
2024                     if ( hRR >= hRL )
2025                         return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
2026
2027                     node_type * pRLRight = child( pRLeft, right_child );
2028                     int hRLR = height_null( pRLRight );
2029                     int balance = hRR - hRLR;
2030                     if ( balance >= -1 && balance <= 1 && !((hRR == 0 || hRLR == 0) && !pRight->is_valued( memory_model::memory_order_relaxed )))
2031                          return rotate_left_over_right_locked( pParent, pNode, hL, pRight, pRLeft, hRR, hRLR );
2032                 }
2033                 return rebalance_to_right_locked( pNode, pRight, pRLeft, hRR );
2034             }
2035         }
2036
2037         static void begin_change( node_type * pNode, version_type version )
2038         {
2039             assert(pNode->version(memory_model::memory_order_acquire) == version );
2040             assert( (version & node_type::shrinking) == 0 );
2041             pNode->version( version | node_type::shrinking, memory_model::memory_order_release );
2042         }
2043         static void end_change( node_type * pNode, version_type version )
2044         {
2045             // Clear shrinking and unlinked flags and increment version
2046             pNode->version( (version | node_type::version_flags) + 1, memory_model::memory_order_release );
2047         }
2048
2049         node_type * rotate_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR, int hLL, node_type * pLRight, int hLR )
2050         {
2051             version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
2052             node_type * pParentLeft = child( pParent, left_child );
2053
2054             begin_change( pNode, nodeVersion );
2055
2056             pNode->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
2057             if ( pLRight != nullptr )
2058                 pLRight->parent( pNode, memory_model::memory_order_relaxed  );
2059
2060             atomics::atomic_thread_fence( memory_model::memory_order_release );
2061
2062             pLeft->m_pRight.store( pNode, memory_model::memory_order_relaxed );
2063             pNode->parent( pLeft, memory_model::memory_order_relaxed );
2064
2065             atomics::atomic_thread_fence( memory_model::memory_order_release );
2066
2067             if ( pParentLeft == pNode )
2068                 pParent->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
2069             else {
2070                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
2071                 pParent->m_pRight.store( pLeft, memory_model::memory_order_relaxed );
2072             }
2073             pLeft->parent( pParent, memory_model::memory_order_relaxed );
2074
2075             atomics::atomic_thread_fence( memory_model::memory_order_release );
2076
2077             // fix up heights links
2078             int hNode = 1 + std::max( hLR, hR );
2079             set_height( pNode, hNode );
2080             set_height( pLeft, 1 + std::max( hLL, hNode ));
2081
2082             end_change( pNode, nodeVersion );
2083             m_stat.onRotateRight();
2084
2085             // We have damaged pParent, pNode (now parent.child.right), and pLeft (now
2086             // parent.child).  pNode is the deepest.  Perform as many fixes as we can
2087             // with the locks we've got.
2088
2089             // We've already fixed the height for pNode, but it might still be outside
2090             // our allowable balance range.  In that case a simple fix_height_locked()
2091             // won't help.
2092             int nodeBalance = hLR - hR;
2093             if ( nodeBalance < -1 || nodeBalance > 1 ) {
2094                 // we need another rotation at pNode
2095                 m_stat.onRotateAfterRightRotation();
2096                 return pNode;
2097             }
2098
2099             // we've fixed balance and height damage for pNode, now handle
2100             // extra-routing node damage
2101             if ( (pLRight == nullptr || hR == 0) && !pNode->is_valued(memory_model::memory_order_relaxed)) {
2102                 // we need to remove pNode and then repair
2103                 m_stat.onRemoveAfterRightRotation();
2104                 return pNode;
2105             }
2106
2107             // we've already fixed the height at pLeft, do we need a rotation here?
2108             int leftBalance = hLL - hNode;
2109             if ( leftBalance < -1 || leftBalance > 1 ) {
2110                 m_stat.onRotateAfterRightRotation();
2111                 return pLeft;
2112             }
2113
2114             // pLeft might also have routing node damage (if pLeft.left was null)
2115             if ( hLL == 0 && !pLeft->is_valued(memory_model::memory_order_relaxed) ) {
2116                 m_stat.onDamageAfterRightRotation();
2117                 return pLeft;
2118             }
2119
2120             // try to fix the parent height while we've still got the lock
2121             return fix_height_locked( pParent );
2122         }
2123
2124         node_type * rotate_left_locked( node_type * pParent, node_type * pNode, int hL, node_type * pRight, node_type * pRLeft, int hRL, int hRR )
2125         {
2126             version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
2127             node_type * pParentLeft = child( pParent, left_child );
2128
2129             begin_change( pNode, nodeVersion );
2130
2131             // fix up pNode links, careful to be compatible with concurrent traversal for all but pNode
2132             pNode->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
2133             if ( pRLeft != nullptr )
2134                 pRLeft->parent( pNode, memory_model::memory_order_relaxed );
2135
2136             atomics::atomic_thread_fence( memory_model::memory_order_release );
2137
2138             pRight->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
2139             pNode->parent( pRight, memory_model::memory_order_relaxed );
2140
2141             atomics::atomic_thread_fence( memory_model::memory_order_release );
2142
2143             if ( pParentLeft == pNode )
2144                 pParent->m_pLeft.store( pRight, memory_model::memory_order_relaxed );
2145             else {
2146                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
2147                 pParent->m_pRight.store( pRight, memory_model::memory_order_relaxed );
2148             }
2149             pRight->parent( pParent, memory_model::memory_order_relaxed );
2150
2151             atomics::atomic_thread_fence( memory_model::memory_order_release );
2152
2153             // fix up heights
2154             int hNode = 1 + std::max( hL, hRL );
2155             set_height( pNode, hNode );
2156             set_height( pRight, 1 + std::max( hNode, hRR ));
2157
2158             end_change( pNode, nodeVersion );
2159             m_stat.onRotateLeft();
2160
2161             int nodeBalance = hRL - hL;
2162             if ( nodeBalance < -1 || nodeBalance > 1 ) {
2163                 m_stat.onRotateAfterLeftRotation();
2164                 return pNode;
2165             }
2166
2167             if ( (pRLeft == nullptr || hL == 0) && !pNode->is_valued(memory_model::memory_order_relaxed) ) {
2168                 m_stat.onRemoveAfterLeftRotation();
2169                 return pNode;
2170             }
2171
2172             int rightBalance = hRR - hNode;
2173             if ( rightBalance < -1 || rightBalance > 1 ) {
2174                 m_stat.onRotateAfterLeftRotation();
2175                 return pRight;
2176             }
2177
2178             if ( hRR == 0 && !pRight->is_valued(memory_model::memory_order_relaxed) ) {
2179                 m_stat.onDamageAfterLeftRotation();
2180                 return pRight;
2181             }
2182
2183             return fix_height_locked( pParent );
2184         }
2185
2186         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 )
2187         {
2188             version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
2189             version_type leftVersion = pLeft->version( memory_model::memory_order_acquire );
2190
2191             node_type * pPL = child( pParent, left_child );
2192             node_type * pLRL = child( pLRight, left_child );
2193             node_type * pLRR = child( pLRight, right_child );
2194             int hLRR = height_null( pLRR );
2195
2196             begin_change( pNode, nodeVersion );
2197             begin_change( pLeft, leftVersion );
2198
2199             // fix up pNode links, careful about the order!
2200             pNode->m_pLeft.store( pLRR, memory_model::memory_order_relaxed );
2201             if ( pLRR != nullptr )
2202                 pLRR->parent( pNode, memory_model::memory_order_relaxed );
2203             atomics::atomic_thread_fence( memory_model::memory_order_release );
2204
2205             pLeft->m_pRight.store( pLRL, memory_model::memory_order_relaxed );
2206             if ( pLRL != nullptr )
2207                 pLRL->parent( pLeft, memory_model::memory_order_relaxed );
2208             atomics::atomic_thread_fence( memory_model::memory_order_release );
2209
2210             pLRight->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
2211             pLeft->parent( pLRight, memory_model::memory_order_relaxed );
2212             atomics::atomic_thread_fence( memory_model::memory_order_release );
2213
2214             pLRight->m_pRight.store( pNode, memory_model::memory_order_relaxed );
2215             pNode->parent( pLRight, memory_model::memory_order_relaxed );
2216             atomics::atomic_thread_fence( memory_model::memory_order_release );
2217
2218             if ( pPL == pNode )
2219                 pParent->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
2220             else {
2221                 assert( child( pParent, right_child ) == pNode );
2222                 pParent->m_pRight.store( pLRight, memory_model::memory_order_relaxed );
2223             }
2224             pLRight->parent( pParent, memory_model::memory_order_relaxed );
2225             atomics::atomic_thread_fence( memory_model::memory_order_release );
2226
2227             // fix up heights
2228             int hNode = 1 + std::max( hLRR, hR );
2229             set_height( pNode, hNode );
2230             int hLeft = 1 + std::max( hLL, hLRL );
2231             set_height( pLeft, hLeft );
2232             set_height( pLRight, 1 + std::max( hLeft, hNode ));
2233
2234             end_change( pNode, nodeVersion );
2235             end_change( pLeft, leftVersion );
2236             m_stat.onRotateRightOverLeft();
2237
2238             // caller should have performed only a single rotation if pLeft was going
2239             // to end up damaged
2240             assert( hLL - hLRL <= 1 && hLRL - hLL <= 1 );
2241             assert( !((hLL == 0 || pLRL == nullptr) && !pLeft->is_valued( memory_model::memory_order_relaxed )));
2242
2243             // We have damaged pParent, pLR (now parent.child), and pNode (now
2244             // parent.child.right).  pNode is the deepest.  Perform as many fixes as we
2245             // can with the locks we've got.
2246
2247             // We've already fixed the height for pNode, but it might still be outside
2248             // our allowable balance range.  In that case a simple fix_height_locked()
2249             // won't help.
2250             int nodeBalance = hLRR - hR;
2251             if ( nodeBalance < -1 || nodeBalance > 1 ) {
2252                 // we need another rotation at pNode
2253                 m_stat.onRotateAfterRLRotation();
2254                 return pNode;
2255             }
2256
2257             // pNode might also be damaged by being an unnecessary routing node
2258             if ( (pLRR == nullptr || hR == 0) && !pNode->is_valued( memory_model::memory_order_relaxed )) {
2259                 // repair involves splicing out pNode and maybe more rotations
2260                 m_stat.onRemoveAfterRLRotation();
2261                 return pNode;
2262             }
2263
2264             // we've already fixed the height at pLRight, do we need a rotation here?
2265             int balanceLR = hLeft - hNode;
2266             if ( balanceLR < -1 || balanceLR > 1 ) {
2267                 m_stat.onRotateAfterRLRotation();
2268                 return pLRight;
2269             }
2270
2271             // try to fix the parent height while we've still got the lock
2272             return fix_height_locked( pParent );
2273         }
2274
2275         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 )
2276         {
2277             version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
2278             version_type rightVersion = pRight->version( memory_model::memory_order_acquire );
2279
2280             node_type * pPL = child( pParent, left_child );
2281             node_type * pRLL = child( pRLeft, left_child );
2282             node_type * pRLR = child( pRLeft, right_child );
2283             int hRLL = height_null( pRLL );
2284
2285             begin_change( pNode, nodeVersion );
2286             begin_change( pRight, rightVersion );
2287
2288             // fix up pNode links, careful about the order!
2289             pNode->m_pRight.store( pRLL, memory_model::memory_order_relaxed );
2290             if ( pRLL != nullptr )
2291                 pRLL->parent( pNode, memory_model::memory_order_relaxed );
2292             atomics::atomic_thread_fence( memory_model::memory_order_release );
2293
2294             pRight->m_pLeft.store( pRLR, memory_model::memory_order_relaxed );
2295             if ( pRLR != nullptr )
2296                 pRLR->parent( pRight, memory_model::memory_order_relaxed );
2297             atomics::atomic_thread_fence( memory_model::memory_order_release );
2298
2299             pRLeft->m_pRight.store( pRight, memory_model::memory_order_relaxed );
2300             pRight->parent( pRLeft, memory_model::memory_order_relaxed );
2301             atomics::atomic_thread_fence( memory_model::memory_order_release );
2302
2303             pRLeft->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
2304             pNode->parent( pRLeft, memory_model::memory_order_relaxed );
2305             atomics::atomic_thread_fence( memory_model::memory_order_release );
2306
2307             if ( pPL == pNode )
2308                 pParent->m_pLeft.store( pRLeft, memory_model::memory_order_relaxed );
2309             else {
2310                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
2311                 pParent->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
2312             }
2313             pRLeft->parent( pParent, memory_model::memory_order_relaxed );
2314             atomics::atomic_thread_fence( memory_model::memory_order_release );
2315
2316             // fix up heights
2317             int hNode = 1 + std::max( hL, hRLL );
2318             set_height( pNode, hNode );
2319             int hRight = 1 + std::max( hRLR, hRR );
2320             set_height( pRight, hRight );
2321             set_height( pRLeft, 1 + std::max( hNode, hRight ));
2322
2323             end_change( pNode, nodeVersion );
2324             end_change( pRight, rightVersion );
2325             m_stat.onRotateLeftOverRight();
2326
2327             assert( hRR - hRLR <= 1 && hRLR - hRR <= 1 );
2328
2329             int nodeBalance = hRLL - hL;
2330             if ( nodeBalance < -1 || nodeBalance > 1 ) {
2331                 m_stat.onRotateAfterLRRotation();
2332                 return pNode;
2333             }
2334
2335             if ( (pRLL == nullptr || hL == 0) && !pNode->is_valued(memory_model::memory_order_relaxed) ) {
2336                 m_stat.onRemoveAfterLRRotation();
2337                 return pNode;
2338             }
2339
2340             int balRL = hRight - hNode;
2341             if ( balRL < -1 || balRL > 1 ) {
2342                 m_stat.onRotateAfterLRRotation();
2343                 return pRLeft;
2344             }
2345
2346             return fix_height_locked( pParent );
2347         }
2348
2349         //@endcond
2350     };
2351 }} // namespace cds::container
2352
2353 #endif // #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H