1 files changed, 105 insertions, 110 deletions

diff --git a/indra/llmath/lloctree.h b/indra/llmath/lloctree.h
index 0e2f62f9db..318ee65cc0 100644
--- a/indra/llmath/lloctree.h
+++ b/indra/llmath/lloctree.h
@@ -34,6 +34,9 @@
 
 #define OCT_ERRS LL_WARNS("OctreeErrors")
 
+#define OCTREE_DEBUG_COLOR_REMOVE   0x0000FF // r
+#define OCTREE_DEBUG_COLOR_INSERT   0x00FF00 // g
+#define OCTREE_DEBUG_COLOR_BALANCE  0xFF0000 // b
 
 extern U32 gOctreeMaxCapacity;
 extern float gOctreeMinSize;
@@ -45,101 +48,98 @@ extern float gOctreeMinSize;
 #define LL_OCTREE_MAX_CAPACITY 128
 #endif*/
 
-template <class T> class LLOctreeNode;
+// T is the type of the element referenced by the octree node.
+// T_PTR determines how pointers to elements are stored internally.
+// LLOctreeNode<T, LLPointer<T>> assumes ownership of inserted elements and
+// deletes elements removed from the tree.
+// LLOctreeNode<T, T*> doesn't take ownership of inserted elements, so the API
+// user is responsible for managing the storage lifecycle of elements added to
+// the tree.
+template <class T, typename T_PTR> class LLOctreeNode;
 
-template <class T>
+template <class T, typename T_PTR>
 class LLOctreeListener: public LLTreeListener<T>
 {
 public:
 	typedef LLTreeListener<T> BaseType;
-	typedef LLOctreeNode<T> oct_node;
+    typedef LLOctreeNode<T, T_PTR> oct_node;
 
 	virtual void handleChildAddition(const oct_node* parent, oct_node* child) = 0;
 	virtual void handleChildRemoval(const oct_node* parent, const oct_node* child) = 0;
 };
 
-template <class T>
+template <class T, typename T_PTR>
 class LLOctreeTraveler
 {
 public:
-	virtual void traverse(const LLOctreeNode<T>* node);
-	virtual void visit(const LLOctreeNode<T>* branch) = 0;
+    virtual void traverse(const LLOctreeNode<T, T_PTR>* node);
+    virtual void visit(const LLOctreeNode<T, T_PTR>* branch) = 0;
 };
 
-template <class T>
-class LLOctreeTravelerDepthFirst : public LLOctreeTraveler<T>
+template <class T, typename T_PTR>
+class LLOctreeTravelerDepthFirst : public LLOctreeTraveler<T, T_PTR>
 {
 public:
-	virtual void traverse(const LLOctreeNode<T>* node);
+	virtual void traverse(const LLOctreeNode<T, T_PTR>* node) override;
 };
 
-template <class T>
-class LLOctreeNode : public LLTreeNode<T>
+template <class T, typename T_PTR>
+class alignas(16) LLOctreeNode : public LLTreeNode<T>
 {
+    LL_ALIGN_NEW
 public:
 
-	typedef LLOctreeTraveler<T>									oct_traveler;
-	typedef LLTreeTraveler<T>									tree_traveler;
-	typedef std::vector< LLPointer<T> >							element_list;		// note:  don't remove the whitespace between "> >"
-	typedef LLPointer<T>*										element_iter;
-	typedef const LLPointer<T>*									const_element_iter;
+    typedef LLOctreeTraveler<T, T_PTR>                          oct_traveler;
+    typedef LLTreeTraveler<T>                                   tree_traveler;
+    typedef std::vector<T_PTR>                                  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 LLOctreeNode<T, T_PTR>**                            child_list;
+    typedef LLOctreeNode<T, T_PTR>**                            child_iter;
 
-	typedef LLTreeNode<T>		BaseType;
-	typedef LLOctreeNode<T>		oct_node;
-	typedef LLOctreeListener<T>	oct_listener;
+    typedef LLTreeNode<T>               BaseType;
+    typedef LLOctreeNode<T, T_PTR>      oct_node;
+    typedef LLOctreeListener<T, T_PTR>  oct_listener;
 
-	void* operator new(size_t size)
-	{
-		return ll_aligned_malloc_16(size);
-	}
-
-	void operator delete(void* ptr)
-	{
-		ll_aligned_free_16(ptr);
-	}
+    enum
+    {
+        NO_CHILD_NODES = 255 // Note: This is an U8 to match the max value in mChildMap[]
+    };
 
 	LLOctreeNode(	const LLVector4a& center, 
 					const LLVector4a& size, 
 					BaseType* parent, 
-					U8 octant = 255)
+					U8 octant = NO_CHILD_NODES)
 	:	mParent((oct_node*)parent), 
 		mOctant(octant) 
 	{ 
 		llassert(size[0] >= gOctreeMinSize*0.5f);
-		//always keep a NULL terminated list to avoid out of bounds exceptions in debug builds
-		mData.push_back(NULL);
-		mDataEnd = &mData[0];
 
 		mCenter = center;
 		mSize = size;
 
 		updateMinMax();
-		if ((mOctant == 255) && mParent)
+		if ((mOctant == NO_CHILD_NODES) && mParent)
 		{
 			mOctant = ((oct_node*) mParent)->getOctant(mCenter);
 		}
 
-		mElementCount = 0;
-
 		clearChildren();
 	}
 
