From 01470a158e4c8d196b0b43291b75f68156be34ba Mon Sep 17 00:00:00 2001 From: khizmax Date: Sun, 19 Feb 2017 11:54:34 +0300 Subject: [PATCH] [FeldmanHashSet/Map]: hash splitter algo can be specified in Traits --- cds/algo/split_bitstring.h | 7 +++-- cds/container/details/feldman_hashset_base.h | 15 ++++++++++ cds/intrusive/details/feldman_hashset_base.h | 30 +++++++++++++++++++- 3 files changed, 49 insertions(+), 3 deletions(-) diff --git a/cds/algo/split_bitstring.h b/cds/algo/split_bitstring.h index 4f56fc56..7935e8e7 100644 --- a/cds/algo/split_bitstring.h +++ b/cds/algo/split_bitstring.h @@ -37,7 +37,7 @@ namespace cds { namespace algo { /// Cuts a bit sequence from fixed-size bit-string /** - The splitter can be used as iterator over bit-string. + The splitter can be used as an iterator over bit-string. Each call of \p cut() or \p safe_cut() cuts the bit count specified and keeps the position inside bit-string for the next call. @@ -48,7 +48,7 @@ namespace cds { namespace algo { - \p BitString - a fixed-sized type that interprets as bit string - \p BitStringSize - the size of \p BitString in bytes, default is sizeof( BitString ). You can specify 0 for default. - - \p UInt - an unsigned integer, return type of \p cut() + - \p UInt - an unsigned integer, return type for \p cut() */ template ::type > class split_bitstring @@ -58,6 +58,9 @@ namespace cds { namespace algo { typedef UInt uint_type; ///< Bit-string portion type static CDS_CONSTEXPR size_t const c_bitstring_size = BitStringSize ? BitStringSize : sizeof( BitString ); ///< size of \p BitString in bytes + /// Minimum count of bits to be cut + static CDS_CONSTEXPR size_t const c_nMinBitCut = 1; + //@cond static CDS_CONSTEXPR size_t const c_nHashSize = (c_bitstring_size + sizeof(uint_type) - 1) / sizeof(uint_type); static CDS_CONSTEXPR size_t const c_nBitPerByte = 8; diff --git a/cds/container/details/feldman_hashset_base.h b/cds/container/details/feldman_hashset_base.h index 02016d69..56074a3b 100644 --- a/cds/container/details/feldman_hashset_base.h +++ b/cds/container/details/feldman_hashset_base.h @@ -53,6 +53,13 @@ namespace cds { namespace container { template using hash_size = cds::intrusive::feldman_hashset::hash_size< Size >; + /// Hash splitter + /** + @copydetails cds::intrusive::feldman_hashset::traits::hash_splitter + */ + template + using hash_splitter = cds::intrusive::feldman_hashset::hash_splitter< Splitter >; + /// \p FeldmanHashSet internal statistics, see cds::intrusive::feldman_hashset::stat template using stat = cds::intrusive::feldman_hashset::stat< EventCounter >; @@ -82,6 +89,12 @@ namespace cds { namespace container { */ 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 @@ -141,6 +154,8 @@ namespace cds { namespace container { @copydetails traits::hash_accessor - \p feldman_hashset::hash_size - the size of hash value in bytes. @copydetails traits::hash_size + - \p feldman_hashset::hash_splitter - a hash splitter algorithm + @copydetails traits::hash_splitter - \p opt::allocator - item allocator @copydetails traits::allocator - \p opt::node_allocator - array node allocator. diff --git a/cds/intrusive/details/feldman_hashset_base.h b/cds/intrusive/details/feldman_hashset_base.h index 00707e06..75abfe26 100644 --- a/cds/intrusive/details/feldman_hashset_base.h +++ b/cds/intrusive/details/feldman_hashset_base.h @@ -77,6 +77,21 @@ namespace cds { namespace intrusive { //@endcond }; + /// Hash splitter option + /** + @copydetails traits::hash_splitter + */ + template + struct hash_splitter { + //@cond + template struct pack: public Base + { + typedef Splitter hash_splitter; + }; + //@endcond + }; + + /// \p FeldmanHashSet internal statistics template struct stat { @@ -197,6 +212,13 @@ namespace cds { namespace intrusive { */ static CDS_CONSTEXPR size_t const hash_size = 0; + /// Hash splitter + /** + This trait specifies hash bit-string splitter algorithm. + By default, \p cds::algo::split_bitstring< HashType, HashSize > is used + */ + typedef cds::opt::none hash_splitter; + /// Disposer for removing data nodes typedef cds::intrusive::opt::v::empty_disposer disposer; @@ -262,6 +284,8 @@ namespace cds { namespace intrusive { @copydetails traits::hash_accessor - \p feldman_hashset::hash_size - the size of hash value in bytes. @copydetails traits::hash_size + - \p feldman_hashset::hash_splitter - a hash splitter algorithm + @copydetails traits::hash_splitter - \p opt::node_allocator - array node allocator. @copydetails traits::node_allocator - \p opt::compare - hash comparison functor. No default functor is provided. @@ -404,7 +428,11 @@ namespace cds { namespace intrusive { /// The size of hash_type in bytes, see \p traits::hash_size for explanation static CDS_CONSTEXPR size_t const c_hash_size = traits::hash_size == 0 ? sizeof( hash_type ) : static_cast( traits::hash_size ); - typedef feldman_hashset::details::hash_splitter< hash_type, c_hash_size > hash_splitter; + typedef typename std::conditional< + std::is_same< typename traits::hash_splitter, cds::opt::none >::value, + feldman_hashset::details::hash_splitter< hash_type, c_hash_size >, + typename traits::hash_splitter + >::type hash_splitter; enum node_flags { flag_array_converting = 1, ///< the cell is converting from data node to an array node -- 2.34.1