[Bf-blender-cvs] [1d2adb08f8e] functions: Fix ArrayLookup for the case when all slots are used or dummies

[Jacques Lucke]

Commit: 1d2adb08f8ed6583626d197407632e5823ad524f
Author: Jacques Lucke
Date:   Sat Jul 6 14:43:31 2019 +0200
Branches: functions
https://developer.blender.org/rB1d2adb08f8ed6583626d197407632e5823ad524f

Fix ArrayLookup for the case when all slots are used or dummies

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

M	source/blender/blenlib/BLI_array_lookup.hpp

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

diff --git a/source/blender/blenlib/BLI_array_lookup.hpp b/source/blender/blenlib/BLI_array_lookup.hpp
index 618441b9fc5..b88a6951508 100644
--- a/source/blender/blenlib/BLI_array_lookup.hpp
+++ b/source/blender/blenlib/BLI_array_lookup.hpp
@@ -91,30 +91,48 @@ class ArrayLookup {
     }
   }
 
+  uint add__no_deleted(Item *array, const Key &key, uint desired_new_index)
+  {
+    BLI_assert(m_dummy_amount == 0);
+    ITER_SLOTS (key, slot, state) {
+      if (state == SLOT_EMPTY) {
+        this->insert_if_fits_or_grow(array, key, desired_new_index, slot);
+        m_length++;
+        return desired_new_index;
+      }
+      else if (GetKey(array[state]) == key) {
+        return state;
+      }
+    }
+  }
+
   uint add(Item *array, const Key &key, uint desired_new_index)
   {
-    int dummy_slot = -1;
+    if (m_dummy_amount == 0) {
+      return this->add__no_deleted(array, key, desired_new_index);
+    }
+
+    int first_dummy_slot = -1;
     ITER_SLOTS (key, slot, state) {
       if (state == SLOT_EMPTY) {
-        if (dummy_slot == -1) {
-          bool map_changed = this->ensure_can_add(array);
-          if (map_changed) {
-            this->insert_index_for_key(key, desired_new_index);
-          }
-          else {
-            m_map[slot] = desired_new_index;
-          }
+        if (first_dummy_slot == -1) {
+          this->insert_if_fits_or_grow(array, key, desired_new_index, slot);
         }
         else {
-          m_map[slot] = desired_new_index;
+          m_map[first_dummy_slot] = desired_new_index;
           m_dummy_amount--;
         }
         m_length++;
         return desired_new_index;
       }
       else if (state == SLOT_DUMMY) {
-        if (dummy_slot == -1) {
-          dummy_slot = slot;
+        if (first_dummy_slot == -1) {
+          first_dummy_slot = slot;
+        }
+        /* Fallback in case there are no empty slots left. */
+        if (m_map.size() == m_length + m_dummy_amount) {
+          this->ensure_can_add(array);
+          this->add(array, key, desired_new_index);
         }
       }
       else if (GetKey(array[state]) == key) {
@@ -237,6 +255,20 @@ class ArrayLookup {
     }
   }
 
+  inline void insert_if_fits_or_grow(Item *array,
+                                     const Key &key,
+                                     uint index,
+                                     uint slot_in_current_map)
+  {
+    bool map_changed = this->ensure_can_add(array);
+    if (map_changed) {
+      this->insert_index_for_key(key, index);
+    }
+    else {
+      m_map[slot_in_current_map] = index;
+    }
+  }
+
   inline float load_factor() const
   {
     return m_length / (float)m_map.size();