cds/container/cuckoo_set.h

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