[Bf-blender-cvs] [8e18a998450] master: BLI: improve exception safety of Set and Map
Jacques Lucke
noreply at git.blender.org
Mon Aug 24 17:31:09 CEST 2020
Commit: 8e18a9984505514a229d66b38fff31d930367968
Author: Jacques Lucke
Date: Mon Aug 24 17:24:13 2020 +0200
Branches: master
https://developer.blender.org/rB8e18a9984505514a229d66b38fff31d930367968
BLI: improve exception safety of Set and Map
For more information see rB2aff45146f1464ba8899368ad004522cb6a1a98c.
===================================================================
M source/blender/blenlib/BLI_array.hh
M source/blender/blenlib/BLI_map.hh
M source/blender/blenlib/BLI_map_slots.hh
M source/blender/blenlib/BLI_set.hh
M source/blender/blenlib/BLI_set_slots.hh
M source/blender/blenlib/tests/BLI_array_test.cc
M source/blender/blenlib/tests/BLI_exception_safety_test_utils.hh
M source/blender/blenlib/tests/BLI_map_test.cc
M source/blender/blenlib/tests/BLI_set_test.cc
===================================================================
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 ot
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list