[Bf-blender-cvs] [b0015fc7cdd] functions: multimap fix

[Jacques Lucke]

Commit: b0015fc7cdd9582c10145f3095cfb5e2a83bd81c
Author: Jacques Lucke
Date:   Fri Jul 12 12:00:39 2019 +0200
Branches: functions
https://developer.blender.org/rBb0015fc7cdd9582c10145f3095cfb5e2a83bd81c

multimap fix

===================================================================

M	source/blender/blenlib/BLI_small_multimap.hpp
M	source/blender/blenlib/BLI_small_vector.hpp

===================================================================

diff --git a/source/blender/blenlib/BLI_small_multimap.hpp b/source/blender/blenlib/BLI_small_multimap.hpp
index b075f71a790..0ee0ae29968 100644
--- a/source/blender/blenlib/BLI_small_multimap.hpp
+++ b/source/blender/blenlib/BLI_small_multimap.hpp
@@ -39,33 +39,41 @@ template<typename K, typename V, uint N = 4> class SmallMultiMap {
   bool add(const K &key, const V &value)
   {
     BLI_STATIC_ASSERT(std::is_trivially_destructible<V>::value, "");
-    bool newly_inserted = m_map.add_or_modify(key,
-                                              /* Insert new key with value. */
-                                              [this, &key, &value]() -> Entry {
-                                                uint offset = m_elements.size();
-                                                m_elements.append(value);
-                                                return {offset, 1, 1};
-                                              },
-                                              /* Append new value for existing key. */
-                                              [this, &value](Entry &entry) {
-                                                if (entry.length < entry.capacity) {
-                                                  m_elements[entry.offset + entry.length] = value;
-                                                  entry.length += 1;
-                                                }
-                                                else {
-                                                  uint new_offset = m_elements.size();
-
-                                                  /* Copy the existing elements to the end. */
-                                                  m_elements.extend(entry.get_slice(m_elements));
-                                                  /* Insert the new value and reserve the capacity
-                                                   * for this entry. */
-                                                  m_elements.append_n_times(value, entry.length);
-
-                                                  entry.offset = new_offset;
-                                                  entry.length += 1;
-                                                  entry.capacity *= 2;
-                                                }
-                                              });
+    bool newly_inserted = m_map.add_or_modify(
+        key,
+        /* Insert new key with value. */
+        [this, &key, &value]() -> Entry {
+          uint offset = m_elements.size();
+          m_elements.append(value);
+          return {offset, 1, 1};
+        },
+        /* Append new value for existing key. */
+        [this, &value](Entry &entry) {
+          if (entry.length < entry.capacity) {
+            m_elements[entry.offset + entry.length] = value;
+            entry.length += 1;
+          }
+          else {
+            uint new_offset = m_elements.size();
+            uint new_capacity = entry.capacity * 2;
+
+            m_elements.reserve(m_elements.size() + new_capacity);
+
+            /* Copy the existing elements to the end. */
+            ArrayRef<V> old_values = entry.get_slice(m_elements);
+            m_elements.extend_unchecked(old_values);
+
+            /* Insert the new value. */
+            m_elements.append_unchecked(value);
+
+            /* Reserve the remaining capacity for this entry. */
+            m_elements.increase_size_unchecked(entry.length - 1);
+
+            entry.offset = new_offset;
+            entry.length += 1;
+            entry.capacity = new_capacity;
+          }
+        });
     return newly_inserted;
   }
 
diff --git a/source/blender/blenlib/BLI_small_vector.hpp b/source/blender/blenlib/BLI_small_vector.hpp
index ffa275973b5..9e344a2617e 100644
--- a/source/blender/blenlib/BLI_small_vector.hpp
+++ b/source/blender/blenlib/BLI_small_vector.hpp
@@ -231,13 +231,25 @@ template<typename T, uint N = 4> class SmallVector {
   void append(const T &value)
   {
     this->ensure_space_for_one();
-    std::uninitialized_copy_n(&value, 1, this->end());
-    m_size++;
+    this->append_unchecked(value);
   }
 
   void append(T &&value)
   {
     this->ensure_space_for_one();
+    this->append_unchecked(std::move(value));
+  }
+
+  void append_unchecked(const T &value)
+  {
+    BLI_assert(m_size < m_capacity);
+    std::uninitialized_copy_n(&value, 1, this->end());
+    m_size++;
+  }
+
+  void append_unchecked(T &&value)
+  {
+    BLI_assert(m_size < m_capacity);
     std::uninitialized_copy_n(std::make_move_iterator(&value), 1, this->end());
     m_size++;
   }
@@ -253,6 +265,12 @@ template<typename T, uint N = 4> class SmallVector {
     m_size += n;
   }
 
+  void increase_size_unchecked(uint n)
+  {
+    BLI_assert(m_size + n <= m_capacity);
+    m_size += n;
+  }
+
   /**
    * Copy the elements of another vector to the end of this vector.
    */
@@ -269,6 +287,17 @@ template<typename T, uint N = 4> class SmallVector {
   void extend(const T *start, uint amount)
   {
     this->reserve(m_size + amount);
+    this->extend_unchecked(start, amount);
+  }
+
+  void extend_unchecked(ArrayRef<T> array)
+  {
+    this->extend_unchecked(array.begin(), array.size());
+  }
+
+  void extend_unchecked(const T *start, uint amount)
+  {
+    BLI_assert(m_size + amount <= m_capacity);
     std::uninitialized_copy_n(start, amount, this->end());
     m_size += amount;
   }