[Bf-blender-cvs] [cbefe2ad550] functions: initial SmallMap

[Jacques Lucke]

Commit: cbefe2ad5504e82714f3cb8b085171bf7e9932f1
Author: Jacques Lucke
Date:   Fri Jan 25 16:28:11 2019 +0100
Branches: functions
https://developer.blender.org/rBcbefe2ad5504e82714f3cb8b085171bf7e9932f1

initial SmallMap

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

A	source/blender/blenlib/BLI_small_map.hpp
M	source/blender/blenlib/CMakeLists.txt
A	tests/gtests/blenlib/BLI_small_map_test.cc
M	tests/gtests/blenlib/CMakeLists.txt

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

diff --git a/source/blender/blenlib/BLI_small_map.hpp b/source/blender/blenlib/BLI_small_map.hpp
new file mode 100644
index 00000000000..5ac6dd25f6b
--- /dev/null
+++ b/source/blender/blenlib/BLI_small_map.hpp
@@ -0,0 +1,56 @@
+#pragma
+
+#include "BLI_small_vector.hpp"
+
+namespace BLI {
+
+	template<typename K, typename V, uint N = 4>
+	class SmallMap {
+	private:
+		struct Entry {
+			K key;
+			V value;
+
+			Entry() {}
+			Entry(K key, V value)
+				: key(key), value(value) {}
+		};
+
+		SmallVector<Entry> m_entries;
+
+	public:
+		SmallMap() {}
+
+		void add(K key, V value)
+		{
+			if (!this->contains(key)) {
+				this->m_entries.append(Entry(key, value));
+			}
+		}
+
+		bool contains(K key) const
+		{
+			for (const Entry &entry : this->m_entries) {
+				if (entry.key == key) {
+					return true;
+				}
+			}
+			return false;
+		}
+
+		V lookup(K key) const
+		{
+			for (const Entry &entry : this->m_entries) {
+				if (entry.key == key) {
+					return entry.value;
+				}
+			}
+			BLI_assert(false);
+		}
+
+		uint size() const
+		{
+			return this->m_entries.size();
+		}
+	};
+};
\ No newline at end of file
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 3f89a1c6603..0e84b210863 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -226,6 +226,7 @@ set(SRC
 	PIL_time_utildefines.h
 
 	BLI_small_vector.hpp
+	BLI_small_map.hpp
 )
 
 if(WITH_MEM_VALGRIND)
diff --git a/tests/gtests/blenlib/BLI_small_map_test.cc b/tests/gtests/blenlib/BLI_small_map_test.cc
new file mode 100644
index 00000000000..793e83a59ea
--- /dev/null
+++ b/tests/gtests/blenlib/BLI_small_map_test.cc
@@ -0,0 +1,39 @@
+#include "testing/testing.h"
+#include "BLI_small_map.hpp"
+
+using IntFloatMap = BLI::SmallMap<int, float>;
+
+TEST(small_map, DefaultConstructor)
+{
+	IntFloatMap map;
+	EXPECT_EQ(map.size(), 0);
+}
+
+TEST(small_map, AddIncreasesSize)
+{
+	IntFloatMap map;
+	EXPECT_EQ(map.size(), 0);
+	map.add(2, 5.0f);
+	EXPECT_EQ(map.size(), 1);
+	map.add(6, 2.0f);
+	EXPECT_EQ(map.size(), 2);
+}
+
+TEST(small_map, Contains)
+{
+	IntFloatMap map;
+	EXPECT_FALSE(map.contains(4));
+	map.add(5, 6.0f);
+	EXPECT_FALSE(map.contains(4));
+	map.add(4, 2.0f);
+	EXPECT_TRUE(map.contains(4));
+}
+
+TEST(small_map, LookupExisting)
+{
+	IntFloatMap map;
+	map.add(2, 6.0f);
+	map.add(4, 1.0f);
+	EXPECT_EQ(map.lookup(2), 6.0f);
+	EXPECT_EQ(map.lookup(4), 1.0f);
+}
\ No newline at end of file
diff --git a/tests/gtests/blenlib/CMakeLists.txt b/tests/gtests/blenlib/CMakeLists.txt
index 4da1a42d7ec..f3b099e86de 100644
--- a/tests/gtests/blenlib/CMakeLists.txt
+++ b/tests/gtests/blenlib/CMakeLists.txt
@@ -56,6 +56,7 @@ BLENDER_TEST(BLI_memiter "bf_blenlib")
 BLENDER_TEST(BLI_path_util "${BLI_path_util_extra_libs}")
 BLENDER_TEST(BLI_polyfill_2d "bf_blenlib")
 BLENDER_TEST(BLI_small_vector "bf_blenlib")
+BLENDER_TEST(BLI_small_map "bf_blenlib")
 BLENDER_TEST(BLI_stack "bf_blenlib")
 BLENDER_TEST(BLI_string "bf_blenlib")
 BLENDER_TEST(BLI_string_utf8 "bf_blenlib")