blender
/
blender
128
396
Fork 568
Code Issues 6.2k Pull Requests 750 Projects 19 Wiki Activity

BLI: improve exception safety of Set and Map 

For more information see rB2aff45146f1464ba8899368ad004522cb6a1a98c.
This commit is contained in:
Jacques Lucke 2020-08-24 17:24:13 +02:00
parent 5303509354
commit 8e18a99845
9 changed files with 410 additions and 197 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

43
source/blender/blenlib/BLI_array.hh
View File

@ -168,7 +168,7 @@ class Array {
Array(Array &&other) noexcept(std::is_nothrow_move_constructible_v<T>)
: Array(NoExceptConstructor(), other.allocator_)
{
if (other.uses_inline_buffer()) {
if (other.data_ == other.inline_buffer_) {
uninitialized_relocate_n(other.data_, other.size_, data_);
}
else {
@ -183,9 +183,7 @@ class Array {
~Array()
{
destruct_n(data_, size_);
if (!this->uses_inline_buffer()) {
allocator_.deallocate(static_cast<void *>(data_));
}
this->deallocate_if_not_inline(data_);
}
Array &operator=(const Array &other)
@ -365,6 +363,37 @@ class Array {
return InlineBufferCapacity;
}
/**
* Destruct values and create a new array of the given size. The values in the new array are
* default constructed.
*/
void reinitialize(const int64_t new_size)
{
BLI_assert(new_size >= 0);
int64_t old_size = size_;
destruct_n(data_, size_);
size_ = 0;
if (new_size <= old_size) {
default_construct_n(data_, new_size);
}
else {
T *new_data = this->get_buffer_for_size(new_size);
try {
default_construct_n(new_data, new_size);
}
catch (...) {
this->deallocate_if_not_inline(new_data);
throw;
}
this->deallocate_if_not_inline(data_);
data_ = new_data;
}
size_ = new_size;
}
private:
T *get_buffer_for_size(int64_t size)
{
@ -382,9 +411,11 @@ class Array {
allocator_.allocate(static_cast<size_t>(size) * sizeof(T), alignof(T), AT));
}
bool uses_inline_buffer() const
void deallocate_if_not_inline(T *ptr)
{
return data_ == inline_buffer_;
if (ptr != inline_buffer_) {
allocator_.deallocate(ptr);
}
}
};

123
source/blender/blenlib/BLI_map.hh
View File

@ -171,14 +171,18 @@ class Map {
* This is necessary to avoid a high cost when no elements are added at all. An optimized grow
* operation is performed on the first insertion.
*/
Map()
Map(Allocator allocator = {}) noexcept
: removed_slots_(0),
occupied_and_removed_slots_(0),
usable_slots_(0),
slot_mask_(0),
hash_(),
is_equal_(),
slots_(1)
slots_(1, allocator)
{
}
Map(NoExceptConstructor, Allocator allocator = {}) noexcept : Map(allocator)
{
}
@ -186,41 +190,38 @@ class Map {
Map(const Map &other) = default;
Map(Map &&other) noexcept
: 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_(std::move(other.hash_)),
is_equal_(std::move(other.is_equal_)),
slots_(std::move(other.slots_))
Map(Map &&other) noexcept(std::is_nothrow_move_constructible_v<SlotArray>)
: Map(NoExceptConstructor(), other.slots_.allocator())
{
other.~Map();
new (&other) Map();
if constexpr (std::is_nothrow_move_constructible_v<SlotArray>) {
slots_ = std::move(other.slots_);
}
else {
try {
slots_ = std::move(other.slots_);
}
catch (...) {
other.noexcept_reset();
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_ = std::move(other.hash_);
is_equal_ = std::move(other.is_equal_);
other.noexcept_reset();
}
Map &operator=(const Map &other)
{
if (this == &other) {
return *this;
}
this->~Map();
new (this) Map(other);
return *this;
return copy_assign_container(*this, other);
}
Map &operator=(Map &&other)
{
if (this == &other) {
return *this;
}
this->~Map();
new (this) Map(std::move(other));
return *this;
return move_assign_container(*this, std::move(other));
}
/**
@ -843,8 +844,7 @@ class Map {
*/
void clear()
{
this->~Map();
new (this) Map();
this->noexcept_reset();
}
/**
@ -869,8 +869,13 @@ class Map {
* Optimize the case when the map 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);
}
catch (...) {
this->noexcept_reset();
throw;
}
removed_slots_ = 0;
occupied_and_removed_slots_ = 0;
usable_slots_ = usable_slots;
@ -880,37 +885,46 @@ class Map {
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;
}
/* 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);
occupied_and_removed_slots_ -= removed_slots_;
usable_slots_ = usable_slots;
removed_slots_ = 0;
slot_mask_ = new_slot_mask;
}
void add_after_grow_and_destruct_old(Slot &old_slot,
SlotArray &new_slots,
uint64_t new_slot_mask)
void add_after_grow(Slot &old_slot, SlotArray &new_slots, uint64_t new_slot_mask)
{
uint64_t hash = old_slot.get_hash(Hash());
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(std::move(*old_slot.key()), std::move(*old_slot.value()), hash);
return;
}
}
SLOT_PROBING_END();
}
void noexcept_reset() noexcept
{
Allocator allocator = slots_.allocator();
this->~Map();
new (this) Map(NoExceptConstructor(), allocator);
}
template<typename ForwardKey> bool contains__impl(const ForwardKey &key, uint64_t hash) const
{
MAP_SLOT_PROBING_BEGIN (hash, slot) {
@ -930,11 +944,11 @@ class Map {
BLI_assert(!this->contains_as(key));
this->ensure_can_add();
occupied_and_removed_slots_++;
MAP_SLOT_PROBING_BEGIN (hash, slot) {
if (slot.is_empty()) {
slot.occupy(std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash);
occupied_and_removed_slots_++;
return;
}
}
@ -978,11 +992,10 @@ class Map {
{
BLI_assert(this->contains_as(key));
removed_slots_++;
MAP_SLOT_PROBING_BEGIN (hash, slot) {
if (slot.contains(key, is_equal_, hash)) {
slot.remove();
removed_slots_++;
return;
}
}
@ -993,12 +1006,11 @@ class Map {
{
BLI_assert(this->contains_as(key));
removed_slots_++;
MAP_SLOT_PROBING_BEGIN (hash, slot) {
if (slot.contains(key, is_equal_, hash)) {
Value value = std::move(*slot.value());
slot.remove();
removed_slots_++;
return value;
}
}
@ -1054,10 +1066,19 @@ class Map {
MAP_SLOT_PROBING_BEGIN (hash, slot) {
if (slot.is_empty()) {
occupied_and_removed_slots_++;
slot.occupy_without_value(std::forward<ForwardKey>(key), hash);
Value *value_ptr = slot.value();
return create_value(value_ptr);
if constexpr (std::is_void_v<CreateReturnT>) {
create_value(value_ptr);
slot.occupy_no_value(std::forward<ForwardKey>(key), hash);
occupied_and_removed_slots_++;
return;
}
else {
auto return_value = create_value(value_ptr);
slot.occupy_no_value(std::forward<ForwardKey>(key), hash);
occupied_and_removed_slots_++;
return return_value;
}
}
if (slot.contains(key, is_equal_, hash)) {
Value *value_ptr = slot.value();

95
source/blender/blenlib/BLI_map_slots.hh
View File

@ -38,6 +38,19 @@
namespace blender {
template<typename Src1, typename Src2, typename Dst1, typename Dst2>
void initialize_pointer_pair(Src1 &&src1, Src2 &&src2, Dst1 *dst1, Dst2 *dst2)
{
new ((void *)dst1) Dst1(std::forward<Src1>(src1));
try {
new ((void *)dst2) Dst2(std::forward<Src2>(src2));
}
catch (...) {
dst1->~Dst1();
throw;
}
}
/**
* The simplest possible map slot. It stores the slot state and the optional key and value
* instances in separate variables. Depending on the alignment requirement of the key and value,
@ -83,8 +96,10 @@ template<typename Key, typename Value> class SimpleMapSlot {
{
state_ = other.state_;
if (other.state_ == Occupied) {
new (&key_buffer_) Key(*other.key_buffer_);
new (&value_buffer_) Value(*other.value_buffer_);
initialize_pointer_pair(other.key_buffer_.ref(),
other.value_buffer_.ref(),
key_buffer_.ptr(),
value_buffer_.ptr());
}
}
@ -93,12 +108,15 @@ template<typename Key, typename Value> class SimpleMapSlot {
* from the other have to moved as well. The other slot stays in the state it was in before. Its
* optionally stored key and value remain in a moved-from state.
*/
SimpleMapSlot(SimpleMapSlot &&other) noexcept
SimpleMapSlot(SimpleMapSlot &&other) noexcept(
std::is_nothrow_move_constructible_v<Key> &&std::is_nothrow_move_constructible_v<Value>)
{
state_ = other.state_;
if (other.state_ == Occupied) {
new (&key_buffer_) Key(std::move(*other.key_buffer_));
new (&value_buffer_) Value(std::move(*other.value_buffer_));
initialize_pointer_pair(std::move(other.key_buffer_.ref()),
std::move(other.value_buffer_.ref()),
key_buffer_.ptr(),
value_buffer_.ptr());
}
}
@ -160,21 +178,6 @@ template<typename Key, typename Value> class SimpleMapSlot {
return hash(*key_buffer_);
}
/**
* 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.
*/
void relocate_occupied_here(SimpleMapSlot &other, uint64_t UNUSED(hash))
{
BLI_assert(!this->is_occupied());
BLI_assert(other.is_occupied());
state_ = Occupied;
new (&key_buffer_) Key(std::move(*other.key_buffer_));
new (&value_buffer_) Value(std::move(*other.value_buffer_));
other.key_buffer_.ref().~Key();
other.value_buffer_.ref().~Value();
}
/**
* Returns true, when this slot is occupied and contains a key that compares equal to the given
* key. The hash can be used by other slot implementations to determine inequality faster.
@ -196,19 +199,27 @@ template<typename Key, typename Value> class SimpleMapSlot {
void occupy(ForwardKey &&key, ForwardValue &&value, uint64_t hash)
{
BLI_assert(!this->is_occupied());
this->occupy_without_value(std::forward<ForwardKey>(key), hash);
new (&value_buffer_) Value(std::forward<ForwardValue>(value));
this->occupy_no_value(std::forward<ForwardKey>(key), hash);
state_ = Occupied;
}
/**
* Change the state of this slot from empty/removed to occupied, but leave the value
* uninitialized. The caller is responsible to construct the value afterwards.
* Change the state of this slot from empty/removed to occupied. The value is assumed to be
* constructed already.
*/
template<typename ForwardKey> void occupy_without_value(ForwardKey &&key, uint64_t UNUSED(hash))
template<typename ForwardKey> void occupy_no_value(ForwardKey &&key, uint64_t UNUSED(hash))
{
BLI_assert(!this->is_occupied());
try {
new (&key_buffer_) Key(std::forward<ForwardKey>(key));
}
catch (...) {
/* The value is assumed to be constructed already, so it has to be destructed as well. */
value_buffer_.ref().~Value();
throw;
}
state_ = Occupied;
new (&key_buffer_) Key(std::forward<ForwardKey>(key));
}
/**
@ -218,17 +229,17 @@ template<typename Key, typename Value> class SimpleMapSlot {
void remove()
{
BLI_assert(this->is_occupied());
state_ = Removed;
key_buffer_.ref().~Key();
value_buffer_.ref().~Value();
state_ = Removed;
}
};
/**
* An IntrusiveMapSlot uses two special values of the key to indicate whether the slot is empty or
* removed. This saves some memory in all cases and is more efficient in many cases. The KeyInfo
* type indicates which specific values are used. An example for a KeyInfo implementation is
* PointerKeyInfo.
* An IntrusiveMapSlot uses two special values of the key to indicate whether the slot is empty
* or removed. This saves some memory in all cases and is more efficient in many cases. The
* KeyInfo type indicates which specific values are used. An example for a KeyInfo
* implementation is PointerKeyInfo.
*
* The special key values are expected to be trivially destructible.
*/
@ -297,16 +308,6 @@ template<typename Key, typename Value, typename KeyInfo> class IntrusiveMapSlot
return hash(key_);
}
void relocate_occupied_here(IntrusiveMapSlot &other, uint64_t UNUSED(hash))
{
BLI_assert(!this->is_occupied());
BLI_assert(other.is_occupied());
key_ = std::move(other.key_);
new (&value_buffer_) Value(std::move(*other.value_buffer_));
other.key_.~Key();
other.value_buffer_.ref().~Value();
}
template<typename ForwardKey, typename IsEqual>
bool contains(const ForwardKey &key, const IsEqual &is_equal, uint64_t UNUSED(hash)) const
{
@ -319,22 +320,28 @@ template<typename Key, typename Value, typename KeyInfo> class IntrusiveMapSlot
{
BLI_assert(!this->is_occupied());
BLI_assert(KeyInfo::is_not_empty_or_removed(key));
this->occupy_without_value(std::forward<ForwardKey>(key), hash);
new (&value_buffer_) Value(std::forward<ForwardValue>(value));
this->occupy_no_value(std::forward<ForwardKey>(key), hash);
}
template<typename ForwardKey> void occupy_without_value(ForwardKey &&key, uint64_t UNUSED(hash))
template<typename ForwardKey> void occupy_no_value(ForwardKey &&key, uint64_t UNUSED(hash))
{
BLI_assert(!this->is_occupied());
BLI_assert(KeyInfo::is_not_empty_or_removed(key));
key_ = std::forward<ForwardKey>(key);
try {
key_ = std::forward<ForwardKey>(key);
}
catch (...) {
value_buffer_.ref().~Value();
throw;
}
}
void remove()
{
BLI_assert(this->is_occupied());
KeyInfo::remove(key_);
value_buffer_.ref().~Value();
KeyInfo::remove(key_);
}
};

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

@ -170,62 +170,68 @@ class Set {
* is. This is necessary to avoid a high cost when no elements are added at all. An optimized
* grow operation is performed on the first insertion.
*/
Set()
Set(Allocator allocator = {}) noexcept
: removed_slots_(0),
occupied_and_removed_slots_(0),
usable_slots_(0),
slot_mask_(0),
slots_(1)
slots_(1, allocator)
{
}
Set(NoExceptConstructor, Allocator allocator = {}) noexcept : Set(allocator)
{
}
Set(Span<Key> values, Allocator allocator = {}) : Set(NoExceptConstructor(), allocator)
{
this->add_multiple(values);
}
/**
* Construct a set that contains the given keys. Duplicates will be removed automatically.
*/
Set(const std::initializer_list<Key> &values) : Set(Span<Key>(values))
{
}
~Set() = default;
/**
* Construct a set that contains the given keys. Duplicates will be removed automatically.
*/
Set(const std::initializer_list<Key> &list) : Set()
{
this->add_multiple(list);
}
Set(const Set &other) = default;
Set(Set &&other) noexcept
: 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_(std::move(other.hash_)),
is_equal_(std::move(other.is_equal_)),
slots_(std::move(other.slots_))
Set(Set &&other) noexcept(std::is_nothrow_move_constructible_v<SlotArray>)
: Set(NoExceptConstructor(), other.slots_.allocator())
{
other.~Set();
new (&other) Set();
if constexpr (std::is_nothrow_move_constructible_v<SlotArray>) {
slots_ = std::move(other.slots_);
}
else {
try {
slots_ = std::move(other.slots_);
}
catch (...) {
other.noexcept_reset();
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_ = std::move(other.hash_);
is_equal_ = std::move(other.is_equal_);
other.noexcept_reset();
}
Set &operator=(const Set &other)
{
if (this == &other) {
return *this;
}
this->~Set();
new (this) Set(other);
return *this;
return copy_assign_container(*this, other);
}
Set &operator=(Set &&other)
{
if (this == &other) {
return *this;
}
this->~Set();
new (this) Set(std::move(other));
return *this;
return move_assign_container(*this, std::move(other));
}
/**
@ -562,8 +568,13 @@ class Set {
* 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);
}
catch (...) {
this->noexcept_reset();
throw;
}
removed_slots_ = 0;
occupied_and_removed_slots_ = 0;
usable_slots_ = usable_slots;
@ -574,38 +585,51 @@ class Set {
/* The grown array that we insert the keys into. */
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;
}
/* 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);
occupied_and_removed_slots_ -= removed_slots_;
usable_slots_ = usable_slots;
removed_slots_ = 0;
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 uint64_t hash = old_slot.get_hash(Hash());
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(std::move(*old_slot.key()), hash);
return;
}
}
SLOT_PROBING_END();
}
/**
* In some cases when exceptions are thrown, it's best to just reset the entire container to make
* sure that invariants are maintained. This should happen very rarely in practice.
*/
void noexcept_reset() noexcept
{
Allocator allocator = slots_.allocator();
this->~Set();
new (this) Set(NoExceptConstructor(), allocator);
}
template<typename ForwardKey>
bool contains__impl(const ForwardKey &key, const uint64_t hash) const
{
@ -699,11 +723,11 @@ class Set {
void remove_contained__impl(const ForwardKey &key, const uint64_t hash)
{
BLI_assert(this->contains_as(key));
removed_slots_++;
SET_SLOT_PROBING_BEGIN (hash, slot) {
if (slot.contains(key, is_equal_, hash)) {
slot.remove();
removed_slots_++;
return;
}
}

47
source/blender/blenlib/BLI_set_slots.hh
View File

@ -88,7 +88,7 @@ template<typename Key> class SimpleSetSlot {
* other slot has to be moved as well. The other slot stays in the state it was in before. Its
* optionally stored key remains in a moved-from state.
*/
SimpleSetSlot(SimpleSetSlot &&other) noexcept
SimpleSetSlot(SimpleSetSlot &&other) noexcept(std::is_nothrow_move_constructible_v<Key>)
{
state_ = other.state_;
if (other.state_ == Occupied) {
@ -138,19 +138,6 @@ template<typename Key> class SimpleSetSlot {
return hash(*key_buffer_);
}
/**
* 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.
*/
void relocate_occupied_here(SimpleSetSlot &other, uint64_t UNUSED(hash))
{
BLI_assert(!this->is_occupied());
BLI_assert(other.is_occupied());
state_ = Occupied;
new (&key_buffer_) Key(std::move(*other.key_buffer_));
other.key_buffer_.ref().~Key();
}
/**
* Return true, when this slot is occupied and contains a key that compares equal to the given
* key. The hash is used by other slot implementations to determine inequality faster.
@ -171,8 +158,8 @@ template<typename Key> class SimpleSetSlot {
template<typename ForwardKey> void occupy(ForwardKey &&key, uint64_t UNUSED(hash))
{
BLI_assert(!this->is_occupied());
state_ = Occupied;
new (&key_buffer_) Key(std::forward<ForwardKey>(key));
state_ = Occupied;
}
/**
@ -181,8 +168,8 @@ template<typename Key> class SimpleSetSlot {
void remove()
{
BLI_assert(this->is_occupied());
state_ = Removed;
key_buffer_.ref().~Key();
state_ = Removed;
}
};
@ -224,7 +211,7 @@ template<typename Key> class HashedSetSlot {
}
}
HashedSetSlot(HashedSetSlot &&other) noexcept
HashedSetSlot(HashedSetSlot &&other) noexcept(std::is_nothrow_move_constructible_v<Key>)
{
state_ = other.state_;
if (other.state_ == Occupied) {
@ -259,16 +246,6 @@ template<typename Key> class HashedSetSlot {
return hash_;
}
void relocate_occupied_here(HashedSetSlot &other, const uint64_t hash)
{
BLI_assert(!this->is_occupied());
BLI_assert(other.is_occupied());
state_ = Occupied;
hash_ = hash;
new (&key_buffer_) Key(std::move(*other.key_buffer_));
key_buffer_.ref().~Key();
}
template<typename ForwardKey, typename IsEqual>
bool contains(const ForwardKey &key, const IsEqual &is_equal, const uint64_t hash) const
{
@ -284,16 +261,16 @@ template<typename Key> class HashedSetSlot {
template<typename ForwardKey> void occupy(ForwardKey &&key, const uint64_t hash)
{
BLI_assert(!this->is_occupied());
new (&key_buffer_) Key(std::forward<ForwardKey>(key));
state_ = Occupied;
hash_ = hash;
new (&key_buffer_) Key(std::forward<ForwardKey>(key));
}
void remove()
{
BLI_assert(this->is_occupied());
state_ = Removed;
key_buffer_.ref().~Key();
state_ = Removed;
}
};
@ -313,7 +290,8 @@ template<typename Key, typename KeyInfo> class IntrusiveSetSlot {
IntrusiveSetSlot() = default;
~IntrusiveSetSlot() = default;
IntrusiveSetSlot(const IntrusiveSetSlot &other) = default;
IntrusiveSetSlot(IntrusiveSetSlot &&other) noexcept = default;
IntrusiveSetSlot(IntrusiveSetSlot &&other) noexcept(std::is_nothrow_move_constructible_v<Key>) =
default;
Key *key()
{
@ -341,14 +319,6 @@ template<typename Key, typename KeyInfo> class IntrusiveSetSlot {
return hash(key_);
}
void relocate_occupied_here(IntrusiveSetSlot &other, const uint64_t UNUSED(hash))
{
BLI_assert(!this->is_occupied());
BLI_assert(other.is_occupied());
key_ = std::move(other.key_);
other.key_.~Key();
}
template<typename ForwardKey, typename IsEqual>
bool contains(const ForwardKey &key, const IsEqual &is_equal, const uint64_t UNUSED(hash)) const
{
@ -360,7 +330,6 @@ template<typename Key, typename KeyInfo> class IntrusiveSetSlot {
{
BLI_assert(!this->is_occupied());
BLI_assert(KeyInfo::is_not_empty_or_removed(key));
key_ = std::forward<ForwardKey>(key);
}

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

@ -236,4 +236,18 @@ TEST(array, Last)
EXPECT_EQ(const_cast<const Array<int> &>(array).last(), 1);
}
TEST(array, Reinitialize)
{
Array<std::string> array = {"hello", "world"};
EXPECT_EQ(array.size(), 2);
EXPECT_EQ(array[1], "world");
array.reinitialize(3);
EXPECT_EQ(array.size(), 3);
EXPECT_EQ(array[0], "");
EXPECT_EQ(array[1], "");
EXPECT_EQ(array[2], "");
array.reinitialize(0);
EXPECT_EQ(array.size(), 0);
}
} // namespace blender::tests

44
source/blender/blenlib/tests/BLI_exception_safety_test_utils.hh
View File

@ -1,3 +1,4 @@
#include "BLI_hash.hh"
#include "BLI_utildefines.h"
#include "MEM_guardedalloc.h"
#include "testing/testing.h"
@ -16,18 +17,21 @@ class ExceptionThrower {
void *my_memory_;
public:
bool throw_during_copy;
bool throw_during_move;
mutable bool throw_during_copy;
mutable bool throw_during_move;
/* Used for hashing and comparing. */
int value;
ExceptionThrower()
ExceptionThrower(int value = 0)
: state_(is_alive_state),
my_memory_(MEM_mallocN(1, AT)),
throw_during_copy(false),
throw_during_move(false)
throw_during_move(false),
value(value)
{
}
ExceptionThrower(const ExceptionThrower &other) : ExceptionThrower()
ExceptionThrower(const ExceptionThrower &other) : ExceptionThrower(other.value)
{
EXPECT_EQ(other.state_, is_alive_state);
if (other.throw_during_copy) {
@ -35,7 +39,7 @@ class ExceptionThrower {
}
}
ExceptionThrower(ExceptionThrower &&other) : ExceptionThrower()
ExceptionThrower(ExceptionThrower &&other) : ExceptionThrower(other.value)
{
EXPECT_EQ(other.state_, is_alive_state);
if (other.throw_during_move) {
@ -49,6 +53,7 @@ class ExceptionThrower {
if (throw_during_copy || other.throw_during_copy) {
throw std::runtime_error("throwing during copy, as requested");
}
value = other.value;
return *this;
}
@ -58,15 +63,40 @@ class ExceptionThrower {
if (throw_during_move || other.throw_during_move) {
throw std::runtime_error("throwing during move, as requested");
}
value = other.value;
return *this;
}
~ExceptionThrower()
{
EXPECT_EQ(state_, is_alive_state);
const char *message = "";
if (state_ != is_alive_state) {
if (state_ == is_destructed_state) {
message = "Trying to destruct an already destructed instance.";
}
else {
message = "Trying to destruct an uninitialized instance.";
}
}
EXPECT_EQ(state_, is_alive_state) << message;
state_ = is_destructed_state;
MEM_freeN(my_memory_);
}
uint64_t hash() const
{
return static_cast<uint64_t>(value);
}
friend bool operator==(const ExceptionThrower &a, const ExceptionThrower &b)
{
return a.value == b.value;
}
friend bool operator!=(const ExceptionThrower &a, const ExceptionThrower &b)
{
return !(a == b);
}
};
} // namespace blender::tests

67
source/blender/blenlib/tests/BLI_map_test.cc
View File

@ -1,5 +1,6 @@
/* Apache License, Version 2.0 */
#include "BLI_exception_safety_test_utils.hh"
#include "BLI_map.hh"
#include "BLI_rand.h"
#include "BLI_set.hh"
@ -479,6 +480,72 @@ TEST(map, ForeachItem)
EXPECT_EQ(keys.first_index_of(1), values.first_index_of(8));
}
TEST(map, CopyConstructorExceptions)
{
using MapType = Map<ExceptionThrower, ExceptionThrower>;
MapType map;
map.add(2, 2);
map.add(4, 4);
map.lookup(2).throw_during_copy = true;
EXPECT_ANY_THROW({ MapType map_copy(map); });
}
TEST(map, MoveConstructorExceptions)
{
using MapType = Map<ExceptionThrower, ExceptionThrower>;
MapType map;
map.add(1, 1);
map.add(2, 2);
map.lookup(1).throw_during_move = true;
EXPECT_ANY_THROW({ MapType map_moved(std::move(map)); });
map.add(5, 5);
}
TEST(map, AddNewExceptions)
{
Map<ExceptionThrower, ExceptionThrower> map;
ExceptionThrower key1 = 1;
key1.throw_during_copy = true;
ExceptionThrower value1;
EXPECT_ANY_THROW({ map.add_new(key1, value1); });
EXPECT_EQ(map.size(), 0);
ExceptionThrower key2 = 2;
ExceptionThrower value2;
value2.throw_during_copy = true;
EXPECT_ANY_THROW({ map.add_new(key2, value2); });
}
TEST(map, ReserveExceptions)
{
Map<ExceptionThrower, ExceptionThrower> map;
map.add(3, 3);
map.add(5, 5);
map.add(2, 2);
map.lookup(2).throw_during_move = true;
EXPECT_ANY_THROW({ map.reserve(100); });
map.add(1, 1);
map.add(5, 5);
}
TEST(map, PopExceptions)
{
Map<ExceptionThrower, ExceptionThrower> map;
map.add(3, 3);
map.lookup(3).throw_during_move = true;
EXPECT_ANY_THROW({ map.pop(3); });
EXPECT_EQ(map.size(), 1);
map.add(1, 1);
EXPECT_EQ(map.size(), 2);
}
TEST(map, AddOrModifyExceptions)
{
Map<ExceptionThrower, ExceptionThrower> map;
auto create_fn = [](ExceptionThrower *UNUSED(v)) { throw std::runtime_error(""); };
auto modify_fn = [](ExceptionThrower *UNUSED(v)) {};
EXPECT_ANY_THROW({ map.add_or_modify(3, create_fn, modify_fn); });
}
/**
* Set this to 1 to activate the benchmark. It is disabled by default, because it prints a lot.
*/

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

@ -3,6 +3,7 @@
#include <set>
#include <unordered_set>
#include "BLI_exception_safety_test_utils.hh"
#include "BLI_ghash.h"
#include "BLI_rand.h"
#include "BLI_set.hh"
@ -462,6 +463,55 @@ TEST(set, StringViewKeys)
EXPECT_TRUE(set.contains("hello"));
}
TEST(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({ Set<ExceptionThrower> set(span); });
}
TEST(set, CopyConstructorExceptions)
{
Set<ExceptionThrower> set = {1, 2, 3, 4, 5};
set.lookup_key(3).throw_during_copy = true;
EXPECT_ANY_THROW({ Set<ExceptionThrower> set_copy(set); });
}
TEST(set, MoveConstructorExceptions)
{
using SetType = Set<ExceptionThrower, 4>;
SetType set = {1, 2, 3};
set.lookup_key(2).throw_during_move = true;
EXPECT_ANY_THROW({ SetType set_moved(std::move(set)); });
EXPECT_EQ(set.size(), 0);
set.add_multiple({3, 6, 7});
EXPECT_EQ(set.size(), 3);
}
TEST(set, AddNewExceptions)
{
Set<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(set, AddExceptions)
{
Set<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);
}
/**
* Set this to 1 to activate the benchmark. It is disabled by default, because it prints a lot.
*/