MAINT-1175: Reimplement LLTypeInfoLookup for better lookup failure.

The original LLTypeInfoLookup implementation was based on two assumptions:
small overall container size, and infrequent normal-case lookup failures.
Those assumptions led to binary-searching a sorted vector, with linear search
as a fallback to cover the problem case of two different type_info* values for
the same type. As documented in the Jira, this turned out to be a problem. The
container size was larger than expected, and failed lookups turned out to be
far more common than expected.
The new implementation is based on a hash map of std::type_info::name()
strings, which should perform equally well in the success and failure cases:
no special-case fallback logic.

1 files changed, 61 insertions, 58 deletions

diff --git a/indra/llcommon/lltypeinfolookup.h b/indra/llcommon/lltypeinfolookup.h
index 7510cc12ed..1e62d33488 100644
--- a/indra/llcommon/lltypeinfolookup.h
+++ b/indra/llcommon/lltypeinfolookup.h
@@ -12,8 +12,12 @@
 #if ! defined(LL_LLTYPEINFOLOOKUP_H)
 #define LL_LLTYPEINFOLOOKUP_H
 
-#include "llsortedvector.h"
+#include <boost/unordered_map.hpp>
+#include <boost/function.hpp>
+#include <boost/mem_fn.hpp>
+#include <boost/iterator/transform_iterator.hpp>
 #include <typeinfo>
