blender
/
blender
136
404
Fork 586
Code Issues 6.2k Pull Requests 755 Projects 19 Wiki Activity

BLI: support looking up a key from a set or adding it when not existant

This commit is contained in:
Jacques Lucke 2020-10-12 15:10:01 +02:00
parent 662c0ac970
commit db8a856a74
2 changed files with 47 additions and 0 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

33
source/blender/blenlib/BLI_set.hh
View File

@ -350,6 +350,23 @@ class Set {
return this->lookup_key_ptr__impl(key, hash_(key));
}
/**
* Returns the key in the set that compares equal to the given key. If it does not exist, the key
* is newly added.
*/
const Key &lookup_key_or_add(const Key &key)
{
return this->lookup_key_or_add_as(key);
}
const Key &lookup_key_or_add(Key &&key)
{
return this->lookup_key_or_add_as(std::move(key));
}
template<typename ForwardKey> const Key &lookup_key_or_add_as(ForwardKey &&key)
{
return this->lookup_key_or_add__impl(std::forward<ForwardKey>(key), hash_(key));
}
/**
* Deletes the key from the set. Returns true when the key did exist beforehand, otherwise false.
*
@ -734,6 +751,22 @@ class Set {
SET_SLOT_PROBING_END();
}
template<typename ForwardKey>
const Key &lookup_key_or_add__impl(ForwardKey &&key, const uint64_t hash)
{
SET_SLOT_PROBING_BEGIN (hash, slot) {
if (slot.contains(key, is_equal_, hash)) {
return *slot.key();
}
if (slot.is_empty()) {
slot.occupy(std::forward<ForwardKey>(key), hash);
occupied_and_removed_slots_++;
return *slot.key();
}
}
SET_SLOT_PROBING_END();
}
template<typename ForwardKey>
int64_t count_collisions__impl(const ForwardKey &key, const uint64_t hash) const
{

14
source/blender/blenlib/tests/BLI_set_test.cc
View File

@ -453,6 +453,20 @@ TEST(set, LookupKeyPtr)
EXPECT_EQ(set.lookup_key_ptr({3, 50}), nullptr);
}
TEST(set, LookupKeyOrAdd)
{
Set<MyKeyType> set;
set.add({1, 10});
set.add({2, 20});
EXPECT_EQ(set.size(), 2);
EXPECT_EQ(set.lookup_key_or_add({2, 40}).attached_data, 20);
EXPECT_EQ(set.size(), 2);
EXPECT_EQ(set.lookup_key_or_add({3, 40}).attached_data, 40);
EXPECT_EQ(set.size(), 3);
EXPECT_EQ(set.lookup_key_or_add({3, 60}).attached_data, 40);
EXPECT_EQ(set.size(), 3);
}
TEST(set, StringViewKeys)
{
Set<std::string_view> set;