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 splitter
 156             /**
 157                 @copydetails cds::intrusive::feldman_hashset::traits::hash_splitter
 158             */
 159             typedef cds::opt::none hash_splitter;
 160
 161             /// Hash comparing functor
 162             /**
 163                 @copydetails cds::intrusive::feldman_hashset::traits::compare
 164             */
 165             typedef cds::opt::none compare;
 166
 167             /// Specifies binary predicate used for hash compare.
 168             /**
 169                 @copydetails cds::intrusive::feldman_hashset::traits::less
 170             */
 171             typedef cds::opt::none less;
 172
 173             /// Item counter
 174             /**
 175                 @copydetails cds::intrusive::feldman_hashset::traits::item_counter
 176             */
 177             typedef cds::atomicity::item_counter item_counter;
 178
 179             /// Item allocator
 180             /**
 181                 Default is \ref CDS_DEFAULT_ALLOCATOR
 182             */
 183             typedef CDS_DEFAULT_ALLOCATOR allocator;
 184
 185             /// Array node allocator
 186             /**
 187                 @copydetails cds::intrusive::feldman_hashset::traits::node_allocator
 188             */
 189             typedef CDS_DEFAULT_ALLOCATOR node_allocator;
 190
 191             /// C++ memory ordering model
 192             /**
 193                 @copydetails cds::intrusive::feldman_hashset::traits::memory_model
 194             */
 195             typedef cds::opt::v::relaxed_ordering memory_model;
 196
 197             /// Back-off strategy
 198             typedef cds::backoff::Default back_off;
 199
 200             /// Internal statistics
 201             /**
 202                 @copydetails cds::intrusive::feldman_hashset::traits::stat
 203             */
 204             typedef empty_stat stat;
 205
 206             /// RCU deadlock checking policy (only for \ref cds_container_FeldmanHashMap_rcu "RCU-based FeldmanHashMap")
 207             /**
 208                 @copydetails cds::intrusive::feldman_hashset::traits::rcu_check_deadlock
 209             */
 210             typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
 211         };
 212
 213         /// Metafunction converting option list to \p feldman_hashmap::traits
 214         /**
 215             Supported \p Options are:
 216             - \p opt::hash - a hash functor, default is \p std::hash
 217                 @copydetails traits::hash
 218             - \p feldman_hashmap::hash_size - the size of hash value in bytes.
 219                 @copydetails traits::hash_size
 220             - \p opt::allocator - item allocator
 221                 @copydetails traits::allocator
 222             - \p opt::node_allocator - array node allocator.
 223                 @copydetails traits::node_allocator
 224             - \p opt::compare - hash comparison functor. No default functor is provided.
 225                 If the option is not specified, the \p opt::less is used.
 226             - \p opt::less - specifies binary predicate used for hash comparison.
 227                 @copydetails cds::container::feldman_hashmap::traits::less
 228             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 229             - \p opt::item_counter - the type of item counting feature.
 230                 @copydetails cds::container::feldman_hashmap::traits::item_counter
 231             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 232                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 233             - \p opt::stat - internal statistics. By default, it is disabled (\p feldman_hashmap::empty_stat).
 234                 To enable it use \p feldman_hashmap::stat
 235             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet"
 236                 Default is \p opt::v::rcu_throw_deadlock
 237         */
 238         template <typename... Options>
 239         struct make_traits
 240         {
 241 #   ifdef CDS_DOXYGEN_INVOKED
 242             typedef implementation_defined type ;   ///< Metafunction result
 243 #   else
 244             typedef typename cds::opt::make_options<
 245                 typename cds::opt::find_type_traits< traits, Options... >::type
 246                 ,Options...
 247             >::type   type;
 248 #   endif
 249         };
 250     } // namespace feldman_hashmap
 251
 252     //@cond
 253     // Forward declaration
 254     template < class GC, typename Key, typename T, class Traits = feldman_hashmap::traits >
 255     class FeldmanHashMap;
 256     //@endcond
 257
 258     //@cond
 259     namespace details {
 260
 261         template <typename Key, typename Value, typename Hash>
 262         struct hash_selector
 263         {
 264             typedef Key key_type;
 265             typedef Value mapped_type;
 266             typedef Hash hasher;
 267
 268             typedef typename std::decay<
 269                 typename std::remove_reference<
 270                 decltype(hasher()(std::declval<key_type>()))
 271                 >::type
 272             >::type hash_type;
 273
 274             struct node_type
 275             {
 276                 std::pair< key_type const, mapped_type> m_Value;
 277                 hash_type const m_hash;
 278
 279                 node_type() = delete;
 280                 node_type(node_type const&) = delete;
 281
 282                 template <typename Q>
 283                 node_type(hasher& h, Q const& key)
 284                     : m_Value( std::move( std::make_pair( key_type( key ), mapped_type())))
 285                     , m_hash( h( m_Value.first ))
 286                 {}
 287
 288                 template <typename Q, typename U >
 289                 node_type(hasher& h, Q const& key, U const& val)
 290                     : m_Value( std::move( std::make_pair( key_type( key ), mapped_type(val))))
 291                     , m_hash( h( m_Value.first ))
 292                 {}
 293
 294                 template <typename Q, typename... Args>
 295                 node_type(hasher& h, Q&& key, Args&&... args)
 296                     : m_Value( std::move(std::make_pair( key_type( std::forward<Q>(key)), std::move( mapped_type(std::forward<Args>(args)...)))))
 297                     , m_hash( h( m_Value.first ))
 298                 {}
 299             };
 300
 301             struct hash_accessor
 302             {
 303                 hash_type const& operator()(node_type const& node) const
 304                 {
 305                     return node.m_hash;
 306                 }
 307             };
 308         };
 309
 310         template <typename Key, typename Value>
 311         struct hash_selector<Key, Value, opt::none>
 312         {
 313             typedef Key key_type;
 314             typedef Value mapped_type;
 315
 316             struct hasher {
 317                 key_type const& operator()(key_type const& k) const
 318                 {
 319                     return k;
 320                 }
 321             };
 322             typedef key_type hash_type;
 323
 324             struct node_type
 325             {
 326                 std::pair< key_type const, mapped_type> m_Value;
 327
 328                 node_type() = delete;
 329                 node_type(node_type const&) = delete;
 330
 331                 template <typename Q, typename... Args>
 332                 node_type( hasher /*h*/, Q&& key, Args&&... args )
 333                     : m_Value( std::make_pair( key_type( std::forward<Q>( key )), mapped_type( std::forward<Args>(args)...)))
 334                 {}
 335             };
 336
 337             struct hash_accessor
 338             {
 339                 hash_type const& operator()(node_type const& node) const
 340                 {
 341                     return node.m_Value.first;
 342                 }
 343             };
 344         };
 345
 346         template <typename GC, typename Key, typename T, typename Traits>
 347         struct make_feldman_hashmap
 348         {
 349             typedef GC      gc;
 350             typedef Key     key_type;
 351             typedef T       mapped_type;
 352             typedef Traits  original_traits;
 353
 354
 355             typedef hash_selector< key_type, mapped_type, typename original_traits::hash > select;
 356             typedef typename select::hasher    hasher;
 357             typedef typename select::hash_type hash_type;
 358             typedef typename select::node_type node_type;
 359
 360             typedef cds::details::Allocator< node_type, typename original_traits::allocator > cxx_node_allocator;
 361
 362             struct node_disposer
 363             {
 364                 void operator()( node_type * p ) const
 365                 {
 366                     cxx_node_allocator().Delete( p );
 367                 }
 368             };
 369
 370             struct intrusive_traits: public original_traits
 371             {
 372                 typedef typename select::hash_accessor hash_accessor;
 373                 typedef node_disposer disposer;
 374             };
 375
 376             // Metafunction result
 377             typedef cds::intrusive::FeldmanHashSet< GC, node_type, intrusive_traits > type;
 378         };
 379     } // namespace details
 380     //@endcond
 381
 382 }} // namespace cds::container
 383
 384 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H