reapply 52b6c9168974: MAINT-646 Factor std::set out of lloctree

4 files changed, 109 insertions, 37 deletions

diff --git a/indra/llmath/lloctree.h b/indra/llmath/lloctree.h
index 6c7744cdf1..a7e176fd51 100644
--- a/indra/llmath/lloctree.h
+++ b/indra/llmath/lloctree.h
@@ -79,9 +79,9 @@ public:
 
 	typedef LLOctreeTraveler<T>									oct_traveler;
 	typedef LLTreeTraveler<T>									tree_traveler;
-	typedef typename std::set<LLPointer<T> >					element_list;
-	typedef typename element_list::iterator						element_iter;
-	typedef typename element_list::const_iterator	const_element_iter;
+	typedef LLPointer<T>*										element_list;
+	typedef LLPointer<T>*										element_iter;
+	typedef const LLPointer<T>*									const_element_iter;
 	typedef typename std::vector<LLTreeListener<T>*>::iterator	tree_listener_iter;
 	typedef typename std::vector<LLOctreeNode<T>* >				child_list;
 	typedef LLTreeNode<T>		BaseType;
@@ -105,6 +105,9 @@ public:
 	:	mParent((oct_node*)parent), 
 		mOctant(octant) 
 	{ 
+		mData = NULL;
+		mDataEnd = NULL;
+
 		mCenter = center;
 		mSize = size;
 
@@ -123,6 +126,16 @@ public:
 	{ 
 		BaseType::destroyListeners(); 
 		
+		for (U32 i = 0; i < mElementCount; ++i)
+		{
+			mData[i]->setBinIndex(-1);
+			mData[i] = NULL;
+		}
+
+		free(mData);
+		mData = NULL;
+		mDataEnd = NULL;
+
 		for (U32 i = 0; i < getChildCount(); i++)
 		{
 			delete getChild(i);
@@ -222,9 +235,14 @@ public:
 	virtual bool isLeaf() const						{ return mChild.empty(); }
 	
 	U32 getElementCount() const						{ return mElementCount; }
+	bool isEmpty() const							{ return mElementCount == 0; }
 	element_list& getData()							{ return mData; }
 	const element_list& getData() const				{ return mData; }
-	
+	element_iter getDataBegin()						{ return mData; }
+	element_iter getDataEnd()						{ return mDataEnd; }
+	const_element_iter getDataBegin() const			{ return mData; }
+	const_element_iter getDataEnd() const			{ return mDataEnd; }
+		
 	U32 getChildCount()	const						{ return mChildCount; }
 	oct_node* getChild(U32 index)					{ return mChild[index]; }
 	const oct_node* getChild(U32 index) const		{ return mChild[index]; }
@@ -289,7 +307,7 @@ public:
 	
 	virtual bool insert(T* data)
 	{
-		if (data == NULL)
+		if (data == NULL || data->getBinIndex() != -1)
 		{
 			OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE BRANCH !!!" << llendl;
 			return false;
@@ -302,13 +320,16 @@ public:
 			if ((getElementCount() < gOctreeMaxCapacity && contains(data->getBinRadius()) ||
 				(data->getBinRadius() > getSize()[0] &&	parent && parent->getElementCount() >= gOctreeMaxCapacity))) 
 			{ //it belongs here
-				//if this is a redundant insertion, error out (should never happen)
-				llassert(mData.find(data) == mData.end());
+				mElementCount++;
+				mData = (element_list) realloc(mData, sizeof(LLPointer<T>)*mElementCount);
 
-				mData.insert(data);
-				BaseType::insert(data);
+				//avoid unref on uninitialized memory
+				memset(mData+mElementCount-1, 0, sizeof(LLPointer<T>));
 
-				mElementCount = mData.size();
+				mData[mElementCount-1] = data;
+				mDataEnd = mData + mElementCount;
+				data->setBinIndex(mElementCount-1);
+				BaseType::insert(data);
 				return true;
 			}
 			else
@@ -342,10 +363,16 @@ public:
 
 				if( lt == 0x7 )
 				{
-					mData.insert(data);
-					BaseType::insert(data);
+					mElementCount++;
+					mData = (element_list) realloc(mData, sizeof(LLPointer<T>)*mElementCount);
+
+					//avoid unref on uninitialized memory
+					memset(mData+mElementCount-1, 0, sizeof(LLPointer<T>));
 
-					mElementCount = mData.size();
+					mData[mElementCount-1] = data;
+					mDataEnd = mData + mElementCount;
+					data->setBinIndex(mElementCount-1);
+					BaseType::insert(data);
 					return true;
 				}
 
@@ -394,23 +421,59 @@ public:
 		return false;
 	}
 
+	void _remove(T* data, S32 i)
+	{ //precondition -- mElementCount > 0, idx is in range [0, mElementCount)
+
+		mElementCount--;
+		data->setBinIndex(-1); 
+		
+		if (mElementCount > 0)
+		{
+			if (mElementCount != i)
+			{
+				mData[i] = mData[mElementCount]; //might unref data, do not access data after this point
+				mData[i]->setBinIndex(i);
+			}
+
+			mData[mElementCount] = NULL; //needed for unref
+			mData = (element_list) realloc(mData, sizeof(LLPointer<T>)*mElementCount);
+			mDataEnd = mData+mElementCount;
+		}
+		else
+		{
+			mData[0] = NULL; //needed for unref
+			free(mData);
+			mData = NULL;
+			mDataEnd = NULL;
+		}
+
+		notifyRemoval(data);
+		checkAlive();
+	}
+
 	bool remove(T* data)
 	{
-		if (mData.find(data) != mData.end())
-		{	//we have data
-			mData.erase(data);
-			mElementCount = mData.size();
-			notifyRemoval(data);
-			checkAlive();
-			return true;
-		}
-		else if (isInside(data))
+		S32 i = data->getBinIndex();
+
+		if (i >= 0 && i < mElementCount)
+		{
+			if (mData[i] == data)
+			{ //found it
+				_remove(data, i);
+				llassert(data->getBinIndex() == -1);
+				return true;
+			}
+		}
+		
+		if (isInside(data))
 		{
 			oct_node* dest = getNodeAt(data);
 
 			if (dest != this)
 			{
-				return dest->remove(data);
+				bool ret = dest->remove(data);
+				llassert(data->getBinIndex() == -1);
+				return ret;
 			}
 		}
 
@@ -429,19 +492,20 @@ public:
 		//node is now root
 		llwarns << "!!! OCTREE REMOVING FACE BY ADDRESS, SEVERE PERFORMANCE PENALTY |||" << llendl;
 		node->removeByAddress(data);
+		llassert(data->getBinIndex() == -1);
 		return true;
 	}
 
 	void removeByAddress(T* data)
 	{
-        if (mData.find(data) != mData.end())
+        for (U32 i = 0; i < mElementCount; ++i)
 		{
-			mData.erase(data);
-			mElementCount = mData.size();
-			notifyRemoval(data);
-			llwarns << "FOUND!" << llendl;
-			checkAlive();
-			return;
+			if (mData[i] == data)
+			{ //we have data
+				_remove(data, i);
+				llwarns << "FOUND!" << llendl;
+				return;
+			}
 		}
 		
 		for (U32 i = 0; i < getChildCount(); i++)
@@ -606,6 +670,7 @@ protected:
 	U32 mChildCount;
 
 	element_list mData;
+	element_iter mDataEnd;
 	U32 mElementCount;
 		
 }; 
diff --git a/indra/llmath/llvolume.cpp b/indra/llmath/llvolume.cpp
index ea09a3afe7..919079fa88 100644
--- a/indra/llmath/llvolume.cpp
+++ b/indra/llmath/llvolume.cpp
@@ -317,16 +317,16 @@ public:
 		LLVector4a& min = node->mExtents[0];
 		LLVector4a& max = node->mExtents[1];
 
-		if (!branch->getData().empty())
+		if (!branch->isEmpty())
 		{ //node has data, find AABB that binds data set
-			const LLVolumeTriangle* tri = *(branch->getData().begin());
+			const LLVolumeTriangle* tri = *(branch->getDataBegin());
 			
 			//initialize min/max to first available vertex
 			min = *(tri->mV[0]);
 			max = *(tri->mV[0]);
 			
 			for (LLOctreeNode<LLVolumeTriangle>::const_element_iter iter = 
-				branch->getData().begin(); iter != branch->getData().end(); ++iter)
+				branch->getDataBegin(); iter != branch->getDataEnd(); ++iter)
 			{ //for each triangle in node
 
 				//stretch by triangles in node
diff --git a/indra/llmath/llvolumeoctree.cpp b/indra/llmath/llvolumeoctree.cpp
index b5a935c2b5..cc83cb7235 100644
--- a/indra/llmath/llvolumeoctree.cpp
+++ b/indra/llmath/llvolumeoctree.cpp
@@ -131,7 +131,7 @@ void LLOctreeTriangleRayIntersect::traverse(const LLOctreeNode<LLVolumeTriangle>
 void LLOctreeTriangleRayIntersect::visit(const LLOctreeNode<LLVolumeTriangle>* node)
 {
 	for (LLOctreeNode<LLVolumeTriangle>::const_element_iter iter = 
-			node->getData().begin(); iter != node->getData().end(); ++iter)
+			node->getDataBegin(); iter != node->getDataEnd(); ++iter)
 	{
 		const LLVolumeTriangle* tri = *iter;
 
@@ -236,8 +236,8 @@ void LLVolumeOctreeValidate::visit(const LLOctreeNode<LLVolumeTriangle>* branch)
 	}
 
 	//children fit, check data
-	for (LLOctreeNode<LLVolumeTriangle>::const_element_iter iter = branch->getData().begin(); 
-			iter != branch->getData().end(); ++iter)
+	for (LLOctreeNode<LLVolumeTriangle>::const_element_iter iter = branch->getDataBegin(); 
+			iter != branch->getDataEnd(); ++iter)
 	{
 		const LLVolumeTriangle* tri = *iter;
 
diff --git a/indra/llmath/llvolumeoctree.h b/indra/llmath/llvolumeoctree.h
index dac97b14b5..9ae34a0c4e 100644
--- a/indra/llmath/llvolumeoctree.h
+++ b/indra/llmath/llvolumeoctree.h
@@ -49,7 +49,7 @@ public:
 
 	LLVolumeTriangle()
 	{
-		
+		mBinIndex = -1;	
 	}
 
 	LLVolumeTriangle(const LLVolumeTriangle& rhs)
@@ -74,9 +74,16 @@ public:
 	U16 mIndex[3];
 
 	F32 mRadius;
+	mutable S32 mBinIndex;
+
 
 	virtual const LLVector4a& getPositionGroup() const;
 	virtual const F32& getBinRadius() const;
+	
+	S32 getBinIndex() const { return mBinIndex; }
+	void setBinIndex(S32 idx) const { mBinIndex = idx; }
+
+
 };
 
 class LLVolumeOctreeListener : public LLOctreeListener<LLVolumeTriangle>