cds/container/bronson_avltree_map_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_BRONSON_AVLTREE_MAP_RCU_H
   4 #define CDSLIB_CONTAINER_BRONSON_AVLTREE_MAP_RCU_H
   5
   6 #include <functional>
   7 #include <cds/container/impl/bronson_avltree_map_rcu.h>
   8
   9 namespace cds { namespace container {
  10
  11     namespace bronson_avltree {
  12         //@cond
  13         namespace details {
  14             template < class RCU, typename Key, typename T, typename Traits>
  15             struct make_map
  16             {
  17                 typedef Key key_type;
  18                 typedef T mapped_type;
  19                 typedef Traits original_traits;
  20
  21                 typedef cds::details::Allocator< mapped_type, typename original_traits::allocator > cxx_allocator;
  22
  23                 struct traits : public original_traits
  24                 {
  25                     struct disposer {
  26                         void operator()( mapped_type * p ) const
  27                         {
  28                             cxx_allocator().Delete( p );
  29                         }
  30                     };
  31                 };
  32
  33                 // Metafunction result
  34                 typedef BronsonAVLTreeMap< RCU, Key, mapped_type *, traits > type;
  35             };
  36         } // namespace details
  37         //@endcond
  38     } // namespace bronson_avltree
  39
  40     /// Bronson et al AVL-tree (RCU specialization)
  41     /** @ingroup cds_nonintrusive_map
  42         @ingroup cds_nonintrusive_tree
  43         @anchor cds_container_BronsonAVLTreeMap_rcu
  44
  45         Source:
  46             - [2010] N.Bronson, J.Casper, H.Chafi, K.Olukotun "A Practical Concurrent Binary Search Tree"
  47             - <a href="http://github.com/nbronson/snaptree">Java implementation</a>
  48
  49         This is a concurrent AVL tree algorithm that uses hand-over-hand optimistic validation,
  50         a concurrency control mechanism for searching and navigating a binary search tree.
  51         This mechanism minimizes spurious retries when concurrent structural changes cannot
  52         affect the correctness of the search or navigation result. The algorithm is based on
  53         partially external trees, a simple scheme that simplifies deletions by leaving a routing
  54         node in the tree when deleting a node that has two children, then opportunistically unlinking
  55         routing nodes during rebalancing. As in external trees, which store values only in leaf nodes,
  56         deletions can be performed locally while holding a fixed number of locks. Partially
  57         external trees, however, require far fewer routing nodes than an external tree for most sequences
  58         of insertions and deletions.
  59
  60         <b>Template arguments</b>:
  61         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  62         - \p Key - key type
  63         - \p T - value type to be stored in tree's nodes.
  64         - \p Traits - tree traits, default is \p bronson_avltree::traits
  65             It is possible to declare option-based tree with \p bronson_avltree::make_traits metafunction
  66             instead of \p Traits template argument.
  67
  68         There is \ref cds_container_BronsonAVLTreeMap_rcu_ptr "a specialization" for "key -> value pointer" map.
  69
  70         @note Before including <tt><cds/container/bronson_avltree_map_rcu.h></tt> you should include appropriate RCU header file,
  71         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  72     */
  73     template <
  74         typename RCU,
  75         typename Key,
  76         typename T,
  77 #   ifdef CDS_DOXYGEN_INVOKED
  78         typename Traits = bronson_avltree::traits
  79 #else
  80         typename Traits
  81 #endif
  82     >
  83     class BronsonAVLTreeMap< cds::urcu::gc<RCU>, Key, T, Traits >
  84 #ifdef CDS_DOXYGEN_INVOKED
  85         : private BronsonAVLTreeMap< cds::urcu::gc<RCU>, Key, T*, Traits >
  86 #else
  87         : private bronson_avltree::details::make_map< cds::urcu::gc<RCU>, Key, T, Traits >::type
  88 #endif
  89     {
  90         //@cond
  91         typedef bronson_avltree::details::make_map< cds::urcu::gc<RCU>, Key, T, Traits > maker;
  92         typedef typename maker::type base_class;
  93         //@endcond
  94
  95     public:
  96         typedef cds::urcu::gc<RCU>  gc;   ///< RCU Garbage collector
  97         typedef Key     key_type;    ///< type of a key stored in the map
  98         typedef T       mapped_type; ///< type of value stored in the map
  99         typedef Traits  traits;      ///< Traits template parameter
 100
 101         typedef typename base_class::key_comparator     key_comparator;     ///< key compare functor based on \p Traits::compare and \p Traits::less
 102         typedef typename traits::item_counter           item_counter;       ///< Item counting policy
 103         typedef typename traits::memory_model           memory_model;       ///< Memory ordering, see \p cds::opt::memory_model option
 104         typedef typename traits::allocator              allocator_type;     ///< allocator for value
 105         typedef typename traits::node_allocator         node_allocator_type;///< allocator for maintaining internal nodes
 106         typedef typename traits::stat                   stat;               ///< internal statistics
 107         typedef typename traits::rcu_check_deadlock     rcu_check_deadlock; ///< Deadlock checking policy
 108         typedef typename traits::back_off               back_off;           ///< Back-off strategy
 109         typedef typename traits::sync_monitor           sync_monitor;       ///< @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
 110
 111         /// Enabled or disabled @ref bronson_avltree::relaxed_insert "relaxed insertion"
 112         static bool const c_bRelaxedInsert = traits::relaxed_insert;
 113
 114         /// Group of \p extract_xxx functions does not require external locking
 115         static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal;
 116
 117         typedef typename base_class::rcu_lock   rcu_lock;  ///< RCU scoped lock
 118
 119         /// Returned pointer to \p mapped_type of extracted node
 120         typedef typename base_class::exempt_ptr exempt_ptr;
 121
 122     protected:
 123         //@cond
 124         typedef typename base_class::node_type        node_type;
 125         typedef typename base_class::node_scoped_lock node_scoped_lock;
 126         typedef typename maker::cxx_allocator         cxx_allocator;
 127
 128         typedef typename base_class::update_flags update_flags;
 129         //@endcond
 130
 131     public:
 132         /// Creates empty map
 133         BronsonAVLTreeMap()
 134         {}
 135
 136         /// Destroys the map
 137         ~BronsonAVLTreeMap()
 138         {}
 139
 140         /// Inserts new node with \p key and default value
 141         /**
 142             The function creates a node with \p key and default value, and then inserts the node created into the map.
 143
 144             Preconditions:
 145             - The \p key_type should be constructible from a value of type \p K.
 146             - The \p mapped_type should be default-constructible.
 147
 148             RCU \p synchronize() can be called. RCU should not be locked.
 149
 150             Returns \p true if inserting successful, \p false otherwise.
 151         */
 152         template <typename K>
 153         bool insert( K const& key )
 154         {
 155             return base_class::do_update(key, key_comparator(),
 156                 []( node_type * pNode ) -> mapped_type*
 157                 {
 158                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 159                     CDS_UNUSED( pNode );
 160                     return cxx_allocator().New();
 161                 },
 162                 update_flags::allow_insert
 163             ) == update_flags::result_inserted;
 164         }
 165
 166         /// Inserts new node
 167         /**
 168             The function creates a node with copy of \p val value
 169             and then inserts the node created into the map.
 170
 171             Preconditions:
 172             - The \p key_type should be constructible from \p key of type \p K.
 173             - The \p mapped_type should be constructible from \p val of type \p V.
 174
 175             RCU \p synchronize() method can be called. RCU should not be locked.
 176
 177             Returns \p true if \p val is inserted into the map, \p false otherwise.
 178         */
 179         template <typename K, typename V>
 180         bool insert( K const& key, V const& val )
 181         {
 182             return base_class::do_update( key, key_comparator(),
 183                 [&val]( node_type * pNode ) -> mapped_type*
 184                 {
 185                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 186                     CDS_UNUSED( pNode );
 187                     return cxx_allocator().New( val );
 188                 },
 189                 update_flags::allow_insert
 190             ) == update_flags::result_inserted;
 191         }
 192
 193         /// Inserts new node and initialize it by a functor
 194         /**
 195             This function inserts new node with key \p key and if inserting is successful then it calls
 196             \p func functor with signature
 197             \code
 198                 struct functor {
 199                     void operator()( key_type const& key, mapped_type& item );
 200                 };
 201             \endcode
 202
 203             The key_type should be constructible from value of type \p K.
 204
 205             The function allows to split creating of new item into two part:
 206             - create item from \p key;
 207             - insert new item into the map;
 208             - if inserting is successful, initialize the value of item by calling \p func functor
 209
 210             This can be useful if complete initialization of object of \p value_type is heavyweight and
 211             it is preferable that the initialization should be completed only if inserting is successful.
 212             The functor is called under the node lock.
 213
 214             RCU \p synchronize() method can be called. RCU should not be locked.
 215         */
 216         template <typename K, typename Func>
 217         bool insert_with( K const& key, Func func )
 218         {
 219             return base_class::do_update( key, key_comparator(),
 220                 [&func]( node_type * pNode ) -> mapped_type*
 221                 {
 222                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 223                     mapped_type * pVal = cxx_allocator().New();
 224                     func( pNode->m_key, *pVal );
 225                     return pVal;
 226                 },
 227                 update_flags::allow_insert
 228             ) == update_flags::result_inserted;
 229         }
 230
 231         /// For key \p key inserts data of type \p mapped_type created in-place from \p args
 232         /**
 233             Returns \p true if inserting successful, \p false otherwise.
 234
 235             RCU \p synchronize() method can be called. RCU should not be locked.
 236         */
 237         template <typename K, typename... Args>
 238         bool emplace( K&& key, Args&&... args )
 239         {
 240 #       if !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 40800 && CDS_COMPILER_VERSION < 40900 )
 241             // Probably, the following code is not so efficient, since we pass lvalues instead rvalues to lambda
 242             //TODO: study how to pass a parameter pack to a lambda efficiently using perfect forwarding
 243             // see http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#904 - this is what we need
 244             return base_class::do_update( key, key_comparator(),
 245                 [&args...]( node_type * pNode ) -> mapped_type *
 246                 {
 247                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 248                     CDS_UNUSED( pNode );
 249                     return cxx_allocator().New( std::forward<Args>(args)...);
 250                 },
 251                 update_flags::allow_insert
 252             ) == update_flags::result_inserted;
 253 #       else
 254             // gcc 4.8 error: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=47226
 255             // workaround (from http://stackoverflow.com/questions/14191989/how-do-i-use-variadic-perfect-forwarding-into-a-lambda)
 256             auto f = std::bind<mapped_type *>(
 257                         []( Args... args) -> mapped_type* { return cxx_allocator().New( std::move(args)...); },
 258                         std::forward<Args>(args)...
 259                         );
 260             return base_class::do_update( key, key_comparator(),
 261                 [&f]( node_type * pNode ) -> mapped_type *
 262                 {
 263                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 264                     CDS_UNUSED( pNode );
 265                     return f();
 266                 },
 267                 update_flags::allow_insert
 268             ) == update_flags::result_inserted;
 269 #       endif
 270         }
 271
 272         /// Ensures that the \p key exists in the map
 273         /**
 274             The operation performs inserting or changing data with lock-free manner.
 275
 276             If the \p key not found in the map, then the new item created from \p key
 277             will be inserted into the map (note that in this case the \ref key_type should be
 278             constructible from type \p K).
 279             Otherwise, the functor \p func is called with item found.
 280             The functor \p Func may be a functor:
 281             \code
 282                 struct my_functor {
 283                     void operator()( bool bNew, key_type const& key, mapped_type& item );
 284                 };
 285             \endcode
 286
 287             with arguments:
 288             - \p bNew - \p true if the item has been inserted, \p false otherwise
 289             - \p item - value
 290
 291             The functor may change any fields of the \p item. The functor is called under the node lock.
 292
 293             RCU \p synchronize() method can be called. RCU should not be locked.
 294
 295             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
 296             \p second is \p true if new item has been added or \p false if the item with \p key
 297             already exists.
 298         */
 299         template <typename K, typename Func>
 300         std::pair<bool, bool> update( K const& key, Func func )
 301         {
 302             int result = base_class::do_update( key, key_comparator(),
 303                 [&func]( node_type * pNode ) -> mapped_type*
 304                 {
 305                     mapped_type * pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
 306                     if ( !pVal ) {
 307                         pVal = cxx_allocator().New();
 308                         func( true, pNode->m_key, *pVal );
 309                     }
 310                     else
 311                         func( false, pNode->m_key, *pVal );
 312                     return pVal;
 313                 },
 314                 update_flags::allow_insert | update_flags::allow_update
 315             );
 316             return std::make_pair( result != 0, (result & update_flags::result_inserted) != 0 );
 317         }
 318
 319         //@cond
 320         template <typename K, typename Func>
 321         std::pair<bool, bool> ensure( K const& key, Func func )
 322         {
 323             return update( key, func );
 324         }
 325         //@endcond
 326
 327
 328         /// Delete \p key from the map
 329         /**
 330             RCU \p synchronize() method can be called. RCU should not be locked.
 331
 332             Return \p true if \p key is found and deleted, \p false otherwise
 333         */
 334         template <typename K>
 335         bool erase( K const& key )
 336         {
 337             return base_class::erase( key );
 338         }
 339
 340         /// Deletes the item from the map using \p pred predicate for searching
 341         /**
 342             The function is an analog of \p erase(K const&)
 343             but \p pred is used for key comparing.
 344             \p Less functor has the interface like \p std::less.
 345             \p Less must imply the same element order as the comparator used for building the map.
 346         */
 347         template <typename K, typename Less>
 348         bool erase_with( K const& key, Less pred )
 349         {
 350             return base_class::erase_with( key, pred );
 351         }
 352
 353         /// Delete \p key from the map
 354         /** \anchor cds_nonintrusive_BronsonAVLTreeMap_rcu_erase_func
 355
 356             The function searches an item with key \p key, calls \p f functor
 357             and deletes the item. If \p key is not found, the functor is not called.
 358
 359             The functor \p Func interface:
 360             \code
 361             struct extractor {
 362                 void operator()(key_type const& key, mapped_type& item) { ... }
 363             };
 364             \endcode
 365
 366             RCU \p synchronize method can be called. RCU should not be locked.
 367
 368             Return \p true if key is found and deleted, \p false otherwise
 369         */
 370         template <typename K, typename Func>
 371         bool erase( K const& key, Func f )
 372         {
 373             return base_class::erase( key, f );
 374         }
 375
 376         /// Deletes the item from the map using \p pred predicate for searching
 377         /**
 378             The function is an analog of \ref cds_nonintrusive_BronsonAVLTreeMap_rcu_erase_func "erase(K const&, Func)"
 379             but \p pred is used for key comparing.
 380             \p Less functor has the interface like \p std::less.
 381             \p Less must imply the same element order as the comparator used for building the map.
 382         */
 383         template <typename K, typename Less, typename Func>
 384         bool erase_with( K const& key, Less pred, Func f )
 385         {
 386             return base_class::erase_with( key, pred, f );
 387         }
 388
 389         /// Extracts a value with minimal key from the map
 390         /**
 391             Returns \p exempt_ptr pointer to the leftmost item.
 392             If the set is empty, returns empty \p exempt_ptr.
 393
 394             Note that the function returns only the value for minimal key.
 395             To retrieve its key use \p extract_min( Func ) member function.
 396
 397             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
 398             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 399             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 400             So, the function returns the item with minimum key at the moment of tree traversing.
 401
 402             RCU \p synchronize method can be called. RCU should NOT be locked.
 403             The function does not free the item.
 404             The deallocator will be implicitly invoked when the returned object is destroyed or when
 405             its \p release() member function is called.
 406         */
 407         exempt_ptr extract_min()
 408         {
 409             return base_class::extract_min();
 410         }
 411
 412         /// Extracts minimal key key and corresponding value
 413         /**
 414             Returns \p exempt_ptr to the leftmost item.
 415             If the tree is empty, returns empty \p exempt_ptr.
 416
 417             \p Func functor is used to store minimal key.
 418             \p Func has the following signature:
 419             \code
 420                 struct functor {
 421                     void operator()( key_type const& key );
 422                 };
 423             \endcode
 424             If the tree is empty, \p f is not called.
 425             Otherwise, is it called with minimal key, the pointer to corresponding value is returned
 426             as \p exempt_ptr.
 427
 428             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
 429             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 430             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 431             So, the function returns the item with minimum key at the moment of tree traversing.
 432
 433             RCU \p synchronize method can be called. RCU should NOT be locked.
 434             The function does not free the item.
 435             The deallocator will be implicitly invoked when the returned object is destroyed or when
 436             its \p release() member function is called.
 437         */
 438         template <typename Func>
 439         exempt_ptr extract_min( Func f )
 440         {
 441             return base_class::extract_min( f );
 442         }
 443
 444         /// Extracts minimal key key and corresponding value
 445         /**
 446             This function is a shortcut for the following call:
 447             \code
 448                 key_type key;
 449                 exempt_ptr xp = theTree.extract_min( [&key]( key_type const& k ) { key = k; } );
 450             \endcode
 451             \p key_type should be copy-assignable. The copy of minimal key
 452             is returned in \p min_key argument.
 453         */
 454         typename std::enable_if< std::is_copy_assignable<key_type>::value, exempt_ptr >::type
 455         extract_min_key( key_type& min_key )
 456         {
 457             return base_class::extract_min_key( min_key );
 458         }
 459
 460         /// Extracts an item with maximal key from the map
 461         /**
 462             Returns \p exempt_ptr pointer to the rightmost item.
 463             If the set is empty, returns empty \p exempt_ptr.
 464
 465             Note that the function returns only the value for maximal key.
 466             To retrieve its key use \p extract_max( Func ) or \p extract_max_key(key_type&) member function.
 467
 468             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
 469             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 470             During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
 471             So, the function returns the item with maximum key at the moment of tree traversing.
 472
 473             RCU \p synchronize method can be called. RCU should NOT be locked.
 474             The function does not free the item.
 475             The deallocator will be implicitly invoked when the returned object is destroyed or when
 476             its \p release() is called.
 477         */
 478         exempt_ptr extract_max()
 479         {
 480             return base_class::extract_max();
 481         }
 482
 483         /// Extracts the maximal key and corresponding value
 484         /**
 485             Returns \p exempt_ptr pointer to the rightmost item.
 486             If the set is empty, returns empty \p exempt_ptr.
 487
 488             \p Func functor is used to store maximal key.
 489             \p Func has the following signature:
 490             \code
 491                 struct functor {
 492                     void operator()( key_type const& key );
 493                 };
 494             \endcode
 495             If the tree is empty, \p f is not called.
 496             Otherwise, is it called with maximal key, the pointer to corresponding value is returned
 497             as \p exempt_ptr.
 498
 499             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
 500             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 501             During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
 502             So, the function returns the item with maximum key at the moment of tree traversing.
 503
 504             RCU \p synchronize method can be called. RCU should NOT be locked.
 505             The function does not free the item.
 506             The deallocator will be implicitly invoked when the returned object is destroyed or when
 507             its \p release() is called.
 508         */
 509         template <typename Func>
 510         exempt_ptr extract_max( Func f )
 511         {
 512             return base_class::extract_max( f );
 513         }
 514
 515         /// Extracts the maximal key and corresponding value
 516         /**
 517             This function is a shortcut for the following call:
 518             \code
 519                 key_type key;
 520                 exempt_ptr xp = theTree.extract_max( [&key]( key_type const& k ) { key = k; } );
 521             \endcode
 522             \p key_type should be copy-assignable. The copy of maximal key
 523             is returned in \p max_key argument.
 524         */
 525         typename std::enable_if< std::is_copy_assignable<key_type>::value, exempt_ptr >::type
 526         extract_max_key( key_type& max_key )
 527         {
 528             return base_class::extract_max_key( max_key );
 529         }
 530
 531         /// Extracts an item from the map
 532         /**
 533             The function searches an item with key equal to \p key in the tree,
 534             unlinks it, and returns \p exempt_ptr pointer to a value found.
 535             If \p key is not found the function returns an empty \p exempt_ptr.
 536
 537             RCU \p synchronize method can be called. RCU should NOT be locked.
 538             The function does not destroy the value found.
 539             The dealloctor will be implicitly invoked when the returned object is destroyed or when
 540             its \p release() member function is called.
 541         */
 542         template <typename Q>
 543         exempt_ptr extract( Q const& key )
 544         {
 545             return base_class::extract( key );
 546         }
 547
 548         /// Extracts an item from the map using \p pred for searching
 549         /**
 550             The function is an analog of \p extract(Q const&)
 551             but \p pred is used for key compare.
 552             \p Less has the interface like \p std::less.
 553             \p pred must imply the same element order as the comparator used for building the map.
 554         */
 555         template <typename Q, typename Less>
 556         exempt_ptr extract_with( Q const& key, Less pred )
 557         {
 558             return base_class::extract_with( key, pred );
 559         }
 560
 561         /// Find the key \p key
 562         /**
 563             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 564             The interface of \p Func functor is:
 565             \code
 566             struct functor {
 567                 void operator()( key_type const& key, mapped_type& val );
 568             };
 569             \endcode
 570             where \p val is the item found for \p key
 571             The functor is called under node-level lock.
 572
 573             The function applies RCU lock internally.
 574
 575             The function returns \p true if \p key is found, \p false otherwise.
 576         */
 577         template <typename K, typename Func>
 578         bool find( K const& key, Func f )
 579         {
 580             return base_class::find( key, f );
 581         }
 582
 583         /// Finds the key \p val using \p pred predicate for searching
 584         /**
 585             The function is an analog of \p find(K const&, Func)
 586             but \p pred is used for key comparing.
 587             \p Less functor has the interface like \p std::less.
 588             \p Less must imply the same element order as the comparator used for building the map.
 589         */
 590         template <typename K, typename Less, typename Func>
 591         bool find_with( K const& key, Less pred, Func f )
 592         {
 593             return base_class::find_with( key, pred, f );
 594         }
 595
 596         /// Find the key \p key
 597         /**
 598             The function searches the item with key equal to \p key
 599             and returns \p true if it is found, and \p false otherwise.
 600
 601             The function applies RCU lock internally.
 602         */
 603         template <typename K>
 604         bool find( K const& key )
 605         {
 606             return base_class::find( key );
 607         }
 608
 609         /// Finds the key \p val using \p pred predicate for searching
 610         /**
 611             The function is an analog of \p find(K const&)
 612             but \p pred is used for key comparing.
 613             \p Less functor has the interface like \p std::less.
 614             \p Less must imply the same element order as the comparator used for building the map.
 615         */
 616         template <typename K, typename Less>
 617         bool find_with( K const& key, Less pred )
 618         {
 619             return base_class::find_with( key, pred );
 620         }
 621
 622         /// Clears the map
 623         void clear()
 624         {
 625             base_class::clear();
 626         }
 627
 628         /// Checks if the map is empty
 629         bool empty() const
 630         {
 631             return base_class::empty();
 632         }
 633
 634         /// Returns item count in the map
 635         /**
 636             Only leaf nodes containing user data are counted.
 637
 638             The value returned depends on item counter type provided by \p Traits template parameter.
 639             If it is \p atomicity::empty_item_counter this function always returns 0.
 640
 641             The function is not suitable for checking the tree emptiness, use \p empty()
 642             member function for this purpose.
 643         */
 644         size_t size() const
 645         {
 646             return base_class::size();
 647         }
 648
 649         /// Returns const reference to internal statistics
 650         stat const& statistics() const
 651         {
 652             return base_class::statistics();
 653         }
 654
 655         /// Checks internal consistency (not atomic, not thread-safe)
 656         /**
 657             The debugging function to check internal consistency of the tree.
 658         */
 659         bool check_consistency() const
 660         {
 661             return base_class::check_consistency();
 662         }
 663
 664         /// Checks internal consistency (not atomic, not thread-safe)
 665         /**
 666             The debugging function to check internal consistency of the tree.
 667             The functor \p Func is called if a violation of internal tree structure
 668             is found:
 669             \code
 670             struct functor {
 671                 void operator()( size_t nLevel, size_t hLeft, size_t hRight );
 672             };
 673             \endcode
 674             where
 675             - \p nLevel - the level where the violation is found
 676             - \p hLeft - the height of left subtree
 677             - \p hRight - the height of right subtree
 678
 679             The functor is called for each violation found.
 680         */
 681         template <typename Func>
 682         bool check_consistency( Func f ) const
 683         {
 684             return base_class::check_consistency( f );
 685         }
 686     };
 687 }} // namespace cds::container
 688
 689 #endif // #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H