More work on hashing

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<typename H>

+    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<const byte> bytes)

+    template<typename T>

+    static HashState combine_contiguous(HashState h, span<const T> s)

     {

-        auto hashed = city_hash::CityHash128WithSeed(

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

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

-            h.state);

-        return HashState{hashed};

+        if constexpr (uniquely_represented<T>)

+        {

+            auto bytes = as_bytes(s);

+            auto hashed = city_hash::CityHash128WithSeed(

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

+                static_cast<size_t>(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<hashable_generic<HashState> Arg, hashable_generic<HashState>... 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<T, HashState>;
 template<typename H, uniquely_represented T>

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

 {

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

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

 }

 

 template<typename H>

 constexpr H AslHashValue(H h, bool value)

 {

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

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

 }

 

+template<typename H, typename T>

+constexpr void AslHashValue(H h, T*); // Don't hash pointers

+

 template<hashable T>

 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<uint64_t> : true_type  {};
 

 template<typename T> concept is_integer = _is_integer_helper<un_cv_t<T>>::value;

 

+template<typename T> concept is_enum = __is_enum(T);

+

 template<typename T> struct is_uniquely_represented : false_type {};

 template<is_integer T> struct is_uniquely_represented<T> : true_type {};

+template<is_enum T> struct is_uniquely_represented<T> : true_type {};

 template<> struct is_uniquely_represented<uint128_t> : true_type {};

 template<> struct is_uniquely_represented<byte> : 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<T>{ data() + size() - sub_size, sub_size };
     }
+
+    template<typename H>
+    friend H AslHashValue(H h, const span& s)
+    {
+        return H::combine_contiguous(ASL_MOVE(h), span<const T>{s.data(), s.size()});
+    }
 };
 
 template<is_object T, isize_t kSize>
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<typename H>
     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<int*>);

+static_assert(!asl::hashable<int[]>);

+static_assert(!asl::hashable<int[9]>);

 

 static_assert(asl::hashable<uint8_t>);

 static_assert(asl::hashable<uint16_t>);

@@ -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<asl::span<const int>>);

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

+

+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<int>(ints1)) == asl::hash_value(asl::span<int>(ints2)));

+    ASL_TEST_EXPECT(asl::hash_value(asl::span<int>(ints1)) != asl::hash_value(asl::span<int>(ints3)));

+    ASL_TEST_EXPECT(asl::hash_value(asl::span<int>(ints1)) != asl::hash_value(asl::span<int>(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<asl::string_view>(strs1)) == asl::hash_value(asl::span<asl::string_view>(strs2)));

+    ASL_TEST_EXPECT(asl::hash_value(asl::span<asl::string_view>(strs1)) != asl::hash_value(asl::span<asl::string_view>(strs3)));

+    ASL_TEST_EXPECT(asl::hash_value(asl::span<asl::string_view>(strs1)) != asl::hash_value(asl::span<asl::string_view>(strs4)));

+}

+

+static_assert(asl::hashable<asl::buffer<int>>);

+

+ASL_TEST(buffer)

+{

+    asl::buffer<int> ints1;

+    ints1.push(1);

+    ints1.push(2);

+    ints1.push(3);

+    

+    asl::buffer<int> ints2;

+    ints2.push(1);

+    ints2.push(2);

+    ints2.push(3);

+    

+    asl::buffer<int> ints3;

+    ints3.push(1);

+    ints3.push(2);

+    

+    asl::buffer<int> 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<asl::string_view> strs1;

+    strs1.push("Hello");

+    strs1.push("World");

+    

+    asl::buffer<asl::string_view> strs2;

+    strs2.push("Hello");

+    strs2.push("World");

+    

+    asl::buffer<asl::string_view> strs3;

+    strs3.push("Hello");

+    strs3.push("world");

+    

+    asl::buffer<asl::string_view> 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<Enum1>);

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

+

 // @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<C>);
 static_assert(asl::uniquely_represented<int>);

 static_assert(asl::uniquely_represented<uint128_t>);

 static_assert(!asl::uniquely_represented<bool>);

+

+enum Enum1 {};

+enum class Enum2 {};

+

+static_assert(asl::uniquely_represented<Enum1>);

+static_assert(asl::uniquely_represented<Enum2>);

+

+static_assert(!asl::is_enum<int>);

+static_assert(asl::is_enum<Enum1>);

+static_assert(asl::is_enum<Enum2>);

+