cds/container/cuckoo_map.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_CUCKOO_MAP_H
   4 #define CDSLIB_CONTAINER_CUCKOO_MAP_H
   5
   6 #include <cds/container/details/cuckoo_base.h>
   7 #include <cds/details/binary_functor_wrapper.h>
   8
   9 namespace cds { namespace container {
  10
  11     //@cond
  12     namespace details {
  13         template <typename Key, typename T, typename Traits>
  14         struct make_cuckoo_map
  15         {
  16             typedef Key key_type;    ///< key type
  17             typedef T   mapped_type; ///< type of value stored in the map
  18             typedef std::pair<key_type const, mapped_type>   value_type;   ///< Pair type
  19
  20             typedef Traits original_traits;
  21             typedef typename original_traits::probeset_type probeset_type;
  22             static bool const store_hash = original_traits::store_hash;
  23             static unsigned int const store_hash_count = store_hash ? ((unsigned int) std::tuple_size< typename original_traits::hash::hash_tuple_type >::value) : 0;
  24
  25             struct node_type: public intrusive::cuckoo::node<probeset_type, store_hash_count>
  26             {
  27                 value_type  m_val;
  28
  29                 template <typename K>
  30                 node_type( K const& key )
  31                     : m_val( std::make_pair( key_type(key), mapped_type() ))
  32                 {}
  33
  34                 template <typename K, typename Q>
  35                 node_type( K const& key, Q const& v )
  36                     : m_val( std::make_pair( key_type(key), mapped_type(v) ))
  37                 {}
  38
  39                 template <typename K, typename... Args>
  40                 node_type( K&& key, Args&&... args )
  41                     : m_val( std::forward<K>(key), std::move( mapped_type(std::forward<Args>(args)...)) )
  42                 {}
  43             };
  44
  45             struct key_accessor {
  46                 key_type const& operator()( node_type const& node ) const
  47                 {
  48                     return node.m_val.first;
  49                 }
  50             };
  51
  52             struct intrusive_traits: public original_traits
  53             {
  54                 typedef intrusive::cuckoo::base_hook<
  55                     cds::intrusive::cuckoo::probeset_type< probeset_type >
  56                     ,cds::intrusive::cuckoo::store_hash< store_hash_count >
  57                 >  hook;
  58
  59                 typedef cds::intrusive::cuckoo::traits::disposer   disposer;
  60
  61                 typedef typename std::conditional<
  62                     std::is_same< typename original_traits::equal_to, opt::none >::value
  63                     , opt::none
  64                     , cds::details::predicate_wrapper< node_type, typename original_traits::equal_to, key_accessor >
  65                 >::type equal_to;
  66
  67                 typedef typename std::conditional<
  68                     std::is_same< typename original_traits::compare, opt::none >::value
  69                     , opt::none
  70                     , cds::details::compare_wrapper< node_type, typename original_traits::compare, key_accessor >
  71                 >::type compare;
  72
  73                 typedef typename std::conditional<
  74                     std::is_same< typename original_traits::less, opt::none >::value
  75                     ,opt::none
  76                     ,cds::details::predicate_wrapper< node_type, typename original_traits::less, key_accessor >
  77                 >::type less;
  78
  79                 typedef opt::details::hash_list_wrapper< typename original_traits::hash, node_type, key_accessor >    hash;
  80             };
  81
  82             typedef intrusive::CuckooSet< node_type, intrusive_traits > type;
  83         };
  84     }   // namespace details
  85     //@endcond
  86
  87     /// Cuckoo hash map
  88     /** @ingroup cds_nonintrusive_map
  89
  90         Source
  91             - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
  92             - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
  93
  94         <b>About Cuckoo hashing</b>
  95
  96             [From "The Art of Multiprocessor Programming"]
  97             Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item
  98             occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
  99             N = 2k we use a two-entry array of tables, and two independent hash functions,
 100             <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
 101             mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
 102             <tt>find(x)</tt> tests whether either <tt>table[0][h0(x)]</tt> or <tt>table[1][h1(x)]</tt> is
 103             equal to \p x. Similarly, <tt>erase(x)</tt>checks whether \p x is in either <tt>table[0][h0(x)]</tt>
 104             or <tt>table[1][h1(x)]</tt>, ad removes it if found.
 105
 106             The <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
 107             To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
 108             If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y
 109             for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
 110             was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables)
 111             until it finds an empty slot. We might not find an empty slot, either because the table is full,
 112             or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
 113             number of successive displacements we are willing to undertake. When this limit is exceeded,
 114             we resize the hash table, choose new hash functions and start over.
 115
 116             For concurrent cuckoo hashing, rather than organizing the set as a two-dimensional table of
 117             items, we use two-dimensional table of probe sets, where a probe set is a constant-sized set
 118             of items with the same hash code. Each probe set holds at most \p PROBE_SIZE items, but the algorithm
 119             tries to ensure that when the set is quiescent (i.e no method call in progress) each probe set
 120             holds no more than <tt>THRESHOLD < PROBE_SET</tt> items. While method calls are in-flight, a probe
 121             set may temporarily hold more than \p THRESHOLD but never more than \p PROBE_SET items.
 122
 123             In current implementation, a probe set can be defined either as a (single-linked) list
 124             or as a fixed-sized vector, optionally ordered.
 125
 126             In description above two-table cuckoo hashing (<tt>k = 2</tt>) has been considered.
 127             We can generalize this approach for <tt>k >= 2</tt> when we have \p k hash functions
 128             <tt>h[0], ... h[k-1]</tt> and \p k tables <tt>table[0], ... table[k-1]</tt>.
 129
 130             The search in probe set is linear, the complexity is <tt> O(PROBE_SET) </tt>.
 131             The probe set may be ordered or not. Ordered probe set can be a little better since
 132             the average search complexity is <tt>O(PROBE_SET/2)</tt>.
 133             However, the overhead of sorting can eliminate a gain of ordered search.
 134
 135             The probe set is ordered if opt::compare or opt::less is specified in \p %CuckooSet
 136             declaration. Otherwise, the probe set is unordered and \p %CuckooSet must contain
 137             opt::equal_to option.
 138
 139         Template arguments:
 140         - \p Key - key type
 141         - \p T - the type stored in the map.
 142         - \p Traits - map traits., default is \p cuckoo::traits.
 143             It is possible to declare option-based set with \p cuckoo::make_traits metafunction
 144             result as \p Traits template argument.
 145
 146        <b>Examples</b>
 147
 148        Declares cuckoo mapping from \p std::string to struct \p foo.
 149        For cuckoo hashing we should provide at least two hash functions:
 150        \code
 151         struct hash1 {
 152             size_t operator()(std::string const& s) const
 153             {
 154                 return cds::opt::v::hash<std::string>( s );
 155             }
 156         };
 157
 158         struct hash2: private hash1 {
 159             size_t operator()(std::string const& s) const
 160             {
 161                 size_t h = ~( hash1::operator()(s));
 162                 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
 163             }
 164         };
 165        \endcode
 166
 167         Cuckoo-map with list-based unordered probe set and storing hash values
 168         \code
 169         #include <cds/container/cuckoo_map.h>
 170
 171         // Declare type traits
 172         struct my_traits: public cds::container::cuckoo::traits
 173         {
 174             typedef std::equal_to< std::string > equal_to;
 175             typedef std::tuple< hash1, hash2 >  hash;
 176
 177             static bool const store_hash = true;
 178         };
 179
 180         // Declare CuckooMap type
 181         typedef cds::container::CuckooMap< std::string, foo, my_traits > my_cuckoo_map;
 182
 183         // Equal option-based declaration
 184         typedef cds::container::CuckooMap< std::string, foo,
 185             cds::container::cuckoo::make_traits<
 186                 cds::opt::hash< std::tuple< hash1, hash2 > >
 187                 ,cds::opt::equal_to< std::equal_to< std::string > >
 188                 ,cds::container::cuckoo::store_hash< true >
 189             >::type
 190         > opt_cuckoo_map;
 191         \endcode
 192
 193         If we provide \p less functor instead of \p equal_to
 194         we get as a result a cuckoo map with ordered probe set that may improve
 195         performance.
 196         Example for ordered vector-based probe-set:
 197
 198         \code
 199         #include <cds/container/cuckoo_map.h>
 200
 201         // Declare type traits
 202         // We use a vector of capacity 4 as probe-set container and store hash values in the node
 203         struct my_traits: public cds::container::cuckoo::traits
 204         {
 205             typedef std::less< std::string > less;
 206             typedef std::tuple< hash1, hash2 >  hash;
 207             typedef cds::container::cuckoo::vector<4> probeset_type;
 208
 209             static bool const store_hash = true;
 210         };
 211
 212         // Declare CuckooMap type
 213         typedef cds::container::CuckooMap< std::string, foo, my_traits > my_cuckoo_map;
 214
 215         // Equal option-based declaration
 216         typedef cds::container::CuckooMap< std::string, foo,
 217             cds::container::cuckoo::make_traits<
 218                 cds::opt::hash< std::tuple< hash1, hash2 > >
 219                 ,cds::opt::less< std::less< std::string > >
 220                 ,cds::container::cuckoo::probeset_type< cds::container::cuckoo::vector<4> >
 221                 ,cds::container::cuckoo::store_hash< true >
 222             >::type
 223         > opt_cuckoo_map;
 224         \endcode
 225
 226     */
 227     template <typename Key, typename T, typename Traits = cuckoo::traits>
 228     class CuckooMap:
 229 #ifdef CDS_DOXYGEN_INVOKED
 230         protected intrusive::CuckooSet< std::pair< Key const, T>, Traits>
 231 #else
 232         protected details::make_cuckoo_map<Key, T, Traits>::type
 233 #endif
 234     {
 235         //@cond
 236         typedef details::make_cuckoo_map<Key, T, Traits>    maker;
 237         typedef typename maker::type  base_class;
 238         //@endcond
 239     public:
 240         typedef Key     key_type;    ///< key type
 241         typedef T       mapped_type; ///< value type stored in the container
 242         typedef std::pair<key_type const, mapped_type> value_type;   ///< Key-value pair type stored in the map
 243         typedef Traits  traits;     ///< Map traits
 244
 245         typedef typename traits::hash                 hash;            ///< hash functor tuple wrapped for internal use
 246         typedef typename base_class::hash_tuple_type  hash_tuple_type; ///< hash tuple type
 247
 248         typedef typename base_class::mutex_policy mutex_policy; ///< Concurrent access policy, see \p cuckoo::traits::mutex_policy
 249         typedef typename base_class::stat         stat;         ///< internal statistics type
 250
 251         static bool const c_isSorted = base_class::c_isSorted; ///< whether the probe set should be ordered
 252         static size_t const c_nArity = base_class::c_nArity;   ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
 253
 254         typedef typename base_class::key_equal_to key_equal_to; ///< Key equality functor; used only for unordered probe-set
 255
 256         typedef typename base_class::key_comparator  key_comparator; ///< key comparing functor based on opt::compare and opt::less option setter. Used only for ordered probe set
 257
 258         typedef typename base_class::allocator     allocator; ///< allocator type used for internal bucket table allocations
 259
 260         /// Node allocator type
 261         typedef typename std::conditional<
 262             std::is_same< typename traits::node_allocator, opt::none >::value,
 263             allocator,
 264             typename traits::node_allocator
 265         >::type node_allocator;
 266
 267         /// item counter type
 268         typedef typename traits::item_counter  item_counter;
 269
 270     protected:
 271         //@cond
 272         typedef typename base_class::scoped_cell_lock   scoped_cell_lock;
 273         typedef typename base_class::scoped_full_lock   scoped_full_lock;
 274         typedef typename base_class::scoped_resize_lock scoped_resize_lock;
 275         typedef typename maker::key_accessor            key_accessor;
 276
 277         typedef typename base_class::value_type         node_type;
 278         typedef cds::details::Allocator< node_type, node_allocator >    cxx_node_allocator;
 279         //@endcond
 280
 281     public:
 282         static unsigned int const   c_nDefaultProbesetSize = base_class::c_nDefaultProbesetSize; ///< default probeset size
 283         static size_t const         c_nDefaultInitialSize = base_class::c_nDefaultInitialSize;   ///< default initial size
 284         static unsigned int const   c_nRelocateLimit = base_class::c_nRelocateLimit;             ///< Count of attempts to relocate before giving up
 285
 286     protected:
 287         //@cond
 288         template <typename K>
 289         static node_type * alloc_node( K const& key )
 290         {
 291             return cxx_node_allocator().New( key );
 292         }
 293         template <typename K, typename... Args>
 294         static node_type * alloc_node( K&& key, Args&&... args )
 295         {
 296             return cxx_node_allocator().MoveNew( std::forward<K>( key ), std::forward<Args>(args)... );
 297         }
 298
 299         static void free_node( node_type * pNode )
 300         {
 301             cxx_node_allocator().Delete( pNode );
 302         }
 303         //@endcond
 304
 305     protected:
 306         //@cond
 307         struct node_disposer {
 308             void operator()( node_type * pNode )
 309             {
 310                 free_node( pNode );
 311             }
 312         };
 313
 314         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 315
 316         //@endcond
 317
 318     public:
 319         /// Default constructor
 320         /**
 321             Initial size = \ref c_nDefaultInitialSize
 322
 323             Probe set size:
 324             - \ref c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
 325             - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
 326
 327             Probe set threshold = probe set size - 1
 328         */
 329         CuckooMap()
 330         {}
 331
 332         /// Constructs an object with given probe set size and threshold
 333         /**
 334             If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
 335             then \p nProbesetSize should be equal to vector's \p Capacity.
 336         */
 337         CuckooMap(
 338             size_t nInitialSize                     ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
 339             , unsigned int nProbesetSize            ///< probe set size
 340             , unsigned int nProbesetThreshold = 0   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
 341         )
 342         : base_class( nInitialSize, nProbesetSize, nProbesetThreshold )
 343         {}
 344
 345         /// Constructs an object with given hash functor tuple
 346         /**
 347             The probe set size and threshold are set as default, see CuckooSet()
 348         */
 349         CuckooMap(
 350             hash_tuple_type const& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
 351         )
 352         : base_class( h )
 353         {}
 354
 355         /// Constructs a map with given probe set properties and hash functor tuple
 356         /**
 357             If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
 358             then \p nProbesetSize should be equal to vector's \p Capacity.
 359         */
 360         CuckooMap(
 361             size_t nInitialSize                 ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
 362             , unsigned int nProbesetSize        ///< probe set size
 363             , unsigned int nProbesetThreshold   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
 364             , hash_tuple_type const& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
 365         )
 366         : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, h )
 367         {}
 368
 369         /// Constructs a map with given hash functor tuple (move semantics)
 370         /**
 371             The probe set size and threshold are set as default, see CuckooSet()
 372         */
 373         CuckooMap(
 374             hash_tuple_type&& h     ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
 375         )
 376         : base_class( std::forward<hash_tuple_type>(h) )
 377         {}
 378
 379         /// Constructs a map with given probe set properties and hash functor tuple (move semantics)
 380         /**
 381             If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
 382             then \p nProbesetSize should be equal to vector's \p Capacity.
 383         */
 384         CuckooMap(
 385             size_t nInitialSize                 ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
 386             , unsigned int nProbesetSize        ///< probe set size
 387             , unsigned int nProbesetThreshold   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
 388             , hash_tuple_type&& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
 389         )
 390         : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h) )
 391         {}
 392
 393         /// Destructor clears the map
 394         ~CuckooMap()
 395         {
 396             clear();
 397         }
 398
 399     public:
 400         /// Inserts new node with key and default value
 401         /**
 402             The function creates a node with \p key and default value, and then inserts the node created into the map.
 403
 404             Preconditions:
 405             - The \ref key_type should be constructible from a value of type \p K.
 406                 In trivial case, \p K is equal to \ref key_type.
 407             - The \ref mapped_type should be default-constructible.
 408
 409             Returns \p true if inserting successful, \p false otherwise.
 410         */
 411         template <typename K>
 412         bool insert( K const& key )
 413         {
 414             return insert_with( key, [](value_type&){} );
 415         }
 416
 417         /// Inserts new node
 418         /**
 419             The function creates a node with copy of \p val value
 420             and then inserts the node created into the map.
 421
 422             Preconditions:
 423             - The \ref key_type should be constructible from \p key of type \p K.
 424             - The \ref value_type should be constructible from \p val of type \p V.
 425
 426             Returns \p true if \p val is inserted into the set, \p false otherwise.
 427         */
 428         template <typename K, typename V>
 429         bool insert( K const& key, V const& val )
 430         {
 431             return insert_with( key, [&val](value_type& item) { item.second = val ; } );
 432         }
 433
 434         /// Inserts new node and initialize it by a functor
 435         /**
 436             This function inserts new node with key \p key and if inserting is successful then it calls
 437             \p func functor with signature
 438             \code
 439                 struct functor {
 440                     void operator()( value_type& item );
 441                 };
 442             \endcode
 443
 444             The argument \p item of user-defined functor \p func is the reference
 445             to the map's item inserted:
 446                 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
 447                 - <tt>item.second</tt> is a reference to item's value that may be changed.
 448
 449             The key_type should be constructible from value of type \p K.
 450
 451             The function allows to split creating of new item into two part:
 452             - create item from \p key;
 453             - insert new item into the map;
 454             - if inserting is successful, initialize the value of item by calling \p func functor
 455
 456             This can be useful if complete initialization of object of \p value_type is heavyweight and
 457             it is preferable that the initialization should be completed only if inserting is successful.
 458         */
 459         template <typename K, typename Func>
 460         bool insert_with( const K& key, Func func )
 461         {
 462             scoped_node_ptr pNode( alloc_node( key ));
 463             if ( base_class::insert( *pNode, [&func]( node_type& item ) { func( item.m_val ); } )) {
 464                 pNode.release();
 465                 return true;
 466             }
 467             return false;
 468         }
 469
 470         /// For key \p key inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 471         /**
 472             Returns \p true if inserting successful, \p false otherwise.
 473         */
 474         template <typename K, typename... Args>
 475         bool emplace( K&& key, Args&&... args )
 476         {
 477             scoped_node_ptr pNode( alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
 478             if ( base_class::insert( *pNode )) {
 479                 pNode.release();
 480                 return true;
 481             }
 482             return false;
 483         }
 484
 485         /// Updates the node
 486         /**
 487             The operation performs inserting or changing data with lock-free manner.
 488
 489             If \p key is not found in the map, then \p key is inserted iff \p bAllowInsert is \p true.
 490             Otherwise, the functor \p func is called with item found.
 491             The functor \p func signature is:
 492             \code
 493                 struct my_functor {
 494                     void operator()( bool bNew, value_type& item );
 495                 };
 496             \endcode
 497             with arguments:
 498             - \p bNew - \p true if the item has been inserted, \p false otherwise
 499             - \p item - an item of the map for \p key
 500
 501             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 502             i.e. the node has been inserted or updated,
 503             \p second is \p true if new item has been added or \p false if the item with \p key
 504             already exists.
 505         */
 506         template <typename K, typename Func>
 507         std::pair<bool, bool> update( K const& key, Func func, bool bAllowInsert = true )
 508         {
 509             scoped_node_ptr pNode( alloc_node( key ));
 510             std::pair<bool, bool> res = base_class::update( *pNode,
 511                 [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_val ); },
 512                 bAllowInsert
 513             );
 514             if ( res.first && res.second )
 515                 pNode.release();
 516             return res;
 517         }
 518         //@cond
 519         template <typename K, typename Func>
 520         CDS_DEPRECATED("ensure() is deprecated, use update()")
 521         std::pair<bool, bool> ensure( K const& key, Func func )
 522         {
 523             return update( key, func, true );
 524         }
 525         //@endcond
 526
 527         /// Delete \p key from the map
 528         /** \anchor cds_nonintrusive_CuckooMap_erase_val
 529
 530             Return \p true if \p key is found and deleted, \p false otherwise
 531         */
 532         template <typename K>
 533         bool erase( K const& key )
 534         {
 535             node_type * pNode = base_class::erase(key);
 536             if ( pNode ) {
 537                 free_node( pNode );
 538                 return true;
 539             }
 540             return false;
 541         }
 542
 543         /// Deletes the item from the list using \p pred predicate for searching
 544         /**
 545             The function is an analog of \ref cds_nonintrusive_CuckooMap_erase_val "erase(Q const&)"
 546             but \p pred is used for key comparing.
 547             If cuckoo map is ordered, then \p Predicate should have the interface and semantics like \p std::less.
 548             If cuckoo map is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
 549             \p Predicate must imply the same element order as the comparator used for building the map.
 550         */
 551         template <typename K, typename Predicate>
 552         bool erase_with( K const& key, Predicate pred )
 553         {
 554             CDS_UNUSED( pred );
 555             node_type * pNode = base_class::erase_with(key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>());
 556             if ( pNode ) {
 557                 free_node( pNode );
 558                 return true;
 559             }
 560             return false;
 561         }
 562
 563         /// Delete \p key from the map
 564         /** \anchor cds_nonintrusive_CuckooMap_erase_func
 565
 566             The function searches an item with key \p key, calls \p f functor
 567             and deletes the item. If \p key is not found, the functor is not called.
 568
 569             The functor \p Func interface:
 570             \code
 571             struct extractor {
 572                 void operator()(value_type& item) { ... }
 573             };
 574             \endcode
 575
 576             Return \p true if key is found and deleted, \p false otherwise
 577
 578             See also: \ref erase
 579         */
 580         template <typename K, typename Func>
 581         bool erase( K const& key, Func f )
 582         {
 583             node_type * pNode = base_class::erase( key );
 584             if ( pNode ) {
 585                 f( pNode->m_val );
 586                 free_node( pNode );
 587                 return true;
 588             }
 589             return false;
 590         }
 591
 592         /// Deletes the item from the list using \p pred predicate for searching
 593         /**
 594             The function is an analog of \ref cds_nonintrusive_CuckooMap_erase_func "erase(Q const&, Func)"
 595             but \p pred is used for key comparing.
 596             If cuckoo map is ordered, then \p Predicate should have the interface and semantics like \p std::less.
 597             If cuckoo map is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
 598             \p Predicate must imply the same element order as the comparator used for building the map.
 599         */
 600         template <typename K, typename Predicate, typename Func>
 601         bool erase_with( K const& key, Predicate pred, Func f )
 602         {
 603             CDS_UNUSED( pred );
 604             node_type * pNode = base_class::erase_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
 605             if ( pNode ) {
 606                 f( pNode->m_val );
 607                 free_node( pNode );
 608                 return true;
 609             }
 610             return false;
 611         }
 612
 613         /// Find the key \p key
 614         /** \anchor cds_nonintrusive_CuckooMap_find_func
 615
 616             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 617             The interface of \p Func functor is:
 618             \code
 619             struct functor {
 620                 void operator()( value_type& item );
 621             };
 622             \endcode
 623             where \p item is the item found.
 624
 625             The functor may change \p item.second.
 626
 627             The function returns \p true if \p key is found, \p false otherwise.
 628         */
 629         template <typename K, typename Func>
 630         bool find( K const& key, Func f )
 631         {
 632             return base_class::find( key, [&f](node_type& item, K const& ) { f( item.m_val );});
 633         }
 634
 635         /// Find the key \p val using \p pred predicate for comparing
 636         /**
 637             The function is an analog of \ref cds_nonintrusive_CuckooMap_find_func "find(K const&, Func)"
 638             but \p pred is used for key comparison.
 639             If you use ordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::less.
 640             If you use unordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::equal_to.
 641             \p pred must imply the same element order as the comparator used for building the map.
 642         */
 643         template <typename K, typename Predicate, typename Func>
 644         bool find_with( K const& key, Predicate pred, Func f )
 645         {
 646             CDS_UNUSED( pred );
 647             return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>(),
 648                 [&f](node_type& item, K const& ) { f( item.m_val );});
 649         }
 650
 651         /// Checks whether the map contains \p key
 652         /**
 653             The function searches the item with key equal to \p key
 654             and returns \p true if it is found, and \p false otherwise.
 655         */
 656         template <typename K>
 657         bool contains( K const& key )
 658         {
 659             return base_class::contains( key );
 660         }
 661         //@cond
 662         template <typename K>
 663         CDS_DEPRECATED("the function is deprecated, use contains()")
 664         bool find( K const& key )
 665         {
 666             return contains( key );
 667         }
 668         //@endcond
 669
 670         /// Checks whether the map contains \p key using \p pred predicate for searching
 671         /**
 672             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
 673             \p Less functor has the interface like \p std::less.
 674             \p Less must imply the same element order as the comparator used for building the map.
 675         */
 676         template <typename K, typename Predicate>
 677         bool contains( K const& key, Predicate pred )
 678         {
 679             CDS_UNUSED( pred );
 680             return base_class::contains( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
 681         }
 682         //@cond
 683         template <typename K, typename Predicate>
 684         CDS_DEPRECATED("the function is deprecated, use contains()")
 685         bool find_with( K const& key, Predicate pred )
 686         {
 687             return contains( key, pred );
 688         }
 689         //@endcond
 690
 691         /// Clears the map
 692         void clear()
 693         {
 694             base_class::clear_and_dispose( node_disposer() );
 695         }
 696
 697         /// Checks if the map is empty
 698         /**
 699             Emptiness is checked by item counting: if item count is zero then the map is empty.
 700         */
 701         bool empty() const
 702         {
 703             return base_class::empty();
 704         }
 705
 706         /// Returns item count in the map
 707         size_t size() const
 708         {
 709             return base_class::size();
 710         }
 711
 712         /// Returns the size of hash table
 713         /**
 714             The hash table size is non-constant and can be increased via resizing.
 715         */
 716         size_t bucket_count() const
 717         {
 718             return base_class::bucket_count();
 719         }
 720
 721         /// Returns lock array size
 722         /**
 723             The lock array size is constant.
 724         */
 725         size_t lock_count() const
 726         {
 727             return base_class::lock_count();
 728         }
 729
 730         /// Returns const reference to internal statistics
 731         stat const& statistics() const
 732         {
 733             return base_class::statistics();
 734         }
 735
 736         /// Returns const reference to mutex policy internal statistics
 737         typename mutex_policy::statistics_type const& mutex_policy_statistics() const
 738         {
 739             return base_class::mutex_policy_statistics();
 740         }
 741     };
 742 }}  // namespace cds::container
 743
 744 #endif //#ifndef CDSLIB_CONTAINER_CUCKOO_MAP_H