cds/container/details/multilevel_hashmap_base.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_DETAILS_MULTILEVEL_HASHMAP_BASE_H
   4 #define CDSLIB_CONTAINER_DETAILS_MULTILEVEL_HASHMAP_BASE_H
   5
   6 #include <cds/intrusive/details/multilevel_hashset_base.h>
   7 #include <cds/container/details/base.h>
   8 #include <cds/opt/hash.h>
   9
  10 namespace cds { namespace container {
  11     /// \p MultiLevelHashMap related definitions
  12     /** @ingroup cds_nonintrusive_helper
  13     */
  14     namespace multilevel_hashmap {
  15         //@cond
  16         using cds::intrusive::multilevel_hashset::implementation_tag;
  17         //@endcond
  18
  19         /// \p MultiLevelHashMap internal statistics, see cds::intrusive::multilevel_hashset::stat
  20         template <typename EventCounter = cds::atomicity::event_counter>
  21         using stat = cds::intrusive::multilevel_hashset::stat< EventCounter >;
  22
  23         /// \p MultiLevelHashMap empty internal statistics
  24         typedef cds::intrusive::multilevel_hashset::empty_stat empty_stat;
  25
  26         /// Bit-wise memcmp-based comparator for hash value \p T
  27         template <typename T>
  28         using bitwise_compare = cds::intrusive::multilevel_hashset::bitwise_compare< T >;
  29
  30         /// \p MultiLevelHashMap traits
  31         struct traits
  32         {
  33             /// Hash functor, default is \p std::hash
  34             /**
  35                 \p MultiLevelHashMap may use any hash functor converting a key to
  36                 fixed-sized bit-string, for example, <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
  37                 <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>,
  38                 <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
  39                 or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a>.
  40             */
  41             typedef opt::none hash;
  42
  43             /// Hash comparing functor
  44             /**
  45                 @copydetails cds::intrusive::multilevel_hashset::traits::compare
  46             */
  47             typedef cds::opt::none compare;
  48
  49             /// Specifies binary predicate used for hash compare.
  50             /**
  51                 @copydetails cds::intrusive::multilevel_hashset::traits::less
  52             */
  53             typedef cds::opt::none less;
  54
  55             /// Item counter
  56             /**
  57                 @copydetails cds::intrusive::multilevel_hashset::traits::item_counter
  58             */
  59             typedef cds::atomicity::item_counter item_counter;
  60
  61             /// Item allocator
  62             /**
  63                 Default is \ref CDS_DEFAULT_ALLOCATOR
  64             */
  65             typedef CDS_DEFAULT_ALLOCATOR allocator;
  66
  67             /// Array node allocator
  68             /**
  69                 @copydetails cds::intrusive::multilevel_hashset::traits::node_allocator
  70             */
  71             typedef CDS_DEFAULT_ALLOCATOR node_allocator;
  72
  73             /// C++ memory ordering model
  74             /**
  75                 @copydetails cds::intrusive::multilevel_hashset::traits::memory_model
  76             */
  77             typedef cds::opt::v::relaxed_ordering memory_model;
  78
  79             /// Back-off strategy
  80             typedef cds::backoff::Default back_off;
  81
  82             /// Internal statistics
  83             /**
  84                 @copydetails cds::intrusive::multilevel_hashset::traits::stat
  85             */
  86             typedef empty_stat stat;
  87
  88             /// RCU deadlock checking policy (only for \ref cds_container_MultilevelHashMap_rcu "RCU-based MultilevelHashMap")
  89             /**
  90                 @copydetails cds::intrusive::multilevel_hashset::traits::rcu_check_deadlock
  91             */
  92             typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
  93         };
  94
  95         /// Metafunction converting option list to \p multilevel_hashmap::traits
  96         /**
  97             Supported \p Options are:
  98             - \p opt::hash - a hash functor, default is \p std::hash
  99                 @copydetails traits::hash
 100             - \p opt::allocator - item allocator
 101                 @copydetails traits::allocator
 102             - \p opt::node_allocator - array node allocator.
 103                 @copydetails traits::node_allocator
 104             - \p opt::compare - hash comparison functor. No default functor is provided.
 105                 If the option is not specified, the \p opt::less is used.
 106             - \p opt::less - specifies binary predicate used for hash comparison.
 107                 @copydetails cds::container::multilevel_hashmap::traits::less
 108             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 109             - \p opt::item_counter - the type of item counting feature.
 110                 @copydetails cds::container::multilevel_hashmap::traits::item_counter
 111             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 112                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 113             - \p opt::stat - internal statistics. By default, it is disabled (\p multilevel_hashmap::empty_stat).
 114                 To enable it use \p multilevel_hashmap::stat
 115             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MultilevelHashSet_rcu "RCU-based MultilevelHashSet"
 116                 Default is \p opt::v::rcu_throw_deadlock
 117         */
 118         template <typename... Options>
 119         struct make_traits
 120         {
 121 #   ifdef CDS_DOXYGEN_INVOKED
 122             typedef implementation_defined type ;   ///< Metafunction result
 123 #   else
 124             typedef typename cds::opt::make_options<
 125                 typename cds::opt::find_type_traits< traits, Options... >::type
 126                 ,Options...
 127             >::type   type;
 128 #   endif
 129         };
 130     } // namespace multilevel_hashmap
 131
 132     //@cond
 133     // Forward declaration
 134     template < class GC, typename Key, typename T, class Traits = multilevel_hashmap::traits >
 135     class MultiLevelHashMap;
 136     //@endcond
 137
 138     //@cond
 139     namespace details {
 140
 141         template <typename GC, typename Key, typename T, typename Traits>
 142         struct make_multilevel_hashmap
 143         {
 144             typedef GC      gc;
 145             typedef Key     key_type;
 146             typedef T       mapped_type;
 147             typedef Traits  original_traits;
 148             typedef typename cds::opt::v::hash_selector< typename original_traits::hash >::type hasher;
 149
 150             typedef typename std::decay<
 151                 typename std::remove_reference<
 152                     decltype( hasher()( std::declval<key_type>()) )
 153                 >::type
 154             >::type hash_type;
 155             //typedef typename std::result_of< hasher( std::declval<key_type>()) >::type hash_type;
 156             static_assert( !std::is_pointer<hash_type>::value, "hash functor should return a reference to hash value" );
 157
 158             struct node_type
 159             {
 160                 std::pair< key_type const, mapped_type> m_Value;
 161                 hash_type const m_hash;
 162
 163                 node_type() = delete;
 164                 node_type( node_type const& ) = delete;
 165
 166                 template <typename Q>
 167                 node_type( hasher& h, Q const& key )
 168                     : m_Value( std::move( std::make_pair( key, mapped_type())))
 169                     , m_hash( h( m_Value.first ))
 170                 {}
 171
 172                 template <typename Q, typename U >
 173                 node_type( hasher& h, Q const& key, U const& val )
 174                     : m_Value( std::move( std::make_pair( key, mapped_type(val))))
 175                     , m_hash( h( m_Value.first ))
 176                 {}
 177
 178                 template <typename Q, typename... Args>
 179                 node_type( hasher& h, Q&& key, Args&&... args )
 180                     : m_Value( std::move( std::make_pair( std::forward<Q>(key), std::move( mapped_type( std::forward<Args>(args)... )))))
 181                     , m_hash( h( m_Value.first ))
 182                 {}
 183             };
 184
 185             typedef cds::details::Allocator< node_type, typename original_traits::allocator > cxx_node_allocator;
 186
 187             struct node_disposer
 188             {
 189                 void operator()( node_type * p ) const
 190                 {
 191                     cxx_node_allocator().Delete( p );
 192                 }
 193             };
 194
 195             struct get_node_hash
 196             {
 197                 hash_type const& operator()( node_type const& n )
 198                 {
 199                     return n.m_hash;
 200                 }
 201             };
 202
 203             struct intrusive_traits: public original_traits
 204             {
 205                 typedef get_node_hash hash_accessor;
 206                 typedef node_disposer disposer;
 207             };
 208
 209             // Metafunction result
 210             typedef cds::intrusive::MultiLevelHashSet< GC, node_type, intrusive_traits > type;
 211         };
 212     } // namespace details
 213     //@endcond
 214
 215 }} // namespace cds::container
 216
 217 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_MULTILEVEL_HASHMAP_BASE_H