From dbe0cb58653b3199f6abcf640d38e8fb99b2e073 Mon Sep 17 00:00:00 2001 From: Cosmic Linden Date: Mon, 11 Apr 2022 10:36:13 -0700 Subject: SL-17021: Clean up some unneeded member variables from lloctree No performance difference measured --- indra/llmath/lloctree.h | 64 ++++++++++++++++++------------------------------- 1 file changed, 23 insertions(+), 41 deletions(-) (limited to 'indra/llmath/lloctree.h') diff --git a/indra/llmath/lloctree.h b/indra/llmath/lloctree.h index a9a54a8113..7e73fb6b57 100644 --- a/indra/llmath/lloctree.h +++ b/indra/llmath/lloctree.h @@ -85,8 +85,8 @@ public: typedef LLOctreeTraveler oct_traveler; typedef LLTreeTraveler tree_traveler; typedef std::vector< LLPointer > element_list; // note: don't remove the whitespace between "> >" - typedef LLPointer* element_iter; - typedef const LLPointer* const_element_iter; + 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; @@ -108,9 +108,6 @@ public: 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; @@ -121,8 +118,6 @@ public: mOctant = ((oct_node*) mParent)->getOctant(mCenter); } - mElementCount = 0; - clearChildren(); } @@ -130,15 +125,14 @@ public: { 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++) { @@ -238,14 +232,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]; } @@ -326,11 +318,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; } @@ -366,11 +355,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; } @@ -429,28 +415,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); @@ -463,7 +446,7 @@ public: S32 i = data->getBinIndex(); - if (i >= 0 && i < mElementCount) + if (i >= 0 && i < getElementCount()) { if (mData[i] == data) { //found it @@ -506,7 +489,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 @@ -677,8 +661,6 @@ protected: 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 -- cgit v1.2.3 From 162280cd981b97ffef927553ec230cddcda878ce Mon Sep 17 00:00:00 2001 From: Cosmic Linden Date: Tue, 12 Apr 2022 14:05:51 -0700 Subject: SL-17021: Templatize LLOctreeNode and related classes to allow for option to store elements in octrees as raw pointers. Use for faster allocation in LLVolumeFace::createOctree. --- indra/llmath/lloctree.h | 89 ++++++++++++++++++++++++++----------------------- 1 file changed, 48 insertions(+), 41 deletions(-) (limited to 'indra/llmath/lloctree.h') diff --git a/indra/llmath/lloctree.h b/indra/llmath/lloctree.h index 7e73fb6b57..318ee65cc0 100644 --- a/indra/llmath/lloctree.h +++ b/indra/llmath/lloctree.h @@ -48,52 +48,59 @@ extern float gOctreeMinSize; #define LL_OCTREE_MAX_CAPACITY 128 #endif*/ -template class LLOctreeNode; - -template +// T is the type of the element referenced by the octree node. +// T_PTR determines how pointers to elements are stored internally. +// LLOctreeNode> assumes ownership of inserted elements and +// deletes elements removed from the tree. +// LLOctreeNode 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 LLOctreeNode; + +template class LLOctreeListener: public LLTreeListener { public: typedef LLTreeListener BaseType; - typedef LLOctreeNode oct_node; + typedef LLOctreeNode 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 +template class LLOctreeTraveler { public: - virtual void traverse(const LLOctreeNode* node); - virtual void visit(const LLOctreeNode* branch) = 0; + virtual void traverse(const LLOctreeNode* node); + virtual void visit(const LLOctreeNode* branch) = 0; }; -template -class LLOctreeTravelerDepthFirst : public LLOctreeTraveler +template +class LLOctreeTravelerDepthFirst : public LLOctreeTraveler { public: - virtual void traverse(const LLOctreeNode* node) override; + virtual void traverse(const LLOctreeNode* node) override; }; -template +template class alignas(16) LLOctreeNode : public LLTreeNode { LL_ALIGN_NEW public: - typedef LLOctreeTraveler oct_traveler; - typedef LLTreeTraveler tree_traveler; - typedef std::vector< LLPointer > element_list; // note: don't remove the whitespace between "> >" + typedef LLOctreeTraveler oct_traveler; + typedef LLTreeTraveler tree_traveler; + typedef std::vector 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 LLOctreeNode** child_list; + typedef LLOctreeNode** child_iter; - typedef LLTreeNode BaseType; - typedef LLOctreeNode oct_node; - typedef LLOctreeListener oct_listener; + typedef LLTreeNode BaseType; + typedef LLOctreeNode oct_node; + typedef LLOctreeListener oct_listener; enum { @@ -255,7 +262,7 @@ public: U8 idx = mChildMap[i]; if (idx != NO_CHILD_NODES) { - LLOctreeNode* child = mChild[idx]; + oct_node* child = mChild[idx]; if (child->getOctant() != i) { @@ -273,7 +280,7 @@ public: oct_node* getNodeAt(const LLVector4a& pos, const F32& rad) { - LLOctreeNode* node = this; + oct_node* node = this; if (node->isInside(pos, rad)) { @@ -295,7 +302,7 @@ public: } else if (!node->contains(rad) && node->getParent()) { //if we got here, data does not exist in this node - return ((LLOctreeNode*) node->getParent())->getNodeAt(pos, rad); + return ((oct_node*) node->getParent())->getNodeAt(pos, rad); } return node; @@ -310,7 +317,7 @@ public: OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE BRANCH !!!" << LL_ENDL; return false; } - LLOctreeNode* parent = getOctParent(); + oct_node* parent = getOctParent(); //is it here? if (isInside(data->getPositionGroup())) @@ -343,7 +350,7 @@ public: size.mul(0.5f); //push center in direction of data - LLOctreeNode::pushCenter(center, size, data); + oct_node::pushCenter(center, size, data); // handle case where floating point number gets too small LLVector4a val; @@ -382,7 +389,7 @@ public: llassert(size[0] >= gOctreeMinSize*0.5f); //make the new kid - child = new LLOctreeNode(center, size, this); + child = new oct_node(center, size, this); addChild(child); child->insert(data); @@ -502,7 +509,7 @@ public: for (U32 i = 0; i < getChildCount(); i++) { //we don't contain data, so pass this guy down - LLOctreeNode* child = (LLOctreeNode*) getChild(i); + oct_node* child = (oct_node*) getChild(i); child->removeByAddress(data); } } @@ -656,7 +663,7 @@ protected: oct_node* mParent; U8 mOctant; - LLOctreeNode* mChild[8]; + oct_node* mChild[8]; U8 mChildMap[8]; U32 mChildCount; @@ -664,12 +671,12 @@ protected: }; //just like a regular node, except it might expand on insert and compress on balance -template -class LLOctreeRoot : public LLOctreeNode +template +class LLOctreeRoot : public LLOctreeNode { public: - typedef LLOctreeNode BaseType; - typedef LLOctreeNode oct_node; + typedef LLOctreeNode BaseType; + typedef LLOctreeNode oct_node; LLOctreeRoot(const LLVector4a& center, const LLVector4a& size, @@ -750,7 +757,7 @@ public: oct_node* node = this->getNodeAt(data); if (node == this) { - LLOctreeNode::insert(data); + oct_node::insert(data); } else if (node->isInside(data->getPositionGroup())) { @@ -770,13 +777,13 @@ public: LLVector4a center, size; center = this->getCenter(); size = this->getSize(); - LLOctreeNode::pushCenter(center, size, data); + oct_node::pushCenter(center, size, data); this->setCenter(center); size.mul(2.f); this->setSize(size); this->updateMinMax(); } - LLOctreeNode::insert(data); + oct_node::insert(data); } else { @@ -788,7 +795,7 @@ public: //expand this node LLVector4a newcenter(center); - LLOctreeNode::pushCenter(newcenter, size, data); + oct_node::pushCenter(newcenter, size, data); this->setCenter(newcenter); LLVector4a size2 = size; size2.mul(2.f); @@ -798,11 +805,11 @@ public: llassert(size[0] >= gOctreeMinSize); //copy our children to a new branch - LLOctreeNode* newnode = new LLOctreeNode(center, size, this); + oct_node* newnode = new oct_node(center, size, this); for (U32 i = 0; i < this->getChildCount(); i++) { - LLOctreeNode* child = this->getChild(i); + oct_node* child = this->getChild(i); newnode->addChild(child); } @@ -828,8 +835,8 @@ public: //======================== // LLOctreeTraveler //======================== -template -void LLOctreeTraveler::traverse(const LLOctreeNode* node) +template +void LLOctreeTraveler::traverse(const LLOctreeNode* node) { node->accept(this); for (U32 i = 0; i < node->getChildCount(); i++) @@ -838,8 +845,8 @@ void LLOctreeTraveler::traverse(const LLOctreeNode* node) } } -template -void LLOctreeTravelerDepthFirst::traverse(const LLOctreeNode* node) +template +void LLOctreeTravelerDepthFirst::traverse(const LLOctreeNode* node) { for (U32 i = 0; i < node->getChildCount(); i++) { -- cgit v1.2.3