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