OpenVDB 11.0.0
Loading...
Searching...
No Matches
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
29namespace 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
38template<typename T, typename OpT = std::plus<T>>
39T 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])
43template<typename T, typename Op>
44void 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
70template<typename T, typename OpT>
71T 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
Custom Range class that is compatible with the tbb::blocked_range classes.
Definition NanoVDB.h:247
T prefixSum(std::vector< T > &vec, bool threaded=true, OpT op=OpT())
Computes inclusive prefix sum of a vector.
Definition PrefixSum.h:71
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