BLI: Support removing keys from a set during iteration
This adds the ability to mark slots as removed while iterating through a mutable set. Differential Revision: https://developer.blender.org/D12867
This commit is contained in:
parent
da949c3574
commit
a76bb1a277
|
@ -423,6 +423,8 @@ class Set {
|
|||
int64_t total_slots_;
|
||||
int64_t current_slot_;
|
||||
|
||||
friend Set;
|
||||
|
||||
public:
|
||||
Iterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
|
||||
: slots_(slots), total_slots_(total_slots), current_slot_(current_slot)
|
||||
|
@ -467,6 +469,12 @@ class Set {
|
|||
{
|
||||
return !(a != b);
|
||||
}
|
||||
|
||||
protected:
|
||||
const Slot ¤t_slot() const
|
||||
{
|
||||
return slots_[current_slot_];
|
||||
}
|
||||
};
|
||||
|
||||
Iterator begin() const
|
||||
|
@ -484,6 +492,20 @@ class Set {
|
|||
return Iterator(slots_.data(), slots_.size(), slots_.size());
|
||||
}
|
||||
|
||||
/**
|
||||
* Remove the key that the iterator is currently pointing at. It is valid to call this method
|
||||
* while iterating over the set. However, after this method has been called, the removed element
|
||||
* must not be accessed anymore.
|
||||
*/
|
||||
void remove(const Iterator &iterator)
|
||||
{
|
||||
/* The const cast is valid because this method itself is not const. */
|
||||
Slot &slot = const_cast<Slot &>(iterator.current_slot());
|
||||
BLI_assert(slot.is_occupied());
|
||||
slot.remove();
|
||||
removed_slots_++;
|
||||
}
|
||||
|
||||
/**
|
||||
* Print common statistics like size and collision count. This is useful for debugging purposes.
|
||||
*/
|
||||
|
|
|
@ -544,6 +544,32 @@ TEST(set, GenericAlgorithms)
|
|||
EXPECT_EQ(std::count(set.begin(), set.end(), 20), 1);
|
||||
}
|
||||
|
||||
TEST(set, RemoveDuringIteration)
|
||||
{
|
||||
Set<int> set;
|
||||
set.add(6);
|
||||
set.add(5);
|
||||
set.add(2);
|
||||
set.add(3);
|
||||
|
||||
EXPECT_EQ(set.size(), 4);
|
||||
|
||||
using Iter = Set<int>::Iterator;
|
||||
Iter begin = set.begin();
|
||||
Iter end = set.end();
|
||||
for (Iter iter = begin; iter != end; ++iter) {
|
||||
int item = *iter;
|
||||
if (item == 2) {
|
||||
set.remove(iter);
|
||||
}
|
||||
}
|
||||
|
||||
EXPECT_EQ(set.size(), 3);
|
||||
EXPECT_TRUE(set.contains(5));
|
||||
EXPECT_TRUE(set.contains(6));
|
||||
EXPECT_TRUE(set.contains(3));
|
||||
}
|
||||
|
||||
/**
|
||||
* Set this to 1 to activate the benchmark. It is disabled by default, because it prints a lot.
|
||||
*/
|
||||
|
|
Loading…
Reference in New Issue