DEV-41998 - refactor mediadataclient to use a std::list, and re-sort every time an item is pulled off the queue

Review #43

This change refactors mediadataclient to no longer use a PriorityQueue (which sorts only on insertion), but rather just use a std::list which is re-sorted on insert, and also when "popped" (at the time the queue timer goes off).

Also implemented a unit test to make sure re-sorting occurs on timer tick.

3 files changed, 131 insertions, 53 deletions

diff --git a/indra/newview/llmediadataclient.cpp b/indra/newview/llmediadataclient.cpp
index badef4c7ae..924f5a2598 100755
--- a/indra/newview/llmediadataclient.cpp
+++ b/indra/newview/llmediadataclient.cpp
@@ -260,7 +260,8 @@ void LLMediaDataClient::Responder::result(const LLSD& content)
 //
 //////////////////////////////////////////////////////////////////////////////////////
 
-bool LLMediaDataClient::Comparator::operator() (const request_ptr_t &o1, const request_ptr_t &o2) const
+// static
+bool LLMediaDataClient::compareRequests(const request_ptr_t &o1, const request_ptr_t &o2)
 {
 	if (o2.isNull()) return true;
 	if (o1.isNull()) return false;
@@ -277,20 +278,13 @@ bool LLMediaDataClient::Comparator::operator() (const request_ptr_t &o1, const r
 	// 3: One item with an impl, another without: item with impl wins 
 	//	  (XXX is that what we want?)		 
 	// Calculate the scores for each.  
-	F64 o1_score = Comparator::getObjectScore(o1->getObject());
-	F64 o2_score = Comparator::getObjectScore(o2->getObject());
-
-    // XXX Weird: a higher score should go earlier, but by observation I notice
-    // that this causes further-away objects load first.  This is counterintuitive
-    // to the priority_queue Comparator, which states that this function should
-    // return 'true' if o1 should be *before* o2.
-    // In other words, I'd have expected that the following should return
-    // ( o1_score > o2_score).
-	return ( o1_score < o2_score );
+	F64 o1_score = getObjectScore(o1->getObject());
+	F64 o2_score = getObjectScore(o2->getObject());
+	return ( o1_score > o2_score );
 }
-	
+
 // static
-F64 LLMediaDataClient::Comparator::getObjectScore(const LLMediaDataClientObject::ptr_t &obj)
+F64 LLMediaDataClient::getObjectScore(const LLMediaDataClientObject::ptr_t &obj)
 {
 	// *TODO: make this less expensive?
 	F64 dist = obj->getDistanceFromAvatar() + 0.1;	 // avoids div by 0
@@ -310,12 +304,12 @@ F64 LLMediaDataClient::Comparator::getObjectScore(const LLMediaDataClientObject:
 //////////////////////////////////////////////////////////////////////////////////////
 
 // dump the queue
-std::ostream& operator<<(std::ostream &s, const LLMediaDataClient::PriorityQueue &q)
+std::ostream& operator<<(std::ostream &s, const LLMediaDataClient::request_queue_t &q)
 {
 	int i = 0;
-	std::vector<LLMediaDataClient::request_ptr_t>::const_iterator iter = q.c.begin();
-	std::vector<LLMediaDataClient::request_ptr_t>::const_iterator end = q.c.end();
-	while (iter < end)
+	LLMediaDataClient::request_queue_t::const_iterator iter = q.begin();
+	LLMediaDataClient::request_queue_t::const_iterator end = q.end();
+	while (iter != end)
 	{
 		s << "\t" << i << "]: " << (*iter)->getObject()->getID().asString();
 		iter++;
@@ -325,11 +319,11 @@ std::ostream& operator<<(std::ostream &s, const LLMediaDataClient::PriorityQueue
 }
 
 // find the given object in the queue.
-bool LLMediaDataClient::PriorityQueue::find(const LLMediaDataClientObject::ptr_t &obj) const
+bool LLMediaDataClient::find(const LLMediaDataClientObject::ptr_t &obj) const
 {
-	std::vector<LLMediaDataClient::request_ptr_t>::const_iterator iter = c.begin();
-	std::vector<LLMediaDataClient::request_ptr_t>::const_iterator end = c.end();
-	while (iter < end)
+	request_queue_t::const_iterator iter = pRequestQueue->begin();
+	request_queue_t::const_iterator end = pRequestQueue->end();
+	while (iter != end)
 	{
 		if (obj->getID() == (*iter)->getObject()->getID())
 		{
@@ -370,13 +364,17 @@ BOOL LLMediaDataClient::QueueTimer::tick()
 		return TRUE;
 	}
 	
-	LLMediaDataClient::PriorityQueue &queue = *(mMDC->pRequestQueue);
+	request_queue_t &queue = *(mMDC->pRequestQueue);
 
 	if(!queue.empty())
 	{
 		LL_INFOS("LLMediaDataClient") << "QueueTimer::tick() started, queue is:	  " << queue << LL_ENDL;
-	}
 
+		// Re-sort the list every time...
+		// XXX Is this really what we want?
+		queue.sort(LLMediaDataClient::compareRequests);
+	}
+	
 	// quick retry loop for cases where we shouldn't wait for the next timer tick
 	while(true)
 	{
@@ -387,7 +385,7 @@ BOOL LLMediaDataClient::QueueTimer::tick()
 		}
 	
 		// Peel one off of the items from the queue, and execute request
-		request_ptr_t request = queue.top();
+		request_ptr_t request = queue.front();
 		llassert(!request.isNull());
 		const LLMediaDataClientObject *object = (request.isNull()) ? NULL : request->getObject();
 		bool performed_request = false;
@@ -398,7 +396,7 @@ BOOL LLMediaDataClient::QueueTimer::tick()
 		{
 			// This object has been marked dead.  Pop it and move on to the next item in the queue immediately.
 			LL_INFOS("LLMediaDataClient") << "Skipping " << *request << ": object is dead!" << LL_ENDL;
-			queue.pop();
+			queue.pop_front();
 			continue;	// jump back to the start of the quick retry loop
 		}
 
@@ -442,7 +440,7 @@ BOOL LLMediaDataClient::QueueTimer::tick()
 											  << mMDC->mMaxNumRetries << " tries...popping object id " << object->getID() << LL_ENDL; 
 				// XXX Should we bring up a warning dialog??
 			}
-			queue.pop();
+			queue.pop_front();
 		}
 		else {
 			request->incRetryCount();
@@ -451,7 +449,7 @@ BOOL LLMediaDataClient::QueueTimer::tick()
  		// end of quick retry loop -- any cases where we want to loop will use 'continue' to jump back to the start.
  		break;
 	}  
-	
+
 	LL_DEBUGS("LLMediaDataClient") << "QueueTimer::tick() finished, queue is now: " << (*(mMDC->pRequestQueue)) << LL_ENDL;
 
 	return queue.empty();
@@ -488,7 +486,9 @@ void LLMediaDataClient::enqueue(const Request *request)
 	LL_INFOS("LLMediaDataClient") << "Queuing request for " << *request << LL_ENDL;
 	// Push the request on the priority queue
 	// Sadly, we have to const-cast because items put into the queue are not const
-	pRequestQueue->push(const_cast<LLMediaDataClient::Request*>(request));
+	pRequestQueue->push_back(const_cast<LLMediaDataClient::Request*>(request));
+	// sort the list
+	pRequestQueue->sort(LLMediaDataClient::compareRequests);
 	LL_DEBUGS("LLMediaDataClient") << "Queue:" << (*pRequestQueue) << LL_ENDL;
 	// Start the timer if not already running
 	startQueueTimer();
@@ -508,7 +508,7 @@ LLMediaDataClient::LLMediaDataClient(F32 queue_timer_delay,
 	  mMaxNumRetries(max_retries),
 	  mQueueTimerIsRunning(false)
 {
-	pRequestQueue = new PriorityQueue();
+	pRequestQueue = new request_queue_t();
 }
 
 LLMediaDataClient::~LLMediaDataClient()
@@ -529,7 +529,7 @@ bool LLMediaDataClient::isEmpty() const
 
 bool LLMediaDataClient::isInQueue(const LLMediaDataClientObject::ptr_t &object) const
 {
-	return (NULL == pRequestQueue) ? false : pRequestQueue->find(object);
+	return (NULL == pRequestQueue) ? false : find(object);
 }
 
 //////////////////////////////////////////////////////////////////////////////////////
diff --git a/indra/newview/llmediadataclient.h b/indra/newview/llmediadataclient.h
index d5dd050111..812e9cbdec 100755
--- a/indra/newview/llmediadataclient.h
+++ b/indra/newview/llmediadataclient.h
@@ -195,30 +195,14 @@ protected:
 	
 private:
 	
-	// Comparator for PriorityQueue
-	class Comparator
-	{
-	public:
-		bool operator() (const request_ptr_t &o1, const request_ptr_t &o2) const;
-	private:
-		static F64 getObjectScore(const LLMediaDataClientObject::ptr_t &obj);
-	};
+	typedef std::list<request_ptr_t> request_queue_t;
 	
-    // PriorityQueue
-	class PriorityQueue : public std::priority_queue<
-		request_ptr_t, 
-		std::vector<request_ptr_t>, 
-		Comparator >
-	{
-	public:
-		// Return whether the given object is in the queue
-		bool find(const LLMediaDataClientObject::ptr_t &obj) const;
-		
-		friend std::ostream& operator<<(std::ostream &s, const PriorityQueue &q);
-	};
+	// Comparator for sorting
+	static bool compareRequests(const request_ptr_t &o1, const request_ptr_t &o2);
+	static F64 getObjectScore(const LLMediaDataClientObject::ptr_t &obj);
     
 	friend std::ostream& operator<<(std::ostream &s, const Request &q);
-    friend std::ostream& operator<<(std::ostream &s, const PriorityQueue &q);
+	friend std::ostream& operator<<(std::ostream &s, const request_queue_t &q);
 
 	class QueueTimer : public LLEventTimer
 	{
@@ -232,6 +216,9 @@ private:
 		LLPointer<LLMediaDataClient> mMDC;
 	};
 
+	// Return whether the given object is in the queue
+	bool find(const LLMediaDataClientObject::ptr_t &obj) const;
+	
 	void startQueueTimer();
 	void stopQueueTimer();
 	void setIsRunning(bool val) { mQueueTimerIsRunning = val; }
@@ -242,7 +229,7 @@ private:
 	
 	bool mQueueTimerIsRunning;
 	
-	PriorityQueue *pRequestQueue;
+	request_queue_t *pRequestQueue;
 };
 
 
diff --git a/indra/newview/tests/llmediadataclient_test.cpp b/indra/newview/tests/llmediadataclient_test.cpp
index 217889c390..6ff2c9446e 100644
--- a/indra/newview/tests/llmediadataclient_test.cpp
+++ b/indra/newview/tests/llmediadataclient_test.cpp
@@ -191,6 +191,12 @@ public:
 	virtual bool isDead() const
 		{ return mDead; }
 
+	void setDistanceFromAvatar(F64 val)
+		{ mRep["distance"] = val; }
+	
+	void setTotalMediaInterest(F64 val)
+		{ mRep["interest"] = val; }
+
 	int getNumBounceBacks() const
 		{ return mNumBounceBacks; }
 	
@@ -593,6 +599,91 @@ namespace tut
 
 			ensure("queue empty", mdc->isEmpty());
 		}
-		
+		ensure("refcount of o1", o1->getNumRefs(), 1);
+		ensure("refcount of o2", o2->getNumRefs(), 1);
+		ensure("refcount of o3", o3->getNumRefs(), 1);
+		ensure("refcount of o4", o4->getNumRefs(), 1);
+
 	}
+	
+	//////////////////////////////////////////////////////////////////////////////////////////
+
+    template<> template<>
+    void mediadataclient_object_t::test<9>()
+    {
+		//
+		// Test queue re-ordering
+		//
+		LOG_TEST(9);
+		
+		LLMediaDataClientObject::ptr_t o1 = new LLMediaDataClientObjectTest(_DATA(VALID_OBJECT_ID_1,"10.0","1.0"));
+		LLMediaDataClientObject::ptr_t o2 = new LLMediaDataClientObjectTest(_DATA(VALID_OBJECT_ID_2,"20.0","1.0"));
+		LLMediaDataClientObject::ptr_t o3 = new LLMediaDataClientObjectTest(_DATA(VALID_OBJECT_ID_3,"30.0","1.0"));
+		LLMediaDataClientObject::ptr_t o4 = new LLMediaDataClientObjectTest(_DATA(VALID_OBJECT_ID_4,"40.0","1.0"));
+		{
+			LLPointer<LLObjectMediaDataClient> mdc = new LLObjectMediaDataClient(NO_PERIOD,NO_PERIOD);
+			
+			// queue up all 4 objects.  They should now be in the queue in
+			// order 1 through 4, with 4 being at the front of the queue
+			mdc->fetchMedia(o1);
+			mdc->fetchMedia(o2);
+			mdc->fetchMedia(o3);
+			mdc->fetchMedia(o4);
+			
+			int test_num = 0;
+			
+			ensure(STR(test_num) + ". is in queue 1", mdc->isInQueue(o1));
+			ensure(STR(test_num) + ". is in queue 2", mdc->isInQueue(o2));
+			ensure(STR(test_num) + ". is in queue 3", mdc->isInQueue(o3));
+			ensure(STR(test_num) + ". is in queue 4", mdc->isInQueue(o4));
+			ensure(STR(test_num) + ". post records", gPostRecords->size(), 0);
+			
+			::pump_timers();
+			++test_num;
+			
+			// The first tick should remove the first one 
+			ensure(STR(test_num) + ". is not in queue 1", !mdc->isInQueue(o1));
+			ensure(STR(test_num) + ". is in queue 2", mdc->isInQueue(o2));
+			ensure(STR(test_num) + ". is in queue 3", mdc->isInQueue(o3));
+			ensure(STR(test_num) + ". is in queue 4", mdc->isInQueue(o4));
+			ensure(STR(test_num) + ". post records", gPostRecords->size(), 1);
+			
+			// Now, pretend that object 4 moved relative to the avatar such
+			// that it is now closest
+			static_cast<LLMediaDataClientObjectTest*>(
+				static_cast<LLMediaDataClientObject*>(o4))->setDistanceFromAvatar(5.0);
+			
+			::pump_timers();
+			++test_num;
+			
+			// The second tick should still pick off item 2, but then re-sort
+			// have picked off object 4
+			ensure(STR(test_num) + ". is in queue 2", mdc->isInQueue(o2));
+			ensure(STR(test_num) + ". is in queue 3", mdc->isInQueue(o3));
+			ensure(STR(test_num) + ". is not in queue 4", !mdc->isInQueue(o4));
+			ensure(STR(test_num) + ". post records", gPostRecords->size(), 2);
+
+			::pump_timers();
+			++test_num;
+			
+			// The third tick should pick off object 2
+			ensure(STR(test_num) + ". is not in queue 2", !mdc->isInQueue(o2));
+			ensure(STR(test_num) + ". is in queue 3", mdc->isInQueue(o3));
+			ensure(STR(test_num) + ". post records", gPostRecords->size(), 3);
+
+			// The fourth tick should pick off object 3
+			::pump_timers();
+			++test_num;
+
+			ensure(STR(test_num) + ". is not in queue 3", !mdc->isInQueue(o3));
+			ensure(STR(test_num) + ". post records", gPostRecords->size(), 4);
+
+			ensure("queue empty", mdc->isEmpty());
+		}
+		ensure("refcount of o1", o1->getNumRefs(), 1);
+		ensure("refcount of o2", o2->getNumRefs(), 1);
+		ensure("refcount of o3", o3->getNumRefs(), 1);
+		ensure("refcount of o4", o4->getNumRefs(), 1);
+    }
+	
 }