HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
PrefixSum.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 PrefixSum.h
6 
7  \author Ken Museth
8 
9  \date March 12, 2023
10 
11  \brief Multi-threaded implementations of inclusive prefix sum
12 
13  \note An exclusive prefix sum is simply an array starting with zero
14  followed by the elements in the inclusive prefix sum, minus its
15  last entry which is the sum of all the input elements.
16 */
17 
18 #ifndef NANOVDB_PREFIX_SUM_H_HAS_BEEN_INCLUDED
19 #define NANOVDB_PREFIX_SUM_H_HAS_BEEN_INCLUDED
20 
21 #include "Range.h"// for Range1D
22 #include <vector>
23 #include <functional>// for std::plus
24 
25 #ifdef NANOVDB_USE_TBB
26 #include <tbb/parallel_scan.h>
27 #endif
28 
29 namespace nanovdb {
30 
31 /// @brief Computes inclusive prefix sum of a vector
32 /// @tparam T Type of the elements in the input/out vector
33 /// @tparam OpT Type of operation performed on each element (defaults to sum)
34 /// @param vec input and output vector
35 /// @param threaded if true multi-threading is used
36 /// @note Inclusive prefix sum: for (i=1; i<N; ++i) vec[i] += vec[i-1]
37 /// @return sum of all input elements, which is also the last element of the inclusive prefix sum
38 template<typename T, typename OpT = std::plus<T>>
39 T prefixSum(std::vector<T> &vec, bool threaded = true, OpT op = OpT());
40 
41 /// @brief An inclusive scan includes in[i] when computing out[i]
42 /// @note Inclusive prefix operation: for (i=1; i<N; ++i) vec[i] = Op(vec[i],vec[i-1])
43 template<typename T, typename Op>
44 void inclusiveScan(T *array, size_t size, const T &identity, bool threaded, Op op)
45 {
46 #ifndef NANOVDB_USE_TBB
47  threaded = false;
48  (void)identity;// avoids compiler warning
49 #endif
50 
51  if (threaded) {
52 #ifdef NANOVDB_USE_TBB
53  using RangeT = tbb::blocked_range<size_t>;
54  tbb::parallel_scan(RangeT(0, size), identity,
55  [&](const RangeT &r, T sum, bool is_final_scan)->T {
56  T tmp = sum;
57  for (size_t i = r.begin(); i < r.end(); ++i) {
58  tmp = op(tmp, array[i]);
59  if (is_final_scan) array[i] = tmp;
60  }
61  return tmp;
62  },[&](const T &a, const T &b) {return op(a, b);}
63  );
64 #endif
65  } else { // serial inclusive prefix operation
66  for (size_t i=1; i<size; ++i) array[i] = op(array[i], array[i-1]);
67  }
68 }// inclusiveScan
69 
70 template<typename T, typename OpT>
71 T prefixSum(std::vector<T> &vec, bool threaded, OpT op)
72 {
73  inclusiveScan(vec.data(), vec.size(), T(0), threaded, op);
74  return vec.back();// sum of all input elements
75 }// prefixSum
76 
77 }// namespace nanovdb
78 
79 #endif // NANOVDB_PREFIX_SUM_H_HAS_BEEN_INCLUDED
void
Definition: png.h:1083
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1222
T prefixSum(std::vector< T > &vec, bool threaded=true, OpT op=OpT())
Computes inclusive prefix sum of a vector.
Definition: PrefixSum.h:71
Custom Range class that is compatible with the tbb::blocked_range classes.
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
GLsizeiptr size
Definition: glcorearb.h:664
void inclusiveScan(T *array, size_t size, const T &identity, bool threaded, Op op)
An inclusive scan includes in[i] when computing out[i].
Definition: PrefixSum.h:44
GLboolean r
Definition: glcorearb.h:1222