cds/container/details/feldman_hashmap_base.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H
  32 #define CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H
  33
  34 #include <cds/intrusive/details/feldman_hashset_base.h>
  35 #include <cds/container/details/base.h>
  36 #include <cds/opt/hash.h>
  37
  38 namespace cds { namespace container {
  39     /// \p FeldmanHashMap related definitions
  40     /** @ingroup cds_nonintrusive_helper
  41     */
  42     namespace feldman_hashmap {
  43         /// \p FeldmanHashMap internal statistics, see cds::intrusive::feldman_hashset::stat
  44         template <typename EventCounter = cds::atomicity::event_counter>
  45         using stat = cds::intrusive::feldman_hashset::stat< EventCounter >;
  46
  47         /// \p FeldmanHashMap empty internal statistics
  48         typedef cds::intrusive::feldman_hashset::empty_stat empty_stat;
  49
  50         /// Bit-wise memcmp-based comparator for hash value \p T
  51         template <typename T>
  52         using bitwise_compare = cds::intrusive::feldman_hashset::bitwise_compare< T >;
  53
  54         /// \p FeldmanHashMap level statistics
  55         typedef cds::intrusive::feldman_hashset::level_statistics level_statistics;
  56
  57         /// Key size option
  58         /**
  59             @copydetails cds::container::feldman_hashmap::traits::hash_size
  60         */
  61         template <size_t Size>
  62         using hash_size = cds::intrusive::feldman_hashset::hash_size< Size >;
  63
  64
  65         /// \p FeldmanHashMap traits
  66         struct traits
  67         {
  68             /// Hash functor, default is \p opt::none
  69             /**
  70                 \p FeldmanHashMap may use any hash functor converting a key to
  71                 fixed-sized bit-string, for example, <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
  72                 <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>,
  73                 <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
  74                 or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a>.
  75
  76                 If you use a fixed-sized key you can use it directly instead of a hash.
  77                 In such case \p %traits::hash should be specified as \p opt::none.
  78                 However, if you want to use the hash values or if your key type is not fixed-sized
  79                 you must specify a proper hash functor in your traits.
  80                 For example:
  81                 fixed-sized key - IP4 address map
  82                 @code
  83                     // Key - IP address
  84                     struct ip4_address {
  85                         uint8_t ip[4];
  86                     };
  87
  88                     // IP compare
  89                     struct ip4_cmp {
  90                         int operator()( ip4_address const& lhs, ip4_address const& rhs ) const
  91                         {
  92                             return memcmp( &lhs, &rhs, sizeof(lhs));
  93                         }
  94                     };
  95
  96                     // Value - statistics for the IP address
  97                     struct statistics {
  98                         // ...
  99                     };
 100
 101                     // Traits
 102                     // Key type (ip4_addr) is fixed-sized so we may use the map without any hash functor
 103                     struct ip4_map_traits: public cds::container::multilevl_hashmap::traits
 104                     {
 105                         typedef ip4_cmp  compare;
 106                     };
 107
 108                     // IP4 address - statistics map
 109                     typedef cds::container::FeldmanHashMap< cds::gc::HP, ip4_address, statistics, ip4_map_traits > ip4_map;
 110                 @endcode
 111
 112                 variable-size key requires a hash functor: URL map
 113                 @code
 114                     // Value - statistics for the URL
 115                     struct statistics {
 116                         // ...
 117                     };
 118
 119                     // Traits
 120                     // Key type (std::string) is variable-sized so we must provide a hash functor in our traits
 121                     // We do not specify any comparing predicate (less or compare) so <tt> std::less<std::string> </tt> will be used by default
 122                     struct url_map_traits: public cds::container::multilevl_hashmap::traits
 123                     {
 124                         typedef std::hash<std::string> hash;
 125                     };
 126
 127                     // URL statistics map
 128                     typedef cds::container::FeldmanHashMap< cds::gc::HP, std::string, statistics, url_map_traits > url_map;
 129                 @endcode
 130             */
 131             typedef opt::none hash;
 132
 133             /// The size of hash value in bytes
 134             /**
 135                 By default, the size of hash value is <tt>sizeof( hash_type )</tt>
 136                 where \p hash_type is type of \p hash() result or <tt>sizeof( key )</tt> if you use fixed-sized key.
 137
 138                 Sometimes that size is wrong, for example, for that 6-byte key:
 139                 \code
 140                 struct key_type {
 141                     uint32_t    key;
 142                     uint16_t    subkey;
 143                 };
 144
 145                 static_assert( sizeof( key_type ) == 6, "Key type size mismatch" );
 146                 \endcode
 147                 Here <tt>sizeof( key_type ) == 8</tt> so \p static_assert will be thrown.
 148
 149                 For that case you can specify \p hash_size explicitly.
 150
 151                 Value \p 0 means auto-calculated <tt>sizeof( key_type )</tt>.
 152             */
 153             static CDS_CONSTEXPR size_t const hash_size = 0;
 154
 155             /// Hash comparing functor
 156             /**
 157                 @copydetails cds::intrusive::feldman_hashset::traits::compare
 158             */
 159             typedef cds::opt::none compare;
 160
 161             /// Specifies binary predicate used for hash compare.
 162             /**
 163                 @copydetails cds::intrusive::feldman_hashset::traits::less
 164             */
 165             typedef cds::opt::none less;
 166
 167             /// Item counter
 168             /**
 169                 @copydetails cds::intrusive::feldman_hashset::traits::item_counter
 170             */
 171             typedef cds::atomicity::item_counter item_counter;
 172
 173             /// Item allocator
 174             /**
 175                 Default is \ref CDS_DEFAULT_ALLOCATOR
 176             */
 177             typedef CDS_DEFAULT_ALLOCATOR allocator;
 178
 179             /// Array node allocator
 180             /**
 181                 @copydetails cds::intrusive::feldman_hashset::traits::node_allocator
 182             */
 183             typedef CDS_DEFAULT_ALLOCATOR node_allocator;
 184
 185             /// C++ memory ordering model
 186             /**
 187                 @copydetails cds::intrusive::feldman_hashset::traits::memory_model
 188             */
 189             typedef cds::opt::v::relaxed_ordering memory_model;
 190
 191             /// Back-off strategy
 192             typedef cds::backoff::Default back_off;
 193
 194             /// Internal statistics
 195             /**
 196                 @copydetails cds::intrusive::feldman_hashset::traits::stat
 197             */
 198             typedef empty_stat stat;
 199
 200             /// RCU deadlock checking policy (only for \ref cds_container_FeldmanHashMap_rcu "RCU-based FeldmanHashMap")
 201             /**
 202                 @copydetails cds::intrusive::feldman_hashset::traits::rcu_check_deadlock
 203             */
 204             typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
 205         };
 206
 207         /// Metafunction converting option list to \p feldman_hashmap::traits
 208         /**
 209             Supported \p Options are:
 210             - \p opt::hash - a hash functor, default is \p std::hash
 211                 @copydetails traits::hash
 212             - \p feldman_hashmap::hash_size - the size of hash value in bytes.
 213                 @copydetails traits::hash_size
 214             - \p opt::allocator - item allocator
 215                 @copydetails traits::allocator
 216             - \p opt::node_allocator - array node allocator.
 217                 @copydetails traits::node_allocator
 218             - \p opt::compare - hash comparison functor. No default functor is provided.
 219                 If the option is not specified, the \p opt::less is used.
 220             - \p opt::less - specifies binary predicate used for hash comparison.
 221                 @copydetails cds::container::feldman_hashmap::traits::less
 222             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 223             - \p opt::item_counter - the type of item counting feature.
 224                 @copydetails cds::container::feldman_hashmap::traits::item_counter
 225             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 226                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 227             - \p opt::stat - internal statistics. By default, it is disabled (\p feldman_hashmap::empty_stat).
 228                 To enable it use \p feldman_hashmap::stat
 229             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet"
 230                 Default is \p opt::v::rcu_throw_deadlock
 231         */
 232         template <typename... Options>
 233         struct make_traits
 234         {
 235 #   ifdef CDS_DOXYGEN_INVOKED
 236             typedef implementation_defined type ;   ///< Metafunction result
 237 #   else
 238             typedef typename cds::opt::make_options<
 239                 typename cds::opt::find_type_traits< traits, Options... >::type
 240                 ,Options...
 241             >::type   type;
 242 #   endif
 243         };
 244     } // namespace feldman_hashmap
 245
 246     //@cond
 247     // Forward declaration
 248     template < class GC, typename Key, typename T, class Traits = feldman_hashmap::traits >
 249     class FeldmanHashMap;
 250     //@endcond
 251
 252     //@cond
 253     namespace details {
 254
 255         template <typename Key, typename Value, typename Hash>
 256         struct hash_selector
 257         {
 258             typedef Key key_type;
 259             typedef Value mapped_type;
 260             typedef Hash hasher;
 261
 262             typedef typename std::decay<
 263                 typename std::remove_reference<
 264                 decltype(hasher()(std::declval<key_type>()))
 265                 >::type
 266             >::type hash_type;
 267
 268             struct node_type
 269             {
 270                 std::pair< key_type const, mapped_type> m_Value;
 271                 hash_type const m_hash;
 272
 273                 node_type() = delete;
 274                 node_type(node_type const&) = delete;
 275
 276                 template <typename Q>
 277                 node_type(hasher& h, Q const& key)
 278                     : m_Value( std::move( std::make_pair( key_type( key ), mapped_type())))
 279                     , m_hash( h( m_Value.first ))
 280                 {}
 281
 282                 template <typename Q, typename U >
 283                 node_type(hasher& h, Q const& key, U const& val)
 284                     : m_Value( std::move( std::make_pair( key_type( key ), mapped_type(val))))
 285                     , m_hash( h( m_Value.first ))
 286                 {}
 287
 288                 template <typename Q, typename... Args>
 289                 node_type(hasher& h, Q&& key, Args&&... args)
 290                     : m_Value( std::move(std::make_pair( key_type( std::forward<Q>(key)), std::move( mapped_type(std::forward<Args>(args)...)))))
 291                     , m_hash( h( m_Value.first ))
 292                 {}
 293             };
 294
 295             struct hash_accessor
 296             {
 297                 hash_type const& operator()(node_type const& node) const
 298                 {
 299                     return node.m_hash;
 300                 }
 301             };
 302         };
 303
 304         template <typename Key, typename Value>
 305         struct hash_selector<Key, Value, opt::none>
 306         {
 307             typedef Key key_type;
 308             typedef Value mapped_type;
 309
 310             struct hasher {
 311                 key_type const& operator()(key_type const& k) const
 312                 {
 313                     return k;
 314                 }
 315             };
 316             typedef key_type hash_type;
 317
 318             struct node_type
 319             {
 320                 std::pair< key_type const, mapped_type> m_Value;
 321
 322                 node_type() = delete;
 323                 node_type(node_type const&) = delete;
 324
 325                 template <typename Q, typename... Args>
 326                 node_type( hasher /*h*/, Q&& key, Args&&... args )
 327                     : m_Value( std::make_pair( key_type( std::forward<Q>( key )), mapped_type( std::forward<Args>(args)...)))
 328                 {}
 329             };
 330
 331             struct hash_accessor
 332             {
 333                 hash_type const& operator()(node_type const& node) const
 334                 {
 335                     return node.m_Value.first;
 336                 }
 337             };
 338         };
 339
 340         template <typename GC, typename Key, typename T, typename Traits>
 341         struct make_feldman_hashmap
 342         {
 343             typedef GC      gc;
 344             typedef Key     key_type;
 345             typedef T       mapped_type;
 346             typedef Traits  original_traits;
 347
 348
 349             typedef hash_selector< key_type, mapped_type, typename original_traits::hash > select;
 350             typedef typename select::hasher    hasher;
 351             typedef typename select::hash_type hash_type;
 352             typedef typename select::node_type node_type;
 353
 354             typedef cds::details::Allocator< node_type, typename original_traits::allocator > cxx_node_allocator;
 355
 356             struct node_disposer
 357             {
 358                 void operator()( node_type * p ) const
 359                 {
 360                     cxx_node_allocator().Delete( p );
 361                 }
 362             };
 363
 364             struct intrusive_traits: public original_traits
 365             {
 366                 typedef typename select::hash_accessor hash_accessor;
 367                 typedef node_disposer disposer;
 368             };
 369
 370             // Metafunction result
 371             typedef cds::intrusive::FeldmanHashSet< GC, node_type, intrusive_traits > type;
 372         };
 373     } // namespace details
 374     //@endcond
 375
 376 }} // namespace cds::container
 377
 378 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H