/// \p MultiLevelHashMap traits
struct traits
{
- /// Hash functor, default is \p std::hash
+ /// Hash functor, default is \p opt::none
/**
\p MultiLevelHashMap may use any hash functor converting a key to
fixed-sized bit-string, for example, <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
<a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>,
<a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a>.
+
+ If you use a fixed-sized key you may use it directly instead of a hash.
+ In such case \p %traits::hash should be specified as \p opt::none.
+ However, if you want to use the hash values or if your key type is not fixed-sized
+ you must specify a proper hash functor in your traits.
+ For example:
+ fixed-sized key - IP4 address map
+ @code
+ // Key - IP address
+ struct ip4_address {
+ uint8_t ip[4];
+ };
+
+ // IP compare
+ struct ip4_cmp {
+ int operator()( ip4_address const& lhs, ip4_address const& rhs ) const
+ {
+ return memcmp( &lhs, &rhs, sizeof(lhs));
+ }
+ };
+
+ // Value - statistics for the IP address
+ struct statistics {
+ // ...
+ };
+
+ // Traits
+ // Key type (ip4_addr) is fixed-sized so we may use the map without any hash functor
+ struct ip4_map_traits: public cds::container::multilevl_hashmap::traits
+ {
+ typedef ip4_cmp compare;
+ };
+
+ // IP4 address - statistics map
+ typedef cds::container::MultiLevelHashMap< cds::gc::HP, ip4_address, statistics, ip4_map_traits > ip4_map;
+ @endcode
+
+ variable-size key requires a hash functor: URL map
+ @code
+ // Value - statistics for the URL
+ struct statistics {
+ // ...
+ };
+
+ // Traits
+ // Key type (std::string) is variable-sized so we must provide a hash functor in our traits
+ // We do not specify any comparing predicate (less or compare) so <tt> std::less<std::string> </tt> will be used by default
+ struct url_map_traits: public cds::container::multilevl_hashmap::traits
+ {
+ typedef std::hash<std::string> hash;
+ };
+
+ // URL statistics map
+ typedef cds::container::MultiLevelHashMap< cds::gc::HP, std::string, statistics, url_map_traits > url_map;
+ @endcode
*/
typedef opt::none hash;
//@cond
namespace details {
- template <typename GC, typename Key, typename T, typename Traits>
- struct make_multilevel_hashmap
+ template <typename Key, typename Value, typename Hash>
+ struct hash_selector
{
- typedef GC gc;
- typedef Key key_type;
- typedef T mapped_type;
- typedef Traits original_traits;
- typedef typename cds::opt::v::hash_selector< typename original_traits::hash >::type hasher;
+ typedef Key key_type;
+ typedef Value mapped_type;
+ typedef Hash hasher;
typedef typename std::decay<
typename std::remove_reference<
- decltype( hasher()( std::declval<key_type>()) )
+ decltype(hasher()(std::declval<key_type>()))
>::type
>::type hash_type;
- //typedef typename std::result_of< hasher( std::declval<key_type>()) >::type hash_type;
- static_assert( !std::is_pointer<hash_type>::value, "hash functor should return a reference to hash value" );
struct node_type
{
hash_type const m_hash;
node_type() = delete;
- node_type( node_type const& ) = delete;
+ node_type(node_type const&) = delete;
template <typename Q>
- node_type( hasher& h, Q const& key )
- : m_Value( std::move( std::make_pair( key, mapped_type())))
- , m_hash( h( m_Value.first ))
+ node_type(hasher& h, Q const& key)
+ : m_Value(std::move(std::make_pair(key, mapped_type())))
+ , m_hash(h(m_Value.first))
{}
template <typename Q, typename U >
- node_type( hasher& h, Q const& key, U const& val )
- : m_Value( std::move( std::make_pair( key, mapped_type(val))))
- , m_hash( h( m_Value.first ))
+ node_type(hasher& h, Q const& key, U const& val)
+ : m_Value(std::move(std::make_pair(key, mapped_type(val))))
+ , m_hash(h(m_Value.first))
{}
template <typename Q, typename... Args>
- node_type( hasher& h, Q&& key, Args&&... args )
- : m_Value( std::move( std::make_pair( std::forward<Q>(key), std::move( mapped_type( std::forward<Args>(args)... )))))
- , m_hash( h( m_Value.first ))
+ node_type(hasher& h, Q&& key, Args&&... args)
+ : m_Value(std::move(std::make_pair(std::forward<Q>(key), std::move(mapped_type(std::forward<Args>(args)...)))))
+ , m_hash(h(m_Value.first))
{}
};
- typedef cds::details::Allocator< node_type, typename original_traits::allocator > cxx_node_allocator;
+ struct hash_accessor
+ {
+ hash_type const& operator()(node_type const& node) const
+ {
+ return node.m_hash;
+ }
+ };
+ };
- struct node_disposer
+ template <typename Key, typename Value>
+ struct hash_selector<Key, Value, opt::none>
+ {
+ typedef Key key_type;
+ typedef Value mapped_type;
+
+ struct hasher {
+ key_type const& operator()(key_type const& k) const
+ {
+ return k;
+ }
+ };
+ typedef key_type hash_type;
+
+ struct node_type
{
- void operator()( node_type * p ) const
+ std::pair< key_type const, mapped_type> m_Value;
+
+ node_type() = delete;
+ node_type(node_type const&) = delete;
+
+ template <typename Q>
+ node_type(hasher /*h*/, Q const& key)
+ : m_Value(std::move(std::make_pair(key, mapped_type())))
+ {}
+
+ template <typename Q, typename U >
+ node_type(hasher /*h*/, Q const& key, U const& val)
+ : m_Value(std::move(std::make_pair(key, mapped_type(val))))
+ {}
+
+ template <typename Q, typename... Args>
+ node_type(hasher /*h*/, Q&& key, Args&&... args)
+ : m_Value(std::move(std::make_pair(std::forward<Q>(key), std::move(mapped_type(std::forward<Args>(args)...)))))
+ {}
+ };
+
+ struct hash_accessor
+ {
+ hash_type const& operator()(node_type const& node) const
{
- cxx_node_allocator().Delete( p );
+ return node.m_Value.first;
}
};
+ };
- struct get_node_hash
+ template <typename GC, typename Key, typename T, typename Traits>
+ struct make_multilevel_hashmap
+ {
+ typedef GC gc;
+ typedef Key key_type;
+ typedef T mapped_type;
+ typedef Traits original_traits;
+
+
+ typedef hash_selector< key_type, mapped_type, typename original_traits::hash > select;
+ typedef typename select::hasher hasher;
+ typedef typename select::hash_type hash_type;
+ typedef typename select::node_type node_type;
+
+ typedef cds::details::Allocator< node_type, typename original_traits::allocator > cxx_node_allocator;
+
+ struct node_disposer
{
- hash_type const& operator()( node_type const& n )
+ void operator()( node_type * p ) const
{
- return n.m_hash;
+ cxx_node_allocator().Delete( p );
}
};
struct intrusive_traits: public original_traits
{
- typedef get_node_hash hash_accessor;
+ typedef typename select::hash_accessor hash_accessor;
typedef node_disposer disposer;
};
projects / libcds.git / blobdiff