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