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