summaryrefslogtreecommitdiff
path: root/indra/llmath/lloctree.h
diff options
context:
space:
mode:
Diffstat (limited to 'indra/llmath/lloctree.h')
-rw-r--r--indra/llmath/lloctree.h147
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;
};