From b94a42b978251c4cdb4eb0be2a2e8d9dc8949eba Mon Sep 17 00:00:00 2001 From: Steven Le Rouzic Date: Tue, 7 Jan 2025 23:17:50 +0100 Subject: More work on hashing --- asl/buffer.hpp | 6 ++++ asl/hash.hpp | 34 ++++++++++++++----- asl/meta.hpp | 3 ++ asl/span.hpp | 6 ++++ asl/string_view.hpp | 2 +- asl/tests/hash_tests.cpp | 88 ++++++++++++++++++++++++++++++++++++++++++++++-- asl/tests/meta_tests.cpp | 11 ++++++ 7 files changed, 138 insertions(+), 12 deletions(-) diff --git a/asl/buffer.hpp b/asl/buffer.hpp index 90bfc96..7d33c73 100644 --- a/asl/buffer.hpp +++ b/asl/buffer.hpp @@ -389,6 +389,12 @@ public: ASL_ASSERT(i >= 0 && i <= size()); return data()[i]; } + + template + friend H AslHashValue(H h, const buffer& b) + { + return H::combine_contiguous(ASL_MOVE(h), b.as_span()); + } }; } // namespace asl diff --git a/asl/hash.hpp b/asl/hash.hpp index fd3c116..5f81e92 100644 --- a/asl/hash.hpp +++ b/asl/hash.hpp @@ -68,13 +68,26 @@ struct HashState constexpr HashState() = default; explicit constexpr HashState(uint128_t s) : state{s} {} - static HashState combine_bytes(HashState h, span bytes) + template + static HashState combine_contiguous(HashState h, span s) { - auto hashed = city_hash::CityHash128WithSeed( - reinterpret_cast(bytes.data()), - static_cast(bytes.size()), - h.state); - return HashState{hashed}; + if constexpr (uniquely_represented) + { + auto bytes = as_bytes(s); + auto hashed = city_hash::CityHash128WithSeed( + reinterpret_cast(bytes.data()), + static_cast(bytes.size()), + h.state); + return HashState{hashed}; + } + else + { + for (const auto& value: s) + { + h = AslHashValue(ASL_MOVE(h), value); + } + return h; + } } static constexpr HashState combine(HashState h) @@ -85,7 +98,7 @@ struct HashState template Arg, hashable_generic... Remaining> static constexpr HashState combine(HashState h, const Arg& arg, const Remaining&... remaining) { - return combine(AslHashValue(h, arg), remaining...); + return combine(AslHashValue(ASL_MOVE(h), arg), remaining...); } }; @@ -95,15 +108,18 @@ concept hashable = hashable_generic; template constexpr H AslHashValue(H h, const T& value) { - return H::combine_bytes(h, as_bytes(span{&value, 1})); + return H::combine_contiguous(ASL_MOVE(h), span{&value, 1}); } template constexpr H AslHashValue(H h, bool value) { - return AslHashValue(h, value ? 1 : 0); + return AslHashValue(ASL_MOVE(h), value ? 1 : 0); } +template +constexpr void AslHashValue(H h, T*); // Don't hash pointers + template constexpr uint64_t hash_value(const T& value) { diff --git a/asl/meta.hpp b/asl/meta.hpp index c353b0f..8940ec6 100644 --- a/asl/meta.hpp +++ b/asl/meta.hpp @@ -189,8 +189,11 @@ template<> struct _is_integer_helper : true_type {}; template concept is_integer = _is_integer_helper>::value; +template concept is_enum = __is_enum(T); + template struct is_uniquely_represented : false_type {}; template struct is_uniquely_represented : true_type {}; +template struct is_uniquely_represented : true_type {}; template<> struct is_uniquely_represented : true_type {}; template<> struct is_uniquely_represented : true_type {}; diff --git a/asl/span.hpp b/asl/span.hpp index 8f6fb4a..bb36291 100644 --- a/asl/span.hpp +++ b/asl/span.hpp @@ -171,6 +171,12 @@ public: ASL_ASSERT(sub_size >= 0 && sub_size <= size()); return span{ data() + size() - sub_size, sub_size }; } + + template + friend H AslHashValue(H h, const span& s) + { + return H::combine_contiguous(ASL_MOVE(h), span{s.data(), s.size()}); + } }; template diff --git a/asl/string_view.hpp b/asl/string_view.hpp index 533a4a8..673e3bc 100644 --- a/asl/string_view.hpp +++ b/asl/string_view.hpp @@ -89,7 +89,7 @@ public: template friend H AslHashValue(H h, string_view sv) { - return H::combine(H::combine_bytes(h, as_bytes(sv.as_span())), sv.size()); + return H::combine(H::combine_contiguous(h, as_bytes(sv.as_span())), sv.size()); } }; diff --git a/asl/tests/hash_tests.cpp b/asl/tests/hash_tests.cpp index d0df77a..1ef051e 100644 --- a/asl/tests/hash_tests.cpp +++ b/asl/tests/hash_tests.cpp @@ -2,6 +2,11 @@ #include "asl/hash.hpp" #include "asl/string_view.hpp" #include "asl/string.hpp" +#include "asl/buffer.hpp" + +static_assert(!asl::hashable); +static_assert(!asl::hashable); +static_assert(!asl::hashable); static_assert(asl::hashable); static_assert(asl::hashable); @@ -51,8 +56,87 @@ ASL_TEST(strings) ASL_TEST_EXPECT(asl::hash_value("hello"_sv) == asl::hash_value(asl::string("hello"_sv))); } -// @Todo span, buffer (add combine_contiguous (optimize uniquely_represented)) -// @Todo enum classes +static_assert(asl::hashable>); +static_assert(asl::hashable>); + +ASL_TEST(span) +{ + int ints1[] = {1, 2, 3}; + int ints2[] = {1, 2, 3}; + int ints3[] = {1, 2}; + int ints4[] = {3, 2, 1}; + + ASL_TEST_EXPECT(asl::hash_value(asl::span(ints1)) == asl::hash_value(asl::span(ints2))); + ASL_TEST_EXPECT(asl::hash_value(asl::span(ints1)) != asl::hash_value(asl::span(ints3))); + ASL_TEST_EXPECT(asl::hash_value(asl::span(ints1)) != asl::hash_value(asl::span(ints4))); + + asl::string_view strs1[] = {"a", "abc", "hello"}; + asl::string_view strs2[] = {"a", "abc", "hello"}; + asl::string_view strs3[] = {"a", "abc"}; + asl::string_view strs4[] = {"a", "abc", "hello", "what"}; + + ASL_TEST_EXPECT(asl::hash_value(asl::span(strs1)) == asl::hash_value(asl::span(strs2))); + ASL_TEST_EXPECT(asl::hash_value(asl::span(strs1)) != asl::hash_value(asl::span(strs3))); + ASL_TEST_EXPECT(asl::hash_value(asl::span(strs1)) != asl::hash_value(asl::span(strs4))); +} + +static_assert(asl::hashable>); + +ASL_TEST(buffer) +{ + asl::buffer ints1; + ints1.push(1); + ints1.push(2); + ints1.push(3); + + asl::buffer ints2; + ints2.push(1); + ints2.push(2); + ints2.push(3); + + asl::buffer ints3; + ints3.push(1); + ints3.push(2); + + asl::buffer ints4; + ints4.push(1); + ints4.push(2); + ints4.push(4); + + ASL_TEST_EXPECT(asl::hash_value(ints1) == asl::hash_value(ints2)); + ASL_TEST_EXPECT(asl::hash_value(ints1) != asl::hash_value(ints3)); + ASL_TEST_EXPECT(asl::hash_value(ints1) != asl::hash_value(ints4)); + ASL_TEST_EXPECT(asl::hash_value(ints1) == asl::hash_value(ints1.as_span())); + + asl::buffer strs1; + strs1.push("Hello"); + strs1.push("World"); + + asl::buffer strs2; + strs2.push("Hello"); + strs2.push("World"); + + asl::buffer strs3; + strs3.push("Hello"); + strs3.push("world"); + + asl::buffer strs4; + strs4.push("Hello"); + strs4.push("World"); + strs4.push("World"); + + ASL_TEST_EXPECT(asl::hash_value(strs1) == asl::hash_value(strs2)); + ASL_TEST_EXPECT(asl::hash_value(strs1) != asl::hash_value(strs3)); + ASL_TEST_EXPECT(asl::hash_value(strs1) != asl::hash_value(strs4)); + ASL_TEST_EXPECT(asl::hash_value(strs1) == asl::hash_value(strs1.as_span())); +} + +enum Enum1 {}; +enum class Enum2 {}; + +static_assert(asl::hashable); +static_assert(asl::hashable); + // @Todo option (optimize uniquely_represented + has_niche) // @Todo status, status_or // @Todo box diff --git a/asl/tests/meta_tests.cpp b/asl/tests/meta_tests.cpp index 4fedd71..c393631 100644 --- a/asl/tests/meta_tests.cpp +++ b/asl/tests/meta_tests.cpp @@ -236,3 +236,14 @@ static_assert(!asl::is_floating_point); static_assert(asl::uniquely_represented); static_assert(asl::uniquely_represented); static_assert(!asl::uniquely_represented); + +enum Enum1 {}; +enum class Enum2 {}; + +static_assert(asl::uniquely_represented); +static_assert(asl::uniquely_represented); + +static_assert(!asl::is_enum); +static_assert(asl::is_enum); +static_assert(asl::is_enum); + -- cgit