[Bf-blender-cvs] [d2911124f42] master: BLI: improve exception safety of VectorSet
Jacques Lucke
noreply at git.blender.org
Mon Sep 7 20:04:07 CEST 2020
Commit: d2911124f42fd58d42b1b734c852980d5dbde401
Author: Jacques Lucke
Date: Mon Sep 7 19:36:24 2020 +0200
Branches: master
https://developer.blender.org/rBd2911124f42fd58d42b1b734c852980d5dbde401
BLI: improve exception safety of VectorSet
For more information see rB2aff45146f1464ba8899368ad004522cb6a1a98c.
===================================================================
M source/blender/blenlib/BLI_array.hh
M source/blender/blenlib/BLI_vector_set.hh
M source/blender/blenlib/BLI_vector_set_slots.hh
M source/blender/blenlib/tests/BLI_vector_set_test.cc
===================================================================
diff --git a/source/blender/blenlib/BLI_array.hh b/source/blender/blenlib/BLI_array.hh
index dddf4f64ff5..8a7dcb7ffaa 100644
--- a/source/blender/blenlib/BLI_array.hh
+++ b/source/blender/blenlib/BLI_array.hh
@@ -353,6 +353,10 @@ class Array {
{
return allocator_;
}
+ const Allocator &allocator() const
+ {
+ return allocator_;
+ }
/**
* Get the value of the InlineBufferCapacity template argument. This is the number of elements
diff --git a/source/blender/blenlib/BLI_vector_set.hh b/source/blender/blenlib/BLI_vector_set.hh
index 9d7c61f9e3b..c9773dc599d 100644
--- a/source/blender/blenlib/BLI_vector_set.hh
+++ b/source/blender/blenlib/BLI_vector_set.hh
@@ -143,7 +143,7 @@ class VectorSet {
* no keys are removed. The first set->size() elements in this array are initialized. The
* capacity of the array is usable_slots_.
*/
- Key *keys_;
+ Key *keys_ = nullptr;
/** Iterate over a slot index sequence for a given hash. */
#define VECTOR_SET_SLOT_PROBING_BEGIN(HASH, R_SLOT) \
@@ -157,22 +157,31 @@ class VectorSet {
* necessary to avoid a high cost when no elements are added at all. An optimized grow operation
* is performed on the first insertion.
*/
- VectorSet()
+ VectorSet(Allocator allocator = {}) noexcept
: removed_slots_(0),
occupied_and_removed_slots_(0),
usable_slots_(0),
slot_mask_(0),
- slots_(1),
+ slots_(1, allocator),
keys_(nullptr)
{
}
+ VectorSet(NoExceptConstructor, Allocator allocator = {}) : VectorSet(allocator)
+ {
+ }
+
+ VectorSet(Span<Key> keys, Allocator allocator = {}) : VectorSet(NoExceptConstructor(), allocator)
+ {
+ this->add_multiple(keys);
+ }
+
/**
* Construct a vector set that contains the given keys. Duplicates will be removed automatically.
*/
- VectorSet(const std::initializer_list<Key> &keys) : VectorSet()
+ VectorSet(const std::initializer_list<Key> &keys, Allocator allocator = {})
+ : VectorSet(Span(keys), allocator)
{
- this->add_multiple(keys);
}
~VectorSet()
@@ -183,15 +192,23 @@ class VectorSet {
}
}
- VectorSet(const VectorSet &other)
- : removed_slots_(other.removed_slots_),
- occupied_and_removed_slots_(other.occupied_and_removed_slots_),
- usable_slots_(other.usable_slots_),
- slot_mask_(other.slot_mask_),
- slots_(other.slots_)
+ VectorSet(const VectorSet &other) : slots_(other.slots_)
{
- keys_ = this->allocate_keys_array(usable_slots_);
- uninitialized_copy_n(other.keys_, other.size(), keys_);
+ keys_ = this->allocate_keys_array(other.usable_slots_);
+ try {
+ uninitialized_copy_n(other.keys_, other.size(), keys_);
+ }
+ catch (...) {
+ this->deallocate_keys_array(keys_);
+ throw;
+ }
+
+ removed_slots_ = other.removed_slots_;
+ occupied_and_removed_slots_ = other.occupied_and_removed_slots_;
+ usable_slots_ = other.usable_slots_;
+ slot_mask_ = other.slot_mask_;
+ hash_ = other.hash_;
+ is_equal_ = other.is_equal_;
}
VectorSet(VectorSet &&other) noexcept
@@ -212,26 +229,12 @@ class VectorSet {
VectorSet &operator=(const VectorSet &other)
{
- if (this == &other) {
- return *this;
- }
-
- this->~VectorSet();
- new (this) VectorSet(other);
-
- return *this;
+ return copy_assign_container(*this, other);
}
VectorSet &operator=(VectorSet &&other)
{
- if (this == &other) {
- return *this;
- }
-
- this->~VectorSet();
- new (this) VectorSet(std::move(other));
-
- return *this;
+ return move_assign_container(*this, std::move(other));
}
/**
@@ -490,32 +493,48 @@ class VectorSet {
/* Optimize the case when the set was empty beforehand. We can avoid some copies here. */
if (this->size() == 0) {
- slots_.~Array();
- new (&slots_) SlotArray(total_slots);
+ try {
+ slots_.reinitialize(total_slots);
+ keys_ = this->allocate_keys_array(usable_slots);
+ }
+ catch (...) {
+ this->noexcept_reset();
+ throw;
+ }
removed_slots_ = 0;
occupied_and_removed_slots_ = 0;
usable_slots_ = usable_slots;
slot_mask_ = new_slot_mask;
- keys_ = this->allocate_keys_array(usable_slots);
return;
}
SlotArray new_slots(total_slots);
- for (Slot &slot : slots_) {
- if (slot.is_occupied()) {
- this->add_after_grow_and_destruct_old(slot, new_slots, new_slot_mask);
+ try {
+ for (Slot &slot : slots_) {
+ if (slot.is_occupied()) {
+ this->add_after_grow(slot, new_slots, new_slot_mask);
+ slot.remove();
+ }
}
+ slots_ = std::move(new_slots);
+ }
+ catch (...) {
+ this->noexcept_reset();
+ throw;
}
Key *new_keys = this->allocate_keys_array(usable_slots);
- uninitialized_relocate_n(keys_, this->size(), new_keys);
+ try {
+ uninitialized_relocate_n(keys_, this->size(), new_keys);
+ }
+ catch (...) {
+ this->deallocate_keys_array(new_keys);
+ this->noexcept_reset();
+ throw;
+ }
this->deallocate_keys_array(keys_);
- /* All occupied slots have been destructed already and empty/removed slots are assumed to be
- * trivially destructible. */
- slots_.clear_without_destruct();
- slots_ = std::move(new_slots);
keys_ = new_keys;
occupied_and_removed_slots_ -= removed_slots_;
usable_slots_ = usable_slots;
@@ -523,9 +542,7 @@ class VectorSet {
slot_mask_ = new_slot_mask;
}
- void add_after_grow_and_destruct_old(Slot &old_slot,
- SlotArray &new_slots,
- const uint64_t new_slot_mask)
+ void add_after_grow(Slot &old_slot, SlotArray &new_slots, const uint64_t new_slot_mask)
{
const Key &key = keys_[old_slot.index()];
const uint64_t hash = old_slot.get_hash(key, Hash());
@@ -533,13 +550,20 @@ class VectorSet {
SLOT_PROBING_BEGIN (ProbingStrategy, hash, new_slot_mask, slot_index) {
Slot &slot = new_slots[slot_index];
if (slot.is_empty()) {
- slot.relocate_occupied_here(old_slot, hash);
+ slot.occupy(old_slot.index(), hash);
return;
}
}
SLOT_PROBING_END();
}
+ void noexcept_reset() noexcept
+ {
+ Allocator allocator = slots_.allocator();
+ this->~VectorSet();
+ new (this) VectorSet(NoExceptConstructor(), allocator);
+ }
+
template<typename ForwardKey>
bool contains__impl(const ForwardKey &key, const uint64_t hash) const
{
@@ -580,8 +604,8 @@ class VectorSet {
if (slot.is_empty()) {
int64_t index = this->size();
new (keys_ + index) Key(std::forward<ForwardKey>(key));
- occupied_and_removed_slots_++;
slot.occupy(index, hash);
+ occupied_and_removed_slots_++;
return true;
}
if (slot.contains(key, is_equal_, hash, keys_)) {
diff --git a/source/blender/blenlib/BLI_vector_set_slots.hh b/source/blender/blenlib/BLI_vector_set_slots.hh
index 0e75c4690a4..b79341ed744 100644
--- a/source/blender/blenlib/BLI_vector_set_slots.hh
+++ b/source/blender/blenlib/BLI_vector_set_slots.hh
@@ -96,18 +96,6 @@ template<typename Key> class SimpleVectorSetSlot {
return false;
}
- /**
- * Move the other slot into this slot and destruct it. We do destruction here, because this way
- * we can avoid a comparison with the state, since we know the slot is occupied. For this
- * specific slot implementation, this does not make a difference.
- */
- void relocate_occupied_here(SimpleVectorSetSlot &other, uint64_t UNUSED(hash))
- {
- BLI_assert(!this->is_occupied());
- BLI_assert(other.is_occupied());
- state_ = other.state_;
- }
-
/**
* Change the state of this slot from empty/removed to occupied. The hash can be used by other
* slot implementations.
diff --git a/source/blender/blenlib/tests/BLI_vector_set_test.cc b/source/blender/blenlib/tests/BLI_vector_set_test.cc
index 8f3db8d8403..320cb15f450 100644
--- a/source/blender/blenlib/tests/BLI_vector_set_test.cc
+++ b/source/blender/blenlib/tests/BLI_vector_set_test.cc
@@ -1,5 +1,6 @@
/* Apache License, Version 2.0 */
+#include "BLI_exception_safety_test_utils.hh"
#include "BLI_strict_flags.h"
#include "BLI_vector_set.hh"
#include "testing/testing.h"
@@ -161,4 +162,74 @@ TEST(vector_set, Remove)
EXPECT_FALSE(set.contains(5));
}
+TEST(vector_set, SpanConstructorExceptions)
+{
+ std::array<ExceptionThrower, 5> array = {1, 2, 3, 4, 5};
+ array[3].throw_during_copy = true;
+ Span<ExceptionThrower> span = array;
+
+ EXPECT_ANY_THROW({ VectorSet<ExceptionThrower> set(span); });
+}
+
+TEST(vector_set, CopyConstructorExceptions)
+{
+ VectorSet<ExceptionThrower> set = {1, 2, 3, 4, 5};
+ set[3].throw_during_copy = true;
+
+ EXPECT_ANY_THROW({ VectorSet<ExceptionThrower> set_copy(set); });
+}
+
+TEST(vector_set, MoveConstructorExceptions)
+{
+ VectorSet<ExceptionThrower> set = {1, 2, 3, 4, 5};
+ set[3].throw_during_copy = true;
+ set[3].throw_during_move = true;
+ /* Currently never throws on move, because values are separately allocated. */
+ VectorSet<ExceptionThrower> set_moved(std::move(set));
+ EXPECT_EQ(set.size(), 0); /* NOLINT: bugprone-use-after-move */
+ set.add_multiple({4, 5, 6, 7, 8});
+ EXPECT_EQ(set.size(), 5);
+}
+
+TEST(vector_set, AddNewExceptions)
+{
+ VectorSet<ExceptionThrower> set;
+ ExceptionThrower value;
+ value.throw_during_copy = true;
+ EXPECT_ANY_THROW({ set.add_new(value); });
+ EXPECT_EQ(set.size(), 0);
+ EXPECT_ANY_THROW({ set.add_new(value); });
+ EXPECT_EQ(set.size(), 0);
+}
+
+TEST(vector_set, AddExceptions)
+{
+ VectorSet<ExceptionThrower> set;
+ ExceptionThrower value;
+ value.throw_during_copy = true;
+ EXPECT_ANY_THROW({ set.add(value); });
+ EXPECT_EQ(set.size(), 0);
+ EXPECT_ANY_THROW({ set.add(value); });
+ EXPECT_EQ(set.size(), 0);
+}
+
+TEST(vector_set, ReserveExceptions)
+{
+ VectorSet<ExceptionThrower> set;
+ set.add_multiple({1, 2, 3, 4, 5});
+ set[2].throw_during_move = true;
+ EXPECT_ANY_THROW({ set.reserve(100); });
+}
+
+TEST(vector_set, PopExceptions
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list