-	virtual ~LLOctreeNode()								
+	virtual ~LLOctreeNode()
 	{ 
-		BaseType::destroyListeners(); 
+		BaseType::destroyListeners();
 		
-		for (U32 i = 0; i < mElementCount; ++i)
+        const U32 element_count = getElementCount();
+        for (U32 i = 0; i < element_count; ++i)
 		{
 			mData[i]->setBinIndex(-1);
 			mData[i] = NULL;
 		}
 
 		mData.clear();
-		mData.push_back(NULL);
-		mDataEnd = &mData[0];
 
 		for (U32 i = 0; i < getChildCount(); i++)
 		{
@@ -168,7 +168,7 @@ public:
 		return rad <= mSize[0]*2.f && isInside(pos); 
 	}
 
-	inline bool isInside(T* data) const			
+	inline bool isInside(T* data) const
 	{ 
 		return isInside(data->getPositionGroup(), data->getBinRadius());
 	}
@@ -239,14 +239,12 @@ public:
 	void accept(oct_traveler* visitor)				{ visitor->visit(this); }
 	virtual bool isLeaf() const						{ return mChildCount == 0; }
 	
-	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[0]; }
-	element_iter getDataEnd()						{ return mDataEnd; }
-	const_element_iter getDataBegin() const			{ return &mData[0]; }
-	const_element_iter getDataEnd() const			{ return mDataEnd; }
+    U32 getElementCount() const                     { return (U32)mData.size(); }
+    bool isEmpty() const                            { return mData.empty(); }
+    element_iter getDataBegin()                     { return mData.begin(); }
+    element_iter getDataEnd()                       { return mData.end(); }
+    const_element_iter getDataBegin() const         { return mData.cbegin(); }
+    const_element_iter getDataEnd() const           { return mData.cend(); }
 		
 	U32 getChildCount()	const						{ return mChildCount; }
 	oct_node* getChild(U32 index)					{ return mChild[index]; }
