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