improve hash api and hash test

2 files changed, 83 insertions, 31 deletions

diff --git a/test/app.cpp b/test/app.cpp
index 35a65743..6ace3ca5 100644
--- a/test/app.cpp
+++ b/test/app.cpp
@@ -65,7 +65,6 @@ int App::exec()
         FM_TEST(test_bptr),
         FM_TEST(test_iptr),
         FM_TEST(test_entity),
-        FM_TEST(test_hash),
         // normal
         FM_TEST(test_bitmask),
         FM_TEST(test_json),
@@ -75,6 +74,7 @@ int App::exec()
         FM_TEST(test_raycast),
         FM_TEST(test_wall_atlas),
         FM_TEST(test_wall_atlas2),
+        FM_TEST(test_hash),
         FM_TEST(test_region),
         // the rest are slow
         FM_TEST(test_rtree),
diff --git a/test/hash.cpp b/test/hash.cpp
index 16ae3173..a06d16a6 100644
--- a/test/hash.cpp
+++ b/test/hash.cpp
@@ -1,9 +1,12 @@
 #include "app.hpp"
 #include "compat/int-hash.hpp"
 #include "compat/array-size.hpp"
+#include "src/global-coords.hpp"
+#include "src/world.hpp"
 #include <cr/StringView.h>
 #include <bitset>
 #include <memory>
+#include <mg/Functions.h>
 
 namespace floormat {
 
@@ -16,49 +19,67 @@ void test_simple()
 
     size_t hashes[size] = {};
     for (auto i = 0uz; i < size; i++)
-        hashes[i] = hash_64(list[i].data(), list[i].size());
+        hashes[i] = hash_buf(list[i].data(), list[i].size());
 
     for (auto i = 0uz; i < size; i++)
         for (auto j = i+1; j < size; j++)
         {
             if (hashes[i] == hashes[j])
-                fm_abort("hash collision between '%s' and '%s': 0x%p", list[i].data(), list[j].data(), (void*)hashes[i]);
+                fm_abort("hash collision between '%s' and '%s': 0x%p",
+                    list[i].data(), list[j].data(), (void*)hashes[i]);
         }
 }
 
-void test_collisions()
+template<int16_t CoordMax, int8_t ZMax, uint32_t MaxCollisions>
+[[nodiscard]] bool test_collisions(const char* name)
 {
-    constexpr int max = 8;
-    constexpr size_t size = (2*max+1)*(2*max+1)*4 * 10;
-    constexpr size_t max_collisions = size*2/100;
-    size_t iter = 0, num_collisions = 0;
-    auto bitset_ = std::make_unique<std::bitset<size>>(false);
+    constexpr size_t Iters = (CoordMax*2 + 1)*(CoordMax*2 + 1)*(1+ZMax);
+    constexpr size_t BucketCount = Math::max(world::initial_capacity, size_t(Math::ceil(Iters / world::max_load_factor)));
+    uint32_t num_collisions = 0, iters = 0;
+    auto bitset_ = std::make_unique<std::bitset<BucketCount>>(false);
     auto& bitset = *bitset_;
 
-    for (int j = -max; j <= max; j++)
-    {
-        for (int i = -max; i <= max; i++)
-        {
-            for (int k = -2; k <= 1; k++)
+    for (int16_t j = -CoordMax; j <= CoordMax; j++)
+        for (int16_t i = -CoordMax; i <= CoordMax; i++)
+            for (int8_t k = 0; k <= ZMax; k++)
             {
-                ++iter;
-                uint64_t value = 0;
-                value |= (uint64_t)(uint16_t)(int16_t)i << 0;
-                value |= (uint64_t)(uint16_t)(int16_t)j << 16;
-                value |= (uint64_t)(uint16_t)(int16_t)k << 32;
-                auto x = (size_t)hash_int(value);
-                //Debug {} << "bitset:" << i << j << k << "=" << x % size << "/" << x;
-                x %= size;
-#if 1
-                if (bitset.test(x) && ++num_collisions >= max_collisions)
-                    fm_abort("test/bitset: %zu collisions at iter %zu id %zu (%d;%d:%d)", num_collisions, iter, x, i, j, k);
+                auto p = global_coords{i, j, k};
+                auto h = hash_buf(&p, sizeof p);
+                h %= BucketCount;
+                auto ref = bitset[h];
+                if (ref) [[unlikely]]
+                    ++num_collisions;
+                else
+                    ref = true;
+                (void)ref;
+                iters++;
+            }
+
+    fm_assert_equal(Iters, iters);
+
+//#define FM_TEST_DEBUG_PRINT
+
+    if (num_collisions > MaxCollisions)
+    {
+        DBG_nospace << Debug::color(Debug::Color::Magenta)
+                    << "fail" << Debug::resetColor << ": test/hash(\"" << name << "\")"
+                    << " collisions " << num_collisions << " > " << MaxCollisions
+                    << " (iters:" << iters << " buckets:" << BucketCount << ")";
+#ifdef FM_TEST_DEBUG_PRINT
+        return false;
 #else
-                if ((void)max_collisions, bitset.test(x))
-                        fm_warn("test/bitset: %zu collisions at iter %zu id %zu (%d;%d:%d)", ++num_collisions, iter, x, i, j, k);
+        fm_abort("test/hash: too many collisions");
 #endif
-                bitset.set(x);
-            }
-        }
+    }
+    else
+    {
+#ifdef FM_TEST_DEBUG_PRINT
+        DBG_nospace << Debug::color(Debug::Color::Cyan) << "pass" << Debug::resetColor
+                    << ": test/hash(\"" << name << "\") collisions "
+                    << num_collisions << " <= " << MaxCollisions
+                    << " (iters:" << iters << " buckets:" << BucketCount << ")";
+#endif
+        return true;
     }
 }
 
@@ -67,7 +88,38 @@ void test_collisions()
 void Test::test_hash()
 {
     test_simple();
-    test_collisions();
+
+    bool success = true;
+
+#ifdef FM_TEST_DEBUG_PRINT
+    DBG_nospace << "";
+#endif
+
+    success &= test_collisions<  3, 0,   0 >("small1");
+    success &= test_collisions<  6, 0,   4 >("mid2");
+    success &= test_collisions<  7, 0,   5 >("mid2");
+    success &= test_collisions<  8, 0,  13 >("mid2");
+    success &= test_collisions<  9, 0,  19 >("mid2");
+    success &= test_collisions< 10, 0,  26 >("large1");
+    success &= test_collisions< 12, 0,  46 >("large2");
+    success &= test_collisions< 14, 0,  83 >("large3");
+    success &= test_collisions< 15, 0, 109 >("large4");
+    success &= test_collisions< 16, 0, 127 >("large5");
+    success &= test_collisions<  3, 1,    2 >("zsmall2");
+    success &= test_collisions<  4, 1,    6 >("zsmall3");
+    success &= test_collisions<  2, 3,    1 >("zmid1");
+    success &= test_collisions<  6, 1,   17 >("zmid3");
+    success &= test_collisions<  6, 2,   37 >("zmid4");
+    success &= test_collisions<  7, 1,   27 >("zmid5");
+    success &= test_collisions< 10, 1,  107 >("zlarge2");
+    success &= test_collisions< 10, 4,  271 >("zlarge3");
+    success &= test_collisions< 16, 8, 1114 >("zlarge4");
+
+    if (!success)
+    {
+        DBG_nospace << "";
+        fm_abort("test/hash: too many collisions");
+    }
 }
 
 } // namespace floormat