Some more work on hashing

5 files changed, 95 insertions, 3 deletions

diff --git a/asl/BUILD.bazel b/asl/BUILD.bazel
index aa1eb90..5621cbd 100644
--- a/asl/BUILD.bazel
+++ b/asl/BUILD.bazel
@@ -58,6 +58,7 @@ cc_library(
     "float",

     "format",

     "functional",

+    "hash",

     "integers",

     "maybe_uninit",

     "meta",

diff --git a/asl/hash.hpp b/asl/hash.hpp
index 5eb64f6..fd3c116 100644
--- a/asl/hash.hpp
+++ b/asl/hash.hpp
@@ -2,7 +2,7 @@
 

 #include "asl/integers.hpp"

 #include "asl/meta.hpp"

-#include "asl/utility.hpp"

+#include "asl/span.hpp"

 

 namespace asl::city_hash

 {

@@ -68,6 +68,15 @@ struct HashState
     constexpr HashState() = default;

     explicit constexpr HashState(uint128_t s) : state{s} {}

 

+    static HashState combine_bytes(HashState h, span<const byte> bytes)

+    {

+        auto hashed = city_hash::CityHash128WithSeed(

+            reinterpret_cast<const char*>(bytes.data()),

+            static_cast<size_t>(bytes.size()),

+            h.state);

+        return HashState{hashed};

+    }

+

     static constexpr HashState combine(HashState h)

     {

         return h;

@@ -86,8 +95,20 @@ concept hashable = hashable_generic<T, HashState>;
 template<typename H, uniquely_represented T>

 constexpr H AslHashValue(H h, const T& value)

 {

-    auto hashed = city_hash::CityHash128WithSeed(reinterpret_cast<const char*>(&value), size_of<T>, h.state);

-    return HashState{hashed};

+    return H::combine_bytes(h, as_bytes(span<const T>{&value, 1}));

+}

+

+template<typename H>

+constexpr H AslHashValue(H h, bool value)

+{

+    return AslHashValue(h, value ? 1 : 0);

+}

+

+template<hashable T>

+constexpr uint64_t hash_value(const T& value)

+{

+    auto result = AslHashValue(HashState{}, value).state;

+    return city_hash::Hash128to64(result);

 }

 

 } // namespace asl

diff --git a/asl/string.hpp b/asl/string.hpp
index 86fc304..fbeffe5 100644
--- a/asl/string.hpp
+++ b/asl/string.hpp
@@ -57,6 +57,12 @@ public:
     {
         return as_string_view() == other;
     }
+
+    template<typename H>
+    friend H AslHashValue(H h, const string& str)
+    {
+        return H::combine(h, str.as_string_view());
+    }
 };
 
 string() -> string<>;
diff --git a/asl/string_view.hpp b/asl/string_view.hpp
index c75695c..533a4a8 100644
--- a/asl/string_view.hpp
+++ b/asl/string_view.hpp
@@ -85,6 +85,12 @@ public:
         if (m_size != other.m_size) { return false; }
         return memcmp(m_data, other.m_data, m_size) == 0;
     }
+
+    template<typename H>
+    friend H AslHashValue(H h, string_view sv)
+    {
+        return H::combine(H::combine_bytes(h, as_bytes(sv.as_span())), sv.size());
+    }
 };
 
 } // namespace asl
diff --git a/asl/tests/hash_tests.cpp b/asl/tests/hash_tests.cpp
new file mode 100644
index 0000000..d0df77a
--- /dev/null
+++ b/asl/tests/hash_tests.cpp
@@ -0,0 +1,58 @@
+#include "asl/testing/testing.hpp"

+#include "asl/hash.hpp"

+#include "asl/string_view.hpp"

+#include "asl/string.hpp"

+

+static_assert(asl::hashable<uint8_t>);

+static_assert(asl::hashable<uint16_t>);

+static_assert(asl::hashable<uint32_t>);

+static_assert(asl::hashable<uint64_t>);

+static_assert(asl::hashable<uint128_t>);

+

+static_assert(asl::hashable<int8_t>);

+static_assert(asl::hashable<int16_t>);

+static_assert(asl::hashable<int32_t>);

+static_assert(asl::hashable<int64_t>);

+

+ASL_TEST(integers)

+{

+    uint64_t a = asl::hash_value<uint16_t>(45);

+    uint64_t b = asl::hash_value<uint16_t>(45);

+    uint64_t c = asl::hash_value<uint16_t>(46);

+    uint64_t d = asl::hash_value<uint32_t>(45);

+

+    ASL_TEST_EXPECT(a == b);

+    ASL_TEST_EXPECT(a != c);

+    ASL_TEST_EXPECT(a != d);

+}

+

+static_assert(asl::hashable<bool>);

+

+ASL_TEST(bool)

+{

+    ASL_TEST_EXPECT(asl::hash_value(true) == asl::hash_value(true));

+    ASL_TEST_EXPECT(asl::hash_value(false) == asl::hash_value(false));

+    ASL_TEST_EXPECT(asl::hash_value(true) != asl::hash_value(false));

+}

+

+static_assert(asl::hashable<asl::string_view>);

+static_assert(asl::hashable<asl::string<>>);

+

+ASL_TEST(strings)

+{

+    ASL_TEST_EXPECT(asl::hash_value("hello"_sv) == asl::hash_value("hello"_sv));

+    ASL_TEST_EXPECT(asl::hash_value("hello"_sv) != asl::hash_value("hello "_sv));

+    ASL_TEST_EXPECT(asl::hash_value("hello"_sv) != asl::hash_value("HELLO"_sv));

+    

+    ASL_TEST_EXPECT(asl::hash_value(asl::string("hello"_sv)) == asl::hash_value(asl::string("hello"_sv)));

+    ASL_TEST_EXPECT(asl::hash_value(asl::string("hello"_sv)) != asl::hash_value(asl::string("hello "_sv)));

+    ASL_TEST_EXPECT(asl::hash_value(asl::string("hello"_sv)) != asl::hash_value(asl::string("HELLO"_sv)));

+

+    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

+// @Todo option (optimize uniquely_represented + has_niche)

+// @Todo status, status_or

+// @Todo box