//$$CDS-header$$
-#ifndef __CDS_CONTAINER_CUCKOO_MAP_H
-#define __CDS_CONTAINER_CUCKOO_MAP_H
+#ifndef CDSLIB_CONTAINER_CUCKOO_MAP_H
+#define CDSLIB_CONTAINER_CUCKOO_MAP_H
-#include <cds/container/cuckoo_base.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;
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,
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;
+
+ //@cond
+ typedef cds::container::cuckoo::implementation_tag implementation_tag;
+ //@endcond
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
/**
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.
std::pair<bool, bool> ensure( K const& key, Func func )
{
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 ); }
+ [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_val ); }
);
-# 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;
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
template <typename K, typename Predicate>
bool find_with( K const& key, Predicate pred )
{
+ CDS_UNUSED( pred );
return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
}
{
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