diff options
Diffstat (limited to 'indra/llmath/lloctree.h')
-rw-r--r-- | indra/llmath/lloctree.h | 147 |
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; }; |