diff options
author | Hans Goudey <h.goudey@me.com> | 2021-10-19 06:15:52 +0300 |
---|---|---|
committer | Hans Goudey <h.goudey@me.com> | 2021-10-19 06:15:52 +0300 |
commit | a76bb1a27782317449c04c0ab4916d66c46b6803 (patch) | |
tree | 63cea49df980078f7d05efaef2a5473738b6a1ee /source | |
parent | da949c357405ad01b00e83177335f55d113a8619 (diff) |
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
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/blenlib/BLI_set.hh | 22 | ||||
-rw-r--r-- | source/blender/blenlib/tests/BLI_set_test.cc | 26 |
2 files changed, 48 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_set.hh b/source/blender/blenlib/BLI_set.hh index a8ccf957f6c..2e0dfea70e9 100644 --- a/source/blender/blenlib/BLI_set.hh +++ b/source/blender/blenlib/BLI_set.hh @@ -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 @@ -485,6 +493,20 @@ class Set { } /** + * 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. */ void print_stats(StringRef name = "") const diff --git a/source/blender/blenlib/tests/BLI_set_test.cc b/source/blender/blenlib/tests/BLI_set_test.cc index 3a4733a218f..28eb4df2ca6 100644 --- a/source/blender/blenlib/tests/BLI_set_test.cc +++ b/source/blender/blenlib/tests/BLI_set_test.cc @@ -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. */ |