[Bf-blender-cvs] [5a1279fdce1] functions: faster adding to array lookup

Jacques Lucke noreply at git.blender.org
Mon Apr 8 16:15:25 CEST 2019


Commit: 5a1279fdce1a8d9c92d7614bc7d4f44865a139d8
Author: Jacques Lucke
Date:   Mon Apr 8 16:01:16 2019 +0200
Branches: functions
https://developer.blender.org/rB5a1279fdce1a8d9c92d7614bc7d4f44865a139d8

faster adding to array lookup

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

M	source/blender/blenlib/BLI_array_lookup.hpp
M	source/blender/blenlib/BLI_small_map.hpp

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

diff --git a/source/blender/blenlib/BLI_array_lookup.hpp b/source/blender/blenlib/BLI_array_lookup.hpp
index ac4e6e9fa24..b30467c5212 100644
--- a/source/blender/blenlib/BLI_array_lookup.hpp
+++ b/source/blender/blenlib/BLI_array_lookup.hpp
@@ -60,6 +60,30 @@ namespace BLI {
 			}
 		}
 
+		bool add(Item *array, const Key &key, Index potential_index)
+		{
+			ITER_SLOTS(key, slot, state) {
+				if (state == SLOT_EMPTY) {
+					bool map_changed = this->ensure_can_add(array);
+					if (map_changed) {
+						this->insert_index_for_key(key, potential_index);
+					}
+					else {
+						m_map[slot] = potential_index;
+					}
+					m_length++;
+					m_usable_slots--;
+					return true;
+				}
+				else if (state == SLOT_DUMMY) {
+					continue;
+				}
+				else if (GetKey(array[state]) == key) {
+					return false;
+				}
+			}
+		}
+
 		void add_new(Item *array, Index index)
 		{
 			this->ensure_can_add(array);
@@ -106,10 +130,10 @@ namespace BLI {
 		}
 
 	private:
-		inline void ensure_can_add(Item *array)
+		inline bool ensure_can_add(Item *array)
 		{
 			if (LIKELY(m_usable_slots > 0)) {
-				return;
+				return false;
 			}
 
 			this->reset_map(m_map.size() * 2);
@@ -118,6 +142,7 @@ namespace BLI {
 				this->insert_index_for_key(key, i);
 			}
 			m_usable_slots -= m_length;
+			return true;
 		}
 
 		void reset_map(uint size)
diff --git a/source/blender/blenlib/BLI_small_map.hpp b/source/blender/blenlib/BLI_small_map.hpp
index 7738ffa36d4..31a59886df0 100644
--- a/source/blender/blenlib/BLI_small_map.hpp
+++ b/source/blender/blenlib/BLI_small_map.hpp
@@ -32,13 +32,12 @@ namespace BLI {
 
 		bool add(const K &key, const V &value)
 		{
-			if (this->contains(key)) {
-				return false;
-			}
-			else {
-				this->add_new(key, value);
-				return true;
+			uint potential_index = m_entries.size();
+			bool newly_inserted = m_lookup.add(m_entries.begin(), key, potential_index);
+			if (newly_inserted) {
+				m_entries.append(Entry(key, value));
 			}
+			return newly_inserted;
 		}
 
 		void add_new(const K &key, const V &value)



More information about the Bf-blender-cvs mailing list