Dendro  5.01
Dendro in Greek language means tree. The Dendro library is a large scale (262K cores on ORNL's Titan) distributed memory adaptive octree framework. The main goal of Dendro is to perform large scale multiphysics simulations efficeiently in mordern supercomputers. Dendro consists of efficient parallel data structures and algorithms to perform variational ( finite element) methods and finite difference mthods on 2:1 balanced arbitary adaptive octrees which enables the users to perform simulations raning from black holes (binary black hole mergers) to blood flow in human body, where applications ranging from relativity, astrophysics to biomedical engineering.
sfcSearch.h
1 //
2 // Created by milinda on 9/25/16.
3 //
4 
14 #ifndef SFCSORTBENCH_SFCSEARCH_H
15 #define SFCSORTBENCH_SFCSEARCH_H
16 
17 #include "sfcSort.h"
18 #include "dendro.h"
19 #include "TreeNode.h"
20 
21 
22 namespace SFC
23 {
24  /*@ breif compare function defined based on sfc < ordering operator defined in ot::TreeSort class.
25  *
26  * */
27  template <typename T>
28  int compare(const void *ap, const void *bp)
29  {
30  const T *a = (T *) ap;
31  const T *b = (T *) bp;
32  if(*a < *b)
33  return -1;
34  else if(*a > *b)
35  return 1;
36  else
37  return 0;
38  }
39 
40 
41  namespace seqSearch
42  {
49  template <typename TKey, typename TOctant>
50  void SFC_treeSearch(TKey* pKeys , TOctant* pNodes,std::vector<unsigned int>& pSearchIndex,DendroIntL nKeyBegin,DendroIntL nKeyEnd,DendroIntL nNodeBegin,DendroIntL nNodeEnd,unsigned int pMaxDepthBit,unsigned int pMaxDepth, unsigned int rot_id);
51 
52 
53  template <typename TKey, typename TOctant>
54  void SFC_treeSearch(TKey* pKeys , TOctant* pNodes,DendroIntL nKeyBegin,DendroIntL nKeyEnd,DendroIntL nNodeBegin,DendroIntL nNodeEnd,unsigned int pMaxDepthBit,unsigned int pMaxDepth, unsigned int rot_id);
55 
56 
63  template <typename TKey, typename TOctant>
64  void SFC_treeSearch(TKey* pKeys , TOctant* pNodes,std::vector<unsigned int> & pSearchIndex,DendroIntL nKeyBegin,DendroIntL nKeyEnd,DendroIntL nNodeBegin,DendroIntL nNodeEnd,unsigned int pMaxDepthBit,unsigned int pMaxDepth, unsigned int rot_id)
65  {
66 
67  unsigned int lev=pMaxDepth-pMaxDepthBit;
68  DendroIntL splitterKeys[(NUM_CHILDREN + 1)];
69  DendroIntL splitterNodes[(NUM_CHILDREN + 1)];
70 
71  unsigned int hindex = 0;
72  unsigned int hindexN = 0;
73  unsigned int index = 0;
74 
75  hindex = (rotations[2 * NUM_CHILDREN * rot_id] - '0');
76  hindexN = (rotations[2 * NUM_CHILDREN * rot_id +1] - '0');
77 
78  SFC::seqSort::SFC_bucketing(pKeys,lev,pMaxDepth,rot_id,nKeyBegin,nKeyEnd,splitterKeys);
79  SFC::seqSort::SFC_bucketing(pNodes,lev,pMaxDepth,rot_id,nNodeBegin,nNodeEnd,splitterNodes);
80 
81 
82  if((pMaxDepthBit) && (((nNodeEnd-nNodeBegin)>=1) && (pNodes[splitterNodes[hindex]].getLevel()>lev)) ) {
83 
84  /*for (unsigned int k = splitterKeys[hindex]; k < splitterKeys[hindexN]; k++) {
85  if ((pKeys[k].getLevel() == lev) & (pNodes[splitterNodes[hindex]].getLevel() == lev)) {
86  pKeys[k].setFlag((pKeys[k].getFlag() | OCT_FOUND));
87  assert(pKeys[k].getFlag() & OCT_FOUND);
88  assert(pKeys[k] == pNodes[splitterNodes[hindex]]);
89  pSearchIndex.push_back(splitterNodes[hindex]);
90  std::cout<<"maxDepth Reached"<<std::endl;
91  }
92  }*/
93 
94  for (int i = 0; i < NUM_CHILDREN; i++) {
95  hindex = (rotations[2 * NUM_CHILDREN * rot_id + i] - '0');
96  if (i == (NUM_CHILDREN - 1))
97  hindexN = i + 1;
98  else
99  hindexN = (rotations[2 * NUM_CHILDREN * rot_id + i + 1] - '0');
100 
101  assert(splitterKeys[hindex] <= splitterKeys[hindexN]);
102  assert(splitterNodes[hindex] <= splitterNodes[hindexN]);
103 
104  index = HILBERT_TABLE[NUM_CHILDREN * rot_id + hindex];
105  SFC_treeSearch(pKeys,pNodes,pSearchIndex,splitterKeys[hindex],splitterKeys[hindexN],splitterNodes[hindex],splitterNodes[hindexN],(pMaxDepthBit-1),pMaxDepth,index);
106 
107  }
108 
109  }else
110  {
111  if(((nNodeEnd-nNodeBegin)==1) )
112  {
113  assert(pNodes[nNodeBegin].getLevel()==lev);
114  for(unsigned int k=nKeyBegin;k<nKeyEnd;k++)
115  {
116  assert(((pNodes[nNodeBegin].isAncestor(pKeys[k]))||(pNodes[nNodeBegin]==pKeys[k])));
117  pKeys[k].setFlag((pKeys[k].getFlag() | OCT_FOUND));
118  assert(pKeys[k].getFlag() & OCT_FOUND);
119  pSearchIndex.push_back(nNodeBegin);
120  }
121 
122  }
123  }
124 
125  }
126 
127 
128 
129  template <typename TKey, typename TOctant>
130  void SFC_treeSearch(TKey* pKeys , TOctant* pNodes,DendroIntL nKeyBegin,DendroIntL nKeyEnd,DendroIntL nNodeBegin,DendroIntL nNodeEnd,unsigned int pMaxDepthBit,unsigned int pMaxDepth, unsigned int rot_id)
131  {
132 
133  unsigned int lev=pMaxDepth-pMaxDepthBit;
134  if(nKeyEnd==nKeyBegin) return;
135  //std::cout<<"call: "<<pMaxDepthBit<<": NBegin: "<<nNodeBegin<<" NEnd: "<<nNodeEnd<<" KBegin: "<<nKeyBegin<<" KEnd: "<<nKeyEnd<<" NodeLev: "<<pNodes[nNodeBegin].getLevel()<<" lev: "<<lev<< std::endl;
136 
137  //if( pMaxDepthBit && ((nNodeEnd-nNodeBegin)>=1) && (pNodes[nNodeBegin].getLevel()>lev))
138  if( pMaxDepthBit && ((nNodeEnd-nNodeBegin)>1) && (pNodes[nNodeBegin].getLevel()>lev))
139  {
140 
141  unsigned int hindex = 0;
142  unsigned int hindexN = 0;
143  unsigned int index = 0;
144  DendroIntL splitterKeys[(NUM_CHILDREN + 1)];
145  DendroIntL splitterNodes[(NUM_CHILDREN + 1)];
146 
147  SFC::seqSort::SFC_bucketing(pKeys, lev, pMaxDepth, rot_id, nKeyBegin, nKeyEnd, splitterKeys);
148  SFC::seqSort::SFC_bucketing(pNodes, lev, pMaxDepth, rot_id, nNodeBegin, nNodeEnd, splitterNodes);
149 
150 
151  for (int i = 0; i < NUM_CHILDREN; i++) {
152  hindex = (rotations[2 * NUM_CHILDREN * rot_id + i] - '0');
153  if (i == (NUM_CHILDREN - 1))
154  hindexN = i + 1;
155  else
156  hindexN = (rotations[2 * NUM_CHILDREN * rot_id + i + 1] - '0');
157 
158  assert(splitterKeys[hindex] <= splitterKeys[hindexN]);
159  assert(splitterNodes[hindex] <= splitterNodes[hindexN]);
160 
161  index = HILBERT_TABLE[NUM_CHILDREN * rot_id + hindex];
162  if(splitterNodes[hindex]!=splitterNodes[hindexN]) SFC_treeSearch(pKeys,pNodes,splitterKeys[hindex],splitterKeys[hindexN],splitterNodes[hindex],splitterNodes[hindexN],(pMaxDepthBit-1),pMaxDepth,index);
163 
164  }
165 
166  }else
167  {
168  if(((nNodeEnd-nNodeBegin)==1) )
169  {
170  //assert(pNodes[nNodeBegin].getLevel()>=lev); this assertion is not always needs to be true. 08-29-2019 Milinda.
171  for(unsigned int k=nKeyBegin;k<nKeyEnd;k++)
172  {
173  //assert(((pNodes[nNodeBegin].isAncestor(pKeys[k]))||(pNodes[nNodeBegin]==pKeys[k]))); // Note: Since we are sarching for the ghost elements we might not find a given key. Hence this should be disabled
174  if((pNodes[nNodeBegin].isAncestor(pKeys[k])) || (pNodes[nNodeBegin]==pKeys[k])){
175  pKeys[k].setFlag((pKeys[k].getFlag() | OCT_FOUND));
176  assert(pKeys[k].getFlag() & OCT_FOUND); // Note: Since we are sarching for the ghost elements we might not find a given key. Hence this should be disabled
177  pKeys[k].setSearchResult(nNodeBegin);
178  }
179 
180 
181  }
182  //std::cout<<"key update: "<<nKeyBegin<<" to : "<<nKeyEnd<<std::endl;
183 
184  }else if(((nNodeEnd-nNodeBegin)>1))
185  {
186 
187  //std::cout<<"Else call: "<<pMaxDepthBit<<": NBegin: "<<nNodeBegin<<" NEnd: "<<nNodeEnd<<" KBegin: "<<nKeyBegin<<" KEnd: "<<nKeyEnd<<" NodeLev: "<<pNodes[nNodeBegin].getLevel()<<" lev: "<<lev<< std::endl;
188  unsigned int nCnt=nNodeBegin;
189  for(unsigned int k=nKeyBegin;k<nKeyEnd;k++)
190  {
191  while( (nCnt<nNodeEnd) && (!(pNodes[nCnt].isAncestor(pKeys[k]))&& !(pNodes[nCnt]==pKeys[k])))
192  nCnt++;
193 
194  //assert(((pNodes[nNodeBegin].isAncestor(pKeys[k]))||(pNodes[nNodeBegin]==pKeys[k]))); // Note: Since we are sarching for the ghost elements we might not find a given key. Hence this should be disabled
195  if(nCnt<nNodeEnd) {
196  pKeys[k].setFlag((pKeys[k].getFlag() | OCT_FOUND));
197  //assert(pKeys[k].getFlag() & OCT_FOUND); // Note: Since we are sarching for the ghost elements we might not find a given key. Hence this should be disabled
198  assert(((pNodes[nCnt].isAncestor(pKeys[k]))||(pNodes[nCnt]==pKeys[k])));
199  pKeys[k].setSearchResult(nCnt);
200  nCnt=nNodeBegin;
201  }
202 
203  }
204 
205 
206  }
207  }
208 
209 
210 
211 
212 
213  }
214 
215 
216 
217 
218 
219  } // namespace seqSearch
220 
221 
222 } // namespace SFC end
223 
224 
225 
226 #endif //SFCSORTBENCH_SFCSEARCH_H
SFC
Definition: sfcSearch.h:22
Generated by   doxygen 1.8.13