diff options
author | Jacques Lucke <jacques@blender.org> | 2020-08-24 18:24:13 +0300 |
---|---|---|
committer | Jacques Lucke <jacques@blender.org> | 2020-08-24 18:24:13 +0300 |
commit | 8e18a9984505514a229d66b38fff31d930367968 (patch) | |
tree | 97bb3e6f766e997df712bf081e05e027648e2c28 | |
parent | 530350935472970dccc211b0e728e2db4fd1d8ef (diff) |
BLI: improve exception safety of Set and Map
For more information see rB2aff45146f1464ba8899368ad004522cb6a1a98c.
-rw-r--r-- | source/blender/blenlib/BLI_array.hh | 43 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_map.hh | 123 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_map_slots.hh | 95 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_set.hh | 114 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_set_slots.hh | 47 | ||||
-rw-r--r-- | source/blender/blenlib/tests/BLI_array_test.cc | 14 | ||||
-rw-r--r-- | source/blender/blenlib/tests/BLI_exception_safety_test_utils.hh | 44 | ||||
-rw-r--r-- | source/blender/blenlib/tests/BLI_map_test.cc | 67 | ||||
-rw-r--r-- | source/blender/blenlib/tests/BLI_set_test.cc | 50 |
9 files changed, 405 insertions, 192 deletions
diff --git a/source/blender/blenlib/BLI_array.hh b/source/blender/blenlib/BLI_array.hh index d6b7ab03203..dddf4f64ff5 100644 --- a/source/blender/blenlib/BLI_array.hh +++ b/source/blender/blenlib/BLI_array.hh @@ -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); + } } }; diff --git a/source/blender/blenlib/BLI_map.hh b/source/blender/blenlib/BLI_map.hh index 229bbfad0e4..e901b2de4bf 100644 --- a/source/blender/blenlib/BLI_map.hh +++ b/source/blender/blenlib/BLI_map.hh @@ -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(); diff --git a/source/blender/blenlib/BLI_map_slots.hh b/source/blender/blenlib/BLI_map_slots.hh index 25fb92d61a3..c0cb3091a8e 100644 --- a/source/blender/blenlib/BLI_map_slots.hh +++ b/source/blender/blenlib/BLI_map_slots.hh @@ -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()); } } @@ -161,21 +179,6 @@ template<typename Key, typename Value> class SimpleMapSlot { } /** - * 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_); } }; diff --git a/source/blender/blenlib/BLI_set.hh b/source/blender/blenlib/BLI_set.hh index 477a03cf623..9684f372db7 100644 --- a/source/blender/blenlib/BLI_set.hh +++ b/source/blender/blenlib/BLI_set.hh @@ -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() = default; + 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> &list) : Set() + Set(const std::initializer_list<Key> &values) : Set(Span<Key>(values)) { - this->add_multiple(list); } + ~Set() = default; + 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; } } diff --git a/source/blender/blenlib/BLI_set_slots.hh b/source/blender/blenlib/BLI_set_slots.hh index ee5da17fcaf..a4d01dfdb68 100644 --- a/source/blender/blenlib/BLI_set_slots.hh +++ b/source/blender/blenlib/BLI_set_slots.hh @@ -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) { @@ -139,19 +139,6 @@ template<typename Key> class SimpleSetSlot { } /** - * 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); } diff --git a/source/blender/blenlib/tests/BLI_array_test.cc b/source/blender/blenlib/tests/BLI_array_test.cc index 3d45a9f5277..7d967eca87e 100644 --- a/source/blender/blenlib/tests/BLI_array_test.cc +++ b/source/blender/blenlib/tests/BLI_array_test.cc @@ -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 diff --git a/source/blender/blenlib/tests/BLI_exception_safety_test_utils.hh b/source/blender/blenlib/tests/BLI_exception_safety_test_utils.hh index 5ad7674396b..91270767a25 100644 --- a/source/blender/blenlib/tests/BLI_exception_safety_test_utils.hh +++ b/source/blender/blenlib/tests/BLI_exception_safety_test_utils.hh @@ -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 diff --git a/source/blender/blenlib/tests/BLI_map_test.cc b/source/blender/blenlib/tests/BLI_map_test.cc index fe7b0f01279..7b4a484e736 100644 --- a/source/blender/blenlib/tests/BLI_map_test.cc +++ b/source/blender/blenlib/tests/BLI_map_test.cc @@ -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. */ diff --git a/source/blender/blenlib/tests/BLI_set_test.cc b/source/blender/blenlib/tests/BLI_set_test.cc index df3f7ab544c..3ea9a59b3db 100644 --- a/source/blender/blenlib/tests/BLI_set_test.cc +++ b/source/blender/blenlib/tests/BLI_set_test.cc @@ -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. */ |