+#include <map>
 
 /**
  * LLTypeInfoLookup is specifically designed for use cases for which you might
@@ -22,40 +26,52 @@
  * you can't rely on always getting the same std::type_info* for a given type:
  * different load modules will produce different std::type_info*.
  * LLTypeInfoLookup contains a workaround to address this issue.
- *
- * Specifically, when we don't find the passed std::type_info*,
- * LLTypeInfoLookup performs a linear search over registered entries to
- * compare name() strings. Presuming that this succeeds, we cache the new
- * (previously unrecognized) std::type_info* to speed future lookups.
- *
- * This worst-case fallback search (linear search with string comparison)
- * should only happen the first time we look up a given type from a particular
- * load module other than the one from which we initially registered types.
- * (However, a lookup which wouldn't succeed anyway will always have
- * worst-case performance.) This class is probably best used with less than a
- * few dozen different types.
  */
 template <typename VALUE>
 class LLTypeInfoLookup
 {
+    // We present an interface like this:
+    typedef std::map<const std::type_info*, VALUE> intf_map_type;
+    // Use this for our underlying implementation: lookup by
+    // std::type_info::name() string. Note that we must store a std::pair<const
+    // std::type_info*, VALUE> -- in other words, an intf_map_type::value_type
+    // pair -- so we can present iterators that do the right thing.
+    // (This might result in a lookup with one std::type_info* returning an
+    // iterator to a different std::type_info*, but frankly, my dear, we don't
+    // give a damn.)
+    typedef boost::unordered_map<std::string, typename intf_map_type::value_type> impl_map_type;
+    // Iterator shorthand
+    typedef typename intf_map_type::iterator       intf_iterator;
+    typedef typename intf_map_type::const_iterator intf_const_iterator;
+    typedef typename intf_map_type::value_type     intf_value_type;
+    typedef typename impl_map_type::iterator       impl_iterator;
+    typedef typename impl_map_type::const_iterator impl_const_iterator;
+    typedef typename impl_map_type::value_type     impl_value_type;
+    // Type of function that transforms impl_value_type to intf_value_type
+    typedef boost::function<intf_value_type&(impl_value_type&)> iterfunc;
+    typedef boost::function<const intf_value_type&(const impl_value_type&)> const_iterfunc;
+
 public:
     typedef LLTypeInfoLookup<VALUE> self;
-    typedef LLSortedVector<const std::type_info*, VALUE> vector_type;
-    typedef typename vector_type::key_type key_type;
-    typedef typename vector_type::mapped_type mapped_type;
-    typedef typename vector_type::value_type value_type;
-    typedef typename vector_type::iterator iterator;
-    typedef typename vector_type::const_iterator const_iterator;
+    typedef typename intf_map_type::key_type    key_type;
+    typedef typename intf_map_type::mapped_type mapped_type;
+    typedef intf_value_type                     value_type;
+
+    // Iterators are different because we have to transform
+    // impl_map_type::iterator to intf_map_type::iterator.
+    typedef boost::transform_iterator<iterfunc, impl_iterator> iterator;
+    typedef boost::transform_iterator<const_iterfunc, impl_const_iterator> const_iterator;
 
     LLTypeInfoLookup() {}
 
-    iterator begin() { return mVector.begin(); }
-    iterator end()   { return mVector.end(); }
-    const_iterator begin() const { return mVector.begin(); }
-    const_iterator end()   const { return mVector.end(); }
-    bool empty() const { return mVector.empty(); }
-    std::size_t size() const { return mVector.size(); }
+    iterator begin() { return transform(mMap.begin()); }
+    iterator end()   { return transform(mMap.end()); }
+    const_iterator begin() const { return transform(mMap.begin()); }
+    const_iterator end() const   { return transform(mMap.end()); }
+    bool empty() const { return mMap.empty(); }
+    std::size_t size() const { return mMap.size(); }
 
+    // Shorthand -- I've always wished std::map supported this signature.
     std::pair<iterator, bool> insert(const std::type_info* key, const VALUE& value)
     {
         return insert(value_type(key, value));
@@ -63,48 +79,35 @@ public:
 
     std::pair<iterator, bool> insert(const value_type& pair)
     {
-        return mVector.insert(pair);
+        // Obtain and store the std::type_info::name() string as the key.
+        // Save the whole incoming pair as the value!
+        std::pair<impl_iterator, bool>
+            inserted(mMap.insert(impl_value_type(pair.first->name(), pair)));
+        // Have to transform the iterator before returning.
+        return std::pair<iterator, bool>(transform(inserted.first), inserted.second);
     }
 
-    // const find() forwards to non-const find(): this can alter mVector!
-    const_iterator find(const std::type_info* key) const
+    iterator find(const std::type_info* key)
     {
-        return const_cast<self*>(this)->find(key);
+        return transform(mMap.find(key->name()));
     }
 
-    // non-const find() caches previously-unknown type_info* to speed future
-    // lookups.
-    iterator find(const std::type_info* key)
+    const_iterator find(const std::type_info* key) const
     {
-        iterator found = mVector.find(key);
-        if (found != mVector.end())
-        {
-            // If LLSortedVector::find() found, great, we're done.
-            return found;
-        }
-        // Here we didn't find the passed type_info*. On Linux, though, even
-        // for the same type, typeid(sametype) produces a different type_info*
-        // when used in different load modules. So the fact that we didn't
-        // find the type_info* we seek doesn't mean this type isn't
-        // registered. Scan for matching name() string.
-        for (typename vector_type::iterator ti(mVector.begin()), tend(mVector.end());
-             ti != tend; ++ti)
-        {
-            if (std::string(ti->first->name()) == key->name())
-            {
-                // This unrecognized 'key' is for the same type as ti->first.
-                // To speed future lookups, insert a new entry that lets us
-                // look up ti->second using this same 'key'.
-                return insert(key, ti->second).first;
-            }
-        }
-        // We simply have never seen a type with this type_info* from any load
-        // module.
-        return mVector.end();
+        return transform(mMap.find(key->name()));
     }
 
 private:
-    vector_type mVector;
+    iterator transform(impl_iterator iter)
+    {
+        return boost::make_transform_iterator(iter, boost::mem_fn(&impl_value_type::second));
+    }
+    const_iterator transform(impl_const_iterator iter)
+    {
+        return boost::make_transform_iterator(iter, boost::mem_fn(&impl_value_type::second));
+    }
+
+    impl_map_type mMap;
 };
 
 #endif /* ! defined(LL_LLTYPEINFOLOOKUP_H) */