summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--indra/llcommon/CMakeLists.txt2
-rw-r--r--indra/llcommon/llinitparam.h7
-rw-r--r--indra/llcommon/llregistry.h21
-rw-r--r--indra/llcommon/llsortedvector.h152
-rw-r--r--indra/llcommon/lltypeinfolookup.h112
5 files changed, 290 insertions, 4 deletions
diff --git a/indra/llcommon/CMakeLists.txt b/indra/llcommon/CMakeLists.txt
index eec5250a23..dd7b8c6eb8 100644
--- a/indra/llcommon/CMakeLists.txt
+++ b/indra/llcommon/CMakeLists.txt
@@ -226,6 +226,7 @@ set(llcommon_HEADER_FILES
llsingleton.h
llskiplist.h
llskipmap.h
+ llsortedvector.h
llstack.h
llstacktrace.h
llstat.h
@@ -241,6 +242,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) */
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-30 15:46:42 +0000