Backing out the changes contributing to DRTVWR-167 and DRTVWR-179 from the repository.

1 files changed, 39 insertions, 108 deletions

diff --git a/indra/llmath/lloctree.h b/indra/llmath/lloctree.h
index c3f6f7de2a..1b11e83b4a 100644
--- a/indra/llmath/lloctree.h
+++ b/indra/llmath/lloctree.h
@@ -31,6 +31,7 @@
 #include "v3math.h"
 #include "llvector4a.h"
 #include <vector>
+#include <set>
 
 #define OCT_ERRS LL_WARNS("OctreeErrors")
 
@@ -78,18 +79,16 @@ public:
 
 	typedef LLOctreeTraveler<T>									oct_traveler;
 	typedef LLTreeTraveler<T>									tree_traveler;
-	typedef LLPointer<T>*										element_list;
-	typedef LLPointer<T>*										element_iter;
-	typedef const LLPointer<T>*									const_element_iter;
+	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 typename std::vector<LLTreeListener<T>*>::iterator	tree_listener_iter;
-	typedef LLOctreeNode<T>**									child_list;
-	typedef LLOctreeNode<T>**									child_iter;
-
+	typedef typename std::vector<LLOctreeNode<T>* >				child_list;
 	typedef LLTreeNode<T>		BaseType;
 	typedef LLOctreeNode<T>		oct_node;
 	typedef LLOctreeListener<T>	oct_listener;
 
-	void* operator new(size_t size)
+	/*void* operator new(size_t size)
 	{
 		return ll_aligned_malloc_16(size);
 	}
@@ -97,7 +96,7 @@ public:
 	void operator delete(void* ptr)
 	{
 		ll_aligned_free_16(ptr);
-	}
+	}*/
 
 	LLOctreeNode(	const LLVector4a& center, 
 					const LLVector4a& size, 
@@ -106,9 +105,6 @@ public:
 	:	mParent((oct_node*)parent), 
 		mOctant(octant) 
 	{ 
-		mData = NULL;
-		mDataEnd = NULL;
-
 		mCenter = center;
 		mSize = size;
 
@@ -127,16 +123,6 @@ 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);
@@ -233,17 +219,12 @@ public:
 	}
 
 	void accept(oct_traveler* visitor)				{ visitor->visit(this); }
-	virtual bool isLeaf() const						{ return mChildCount == 0; }
+	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]; }
@@ -308,7 +289,7 @@ public:
 	
 	virtual bool insert(T* data)
 	{
-		if (data == NULL || data->getBinIndex() != -1)
+		if (data == NULL)
 		{
 			OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE BRANCH !!!" << llendl;
 			return false;
@@ -321,16 +302,13 @@ public:
 			if ((getElementCount() < gOctreeMaxCapacity && contains(data->getBinRadius()) ||
 				(data->getBinRadius() > getSize()[0] &&	parent && parent->getElementCount() >= gOctreeMaxCapacity))) 
 			{ //it belongs here
-				mElementCount++;
-				mData = (element_list) realloc(mData, sizeof(LLPointer<T>)*mElementCount);
-
-				//avoid unref on uninitialized memory
-				memset(mData+mElementCount-1, 0, sizeof(LLPointer<T>));
+				//if this is a redundant insertion, error out (should never happen)
+				llassert(mData.find(data) == mData.end());
 
-				mData[mElementCount-1] = data;
-				mDataEnd = mData + mElementCount;
-				data->setBinIndex(mElementCount-1);
+				mData.insert(data);
 				BaseType::insert(data);
+
+				mElementCount = mData.size();
 				return true;
 			}
 			else
@@ -364,16 +342,10 @@ public:
 
 				if( lt == 0x7 )
 				{
-					mElementCount++;
-					mData = (element_list) realloc(mData, sizeof(LLPointer<T>)*mElementCount);
-
-					//avoid unref on uninitialized memory
-					memset(mData+mElementCount-1, 0, sizeof(LLPointer<T>));
-
-					mData[mElementCount-1] = data;
-					mDataEnd = mData + mElementCount;
-					data->setBinIndex(mElementCount-1);
+					mData.insert(data);
 					BaseType::insert(data);
+
+					mElementCount = mData.size();
 					return true;
 				}
 
@@ -422,59 +394,23 @@ 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)
 	{
-		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))
+		if (mData.find(data) != mData.end())
+		{	//we have data
+			mData.erase(data);
+			mElementCount = mData.size();
+			notifyRemoval(data);
+			checkAlive();
+			return true;
+		}
+		else if (isInside(data))
 		{
 			oct_node* dest = getNodeAt(data);
 
 			if (dest != this)
 			{
-				bool ret = dest->remove(data);
-				llassert(data->getBinIndex() == -1);
-				return ret;
+				return dest->remove(data);
 			}
 		}
 
@@ -493,20 +429,19 @@ 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)
 	{
-        for (U32 i = 0; i < mElementCount; ++i)
+        if (mData.find(data) != mData.end())
 		{
-			if (mData[i] == data)
-			{ //we have data
-				_remove(data, i);
-				llwarns << "FOUND!" << llendl;
-				return;
-			}
+			mData.erase(data);
+			mElementCount = mData.size();
+			notifyRemoval(data);
+			llwarns << "FOUND!" << llendl;
+			checkAlive();
+			return;
 		}
 		
 		for (U32 i = 0; i < getChildCount(); i++)
@@ -518,8 +453,8 @@ public:
 
 	void clearChildren()
 	{
+		mChild.clear();
 		mChildCount = 0;
-
 		U32* foo = (U32*) mChildMap;
 		foo[0] = foo[1] = 0xFFFFFFFF;
 	}
@@ -581,7 +516,7 @@ public:
 
 		mChildMap[child->getOctant()] = mChildCount;
 
-		mChild[mChildCount] = child;
+		mChild.push_back(child);
 		++mChildCount;
 		child->setParent(this);
 
@@ -608,12 +543,9 @@ public:
 			mChild[index]->destroy();
 			delete mChild[index];
 		}
-
+		mChild.erase(mChild.begin() + index);
 		--mChildCount;
 
-		mChild[index] = mChild[mChildCount];
-		
-
 		//rebuild child map
 		U32* foo = (U32*) mChildMap;
 		foo[0] = foo[1] = 0xFFFFFFFF;
@@ -669,12 +601,11 @@ protected:
 	oct_node* mParent;
 	U8 mOctant;
 
-	LLOctreeNode<T>* mChild[8];
+	child_list mChild;
 	U8 mChildMap[8];
 	U32 mChildCount;
 
 	element_list mData;
-	element_iter mDataEnd;
 	U32 mElementCount;
 		
 };