concurrenthistogram.h 7.26 KB
Newer Older
1
2
3
#ifndef CONCURRENTHISTOGRAM_H__
#define CONCURRENTHISTOGRAM_H__

4

5
6
#include "tgt/assert.h"
#include "tgt/logmanager.h"
7
8
9
#include "tgt/tgt_math.h"
#include "tbb/include/tbb/atomic.h"

schultezub's avatar
schultezub committed
10
namespace campvis {
11

12
13
14
15
16
17
18
19
    /**
     * Generic implementation of thread-safe n-D histograms.
     * After successfull creation ConcurrentGenericHistogramND ensures:
     *  * Calling addSample() is thread-safe.
     * 
     * \tparam  T   Base data type of the histogram elements
     * \tparam  ND  Dimensionality of the histogram
     */
20
21
22
    template<typename T, size_t ND>
    class ConcurrentGenericHistogramND {
    public:
23
24
25
26
27
28
        /**
         * Creates a new ND-histogram with the given bounds and number of buckets.
         * \param   mins        Array of mininum values for each dimension (must have at least ND elements)
         * \param   maxs        Array of maximum values for each dimension (must have at least ND elements)
         * \param   numBuckets  Array of number of buckets for each dimension (must have at least ND elements)
         */
29
30
        ConcurrentGenericHistogramND(T mins[ND], T maxs[ND], size_t numBuckets[ND]);

31
32
33
        /**
         * Destructor
         */
34
35
        virtual ~ConcurrentGenericHistogramND();

36
37
38
39
40
41
42
        /**
         * Returns the number of buckets for the given dimension.
         * \param   dimension   Dimension, must be smaller than ND.
         * \return  _numBuckets[dimension]
         */
        size_t getNumBuckets(size_t dimension) const;

43
44
45
46
47
48
49
50
51
52
53
        /**
         * Adds the given sample to the histogram.
         * \note    This method is thread-safe.
         * \param   sample  Sample to add, array of the values for each dimension (must have at least ND elements)
         */
        void addSample(T sample[ND]);

        /**
         * Returns a const pointer to the raw data.
         * \return  _buckets
         */
54
55
        const tbb::atomic<size_t>* getBuckets() const { return _buckets; };

56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
        /**
         * Returns the number of elements of the bucket with the given index.
         * \param   index   Array index of the bucket to return.
         * \return  _buckets[index]
         */
        size_t getNumElements(size_t index) const { return _buckets[index]; };

        /**
         * Returns the number of elements in the given bucket.
         * \param   bucket[ND]  Array of the bucket number for each dimension (must have at least ND elements)
         * \return  The number of elements in the given bucket.
         */
        size_t getNumElements(size_t bucket[ND]);

        /**
         * Get the total number of samples in this histogram.
         * \return  _numSamples
         */
74
75
        size_t getNumSamples() const { return _numSamples; };

76
77
78
79
80
81
        /**
         * Returns the number of elements in the bucket with the most samples.
         * \return  _maxFilling
         */
        size_t getMaxFilling() const { return _maxFilling; };

82
    protected:
83
84
85
86
87
88
        /**
         * Transforms the sample value for the given dimension into the corresponding bucket number.
         * \param   dimension   Dimension
         * \param   sample      Sample value to transform
         * \return  The bucket number for \a sample in the given dimension.
         */
89
90
        size_t getBucketNumber(size_t dimension, T sample) const;

91
92
93
94
95
        /**
         * Transforms the array of bucket numbers into the corresponding array index in _buckets.
         * \param   bucketNumbers   Array of the bucket number for each dimension (must have at least ND elements).
         * \return  The array index for the given bucket numbers.
         */
96
97
        size_t getArrayIndex(size_t* bucketNumbers) const;

98
99
100
101
102
103
        T _min[ND];                         ///< minimum value for each dimension
        T _max[ND];                         ///< maximum value for each dimension
        size_t _numBuckets[ND];             ///< number of buckets for each dimension
        size_t _arraySize;                  ///< size of _buckets (total number of buckets)
        tbb::atomic<size_t>* _buckets;      ///< array of the buckets storing the histogram
        tbb::atomic<size_t> _numSamples;    ///< total number of sampled elements
104
        tbb::atomic<size_t> _maxFilling;    ///< number of elements in the bucket with the most samples
105
106
107
108
109
    };

// ================================================================================================

