Enhance LLInstanceTracker variants to be more uniform.

For both the (so far unused) generic KEY form and the KEY = T* form, provide
key_iter, beginKeys(), endKeys().
Change instance_iter so that when dereferenced, it gives you a T& rather than
a T*, to be more harmonious with a typical STL container. (You parameterize
LLInstanceTracker with T, not with T*.)
Fix existing usage in llfasttimer.cpp and lltimer.cpp to agree.
For the KEY = T* specialization, add T* getInstance(T*) so client isn't forced
to know which variant was used.
Add unit tests for uniformity of public operations on both variants.

4 files changed, 231 insertions, 32 deletions

diff --git a/indra/llcommon/CMakeLists.txt b/indra/llcommon/CMakeLists.txt
index f785698612..3a36b8430c 100644
--- a/indra/llcommon/CMakeLists.txt
+++ b/indra/llcommon/CMakeLists.txt
@@ -305,6 +305,7 @@ LL_ADD_INTEGRATION_TEST(lldate "" "${test_libs}")
 LL_ADD_INTEGRATION_TEST(lldependencies "" "${test_libs}")
 LL_ADD_INTEGRATION_TEST(llerror "" "${test_libs}")
 LL_ADD_INTEGRATION_TEST(llframetimer "" "${test_libs}")
+LL_ADD_INTEGRATION_TEST(llinstancetracker "" "${test_libs}")
 LL_ADD_INTEGRATION_TEST(lllazy "" "${test_libs}")
 LL_ADD_INTEGRATION_TEST(llrand "" "${test_libs}")
 LL_ADD_INTEGRATION_TEST(llsdserialize "" "${test_libs}")
diff --git a/indra/llcommon/llinstancetracker.h b/indra/llcommon/llinstancetracker.h
index ea50acbbc5..039d68faef 100644
--- a/indra/llcommon/llinstancetracker.h
+++ b/indra/llcommon/llinstancetracker.h
@@ -38,22 +38,53 @@
 
 #include "string_table.h"
 #include <boost/utility.hpp>
-
-// This mix-in class adds support for tracking all instances of the specified class parameter T
-// The (optional) key associates a value of type KEY with a given instance of T, for quick lookup
-// If KEY is not provided, then instances are stored in a simple set
-// *NOTE: see explicit specialization below for default KEY==T* case
+#include <boost/function.hpp>
+#include <boost/bind.hpp>
+#include <boost/iterator/transform_iterator.hpp>
+#include <boost/iterator/indirect_iterator.hpp>
+
+/// This mix-in class adds support for tracking all instances of the specified class parameter T
+/// The (optional) key associates a value of type KEY with a given instance of T, for quick lookup
+/// If KEY is not provided, then instances are stored in a simple set
+/// @NOTE: see explicit specialization below for default KEY==T* case
 template<typename T, typename KEY = T*>
 class LLInstanceTracker : boost::noncopyable
 {
+	typedef typename std::map<KEY, T*> InstanceMap;
+	typedef boost::function<const KEY&(typename InstanceMap::value_type&)> KeyGetter;
+	typedef boost::function<T*(typename InstanceMap::value_type&)> InstancePtrGetter;
 public:
-	typedef typename std::map<KEY, T*>::iterator instance_iter;
-	typedef typename std::map<KEY, T*>::const_iterator instance_const_iter;
-
-	static T* getInstance(const KEY& k) { instance_iter found = getMap().find(k); return (found == getMap().end()) ? NULL : found->second; }
+	/// Dereferencing key_iter gives you a const KEY&
+	typedef boost::transform_iterator<KeyGetter, typename InstanceMap::iterator> key_iter;
+	/// Dereferencing instance_iter gives you a T&
+	typedef boost::indirect_iterator< boost::transform_iterator<InstancePtrGetter, typename InstanceMap::iterator> > instance_iter;
+
+	static T* getInstance(const KEY& k)
+	{
+		typename InstanceMap::const_iterator found = getMap().find(k);
+		return (found == getMap().end()) ? NULL : found->second;
+	}
 
-	static instance_iter beginInstances() { return getMap().begin(); }
-	static instance_iter endInstances() { return getMap().end(); }
+	static key_iter beginKeys()
+	{
+		return boost::make_transform_iterator(getMap().begin(),
+											  boost::bind(&InstanceMap::value_type::first, _1));
+	}
+	static key_iter endKeys()
+	{
+		return boost::make_transform_iterator(getMap().end(),
+											  boost::bind(&InstanceMap::value_type::first, _1));
+	}
+	static instance_iter beginInstances()
+	{
+		return instance_iter(boost::make_transform_iterator(getMap().begin(),
+															boost::bind(&InstanceMap::value_type::second, _1)));
+	}
+	static instance_iter endInstances()
+	{
+		return instance_iter(boost::make_transform_iterator(getMap().end(),
+															boost::bind(&InstanceMap::value_type::second, _1)));
+	}
 	static S32 instanceCount() { return getMap().size(); }
 protected:
 	LLInstanceTracker(KEY key) { add(key); }
@@ -69,11 +100,11 @@ private:
 	}
 	void remove() { getMap().erase(mKey); }
 
