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