[Bf-blender-cvs] [b07b7d0a63d] functions: deduplicate some array lookup code

[Jacques Lucke]

Commit: b07b7d0a63d0a85a60647bdea9d312df085d7d0a
Author: Jacques Lucke
Date:   Mon Apr 15 15:03:23 2019 +0200
Branches: functions
https://developer.blender.org/rBb07b7d0a63d0a85a60647bdea9d312df085d7d0a

deduplicate some array lookup code

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

M	source/blender/blenlib/BLI_array_lookup.hpp
M	source/blender/blenlib/BLI_small_map.hpp
M	source/blender/blenlib/BLI_small_set.hpp
M	tests/gtests/blenlib/BLI_small_set_test.cc

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

diff --git a/source/blender/blenlib/BLI_array_lookup.hpp b/source/blender/blenlib/BLI_array_lookup.hpp
index 5be33618492..ac33ea5336d 100644
--- a/source/blender/blenlib/BLI_array_lookup.hpp
+++ b/source/blender/blenlib/BLI_array_lookup.hpp
@@ -129,6 +129,21 @@ namespace BLI {
 			}
 		}
 
+		Index remove(Item *array, const Key &key)
+		{
+			BLI_assert(this->contains(array, key));
+			ITER_SLOTS(key, slot, state) {
+				if (state == SLOT_DUMMY) {
+					continue;
+				}
+				else if (GetKey(array[state]) == key) {
+					m_map[slot] = SLOT_DUMMY;
+					m_length--;
+					return state;
+				}
+			}
+		}
+
 	private:
 		inline bool ensure_can_add(Item *array)
 		{
diff --git a/source/blender/blenlib/BLI_small_map.hpp b/source/blender/blenlib/BLI_small_map.hpp
index 911c5353e71..301da9776bd 100644
--- a/source/blender/blenlib/BLI_small_map.hpp
+++ b/source/blender/blenlib/BLI_small_map.hpp
@@ -57,17 +57,15 @@ namespace BLI {
 		V pop(const K &key)
 		{
 			BLI_assert(this->contains(key));
-			uint index = m_lookup.find(m_entries.begin(), key);
+			uint index = m_lookup.remove(m_entries.begin(), key);
 			V value = m_entries[index].value;
 
 			uint last_index = m_entries.size() - 1;
 			if (index == last_index) {
 				m_entries.remove_last();
-				m_lookup.remove(key, index);
 			}
 			else {
 				m_entries.remove_and_reorder(index);
-				m_lookup.remove(key, index);
 				K &moved_key = m_entries[index].key;
 				m_lookup.update_index(moved_key, last_index, index);
 			}
diff --git a/source/blender/blenlib/BLI_small_set.hpp b/source/blender/blenlib/BLI_small_set.hpp
index dacd8f82dec..08cd9e22597 100644
--- a/source/blender/blenlib/BLI_small_set.hpp
+++ b/source/blender/blenlib/BLI_small_set.hpp
@@ -71,16 +71,14 @@ namespace BLI {
 		void remove(const T &value)
 		{
 			BLI_assert(this->contains(value));
-			uint index = m_lookup.find(m_elements.begin(), value);
+			uint index = m_lookup.remove(m_elements.begin(), value);
 
 			uint last_index = m_elements.size() - 1;
 			if (index == last_index) {
 				m_elements.remove_last();
-				m_lookup.remove(value, index);
 			}
 			else {
 				m_elements.remove_and_reorder(index);
-				m_lookup.remove(value, index);
 				T &moved_value = m_elements[index];
 				m_lookup.update_index(moved_value, last_index, index);
 			}
diff --git a/tests/gtests/blenlib/BLI_small_set_test.cc b/tests/gtests/blenlib/BLI_small_set_test.cc
index 4a1c98ea965..c781988d7e0 100644
--- a/tests/gtests/blenlib/BLI_small_set_test.cc
+++ b/tests/gtests/blenlib/BLI_small_set_test.cc
@@ -99,3 +99,27 @@ TEST(small_set, Remove)
 	EXPECT_FALSE(set.contains(4));
 	EXPECT_FALSE(set.contains(5));
 }
+
+TEST(small_set, RemoveMany)
+{
+	IntSet set;
+	for (uint i = 0; i < 1000; i++) {
+		set.add(i);
+	}
+	for (uint i = 100; i < 1000; i++) {
+		set.remove(i);
+	}
+	for (uint i = 900; i < 1000; i++) {
+		set.add(i);
+	}
+
+	for (uint i = 0; i < 1000; i++) {
+		if (i < 100 || i >= 900) {
+			EXPECT_TRUE(set.contains(i));
+		}
+		else {
+			EXPECT_FALSE(set.contains(i));
+		}
+	}
+
+}