-//$$CDS-header$$
-
-#ifndef __CDS_CONTAINER_CUCKOO_MAP_H
-#define __CDS_CONTAINER_CUCKOO_MAP_H
-
-#include <cds/container/cuckoo_base.h>
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+
+ 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>
{
: 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)...)) )
{}
-# 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 <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
- If the prior value was \p NULL, it is done. Otherwise, it swaps the newly nest-less value \p y
+ If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y
for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
- was \p NULL, it is done. Otherwise, the method continues swapping entries (alternating tables)
+ was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables)
until it finds an empty slot. We might not find an empty slot, either because the table is full,
or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
number of successive displacements we are willing to undertake. When this limit is exceeded,
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:
: base_class( nInitialSize, nProbesetSize, nProbesetThreshold, h )
{}
-# ifdef CDS_MOVE_SEMANTICS_SUPPORT
/// Constructs a map with given hash functor tuple (move semantics)
/**
The probe set size and threshold are set as default, see CuckooSet()
)
: base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h) )
{}
-# endif // ifdef CDS_MOVE_SEMANTICS_SUPPORT
/// Destructor clears the map
~CuckooMap()
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
+ - \p item - an item of the map for \p key
- 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>.
-
- 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 )
{
+ 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()
{
return base_class::mutex_policy_statistics();
}
-
};
}} // namespace cds::container
-#endif //#ifndef __CDS_CONTAINER_CUCKOO_MAP_H
+#endif //#ifndef CDSLIB_CONTAINER_CUCKOO_MAP_H
projects / libcds.git / blobdiff