@@ -262,9 +260,9 @@ public:
 		for (U32 i = 0; i < 8; i++)
 		{
 			U8 idx = mChildMap[i];
-			if (idx != 255)
+			if (idx != NO_CHILD_NODES)
 			{
-				LLOctreeNode<T>* child = mChild[idx];
+                oct_node* child = mChild[idx];
 
 				if (child->getOctant() != i)
 				{
@@ -282,10 +280,10 @@ public:
 
 	oct_node* getNodeAt(const LLVector4a& pos, const F32& rad)
 	{ 
-		LLOctreeNode<T>* node = this;
+        oct_node* node = this;
 
 		if (node->isInside(pos, rad))
-		{		
+		{
 			//do a quick search by octant
 			U8 octant = node->getOctant(pos);
 			
@@ -295,7 +293,7 @@ public:
 			// the data
 			U8 next_node = node->mChildMap[octant];
 			
-			while (next_node != 255 && node->getSize()[0] >= rad)
+			while (next_node != NO_CHILD_NODES && node->getSize()[0] >= rad)
 			{	
 				node = node->getChild(next_node);
 				octant = node->getOctant(pos);
@@ -304,7 +302,7 @@ public:
 		}
 		else if (!node->contains(rad) && node->getParent())
 		{ //if we got here, data does not exist in this node
-			return ((LLOctreeNode<T>*) node->getParent())->getNodeAt(pos, rad);
+            return ((oct_node*) node->getParent())->getNodeAt(pos, rad);
 		}
 
 		return node;
@@ -312,12 +310,14 @@ public:
 	
 	virtual bool insert(T* data)
 	{
+        //LL_PROFILE_ZONE_NAMED_COLOR("Octree::insert()",OCTREE_DEBUG_COLOR_INSERT);
+
 		if (data == NULL || data->getBinIndex() != -1)
 		{
 			OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE BRANCH !!!" << LL_ENDL;
 			return false;
 		}
-		LLOctreeNode<T>* parent = getOctParent();
+        oct_node* parent = getOctParent();
 
 		//is it here?
 		if (isInside(data->getPositionGroup()))
@@ -325,11 +325,8 @@ public:
 			if ((((getElementCount() < gOctreeMaxCapacity || getSize()[0] <= gOctreeMinSize) && contains(data->getBinRadius())) ||
 				(data->getBinRadius() > getSize()[0] &&	parent && parent->getElementCount() >= gOctreeMaxCapacity))) 
 			{ //it belongs here
-				mData.push_back(NULL);
-				mData[mElementCount] = data;
-				mElementCount++;
-				mDataEnd = &mData[mElementCount];
-				data->setBinIndex(mElementCount-1);
+                mData.push_back(data);
+                data->setBinIndex(getElementCount() - 1);
 				BaseType::insert(data);
 				return true;
 			}
@@ -353,7 +350,7 @@ public:
 				size.mul(0.5f);
 		        		
 				//push center in direction of data
-				LLOctreeNode<T>::pushCenter(center, size, data);
+                oct_node::pushCenter(center, size, data);
 
 				// handle case where floating point number gets too small
 				LLVector4a val;
@@ -365,11 +362,8 @@ public:
 
 				if( lt == 0x7 )
 				{
-					mData.push_back(NULL);
-					mData[mElementCount] = data;
-					mElementCount++;
-					mDataEnd = &mData[mElementCount];
-					data->setBinIndex(mElementCount-1);
+                    mData.push_back(data);
+                    data->setBinIndex(getElementCount() - 1);
 					BaseType::insert(data);
 					return true;
 				}
@@ -395,7 +389,7 @@ public:
 
 				llassert(size[0] >= gOctreeMinSize*0.5f);
 				//make the new kid
-				child = new LLOctreeNode<T>(center, size, this);
+                child = new oct_node(center, size, this);
 				addChild(child);
 								
 				child->insert(data);
@@ -428,28 +422,25 @@ public:
 	}
 
 	void _remove(T* data, S32 i)
-	{ //precondition -- mElementCount > 0, idx is in range [0, mElementCount)
+    { //precondition -- getElementCount() > 0, idx is in range [0, getElementCount())
 
-		mElementCount--;
 		data->setBinIndex(-1); 
 		
-		if (mElementCount > 0)
+        const U32 new_element_count = getElementCount() - 1;
+		if (new_element_count > 0)
 		{
-			if (mElementCount != i)
+			if (new_element_count != i)
 			{
-				mData[i] = mData[mElementCount]; //might unref data, do not access data after this point
+				mData[i] = mData[new_element_count]; //might unref data, do not access data after this point
 				mData[i]->setBinIndex(i);
 			}
 
-			mData[mElementCount] = NULL;
+			mData[new_element_count] = NULL;
 			mData.pop_back();
-			mDataEnd = &mData[mElementCount];
 		}
 		else
 		{
 			mData.clear();
-			mData.push_back(NULL);
-			mDataEnd = &mData[0];
 		}
 
 		this->notifyRemoval(data);
@@ -458,9 +449,11 @@ public:
 
 	bool remove(T* data)
 	{
+        //LL_PROFILE_ZONE_NAMED_COLOR("Octree::remove()", OCTREE_DEBUG_COLOR_REMOVE);
+
 		S32 i = data->getBinIndex();
 
-		if (i >= 0 && i < mElementCount)
+        if (i >= 0 && i < getElementCount())
 		{
 			if (mData[i] == data)
 			{ //found it
@@ -503,7 +496,8 @@ public:
 
 	void removeByAddress(T* data)
 	{
-        for (U32 i = 0; i < mElementCount; ++i)
+        const U32 element_count = getElementCount();
+        for (U32 i = 0; i < element_count; ++i)
 		{
 			if (mData[i] == data)
 			{ //we have data
@@ -515,7 +509,7 @@ public:
 		
 		for (U32 i = 0; i < getChildCount(); i++)
 		{	//we don't contain data, so pass this guy down
-			LLOctreeNode<T>* child = (LLOctreeNode<T>*) getChild(i);
+            oct_node* child = (oct_node*) getChild(i);
 			child->removeByAddress(data);
 		}
 	}
@@ -523,9 +517,7 @@ public:
 	void clearChildren()
 	{
 		mChildCount = 0;
-
-		U32* foo = (U32*) mChildMap;
-		foo[0] = foo[1] = 0xFFFFFFFF;
+		memset(mChildMap, NO_CHILD_NODES, sizeof(mChildMap));
 	}
 
 	void validate()
@@ -616,11 +608,9 @@ public:
 		--mChildCount;
 
 		mChild[index] = mChild[mChildCount];
-		
 
 		//rebuild child map
-		U32* foo = (U32*) mChildMap;
-		foo[0] = foo[1] = 0xFFFFFFFF;
+		memset(mChildMap, NO_CHILD_NODES, sizeof(mChildMap));
 
 		for (U32 i = 0; i < mChildCount; ++i)
 		{
@@ -656,7 +646,7 @@ public:
 		OCT_ERRS << "Octree failed to delete requested child." << LL_ENDL;
 	}
 
-protected:	
+protected:
 	typedef enum
 	{
 		CENTER = 0,
@@ -673,23 +663,20 @@ protected:
 	oct_node* mParent;
 	U8 mOctant;
 
-	LLOctreeNode<T>* mChild[8];
+    oct_node* mChild[8];
 	U8 mChildMap[8];
 	U32 mChildCount;
 
 	element_list mData;
-	element_iter mDataEnd;
-	U32 mElementCount;
-		
 }; 
 
 //just like a regular node, except it might expand on insert and compress on balance
-template <class T>
-class LLOctreeRoot : public LLOctreeNode<T>
+template <class T, typename T_PTR>
+class LLOctreeRoot : public LLOctreeNode<T, T_PTR>
 {
 public:
-	typedef LLOctreeNode<T>	BaseType;
-	typedef LLOctreeNode<T>		oct_node;
+    typedef LLOctreeNode<T, T_PTR> BaseType;
+    typedef LLOctreeNode<T, T_PTR> oct_node;
 
 	LLOctreeRoot(const LLVector4a& center, 
 				 const LLVector4a& size, 
@@ -698,11 +685,13 @@ public:
 	{
 	}
 	
-	bool balance()
+	bool balance() override
 	{	
+        //LL_PROFILE_ZONE_NAMED_COLOR("Octree::balance()",OCTREE_DEBUG_COLOR_BALANCE);
+
 		if (this->getChildCount() == 1 && 
 			!(this->mChild[0]->isLeaf()) &&
-			this->mChild[0]->getElementCount() == 0) 
+			this->mChild[0]->getElementCount() == 0)
 		{ //if we have only one child and that child is an empty branch, make that child the root
 			oct_node* child = this->mChild[0];
 					
@@ -732,7 +721,7 @@ public:
 	}
 
 	// LLOctreeRoot::insert
-	bool insert(T* data)
+	bool insert(T* data) override
 	{
 		if (data == NULL) 
 		{
@@ -768,7 +757,7 @@ public:
 			oct_node* node = this->getNodeAt(data);
 			if (node == this)
 			{
-				LLOctreeNode<T>::insert(data);
+                oct_node::insert(data);
 			}
 			else if (node->isInside(data->getPositionGroup()))
 			{
@@ -788,13 +777,13 @@ public:
 				LLVector4a center, size;
 				center = this->getCenter();
 				size = this->getSize();
-				LLOctreeNode<T>::pushCenter(center, size, data);
+                oct_node::pushCenter(center, size, data);
 				this->setCenter(center);
 				size.mul(2.f);
 				this->setSize(size);
 				this->updateMinMax();
 			}
-			LLOctreeNode<T>::insert(data);
+            oct_node::insert(data);
 		}
 		else
 		{
@@ -806,7 +795,7 @@ public:
 
 				//expand this node
 				LLVector4a newcenter(center);
-				LLOctreeNode<T>::pushCenter(newcenter, size, data);
+                oct_node::pushCenter(newcenter, size, data);
 				this->setCenter(newcenter);
 				LLVector4a size2 = size;
 				size2.mul(2.f);
@@ -816,11 +805,11 @@ public:
 				llassert(size[0] >= gOctreeMinSize);
 
 				//copy our children to a new branch
-				LLOctreeNode<T>* newnode = new LLOctreeNode<T>(center, size, this);
+                oct_node* newnode = new oct_node(center, size, this);
 				
 				for (U32 i = 0; i < this->getChildCount(); i++)
 				{
-					LLOctreeNode<T>* child = this->getChild(i);
+                    oct_node* child = this->getChild(i);
 					newnode->addChild(child);
 				}
 
@@ -835,13 +824,19 @@ public:
 
 		return false;
 	}
+
+    bool isLeaf() const override
+    {
+        // root can't be a leaf
+        return false;
+    }
 };
 
 //========================
 //		LLOctreeTraveler
 //========================
-template <class T>
-void LLOctreeTraveler<T>::traverse(const LLOctreeNode<T>* node)
+template <class T, typename T_PTR>
+void LLOctreeTraveler<T, T_PTR>::traverse(const LLOctreeNode<T, T_PTR>* node)
 {
 	node->accept(this);
 	for (U32 i = 0; i < node->getChildCount(); i++)
@@ -850,8 +845,8 @@ void LLOctreeTraveler<T>::traverse(const LLOctreeNode<T>* node)
 	}
 }
 
-template <class T>
-void LLOctreeTravelerDepthFirst<T>::traverse(const LLOctreeNode<T>* node)
+template <class T, typename T_PTR>
+void LLOctreeTravelerDepthFirst<T, T_PTR>::traverse(const LLOctreeNode<T, T_PTR>* node)
 {
 	for (U32 i = 0; i < node->getChildCount(); i++)
 	{