cds/container/ellen_bintree_map_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_ELLEN_BINTREE_MAP_RCU_H
   4 #define __CDS_CONTAINER_ELLEN_BINTREE_MAP_RCU_H
   5
   6 #include <cds/container/ellen_bintree_base.h>
   7 #include <cds/intrusive/ellen_bintree_rcu.h>
   8 #include <cds/details/functor_wrapper.h>
   9
  10 namespace cds { namespace container {
  11
  12     /// Map based on Ellen's et al binary search tree (RCU specialization)
  13     /** @ingroup cds_nonintrusive_map
  14         @ingroup cds_nonintrusive_tree
  15         @anchor cds_container_EllenBinTreeMap_rcu
  16
  17         Source:
  18             - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
  19
  20         %EllenBinTreeMap is an unbalanced leaf-oriented binary search tree that implements the <i>map</i>
  21         abstract data type. Nodes maintains child pointers but not parent pointers.
  22         Every internal node has exactly two children, and all data of type <tt>std::pair<Key const, T></tt>
  23         currently in the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find
  24         operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
  25         may or may not be in the map.
  26         Unlike \ref cds_container_EllenBinTreeSet_rcu "EllenBinTreeSet" keys are not a part of \p T type.
  27         The map can be represented as a set containing <tt>std::pair< Key const, T> </tt> values.
  28
  29         Due to \p extract_min and \p extract_max member functions the \p %EllenBinTreeMap can act as
  30         a <i>priority queue</i>. In this case you should provide unique compound key, for example,
  31         the priority value plus some uniformly distributed random value.
  32
  33         @warning Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
  34         for uniformly distributed random keys, but in worst case the complexity is <tt>O(N)</tt>.
  35
  36         @note In the current implementation we do not use helping technique described in original paper.
  37         So, the current implementation is near to fine-grained lock-based tree.
  38         Helping will be implemented in future release
  39
  40         <b>Template arguments</b> :
  41         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  42         - \p Key - key type
  43         - \p T - value type to be stored in tree's leaf nodes.
  44         - \p Traits - type traits. See ellen_bintree::type_traits for explanation.
  45
  46         It is possible to declare option-based tree with ellen_bintree::make_map_traits metafunction
  47         instead of \p Traits template argument.
  48         Template argument list \p Options of ellen_bintree::make_map_traits metafunction are:
  49         - opt::compare - key compare functor. No default functor is provided.
  50             If the option is not specified, \p %opt::less is used.
  51         - opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
  52         - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
  53         - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
  54             or opt::v::sequential_consistent (sequentially consisnent memory model).
  55         - opt::allocator - the allocator used for \ref ellen_bintree::map_node "leaf nodes" which contains data.
  56             Default is \ref CDS_DEFAULT_ALLOCATOR.
  57         - opt::node_allocator - the allocator used for \ref ellen_bintree::internal_node "internal nodes".
  58             Default is \ref CDS_DEFAULT_ALLOCATOR.
  59         - ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
  60             default is \ref CDS_DEFAULT_ALLOCATOR.
  61             Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
  62             The number of simultaneously existing descriptors is a relatively small number limited the number of threads
  63             working with the tree and RCU buffer size.
  64             Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list
  65             of update descriptors, see cds::memory::vyukov_queue_pool free-list implementation.
  66             Also notice that size of update descriptor is not dependent on the type of data
  67             stored in the tree so single free-list object can be used for several EllenBinTree-based object.
  68         - opt::stat - internal statistics. Available types: ellen_bintree::stat, ellen_bintree::empty_stat (the default)
  69         - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
  70         - opt::copy_policy - key copy policy defines a functor to copy leaf node's key to internal node.
  71             By default, assignment operator is used.
  72             The copy functor interface is:
  73             \code
  74             struct copy_functor {
  75                 void operator()( Key& dest, Key const& src );
  76             };
  77             \endcode
  78
  79         @note Before including <tt><cds/container/ellen_bintree_map_rcu.h></tt> you should include appropriate RCU header file,
  80         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  81     */
  82     template <
  83         class RCU,
  84         typename Key,
  85         typename T,
  86 #ifdef CDS_DOXYGEN_INVOKED
  87         class Traits = ellen_bintree::type_traits
  88 #else
  89         class Traits
  90 #endif
  91     >
  92     class EllenBinTreeMap< cds::urcu::gc<RCU>, Key, T, Traits >
  93 #ifdef CDS_DOXYGEN_INVOKED
  94         : public cds::intrusive::EllenBinTree< cds::urcu::gc<RCU>, Key, T, Traits >
  95 #else
  96         : public ellen_bintree::details::make_ellen_bintree_map< cds::urcu::gc<RCU>, Key, T, Traits >::type
  97 #endif
  98     {
  99         //@cond
 100         typedef ellen_bintree::details::make_ellen_bintree_map< cds::urcu::gc<RCU>, Key, T, Traits > maker;
 101         typedef typename maker::type base_class;
 102         //@endcond
 103     public:
 104         typedef cds::urcu::gc<RCU>  gc  ;   ///< RCU Garbage collector
 105         typedef Key     key_type        ;   ///< type of a key stored in the map
 106         typedef T       mapped_type      ;  ///< type of value stored in the map
 107         typedef std::pair< key_type const, mapped_type >    value_type  ;   ///< Key-value pair stored in leaf node of the mp
 108         typedef Traits  options         ;   ///< Traits template parameter
 109
 110 #   ifdef CDS_DOXYGEN_INVOKED
 111         typedef implementation_defined key_comparator  ;    ///< key compare functor based on opt::compare and opt::less option setter.
 112 #   else
 113         typedef typename maker::intrusive_type_traits::compare   key_comparator;
 114 #   endif
 115         typedef typename base_class::item_counter           item_counter        ; ///< Item counting policy used
 116         typedef typename base_class::memory_model           memory_model        ; ///< Memory ordering. See cds::opt::memory_model option
 117         typedef typename base_class::node_allocator         node_allocator_type ; ///< allocator for maintaining internal node
 118         typedef typename base_class::stat                   stat                ; ///< internal statistics type
 119         typedef typename base_class::rcu_check_deadlock     rcu_check_deadlock  ; ///< Deadlock checking policy
 120         typedef typename options::copy_policy               copy_policy         ; ///< key copy policy
 121
 122         typedef typename options::allocator                 allocator_type      ;   ///< Allocator for leaf nodes
 123         typedef typename base_class::node_allocator         node_allocator      ;   ///< Internal node allocator
 124         typedef typename base_class::update_desc_allocator  update_desc_allocator ; ///< Update descriptor allocator
 125
 126         static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions do not require external locking
 127
 128     protected:
 129         //@cond
 130         typedef typename base_class::value_type         leaf_node;
 131         typedef typename base_class::internal_node      internal_node;
 132         typedef typename base_class::update_desc        update_desc;
 133
 134         typedef typename maker::cxx_leaf_node_allocator cxx_leaf_node_allocator;
 135
 136         typedef std::unique_ptr< leaf_node, typename maker::leaf_deallocator >    scoped_node_ptr;
 137         //@endcond
 138
 139     public:
 140         typedef typename gc::scoped_lock    rcu_lock ;  ///< RCU scoped lock
 141
 142         /// pointer to extracted node
 143         typedef cds::urcu::exempt_ptr< gc, leaf_node, value_type, typename maker::intrusive_type_traits::disposer,
 144             cds::urcu::details::conventional_exempt_member_cast<leaf_node, value_type>
 145         > exempt_ptr;
 146
 147     public:
 148         /// Default constructor
 149         EllenBinTreeMap()
 150             : base_class()
 151         {}
 152
 153         /// Clears the map
 154         ~EllenBinTreeMap()
 155         {}
 156
 157         /// Inserts new node with key and default value
 158         /**
 159             The function creates a node with \p key and default value, and then inserts the node created into the map.
 160
 161             Preconditions:
 162             - The \ref key_type should be constructible from a value of type \p K.
 163                 In trivial case, \p K is equal to \ref key_type.
 164             - The \ref mapped_type should be default-constructible.
 165
 166             RCU \p synchronize method can be called. RCU should not be locked.
 167
 168             Returns \p true if inserting successful, \p false otherwise.
 169         */
 170         template <typename K>
 171         bool insert( K const& key )
 172         {
 173             return insert_key( key, [](value_type&){} );
 174         }
 175
 176         /// Inserts new node
 177         /**
 178             The function creates a node with copy of \p val value
 179             and then inserts the node created into the map.
 180
 181             Preconditions:
 182             - The \ref key_type should be constructible from \p key of type \p K.
 183             - The \ref value_type should be constructible from \p val of type \p V.
 184
 185             RCU \p synchronize method can be called. RCU should not be locked.
 186
 187             Returns \p true if \p val is inserted into the map, \p false otherwise.
 188         */
 189         template <typename K, typename V>
 190         bool insert( K const& key, V const& val )
 191         {
 192             scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key, val ));
 193             if ( base_class::insert( *pNode ))
 194             {
 195                 pNode.release();
 196                 return true;
 197             }
 198             return false;
 199         }
 200
 201         /// Inserts new node and initialize it by a functor
 202         /**
 203             This function inserts new node with key \p key and if inserting is successful then it calls
 204             \p func functor with signature
 205             \code
 206                 struct functor {
 207                     void operator()( value_type& item );
 208                 };
 209             \endcode
 210
 211             The argument \p item of user-defined functor \p func is the reference
 212             to the map's item inserted:
 213                 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
 214                 - <tt>item.second</tt> is a reference to item's value that may be changed.
 215
 216             The user-defined functor can be passed by reference using <tt>boost::ref</tt>
 217             and it is called only if inserting is successful.
 218
 219             The key_type should be constructible from value of type \p K.
 220
 221             The function allows to split creating of new item into two part:
 222             - create item from \p key;
 223             - insert new item into the map;
 224             - if inserting is successful, initialize the value of item by calling \p func functor
 225
 226             This can be useful if complete initialization of object of \p value_type is heavyweight and
 227             it is preferable that the initialization should be completed only if inserting is successful.
 228
 229             RCU \p synchronize method can be called. RCU should not be locked.
 230         */
 231         template <typename K, typename Func>
 232         bool insert_key( const K& key, Func func )
 233         {
 234             scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key ));
 235             if ( base_class::insert( *pNode, [&func]( leaf_node& item ) { cds::unref(func)( item.m_Value ); } )) {
 236                 pNode.release();
 237                 return true;
 238             }
 239             return false;
 240         }
 241
 242         /// For key \p key inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 243         /**
 244             Returns \p true if inserting successful, \p false otherwise.
 245
 246             RCU \p synchronize method can be called. RCU should not be locked.
 247         */
 248         template <typename K, typename... Args>
 249         bool emplace( K&& key, Args&&... args )
 250         {
 251             scoped_node_ptr pNode( cxx_leaf_node_allocator().New( std::forward<K>(key), std::forward<Args>(args)... ));
 252             if ( base_class::insert( *pNode )) {
 253                 pNode.release();
 254                 return true;
 255             }
 256             return false;
 257         }
 258
 259         /// Ensures that the \p key exists in the map
 260         /**
 261             The operation performs inserting or changing data with lock-free manner.
 262
 263             If the \p key not found in the map, then the new item created from \p key
 264             is inserted into the map (note that in this case the \ref key_type should be
 265             constructible from type \p K).
 266             Otherwise, the functor \p func is called with item found.
 267             The functor \p Func may be a function with signature:
 268             \code
 269                 void func( bool bNew, value_type& item );
 270             \endcode
 271             or a functor:
 272             \code
 273                 struct my_functor {
 274                     void operator()( bool bNew, value_type& item );
 275                 };
 276             \endcode
 277
 278             with arguments:
 279             - \p bNew - \p true if the item has been inserted, \p false otherwise
 280             - \p item - item of the list
 281
 282             The functor may change any fields of the \p item.second that is \ref value_type.
 283
 284             You may pass \p func argument by reference using <tt>boost::ref</tt>.
 285
 286             RCU \p synchronize method can be called. RCU should not be locked.
 287
 288             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 289             \p second is true if new item has been added or \p false if the item with \p key
 290             already is in the list.
 291         */
 292         template <typename K, typename Func>
 293         std::pair<bool, bool> ensure( K const& key, Func func )
 294         {
 295             scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key ));
 296             std::pair<bool, bool> res = base_class::ensure( *pNode,
 297                 [&func](bool bNew, leaf_node& item, leaf_node const& ){ cds::unref(func)( bNew, item.m_Value ); }
 298             );
 299             if ( res.first && res.second )
 300                 pNode.release();
 301             return res;
 302         }
 303
 304         /// Delete \p key from the map
 305         /**\anchor cds_nonintrusive_EllenBinTreeMap_rcu_erase_val
 306
 307             RCU \p synchronize method can be called. RCU should not be locked.
 308
 309             Return \p true if \p key is found and deleted, \p false otherwise
 310         */
 311         template <typename K>
 312         bool erase( K const& key )
 313         {
 314             return base_class::erase(key);
 315         }
 316
 317         /// Deletes the item from the map using \p pred predicate for searching
 318         /**
 319             The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_erase_val "erase(K const&)"
 320             but \p pred is used for key comparing.
 321             \p Less functor has the interface like \p std::less.
 322             \p Less must imply the same element order as the comparator used for building the map.
 323         */
 324         template <typename K, typename Less>
 325         bool erase_with( K const& key, Less pred )
 326         {
 327             return base_class::erase_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >());
 328         }
 329
 330         /// Delete \p key from the map
 331         /** \anchor cds_nonintrusive_EllenBinTreeMap_rcu_erase_func
 332
 333             The function searches an item with key \p key, calls \p f functor
 334             and deletes the item. If \p key is not found, the functor is not called.
 335
 336             The functor \p Func interface:
 337             \code
 338             struct extractor {
 339                 void operator()(value_type& item) { ... }
 340             };
 341             \endcode
 342             The functor may be passed by reference using <tt>boost:ref</tt>
 343
 344             RCU \p synchronize method can be called. RCU should not be locked.
 345
 346             Return \p true if key is found and deleted, \p false otherwise
 347         */
 348         template <typename K, typename Func>
 349         bool erase( K const& key, Func f )
 350         {
 351             return base_class::erase( key, [&f]( leaf_node& node) { cds::unref(f)( node.m_Value ); } );
 352         }
 353
 354         /// Deletes the item from the map using \p pred predicate for searching
 355         /**
 356             The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_erase_func "erase(K const&, Func)"
 357             but \p pred is used for key comparing.
 358             \p Less functor has the interface like \p std::less.
 359             \p Less must imply the same element order as the comparator used for building the map.
 360         */
 361         template <typename K, typename Less, typename Func>
 362         bool erase_with( K const& key, Less pred, Func f )
 363         {
 364             return base_class::erase_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >(),
 365                 [&f]( leaf_node& node) { cds::unref(f)( node.m_Value ); } );
 366         }
 367
 368         /// Extracts an item with minimal key from the map
 369         /**
 370             If the map is not empty, the function returns \p true, \p result contains a pointer to value.
 371             If the map is empty, the function returns \p false, \p result is left unchanged.
 372
 373             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
 374             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 375             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 376             So, the function returns the item with minimum key at the moment of tree traversing.
 377
 378             RCU \p synchronize method can be called. RCU should NOT be locked.
 379             The function does not free the item.
 380             The deallocator will be implicitly invoked when \p result object is destroyed or when
 381             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
 382             @note Before reusing \p result object you should call its \p release() method.
 383         */
 384         bool extract_min( exempt_ptr& result )
 385         {
 386             return base_class::extract_min_( result );
 387         }
 388
 389         /// Extracts an item with maximal key from the map
 390         /**
 391             If the map is not empty, the function returns \p true, \p result contains a pointer to extracted item.
 392             If the map is empty, the function returns \p false, \p result is left unchanged.
 393
 394             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
 395             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 396             During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
 397             So, the function returns the item with maximum key at the moment of tree traversing.
 398
 399             RCU \p synchronize method can be called. RCU should NOT be locked.
 400             The function does not free the item.
 401             The deallocator will be implicitly invoked when \p result object is destroyed or when
 402             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
 403             @note Before reusing \p result object you should call its \p release() method.
 404         */
 405         bool extract_max( exempt_ptr& result )
 406         {
 407             return base_class::extract_max_( result );
 408         }
 409
 410         /// Extracts an item from the map
 411         /** \anchor cds_nonintrusive_EllenBinTreeMap_rcu_extract
 412             The function searches an item with key equal to \p key in the tree,
 413             unlinks it, and returns pointer to an item found in \p result parameter.
 414             If \p key is not found the function returns \p false.
 415
 416             RCU \p synchronize method can be called. RCU should NOT be locked.
 417             The function does not destroy the item found.
 418             The dealloctor will be implicitly invoked when \p result object is destroyed or when
 419             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
 420             @note Before reusing \p result object you should call its \p release() method.
 421         */
 422         template <typename Q>
 423         bool extract( exempt_ptr& result, Q const& key )
 424         {
 425             return base_class::extract_( result, key, typename base_class::node_compare());
 426         }
 427
 428         /// Extracts an item from the map using \p pred for searching
 429         /**
 430             The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_extract "extract(exempt_ptr&, Q const&)"
 431             but \p pred is used for key compare.
 432             \p Less has the interface like \p std::less and should meet \ref cds_container_EllenBinTreeSet_rcu_less
 433             "predicate requirements".
 434             \p pred must imply the same element order as the comparator used for building the map.
 435         */
 436         template <typename Q, typename Less>
 437         bool extract_with( exempt_ptr& result,  Q const& val, Less pred )
 438         {
 439             return base_class::extract_with_( result, val,
 440                 cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >() );
 441         }
 442
 443         /// Find the key \p key
 444         /** \anchor cds_nonintrusive_EllenBinTreeMap_rcu_find_cfunc
 445
 446             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 447             The interface of \p Func functor is:
 448             \code
 449             struct functor {
 450                 void operator()( value_type& item );
 451             };
 452             \endcode
 453             where \p item is the item found.
 454
 455             You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 456
 457             The functor may change \p item.second.
 458
 459             The function applies RCU lock internally.
 460
 461             The function returns \p true if \p key is found, \p false otherwise.
 462         */
 463         template <typename K, typename Func>
 464         bool find( K const& key, Func f )
 465         {
 466             return base_class::find( key, [&f](leaf_node& item, K const& ) { cds::unref(f)( item.m_Value );});
 467         }
 468
 469         /// Finds the key \p val using \p pred predicate for searching
 470         /**
 471             The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_find_cfunc "find(K const&, Func)"
 472             but \p pred is used for key comparing.
 473             \p Less functor has the interface like \p std::less.
 474             \p Less must imply the same element order as the comparator used for building the map.
 475         */
 476         template <typename K, typename Less, typename Func>
 477         bool find_with( K const& key, Less pred, Func f )
 478         {
 479             return base_class::find_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >(),
 480                 [&f](leaf_node& item, K const& ) { cds::unref(f)( item.m_Value );});
 481         }
 482
 483         /// Find the key \p key
 484         /** \anchor cds_nonintrusive_EllenBinTreeMap_rcu_find_val
 485
 486             The function searches the item with key equal to \p key
 487             and returns \p true if it is found, and \p false otherwise.
 488
 489             The function applies RCU lock internally.
 490         */
 491         template <typename K>
 492         bool find( K const& key )
 493         {
 494             return base_class::find( key );
 495         }
 496
 497         /// Finds the key \p val using \p pred predicate for searching
 498         /**
 499             The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_find_val "find(K const&)"
 500             but \p pred is used for key comparing.
 501             \p Less functor has the interface like \p std::less.
 502             \p Less must imply the same element order as the comparator used for building the map.
 503         */
 504         template <typename K, typename Less>
 505         bool find_with( K const& key, Less pred )
 506         {
 507             return base_class::find_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >() );
 508         }
 509
 510         /// Finds \p key and return the item found
 511         /** \anchor cds_nonintrusive_EllenBinTreeMap_rcu_get
 512             The function searches the item with key equal to \p key and returns the pointer to item found.
 513             If \p key is not found it returns \p nullptr.
 514
 515             RCU should be locked before call the function.
 516             Returned pointer is valid while RCU is locked.
 517         */
 518         template <typename Q>
 519         value_type * get( Q const& key ) const
 520         {
 521             leaf_node * pNode = base_class::get( key );
 522             return pNode ? &pNode->m_Value : nullptr;
 523         }
 524
 525         /// Finds \p key with \p pred predicate and return the item found
 526         /**
 527             The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_get "get(Q const&)"
 528             but \p pred is used for comparing the keys.
 529
 530             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type
 531             and \p Q in any order.
 532             \p pred must imply the same element order as the comparator used for building the map.
 533         */
 534         template <typename Q, typename Less>
 535         value_type * get_with( Q const& key, Less pred ) const
 536         {
 537             leaf_node * pNode = base_class::get_with( key,
 538                 cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >());
 539             return pNode ? &pNode->m_Value : nullptr;
 540         }
 541
 542         /// Clears the map
 543         void clear()
 544         {
 545             base_class::clear();
 546         }
 547
 548         /// Checks if the map is empty
 549         /**
 550             Emptiness is checked by item counting: if item count is zero then the map is empty.
 551         */
 552         bool empty() const
 553         {
 554             return base_class::empty();
 555         }
 556
 557         /// Returns item count in the map
 558         size_t size() const
 559         {
 560             return base_class::size();
 561         }
 562
 563         /// Returns const reference to internal statistics
 564         stat const& statistics() const
 565         {
 566             return base_class::statistics();
 567         }
 568
 569         /// Checks internal consistency (not atomic, not thread-safe)
 570         /**
 571             The debugging function to check internal consistency of the tree.
 572         */
 573         bool check_consistency() const
 574         {
 575             return base_class::check_consistency();
 576         }
 577
 578     };
 579 }} // namespace cds::container
 580
 581 #endif //#ifndef __CDS_CONTAINER_ELLEN_BINTREE_MAP_RCU_H