blender
/
blender
129
397
Fork 571
Code Issues 6.2k Pull Requests 754 Projects 19 Wiki Activity

BLI: improve VectorSet data structure 

This adds two new methods:
* `clear` just removes all keys from the vector set.
* `index_of_or_add` returns the index of a key and adds it if has not
  been added before.
This commit is contained in:
Jacques Lucke 2021-04-30 11:09:19 +02:00
parent 2b723abea0
commit 7041568ff9
2 changed files with 71 additions and 0 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

45
source/blender/blenlib/BLI_vector_set.hh
View File

@ -397,6 +397,23 @@ class VectorSet {
return this->index_of_try__impl(key, hash_(key));
}
/**
* Return the index of the key in the vector. If the key is not in the set, add it and return its
* index.
*/
int64_t index_of_or_add(const Key &key)
{
return this->index_of_or_add_as(key);
}
int64_t index_of_or_add(Key &&key)
{
return this->index_of_or_add_as(std::move(key));
}
template<typename ForwardKey> int64_t index_of_or_add_as(ForwardKey &&key)
{
return this->index_of_or_add__impl(std::forward<ForwardKey>(key), hash_(key));
}
/**
* Get a pointer to the beginning of the array containing all keys.
*/
@ -483,6 +500,14 @@ class VectorSet {
}
}
/**
* Remove all keys from the vector set.
*/
void clear()
{
this->noexcept_reset();
}
/**
* Get the number of collisions that the probing strategy has to go through to find the key or
* determine that it is not in the set.
@ -652,6 +677,26 @@ class VectorSet {
VECTOR_SET_SLOT_PROBING_END();
}
template<typename ForwardKey>
int64_t index_of_or_add__impl(ForwardKey &&key, const uint64_t hash)
{
this->ensure_can_add();
VECTOR_SET_SLOT_PROBING_BEGIN (hash, slot) {
if (slot.contains(key, is_equal_, hash, keys_)) {
return slot.index();
}
if (slot.is_empty()) {
const int64_t index = this->size();
new (keys_ + index) Key(std::forward<ForwardKey>(key));
slot.occupy(index, hash);
occupied_and_removed_slots_++;
return index;
}
}
VECTOR_SET_SLOT_PROBING_END();
}
Key pop__impl()
{
BLI_assert(this->size() > 0);

26
source/blender/blenlib/tests/BLI_vector_set_test.cc
View File

@ -232,4 +232,30 @@ TEST(vector_set, PopExceptions)
EXPECT_EQ(set.size(), 4);
}
TEST(vector_set, IndexOfOrAdd)
{
VectorSet<int> set;
EXPECT_EQ(set.index_of_or_add(3), 0);
EXPECT_EQ(set.index_of_or_add(3), 0);
EXPECT_EQ(set.index_of_or_add(2), 1);
EXPECT_EQ(set.index_of_or_add(0), 2);
EXPECT_EQ(set.index_of_or_add(2), 1);
EXPECT_EQ(set.index_of_or_add(3), 0);
EXPECT_EQ(set.index_of_or_add(5), 3);
EXPECT_EQ(set.index_of_or_add(8), 4);
EXPECT_EQ(set.index_of_or_add(5), 3);
}
TEST(vector_set, Clear)
{
VectorSet<int> set = {4, 6, 2, 4};
EXPECT_EQ(set.size(), 3);
set.clear();
EXPECT_EQ(set.size(), 0);
set.add_multiple({4, 1, 6, 8, 3, 6, 9, 3});
EXPECT_EQ(set.size(), 6);
set.clear();
EXPECT_EQ(set.size(), 0);
}
} // namespace blender::tests