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