From a766e26db46c7c054bae1021470dbe365f2a3cb3 Mon Sep 17 00:00:00 2001 From: William Todd Stinson Date: Mon, 10 Sep 2012 10:37:02 -0700 Subject: Backing out the changes contributing to DRTVWR-167 and DRTVWR-179 from the repository. --- indra/llmath/lloctree.h | 147 +++++++++++++----------------------------------- 1 file changed, 39 insertions(+), 108 deletions(-) (limited to 'indra/llmath/lloctree.h') 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 +#include #define OCT_ERRS LL_WARNS("OctreeErrors") @@ -78,18 +79,16 @@ public: typedef LLOctreeTraveler oct_traveler; typedef LLTreeTraveler tree_traveler; - typedef LLPointer* element_list; - typedef LLPointer* element_iter; - typedef const LLPointer* const_element_iter; + typedef typename std::set > element_list; + typedef typename element_list::iterator element_iter; + typedef typename element_list::const_iterator const_element_iter; typedef typename std::vector*>::iterator tree_listener_iter; - typedef LLOctreeNode** child_list; - typedef LLOctreeNode** child_iter; - + typedef typename std::vector* > child_list; typedef LLTreeNode BaseType; typedef LLOctreeNode oct_node; typedef LLOctreeListener 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)*mElementCount); - - //avoid unref on uninitialized memory - memset(mData+mElementCount-1, 0, sizeof(LLPointer)); + //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)*mElementCount); - - //avoid unref on uninitialized memory - memset(mData+mElementCount-1, 0, sizeof(LLPointer)); - - 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)*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* mChild[8]; + child_list mChild; U8 mChildMap[8]; U32 mChildCount; element_list mData; - element_iter mDataEnd; U32 mElementCount; }; -- cgit v1.2.3 From 97d969a338c1e4f973eb817ba7701aff51a02ccb Mon Sep 17 00:00:00 2001 From: Oz Linden Date: Wed, 12 Sep 2012 14:36:37 -0400 Subject: initial attempt to restore changes that make removing tcmalloc possible; not tested --- indra/llmath/lloctree.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'indra/llmath/lloctree.h') diff --git a/indra/llmath/lloctree.h b/indra/llmath/lloctree.h index 1b11e83b4a..6c7744cdf1 100644 --- a/indra/llmath/lloctree.h +++ b/indra/llmath/lloctree.h @@ -88,7 +88,7 @@ public: typedef LLOctreeNode oct_node; typedef LLOctreeListener oct_listener; - /*void* operator new(size_t size) + void* operator new(size_t size) { return ll_aligned_malloc_16(size); } @@ -96,7 +96,7 @@ public: void operator delete(void* ptr) { ll_aligned_free_16(ptr); - }*/ + } LLOctreeNode( const LLVector4a& center, const LLVector4a& size, -- cgit v1.2.3 From cf98064700a736f73a6c21ce899b186919cbeb64 Mon Sep 17 00:00:00 2001 From: Dave Parks Date: Thu, 20 Sep 2012 09:48:55 -0400 Subject: reapply 52b6c9168974: MAINT-646 Factor std::set out of lloctree --- indra/llmath/lloctree.h | 125 ++++++++++++++++++++++++++++++++++++------------ 1 file changed, 95 insertions(+), 30 deletions(-) (limited to 'indra/llmath/lloctree.h') 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 oct_traveler; typedef LLTreeTraveler tree_traveler; - typedef typename std::set > element_list; - typedef typename element_list::iterator element_iter; - typedef typename element_list::const_iterator const_element_iter; + typedef LLPointer* element_list; + typedef LLPointer* element_iter; + typedef const LLPointer* const_element_iter; typedef typename std::vector*>::iterator tree_listener_iter; typedef typename std::vector* > child_list; typedef LLTreeNode 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)*mElementCount); - mData.insert(data); - BaseType::insert(data); + //avoid unref on uninitialized memory + memset(mData+mElementCount-1, 0, sizeof(LLPointer)); - 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)*mElementCount); + + //avoid unref on uninitialized memory + memset(mData+mElementCount-1, 0, sizeof(LLPointer)); - 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)*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; }; -- cgit v1.2.3 From 4127f3e7fcc725dbbf500c52605c5b950073c828 Mon Sep 17 00:00:00 2001 From: Dave Parks Date: Thu, 20 Sep 2012 09:48:56 -0400 Subject: reapply efcec3eb374f: MAINT-646 Factor std::vector out of lloctree --- indra/llmath/lloctree.h | 18 +++++++++++------- 1 file changed, 11 insertions(+), 7 deletions(-) (limited to 'indra/llmath/lloctree.h') diff --git a/indra/llmath/lloctree.h b/indra/llmath/lloctree.h index a7e176fd51..c3f6f7de2a 100644 --- a/indra/llmath/lloctree.h +++ b/indra/llmath/lloctree.h @@ -31,7 +31,6 @@ #include "v3math.h" #include "llvector4a.h" #include -#include #define OCT_ERRS LL_WARNS("OctreeErrors") @@ -83,7 +82,9 @@ public: typedef LLPointer* element_iter; typedef const LLPointer* const_element_iter; typedef typename std::vector*>::iterator tree_listener_iter; - typedef typename std::vector* > child_list; + typedef LLOctreeNode** child_list; + typedef LLOctreeNode** child_iter; + typedef LLTreeNode BaseType; typedef LLOctreeNode oct_node; typedef LLOctreeListener oct_listener; @@ -232,7 +233,7 @@ public: } void accept(oct_traveler* visitor) { visitor->visit(this); } - virtual bool isLeaf() const { return mChild.empty(); } + virtual bool isLeaf() const { return mChildCount == 0; } U32 getElementCount() const { return mElementCount; } bool isEmpty() const { return mElementCount == 0; } @@ -517,8 +518,8 @@ public: void clearChildren() { - mChild.clear(); mChildCount = 0; + U32* foo = (U32*) mChildMap; foo[0] = foo[1] = 0xFFFFFFFF; } @@ -580,7 +581,7 @@ public: mChildMap[child->getOctant()] = mChildCount; - mChild.push_back(child); + mChild[mChildCount] = child; ++mChildCount; child->setParent(this); @@ -607,9 +608,12 @@ 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; @@ -665,7 +669,7 @@ protected: oct_node* mParent; U8 mOctant; - child_list mChild; + LLOctreeNode* mChild[8]; U8 mChildMap[8]; U32 mChildCount; -- cgit v1.2.3 From cdbfdfc351a51f4fe0c264110cf68a59f0859f04 Mon Sep 17 00:00:00 2001 From: Dave Parks Date: Thu, 11 Oct 2012 17:02:45 -0500 Subject: MAINT-1709 Factor out realloc Reviewed by VoidPointer --- indra/llmath/lloctree.h | 52 +++++++++++++++++++++---------------------------- 1 file changed, 22 insertions(+), 30 deletions(-) (limited to 'indra/llmath/lloctree.h') diff --git a/indra/llmath/lloctree.h b/indra/llmath/lloctree.h index c3f6f7de2a..68d8110f1d 100644 --- a/indra/llmath/lloctree.h +++ b/indra/llmath/lloctree.h @@ -78,7 +78,7 @@ public: typedef LLOctreeTraveler oct_traveler; typedef LLTreeTraveler tree_traveler; - typedef LLPointer* element_list; + typedef std::vector> element_list; typedef LLPointer* element_iter; typedef const LLPointer* const_element_iter; typedef typename std::vector*>::iterator tree_listener_iter; @@ -106,8 +106,9 @@ public: : mParent((oct_node*)parent), mOctant(octant) { - mData = NULL; - mDataEnd = NULL; + //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; @@ -133,9 +134,9 @@ public: mData[i] = NULL; } - free(mData); - mData = NULL; - mDataEnd = NULL; + mData.clear(); + mData.push_back(NULL); + mDataEnd = &mData[0]; for (U32 i = 0; i < getChildCount(); i++) { @@ -239,9 +240,9 @@ public: 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 getDataBegin() { return &mData[0]; } element_iter getDataEnd() { return mDataEnd; } - const_element_iter getDataBegin() const { return mData; } + const_element_iter getDataBegin() const { return &mData[0]; } const_element_iter getDataEnd() const { return mDataEnd; } U32 getChildCount() const { return mChildCount; } @@ -321,14 +322,10 @@ public: if ((getElementCount() < gOctreeMaxCapacity && contains(data->getBinRadius()) || (data->getBinRadius() > getSize()[0] && parent && parent->getElementCount() >= gOctreeMaxCapacity))) { //it belongs here + mData.push_back(NULL); + mData[mElementCount] = data; mElementCount++; - mData = (element_list) realloc(mData, sizeof(LLPointer)*mElementCount); - - //avoid unref on uninitialized memory - memset(mData+mElementCount-1, 0, sizeof(LLPointer)); - - mData[mElementCount-1] = data; - mDataEnd = mData + mElementCount; + mDataEnd = &mData[mElementCount]; data->setBinIndex(mElementCount-1); BaseType::insert(data); return true; @@ -364,14 +361,10 @@ public: if( lt == 0x7 ) { + mData.push_back(NULL); + mData[mElementCount] = data; mElementCount++; - mData = (element_list) realloc(mData, sizeof(LLPointer)*mElementCount); - - //avoid unref on uninitialized memory - memset(mData+mElementCount-1, 0, sizeof(LLPointer)); - - mData[mElementCount-1] = data; - mDataEnd = mData + mElementCount; + mDataEnd = &mData[mElementCount]; data->setBinIndex(mElementCount-1); BaseType::insert(data); return true; @@ -436,16 +429,15 @@ public: mData[i]->setBinIndex(i); } - mData[mElementCount] = NULL; //needed for unref - mData = (element_list) realloc(mData, sizeof(LLPointer)*mElementCount); - mDataEnd = mData+mElementCount; + mData[mElementCount] = NULL; + mData.pop_back(); + mDataEnd = &mData[mElementCount]; } else { - mData[0] = NULL; //needed for unref - free(mData); - mData = NULL; - mDataEnd = NULL; + mData.clear(); + mData.push_back(NULL); + mDataEnd = &mData[0]; } notifyRemoval(data); @@ -491,7 +483,7 @@ public: } //node is now root - llwarns << "!!! OCTREE REMOVING FACE BY ADDRESS, SEVERE PERFORMANCE PENALTY |||" << llendl; + llwarns << "!!! OCTREE REMOVING ELEMENT BY ADDRESS, SEVERE PERFORMANCE PENALTY |||" << llendl; node->removeByAddress(data); llassert(data->getBinIndex() == -1); return true; -- cgit v1.2.3 From b8e14ad2b250ae8c4cae877035e38c485a841515 Mon Sep 17 00:00:00 2001 From: Dave Parks Date: Fri, 26 Oct 2012 15:55:58 -0500 Subject: MAINT-1709 Fix for >> that should have been > > --- indra/llmath/lloctree.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'indra/llmath/lloctree.h') diff --git a/indra/llmath/lloctree.h b/indra/llmath/lloctree.h index 68d8110f1d..4ac1e55cfc 100644 --- a/indra/llmath/lloctree.h +++ b/indra/llmath/lloctree.h @@ -78,7 +78,7 @@ public: typedef LLOctreeTraveler oct_traveler; typedef LLTreeTraveler tree_traveler; - typedef std::vector> element_list; + typedef std::vector > element_list; typedef LLPointer* element_iter; typedef const LLPointer* const_element_iter; typedef typename std::vector*>::iterator tree_listener_iter; -- cgit v1.2.3