-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
-#ifndef __CDS_CONTAINER_CUCKOO_MAP_H
-#define __CDS_CONTAINER_CUCKOO_MAP_H
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
-#include <cds/container/cuckoo_base.h>
+ Source code repo: http://github.com/khizmax/libcds/
+ Download: http://sourceforge.net/projects/libcds/files/
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions are met:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef CDSLIB_CONTAINER_CUCKOO_MAP_H
+#define CDSLIB_CONTAINER_CUCKOO_MAP_H
+
+#include <cds/container/details/cuckoo_base.h>
#include <cds/details/binary_functor_wrapper.h>
namespace cds { namespace container {
template <typename Key, typename T, typename Traits>
struct make_cuckoo_map
{
- typedef Key key_type ; ///< key type
- typedef T mapped_type ; ///< type of value stored in the map
- typedef std::pair<key_type const, mapped_type> value_type ; ///< Pair type
+ typedef Key key_type; ///< key type
+ typedef T mapped_type; ///< type of value stored in the map
+ typedef std::pair<key_type const, mapped_type> value_type; ///< Pair type
- typedef Traits original_type_traits;
- typedef typename original_type_traits::probeset_type probeset_type;
- static bool const store_hash = original_type_traits::store_hash;
- static unsigned int const store_hash_count = store_hash ? ((unsigned int) std::tuple_size< typename original_type_traits::hash::hash_tuple_type >::value) : 0;
+ typedef Traits original_traits;
+ typedef typename original_traits::probeset_type probeset_type;
+ static bool const store_hash = original_traits::store_hash;
+ static unsigned int const store_hash_count = store_hash ? ((unsigned int) std::tuple_size< typename original_traits::hash::hash_tuple_type >::value) : 0;
struct node_type: public intrusive::cuckoo::node<probeset_type, store_hash_count>
{
template <typename K>
node_type( K const& key )
- : m_val( std::make_pair( key_type(key), mapped_type() ))
+ : m_val( std::make_pair( key_type(key), mapped_type()))
{}
template <typename K, typename Q>
node_type( K const& key, Q const& v )
- : m_val( std::make_pair( key_type(key), mapped_type(v) ))
+ : m_val( std::make_pair( key_type(key), mapped_type(v)))
{}
-# ifdef CDS_EMPLACE_SUPPORT
template <typename K, typename... Args>
node_type( K&& key, Args&&... args )
- : m_val( std::forward<K>(key), std::move( mapped_type(std::forward<Args>(args)...)) )
+ : m_val( std::forward<K>(key), std::move( mapped_type(std::forward<Args>(args)...)))
{}
-# else
- node_type()
- {}
-# endif
};
- /*
- template <typename Pred, typename ReturnValue>
- struct predicate_wrapper {
- typedef Pred native_predicate;
-
- ReturnValue operator()( node_type const& n1, node_type const& n2) const
- {
- return native_predicate()(n1.m_val.first, n2.m_val.first );
- }
- template <typename Q>
- ReturnValue operator()( node_type const& n, Q const& v) const
- {
- return native_predicate()(n.m_val.first, v);
- }
- template <typename Q>
- ReturnValue operator()( Q const& v, node_type const& n) const
- {
- return native_predicate()(v, n.m_val.first);
- }
-
- template <typename Q1, typename Q2>
- ReturnValue operator()( Q1 const& v1, Q2 const& v2) const
- {
- return native_predicate()(v1, v2);
- }
- };
- */
-
struct key_accessor {
key_type const& operator()( node_type const& node ) const
{
}
};
- struct intrusive_traits: public original_type_traits
+ struct intrusive_traits: public original_traits
{
typedef intrusive::cuckoo::base_hook<
cds::intrusive::cuckoo::probeset_type< probeset_type >
,cds::intrusive::cuckoo::store_hash< store_hash_count >
> hook;
- typedef cds::intrusive::cuckoo::type_traits::disposer disposer;
+ typedef cds::intrusive::cuckoo::traits::disposer disposer;
typedef typename std::conditional<
- std::is_same< typename original_type_traits::equal_to, opt::none >::value
+ std::is_same< typename original_traits::equal_to, opt::none >::value
, opt::none
- , cds::details::predicate_wrapper< node_type, typename original_type_traits::equal_to, key_accessor >
+ , cds::details::predicate_wrapper< node_type, typename original_traits::equal_to, key_accessor >
>::type equal_to;
typedef typename std::conditional<
- std::is_same< typename original_type_traits::compare, opt::none >::value
+ std::is_same< typename original_traits::compare, opt::none >::value
, opt::none
- , cds::details::compare_wrapper< node_type, typename original_type_traits::compare, key_accessor >
+ , cds::details::compare_wrapper< node_type, typename original_traits::compare, key_accessor >
>::type compare;
typedef typename std::conditional<
- std::is_same< typename original_type_traits::less, opt::none >::value
+ std::is_same< typename original_traits::less, opt::none >::value
,opt::none
- ,cds::details::predicate_wrapper< node_type, typename original_type_traits::less, key_accessor >
+ ,cds::details::predicate_wrapper< node_type, typename original_traits::less, key_accessor >
>::type less;
- typedef opt::details::hash_list_wrapper< typename original_type_traits::hash, node_type, key_accessor > hash;
+ typedef opt::details::hash_list_wrapper< typename original_traits::hash, node_type, key_accessor > hash;
};
typedef intrusive::CuckooSet< node_type, intrusive_traits > type;
<b>About Cuckoo hashing</b>
[From "The Art of Multiprocessor Programming"]
- Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item
+ <a href="https://en.wikipedia.org/wiki/Cuckoo_hashing">Cuckoo hashing</a> is a hashing algorithm in which a newly added item displaces any earlier item
occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
N = 2k we use a two-entry array of tables, and two independent hash functions,
<tt> h0, h1: KeyRange -> 0,...,k-1</tt>
the average search complexity is <tt>O(PROBE_SET/2)</tt>.
However, the overhead of sorting can eliminate a gain of ordered search.
- The probe set is ordered if opt::compare or opt::less is specified in \p %CuckooSet
- declaration. Otherwise, the probe set is unordered and \p %CuckooSet must contain
- opt::equal_to option.
+ The probe set is ordered if \p compare or \p less is specified in \p Traits
+ template parameter. Otherwise, the probe set is unordered and \p Traits must contain
+ \p equal_to predicate.
Template arguments:
- \p Key - key type
- \p T - the type stored in the map.
- - \p Traits - type traits. See cuckoo::type_traits for explanation.
- It is possible to declare option-based set with cuckoo::make_traits metafunction result as \p Traits template argument.
-
- Template argument list \p Options... of cuckoo::make_traits metafunction are:
- - opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
- should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
- The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
- the number \p k - the count of hash tables in cuckoo hashing. If the compiler supports variadic templates
- then k is unlimited, otherwise up to 10 different hash functors are supported.
- - opt::mutex_policy - concurrent access policy.
- Available policies: cuckoo::striping, cuckoo::refinable.
- Default is cuckoo::striping.
- - opt::equal_to - key equality functor like \p std::equal_to.
- If this functor is defined then the probe-set will be unordered.
- If opt::compare or opt::less option is specified too, then the probe-set will be ordered
- and opt::equal_to will be ignored.
- - opt::compare - key comparison functor. No default functor is provided.
- If the option is not specified, the opt::less is used.
- If opt::compare or opt::less option is specified, then the probe-set will be ordered.
- - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
- If opt::compare or opt::less option is specified, then the probe-set will be ordered.
- - opt::item_counter - the type of item counting feature. Default is \ref opt::v::sequential_item_counter.
- - opt::allocator - the allocator type using for allocating bucket tables.
- Default is \p CDS_DEFAULT_ALLOCATOR
- - opt::node_allocator - the allocator type using for allocating map's items. If this option
- is not specified then the type defined in opt::allocator option is used.
- - cuckoo::store_hash - this option reserves additional space in the node to store the hash value
- of the object once it's introduced in the container. When this option is used,
- the map will store the calculated hash value in the node and rehashing operations won't need
- to recalculate the hash of the value. This option will improve the performance of maps
- when rehashing is frequent or hashing the value is a slow operation. Default value is \p false.
- - \ref intrusive::cuckoo::probeset_type "cuckoo::probeset_type" - type of probe set, may be \p cuckoo::list or <tt>cuckoo::vector<Capacity></tt>,
- Default is \p cuckoo::list.
- - opt::stat - internal statistics. Possibly types: cuckoo::stat, cuckoo::empty_stat.
- Default is cuckoo::empty_stat
+ - \p Traits - map traits, default is \p cuckoo::traits.
+ It is possible to declare option-based set with \p cuckoo::make_traits metafunction
+ result as \p Traits template argument.
<b>Examples</b>
#include <cds/container/cuckoo_map.h>
// Declare type traits
- struct my_traits: public cds::container::cuckoo::type_traits
+ struct my_traits: public cds::container::cuckoo::traits
{
typedef std::equal_to< std::string > equal_to;
typedef std::tuple< hash1, hash2 > hash;
// Declare type traits
// We use a vector of capacity 4 as probe-set container and store hash values in the node
- struct my_traits: public cds::container::cuckoo::type_traits
+ struct my_traits: public cds::container::cuckoo::traits
{
typedef std::less< std::string > less;
typedef std::tuple< hash1, hash2 > hash;
\endcode
*/
- template <typename Key, typename T, typename Traits = cuckoo::type_traits>
+ template <typename Key, typename T, typename Traits = cuckoo::traits>
class CuckooMap:
#ifdef CDS_DOXYGEN_INVOKED
protected intrusive::CuckooSet< std::pair< Key const, T>, Traits>
typedef typename maker::type base_class;
//@endcond
public:
- typedef Key key_type ; ///< key type
- typedef T mapped_type ; ///< value type stored in the container
- typedef std::pair<key_type const, mapped_type> value_type ; ///< Key-value pair type stored in the map
+ typedef Key key_type; ///< key type
+ typedef T mapped_type; ///< value type stored in the container
+ typedef std::pair<key_type const, mapped_type> value_type; ///< Key-value pair type stored in the map
+ typedef Traits traits; ///< Map traits
- typedef Traits options ; ///< traits
+ typedef typename traits::hash hash; ///< hash functor tuple wrapped for internal use
+ typedef typename base_class::hash_tuple_type hash_tuple_type; ///< hash tuple type
- typedef typename options::hash hash ; ///< hash functor tuple wrapped for internal use
- typedef typename base_class::hash_tuple_type hash_tuple_type ; ///< hash tuple type
+ typedef typename base_class::mutex_policy mutex_policy; ///< Concurrent access policy, see \p cuckoo::traits::mutex_policy
+ typedef typename base_class::stat stat; ///< internal statistics type
- typedef typename base_class::mutex_policy mutex_policy ; ///< Concurrent access policy, see cuckoo::type_traits::mutex_policy
- typedef typename base_class::stat stat ; ///< internal statistics type
+ static bool const c_isSorted = base_class::c_isSorted; ///< whether the probe set should be ordered
+ static size_t const c_nArity = base_class::c_nArity; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
- static bool const c_isSorted = base_class::c_isSorted ; ///< whether the probe set should be ordered
- static size_t const c_nArity = base_class::c_nArity ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
+ typedef typename base_class::key_equal_to key_equal_to; ///< Key equality functor; used only for unordered probe-set
- typedef typename base_class::key_equal_to key_equal_to ; ///< Key equality functor; used only for unordered probe-set
+ 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
- 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
-
- typedef typename base_class::allocator allocator ; ///< allocator type used for internal bucket table allocations
+ typedef typename base_class::allocator allocator; ///< allocator type used for internal bucket table allocations
/// Node allocator type
typedef typename std::conditional<
- std::is_same< typename options::node_allocator, opt::none >::value,
+ std::is_same< typename traits::node_allocator, opt::none >::value,
allocator,
- typename options::node_allocator
+ typename traits::node_allocator
>::type node_allocator;
/// item counter type
- typedef typename options::item_counter item_counter;
+ typedef typename traits::item_counter item_counter;
protected:
//@cond
//@endcond
public:
- static unsigned int const c_nDefaultProbesetSize = base_class::c_nDefaultProbesetSize ; ///< default probeset size
- static size_t const c_nDefaultInitialSize = base_class::c_nDefaultInitialSize ; ///< default initial size
- static unsigned int const c_nRelocateLimit = base_class::c_nRelocateLimit ; ///< Count of attempts to relocate before giving up
+ static unsigned int const c_nDefaultProbesetSize = base_class::c_nDefaultProbesetSize; ///< default probeset size
+ static size_t const c_nDefaultInitialSize = base_class::c_nDefaultInitialSize; ///< default initial size
+ static unsigned int const c_nRelocateLimit = base_class::c_nRelocateLimit; ///< Count of attempts to relocate before giving up
protected:
//@cond
{
return cxx_node_allocator().New( key );
}
-# ifdef CDS_EMPLACE_SUPPORT
template <typename K, typename... Args>
static node_type * alloc_node( K&& key, Args&&... args )
{
return cxx_node_allocator().MoveNew( std::forward<K>( key ), std::forward<Args>(args)... );
}
-# endif
static void free_node( node_type * pNode )
{
typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
-#ifndef CDS_CXX11_LAMBDA_SUPPORT
- struct empty_insert_functor
- {
- void operator()( value_type& ) const
- {}
- };
-
- template <typename Q>
- class insert_value_functor
- {
- Q const& m_val;
- public:
- insert_value_functor( Q const & v)
- : m_val(v)
- {}
-
- void operator()( value_type& item )
- {
- item.second = m_val;
- }
- };
-
- template <typename Func>
- class insert_key_wrapper: protected cds::details::functor_wrapper<Func>
- {
- typedef cds::details::functor_wrapper<Func> base_class;
- public:
- insert_key_wrapper( Func f ): base_class(f) {}
-
- void operator()( node_type& item )
- {
- base_class::get()( item.m_val );
- }
- };
-
- template <typename Func>
- class ensure_wrapper: protected cds::details::functor_wrapper<Func>
- {
- typedef cds::details::functor_wrapper<Func> base_class;
- public:
- ensure_wrapper( Func f) : base_class(f) {}
-
- void operator()( bool bNew, node_type& item, node_type const& )
- {
- base_class::get()( bNew, item.m_val );
- }
- };
-
- template <typename Func>
- class find_wrapper: protected cds::details::functor_wrapper<Func>
- {
- typedef cds::details::functor_wrapper<Func> base_class;
- public:
- find_wrapper( Func f )
- : base_class(f)
- {}
-
- template <typename Q>
- void operator()( node_type& item, Q& val )
- {
- base_class::get()( item.m_val, val );
- }
- };
-#endif // #ifndef CDS_CXX11_LAMBDA_SUPPORT
-
//@endcond
public:
CuckooMap(
hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
)
- : base_class( std::forward<hash_tuple_type>(h) )
+ : base_class( std::forward<hash_tuple_type>(h))
{}
/// Constructs a map with given probe set properties and hash functor tuple (move semantics)
, unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
, hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
)
- : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h) )
+ : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h))
{}
/// Destructor clears the map
template <typename K>
bool insert( K const& key )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- return insert_key( key, [](value_type&){} );
-# else
- return insert_key( key, empty_insert_functor() );
-# endif
+ return insert_with( key, [](value_type&){} );
}
/// Inserts new node
template <typename K, typename V>
bool insert( K const& key, V const& val )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- return insert_key( key, [&val](value_type& item) { item.second = val ; } );
-# else
- insert_value_functor<V> f(val);
- return insert_key( key, cds::ref(f) );
-# endif
+ return insert_with( key, [&val](value_type& item) { item.second = val ; } );
}
/// Inserts new node and initialize it by a functor
- <tt>item.first</tt> is a const reference to item's key that cannot be changed.
- <tt>item.second</tt> is a reference to item's value that may be changed.
- The user-defined functor can be passed by reference using <tt>boost::ref</tt>
- and it is called only if inserting is successful.
-
The key_type should be constructible from value of type \p K.
The function allows to split creating of new item into two part:
it is preferable that the initialization should be completed only if inserting is successful.
*/
template <typename K, typename Func>
- bool insert_key( const K& key, Func func )
+ bool insert_with( const K& key, Func func )
{
scoped_node_ptr pNode( alloc_node( key ));
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- if ( base_class::insert( *pNode, [&func]( node_type& item ) { cds::unref(func)( item.m_val ); } ))
-# else
- insert_key_wrapper<Func> wrapper(func);
- if ( base_class::insert( *pNode, cds::ref(wrapper) ))
-#endif
- {
+ if ( base_class::insert( *pNode, [&func]( node_type& item ) { func( item.m_val ); } )) {
pNode.release();
return true;
}
return false;
}
-# ifdef CDS_EMPLACE_SUPPORT
/// For key \p key inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
/**
Returns \p true if inserting successful, \p false otherwise.
-
- This function is available only for compiler that supports
- variadic template and move semantics
*/
template <typename K, typename... Args>
bool emplace( K&& key, Args&&... args )
}
return false;
}
-# endif
-
- /// Ensures that the \p key exists in the map
+ /// Updates the node
/**
The operation performs inserting or changing data with lock-free manner.
- If the \p key not found in the map, then the new item created from \p key
- is inserted into the map (note that in this case the \ref key_type should be
- constructible from type \p K).
+ If \p key is not found in the map, then \p key is inserted iff \p bAllowInsert is \p true.
Otherwise, the functor \p func is called with item found.
- The functor \p Func may be a function with signature:
- \code
- void func( bool bNew, value_type& item );
- \endcode
- or a functor:
+ The functor \p func signature is:
\code
struct my_functor {
void operator()( bool bNew, value_type& item );
};
\endcode
-
with arguments:
- \p bNew - \p true if the item has been inserted, \p false otherwise
- - \p item - item of the list
-
- The functor may change any fields of the \p item.second that is \ref value_type.
-
- You may pass \p func argument by reference using <tt>boost::ref</tt>.
+ - \p item - an item of the map for \p key
- Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
- \p second is true if new item has been added or \p false if the item with \p key
- already is in the list.
+ Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
+ i.e. the node has been inserted or updated,
+ \p second is \p true if new item has been added or \p false if the item with \p key
+ already exists.
*/
template <typename K, typename Func>
- std::pair<bool, bool> ensure( K const& key, Func func )
+ std::pair<bool, bool> update( K const& key, Func func, bool bAllowInsert = true )
{
scoped_node_ptr pNode( alloc_node( key ));
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- std::pair<bool, bool> res = base_class::ensure( *pNode,
- [&func](bool bNew, node_type& item, node_type const& ){ cds::unref(func)( bNew, item.m_val ); }
+ std::pair<bool, bool> res = base_class::update( *pNode,
+ [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_val ); },
+ bAllowInsert
);
-# else
- ensure_wrapper<Func> wrapper( func );
- std::pair<bool, bool> res = base_class::ensure( *pNode, cds::ref(wrapper) );
-# endif
if ( res.first && res.second )
pNode.release();
return res;
}
+ //@cond
+ template <typename K, typename Func>
+ CDS_DEPRECATED("ensure() is deprecated, use update()")
+ std::pair<bool, bool> ensure( K const& key, Func func )
+ {
+ return update( key, func, true );
+ }
+ //@endcond
/// Delete \p key from the map
/** \anchor cds_nonintrusive_CuckooMap_erase_val
template <typename K, typename Predicate>
bool erase_with( K const& key, Predicate pred )
{
+ CDS_UNUSED( pred );
node_type * pNode = base_class::erase_with(key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>());
if ( pNode ) {
free_node( pNode );
void operator()(value_type& item) { ... }
};
\endcode
- The functor may be passed by reference using <tt>boost:ref</tt>
Return \p true if key is found and deleted, \p false otherwise
{
node_type * pNode = base_class::erase( key );
if ( pNode ) {
- cds::unref(f)( pNode->m_val );
+ f( pNode->m_val );
free_node( pNode );
return true;
}
template <typename K, typename Predicate, typename Func>
bool erase_with( K const& key, Predicate pred, Func f )
{
- node_type * pNode = base_class::erase_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
+ CDS_UNUSED( pred );
+ node_type * pNode = base_class::erase_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>());
if ( pNode ) {
- cds::unref(f)( pNode->m_val );
+ f( pNode->m_val );
free_node( pNode );
return true;
}
\endcode
where \p item is the item found.
- You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
-
The functor may change \p item.second.
The function returns \p true if \p key is found, \p false otherwise.
template <typename K, typename Func>
bool find( K const& key, Func f )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- return base_class::find( key, [&f](node_type& item, K const& ) { cds::unref(f)( item.m_val );});
-# else
- find_wrapper<Func> wrapper(f);
- return base_class::find( key, cds::ref(wrapper) );
-# endif
+ return base_class::find( key, [&f](node_type& item, K const& ) { f( item.m_val );});
}
/// Find the key \p val using \p pred predicate for comparing
template <typename K, typename Predicate, typename Func>
bool find_with( K const& key, Predicate pred, Func f )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
+ CDS_UNUSED( pred );
return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>(),
- [&f](node_type& item, K const& ) { cds::unref(f)( item.m_val );});
-# else
- find_wrapper<Func> wrapper(f);
- return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>(), cds::ref(wrapper) );
-# endif
+ [&f](node_type& item, K const& ) { f( item.m_val );});
}
- /// Find the key \p key
- /** \anchor cds_nonintrusive_CuckooMap_find_val
-
+ /// Checks whether the map contains \p key
+ /**
The function searches the item with key equal to \p key
and returns \p true if it is found, and \p false otherwise.
*/
template <typename K>
+ bool contains( K const& key )
+ {
+ return base_class::contains( key );
+ }
+ //@cond
+ template <typename K>
+ CDS_DEPRECATED("the function is deprecated, use contains()")
bool find( K const& key )
{
- return base_class::find( key );
+ return contains( key );
}
+ //@endcond
- /// Find the key \p val using \p pred predicate for comparing
+ /// Checks whether the map contains \p key using \p pred predicate for searching
/**
- The function is an analog of \ref cds_nonintrusive_CuckooMap_find_val "find(K const&)"
- but \p pred is used for key comparison.
- If you use ordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::less.
- If you use unordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::equal_to.
- \p pred must imply the same element order as the comparator used for building the map.
+ The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
+ \p Less functor has the interface like \p std::less.
+ \p Less must imply the same element order as the comparator used for building the map.
*/
template <typename K, typename Predicate>
+ bool contains( K const& key, Predicate pred )
+ {
+ CDS_UNUSED( pred );
+ return base_class::contains( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>());
+ }
+ //@cond
+ template <typename K, typename Predicate>
+ CDS_DEPRECATED("the function is deprecated, use contains()")
bool find_with( K const& key, Predicate pred )
{
- return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
+ return contains( key, pred );
}
+ //@endcond
/// Clears the map
void clear()
{
- base_class::clear_and_dispose( node_disposer() );
+ base_class::clear_and_dispose( node_disposer());
}
/// Checks if the map is empty
{
return base_class::mutex_policy_statistics();
}
-
};
}} // namespace cds::container
-#endif //#ifndef __CDS_CONTAINER_CUCKOO_MAP_H
+#endif //#ifndef CDSLIB_CONTAINER_CUCKOO_MAP_H