[Bf-blender-cvs] [3ab2a2af293] functions: correct small object optimization for sets and maps

[Jacques Lucke]

Commit: 3ab2a2af293354b87ff0ee87401416bb0dc60def
Author: Jacques Lucke
Date:   Wed May 22 16:37:07 2019 +0200
Branches: functions
https://developer.blender.org/rB3ab2a2af293354b87ff0ee87401416bb0dc60def

correct small object optimization for sets and maps

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

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

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

diff --git a/source/blender/blenlib/BLI_array_lookup.hpp b/source/blender/blenlib/BLI_array_lookup.hpp
index e40a5cec5b6..7f3ca3afcc1 100644
--- a/source/blender/blenlib/BLI_array_lookup.hpp
+++ b/source/blender/blenlib/BLI_array_lookup.hpp
@@ -8,6 +8,8 @@
  * it allows fast `contains` and `find` calls on that array.
  */
 
+#include <cmath>
+
 #include "BLI_utildefines.h"
 #include "BLI_small_vector.hpp"
 #include "BLI_math_bits.h"
@@ -47,14 +49,16 @@ template<typename T> struct ArrayLookupHash<T *> {
 };
 
 template<typename Key,
+         uint N = 4,
          typename Item = Key,
          const Key &GetKey(const Item &entry) = get_key_from_item,
-         uint N_EXP = 3,
          typename Hash = ArrayLookupHash<Key>,
          typename Index = int>
 class ArrayLookup {
  private:
+  static const uint N_EXP = (uint)std::ceil(std::log2(N)) + 1;
   using Mapping = SmallVector<Index, (1 << N_EXP)>;
+
   Mapping m_map;
   uint m_length;
   uint m_dummy_amount;
diff --git a/source/blender/blenlib/BLI_small_map.hpp b/source/blender/blenlib/BLI_small_map.hpp
index c21779adfe9..c86858a6637 100644
--- a/source/blender/blenlib/BLI_small_map.hpp
+++ b/source/blender/blenlib/BLI_small_map.hpp
@@ -30,8 +30,8 @@ template<typename K, typename V, uint N = 4> class SmallMap {
     return entry.key;
   }
 
-  SmallVector<Entry> m_entries;
-  ArrayLookup<K, Entry, get_key_from_entry> m_lookup;
+  SmallVector<Entry, N> m_entries;
+  ArrayLookup<K, N, Entry, get_key_from_entry> m_lookup;
 
  public:
   class ValueIterator;
diff --git a/source/blender/blenlib/BLI_small_set.hpp b/source/blender/blenlib/BLI_small_set.hpp
index 41308735e5d..aae740ac76f 100644
--- a/source/blender/blenlib/BLI_small_set.hpp
+++ b/source/blender/blenlib/BLI_small_set.hpp
@@ -11,10 +11,10 @@
 
 namespace BLI {
 
-template<typename T, uint N = 4, typename Hash = std::hash<T>> class SmallSet {
+template<typename T, uint N = 4> class SmallSet {
  protected:
-  SmallVector<T> m_elements;
-  ArrayLookup<T> m_lookup;
+  SmallVector<T, N> m_elements;
+  ArrayLookup<T, N> m_lookup;
 
  public:
   SmallSet() = default;