From 578d70dec0a01b5ed7b461c38503c082ac1a3608 Mon Sep 17 00:00:00 2001 From: Nat Goodspeed Date: Wed, 11 Jul 2012 08:20:14 -0400 Subject: MAINT-1175: Change LLTypeInfoLookup API for future optimizations. Per discussion with Richard, accept the type key for insert() and find() as a template parameter rather than as std::type_info*. This permits (e.g.) some sort of compile-time prehashing for common types, without changing the API. Eliminate iterators from the API altogether, thus avoiding costs associated with transform_iterator. Fix existing references in llinitparam.h. --- indra/llcommon/llinitparam.h | 24 +++++------ indra/llcommon/lltypeinfolookup.h | 90 +++++++++++---------------------------- 2 files changed, 38 insertions(+), 76 deletions(-) (limited to 'indra/llcommon') diff --git a/indra/llcommon/llinitparam.h b/indra/llcommon/llinitparam.h index 99983a19cb..c0170e533b 100644 --- a/indra/llcommon/llinitparam.h +++ b/indra/llcommon/llinitparam.h @@ -242,20 +242,20 @@ namespace LLInitParam template bool readValue(T& param) { - parser_read_func_map_t::iterator found_it = mParserReadFuncs->find(&typeid(T)); - if (found_it != mParserReadFuncs->end()) + boost::optional found_it = mParserReadFuncs->find(); + if (found_it) { - return found_it->second(*this, (void*)¶m); + return (*found_it)(*this, (void*)¶m); } return false; } template bool writeValue(const T& param, name_stack_t& name_stack) { - parser_write_func_map_t::iterator found_it = mParserWriteFuncs->find(&typeid(T)); - if (found_it != mParserWriteFuncs->end()) + boost::optional found_it = mParserWriteFuncs->find(); + if (found_it) { - return found_it->second(*this, (const void*)¶m, name_stack); + return (*found_it)(*this, (const void*)¶m, name_stack); } return false; } @@ -263,10 +263,10 @@ namespace LLInitParam // dispatch inspection to registered inspection functions, for each parameter in a param block template bool inspectValue(name_stack_t& name_stack, S32 min_count, S32 max_count, const possible_values_t* possible_values) { - parser_inspect_func_map_t::iterator found_it = mParserInspectFuncs->find(&typeid(T)); - if (found_it != mParserInspectFuncs->end()) + boost::optional found_it = mParserInspectFuncs->find(); + if (found_it) { - found_it->second(name_stack, min_count, max_count, possible_values); + (*found_it)(name_stack, min_count, max_count, possible_values); return true; } return false; @@ -281,14 +281,14 @@ namespace LLInitParam template void registerParserFuncs(parser_read_func_t read_func, parser_write_func_t write_func = NULL) { - mParserReadFuncs->insert(std::make_pair(&typeid(T), read_func)); - mParserWriteFuncs->insert(std::make_pair(&typeid(T), write_func)); + mParserReadFuncs->insert(read_func); + mParserWriteFuncs->insert(write_func); } template void registerInspectFunc(parser_inspect_func_t inspect_func) { - mParserInspectFuncs->insert(std::make_pair(&typeid(T), inspect_func)); + mParserInspectFuncs->insert(inspect_func); } bool mParseSilently; diff --git a/indra/llcommon/lltypeinfolookup.h b/indra/llcommon/lltypeinfolookup.h index 679cc51f1d..5267e3d2fb 100644 --- a/indra/llcommon/lltypeinfolookup.h +++ b/indra/llcommon/lltypeinfolookup.h @@ -13,11 +13,8 @@ #define LL_LLTYPEINFOLOOKUP_H #include -#include -#include -#include +#include #include -#include /** * LLTypeInfoLookup is specifically designed for use cases for which you might @@ -26,87 +23,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. + * + * The API deliberately diverges from std::map in several respects: + * * It avoids iterators, not only begin()/end() but also as return values + * from insert() and find(). This bypasses transform_iterator overhead. + * * Since we literally use compile-time types as keys, the essential insert() + * and find() methods accept the key type as a @em template parameter, + * accepting and returning value_type as a normal runtime value. This is to + * permit future optimization (e.g. compile-time type hashing) without + * changing the API. */ template class LLTypeInfoLookup { - // We present an interface like this: - typedef std::map intf_map_type; // Use this for our underlying implementation: lookup by - // std::type_info::name() string. Note that we must store a std::pair -- 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 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 iterfunc; - typedef boost::function const_iterfunc; + // std::type_info::name() string. This is one of the rare cases in which I + // dare use const char* directly, rather than std::string, because I'm + // sure that every value returned by std::type_info::name() is static. + typedef boost::unordered_map impl_map_type; public: - typedef LLTypeInfoLookup self; - 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 iterator; - typedef boost::transform_iterator const_iterator; + typedef VALUE value_type; LLTypeInfoLookup() {} - iterator begin() { return transform(mMap.begin()); } - iterator end() { return transform(mMap.end()); } - const_iterator begin() const { return const_transform(mMap.begin()); } - const_iterator end() const { return const_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 insert(const std::type_info* key, const VALUE& value) - { - return insert(value_type(key, value)); - } - - std::pair insert(const value_type& pair) + template + bool insert(const value_type& value) { // Obtain and store the std::type_info::name() string as the key. - // Save the whole incoming pair as the value! - std::pair - inserted(mMap.insert(impl_value_type(pair.first->name(), pair))); - // Have to transform the iterator before returning. - return std::pair(transform(inserted.first), inserted.second); - } - - iterator find(const std::type_info* key) - { - return transform(mMap.find(key->name())); + // Return just the bool from std::map::insert()'s return pair. + return mMap.insert(typename impl_map_type::value_type(typeid(KEY).name(), value)).second; } - const_iterator find(const std::type_info* key) const + template + boost::optional find() const { - return const_transform(mMap.find(key->name())); + // Use the std::type_info::name() string as the key. + typename impl_map_type::const_iterator found = mMap.find(typeid(KEY).name()); + if (found == mMap.end()) + return boost::optional(); + return found->second; } private: - iterator transform(impl_iterator iter) - { - return iterator(iter, boost::mem_fn(&impl_value_type::second)); - } - const_iterator const_transform(impl_const_iterator iter) - { - return const_iterator(iter, boost::mem_fn(&impl_value_type::second)); - } - impl_map_type mMap; }; -- cgit v1.2.3 From 709c1eeae90dae106800e3742f3655bd7b590b7b Mon Sep 17 00:00:00 2001 From: Nat Goodspeed Date: Wed, 11 Jul 2012 14:13:45 -0400 Subject: MAINT-1175: Properly pass LLRegistry's COMPARATOR to underlying map. Although LLRegistry and LLRegistrySingleton have always defined a COMPARATOR template parameter, it wasn't used for the underlying map. Therefore every type, including any pointer type, was being compared using std::less. This happens to work most of the time -- but is tripping us up now. Pass COMPARATOR to underlying std::map. Fix a couple minor bugs in LLRegistryDefaultComparator (never before used!). Specialize for const char*. Remove CompareTypeID and LLCompareTypeID because we now actively forbid using LLRegistry; remove only known reference (LLWidgetNameRegistry definition). --- indra/llcommon/llinitparam.h | 8 -------- indra/llcommon/llregistry.h | 16 +++++++++++++--- 2 files changed, 13 insertions(+), 11 deletions(-) (limited to 'indra/llcommon') diff --git a/indra/llcommon/llinitparam.h b/indra/llcommon/llinitparam.h index c0170e533b..66c72c2d9f 100644 --- a/indra/llcommon/llinitparam.h +++ b/indra/llcommon/llinitparam.h @@ -212,14 +212,6 @@ namespace LLInitParam public: - struct CompareTypeID - { - bool operator()(const std::type_info* lhs, const std::type_info* rhs) const - { - return lhs->before(*rhs); - } - }; - typedef std::vector > name_stack_t; typedef std::pair name_stack_range_t; typedef std::vector possible_values_t; diff --git a/indra/llcommon/llregistry.h b/indra/llcommon/llregistry.h index 843c169f3d..8eeab59024 100644 --- a/indra/llcommon/llregistry.h +++ b/indra/llcommon/llregistry.h @@ -34,9 +34,19 @@ #include "llsingleton.h" template -class LLRegistryDefaultComparator +struct LLRegistryDefaultComparator { - bool operator()(const T& lhs, const T& rhs) { return lhs < rhs; } + bool operator()(const T& lhs, const T& rhs) const { return lhs < rhs; } +}; + +// comparator for const char* registry keys +template <> +struct LLRegistryDefaultComparator +{ + bool operator()(const char* lhs, const char* rhs) const + { + return strcmp(lhs, rhs) < 0; + } }; template > @@ -62,7 +72,7 @@ public: { friend class LLRegistry; public: - typedef std::map registry_map_t; + typedef std::map registry_map_t; bool add(ref_const_key_t key, ref_const_value_t value) { -- cgit v1.2.3 From 79a171209f41189adfeb1ba8e70c8570d380cdc5 Mon Sep 17 00:00:00 2001 From: Nat Goodspeed Date: Thu, 12 Jul 2012 13:19:26 -0400 Subject: MAINT-1175: Linux viewer built on TC is broken, built on dev box works. Try to diagnose the cause of the misbehavior with a BOOST_STATIC_ASSERT. --- indra/llcommon/llregistry.h | 2 ++ 1 file changed, 2 insertions(+) (limited to 'indra/llcommon') diff --git a/indra/llcommon/llregistry.h b/indra/llcommon/llregistry.h index 8eeab59024..babc1b87aa 100644 --- a/indra/llcommon/llregistry.h +++ b/indra/llcommon/llregistry.h @@ -36,6 +36,8 @@ template struct LLRegistryDefaultComparator { + // It would be Bad if this comparison were used for const char* + BOOST_STATIC_ASSERT(! (boost::is_same::type>::type, char>::value)); bool operator()(const T& lhs, const T& rhs) const { return lhs < rhs; } }; -- cgit v1.2.3 From 55a7bdf8d3f59b0d1973d1ec22d3c8770a077723 Mon Sep 17 00:00:00 2001 From: Nat Goodspeed Date: Mon, 16 Jul 2012 21:05:23 -0400 Subject: MAINT-1175: Pass boost::unordered_map hash/equals functors for char*. boost::unordered_map does NOT, by default, "do the right thing." Give it hash and equality functors that do. --- indra/llcommon/lltypeinfolookup.h | 44 ++++++++++++++++++++++++++++++++++++++- 1 file changed, 43 insertions(+), 1 deletion(-) (limited to 'indra/llcommon') diff --git a/indra/llcommon/lltypeinfolookup.h b/indra/llcommon/lltypeinfolookup.h index 5267e3d2fb..0b6862444e 100644 --- a/indra/llcommon/lltypeinfolookup.h +++ b/indra/llcommon/lltypeinfolookup.h @@ -13,9 +13,48 @@ #define LL_LLTYPEINFOLOOKUP_H #include +#include #include +#include // std::binary_function #include +/** + * The following helper classes are based on the Boost.Unordered documentation: + * http://www.boost.org/doc/libs/1_45_0/doc/html/unordered/hash_equality.html + */ + +/** + * Compute hash for a string passed as const char* + */ +struct const_char_star_hash: public std::unary_function +{ + std::size_t operator()(const char* str) const + { + std::size_t seed = 0; + for ( ; *str; ++str) + { + boost::hash_combine(seed, *str); + } + return seed; + } +}; + +/** + * Compute equality for strings passed as const char* + * + * I (nat) suspect that this is where the default behavior breaks for the + * const char* values returned from std::type_info::name(). If you compare the + * two const char* pointer values, as a naive, unspecialized implementation + * will surely do, they'll compare unequal. + */ +struct const_char_star_equal: public std::binary_function +{ + bool operator()(const char* lhs, const char* rhs) const + { + return strcmp(lhs, rhs) == 0; + } +}; + /** * LLTypeInfoLookup is specifically designed for use cases for which you might * consider std::map. We have several such data @@ -40,7 +79,10 @@ class LLTypeInfoLookup // std::type_info::name() string. This is one of the rare cases in which I // dare use const char* directly, rather than std::string, because I'm // sure that every value returned by std::type_info::name() is static. - typedef boost::unordered_map impl_map_type; + // HOWEVER, specify our own hash + equality functors: naively comparing + // distinct const char* values won't work. + typedef boost::unordered_map impl_map_type; public: typedef VALUE value_type; -- cgit v1.2.3