BLI: improve exception safety of VectorSet

For more information see rB2aff45146f1464ba8899368ad004522cb6a1a98c.

1 files changed, 69 insertions, 45 deletions

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_)) {