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.
This commit is contained in:
parent
72b4f91914
commit
cc48610d2c
|
@ -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
|
||||
|
|
|
@ -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.
|
||||
*/
|
||||
|
|
|
@ -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();
|
||||
|
|
|
@ -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.
|
||||
*/
|
||||
|
|
Loading…
Reference in New Issue