OpenVDB  9.1.1
NodeManager.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 
4 /*!
5  \file NodeManager.h
6 
7  \author Ken Museth
8 
9  \date February 12, 2021
10 
11  \brief This class allows for sequential access to nodes in a NanoVDB tree.
12 
13  \brief Currently it is limited to the host (CPU) but it can easily be ported
14  to the device (GPU) if sequential node access is required.
15 */
16 
17 #include "../NanoVDB.h"
18 #include "Invoke.h"
19 
20 #ifndef NANOVDB_NODEMANAGER_H_HAS_BEEN_INCLUDED
21 #define NANOVDB_NODEMANAGER_H_HAS_BEEN_INCLUDED
22 
23 namespace nanovdb {
24 
25 /// @brief NodeNanager maintains separate linear arrays of the three nodes types
26 template<typename GridT>
28 
29 /// @brief LeafNanager maintains a linear array of leaf nodes
30 template<typename GridT>
32 
33 /// @brief creates a NodeManager from a grid. Move semantics is used.
34 template<typename GridT>
36 
37 /// @brief creates a LeafManager from a grid. Move semantics is used.
38 template<typename GridT>
40 
41 /// @brief This host class allows for sequential access to nodes in a NanoVDB tree
42 ///
43 /// @details Nodes are stored breadth first to allow for sequential access of nodes
44 /// at a particular level.
45 template<typename GridT>
46 class NodeManager
47 {
48  using TreeT = typename GridTree<GridT>::type;
49  template<int LEVEL>
50  using NodeT = typename NodeTrait<TreeT, LEVEL>::type;
51  using RootT = NodeT<3>;// root node
52  using Node2 = NodeT<2>;// upper internal node
53  using Node1 = NodeT<1>;// lower internal node
54  using Node0 = NodeT<0>;// leaf node
55 
56  template <typename T>
57  void sequential(T **nodes);
58 
59 public:
60  /// @brief Empty constructor
61  NodeManager();
62 
63  /// @brief Construction from a grid
64  NodeManager(GridT &grid);
65 
66  /// @brief Disallow copy construction
67  NodeManager(const NodeManager&) = delete;
68 
69  /// @brief Move constructor
71 
72  /// @brief Destructor
73  ~NodeManager() { this->clear(); }
74 
75  /// @brief Disallow copy assignment operator
76  NodeManager& operator=(const NodeManager&) = delete;
77 
78  /// @brief Move assignment operator
80 
81  /// @brief Return true of this instance is uninitialized
82  bool empty() const { return mGrid == nullptr; }
83 
84  /// @brief Return the memory footprint in bytes of this instance
85  inline size_t memUsage() const;
86 
87  /// @brief Return a pointer to the grid, or NULL if it is uninitialized
88  GridT* grid() { return mGrid; }
89 
90  /// @brief Return a pointer to the tree, or NULL if it is uninitialized
91  TreeT* tree() { return mTree; }
92 
93  /// @brief Return a pointer to the root, or NULL if it is uninitialized
94  RootT* root() { return mRoot; }
95 
96  /// @brief Return the number of tree nodes at the specified level
97  uint64_t nodeCount(int level) const { return mNodeCount[level]; }
98 
99  /// @brief Return the i'th leaf node
100  ///
101  /// @warning Never call this method is the NodeManager is un-initialized
102  Node0* leaf( uint32_t i) const { return mLeafs[i]; }
103 
104  /// @brief Return the i'th lower internal node
105  ///
106  /// @warning Never call this method is the NodeManager is un-initialized
107  Node1* lower(uint32_t i) const { return mLower[i]; }
108 
109  /// @brief Return the i'th upper internal node
110  ///
111  /// @warning Never call this method is the NodeManager is un-initialized
112  Node2* upper(uint32_t i) const { return mUpper[i]; }
113 
114 private:
115 
116  void clear();
117 
118  GridT* mGrid;
119  TreeT* mTree;
120  RootT* mRoot;
121  uint64_t mNodeCount[3];
122  Node2** mUpper;
123  Node1** mLower;
124  Node0** mLeafs;
125 }; // NodeManager<GridT> class
126 
127 template<typename GridT>
129  : mGrid(nullptr)
130  , mTree(nullptr)
131  , mRoot(nullptr)
132  , mNodeCount{0,0,0}
133  , mUpper(nullptr)
134  , mLower(nullptr)
135  , mLeafs(nullptr)
136 {
137 }
138 
139 template<typename GridT>
141  : mGrid(&grid)
142  , mTree(&grid.tree())
143  , mRoot(&grid.tree().root())
144  , mNodeCount{mTree->nodeCount(0), mTree->nodeCount(1), mTree->nodeCount(2)}
145  , mUpper(new Node2*[mNodeCount[2]])
146  , mLower(new Node1*[mNodeCount[1]])
147  , mLeafs(new Node0*[mNodeCount[0]])
148 
149 {
150  if (Node0::FIXED_SIZE && Node1::FIXED_SIZE && Node2::FIXED_SIZE &&// resolved at compile-time
151  grid.isBreadthFirst()) {
152 #if 1
153  invoke([&](){this->sequential(mLeafs);},
154  [&](){this->sequential(mLower);},
155  [&](){this->sequential(mUpper);});
156 #else
157  this->sequential(mLeafs);
158  this->sequential(mLower);
159  this->sequential(mUpper);
160 #endif
161  } else {
162  auto **ptr2 = mUpper;
163  auto **ptr1 = mLower;
164  auto **ptr0 = mLeafs;
165  auto *data3 = mRoot->data();
166  // Performs depth first traversal but breadth first insertion
167  for (uint32_t i=0, size=data3->mTableSize; i<size; ++i) {
168  auto *tile = data3->tile(i);
169  if (!tile->isChild()) continue;
170  Node2 *node2 = data3->getChild(tile);
171  *ptr2++ = node2;
172  auto *data2 = node2->data();
173  for (auto it2 = data2->mChildMask.beginOn(); it2; ++it2) {
174  Node1 *node1 = data2->getChild(*it2);
175  *ptr1++ = node1;
176  auto *data1 = node1->data();
177  for (auto it1 = data1->mChildMask.beginOn(); it1; ++it1) {
178  Node0 *node0 = data1->getChild(*it1);
179  *ptr0++ = node0;
180  }// loop over child nodes of the lower internal node
181  }// loop over child nodes of the upper internal node
182  }// loop over child nodes of the root node
183  }
184 }
185 
186 template<typename GridT>
188  : mGrid(other.mGrid)
189  , mTree(other.mTree)
190  , mRoot(other.mRoot)
191  , mNodeCount{other.mNodeCount[0],other.mNodeCount[1],other.mNodeCount[2]}
192  , mUpper(other.mUpper)
193  , mLower(other.mLower)
194  , mLeafs(other.mLeafs)
195 {
196  other.mGrid = nullptr;
197  other.mTree = nullptr;
198  other.mRoot = nullptr;
199  other.mNodeCount[0] = 0;
200  other.mNodeCount[1] = 0;
201  other.mNodeCount[2] = 0;
202  other.mUpper = nullptr;
203  other.mLower = nullptr;
204  other.mLeafs = nullptr;
205 }
206 
207 template<typename GridT>
209 {
210  this->clear();
211  mGrid = other.mGrid;
212  mTree = other.mTree;
213  mRoot = other.mRoot;
214  mNodeCount[0] = other.mNodeCount[0];
215  mNodeCount[1] = other.mNodeCount[1];
216  mNodeCount[2] = other.mNodeCount[2];
217  mUpper = other.mUpper;
218  mLower = other.mLower;
219  mLeafs = other.mLeafs;
220 
221  other.mGrid = nullptr;
222  other.mTree = nullptr;
223  other.mRoot = nullptr;
224  other.mNodeCount[0] = 0;
225  other.mNodeCount[1] = 0;
226  other.mNodeCount[2] = 0;
227  other.mUpper = nullptr;
228  other.mLower = nullptr;
229  other.mLeafs = nullptr;
230 
231  return *this;
232 }
233 
234 template<typename GridT>
236 {
237  delete [] mUpper;
238  delete [] mLower;
239  delete [] mLeafs;
240 }
241 
242 template<typename GridT>
244 {
245  return sizeof(*this) +
246  mNodeCount[0]*sizeof(Node0*) +
247  mNodeCount[1]*sizeof(Node1*) +
248  mNodeCount[2]*sizeof(Node2*);
249 }
250 
251 template<typename GridT>
253 {
254  NodeManager<GridT> mgr(grid);
255  return mgr;// // is converted to r-value so return value is move constructed!
256 }
257 
258 
259 template<typename GridT>
260 template <typename T>
261 void NodeManager<GridT>::sequential(T **nodes)
262 {
263  NANOVDB_ASSERT(mGrid->template isSequential<T>());
264  auto *ptr = mTree->template getFirstNode<T>();
265  uint64_t n = mNodeCount[T::LEVEL] / 4;
266  while (n--) {// loop unrolling
267  *nodes++ = ptr++;
268  *nodes++ = ptr++;
269  *nodes++ = ptr++;
270  *nodes++ = ptr++;
271  }
272  n = mNodeCount[T::LEVEL] % 4;
273  while (n--) {// loop reminder
274  *nodes++ = ptr++;
275  }
276 }
277 
278 //////////////////////////////////////////////////////////////////////////////
279 
280 template<typename GridT>
281 class LeafManager
282 {
283  using LeafT = typename NodeTrait<typename GridTree<GridT>::type, 0>::type;
284 
285 public:
286  /// @brief Empty constructor
287  LeafManager() : mGrid(nullptr), mSize(0), mLeafs(nullptr) {}
288 
289  /// @brief Construction from a grid
290  LeafManager(GridT &grid);
291 
292  /// @brief Disallow copy construction
293  LeafManager(const LeafManager&) = delete;
294 
295  /// @brief Move constructor
297 
298  /// @brief Destructor
299  ~LeafManager() { delete [] mLeafs; }
300 
301  /// @brief Disallow copy assignment operator
302  LeafManager& operator=(const LeafManager&) = delete;
303 
304  /// @brief Move assignment operator
306 
307  /// @brief Return true of this instance is un-initialized
308  bool empty() const { return mGrid == nullptr; }
309 
310  /// @brief Return the memory footprint in bytes of this instance
311  size_t memUsage() const { return sizeof(*this) + mSize*sizeof(LeafT*); }
312 
313  /// @brief Return a pointer to the grid, or NULL if it is uninitialized
314  GridT* grid() { return mGrid; }
315 
316  /// @brief Return the number of leaf nodes
317  uint32_t size() const { return mSize; };
318 
319  /// @brief Return the i'th leaf node
320  ///
321  /// @warning Never call this method is the LeafManager is uninitialized
322  LeafT* operator[](uint32_t i) const { return mLeafs[i]; };
323 
324 private:
325 
326  GridT *mGrid;
327  uint32_t mSize;
328  LeafT **mLeafs;
329 
330 }; // LeafManager<GridT> class
331 
332 template<typename GridT>
334  : mGrid(&grid), mSize(grid.tree().nodeCount(0)), mLeafs(nullptr)
335 {
336  if (mSize>0) {
337  mLeafs = new LeafT*[mSize];
338  auto **leafs = mLeafs;
339  if (grid.template isSequential<LeafT>()) {
340  auto *ptr = grid.tree().template getFirstNode<LeafT>();
341  uint64_t n = mSize / 4;
342  while (n--) {// loop unrolling
343  *leafs++ = ptr++;
344  *leafs++ = ptr++;
345  *leafs++ = ptr++;
346  *leafs++ = ptr++;
347  }
348  n = mSize % 4;
349  while (n--) {// loop reminder
350  *leafs++ = ptr++;
351  }
352  } else {
353  auto *data3 = grid.tree().root().data();
354  for (uint32_t i=0, size=data3->mTableSize; i<size; ++i) {
355  auto *tile = data3->tile(i);
356  if (!tile->isChild()) continue;
357  auto *data2 = data3->getChild(tile)->data();
358  for (auto it2 = data2->mChildMask.beginOn(); it2; ++it2) {
359  auto *data1 = data2->getChild(*it2)->data();
360  for (auto it1 = data1->mChildMask.beginOn(); it1; ++it1) {
361  *leafs++ = data1->getChild(*it1);
362  }// loop over child nodes of the lower internal node
363  }// loop over child nodes of the upper internal node
364  }// loop over child nodes of the root node
365  }
366  }
367 }
368 
369 template<typename GridT>
371 {
372  mGrid = other.mGrid;
373  mSize = other.mSize;
374  mLeafs = other.mLeafs;
375  other.mGrid = nullptr;
376  other.mSize = 0;
377  other.mLeafs = nullptr;
378 }
379 
380 template<typename GridT>
382 {
383  mGrid = other.mGrid;
384  mSize = other.mSize;
385  delete [] mLeafs;
386  mLeafs = other.mLeafs;
387  other.mGrid = nullptr;
388  other.mSize = 0;
389  other.mLeafs = nullptr;
390  return *this;
391 }
392 
393 template<typename GridT>
395 {
396  LeafManager<GridT> mgr(grid);
397  return mgr;// // is converted to r-value so return value is move constructed!
398 }
399 
400 } // namespace nanovdb
401 
402 #endif // NANOVDB_NODEMANAGER_H_HAS_BEEN_INCLUDED
GridT * grid()
Return a pointer to the grid, or NULL if it is uninitialized.
Definition: NodeManager.h:314
A unified wrapper for tbb::parallel_invoke and a naive std::thread analog.
LeafNanager maintains a linear array of leaf nodes.
Definition: NodeManager.h:31
Node2 * upper(uint32_t i) const
Return the i&#39;th upper internal node.
Definition: NodeManager.h:112
NodeManager< GridT > createNodeMgr(GridT &grid)
creates a NodeManager from a grid. Move semantics is used.
Definition: NodeManager.h:252
Definition: NanoVDB.h:184
Struct to derive node type from its level in a given grid, tree or root while perserving constness...
Definition: NanoVDB.h:2097
typename GridT::TreeType type
Definition: NanoVDB.h:2530
LeafManager & operator=(const LeafManager &)=delete
Disallow copy assignment operator.
NodeManager & operator=(const NodeManager &)=delete
Disallow copy assignment operator.
GridT * grid()
Return a pointer to the grid, or NULL if it is uninitialized.
Definition: NodeManager.h:88
bool empty() const
Return true of this instance is uninitialized.
Definition: NodeManager.h:82
bool empty() const
Return true of this instance is un-initialized.
Definition: NodeManager.h:308
~LeafManager()
Destructor.
Definition: NodeManager.h:299
Node0 * leaf(uint32_t i) const
Return the i&#39;th leaf node.
Definition: NodeManager.h:102
#define NANOVDB_ASSERT(x)
Definition: NanoVDB.h:149
RootT * root()
Return a pointer to the root, or NULL if it is uninitialized.
Definition: NodeManager.h:94
size_t memUsage() const
Return the memory footprint in bytes of this instance.
Definition: NodeManager.h:243
NodeNanager maintains separate linear arrays of the three nodes types.
Definition: NodeManager.h:27
LeafT * operator[](uint32_t i) const
Return the i&#39;th leaf node.
Definition: NodeManager.h:322
uint64_t nodeCount(int level) const
Return the number of tree nodes at the specified level.
Definition: NodeManager.h:97
Node1 * lower(uint32_t i) const
Return the i&#39;th lower internal node.
Definition: NodeManager.h:107
NodeManager()
Empty constructor.
Definition: NodeManager.h:128
size_t memUsage() const
Return the memory footprint in bytes of this instance.
Definition: NodeManager.h:311
~NodeManager()
Destructor.
Definition: NodeManager.h:73
uint32_t size() const
Return the number of leaf nodes.
Definition: NodeManager.h:317
TreeT * tree()
Return a pointer to the tree, or NULL if it is uninitialized.
Definition: NodeManager.h:91
LeafManager< GridT > createLeafMgr(GridT &grid)
creates a LeafManager from a grid. Move semantics is used.
Definition: NodeManager.h:394
LeafManager()
Empty constructor.
Definition: NodeManager.h:287
int invoke(const Func &taskFunc1, Rest...taskFuncN)
Definition: Invoke.h:64