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