diff options
Diffstat (limited to 'absl/hash/internal')
-rw-r--r-- | absl/hash/internal/city.cc | 4 | ||||
-rw-r--r-- | absl/hash/internal/city.h | 7 | ||||
-rw-r--r-- | absl/hash/internal/city_test.cc | 4 | ||||
-rw-r--r-- | absl/hash/internal/hash.cc | 34 | ||||
-rw-r--r-- | absl/hash/internal/hash.h | 141 | ||||
-rw-r--r-- | absl/hash/internal/spy_hash_state.h | 17 |
6 files changed, 192 insertions, 15 deletions
diff --git a/absl/hash/internal/city.cc b/absl/hash/internal/city.cc index c7ad1591..e122c184 100644 --- a/absl/hash/internal/city.cc +++ b/absl/hash/internal/city.cc @@ -30,7 +30,7 @@ #include "absl/base/optimization.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace hash_internal { #ifdef ABSL_IS_BIG_ENDIAN @@ -342,5 +342,5 @@ uint64_t CityHash64WithSeeds(const char *s, size_t len, uint64_t seed0, } } // namespace hash_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/hash/internal/city.h b/absl/hash/internal/city.h index 7586ba08..161c7748 100644 --- a/absl/hash/internal/city.h +++ b/absl/hash/internal/city.h @@ -47,10 +47,13 @@ #include <stdint.h> #include <stdlib.h> // for size_t. + #include <utility> +#include "absl/base/config.h" + namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace hash_internal { typedef std::pair<uint64_t, uint64_t> uint128; @@ -87,7 +90,7 @@ inline uint64_t Hash128to64(const uint128 &x) { } } // namespace hash_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_HASH_INTERNAL_CITY_H_ diff --git a/absl/hash/internal/city_test.cc b/absl/hash/internal/city_test.cc index 1b9373c2..251d381d 100644 --- a/absl/hash/internal/city_test.cc +++ b/absl/hash/internal/city_test.cc @@ -20,7 +20,7 @@ #include "gtest/gtest.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace hash_internal { static const uint64_t k0 = 0xc3a5c85c97cb3127ULL; @@ -591,5 +591,5 @@ TEST(CityHashTest, Unchanging) { } } // namespace hash_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/hash/internal/hash.cc b/absl/hash/internal/hash.cc index 087b389b..b44ecb3a 100644 --- a/absl/hash/internal/hash.cc +++ b/absl/hash/internal/hash.cc @@ -15,11 +15,41 @@ #include "absl/hash/internal/hash.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace hash_internal { +uint64_t CityHashState::CombineLargeContiguousImpl32(uint64_t state, + const unsigned char* first, + size_t len) { + while (len >= PiecewiseChunkSize()) { + state = + Mix(state, absl::hash_internal::CityHash32(reinterpret_cast<const char*>(first), + PiecewiseChunkSize())); + len -= PiecewiseChunkSize(); + first += PiecewiseChunkSize(); + } + // Handle the remainder. + return CombineContiguousImpl(state, first, len, + std::integral_constant<int, 4>{}); +} + +uint64_t CityHashState::CombineLargeContiguousImpl64(uint64_t state, + const unsigned char* first, + size_t len) { + while (len >= PiecewiseChunkSize()) { + state = + Mix(state, absl::hash_internal::CityHash64(reinterpret_cast<const char*>(first), + PiecewiseChunkSize())); + len -= PiecewiseChunkSize(); + first += PiecewiseChunkSize(); + } + // Handle the remainder. + return CombineContiguousImpl(state, first, len, + std::integral_constant<int, 8>{}); +} + ABSL_CONST_INIT const void* const CityHashState::kSeed = &kSeed; } // namespace hash_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h index 81f1edf8..ae7a60cd 100644 --- a/absl/hash/internal/hash.h +++ b/absl/hash/internal/hash.h @@ -50,9 +50,15 @@ #include "absl/hash/internal/city.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace hash_internal { +class PiecewiseCombiner; + +// Internal detail: Large buffers are hashed in smaller chunks. This function +// returns the size of these chunks. +constexpr size_t PiecewiseChunkSize() { return 1024; } + // HashStateBase // // A hash state object represents an intermediate state in the computation @@ -69,7 +75,7 @@ namespace hash_internal { // // `static H combine_contiguous(H state, const unsigned char*, size_t)`. // -// `HashStateBase` will provide a complete implementations for a hash state +// `HashStateBase` will provide a complete implementation for a hash state // object in terms of this method. // // Example: @@ -118,6 +124,9 @@ class HashStateBase { // for-loop instead. template <typename T> static H combine_contiguous(H state, const T* data, size_t size); + + private: + friend class PiecewiseCombiner; }; // is_uniquely_represented @@ -188,6 +197,61 @@ H hash_bytes(H hash_state, const T& value) { return H::combine_contiguous(std::move(hash_state), start, sizeof(value)); } +// PiecewiseCombiner +// +// PiecewiseCombiner is an internal-only helper class for hashing a piecewise +// buffer of `char` or `unsigned char` as though it were contiguous. This class +// provides two methods: +// +// H add_buffer(state, data, size) +// H finalize(state) +// +// `add_buffer` can be called zero or more times, followed by a single call to +// `finalize`. This will produce the same hash expansion as concatenating each +// buffer piece into a single contiguous buffer, and passing this to +// `H::combine_contiguous`. +// +// Example usage: +// PiecewiseCombiner combiner; +// for (const auto& piece : pieces) { +// state = combiner.add_buffer(std::move(state), piece.data, piece.size); +// } +// return combiner.finalize(std::move(state)); +class PiecewiseCombiner { + public: + PiecewiseCombiner() : position_(0) {} + PiecewiseCombiner(const PiecewiseCombiner&) = delete; + PiecewiseCombiner& operator=(const PiecewiseCombiner&) = delete; + + // PiecewiseCombiner::add_buffer() + // + // Appends the given range of bytes to the sequence to be hashed, which may + // modify the provided hash state. + template <typename H> + H add_buffer(H state, const unsigned char* data, size_t size); + template <typename H> + H add_buffer(H state, const char* data, size_t size) { + return add_buffer(std::move(state), + reinterpret_cast<const unsigned char*>(data), size); + } + + // PiecewiseCombiner::finalize() + // + // Finishes combining the hash sequence, which may may modify the provided + // hash state. + // + // Once finalize() is called, add_buffer() may no longer be called. The + // resulting hash state will be the same as if the pieces passed to + // add_buffer() were concatenated into a single flat buffer, and then provided + // to H::combine_contiguous(). + template <typename H> + H finalize(H state); + + private: + unsigned char buf_[PiecewiseChunkSize()]; + size_t position_; +}; + // ----------------------------------------------------------------------------- // AbslHashValue for Basic Types // ----------------------------------------------------------------------------- @@ -364,6 +428,19 @@ H AbslHashValue(H hash_state, absl::string_view str) { str.size()); } +// Support std::wstring, std::u16string and std::u32string. +template <typename Char, typename Alloc, typename H, + typename = absl::enable_if_t<std::is_same<Char, wchar_t>::value || + std::is_same<Char, char16_t>::value || + std::is_same<Char, char32_t>::value>> +H AbslHashValue( + H hash_state, + const std::basic_string<Char, std::char_traits<Char>, Alloc>& str) { + return H::combine( + H::combine_contiguous(std::move(hash_state), str.data(), str.size()), + str.size()); +} + // ----------------------------------------------------------------------------- // AbslHashValue for Sequence Containers // ----------------------------------------------------------------------------- @@ -631,7 +708,8 @@ struct is_hashable : std::integral_constant<bool, HashSelect::template Apply<T>::value> {}; // CityHashState -class CityHashState : public HashStateBase<CityHashState> { +class ABSL_DLL CityHashState + : public HashStateBase<CityHashState> { // absl::uint128 is not an alias or a thin wrapper around the intrinsic. // We use the intrinsic when available to improve performance. #ifdef ABSL_HAVE_INTRINSIC_INT128 @@ -710,6 +788,16 @@ class CityHashState : public HashStateBase<CityHashState> { std::integral_constant<int, 8> /* sizeof_size_t*/); + // Slow dispatch path for calls to CombineContiguousImpl with a size argument + // larger than PiecewiseChunkSize(). Has the same effect as calling + // CombineContiguousImpl() repeatedly with the chunk stride size. + static uint64_t CombineLargeContiguousImpl32(uint64_t state, + const unsigned char* first, + size_t len); + static uint64_t CombineLargeContiguousImpl64(uint64_t state, + const unsigned char* first, + size_t len); + // Reads 9 to 16 bytes from p. // The first 8 bytes are in .first, the rest (zero padded) bytes are in // .second. @@ -777,6 +865,9 @@ inline uint64_t CityHashState::CombineContiguousImpl( // multiplicative hash. uint64_t v; if (len > 8) { + if (ABSL_PREDICT_FALSE(len > PiecewiseChunkSize())) { + return CombineLargeContiguousImpl32(state, first, len); + } v = absl::hash_internal::CityHash32(reinterpret_cast<const char*>(first), len); } else if (len >= 4) { v = Read4To8(first, len); @@ -797,6 +888,9 @@ inline uint64_t CityHashState::CombineContiguousImpl( // multiplicative hash. uint64_t v; if (len > 16) { + if (ABSL_PREDICT_FALSE(len > PiecewiseChunkSize())) { + return CombineLargeContiguousImpl64(state, first, len); + } v = absl::hash_internal::CityHash64(reinterpret_cast<const char*>(first), len); } else if (len > 8) { auto p = Read9To16(first, len); @@ -813,7 +907,6 @@ inline uint64_t CityHashState::CombineContiguousImpl( return Mix(state, v); } - struct AggregateBarrier {}; // HashImpl @@ -850,8 +943,46 @@ template <typename T> H HashStateBase<H>::combine_contiguous(H state, const T* data, size_t size) { return hash_internal::hash_range_or_bytes(std::move(state), data, size); } + +// HashStateBase::PiecewiseCombiner::add_buffer() +template <typename H> +H PiecewiseCombiner::add_buffer(H state, const unsigned char* data, + size_t size) { + if (position_ + size < PiecewiseChunkSize()) { + // This partial chunk does not fill our existing buffer + memcpy(buf_ + position_, data, size); + position_ += size; + return state; + } + + // Complete the buffer and hash it + const size_t bytes_needed = PiecewiseChunkSize() - position_; + memcpy(buf_ + position_, data, bytes_needed); + state = H::combine_contiguous(std::move(state), buf_, PiecewiseChunkSize()); + data += bytes_needed; + size -= bytes_needed; + + // Hash whatever chunks we can without copying + while (size >= PiecewiseChunkSize()) { + state = H::combine_contiguous(std::move(state), data, PiecewiseChunkSize()); + data += PiecewiseChunkSize(); + size -= PiecewiseChunkSize(); + } + // Fill the buffer with the remainder + memcpy(buf_, data, size); + position_ = size; + return state; +} + +// HashStateBase::PiecewiseCombiner::finalize() +template <typename H> +H PiecewiseCombiner::finalize(H state) { + // Hash the remainder left in the buffer, which may be empty + return H::combine_contiguous(std::move(state), buf_, position_); +} + } // namespace hash_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_HASH_INTERNAL_HASH_H_ diff --git a/absl/hash/internal/spy_hash_state.h b/absl/hash/internal/spy_hash_state.h index 57cd70b2..c0831208 100644 --- a/absl/hash/internal/spy_hash_state.h +++ b/absl/hash/internal/spy_hash_state.h @@ -25,7 +25,7 @@ #include "absl/strings/str_join.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace hash_internal { // SpyHashState is an implementation of the HashState API that simply @@ -147,6 +147,19 @@ class SpyHashStateImpl : public HashStateBase<SpyHashStateImpl<T>> { static SpyHashStateImpl combine_contiguous(SpyHashStateImpl hash_state, const unsigned char* begin, size_t size) { + const size_t large_chunk_stride = PiecewiseChunkSize(); + if (size > large_chunk_stride) { + // Combining a large contiguous buffer must have the same effect as + // doing it piecewise by the stride length, followed by the (possibly + // empty) remainder. + while (size >= large_chunk_stride) { + hash_state = SpyHashStateImpl::combine_contiguous( + std::move(hash_state), begin, large_chunk_stride); + begin += large_chunk_stride; + size -= large_chunk_stride; + } + } + hash_state.hash_representation_.emplace_back( reinterpret_cast<const char*>(begin), size); return hash_state; @@ -212,7 +225,7 @@ void AbslHashValue(SpyHashStateImpl<T>, const U&); using SpyHashState = SpyHashStateImpl<void>; } // namespace hash_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_HASH_INTERNAL_SPY_HASH_STATE_H_ |