[Bf-blender-cvs] [cc48610d2c5] master: BLI: improve support for using vectors as hash table keys

[Jacques Lucke]

Commit: cc48610d2c55a001bcd3af57ad11f7951602936d
Author: Jacques Lucke
Date:   Thu Dec 29 14:59:48 2022 +0100
Branches: master
https://developer.blender.org/rBcc48610d2c55a001bcd3af57ad11f7951602936d

BLI: improve support for using vectors as hash table keys

To support this, I had to add comparison and hashing functions for
vectors or sequences more generally.

===================================================================

M	source/blender/blenlib/BLI_hash_tables.hh
M	source/blender/blenlib/BLI_span.hh
M	source/blender/blenlib/BLI_vector.hh
M	source/blender/blenlib/tests/BLI_map_test.cc

===================================================================

diff --git a/source/blender/blenlib/BLI_hash_tables.hh b/source/blender/blenlib/BLI_hash_tables.hh
index fff2411f94c..6e453820ec9 100644
--- a/source/blender/blenlib/BLI_hash_tables.hh
+++ b/source/blender/blenlib/BLI_hash_tables.hh
@@ -353,4 +353,22 @@ template<typename T> struct DefaultEquality<std::unique_ptr<T>> : public Pointer
 template<typename T> struct DefaultEquality<std::shared_ptr<T>> : public PointerComparison {
 };
 
+struct SequenceComparison {
+  template<typename T1, typename T2> bool operator()(const T1 &a, const T2 &b) const
+  {
+    const auto a_begin = a.begin();
+    const auto a_end = a.end();
+    const auto b_begin = b.begin();
+    const auto b_end = b.end();
+    if (a_end - a_begin != b_end - b_begin) {
+      return false;
+    }
+    return std::equal(a_begin, a_end, b_begin);
+  }
+};
+
+template<typename T, int64_t InlineBufferCapacity, typename Allocator>
+struct DefaultEquality<Vector<T, InlineBufferCapacity, Allocator>> : public SequenceComparison {
+};
+
 }  // namespace blender
diff --git a/source/blender/blenlib/BLI_span.hh b/source/blender/blenlib/BLI_span.hh
index 84a5c87d423..a276bbd8f68 100644
--- a/source/blender/blenlib/BLI_span.hh
+++ b/source/blender/blenlib/BLI_span.hh
@@ -66,6 +66,8 @@
 
 namespace blender {
 
+template<typename T> uint64_t get_default_hash(const T &v);
+
 /**
  * References an array of type T that is owned by someone else. The data in the array cannot be
  * modified.
@@ -418,6 +420,15 @@ template<typename T> class Span {
     return IndexRange(size_);
   }
 
+  constexpr uint64_t hash() const
+  {
+    uint64_t hash = 0;
+    for (const T &value : *this) {
+      hash = hash * 33 ^ get_default_hash(value);
+    }
+    return hash;
+  }
+
   /**
    * Returns a new Span to the same underlying memory buffer. No conversions are done.
    */
diff --git a/source/blender/blenlib/BLI_vector.hh b/source/blender/blenlib/BLI_vector.hh
index 8860bb05127..09486b32480 100644
--- a/source/blender/blenlib/BLI_vector.hh
+++ b/source/blender/blenlib/BLI_vector.hh
@@ -157,6 +157,12 @@ class Vector {
     this->increase_size_by_unchecked(size);
   }
 
+  template<typename U, BLI_ENABLE_IF((std::is_convertible_v<U, T>))>
+  explicit Vector(MutableSpan<U> values, Allocator allocator = {})
+      : Vector(values.as_span(), allocator)
+  {
+  }
+
   /**
    * Create a vector that contains copies of the values in the initialized list.
    *
@@ -937,6 +943,16 @@ class Vector {
     return IndexRange(this->size());
   }
 
+  uint64_t hash() const
+  {
+    return this->as_span().hash();
+  }
+
+  static uint64_t hash_as(const Span<T> values)
+  {
+    return values.hash();
+  }
+
   friend bool operator==(const Vector &a, const Vector &b)
   {
     return a.as_span() == b.as_span();
diff --git a/source/blender/blenlib/tests/BLI_map_test.cc b/source/blender/blenlib/tests/BLI_map_test.cc
index 69ae82d6f05..2662d547ee9 100644
--- a/source/blender/blenlib/tests/BLI_map_test.cc
+++ b/source/blender/blenlib/tests/BLI_map_test.cc
@@ -671,6 +671,24 @@ TEST(map, LookupKey)
   EXPECT_EQ(map.lookup_key_ptr("a"), map.lookup_key_ptr_as("a"));
 }
 
+TEST(map, VectorKey)
+{
+  Map<Vector<int>, int> map;
+  map.add({1, 2, 3}, 100);
+  map.add({3, 2, 1}, 200);
+
+  EXPECT_EQ(map.size(), 2);
+  EXPECT_EQ(map.lookup({1, 2, 3}), 100);
+  EXPECT_EQ(map.lookup({3, 2, 1}), 200);
+  EXPECT_FALSE(map.contains({1, 2}));
+
+  std::array<int, 3> array = {1, 2, 3};
+  EXPECT_EQ(map.lookup_as(array), 100);
+
+  map.remove_as(Vector<int>({1, 2, 3}).as_mutable_span());
+  EXPECT_EQ(map.size(), 1);
+}
+
 /**
  * Set this to 1 to activate the benchmark. It is disabled by default, because it prints a lot.
  */