cds/container/cuckoo_map.h

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