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         //@cond
 349         typedef cds::container::cuckoo::implementation_tag implementation_tag;
 350         //@endcond
 351
 352     protected:
 353         //@cond
 354         typedef typename base_class::value_type         node_type;
 355         typedef cds::details::Allocator< node_type, node_allocator >    cxx_node_allocator;
 356         //@endcond
 357
 358     public:
 359         static unsigned int const   c_nDefaultProbesetSize = base_class::c_nDefaultProbesetSize; ///< default probeset size
 360         static size_t const         c_nDefaultInitialSize = base_class::c_nDefaultInitialSize;   ///< default initial size
 361         static unsigned int const   c_nRelocateLimit = base_class::c_nRelocateLimit;             ///< Count of attempts to relocate before giving up
 362
 363     protected:
 364         //@cond
 365         template <typename Q>
 366         static node_type * alloc_node( Q const& v )
 367         {
 368             return cxx_node_allocator().New( v );
 369         }
 370         template <typename... Args>
 371         static node_type * alloc_node( Args&&... args )
 372         {
 373             return cxx_node_allocator().MoveNew( std::forward<Args>(args)... );
 374         }
 375
 376         static void free_node( node_type * pNode )
 377         {
 378             cxx_node_allocator().Delete( pNode );
 379         }
 380         //@endcond
 381
 382     protected:
 383         //@cond
 384         struct node_disposer {
 385             void operator()( node_type * pNode )
 386             {
 387                 free_node( pNode );
 388             }
 389         };
 390
 391         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 392
 393         //@endcond
 394
 395     public:
 396         /// Default constructor
 397         /**
 398             Initial size = \ref c_nDefaultInitialSize
 399
 400             Probe set size:
 401             - \ref c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
 402             - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
 403
 404             Probe set threshold = probe set size - 1
 405         */
 406         CuckooSet()
 407         {}
 408
 409         /// Constructs the set object with given probe set size and threshold
 410         /**
 411             If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
 412             then \p nProbesetSize should be equal to vector's \p Capacity.
 413         */
 414         CuckooSet(
 415             size_t nInitialSize                 ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
 416             , unsigned int nProbesetSize        ///< probe set size
 417             , unsigned int nProbesetThreshold = 0  ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
 418         )
 419         : base_class( nInitialSize, nProbesetSize, nProbesetThreshold )
 420         {}
 421
 422         /// Constructs the set object with given hash functor tuple
 423         /**
 424             The probe set size and threshold are set as default, see CuckooSet()
 425         */
 426         CuckooSet(
 427             hash_tuple_type const& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
 428         )
 429         : base_class( h )
 430         {}
 431
 432         /// Constructs the set object with given probe set properties and hash functor tuple
 433         /**
 434             If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
 435             then \p nProbesetSize should be equal to vector's \p Capacity.
 436         */
 437         CuckooSet(
 438             size_t nInitialSize                 ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
 439             , unsigned int nProbesetSize        ///< probe set size
 440             , unsigned int nProbesetThreshold   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
 441             , hash_tuple_type const& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
 442         )
 443         : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, h )
 444         {}
 445
 446         /// Constructs the set object with given hash functor tuple (move semantics)
 447         /**
 448             The probe set size and threshold are set as default, see CuckooSet()
 449         */
 450         CuckooSet(
 451             hash_tuple_type&& h     ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
 452         )
 453         : base_class( std::forward<hash_tuple_type>(h) )
 454         {}
 455
 456         /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
 457         /**
 458             If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
 459             then \p nProbesetSize should be equal to vector's \p Capacity.
 460         */
 461         CuckooSet(
 462             size_t nInitialSize                 ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
 463             , unsigned int nProbesetSize        ///< probe set size
 464             , unsigned int nProbesetThreshold   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
 465             , hash_tuple_type&& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
 466         )
 467         : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h) )
 468         {}
 469
 470         /// Destructor clears the set
 471         ~CuckooSet()
 472         {
 473             clear();
 474         }
 475
 476     public:
 477         /// Inserts new node
 478         /**
 479             The function creates a node with copy of \p val value
 480             and then inserts the node created into the set.
 481
 482             The type \p Q should contain as minimum the complete key for the node.
 483             The object of \ref value_type should be constructible from a value of type \p Q.
 484             In trivial case, \p Q is equal to \ref value_type.
 485
 486             Returns \p true if \p val is inserted into the set, \p false otherwise.
 487         */
 488         template <typename Q>
 489         bool insert( Q const& val )
 490         {
 491             return insert( val, []( value_type& ) {} );
 492         }
 493
 494         /// Inserts new node
 495         /**
 496             The function allows to split creating of new item into two part:
 497             - create item with key only
 498             - insert new item into the set
 499             - if inserting is success, calls \p f functor to initialize value-field of new item .
 500
 501             The functor signature is:
 502             \code
 503                 void func( value_type& item );
 504             \endcode
 505             where \p item is the item inserted.
 506
 507             The type \p Q can differ from \ref value_type of items storing in the set.
 508             Therefore, the \p value_type should be constructible from type \p Q.
 509
 510             The user-defined functor is called only if the inserting is success.
 511         */
 512         template <typename Q, typename Func>
 513         bool insert( Q const& val, Func f )
 514         {
 515             scoped_node_ptr pNode( alloc_node( val ));
 516             if ( base_class::insert( *pNode, [&f]( node_type& node ) { f( node.m_val ); } )) {
 517                 pNode.release();
 518                 return true;
 519             }
 520             return false;
 521         }
 522
 523         /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 524         /**
 525             Returns \p true if inserting successful, \p false otherwise.
 526         */
 527         template <typename... Args>
 528         bool emplace( Args&&... args )
 529         {
 530             scoped_node_ptr pNode( alloc_node( std::forward<Args>(args)... ));
 531             if ( base_class::insert( *pNode )) {
 532                 pNode.release();
 533                 return true;
 534             }
 535             return false;
 536         }
 537
 538         /// Ensures that the \p val exists in the set
 539         /**
 540             The operation performs inserting or changing data.
 541
 542             If the \p val key not found in the set, then the new item created from \p val
 543             is inserted into the set. Otherwise, the functor \p func is called with the item found.
 544             The functor \p Func should be a function with signature:
 545             \code
 546                 void func( bool bNew, value_type& item, const Q& val );
 547             \endcode
 548             or a functor:
 549             \code
 550                 struct my_functor {
 551                     void operator()( bool bNew, value_type& item, const Q& val );
 552                 };
 553             \endcode
 554
 555             with arguments:
 556             - \p bNew - \p true if the item has been inserted, \p false otherwise
 557             - \p item - item of the set
 558             - \p val - argument \p val passed into the \p ensure function
 559
 560             The functor can change non-key fields of the \p item.
 561
 562             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 563             \p second is true if new item has been added or \p false if the item with \p val key
 564             already exists.
 565         */
 566         template <typename Q, typename Func>
 567         std::pair<bool, bool> ensure( Q const& val, Func func )
 568         {
 569             scoped_node_ptr pNode( alloc_node( val ));
 570             std::pair<bool, bool> res = base_class::ensure( *pNode,
 571                 [&val,&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_val, val ); }
 572             );
 573             if ( res.first && res.second )
 574                 pNode.release();
 575             return res;
 576         }
 577
 578         /// Delete \p key from the set
 579         /** \anchor cds_nonintrusive_CuckooSet_erase
 580
 581             Since the key of set's item type \ref value_type is not explicitly specified,
 582             template parameter \p Q defines the key type searching in the list.
 583             The set item comparator should be able to compare the type \p value_type
 584             and the type \p Q.
 585
 586             Return \p true if key is found and deleted, \p false otherwise
 587         */
 588         template <typename Q>
 589         bool erase( Q const& key )
 590         {
 591             node_type * pNode = base_class::erase( key );
 592             if ( pNode ) {
 593                 free_node( pNode );
 594                 return true;
 595             }
 596             return false;
 597         }
 598
 599         /// Deletes the item from the list using \p pred predicate for searching
 600         /**
 601             The function is an analog of \ref cds_nonintrusive_CuckooSet_erase "erase(Q const&)"
 602             but \p pred is used for key comparing.
 603             If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
 604             If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
 605             \p Predicate must imply the same element order as the comparator used for building the set.
 606         */
 607         template <typename Q, typename Predicate>
 608         bool erase_with( Q const& key, Predicate pred )
 609         {
 610             CDS_UNUSED( pred );
 611             node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>() );
 612             if ( pNode ) {
 613                 free_node( pNode );
 614                 return true;
 615             }
 616             return false;
 617         }
 618
 619         /// Delete \p key from the set
 620         /** \anchor cds_nonintrusive_CuckooSet_erase_func
 621
 622             The function searches an item with key \p key, calls \p f functor
 623             and deletes the item. If \p key is not found, the functor is not called.
 624
 625             The functor \p Func interface is:
 626             \code
 627             struct functor {
 628                 void operator()(value_type const& val);
 629             };
 630             \endcode
 631
 632             Return \p true if key is found and deleted, \p false otherwise
 633         */
 634         template <typename Q, typename Func>
 635         bool erase( Q const& key, Func f )
 636         {
 637             node_type * pNode = base_class::erase( key );
 638             if ( pNode ) {
 639                 f( pNode->m_val );
 640                 free_node( pNode );
 641                 return true;
 642             }
 643             return false;
 644         }
 645
 646         /// Deletes the item from the list using \p pred predicate for searching
 647         /**
 648             The function is an analog of \ref cds_nonintrusive_CuckooSet_erase_func "erase(Q const&, Func)"
 649             but \p pred is used for key comparing.
 650             If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
 651             If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
 652             \p Predicate must imply the same element order as the comparator used for building the set.
 653         */
 654         template <typename Q, typename Predicate, typename Func>
 655         bool erase_with( Q const& key, Predicate pred, Func f )
 656         {
 657             CDS_UNUSED( pred );
 658             node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>() );
 659             if ( pNode ) {
 660                 f( pNode->m_val );
 661                 free_node( pNode );
 662                 return true;
 663             }
 664             return false;
 665         }
 666
 667         /// Find the key \p val
 668         /** \anchor cds_nonintrusive_CuckooSet_find_func
 669
 670             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 671             The interface of \p Func functor is:
 672             \code
 673             struct functor {
 674                 void operator()( value_type& item, Q& val );
 675             };
 676             \endcode
 677             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 678
 679             The functor can change non-key fields of \p item.
 680             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 681             can modify both arguments.
 682
 683             The type \p Q can differ from \ref value_type of items storing in the container.
 684             Therefore, the \p value_type should be comparable with type \p Q.
 685
 686             The function returns \p true if \p val is found, \p false otherwise.
 687         */
 688         template <typename Q, typename Func>
 689         bool find( Q& val, Func f )
 690         {
 691             return base_class::find( val, [&f](node_type& item, Q& v) { f( item.m_val, v );});
 692         }
 693
 694         /// Find the key \p val using \p pred predicate for comparing
 695         /**
 696             The function is an analog of \ref cds_nonintrusive_CuckooSet_find_func "find(Q&, Func)"
 697             but \p pred is used for key comparison.
 698             If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
 699             If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
 700             \p pred must imply the same element order as the comparator used for building the set.
 701         */
 702         template <typename Q, typename Predicate, typename Func>
 703         bool find_with( Q& val, Predicate pred, Func f )
 704         {
 705             CDS_UNUSED( pred );
 706             return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(),
 707                 [&f](node_type& item, Q& v) { f( item.m_val, v );});
 708         }
 709
 710         /// Find the key \p val
 711         /** \anchor cds_nonintrusive_CuckooSet_find_cfunc
 712
 713             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 714             The interface of \p Func functor is:
 715             \code
 716             struct functor {
 717                 void operator()( value_type& item, Q const& val );
 718             };
 719             \endcode
 720             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 721
 722             The functor can change non-key fields of \p item.
 723
 724             The type \p Q can differ from \ref value_type of items storing in the container.
 725             Therefore, the \p value_type should be comparable with type \p Q.
 726
 727             The function returns \p true if \p val is found, \p false otherwise.
 728         */
 729         template <typename Q, typename Func>
 730         bool find( Q const& val, Func f )
 731         {
 732             return base_class::find( val, [&f](node_type& item, Q const& v) { f( item.m_val, v );});
 733         }
 734
 735         /// Find the key \p val using \p pred predicate for comparing
 736         /**
 737             The function is an analog of \ref cds_nonintrusive_CuckooSet_find_cfunc "find(Q const&, Func)"
 738             but \p pred is used for key comparison.
 739             If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
 740             If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
 741             \p pred must imply the same element order as the comparator used for building the set.
 742         */
 743         template <typename Q, typename Predicate, typename Func>
 744         bool find_with( Q const& val, Predicate pred, Func f )
 745         {
 746             CDS_UNUSED( pred );
 747             return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(),
 748                 [&f](node_type& item, Q const& v) { f( item.m_val, v );});
 749         }
 750
 751         /// Find the key \p val
 752         /** \anchor cds_nonintrusive_CuckooSet_find_val
 753
 754             The function searches the item with key equal to \p val
 755             and returns \p true if it is found, and \p false otherwise.
 756
 757             Note the hash functor specified for class \p Traits template parameter
 758             should accept a parameter of type \p Q that can be not the same as \ref value_type.
 759         */
 760         template <typename Q>
 761         bool find( Q const& val )
 762         {
 763             return base_class::find( val, [](node_type&, Q const&) {});
 764         }
 765
 766         /// Find the key \p val using \p pred predicate for comparing
 767         /**
 768             The function is an analog of \ref cds_nonintrusive_CuckooSet_find_val "find(Q const&)"
 769             but \p pred is used for key comparison.
 770             If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
 771             If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
 772             \p pred must imply the same element order as the comparator used for building the set.
 773         */
 774         template <typename Q, typename Predicate>
 775         bool find_with( Q const& val, Predicate pred )
 776         {
 777             CDS_UNUSED( pred );
 778             return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), [](node_type&, Q const&) {});
 779         }
 780
 781         /// Clears the set
 782         /**
 783             The function erases all items from the set.
 784         */
 785         void clear()
 786         {
 787             return base_class::clear_and_dispose( node_disposer() );
 788         }
 789
 790         /// Checks if the set is empty
 791         /**
 792             Emptiness is checked by item counting: if item count is zero then the set is empty.
 793         */
 794         bool empty() const
 795         {
 796             return base_class::empty();
 797         }
 798
 799         /// Returns item count in the set
 800         size_t size() const
 801         {
 802             return base_class::size();
 803         }
 804
 805         /// Returns the size of hash table
 806         /**
 807             The hash table size is non-constant and can be increased via resizing.
 808         */
 809         size_t bucket_count() const
 810         {
 811             return base_class::bucket_count();
 812         }
 813
 814         /// Returns lock array size
 815         size_t lock_count() const
 816         {
 817             return base_class::lock_count();
 818         }
 819
 820         /// Returns const reference to internal statistics
 821         stat const& statistics() const
 822         {
 823             return base_class::statistics();
 824         }
 825
 826         /// Returns const reference to mutex policy internal statistics
 827         typename mutex_policy::statistics_type const& mutex_policy_statistics() const
 828         {
 829             return base_class::mutex_policy_statistics();
 830         }
 831     };
 832
 833 }} // namespace cds::container
 834
 835 #endif //#ifndef CDSLIB_CONTAINER_CUCKOO_SET_H