cds/container/ellen_bintree_map_impl.h

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