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         /// Constructs the set object with given hash functor tuple (move semantics)
 539         /**
 540             The probe set size and threshold are set as default, see CuckooSet()
 541         */
 542         CuckooSet(
 543             hash_tuple_type&& h     ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
 544         )
 545         : base_class( std::forward<hash_tuple_type>(h) )
 546         {}
 547
 548         /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
 549         /**
 550             If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
 551             then \p nProbesetSize should be equal to vector's \p Capacity.
 552         */
 553         CuckooSet(
 554             size_t nInitialSize                 ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
 555             , unsigned int nProbesetSize        ///< probe set size
 556             , unsigned int nProbesetThreshold   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
 557             , hash_tuple_type&& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
 558         )
 559         : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h) )
 560         {}
 561
 562         /// Destructor clears the set
 563         ~CuckooSet()
 564         {
 565             clear();
 566         }
 567
 568     public:
 569         /// Inserts new node
 570         /**
 571             The function creates a node with copy of \p val value
 572             and then inserts the node created into the set.
 573
 574             The type \p Q should contain as minimum the complete key for the node.
 575             The object of \ref value_type should be constructible from a value of type \p Q.
 576             In trivial case, \p Q is equal to \ref value_type.
 577
 578             Returns \p true if \p val is inserted into the set, \p false otherwise.
 579         */
 580         template <typename Q>
 581         bool insert( Q const& val )
 582         {
 583 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 584             return insert( val, []( value_type& ) {} );
 585 #       else
 586             return insert( val, empty_insert_functor() );
 587 #       endif
 588         }
 589
 590         /// Inserts new node
 591         /**
 592             The function allows to split creating of new item into two part:
 593             - create item with key only
 594             - insert new item into the set
 595             - if inserting is success, calls \p f functor to initialize value-field of new item .
 596
 597             The functor signature is:
 598             \code
 599                 void func( value_type& item );
 600             \endcode
 601             where \p item is the item inserted.
 602
 603             The type \p Q can differ from \ref value_type of items storing in the set.
 604             Therefore, the \p value_type should be constructible from type \p Q.
 605
 606             The user-defined functor is called only if the inserting is success. It can be passed by reference
 607             using <tt>boost::ref</tt>
 608         */
 609         template <typename Q, typename Func>
 610         bool insert( Q const& val, Func f )
 611         {
 612             scoped_node_ptr pNode( alloc_node( val ));
 613 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 614             if ( base_class::insert( *pNode, [&f]( node_type& node ) { cds::unref(f)( node.m_val ); } ))
 615 #       else
 616             insert_wrapper<Func> wrapper( f );
 617             if ( base_class::insert( *pNode, cds::ref(wrapper) ))
 618 #       endif
 619             {
 620                 pNode.release();
 621                 return true;
 622             }
 623             return false;
 624         }
 625
 626 #   ifdef CDS_EMPLACE_SUPPORT
 627         /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 628         /**
 629             Returns \p true if inserting successful, \p false otherwise.
 630
 631             This function is available only for compiler that supports
 632             variadic template and move semantics
 633         */
 634         template <typename... Args>
 635         bool emplace( Args&&... args )
 636         {
 637             scoped_node_ptr pNode( alloc_node( std::forward<Args>(args)... ));
 638             if ( base_class::insert( *pNode )) {
 639                 pNode.release();
 640                 return true;
 641             }
 642             return false;
 643         }
 644 #   endif
 645
 646         /// Ensures that the \p val exists in the set
 647         /**
 648             The operation performs inserting or changing data.
 649
 650             If the \p val key not found in the set, then the new item created from \p val
 651             is inserted into the set. Otherwise, the functor \p func is called with the item found.
 652             The functor \p Func should be a function with signature:
 653             \code
 654                 void func( bool bNew, value_type& item, const Q& val );
 655             \endcode
 656             or a functor:
 657             \code
 658                 struct my_functor {
 659                     void operator()( bool bNew, value_type& item, const Q& val );
 660                 };
 661             \endcode
 662
 663             with arguments:
 664             - \p bNew - \p true if the item has been inserted, \p false otherwise
 665             - \p item - item of the set
 666             - \p val - argument \p val passed into the \p ensure function
 667
 668             The functor can change non-key fields of the \p item.
 669
 670             You can pass \p func argument by value or by reference using <tt>boost::ref</tt>.
 671
 672             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 673             \p second is true if new item has been added or \p false if the item with \p val key
 674             already exists.
 675         */
 676         template <typename Q, typename Func>
 677         std::pair<bool, bool> ensure( Q const& val, Func func )
 678         {
 679             scoped_node_ptr pNode( alloc_node( val ));
 680 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 681             std::pair<bool, bool> res = base_class::ensure( *pNode,
 682                 [&val,&func](bool bNew, node_type& item, node_type const& ){ cds::unref(func)( bNew, item.m_val, val ); }
 683             );
 684 #       else
 685             ensure_wrapper<Q, Func> wrapper( val, func );
 686             std::pair<bool, bool> res = base_class::ensure( *pNode, cds::ref(wrapper) );
 687 #       endif
 688             if ( res.first && res.second )
 689                 pNode.release();
 690             return res;
 691         }
 692
 693         /// Delete \p key from the set
 694         /** \anchor cds_nonintrusive_CuckooSet_erase
 695
 696             Since the key of set's item type \ref value_type is not explicitly specified,
 697             template parameter \p Q defines the key type searching in the list.
 698             The set item comparator should be able to compare the type \p value_type
 699             and the type \p Q.
 700
 701             Return \p true if key is found and deleted, \p false otherwise
 702         */
 703         template <typename Q>
 704         bool erase( Q const& key )
 705         {
 706             node_type * pNode = base_class::erase( key );
 707             if ( pNode ) {
 708                 free_node( pNode );
 709                 return true;
 710             }
 711             return false;
 712         }
 713
 714         /// Deletes the item from the list using \p pred predicate for searching
 715         /**
 716             The function is an analog of \ref cds_nonintrusive_CuckooSet_erase "erase(Q const&)"
 717             but \p pred is used for key comparing.
 718             If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
 719             If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
 720             \p Predicate must imply the same element order as the comparator used for building the set.
 721         */
 722         template <typename Q, typename Predicate>
 723         bool erase_with( Q const& key, Predicate pred )
 724         {
 725             node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>() );
 726             if ( pNode ) {
 727                 free_node( pNode );
 728                 return true;
 729             }
 730             return false;
 731         }
 732
 733         /// Delete \p key from the set
 734         /** \anchor cds_nonintrusive_CuckooSet_erase_func
 735
 736             The function searches an item with key \p key, calls \p f functor
 737             and deletes the item. If \p key is not found, the functor is not called.
 738
 739             The functor \p Func interface is:
 740             \code
 741             struct functor {
 742                 void operator()(value_type const& val);
 743             };
 744             \endcode
 745             The functor can be passed by value or by reference using <tt>boost:ref</tt>
 746
 747             Return \p true if key is found and deleted, \p false otherwise
 748         */
 749         template <typename Q, typename Func>
 750         bool erase( Q const& key, Func f )
 751         {
 752             node_type * pNode = base_class::erase( key );
 753             if ( pNode ) {
 754                 cds::unref(f)( pNode->m_val );
 755                 free_node( pNode );
 756                 return true;
 757             }
 758             return false;
 759         }
 760
 761         /// Deletes the item from the list using \p pred predicate for searching
 762         /**
 763             The function is an analog of \ref cds_nonintrusive_CuckooSet_erase_func "erase(Q const&, Func)"
 764             but \p pred is used for key comparing.
 765             If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
 766             If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
 767             \p Predicate must imply the same element order as the comparator used for building the set.
 768         */
 769         template <typename Q, typename Predicate, typename Func>
 770         bool erase_with( Q const& key, Predicate pred, Func f )
 771         {
 772             node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>() );
 773             if ( pNode ) {
 774                 cds::unref(f)( pNode->m_val );
 775                 free_node( pNode );
 776                 return true;
 777             }
 778             return false;
 779         }
 780
 781         /// Find the key \p val
 782         /** \anchor cds_nonintrusive_CuckooSet_find_func
 783
 784             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 785             The interface of \p Func functor is:
 786             \code
 787             struct functor {
 788                 void operator()( value_type& item, Q& val );
 789             };
 790             \endcode
 791             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 792
 793             You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
 794
 795             The functor can change non-key fields of \p item.
 796             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 797             can modify both arguments.
 798
 799             The type \p Q can differ from \ref value_type of items storing in the container.
 800             Therefore, the \p value_type should be comparable with type \p Q.
 801
 802             The function returns \p true if \p val is found, \p false otherwise.
 803         */
 804         template <typename Q, typename Func>
 805         bool find( Q& val, Func f )
 806         {
 807 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 808             return base_class::find( val, [&f](node_type& item, Q& v) { cds::unref(f)( item.m_val, v );});
 809 #       else
 810             find_wrapper<Func> wrapper(f);
 811             return base_class::find( val, cds::ref(wrapper) );
 812 #       endif
 813         }
 814
 815         /// Find the key \p val using \p pred predicate for comparing
 816         /**
 817             The function is an analog of \ref cds_nonintrusive_CuckooSet_find_func "find(Q&, Func)"
 818             but \p pred is used for key comparison.
 819             If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
 820             If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
 821             \p pred must imply the same element order as the comparator used for building the set.
 822         */
 823         template <typename Q, typename Predicate, typename Func>
 824         bool find_with( Q& val, Predicate pred, Func f )
 825         {
 826 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 827             return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(),
 828                 [&f](node_type& item, Q& v) { cds::unref(f)( item.m_val, v );});
 829 #       else
 830             find_wrapper<Func> wrapper(f);
 831             return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), cds::ref(wrapper) );
 832 #       endif
 833         }
 834
 835         /// Find the key \p val
 836         /** \anchor cds_nonintrusive_CuckooSet_find_cfunc
 837
 838             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 839             The interface of \p Func functor is:
 840             \code
 841             struct functor {
 842                 void operator()( value_type& item, Q const& val );
 843             };
 844             \endcode
 845             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 846
 847             You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
 848
 849             The functor can change non-key fields of \p item.
 850
 851             The type \p Q can differ from \ref value_type of items storing in the container.
 852             Therefore, the \p value_type should be comparable with type \p Q.
 853
 854             The function returns \p true if \p val is found, \p false otherwise.
 855         */
 856         template <typename Q, typename Func>
 857         bool find( Q const& val, Func f )
 858         {
 859 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 860             return base_class::find( val, [&f](node_type& item, Q const& v) { cds::unref(f)( item.m_val, v );});
 861 #       else
 862             find_wrapper<Func> wrapper(f);
 863             return base_class::find( val, cds::ref(wrapper) );
 864 #       endif
 865         }
 866
 867         /// Find the key \p val using \p pred predicate for comparing
 868         /**
 869             The function is an analog of \ref cds_nonintrusive_CuckooSet_find_cfunc "find(Q const&, Func)"
 870             but \p pred is used for key comparison.
 871             If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
 872             If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
 873             \p pred must imply the same element order as the comparator used for building the set.
 874         */
 875         template <typename Q, typename Predicate, typename Func>
 876         bool find_with( Q const& val, Predicate pred, Func f )
 877         {
 878 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 879             return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(),
 880                 [&f](node_type& item, Q const& v) { cds::unref(f)( item.m_val, v );});
 881 #       else
 882             find_wrapper<Func> wrapper(f);
 883             return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), cds::ref(wrapper) );
 884 #       endif
 885         }
 886
 887         /// Find the key \p val
 888         /** \anchor cds_nonintrusive_CuckooSet_find_val
 889
 890             The function searches the item with key equal to \p val
 891             and returns \p true if it is found, and \p false otherwise.
 892
 893             Note the hash functor specified for class \p Traits template parameter
 894             should accept a parameter of type \p Q that can be not the same as \ref value_type.
 895         */
 896         template <typename Q>
 897         bool find( Q const& val )
 898         {
 899 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 900             return base_class::find( val, [](node_type&, Q const&) {});
 901 #       else
 902             return base_class::find( val, empty_find_functor());
 903 #       endif
 904         }
 905
 906         /// Find the key \p val using \p pred predicate for comparing
 907         /**
 908             The function is an analog of \ref cds_nonintrusive_CuckooSet_find_val "find(Q const&)"
 909             but \p pred is used for key comparison.
 910             If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
 911             If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
 912             \p pred must imply the same element order as the comparator used for building the set.
 913         */
 914         template <typename Q, typename Predicate>
 915         bool find_with( Q const& val, Predicate pred )
 916         {
 917 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 918             return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), [](node_type&, Q const&) {});
 919 #       else
 920             return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), empty_find_functor());
 921 #       endif
 922         }
 923
 924         /// Clears the set
 925         /**
 926             The function erases all items from the set.
 927         */
 928         void clear()
 929         {
 930             return base_class::clear_and_dispose( node_disposer() );
 931         }
 932
 933         /// Checks if the set is empty
 934         /**
 935             Emptiness is checked by item counting: if item count is zero then the set is empty.
 936         */
 937         bool empty() const
 938         {
 939             return base_class::empty();
 940         }
 941
 942         /// Returns item count in the set
 943         size_t size() const
 944         {
 945             return base_class::size();
 946         }
 947
 948         /// Returns the size of hash table
 949         /**
 950             The hash table size is non-constant and can be increased via resizing.
 951         */
 952         size_t bucket_count() const
 953         {
 954             return base_class::bucket_count();
 955         }
 956
 957         /// Returns lock array size
 958         size_t lock_count() const
 959         {
 960             return base_class::lock_count();
 961         }
 962
 963         /// Returns const reference to internal statistics
 964         stat const& statistics() const
 965         {
 966             return base_class::statistics();
 967         }
 968
 969         /// Returns const reference to mutex policy internal statistics
 970         typename mutex_policy::statistics_type const& mutex_policy_statistics() const
 971         {
 972             return base_class::mutex_policy_statistics();
 973         }
 974
 975     };
 976
 977 }} // namespace cds::container
 978
 979 #endif //#ifndef __CDS_CONTAINER_CUCKOO_SET_H