Fix Linux UI issues introduced by moving llinitparam to llcommon.

In a number of places, the viewer uses a lookup based on std::type_info*. We
used to use std::map<std::type_info*, whatever>. But on Linux,
&typeid(SomeType) can produce different pointer values, depending on the
dynamic load module in which the code is executed. Introduce
LLTypeInfoLookup<T>, with an API that deliberately mimics
std::map<std::type_info*, T>. LLTypeInfoLookup::find() first tries an
efficient search for the specified std::type_info*. But if that fails, it
scans the underlying container for a match on the std::type_info::name()
string. If found, it caches the new std::type_info* to optimize subsequent
lookups with the same pointer.
Use LLTypeInfoLookup instead of std::map<std::type_info*, ...> in
llinitparam.h and llregistry.h.
Introduce LLSortedVector<KEY, VALUE>, a std::vector<std::pair<KEY, VALUE>>
maintained in sorted order with binary-search lookup. It presents a subset of
the std::map<KEY, VALUE> API.

5 files changed, 290 insertions, 4 deletions

diff --git a/indra/llcommon/CMakeLists.txt b/indra/llcommon/CMakeLists.txt
index a1aa887d3a..f9bc22e98a 100644
--- a/indra/llcommon/CMakeLists.txt
+++ b/indra/llcommon/CMakeLists.txt
@@ -221,6 +221,7 @@ set(llcommon_HEADER_FILES
     llsingleton.h
     llskiplist.h
     llskipmap.h
+    llsortedvector.h
     llstack.h
     llstacktrace.h
     llstat.h
@@ -235,6 +236,7 @@ set(llcommon_HEADER_FILES
     llthreadsafequeue.h
     lltimer.h
     lltreeiterators.h
+    lltypeinfolookup.h
     lluri.h
     lluuid.h
     lluuidhashmap.h
diff --git a/indra/llcommon/llinitparam.h b/indra/llcommon/llinitparam.h
index beaf07e56b..ef6c6335d1 100644
--- a/indra/llcommon/llinitparam.h
+++ b/indra/llcommon/llinitparam.h
@@ -35,6 +35,7 @@
 #include <boost/shared_ptr.hpp>
 
 #include "llerror.h"
+#include "lltypeinfolookup.h"
 
 namespace LLInitParam
 {
@@ -227,9 +228,9 @@ namespace LLInitParam
 		typedef bool (*parser_write_func_t)(Parser& parser, const void*, name_stack_t&);
 		typedef boost::function<void (name_stack_t&, S32, S32, const possible_values_t*)>	parser_inspect_func_t;
 
-		typedef std::map<const std::type_info*, parser_read_func_t, CompareTypeID>		parser_read_func_map_t;
-		typedef std::map<const std::type_info*, parser_write_func_t, CompareTypeID>		parser_write_func_map_t;
-		typedef std::map<const std::type_info*, parser_inspect_func_t, CompareTypeID>	parser_inspect_func_map_t;
+		typedef LLTypeInfoLookup<parser_read_func_t>		parser_read_func_map_t;
+		typedef LLTypeInfoLookup<parser_write_func_t>		parser_write_func_map_t;
+		typedef LLTypeInfoLookup<parser_inspect_func_t>		parser_inspect_func_map_t;
 
 		Parser(parser_read_func_map_t& read_map, parser_write_func_map_t& write_map, parser_inspect_func_map_t& inspect_map)
 		:	mParseSilently(false),
diff --git a/indra/llcommon/llregistry.h b/indra/llcommon/llregistry.h
index 36ce6a97b7..36d7f7a44c 100644
--- a/indra/llcommon/llregistry.h
+++ b/indra/llcommon/llregistry.h
@@ -31,6 +31,7 @@
 
 #include <boost/type_traits.hpp>
 #include "llsingleton.h"
+#include "lltypeinfolookup.h"
 
 template <typename T>
 class LLRegistryDefaultComparator
@@ -38,6 +39,24 @@ class LLRegistryDefaultComparator
 	bool operator()(const T& lhs, const T& rhs) { return lhs < rhs; }
 };
 
+template <typename KEY, typename VALUE>
+struct LLRegistryMapSelector
+{
+    typedef std::map<KEY, VALUE> type;
+};
+
+template <typename VALUE>
+struct LLRegistryMapSelector<std::type_info*, VALUE>
+{
+    typedef LLTypeInfoLookup<VALUE> type;
+};
+
+template <typename VALUE>
+struct LLRegistryMapSelector<const std::type_info*, VALUE>
+{
+    typedef LLTypeInfoLookup<VALUE> type;
+};
+
 template <typename KEY, typename VALUE, typename COMPARATOR = LLRegistryDefaultComparator<KEY> >
 class LLRegistry
 {
@@ -53,7 +72,7 @@ public:
 	{
 		friend class LLRegistry<KEY, VALUE, COMPARATOR>;
 	public:
-		typedef typename std::map<KEY, VALUE> registry_map_t;
+		typedef typename LLRegistryMapSelector<KEY, VALUE>::type registry_map_t;
 
 		bool add(ref_const_key_t key, ref_const_value_t value)
 		{
diff --git a/indra/llcommon/llsortedvector.h b/indra/llcommon/llsortedvector.h
new file mode 100644
index 0000000000..391b82ee44
--- /dev/null
+++ b/indra/llcommon/llsortedvector.h
@@ -0,0 +1,152 @@
+/**
+ * @file   llsortedvector.h
+ * @author Nat Goodspeed
+ * @date   2012-04-08
+ * @brief  LLSortedVector class wraps a vector that we maintain in sorted
+ *         order so we can perform binary-search lookups.
+ * 
+ * $LicenseInfo:firstyear=2012&license=viewerlgpl$
+ * Copyright (c) 2012, Linden Research, Inc.
+ * $/LicenseInfo$
+ */
+
+#if ! defined(LL_LLSORTEDVECTOR_H)
+#define LL_LLSORTEDVECTOR_H
+
+#include <vector>
+#include <algorithm>
+
+/**
+ * LLSortedVector contains a std::vector<std::pair> that we keep sorted on the
+ * first of the pair. This makes insertion somewhat more expensive than simple
+ * std::vector::push_back(), but allows us to use binary search for lookups.
+ * It's intended for small aggregates where lookup is far more performance-
+ * critical than insertion; in such cases a binary search on a small, sorted
+ * std::vector can be more performant than a std::map lookup.
+ */
+template <typename KEY, typename VALUE>
+class LLSortedVector
+{
+public:
+    typedef LLSortedVector<KEY, VALUE> self;
+    typedef KEY key_type;
+    typedef VALUE mapped_type;
+    typedef std::pair<key_type, mapped_type> value_type;
+    typedef std::vector<value_type> PairVector;
+    typedef typename PairVector::iterator iterator;
+    typedef typename PairVector::const_iterator const_iterator;
+
+    /// Empty
+    LLSortedVector() {}
+
+    /// Fixed initial size
+    LLSortedVector(std::size_t size):
+        mVector(size)
+    {}
+
+    /// Bulk load
+    template <typename ITER>
+    LLSortedVector(ITER begin, ITER end):
+        mVector(begin, end)
+    {
+        // Allow caller to dump in a bunch of (pairs convertible to)
+        // value_type if desired, but make sure we sort afterwards.
+        std::sort(mVector.begin(), mVector.end());
+    }
+
+    /// insert(key, value)
+    std::pair<iterator, bool> insert(const key_type& key, const mapped_type& value)
+    {
+        return insert(value_type(key, value));
+    }
+
+    /// insert(value_type)
+    std::pair<iterator, bool> insert(const value_type& pair)
+    {
+        typedef std::pair<iterator, bool> iterbool;
+        iterator found = std::lower_bound(mVector.begin(), mVector.end(), pair,
+                                          less<value_type>());
+        // have to check for end() before it's even valid to dereference
+        if (found == mVector.end())
+        {
+            std::size_t index(mVector.size());
+            mVector.push_back(pair);
+            // don't forget that push_back() invalidates 'found'
+            return iterbool(mVector.begin() + index, true);
+        }
+        if (found->first == pair.first)
+        {
+            return iterbool(found, false);
+        }
+        // remember that insert() invalidates 'found' -- save index
+        std::size_t index(found - mVector.begin());
+        mVector.insert(found, pair);
+        // okay, convert from index back to iterator
+        return iterbool(mVector.begin() + index, true);
+    }
+
+    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(); }
+
+    /// find
+    iterator find(const key_type& key)
+    {
+        iterator found = std::lower_bound(mVector.begin(), mVector.end(),
+                                          value_type(key, mapped_type()),
+                                          less<value_type>());
+        if (found == mVector.end() || found->first != key)
+            return mVector.end();
+        return found;
+    }
+
+    const_iterator find(const key_type& key) const
+    {
+        return const_cast<self*>(this)->find(key);
+    }
+
+private:
+    // Define our own 'less' comparator so we can specialize without messing
+    // with std::less.
+    template <typename T>
+    struct less: public std::less<T> {};
+
+    // Specialize 'less' for an LLSortedVector::value_type involving
+    // std::type_info*. This is one of LLSortedVector's foremost use cases. We
+    // specialize 'less' rather than just defining a specific comparator
+    // because LLSortedVector should be usable for other key_types as well.
+    template <typename T>
+    struct less< std::pair<std::type_info*, T> >:
+        public std::binary_function<std::pair<std::type_info*, T>,
+                                    std::pair<std::type_info*, T>,
+                                    bool>
+    {
+        bool operator()(const std::pair<std::type_info*, T>& lhs,
+                        const std::pair<std::type_info*, T>& rhs) const
+        {
+            return lhs.first->before(*rhs.first);
+        }
+    };
+
+    // Same as above, but with const std::type_info*.
+    template <typename T>
+    struct less< std::pair<const std::type_info*, T> >:
+        public std::binary_function<std::pair<const std::type_info*, T>,
+                                    std::pair<const std::type_info*, T>,
+                                    bool>
+    {
+        bool operator()(const std::pair<const std::type_info*, T>& lhs,
+                        const std::pair<const std::type_info*, T>& rhs) const
+        {
+            return lhs.first->before(*rhs.first);
+        }
+    };
+
+    PairVector mVector;
+};
+
+#endif /* ! defined(LL_LLSORTEDVECTOR_H) */
diff --git a/indra/llcommon/lltypeinfolookup.h b/indra/llcommon/lltypeinfolookup.h
new file mode 100644
index 0000000000..fc99f7ff33
--- /dev/null
+++ b/indra/llcommon/lltypeinfolookup.h
@@ -0,0 +1,112 @@
+/**
+ * @file   lltypeinfolookup.h
+ * @author Nat Goodspeed
+ * @date   2012-04-08
+ * @brief  Template data structure like std::map<std::type_info*, T>
+ * 
+ * $LicenseInfo:firstyear=2012&license=viewerlgpl$
+ * Copyright (c) 2012, Linden Research, Inc.
+ * $/LicenseInfo$
+ */
+
+#if ! defined(LL_LLTYPEINFOLOOKUP_H)
+#define LL_LLTYPEINFOLOOKUP_H
+
+#include "llsortedvector.h"
+#include <typeinfo>
+
+/**
+ * LLTypeInfoLookup is specifically designed for use cases for which you might
+ * consider std::map<std::type_info*, VALUE>. We have several such data
+ * structures in the viewer. The trouble with them is that at least on Linux,
+ * 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
+{
+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;
+
+    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(); }
+
+    std::pair<iterator, bool> insert(const std::type_info* key, const VALUE& value)
+    {
+        return insert(value_type(key, value));
+    }
+
+    std::pair<iterator, bool> insert(const value_type& pair)
+    {
+        return mVector.insert(pair);
+    }
+
+    const_iterator find(const std::type_info* key) const
+    {
+        return const_cast<self*>(this)->find(key);
+    }
+
+    iterator find(const std::type_info* key)
+    {
+        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();
+    }
+
+private:
+    /// Our LLSortedVector is mutable so that if we're passed an unrecognized
+    /// std::type_info* for a registered type (which we can identify by
+    /// searching for the name() string), we can cache the new std::type_info*
+    /// to speed future lookups -- even when the containing LLTypeInfoLookup
+    /// is const.
+    vector_type mVector;
+};
+
+#endif /* ! defined(LL_LLTYPEINFOLOOKUP_H) */