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