cds/container/details/feldman_hashmap_base.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H
   4 #define CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H
   5
   6 #include <cds/intrusive/details/feldman_hashset_base.h>
   7 #include <cds/container/details/base.h>
   8 #include <cds/opt/hash.h>
   9
  10 namespace cds { namespace container {
  11     /// \p FeldmanHashMap related definitions
  12     /** @ingroup cds_nonintrusive_helper
  13     */
  14     namespace feldman_hashmap {
  15         /// \p FeldmanHashMap internal statistics, see cds::intrusive::feldman_hashset::stat
  16         template <typename EventCounter = cds::atomicity::event_counter>
  17         using stat = cds::intrusive::feldman_hashset::stat< EventCounter >;
  18
  19         /// \p FeldmanHashMap empty internal statistics
  20         typedef cds::intrusive::feldman_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::feldman_hashset::bitwise_compare< T >;
  25
  26         /// \p FeldmanHashMap level statistics
  27         typedef cds::intrusive::feldman_hashset::level_statistics level_statistics;
  28
  29         /// \p FeldmanHashMap traits
  30         struct traits
  31         {
  32             /// Hash functor, default is \p opt::none
  33             /**
  34                 \p FeldmanHashMap may use any hash functor converting a key to
  35                 fixed-sized bit-string, for example, <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
  36                 <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>,
  37                 <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
  38                 or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a>.
  39
  40                 If you use a fixed-sized key you may use it directly instead of a hash.
  41                 In such case \p %traits::hash should be specified as \p opt::none.
  42                 However, if you want to use the hash values or if your key type is not fixed-sized
  43                 you must specify a proper hash functor in your traits.
  44                 For example:
  45                 fixed-sized key - IP4 address map
  46                 @code
  47                     // Key - IP address
  48                     struct ip4_address {
  49                         uint8_t ip[4];
  50                     };
  51
  52                     // IP compare
  53                     struct ip4_cmp {
  54                         int operator()( ip4_address const& lhs, ip4_address const& rhs ) const
  55                         {
  56                             return memcmp( &lhs, &rhs, sizeof(lhs));
  57                         }
  58                     };
  59
  60                     // Value - statistics for the IP address
  61                     struct statistics {
  62                         // ...
  63                     };
  64
  65                     // Traits
  66                     // Key type (ip4_addr) is fixed-sized so we may use the map without any hash functor
  67                     struct ip4_map_traits: public cds::container::multilevl_hashmap::traits
  68                     {
  69                         typedef ip4_cmp  compare;
  70                     };
  71
  72                     // IP4 address - statistics map
  73                     typedef cds::container::FeldmanHashMap< cds::gc::HP, ip4_address, statistics, ip4_map_traits > ip4_map;
  74                 @endcode
  75
  76                 variable-size key requires a hash functor: URL map
  77                 @code
  78                     // Value - statistics for the URL
  79                     struct statistics {
  80                         // ...
  81                     };
  82
  83                     // Traits
  84                     // Key type (std::string) is variable-sized so we must provide a hash functor in our traits
  85                     // We do not specify any comparing predicate (less or compare) so <tt> std::less<std::string> </tt> will be used by default
  86                     struct url_map_traits: public cds::container::multilevl_hashmap::traits
  87                     {
  88                         typedef std::hash<std::string> hash;
  89                     };
  90
  91                     // URL statistics map
  92                     typedef cds::container::FeldmanHashMap< cds::gc::HP, std::string, statistics, url_map_traits > url_map;
  93                 @endcode
  94             */
  95             typedef opt::none hash;
  96
  97             /// Hash comparing functor
  98             /**
  99                 @copydetails cds::intrusive::feldman_hashset::traits::compare
 100             */
 101             typedef cds::opt::none compare;
 102
 103             /// Specifies binary predicate used for hash compare.
 104             /**
 105                 @copydetails cds::intrusive::feldman_hashset::traits::less
 106             */
 107             typedef cds::opt::none less;
 108
 109             /// Item counter
 110             /**
 111                 @copydetails cds::intrusive::feldman_hashset::traits::item_counter
 112             */
 113             typedef cds::atomicity::item_counter item_counter;
 114
 115             /// Item allocator
 116             /**
 117                 Default is \ref CDS_DEFAULT_ALLOCATOR
 118             */
 119             typedef CDS_DEFAULT_ALLOCATOR allocator;
 120
 121             /// Array node allocator
 122             /**
 123                 @copydetails cds::intrusive::feldman_hashset::traits::node_allocator
 124             */
 125             typedef CDS_DEFAULT_ALLOCATOR node_allocator;
 126
 127             /// C++ memory ordering model
 128             /**
 129                 @copydetails cds::intrusive::feldman_hashset::traits::memory_model
 130             */
 131             typedef cds::opt::v::relaxed_ordering memory_model;
 132
 133             /// Back-off strategy
 134             typedef cds::backoff::Default back_off;
 135
 136             /// Internal statistics
 137             /**
 138                 @copydetails cds::intrusive::feldman_hashset::traits::stat
 139             */
 140             typedef empty_stat stat;
 141
 142             /// RCU deadlock checking policy (only for \ref cds_container_FeldmanHashMap_rcu "RCU-based FeldmanHashMap")
 143             /**
 144                 @copydetails cds::intrusive::feldman_hashset::traits::rcu_check_deadlock
 145             */
 146             typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
 147         };
 148
 149         /// Metafunction converting option list to \p feldman_hashmap::traits
 150         /**
 151             Supported \p Options are:
 152             - \p opt::hash - a hash functor, default is \p std::hash
 153                 @copydetails traits::hash
 154             - \p opt::allocator - item allocator
 155                 @copydetails traits::allocator
 156             - \p opt::node_allocator - array node allocator.
 157                 @copydetails traits::node_allocator
 158             - \p opt::compare - hash comparison functor. No default functor is provided.
 159                 If the option is not specified, the \p opt::less is used.
 160             - \p opt::less - specifies binary predicate used for hash comparison.
 161                 @copydetails cds::container::feldman_hashmap::traits::less
 162             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 163             - \p opt::item_counter - the type of item counting feature.
 164                 @copydetails cds::container::feldman_hashmap::traits::item_counter
 165             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 166                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 167             - \p opt::stat - internal statistics. By default, it is disabled (\p feldman_hashmap::empty_stat).
 168                 To enable it use \p feldman_hashmap::stat
 169             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet"
 170                 Default is \p opt::v::rcu_throw_deadlock
 171         */
 172         template <typename... Options>
 173         struct make_traits
 174         {
 175 #   ifdef CDS_DOXYGEN_INVOKED
 176             typedef implementation_defined type ;   ///< Metafunction result
 177 #   else
 178             typedef typename cds::opt::make_options<
 179                 typename cds::opt::find_type_traits< traits, Options... >::type
 180                 ,Options...
 181             >::type   type;
 182 #   endif
 183         };
 184     } // namespace feldman_hashmap
 185
 186     //@cond
 187     // Forward declaration
 188     template < class GC, typename Key, typename T, class Traits = feldman_hashmap::traits >
 189     class FeldmanHashMap;
 190     //@endcond
 191
 192     //@cond
 193     namespace details {
 194
 195         template <typename Key, typename Value, typename Hash>
 196         struct hash_selector
 197         {
 198             typedef Key key_type;
 199             typedef Value mapped_type;
 200             typedef Hash hasher;
 201
 202             typedef typename std::decay<
 203                 typename std::remove_reference<
 204                 decltype(hasher()(std::declval<key_type>()))
 205                 >::type
 206             >::type hash_type;
 207
 208             struct node_type
 209             {
 210                 std::pair< key_type const, mapped_type> m_Value;
 211                 hash_type const m_hash;
 212
 213                 node_type() = delete;
 214                 node_type(node_type const&) = delete;
 215
 216                 template <typename Q>
 217                 node_type(hasher& h, Q const& key)
 218                     : m_Value(std::move(std::make_pair(key, mapped_type())))
 219                     , m_hash(h(m_Value.first))
 220                 {}
 221
 222                 template <typename Q, typename U >
 223                 node_type(hasher& h, Q const& key, U const& val)
 224                     : m_Value(std::move(std::make_pair(key, mapped_type(val))))
 225                     , m_hash(h(m_Value.first))
 226                 {}
 227
 228                 template <typename Q, typename... Args>
 229                 node_type(hasher& h, Q&& key, Args&&... args)
 230                     : m_Value(std::move(std::make_pair(std::forward<Q>(key), std::move(mapped_type(std::forward<Args>(args)...)))))
 231                     , m_hash(h(m_Value.first))
 232                 {}
 233             };
 234
 235             struct hash_accessor
 236             {
 237                 hash_type const& operator()(node_type const& node) const
 238                 {
 239                     return node.m_hash;
 240                 }
 241             };
 242         };
 243
 244         template <typename Key, typename Value>
 245         struct hash_selector<Key, Value, opt::none>
 246         {
 247             typedef Key key_type;
 248             typedef Value mapped_type;
 249
 250             struct hasher {
 251                 key_type const& operator()(key_type const& k) const
 252                 {
 253                     return k;
 254                 }
 255             };
 256             typedef key_type hash_type;
 257
 258             struct node_type
 259             {
 260                 std::pair< key_type const, mapped_type> m_Value;
 261
 262                 node_type() = delete;
 263                 node_type(node_type const&) = delete;
 264
 265                 template <typename Q>
 266                 node_type(hasher /*h*/, Q const& key)
 267                     : m_Value(std::move(std::make_pair(key, mapped_type())))
 268                 {}
 269
 270                 template <typename Q, typename U >
 271                 node_type(hasher /*h*/, Q const& key, U const& val)
 272                     : m_Value(std::move(std::make_pair(key, mapped_type(val))))
 273                 {}
 274
 275                 template <typename Q, typename... Args>
 276                 node_type(hasher /*h*/, Q&& key, Args&&... args)
 277                     : m_Value(std::move(std::make_pair(std::forward<Q>(key), std::move(mapped_type(std::forward<Args>(args)...)))))
 278                 {}
 279             };
 280
 281             struct hash_accessor
 282             {
 283                 hash_type const& operator()(node_type const& node) const
 284                 {
 285                     return node.m_Value.first;
 286                 }
 287             };
 288         };
 289
 290         template <typename GC, typename Key, typename T, typename Traits>
 291         struct make_feldman_hashmap
 292         {
 293             typedef GC      gc;
 294             typedef Key     key_type;
 295             typedef T       mapped_type;
 296             typedef Traits  original_traits;
 297
 298
 299             typedef hash_selector< key_type, mapped_type, typename original_traits::hash > select;
 300             typedef typename select::hasher    hasher;
 301             typedef typename select::hash_type hash_type;
 302             typedef typename select::node_type node_type;
 303
 304             typedef cds::details::Allocator< node_type, typename original_traits::allocator > cxx_node_allocator;
 305
 306             struct node_disposer
 307             {
 308                 void operator()( node_type * p ) const
 309                 {
 310                     cxx_node_allocator().Delete( p );
 311                 }
 312             };
 313
 314             struct intrusive_traits: public original_traits
 315             {
 316                 typedef typename select::hash_accessor hash_accessor;
 317                 typedef node_disposer disposer;
 318             };
 319
 320             // Metafunction result
 321             typedef cds::intrusive::FeldmanHashSet< GC, node_type, intrusive_traits > type;
 322         };
 323     } // namespace details
 324     //@endcond
 325
 326 }} // namespace cds::container
 327
 328 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H