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         //@cond
 271         typedef cds::container::cuckoo::implementation_tag implementation_tag;
 272         //@endcond
 273
 274     protected:
 275         //@cond
 276         typedef typename base_class::scoped_cell_lock   scoped_cell_lock;
 277         typedef typename base_class::scoped_full_lock   scoped_full_lock;
 278         typedef typename base_class::scoped_resize_lock scoped_resize_lock;
 279         typedef typename maker::key_accessor            key_accessor;
 280
 281         typedef typename base_class::value_type         node_type;
 282         typedef cds::details::Allocator< node_type, node_allocator >    cxx_node_allocator;
 283         //@endcond
 284
 285     public:
 286         static unsigned int const   c_nDefaultProbesetSize = base_class::c_nDefaultProbesetSize; ///< default probeset size
 287         static size_t const         c_nDefaultInitialSize = base_class::c_nDefaultInitialSize;   ///< default initial size
 288         static unsigned int const   c_nRelocateLimit = base_class::c_nRelocateLimit;             ///< Count of attempts to relocate before giving up
 289
 290     protected:
 291         //@cond
 292         template <typename K>
 293         static node_type * alloc_node( K const& key )
 294         {
 295             return cxx_node_allocator().New( key );
 296         }
 297         template <typename K, typename... Args>
 298         static node_type * alloc_node( K&& key, Args&&... args )
 299         {
 300             return cxx_node_allocator().MoveNew( std::forward<K>( key ), std::forward<Args>(args)... );
 301         }
 302
 303         static void free_node( node_type * pNode )
 304         {
 305             cxx_node_allocator().Delete( pNode );
 306         }
 307         //@endcond
 308
 309     protected:
 310         //@cond
 311         struct node_disposer {
 312             void operator()( node_type * pNode )
 313             {
 314                 free_node( pNode );
 315             }
 316         };
 317
 318         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 319
 320         //@endcond
 321
 322     public:
 323         /// Default constructor
 324         /**
 325             Initial size = \ref c_nDefaultInitialSize
 326
 327             Probe set size:
 328             - \ref c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
 329             - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
 330
 331             Probe set threshold = probe set size - 1
 332         */
 333         CuckooMap()
 334         {}
 335
 336         /// Constructs an object with given probe set size and threshold
 337         /**
 338             If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
 339             then \p nProbesetSize should be equal to vector's \p Capacity.
 340         */
 341         CuckooMap(
 342             size_t nInitialSize                     ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
 343             , unsigned int nProbesetSize            ///< probe set size
 344             , unsigned int nProbesetThreshold = 0   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
 345         )
 346         : base_class( nInitialSize, nProbesetSize, nProbesetThreshold )
 347         {}
 348
 349         /// Constructs an object with given hash functor tuple
 350         /**
 351             The probe set size and threshold are set as default, see CuckooSet()
 352         */
 353         CuckooMap(
 354             hash_tuple_type const& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
 355         )
 356         : base_class( h )
 357         {}
 358
 359         /// Constructs a map with given probe set properties and hash functor tuple
 360         /**
 361             If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
 362             then \p nProbesetSize should be equal to vector's \p Capacity.
 363         */
 364         CuckooMap(
 365             size_t nInitialSize                 ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
 366             , unsigned int nProbesetSize        ///< probe set size
 367             , unsigned int nProbesetThreshold   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
 368             , hash_tuple_type const& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
 369         )
 370         : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, h )
 371         {}
 372
 373         /// Constructs a map with given hash functor tuple (move semantics)
 374         /**
 375             The probe set size and threshold are set as default, see CuckooSet()
 376         */
 377         CuckooMap(
 378             hash_tuple_type&& h     ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
 379         )
 380         : base_class( std::forward<hash_tuple_type>(h) )
 381         {}
 382
 383         /// Constructs a map with given probe set properties and hash functor tuple (move semantics)
 384         /**
 385             If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
 386             then \p nProbesetSize should be equal to vector's \p Capacity.
 387         */
 388         CuckooMap(
 389             size_t nInitialSize                 ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
 390             , unsigned int nProbesetSize        ///< probe set size
 391             , unsigned int nProbesetThreshold   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
 392             , hash_tuple_type&& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
 393         )
 394         : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h) )
 395         {}
 396
 397         /// Destructor clears the map
 398         ~CuckooMap()
 399         {
 400             clear();
 401         }
 402
 403     public:
 404         /// Inserts new node with key and default value
 405         /**
 406             The function creates a node with \p key and default value, and then inserts the node created into the map.
 407
 408             Preconditions:
 409             - The \ref key_type should be constructible from a value of type \p K.
 410                 In trivial case, \p K is equal to \ref key_type.
 411             - The \ref mapped_type should be default-constructible.
 412
 413             Returns \p true if inserting successful, \p false otherwise.
 414         */
 415         template <typename K>
 416         bool insert( K const& key )
 417         {
 418             return insert_with( key, [](value_type&){} );
 419         }
 420
 421         /// Inserts new node
 422         /**
 423             The function creates a node with copy of \p val value
 424             and then inserts the node created into the map.
 425
 426             Preconditions:
 427             - The \ref key_type should be constructible from \p key of type \p K.
 428             - The \ref value_type should be constructible from \p val of type \p V.
 429
 430             Returns \p true if \p val is inserted into the set, \p false otherwise.
 431         */
 432         template <typename K, typename V>
 433         bool insert( K const& key, V const& val )
 434         {
 435             return insert_with( key, [&val](value_type& item) { item.second = val ; } );
 436         }
 437
 438         /// Inserts new node and initialize it by a functor
 439         /**
 440             This function inserts new node with key \p key and if inserting is successful then it calls
 441             \p func functor with signature
 442             \code
 443                 struct functor {
 444                     void operator()( value_type& item );
 445                 };
 446             \endcode
 447
 448             The argument \p item of user-defined functor \p func is the reference
 449             to the map's item inserted:
 450                 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
 451                 - <tt>item.second</tt> is a reference to item's value that may be changed.
 452
 453             The key_type should be constructible from value of type \p K.
 454
 455             The function allows to split creating of new item into two part:
 456             - create item from \p key;
 457             - insert new item into the map;
 458             - if inserting is successful, initialize the value of item by calling \p func functor
 459
 460             This can be useful if complete initialization of object of \p value_type is heavyweight and
 461             it is preferable that the initialization should be completed only if inserting is successful.
 462         */
 463         template <typename K, typename Func>
 464         bool insert_with( const K& key, Func func )
 465         {
 466             scoped_node_ptr pNode( alloc_node( key ));
 467             if ( base_class::insert( *pNode, [&func]( node_type& item ) { func( item.m_val ); } )) {
 468                 pNode.release();
 469                 return true;
 470             }
 471             return false;
 472         }
 473
 474         /// For key \p key inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 475         /**
 476             Returns \p true if inserting successful, \p false otherwise.
 477         */
 478         template <typename K, typename... Args>
 479         bool emplace( K&& key, Args&&... args )
 480         {
 481             scoped_node_ptr pNode( alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
 482             if ( base_class::insert( *pNode )) {
 483                 pNode.release();
 484                 return true;
 485             }
 486             return false;
 487         }
 488
 489         /// Ensures that the \p key exists in the map
 490         /**
 491             The operation performs inserting or changing data with lock-free manner.
 492
 493             If the \p key not found in the map, then the new item created from \p key
 494             is inserted into the map (note that in this case the \ref key_type should be
 495             constructible from type \p K).
 496             Otherwise, the functor \p func is called with item found.
 497             The functor \p Func may be a function with signature:
 498             \code
 499                 void func( bool bNew, value_type& item );
 500             \endcode
 501             or a functor:
 502             \code
 503                 struct my_functor {
 504                     void operator()( bool bNew, value_type& item );
 505                 };
 506             \endcode
 507
 508             with arguments:
 509             - \p bNew - \p true if the item has been inserted, \p false otherwise
 510             - \p item - item of the list
 511
 512             The functor may change any fields of the \p item.second that is \ref value_type.
 513
 514             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 515             \p second is true if new item has been added or \p false if the item with \p key
 516             already is in the list.
 517         */
 518         template <typename K, typename Func>
 519         std::pair<bool, bool> ensure( K const& key, Func func )
 520         {
 521             scoped_node_ptr pNode( alloc_node( key ));
 522             std::pair<bool, bool> res = base_class::ensure( *pNode,
 523                 [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_val ); }
 524             );
 525             if ( res.first && res.second )
 526                 pNode.release();
 527             return res;
 528         }
 529
 530         /// Delete \p key from the map
 531         /** \anchor cds_nonintrusive_CuckooMap_erase_val
 532
 533             Return \p true if \p key is found and deleted, \p false otherwise
 534         */
 535         template <typename K>
 536         bool erase( K const& key )
 537         {
 538             node_type * pNode = base_class::erase(key);
 539             if ( pNode ) {
 540                 free_node( pNode );
 541                 return true;
 542             }
 543             return false;
 544         }
 545
 546         /// Deletes the item from the list using \p pred predicate for searching
 547         /**
 548             The function is an analog of \ref cds_nonintrusive_CuckooMap_erase_val "erase(Q const&)"
 549             but \p pred is used for key comparing.
 550             If cuckoo map is ordered, then \p Predicate should have the interface and semantics like \p std::less.
 551             If cuckoo map is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
 552             \p Predicate must imply the same element order as the comparator used for building the map.
 553         */
 554         template <typename K, typename Predicate>
 555         bool erase_with( K const& key, Predicate pred )
 556         {
 557             CDS_UNUSED( pred );
 558             node_type * pNode = base_class::erase_with(key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>());
 559             if ( pNode ) {
 560                 free_node( pNode );
 561                 return true;
 562             }
 563             return false;
 564         }
 565
 566         /// Delete \p key from the map
 567         /** \anchor cds_nonintrusive_CuckooMap_erase_func
 568
 569             The function searches an item with key \p key, calls \p f functor
 570             and deletes the item. If \p key is not found, the functor is not called.
 571
 572             The functor \p Func interface:
 573             \code
 574             struct extractor {
 575                 void operator()(value_type& item) { ... }
 576             };
 577             \endcode
 578
 579             Return \p true if key is found and deleted, \p false otherwise
 580
 581             See also: \ref erase
 582         */
 583         template <typename K, typename Func>
 584         bool erase( K const& key, Func f )
 585         {
 586             node_type * pNode = base_class::erase( key );
 587             if ( pNode ) {
 588                 f( pNode->m_val );
 589                 free_node( pNode );
 590                 return true;
 591             }
 592             return false;
 593         }
 594
 595         /// Deletes the item from the list using \p pred predicate for searching
 596         /**
 597             The function is an analog of \ref cds_nonintrusive_CuckooMap_erase_func "erase(Q const&, Func)"
 598             but \p pred is used for key comparing.
 599             If cuckoo map is ordered, then \p Predicate should have the interface and semantics like \p std::less.
 600             If cuckoo map is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
 601             \p Predicate must imply the same element order as the comparator used for building the map.
 602         */
 603         template <typename K, typename Predicate, typename Func>
 604         bool erase_with( K const& key, Predicate pred, Func f )
 605         {
 606             CDS_UNUSED( pred );
 607             node_type * pNode = base_class::erase_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
 608             if ( pNode ) {
 609                 f( pNode->m_val );
 610                 free_node( pNode );
 611                 return true;
 612             }
 613             return false;
 614         }
 615
 616         /// Find the key \p key
 617         /** \anchor cds_nonintrusive_CuckooMap_find_func
 618
 619             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 620             The interface of \p Func functor is:
 621             \code
 622             struct functor {
 623                 void operator()( value_type& item );
 624             };
 625             \endcode
 626             where \p item is the item found.
 627
 628             The functor may change \p item.second.
 629
 630             The function returns \p true if \p key is found, \p false otherwise.
 631         */
 632         template <typename K, typename Func>
 633         bool find( K const& key, Func f )
 634         {
 635             return base_class::find( key, [&f](node_type& item, K const& ) { f( item.m_val );});
 636         }
 637
 638         /// Find the key \p val using \p pred predicate for comparing
 639         /**
 640             The function is an analog of \ref cds_nonintrusive_CuckooMap_find_func "find(K const&, Func)"
 641             but \p pred is used for key comparison.
 642             If you use ordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::less.
 643             If you use unordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::equal_to.
 644             \p pred must imply the same element order as the comparator used for building the map.
 645         */
 646         template <typename K, typename Predicate, typename Func>
 647         bool find_with( K const& key, Predicate pred, Func f )
 648         {
 649             CDS_UNUSED( pred );
 650             return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>(),
 651                 [&f](node_type& item, K const& ) { f( item.m_val );});
 652         }
 653
 654         /// Find the key \p key
 655         /** \anchor cds_nonintrusive_CuckooMap_find_val
 656
 657             The function searches the item with key equal to \p key
 658             and returns \p true if it is found, and \p false otherwise.
 659         */
 660         template <typename K>
 661         bool find( K const& key )
 662         {
 663             return base_class::find( key );
 664         }
 665
 666         /// Find the key \p val using \p pred predicate for comparing
 667         /**
 668             The function is an analog of \ref cds_nonintrusive_CuckooMap_find_val "find(K const&)"
 669             but \p pred is used for key comparison.
 670             If you use ordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::less.
 671             If you use unordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::equal_to.
 672             \p pred must imply the same element order as the comparator used for building the map.
 673         */
 674         template <typename K, typename Predicate>
 675         bool find_with( K const& key, Predicate pred )
 676         {
 677             CDS_UNUSED( pred );
 678             return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
 679         }
 680
 681         /// Clears the map
 682         void clear()
 683         {
 684             base_class::clear_and_dispose( node_disposer() );
 685         }
 686
 687         /// Checks if the map is empty
 688         /**
 689             Emptiness is checked by item counting: if item count is zero then the map is empty.
 690         */
 691         bool empty() const
 692         {
 693             return base_class::empty();
 694         }
 695
 696         /// Returns item count in the map
 697         size_t size() const
 698         {
 699             return base_class::size();
 700         }
 701
 702         /// Returns the size of hash table
 703         /**
 704             The hash table size is non-constant and can be increased via resizing.
 705         */
 706         size_t bucket_count() const
 707         {
 708             return base_class::bucket_count();
 709         }
 710
 711         /// Returns lock array size
 712         /**
 713             The lock array size is constant.
 714         */
 715         size_t lock_count() const
 716         {
 717             return base_class::lock_count();
 718         }
 719
 720         /// Returns const reference to internal statistics
 721         stat const& statistics() const
 722         {
 723             return base_class::statistics();
 724         }
 725
 726         /// Returns const reference to mutex policy internal statistics
 727         typename mutex_policy::statistics_type const& mutex_policy_statistics() const
 728         {
 729             return base_class::mutex_policy_statistics();
 730         }
 731     };
 732 }}  // namespace cds::container
 733
 734 #endif //#ifndef CDSLIB_CONTAINER_CUCKOO_MAP_H