    template<typename T, size_t ND>
schultezub's avatar
schultezub committed
110
    campvis::ConcurrentGenericHistogramND<T, ND>::ConcurrentGenericHistogramND(T mins[ND], T maxs[ND], size_t numBuckets[ND]) 
111
112
113
114
115
116
117
118
119
120
121
122
123
124
        : _arraySize(1)
        , _buckets(0)
    {
        for (size_t i = 0; i < ND; ++i) {
            _min[i] = mins[i];
            _max[i] = maxs[i];
            tgtAssert(_min[i] < _max[i], "Min must be smaller than Max!");
            _numBuckets[i] = numBuckets[i];
            _arraySize *= _numBuckets[i];
        }

        _buckets = new tbb::atomic<size_t>[_arraySize];
        for (size_t i = 0; i < _arraySize; ++i)
            _buckets[i] = 0;
125
126
        _numSamples = 0;
        _maxFilling = 0;
127
128
129
    }

    template<typename T, size_t ND>
schultezub's avatar
schultezub committed
130
    campvis::ConcurrentGenericHistogramND<T, ND>::~ConcurrentGenericHistogramND() {
131
132
133
        delete [] _buckets;
    }

134
    template<typename T, size_t ND>
schultezub's avatar
schultezub committed
135
    size_t campvis::ConcurrentGenericHistogramND<T, ND>::getNumBuckets(size_t dimension) const {
136
137
138
139
        tgtAssert(dimension < ND, "Dimension out of bounds.");
        return _numBuckets[dimension];
    }

140
    template<typename T, size_t ND>
schultezub's avatar
schultezub committed
141
    void campvis::ConcurrentGenericHistogramND<T, ND>::addSample(T sample[ND]) {
142
143
        size_t bucketNumbers[ND];
        for(int i = 0; i < ND; ++i)
144
            bucketNumbers[i] = getBucketNumber(i, sample[i]);
145
146
147
148
149

        size_t index = getArrayIndex(bucketNumbers);
        ++(_buckets[index]);
        ++_numSamples;

150
151
152
153
154
155
156
157
        // thread-safe update of _maxFilling 
        size_t old = 0;
        do {
            old = _maxFilling;
            if (old >= _buckets[index])
                break;
        } while (_maxFilling.compare_and_swap(_buckets[index], old) != old);
    }
158
159

    template<typename T, size_t ND>
schultezub's avatar
schultezub committed
160
    size_t campvis::ConcurrentGenericHistogramND<T, ND>::getBucketNumber(size_t dimension, T sample) const {
161
        tgtAssert(dimension < ND, "Dimension out of bounds.");
schultezub's avatar
schultezub committed
162
#ifdef CAMPVIS_DEBUG
163
        if (sample < _min[dimension] || sample > _max[dimension])
schultezub's avatar
schultezub committed
164
            LWARNINGC("CAMPVis.core.tools.ConcurrentGenericHistogramND", "Added sample " << sample << " out of bounds for dimension " << dimension << ".");
165
#endif
166
167
168
169
170
        double ratio = static_cast<double>(sample - _min[dimension]) / static_cast<double>(_max[dimension] - _min[dimension]);
        return static_cast<size_t>(tgt::clamp(static_cast<int>(ratio * _numBuckets[dimension]), static_cast<int>(0), static_cast<int>(_numBuckets[dimension] - 1)));
    }

    template<typename T, size_t ND>
schultezub's avatar
schultezub committed
171
    size_t campvis::ConcurrentGenericHistogramND<T, ND>::getArrayIndex(size_t* bucketNumbers) const {
172
173
174
175
176
177
178
179
180
181
182
        size_t index = 0;
        size_t multiplier = 1;
        for (size_t i = 0; i < ND; ++i) {
            index += multiplier * bucketNumbers[i];
            multiplier *= _numBuckets[i];
        }
        return index;
    }


}
183
184

#endif // CONCURRENTHISTOGRAM_H__