-    static std::map<KEY, T*>& getMap()
+    static InstanceMap& getMap()
     {
         if (! sInstances)
         {
-            sInstances = new std::map<KEY, T*>;
+            sInstances = new InstanceMap;
         }
         return *sInstances;
     }
@@ -81,20 +112,27 @@ private:
 private:
 
 	KEY mKey;
-	static std::map<KEY, T*>* sInstances;
+	static InstanceMap* sInstances;
 };
 
-// explicit specialization for default case where KEY is T*
-// use a simple std::set<T*>
+/// explicit specialization for default case where KEY is T*
+/// use a simple std::set<T*>
 template<typename T>
 class LLInstanceTracker<T, T*>
 {
+	typedef typename std::set<T*> InstanceSet;
 public:
-	typedef typename std::set<T*>::iterator instance_iter;
-	typedef typename std::set<T*>::const_iterator instance_const_iter;
-
-	static instance_iter beginInstances() { return getSet().begin(); }
-	static instance_iter endInstances() { return getSet().end(); }
+	/// Dereferencing key_iter gives you a T* (since T* is the key)
+	typedef typename InstanceSet::iterator key_iter;
+	/// Dereferencing instance_iter gives you a T&
+	typedef boost::indirect_iterator<key_iter> instance_iter;
+
+	/// for completeness of analogy with the generic implementation
+	static T* getInstance(T* k) { return k; }
+	static key_iter beginKeys() { return getSet().begin(); }
+	static key_iter endKeys()   { return getSet().end(); }
+	static instance_iter beginInstances() { return instance_iter(getSet().begin()); }
+	static instance_iter endInstances()   { return instance_iter(getSet().end()); }
 	static S32 instanceCount() { return getSet().size(); }
 
 protected:
@@ -103,19 +141,19 @@ protected:
 
 	LLInstanceTracker(const LLInstanceTracker& other) { getSet().insert(static_cast<T*>(this)); }
 
-    static std::set<T*>& getSet()   // called after getReady() but before go()
+    static InstanceSet& getSet()   // called after getReady() but before go()
     {
         if (! sInstances)
         {
-            sInstances = new std::set<T*>;
+            sInstances = new InstanceSet;
         }
         return *sInstances;
     }
 
-	static std::set<T*>* sInstances;
+	static InstanceSet* sInstances;
 };
 
-template <typename T, typename KEY> std::map<KEY, T*>* LLInstanceTracker<T, KEY>::sInstances = NULL;
-template <typename T> std::set<T*>* LLInstanceTracker<T, T*>::sInstances = NULL;
+template <typename T, typename KEY> typename LLInstanceTracker<T, KEY>::InstanceMap* LLInstanceTracker<T, KEY>::sInstances = NULL;
+template <typename T> typename LLInstanceTracker<T, T*>::InstanceSet* LLInstanceTracker<T, T*>::sInstances = NULL;
 
 #endif
