BLI: support looking up a key stored in Map or VectorSet
Sometimes it is useful to find the key that compares equal to a known key. Typically that happens when the key itself has additional data attached that is not part of its hash. Note that the returned key reference/pointer is const, because the caller must not change the key in a way that changes its hash or how it compares to other keys.
This commit is contained in:
parent
522868001c
commit
d288eeb79a
|
@ -604,6 +604,37 @@ class Map {
|
|||
return this->lookup_or_add_cb_as(std::forward<ForwardKey>(key), []() { return Value(); });
|
||||
}
|
||||
|
||||
/**
|
||||
* Returns the key that is stored in the set that compares equal to the given key. This invokes
|
||||
* undefined behavior when the key is not in the map.
|
||||
*/
|
||||
const Key &lookup_key(const Key &key) const
|
||||
{
|
||||
return this->lookup_key_as(key);
|
||||
}
|
||||
template<typename ForwardKey> const Key &lookup_key_as(const ForwardKey &key) const
|
||||
{
|
||||
const Slot &slot = this->lookup_slot(key, hash_(key));
|
||||
return *slot.key();
|
||||
}
|
||||
|
||||
/**
|
||||
* Returns a pointer to the key that is stored in the map that compares equal to the given key.
|
||||
* If the key is not in the map, null is returned.
|
||||
*/
|
||||
const Key *lookup_key_ptr(const Key &key) const
|
||||
{
|
||||
return this->lookup_key_ptr_as(key);
|
||||
}
|
||||
template<typename ForwardKey> const Key *lookup_key_ptr_as(const ForwardKey &key) const
|
||||
{
|
||||
const Slot *slot = this->lookup_slot_ptr(key, hash_(key));
|
||||
if (slot == nullptr) {
|
||||
return nullptr;
|
||||
}
|
||||
return slot->key();
|
||||
}
|
||||
|
||||
/**
|
||||
* Calls the provided callback for every key-value-pair in the map. The callback is expected
|
||||
* to take a `const Key &` as first and a `const Value &` as second parameter.
|
||||
|
|
|
@ -414,6 +414,38 @@ class VectorSet {
|
|||
return this->index_of_or_add__impl(std::forward<ForwardKey>(key), hash_(key));
|
||||
}
|
||||
|
||||
/**
|
||||
* Returns the key that is stored in the vector set that compares equal to the given key. This
|
||||
* invokes undefined behavior when the key is not in the set.
|
||||
*/
|
||||
const Key &lookup_key(const Key &key) const
|
||||
{
|
||||
return this->lookup_key_as(key);
|
||||
}
|
||||
template<typename ForwardKey> const Key &lookup_key_as(const ForwardKey &key) const
|
||||
{
|
||||
const Key *key_ptr = this->lookup_key_ptr_as(key);
|
||||
BLI_assert(key_ptr != nullptr);
|
||||
return *key_ptr;
|
||||
}
|
||||
|
||||
/**
|
||||
* Returns a pointer to the key that is stored in the vector set that compares equal to the given
|
||||
* key. If the key is not in the set, null is returned.
|
||||
*/
|
||||
const Key *lookup_key_ptr(const Key &key) const
|
||||
{
|
||||
return this->lookup_key_ptr_as(key);
|
||||
}
|
||||
template<typename ForwardKey> const Key *lookup_key_ptr_as(const ForwardKey &key) const
|
||||
{
|
||||
const int64_t index = this->index_of_try__impl(key, hash_(key));
|
||||
if (index >= 0) {
|
||||
return keys_ + index;
|
||||
}
|
||||
return nullptr;
|
||||
}
|
||||
|
||||
/**
|
||||
* Get a pointer to the beginning of the array containing all keys.
|
||||
*/
|
||||
|
|
|
@ -640,6 +640,19 @@ TEST(map, RemoveDuringIteration)
|
|||
EXPECT_EQ(map.lookup(3), 3);
|
||||
}
|
||||
|
||||
TEST(map, LookupKey)
|
||||
{
|
||||
Map<std::string, int> map;
|
||||
map.add("a", 0);
|
||||
map.add("b", 1);
|
||||
map.add("c", 2);
|
||||
EXPECT_EQ(map.lookup_key("a"), "a");
|
||||
EXPECT_EQ(map.lookup_key_as("c"), "c");
|
||||
EXPECT_EQ(map.lookup_key_ptr_as("d"), nullptr);
|
||||
EXPECT_EQ(map.lookup_key_ptr_as("b")->size(), 1);
|
||||
EXPECT_EQ(map.lookup_key_ptr("a"), map.lookup_key_ptr_as("a"));
|
||||
}
|
||||
|
||||
/**
|
||||
* Set this to 1 to activate the benchmark. It is disabled by default, because it prints a lot.
|
||||
*/
|
||||
|
|
|
@ -258,4 +258,17 @@ TEST(vector_set, Clear)
|
|||
EXPECT_EQ(set.size(), 0);
|
||||
}
|
||||
|
||||
TEST(vector_set, LookupKey)
|
||||
{
|
||||
VectorSet<std::string> set;
|
||||
set.add("a");
|
||||
set.add("b");
|
||||
set.add("c");
|
||||
EXPECT_EQ(set.lookup_key("a"), "a");
|
||||
EXPECT_EQ(set.lookup_key_as("c"), "c");
|
||||
EXPECT_EQ(set.lookup_key_ptr_as("d"), nullptr);
|
||||
EXPECT_EQ(set.lookup_key_ptr_as("b")->size(), 1);
|
||||
EXPECT_EQ(set.lookup_key_ptr("a"), set.lookup_key_ptr_as("a"));
|
||||
}
|
||||
|
||||
} // namespace blender::tests
|
||||
|
|
Loading…
Reference in New Issue