X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=blobdiff_plain;f=cds%2Fcontainer%2Fdetails%2Ffeldman_hashmap_base.h;h=a6dbab0766a3c59aab39ad36a1b81ea7a73c251a;hp=20eab6b3dfa7f60021e9a73e7342704944e2994e;hb=dd527e913731ce28ff1a6cea10bdabfd507ef856;hpb=87974cb23acebee8e4f679d922e264cc08a9a4eb diff --git a/cds/container/details/feldman_hashmap_base.h b/cds/container/details/feldman_hashmap_base.h index 20eab6b3..a6dbab07 100644 --- a/cds/container/details/feldman_hashmap_base.h +++ b/cds/container/details/feldman_hashmap_base.h @@ -1,4 +1,32 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ #ifndef CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H #define CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H @@ -23,6 +51,17 @@ namespace cds { namespace container { template using bitwise_compare = cds::intrusive::feldman_hashset::bitwise_compare< T >; + /// \p FeldmanHashMap level statistics + typedef cds::intrusive::feldman_hashset::level_statistics level_statistics; + + /// Key size option + /** + @copydetails cds::container::feldman_hashmap::traits::hash_size + */ + template + using hash_size = cds::intrusive::feldman_hashset::hash_size< Size >; + + /// \p FeldmanHashMap traits struct traits { @@ -34,7 +73,7 @@ namespace cds { namespace container { CityHash or its successor FarmHash. - If you use a fixed-sized key you may use it directly instead of a hash. + If you use a fixed-sized key you can use it directly instead of a hash. In such case \p %traits::hash should be specified as \p opt::none. However, if you want to use the hash values or if your key type is not fixed-sized you must specify a proper hash functor in your traits. @@ -91,6 +130,34 @@ namespace cds { namespace container { */ typedef opt::none hash; + /// The size of hash value in bytes + /** + By default, the size of hash value is sizeof( hash_type ) + where \p hash_type is type of \p hash() result or sizeof( key ) if you use fixed-sized key. + + Sometimes that size is wrong, for example, for that 6-byte key: + \code + struct key_type { + uint32_t key; + uint16_t subkey; + }; + + static_assert( sizeof( key_type ) == 6, "Key type size mismatch" ); + \endcode + Here sizeof( key_type ) == 8 so \p static_assert will be thrown. + + For that case you can specify \p hash_size explicitly. + + Value \p 0 means auto-calculated sizeof( key_type ). + */ + static CDS_CONSTEXPR size_t const hash_size = 0; + + /// Hash splitter + /** + @copydetails cds::intrusive::feldman_hashset::traits::hash_splitter + */ + typedef cds::opt::none hash_splitter; + /// Hash comparing functor /** @copydetails cds::intrusive::feldman_hashset::traits::compare @@ -148,6 +215,8 @@ namespace cds { namespace container { Supported \p Options are: - \p opt::hash - a hash functor, default is \p std::hash @copydetails traits::hash + - \p feldman_hashmap::hash_size - the size of hash value in bytes. + @copydetails traits::hash_size - \p opt::allocator - item allocator @copydetails traits::allocator - \p opt::node_allocator - array node allocator. @@ -212,20 +281,20 @@ namespace cds { namespace container { template node_type(hasher& h, Q const& key) - : m_Value(std::move(std::make_pair(key, mapped_type()))) - , m_hash(h(m_Value.first)) + : m_Value( std::move( std::make_pair( key_type( key ), mapped_type()))) + , m_hash( h( m_Value.first )) {} template node_type(hasher& h, Q const& key, U const& val) - : m_Value(std::move(std::make_pair(key, mapped_type(val)))) - , m_hash(h(m_Value.first)) + : m_Value( std::move( std::make_pair( key_type( key ), mapped_type(val)))) + , m_hash( h( m_Value.first )) {} template node_type(hasher& h, Q&& key, Args&&... args) - : m_Value(std::move(std::make_pair(std::forward(key), std::move(mapped_type(std::forward(args)...))))) - , m_hash(h(m_Value.first)) + : m_Value( std::move(std::make_pair( key_type( std::forward(key)), std::move( mapped_type(std::forward(args)...))))) + , m_hash( h( m_Value.first )) {} }; @@ -259,19 +328,9 @@ namespace cds { namespace container { node_type() = delete; node_type(node_type const&) = delete; - template - node_type(hasher /*h*/, Q const& key) - : m_Value(std::move(std::make_pair(key, mapped_type()))) - {} - - template - node_type(hasher /*h*/, Q const& key, U const& val) - : m_Value(std::move(std::make_pair(key, mapped_type(val)))) - {} - template - node_type(hasher /*h*/, Q&& key, Args&&... args) - : m_Value(std::move(std::make_pair(std::forward(key), std::move(mapped_type(std::forward(args)...))))) + node_type( hasher /*h*/, Q&& key, Args&&... args ) + : m_Value( std::make_pair( key_type( std::forward( key )), mapped_type( std::forward(args)...))) {} };