diff --git a/indra/llcommon/lltimer.cpp b/indra/llcommon/lltimer.cpp
index ea5b0c03ef..ef3e8dbc94 100644
--- a/indra/llcommon/lltimer.cpp
+++ b/indra/llcommon/lltimer.cpp
@@ -583,13 +583,13 @@ void LLEventTimer::updateClass()
 	std::list<LLEventTimer*> completed_timers;
 	for (instance_iter iter = beginInstances(); iter != endInstances(); ) 
 	{
-		LLEventTimer* timer = *iter++;
-		F32 et = timer->mEventTimer.getElapsedTimeF32();
-		if (timer->mEventTimer.getStarted() && et > timer->mPeriod) {
-			timer->mEventTimer.reset();
-			if ( timer->tick() )
+		LLEventTimer& timer = *iter++;
+		F32 et = timer.mEventTimer.getElapsedTimeF32();
+		if (timer.mEventTimer.getStarted() && et > timer.mPeriod) {
+			timer.mEventTimer.reset();
+			if ( timer.tick() )
 			{
-				completed_timers.push_back( timer );
+				completed_timers.push_back( &timer );
 			}
 		}
 	}
diff --git a/indra/llcommon/tests/llinstancetracker_test.cpp b/indra/llcommon/tests/llinstancetracker_test.cpp
new file mode 100644
index 0000000000..7415f2d33b
--- /dev/null
+++ b/indra/llcommon/tests/llinstancetracker_test.cpp
@@ -0,0 +1,160 @@
+/**
+ * @file   llinstancetracker_test.cpp
+ * @author Nat Goodspeed
+ * @date   2009-11-10
+ * @brief  Test for llinstancetracker.
+ * 
+ * $LicenseInfo:firstyear=2009&license=viewergpl$
+ * Copyright (c) 2009, Linden Research, Inc.
+ * $/LicenseInfo$
+ */
+
+// Precompiled header
+#include "linden_common.h"
+// associated header
+#include "llinstancetracker.h"
+// STL headers
+#include <string>
+#include <vector>
+#include <set>
+#include <algorithm>                // std::sort()
+// std headers
+// external library headers
+#include <boost/scoped_ptr.hpp>
+// other Linden headers
+#include "../test/lltut.h"
+
+struct Keyed: public LLInstanceTracker<Keyed, std::string>
+{
+    Keyed(const std::string& name):
+        LLInstanceTracker<Keyed, std::string>(name),
+        mName(name)
+    {}
+    std::string mName;
+};
+
+struct Unkeyed: public LLInstanceTracker<Unkeyed>
+{
+};
+
+/*****************************************************************************
+*   TUT
+*****************************************************************************/
+namespace tut
+{
+    struct llinstancetracker_data
+    {
+    };
+    typedef test_group<llinstancetracker_data> llinstancetracker_group;
+    typedef llinstancetracker_group::object object;
+    llinstancetracker_group llinstancetrackergrp("llinstancetracker");
+
+    template<> template<>
+    void object::test<1>()
+    {
+        ensure_equals(Keyed::instanceCount(), 0);
+        {
+            Keyed one("one");
+            ensure_equals(Keyed::instanceCount(), 1);
+            Keyed* found = Keyed::getInstance("one");
+            ensure("couldn't find stack Keyed", found);
+            ensure_equals("found wrong Keyed instance", found, &one);
+            {
+                boost::scoped_ptr<Keyed> two(new Keyed("two"));
+                ensure_equals(Keyed::instanceCount(), 2);
+                Keyed* found = Keyed::getInstance("two");
+                ensure("couldn't find heap Keyed", found);
+                ensure_equals("found wrong Keyed instance", found, two.get());
+            }
+            ensure_equals(Keyed::instanceCount(), 1);
+        }
+        Keyed* found = Keyed::getInstance("one");
+        ensure("Keyed key lives too long", ! found);
+        ensure_equals(Keyed::instanceCount(), 0);
+    }
+
+    template<> template<>
+    void object::test<2>()
+    {
+        ensure_equals(Unkeyed::instanceCount(), 0);
+        {
+            Unkeyed one;
+            ensure_equals(Unkeyed::instanceCount(), 1);
+            Unkeyed* found = Unkeyed::getInstance(&one);
+            ensure_equals(found, &one);
+            {
+                boost::scoped_ptr<Unkeyed> two(new Unkeyed);
+                ensure_equals(Unkeyed::instanceCount(), 2);
+                Unkeyed* found = Unkeyed::getInstance(two.get());
+                ensure_equals(found, two.get());
+            }
+            ensure_equals(Unkeyed::instanceCount(), 1);
+        }
+        ensure_equals(Unkeyed::instanceCount(), 0);
+    }
+
+    template<> template<>
+    void object::test<3>()
+    {
+        Keyed one("one"), two("two"), three("three");
+        // We don't want to rely on the underlying container delivering keys
+        // in any particular order. That allows us the flexibility to
+        // reimplement LLInstanceTracker using, say, a hash map instead of a
+        // std::map. We DO insist that every key appear exactly once.
+        typedef std::vector<std::string> StringVector;
+        StringVector keys(Keyed::beginKeys(), Keyed::endKeys());
+        std::sort(keys.begin(), keys.end());
+        StringVector::const_iterator ki(keys.begin());
+        ensure_equals(*ki++, "one");
+        ensure_equals(*ki++, "three");
+        ensure_equals(*ki++, "two");
+        // Use ensure() here because ensure_equals would want to display
+        // mismatched values, and frankly that wouldn't help much.
+        ensure("didn't reach end", ki == keys.end());
+
+        // Use a somewhat different approach to order independence with
+        // beginInstances(): explicitly capture the instances we know in a
+        // set, and delete them as we iterate through.
+        typedef std::set<Keyed*> InstanceSet;
+        InstanceSet instances;
+        instances.insert(&one);
+        instances.insert(&two);
+        instances.insert(&three);
+        for (Keyed::instance_iter ii(Keyed::beginInstances()), iend(Keyed::endInstances());
+             ii != iend; ++ii)
+        {
+            Keyed& ref = *ii;
+            ensure_equals("spurious instance", instances.erase(&ref), 1);
+        }
+        ensure_equals("unreported instance", instances.size(), 0);
+    }
+
+    template<> template<>
+    void object::test<4>()
+    {
+        Unkeyed one, two, three;
+        typedef std::set<Unkeyed*> KeySet;
+        KeySet keys;
+        keys.insert(&one);
+        keys.insert(&two);
+        keys.insert(&three);
+        for (Unkeyed::key_iter ki(Unkeyed::beginKeys()), kend(Unkeyed::endKeys());
+             ki != kend; ++ki)
+        {
+            ensure_equals("spurious key", keys.erase(*ki), 1);
+        }
+        ensure_equals("unreported key", keys.size(), 0);
+
+        KeySet instances;
+        instances.insert(&one);
+        instances.insert(&two);
+        instances.insert(&three);
+        for (Unkeyed::instance_iter ii(Unkeyed::beginInstances()), iend(Unkeyed::endInstances());
+             ii != iend; ++ii)
+        {
+            Unkeyed& ref = *ii;
+            ensure_equals("spurious instance", instances.erase(&ref), 1);
+        }
+        ensure_equals("unreported instance", instances.size(), 0);
+    }
+} // namespace tut