[Bf-blender-cvs] [33dda8463d7] functions: improved lookup or insert functions for map

[Jacques Lucke]

Commit: 33dda8463d7e9918268b0ef1f4331b03f6536b1c
Author: Jacques Lucke
Date:   Wed Jul 3 18:41:16 2019 +0200
Branches: functions
https://developer.blender.org/rB33dda8463d7e9918268b0ef1f4331b03f6536b1c

improved lookup or insert functions for map

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

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

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

diff --git a/source/blender/blenlib/BLI_small_map.hpp b/source/blender/blenlib/BLI_small_map.hpp
index e8add508606..57b440cb5f2 100644
--- a/source/blender/blenlib/BLI_small_map.hpp
+++ b/source/blender/blenlib/BLI_small_map.hpp
@@ -162,43 +162,55 @@ template<typename K, typename V, uint N = 4> class SmallMap {
   }
 
   /**
-   * Return the pointer to the value corresponding to the key.
+   * Return a reference to the value corresponding to the key.
    * If the key does not exist yet, insert the given key-value-pair first.
    */
-  V *lookup_ptr_or_insert(const K &key, V initial_value)
+  V &lookup_ref_or_insert(const K &key, V initial_value)
   {
     V *ptr = this->lookup_ptr(key);
-    if (ptr == nullptr) {
-      this->add_new(key, initial_value);
-      ptr = &m_entries[m_entries.size() - 1].value;
+    if (ptr != nullptr) {
+      return *ptr;
     }
-    return ptr;
+    this->add_new(key, initial_value);
+    return m_entries[m_entries.size() - 1].value;
   }
 
   /**
    * Return a reference to the value corresponding to the key.
-   * If the key does not exist yet, the given function will be called
-   * with the given parameters, to create the value that will be stored for the key.
+   * If the key does not exist yet, create the value by calling the function, and insert the
+   * key-value pair.
    */
-  template<typename... Args>
-  V &lookup_ref_or_insert_func(const K &key, V (*create_value)(Args... args), Args &&... args)
+  template<typename CreateValueFunc>
+  V &lookup_ref_or_insert_func(const K &key, const CreateValueFunc &create_value)
   {
-    V *value = this->lookup_ptr(key);
-    if (value != NULL) {
-      return *value;
+    V *ptr = this->lookup_ptr(key);
+    if (ptr != nullptr) {
+      return *ptr;
     }
-    this->add_new(key, create_value(std::forward<Args>(args)...));
-    return this->lookup_ref(key);
+
+    this->add_new(key, create_value());
+    return m_entries[m_entries.size() - 1].value;
   }
 
   /**
-   * Returns a reference to the value corresponding to the key.
-   * If the key does not exist yet, the given function will be called
-   * with the key as parameter, to create the value that will be stored for the key.
+   * Insert a new value for the given key or modify the existing one.
+   * Return true when a new value was inserted, false otherwise.
    */
-  V &lookup_ref_or_insert_key_func(const K &key, V (*create_value)(const K &key))
+  template<typename CreateValueFunc, typename ModifyValueFunc>
+  bool insert_or_modify(const K &key,
+                        const CreateValueFunc &create_value,
+                        const ModifyValueFunc &modify_value)
   {
-    return lookup_ref_or_insert_func(key, create_value, key);
+    uint desired_new_index = m_entries.size();
+    uint value_index = m_lookup.add(m_entries.begin(), key, desired_new_index);
+    if (value_index == desired_new_index) {
+      m_entries.append({key, create_value()});
+      return true;
+    }
+    else {
+      modify_value(m_entries[value_index].value);
+      return false;
+    }
   }
 
   /**
diff --git a/tests/gtests/blenlib/BLI_small_map_test.cc b/tests/gtests/blenlib/BLI_small_map_test.cc
index 5ab6743cd06..366ce770070 100644
--- a/tests/gtests/blenlib/BLI_small_map_test.cc
+++ b/tests/gtests/blenlib/BLI_small_map_test.cc
@@ -87,14 +87,14 @@ TEST(small_map, PopItemMany)
   }
 }
 
-TEST(small_map, LookupPtrOrInsert)
+TEST(small_map, LookupRefOrInsert)
 {
   IntFloatMap map;
-  float *value = map.lookup_ptr_or_insert(3, 5.0f);
-  EXPECT_EQ(*value, 5.0f);
-  *value += 1;
-  value = map.lookup_ptr_or_insert(3, 5.0f);
-  EXPECT_EQ(*value, 6.0f);
+  float &value = map.lookup_ref_or_insert(3, 5.0f);
+  EXPECT_EQ(value, 5.0f);
+  value += 1;
+  value = map.lookup_ref_or_insert(3, 5.0f);
+  EXPECT_EQ(value, 6.0f);
 }
 
 TEST(small_map, ValueIterator)
@@ -170,73 +170,32 @@ float return_42()
   return 42.0f;
 }
 
-TEST(small_map, LookupOrInsertFunc_NoArgs)
+TEST(small_map, LookupOrInsertFunc_SeparateFunction)
 {
   IntFloatMap map;
   EXPECT_EQ(map.lookup_ref_or_insert_func(0, return_42), 42.0f);
   EXPECT_EQ(map.lookup(0), 42);
 }
 
-float return_identity(float a)
-{
-  return a;
-}
-
-TEST(small_map, LookupOrInsertFunc_SingleArg)
-{
-  IntFloatMap map;
-  EXPECT_EQ(map.lookup_ref_or_insert_func(1, return_identity, 5.0f), 5.0f);
-  EXPECT_EQ(map.lookup(1), 5.0f);
-}
-
-float add_func(float a, float b)
-{
-  return a + b;
-}
-
-TEST(small_map, LookupOrInsertFunc_TwoArgs)
-{
-  IntFloatMap map;
-  EXPECT_EQ(map.lookup_ref_or_insert_func(2, add_func, 4.0f, 6.0f), 10.0f);
-  EXPECT_EQ(map.lookup(2), 10.0f);
-}
-
-TEST(small_map, LookupOrInsertFunc_NoReinsert)
+TEST(small_map, LookupOrInsertFunc_Lambdas)
 {
   IntFloatMap map;
-  EXPECT_EQ(map.lookup_ref_or_insert_func(2, return_identity, 4.0f), 4.0f);
-  EXPECT_EQ(map.lookup_ref_or_insert_func(2, return_identity, 6.0f), 4.0f);
-  EXPECT_EQ(map.lookup_ref_or_insert_func(2, return_identity, 8.0f), 4.0f);
-  EXPECT_EQ(map.size(), 1);
-}
+  auto lambda1 = []() { return 11.0f; };
+  EXPECT_EQ(map.lookup_ref_or_insert_func(0, lambda1), 11.0f);
+  auto lambda2 = []() { return 20.0f; };
+  EXPECT_EQ(map.lookup_ref_or_insert_func(1, lambda2), 20.0f);
 
-float inc_value_and_return_42(int *ptr)
-{
-  *ptr += 1;
-  return 42.0f;
+  EXPECT_EQ(map.lookup_ref_or_insert_func(0, lambda2), 11.0f);
+  EXPECT_EQ(map.lookup_ref_or_insert_func(1, lambda1), 20.0f);
 }
 
-TEST(small_map, LookupOrInsertFunc_FuncCalledOnce)
+TEST(small_map, InsertOrModify)
 {
-  int counter = 0;
   IntFloatMap map;
-  EXPECT_EQ(map.lookup_ref_or_insert_func(0, inc_value_and_return_42, &counter), 42.0f);
-  EXPECT_EQ(counter, 1);
-  EXPECT_EQ(map.lookup_ref_or_insert_func(0, inc_value_and_return_42, &counter), 42.0f);
-  EXPECT_EQ(counter, 1);
-}
-
-float add_10(const int &value)
-{
-  return value + 10.0f;
-}
-
-TEST(small_map, LookupOrInsertKeyFunc)
-{
-  IntFloatMap map;
-  EXPECT_EQ(map.lookup_ref_or_insert_key_func(4, add_10), 14.0f);
-  EXPECT_EQ(map.lookup_ref_or_insert_key_func(10, add_10), 20.0f);
-
-  EXPECT_EQ(map.lookup(4), 14.0f);
-  EXPECT_EQ(map.lookup(10), 20.0f);
+  auto create_func = []() { return 10.0f; };
+  auto modify_func = [](float &value) { value += 5; };
+  EXPECT_TRUE(map.insert_or_modify(1, create_func, modify_func));
+  EXPECT_EQ(map.lookup(1), 10.0f);
+  EXPECT_FALSE(map.insert_or_modify(1, create_func, modify_func));
+  EXPECT_EQ(map.lookup(1), 15.0f);
 }