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