summaryrefslogtreecommitdiff
path: root/absl/hash/internal
diff options
context:
space:
mode:
Diffstat (limited to 'absl/hash/internal')
-rw-r--r--absl/hash/internal/hash.cc30
-rw-r--r--absl/hash/internal/hash.h121
-rw-r--r--absl/hash/internal/spy_hash_state.h13
3 files changed, 162 insertions, 2 deletions
diff --git a/absl/hash/internal/hash.cc b/absl/hash/internal/hash.cc
index 4ab7a9f8..c17f3be1 100644
--- a/absl/hash/internal/hash.cc
+++ b/absl/hash/internal/hash.cc
@@ -17,6 +17,36 @@
namespace absl {
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
diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h
index 4ff4a126..e99f8e75 100644
--- a/absl/hash/internal/hash.h
+++ b/absl/hash/internal/hash.h
@@ -52,6 +52,12 @@
namespace absl {
namespace hash_internal {
+class PiecewiseCombiner;
+
+// Internal detail: Large buffers are hashed in smaller chunks. This function
+// returns the size of these chunks.
+constexpr int PiecewiseChunkSize() { return 1024; }
+
// HashStateBase
//
// A hash state object represents an intermediate state in the computation
@@ -68,7 +74,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:
@@ -117,6 +123,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
@@ -187,6 +196,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
// -----------------------------------------------------------------------------
@@ -709,6 +773,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.
@@ -776,6 +850,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);
@@ -796,6 +873,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);
@@ -812,7 +892,6 @@ inline uint64_t CityHashState::CombineContiguousImpl(
return Mix(state, v);
}
-
struct AggregateBarrier {};
// HashImpl
@@ -849,6 +928,44 @@ 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 std::move(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 std::move(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
} // namespace absl
diff --git a/absl/hash/internal/spy_hash_state.h b/absl/hash/internal/spy_hash_state.h
index c4cc8d07..05c7cafe 100644
--- a/absl/hash/internal/spy_hash_state.h
+++ b/absl/hash/internal/spy_hash_state.h
@@ -146,6 +146,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;