7 #ifndef GENERICTREENODE_H
8 #define GENERICTREENODE_H
18 #include "OrientedBox.h"
35 typedef KeyType NodeKey;
36 static const int NodeKeyBits = 8*
sizeof(NodeKey);
54 extern int numEmptyNodes;
60 #ifdef CHANGA_REFACTOR_WALKCHECK
79 bucketArrayIndex = -1;
82 #ifdef CHANGA_REFACTOR_WALKCHECK
124 #if INTERLIST_VER > 0
132 int bucketArrayIndex;
151 #if INTERLIST_VER > 0
156 bucketArrayIndex = -1;
166 inline NodeType
getType()
const {
return myType; }
168 inline void setType(NodeType t) { myType = t; }
171 inline NodeKey
getKey()
const {
return key; }
185 #if INTERLIST_VER > 0
186 virtual bool contains(NodeKey nodekey) = 0;
192 return (myType != Invalid);
197 return (myType == Cached ||
198 myType == CachedBucket ||
199 myType == CachedEmpty);
204 return (myType == Bucket ||
205 myType == CachedBucket ||
206 myType == NonLocalBucket);
216 virtual void getChunks(
int num, NodeKey *&ret) = 0;
222 #if INTERLIST_VER > 0
235 double fBallMax = part[i].fBallMax();
237 + Vector3D<double>(fBallMax, fBallMax, fBallMax));
239 - Vector3D<double>(fBallMax, fBallMax, fBallMax));
254 #if INTERLIST_VER > 0
270 CkAbort(
"getLongestCommonPrefix not implemented\n");
275 virtual int getLevel(NodeKey k) = 0;
280 virtual void pup(PUP::er &p,
int depth) = 0;
282 virtual void pup(PUP::er &p) {
284 if(p.isUnpacking()) {
286 myType = (NodeType) iType;
291 bucketArrayIndex = -1;
294 iType = (int) myType;
307 #if INTERLIST_VER > 0
314 #ifdef CHANGA_REFACTOR_WALKCHECK
321 class BinaryTreeNode;
328 std::list<BinaryTreeNode *> pools;
344 typedef std::map<NodeKey, GenericTreeNode *> NodeLookupType;
364 if (children[0] != NULL) children[0]->
fullyDelete();
366 if (children[1] != NULL) children[1]->
fullyDelete();
375 CkAssert(i>=0 && i<2);
380 CkAssert(i>=0 && i<2);
385 CkAssert(i>=0 && i<2);
408 NodeKey a1 = k1 << (NodeKeyBits-l1);
409 NodeKey a2 = k2 << (NodeKeyBits-l2);
413 while( a < (NodeKey(1)<<(NodeKeyBits-1)) )
418 return (k1 >> (l1-i));
425 return ((child >> (childLevel-thisLevel-1)) ^ (key << 1));
428 #if INTERLIST_VER > 0
433 if(nodeLevel<thisLevel)
return false;
435 return ((node>>(nodeLevel-thisLevel))==key);
439 bool isLeftChild()
const {
440 return (dynamic_cast<BinaryTreeNode *>(
parent) && dynamic_cast<BinaryTreeNode *>(
parent)->children[0] ==
this);
443 bool isRightChild()
const {
444 return (dynamic_cast<BinaryTreeNode *>(
parent) && dynamic_cast<BinaryTreeNode *>(
parent)->children[1] ==
this);
447 BinaryTreeNode* getSibling()
const {
448 BinaryTreeNode* p =
dynamic_cast<BinaryTreeNode *
>(
parent);
450 return (p->children[0] ==
this ? p->children[1] : p->children[0]);
468 children[0] = pool->alloc_one();
469 children[1] = pool->alloc_one();
475 children[0]->
parent =
this;
476 children[1]->
parent =
this;
497 children[0]->key = key << 1;
498 children[1]->key = (key << 1) + 1;
504 SFC::Key mask = SFC::Key(1) << ((SFC::KeyBits-1) - level);
508 if (leftBit == rightBit) {
515 children[0]->myType = NonLocal;
516 children[1]->myType = Boundary;
519 children[1]->myType =
lastParticle==totalPart+1 ? Boundary : Internal;
530 children[1]->myType = NonLocal;
531 children[0]->myType = Boundary;
534 children[0]->myType =
firstParticle==0 ? Boundary : Internal;
541 }
else if (leftBit < rightBit) {
547 children[0]->myType = NonLocal;
549 children[1]->myType =
lastParticle==totalPart+1 ? Boundary : Internal;
552 }
else if (
lastParticle == totalPart+1 && rightBit != (part[totalPart].key & mask)) {
556 children[1]->myType = NonLocal;
558 children[0]->myType =
firstParticle==0 ? Boundary : Internal;
568 & ((~ (SFC::Key)0) << ((SFC::KeyBits-1)-level))));
573 children[0]->myType = children[0]->
particleCount==0 ? Empty : (firstParticle==0 ? Boundary : Internal);
575 if (children[0]->myType==Empty) children[0]->
makeEmpty();
576 if (children[1]->myType==Empty) children[1]->
makeEmpty();
581 CkAbort(
"Ok, the particles should be ordered so, how the hell did we get here?!?");
584 children[1]->particlePointer = &part[children[1]->firstParticle];
585 #if INTERLIST_VER > 0
586 if(children[0]->myType == NonLocal) children[0]->numBucketsBeneath = 0;
587 if(children[1]->myType == NonLocal) children[1]->numBucketsBeneath = 0;
596 bool spatial,
NodePool *pool=NULL) {
599 children[0] = pool->alloc_one();
600 children[1] = pool->alloc_one();
603 children[0] =
new BinaryTreeNode();
604 children[1] =
new BinaryTreeNode();
606 children[0]->
parent =
this;
607 children[1]->
parent =
this;
611 children[0]->key = key << 1;
612 children[1]->key = (key << 1) + 1;
617 if(level<rootsLevel){
620 SFC::Key tmp = 1 << (level+1);
621 tmp = children[0]->key - tmp;
622 SFC::Key tmp2 = part[0].key >> (rootsLevel-level-1);
624 if(level+1 != rootsLevel){
626 children[0]->myType = Boundary;
627 children[1]->myType = NonLocal;
633 children[0]->myType = NonLocal;
634 children[1]->myType = Boundary;
642 children[0]->myType = Internal;
643 children[1]->myType = NonLocal;
653 children[0]->myType = NonLocal;
654 children[1]->myType = Internal;
666 float len=0.0,len2=0.0;
680 if(len2>len) { len = len2; dim=1; }
683 if(len2>len) { len = len2; dim=2; }
711 Vector3D<double> divide(0.0,0.0,0.0);
713 dummy.position = divide;
716 dummy,compFnPtr[dim]);
721 - (divEnd - divStart);
726 children[0]->myType = Internal;
727 children[1]->myType = Internal;
740 children[1]->particlePointer = &part[children[1]->firstParticle];
745 GenericTreeNode *
clone()
const;
761 int additional = num - base;
762 if (ret==NULL) ret =
new NodeKey[num];
763 for (
int j=additional, k=additional*2; j<base; ++j, ++k) ret[k] = j + base;
765 for (
int j=0; j<additional*2; ++j) ret[j] = j + base;
769 int countDepth(
int depth) {
772 if (children[0] != NULL) count += children[0]->countDepth(depth-1);
773 if (children[1] != NULL) count += children[1]->countDepth(depth-1);
780 int packNodes(BinaryTreeNode *buffer,
int depth,
int extraSpace=0) {
783 memcpy((
void *)buffer, (
void *)
this,
sizeof(*
this));
784 buffer->parent = NULL;
785 buffer->particlePointer = NULL;
786 #if INTERLIST_VER > 0 && defined CUDA
787 buffer->nodeArrayIndex = -1;
788 buffer->bucketArrayIndex = -1;
792 if (children[0] != NULL) {
793 BinaryTreeNode *nextBuf = (BinaryTreeNode *) (((
char*)buffer) + used * ALIGN_DEFAULT(
sizeof(BinaryTreeNode)+extraSpace));
794 buffer->children[0] = (BinaryTreeNode*)(((
char*)nextBuf) - ((
char*)buffer));
796 used += children[0]->packNodes(nextBuf, depth-1, extraSpace);
799 buffer->children[0] = NULL;
801 if (children[1] != NULL) {
802 BinaryTreeNode *nextBuf = (BinaryTreeNode *) (((
char*)buffer) + used * ALIGN_DEFAULT(
sizeof(BinaryTreeNode)+extraSpace));
803 buffer->children[1] = (BinaryTreeNode*)(((
char*)nextBuf) - ((
char*)buffer));
805 used += children[1]->packNodes(nextBuf, depth-1, extraSpace);
808 buffer->children[1] = NULL;
812 buffer->children[0] = buffer->children[1] = NULL;
821 if (children[0] != NULL) {
823 children[0] = (BinaryTreeNode*)(((
long int)children[0]) + ((
char*)
this));
824 children[0]->
parent =
this;
825 children[0]->unpackNodes();
827 if (children[1] != NULL) {
829 children[1] = (BinaryTreeNode*)(((
long int)children[1]) + ((
char*)
this));
830 children[1]->
parent =
this;
831 children[1]->unpackNodes();
836 void pup(PUP::er &p,
int depth);
854 NodePool::~NodePool() {
855 while(!pools.empty()) {
856 delete [] pools.front();
861 inline BinaryTreeNode *
866 pools.push_front(nodes);
868 return &pools.front()[next++];
886 for (
int i = 0; i < 8; i++) {
893 for (
int i = 0; i < 8; i++) {
900 if (children[i] != NULL) {
901 children[i]->fullyDelete();
912 CkAssert(i>=0 && i<8);
917 CkAssert(i>=0 && i<8);
922 CkAssert(i>=0 && i<8);
931 return (child ^ (key<<3));
944 #if INTERLIST_VER > 0
978 void pup(PUP::er &p);
979 void pup(PUP::er &p,
int depth);
999 bool operator()(NodeKey key1, NodeKey key2)
const {
1001 NodeKey tmp = NodeKey(1);
1005 while(tmp<=key1 || tmp<=key2){
1008 if(len1==0 && tmp>key1){
1011 if(len2==0 && tmp>key2){
1031 inline void operator|(PUP::er &p, NodeType &nt) {
1033 if (p.isUnpacking()) {
1043 inline void operator|(PUP::er &p, GenericTrees >) {
1045 if (p.isUnpacking()) {
1047 gt = (GenericTrees)gti;
1056 #endif //GENERICTREENODE_H
void setChildren(int i, GenericTreeNode *node)
set the specified child of this node to the passed pointer
Definition: GenericTreeNode.h:379
virtual GenericTreeNode * getChildren(int)=0
return the pointers to the specified child of this node
int whichChild(NodeKey child)
return an integer with the number of the child reflecting the key
Definition: GenericTreeNode.h:422
A representation of a multipole expansion.
Definition: MultipoleMoments.h:163
void setType(NodeType t)
set Tree::NodeType of node
Definition: GenericTreeNode.h:168
void getChunks(int num, NodeKey *&ret)
Definition: GenericTreeNode.h:974
unsigned int iParticleTypes
Mask of particle types contatained in this node.
Definition: GenericTreeNode.h:102
int remoteIndex
Definition: GenericTreeNode.h:113
void fullyDelete()
Recursively delete all nodes beneath this node.
Definition: GenericTreeNode.h:898
NodeType getType() const
return Tree::NodeType of node
Definition: GenericTreeNode.h:166
virtual NodeKey getChildKey(int)=0
return the keys for the specified child
unsigned int numChildren() const
return the number of children this node has
Definition: GenericTreeNode.h:370
virtual int whichChild(NodeKey childkey)=0
return an integer with the number of the child reflecting the key
GravityParticle * particlePointer
Pointer to the first particle in this node.
Definition: GenericTreeNode.h:117
double fKeyMax
Maximum smoothing radius of smoothActive particles.
Definition: GenericTreeNode.h:140
void makeOctChildren(GravityParticle *part, int totalPart, int level, NodePool *pool=NULL)
Definition: GenericTreeNode.h:465
bool isCached()
Is this a node in the cache.
Definition: GenericTreeNode.h:196
MultipoleMoments moments
The moments for the gravity computation.
Definition: GenericTreeNode.h:94
unsigned int iType
Bitmask to hold particle type information.
Definition: GravityParticle.h:330
unsigned int particleCount
Total number of particles contained (across all chares)
Definition: GenericTreeNode.h:115
BinaryTreeNode * alloc_one()
give out one node from the pool, allocating a new pool block if needed.
Definition: GenericTreeNode.h:862
void pup(PUP::er &p)
PUP just this node.
Definition: GenericTreeNode.h:835
int getLevel(NodeKey k)
depth of node corresponding to NodeKey
Definition: GenericTreeNode.h:934
int iRank
SMP rank of node owner.
Definition: GenericTreeNode.h:142
bool contains(NodeKey node)
Is nodekey contained by this node.
Definition: GenericTreeNode.h:429
virtual void getChunks(int num, NodeKey *&ret)=0
virtual int getLevel(NodeKey k)=0
depth of node corresponding to NodeKey
int startBucket
index of first bucket in this node
Definition: GenericTreeNode.h:128
void calculateRadiusBox(MultipoleMoments &m, const OrientedBox< double > &box)
Definition: MultipoleMoments.h:470
virtual NodeKey getParentKey()=0
return the key for the parent
void clear()
Reset this expansion to nothing.
Definition: MultipoleMoments.h:396
NodeKey getKey() const
return unique Tree::NodeKey
Definition: GenericTreeNode.h:171
double sizeSm
Radius of bounding sphere of smoothActive particles.
Definition: GenericTreeNode.h:138
NodeKey getParentKey()
return the key for the parent
Definition: GenericTreeNode.h:389
virtual NodeKey getLongestCommonPrefix(NodeKey k1, NodeKey k2)
return the NodeKey of the lowest common ancestor.
Definition: GenericTreeNode.h:268
GenericTreeNode * parent
The parent of this node, or null if none.
Definition: GenericTreeNode.h:96
virtual GenericTreeNode * clone() const =0
make a copy of the node
Base class for tree nodes.
Definition: GenericTreeNode.h:59
bool isValid()
Is the NodeType valid.
Definition: GenericTreeNode.h:191
virtual unsigned int numChildren() const =0
return the number of children this node has
void fullyDelete()
Recursively delete all nodes beneath this node.
Definition: GenericTreeNode.h:363
NodeKey getChildKey(int i)
return the keys for the specified child
Definition: GenericTreeNode.h:384
void getChunks(int num, NodeKey *&ret)
Get a number of top level NodeKeys which together make a complete tree.
Definition: GenericTreeNode.h:752
virtual void setChildren(int, GenericTreeNode *)=0
set the specified child of this node to the passed pointer
GenericTreeNode * clone() const
make a copy of the node
Definition: GenericTreeNode.cpp:6
int lastParticle
An index to the last particle contained by this node, myNumParticles+1 means outside the node...
Definition: GenericTreeNode.h:108
virtual void setChildren(int i, GenericTreeNode *node)
set the specified child of this node to the passed pointer
Definition: GenericTreeNode.h:916
GenericTreeNode * clone() const
make a copy of the node
Definition: GenericTreeNode.h:957
virtual unsigned int numChildren() const
return the number of children this node has
Definition: GenericTreeNode.h:907
int rungs
Definition: GenericTreeNode.h:122
int64_t nSPH
The number of SPH particles this node contains.
Definition: GenericTreeNode.h:104
int firstParticle
An index for the first particle contained by this node, 0 means outside the node. ...
Definition: GenericTreeNode.h:106
OrientedBox< cosmoType > boundingBox
The axis-aligned bounding box of this node.
Definition: GenericTreeNode.h:98
int numBucketsBeneath
Number of buckets in this node.
Definition: GenericTreeNode.h:126
void getGraphViz(std::ostream &out)
print out a visualization of the tree for diagnostics
Definition: ParallelGravity.cpp:4218
NodeKey getParentKey()
return the key for the parent
Definition: GenericTreeNode.h:926
bool contains(NodeKey node)
Is nodekey contained by this node.
Definition: GenericTreeNode.h:945
void calculateRadiusFarthestParticle(MultipoleMoments &m, const ParticleType *begin, const ParticleType *end)
Given the positions that make up a multipole expansion, set the distance to the farthest particle fro...
Definition: MultipoleMoments.h:483
bool isBucket()
Is this a node a bucket.
Definition: GenericTreeNode.h:203
virtual void pup(PUP::er &p)
PUP just this node.
Definition: GenericTreeNode.h:282
void makeOctChildren(GravityParticle *part, int totalPart, int level, NodePool *pool=NULL)
construct the children of the "this" node following the given logical criteria (Oct/Orb) ...
Definition: GenericTreeNode.h:951
Vector3D< double > centerSm
center of smoothActive particles during smooth operation
Definition: GenericTreeNode.h:136
NodeKey getLongestCommonPrefix(NodeKey k1, NodeKey k2)
return the NodeKey of the lowest common ancestor.
Definition: GenericTreeNode.h:403
Class for Oct tree where each node has 8 direct children.
Definition: GenericTreeNode.h:879
GenericTreeNode(NodeKey k, NodeType type, int first, int last, GenericTreeNode *p)
Construct GenericTreeNode.
Definition: GenericTreeNode.h:150
virtual bool contains(NodeKey nodekey)=0
Is nodekey contained by this node.
int TYPETest(const GravityParticle *a, unsigned int b)
Test for a type flag.
Definition: GravityParticle.h:525
Fundamental type for a particle.
Definition: GravityParticle.h:316
NodeKey getChildKey(int i)
return the keys for the specified child
Definition: GenericTreeNode.h:921
virtual GenericTreeNode * getChildren(int i)
return the pointers to the specified child of this node
Definition: GenericTreeNode.h:911
Utility to pool allocations of tree nodes.
Definition: GenericTreeNode.h:324
virtual void makeOctChildren(GravityParticle *part, int totalPart, int level, NodePool *pool=NULL)=0
construct the children of the "this" node following the given logical criteria (Oct/Orb) ...
OrientedBox< double > bndBoxBall
The bounding box including search balls of this node.
Definition: GenericTreeNode.h:100
GenericTreeNode * getChildren(int i)
return the pointers to the specified child of this node
Definition: GenericTreeNode.h:374
void makeEmpty()
initialize an empty node
Definition: GenericTreeNode.h:251
void makeBucket(GravityParticle *part)
transform an internal node into a bucket
Definition: GenericTreeNode.h:219
virtual void pup(PUP::er &p, int depth)=0
PUP node and children down to depth.
int getLevel(NodeKey k)
depth of node corresponding to NodeKey
Definition: GenericTreeNode.h:393
int whichChild(NodeKey child)
return an integer with the number of the child reflecting the key
Definition: GenericTreeNode.h:930
virtual void fullyDelete()=0
Recursively delete all nodes beneath this node.
A TreeNode with two children.
Definition: GenericTreeNode.h:347
int rung
the current rung (greater means faster)
Definition: GravityParticle.h:329
Definition: GenericTreeNode.h:995
void pup(PUP::er &p)
PUP just this node.