cds/container/cuckoo_set.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_CUCKOO_SET_H
   4 #define CDSLIB_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         /// Updates the node
 535         /**
 536             The operation performs inserting or changing data with lock-free manner.
 537
 538             If the item \p val is not found in the set, then \p val is inserted into the set
 539             iff \p bAllowInsert is \p true.
 540             Otherwise, the functor \p func is called with item found.
 541             The functor \p func signature is:
 542             \code
 543                 struct my_functor {
 544                     void operator()( bool bNew, value_type& item, const Q& val );
 545                 };
 546             \endcode
 547             with arguments:
 548             - \p bNew - \p true if the item has been inserted, \p false otherwise
 549             - \p item - item of the set
 550             - \p val - argument \p val passed into the \p %update() function
 551             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 552             refer to the same thing.
 553
 554             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 555             i.e. the node has been inserted or updated,
 556             \p second is \p true if new item has been added or \p false if the item with \p key
 557             already exists.
 558         */
 559         template <typename Q, typename Func>
 560         std::pair<bool, bool> update( Q const& val, Func func, bool bAllowInsert = true )
 561         {
 562             scoped_node_ptr pNode( alloc_node( val ));
 563             std::pair<bool, bool> res = base_class::update( *pNode,
 564                 [&val,&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_val, val ); },
 565                 bAllowInsert
 566             );
 567             if ( res.first && res.second )
 568                 pNode.release();
 569             return res;
 570         }
 571         //@cond
 572         template <typename Q, typename Func>
 573         CDS_DEPRECATED("ensure() is deprecated, use update()")
 574         std::pair<bool, bool> ensure( Q const& val, Func func )
 575         {
 576             return update( val, func, true );
 577         }
 578         //@endcond
 579
 580         /// Delete \p key from the set
 581         /** \anchor cds_nonintrusive_CuckooSet_erase
 582
 583             Since the key of set's item type \ref value_type is not explicitly specified,
 584             template parameter \p Q defines the key type searching in the list.
 585             The set item comparator should be able to compare the type \p value_type
 586             and the type \p Q.
 587
 588             Return \p true if key is found and deleted, \p false otherwise
 589         */
 590         template <typename Q>
 591         bool erase( Q const& key )
 592         {
 593             node_type * pNode = base_class::erase( key );
 594             if ( pNode ) {
 595                 free_node( pNode );
 596                 return true;
 597             }
 598             return false;
 599         }
 600
 601         /// Deletes the item from the list using \p pred predicate for searching
 602         /**
 603             The function is an analog of \ref cds_nonintrusive_CuckooSet_erase "erase(Q const&)"
 604             but \p pred is used for key comparing.
 605             If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
 606             If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
 607             \p Predicate must imply the same element order as the comparator used for building the set.
 608         */
 609         template <typename Q, typename Predicate>
 610         bool erase_with( Q const& key, Predicate pred )
 611         {
 612             CDS_UNUSED( pred );
 613             node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>() );
 614             if ( pNode ) {
 615                 free_node( pNode );
 616                 return true;
 617             }
 618             return false;
 619         }
 620
 621         /// Delete \p key from the set
 622         /** \anchor cds_nonintrusive_CuckooSet_erase_func
 623
 624             The function searches an item with key \p key, calls \p f functor
 625             and deletes the item. If \p key is not found, the functor is not called.
 626
 627             The functor \p Func interface is:
 628             \code
 629             struct functor {
 630                 void operator()(value_type const& val);
 631             };
 632             \endcode
 633
 634             Return \p true if key is found and deleted, \p false otherwise
 635         */
 636         template <typename Q, typename Func>
 637         bool erase( Q const& key, Func f )
 638         {
 639             node_type * pNode = base_class::erase( key );
 640             if ( pNode ) {
 641                 f( pNode->m_val );
 642                 free_node( pNode );
 643                 return true;
 644             }
 645             return false;
 646         }
 647
 648         /// Deletes the item from the list using \p pred predicate for searching
 649         /**
 650             The function is an analog of \ref cds_nonintrusive_CuckooSet_erase_func "erase(Q const&, Func)"
 651             but \p pred is used for key comparing.
 652             If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
 653             If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
 654             \p Predicate must imply the same element order as the comparator used for building the set.
 655         */
 656         template <typename Q, typename Predicate, typename Func>
 657         bool erase_with( Q const& key, Predicate pred, Func f )
 658         {
 659             CDS_UNUSED( pred );
 660             node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>() );
 661             if ( pNode ) {
 662                 f( pNode->m_val );
 663                 free_node( pNode );
 664                 return true;
 665             }
 666             return false;
 667         }
 668
 669         /// Find the key \p val
 670         /** \anchor cds_nonintrusive_CuckooSet_find_func
 671
 672             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 673             The interface of \p Func functor is:
 674             \code
 675             struct functor {
 676                 void operator()( value_type& item, Q& val );
 677             };
 678             \endcode
 679             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 680
 681             The functor can change non-key fields of \p item.
 682             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 683             can modify both arguments.
 684
 685             The type \p Q can differ from \ref value_type of items storing in the container.
 686             Therefore, the \p value_type should be comparable with type \p Q.
 687
 688             The function returns \p true if \p val is found, \p false otherwise.
 689         */
 690         template <typename Q, typename Func>
 691         bool find( Q& val, Func f )
 692         {
 693             return base_class::find( val, [&f](node_type& item, Q& v) { f( item.m_val, v );});
 694         }
 695         //@cond
 696         template <typename Q, typename Func>
 697         bool find( Q const& val, Func f )
 698         {
 699             return base_class::find( val, [&f](node_type& item, Q const& v) { f( item.m_val, v );});
 700         }
 701         //@endcond
 702
 703         /// Find the key \p val using \p pred predicate for comparing
 704         /**
 705             The function is an analog of \ref cds_nonintrusive_CuckooSet_find_func "find(Q&, Func)"
 706             but \p pred is used for key comparison.
 707             If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
 708             If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
 709             \p pred must imply the same element order as the comparator used for building the set.
 710         */
 711         template <typename Q, typename Predicate, typename Func>
 712         bool find_with( Q& val, Predicate pred, Func f )
 713         {
 714             CDS_UNUSED( pred );
 715             return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(),
 716                 [&f](node_type& item, Q& v) { f( item.m_val, v );});
 717         }
 718         //@cond
 719         template <typename Q, typename Predicate, typename Func>
 720         bool find_with( Q const& val, Predicate pred, Func f )
 721         {
 722             CDS_UNUSED( pred );
 723             return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(),
 724                 [&f](node_type& item, Q const& v) { f( item.m_val, v );});
 725         }
 726         //@endcond
 727
 728         /// Checks whether the set contains \p key
 729         /**
 730             The function searches the item with key equal to \p key
 731             and returns \p true if it is found, and \p false otherwise.
 732         */
 733         template <typename Q>
 734         bool contains( Q const& key )
 735         {
 736             return base_class::find( key, [](node_type&, Q const&) {});
 737         }
 738         //@cond
 739         template <typename Q>
 740         CDS_DEPRECATED("the function is deprecated, use contains()")
 741         bool find( Q const& key )
 742         {
 743             return contains( key );
 744         }
 745         //@endcond
 746
 747         /// Checks whether the set contains \p key using \p pred predicate for searching
 748         /**
 749             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
 750             \p Less functor has the interface like \p std::less.
 751             \p Less must imply the same element order as the comparator used for building the set.
 752         */
 753         template <typename Q, typename Predicate>
 754         bool contains( Q const& key, Predicate pred )
 755         {
 756             CDS_UNUSED( pred );
 757             return base_class::find_with( key, typename maker::template predicate_wrapper<Predicate, bool>(), [](node_type&, Q const&) {});
 758         }
 759         //@cond
 760         template <typename Q, typename Predicate>
 761         CDS_DEPRECATED("the function is deprecated, use contains()")
 762         bool find_with( Q const& key, Predicate pred )
 763         {
 764             return contains( key, pred );
 765         }
 766         //@endcond
 767
 768         /// Clears the set
 769         /**
 770             The function erases all items from the set.
 771         */
 772         void clear()
 773         {
 774             return base_class::clear_and_dispose( node_disposer() );
 775         }
 776
 777         /// Checks if the set is empty
 778         /**
 779             Emptiness is checked by item counting: if item count is zero then the set is empty.
 780         */
 781         bool empty() const
 782         {
 783             return base_class::empty();
 784         }
 785
 786         /// Returns item count in the set
 787         size_t size() const
 788         {
 789             return base_class::size();
 790         }
 791
 792         /// Returns the size of hash table
 793         /**
 794             The hash table size is non-constant and can be increased via resizing.
 795         */
 796         size_t bucket_count() const
 797         {
 798             return base_class::bucket_count();
 799         }
 800
 801         /// Returns lock array size
 802         size_t lock_count() const
 803         {
 804             return base_class::lock_count();
 805         }
 806
 807         /// Returns const reference to internal statistics
 808         stat const& statistics() const
 809         {
 810             return base_class::statistics();
 811         }
 812
 813         /// Returns const reference to mutex policy internal statistics
 814         typename mutex_policy::statistics_type const& mutex_policy_statistics() const
 815         {
 816             return base_class::mutex_policy_statistics();
 817         }
 818     };
 819
 820 }} // namespace cds::container
 821
 822 #endif //#ifndef CDSLIB_CONTAINER_CUCKOO_SET_H