2.12.2021, 9:00 - 11:00: Due to updates GitLab may be unavailable for some minutes between 09:00 and 11:00.

concurrenthistogram.h 8.5 KB
Newer Older
schultezub's avatar
schultezub committed
1
2
3
4
// ================================================================================================
// 
// This file is part of the CAMPVis Software Framework.
// 
5
// If not explicitly stated otherwise: Copyright (C) 2012-2014, all rights reserved,
schultezub's avatar
schultezub committed
6
7
//      Christian Schulte zu Berge <christian.szb@in.tum.de>
//      Chair for Computer Aided Medical Procedures
8
9
//      Technische Universitaet Muenchen
//      Boltzmannstr. 3, 85748 Garching b. Muenchen, Germany
10
// 
schultezub's avatar
schultezub committed
11
12
// For a full list of authors and contributors, please refer to the file "AUTHORS.txt".
// 
13
14
15
16
// Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file 
// except in compliance with the License. You may obtain a copy of the License at
// 
// http://www.apache.org/licenses/LICENSE-2.0
schultezub's avatar
schultezub committed
17
// 
18
19
20
21
// Unless required by applicable law or agreed to in writing, software distributed under the 
// License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, 
// either express or implied. See the License for the specific language governing permissions 
// and limitations under the License.
schultezub's avatar
schultezub committed
22
23
24
// 
// ================================================================================================

25
26
27
#ifndef CONCURRENTHISTOGRAM_H__
#define CONCURRENTHISTOGRAM_H__

28

29
30
#include "tgt/assert.h"
#include "tgt/logmanager.h"
31
#include "tgt/tgt_math.h"
32
#include <tbb/atomic.h>
33

schultezub's avatar
schultezub committed
34
namespace campvis {
35

36
37
    /**
     * Generic implementation of thread-safe n-D histograms.
38
     * After successful creation ConcurrentGenericHistogramND ensures:
39
40
41
42
43
     *  * Calling addSample() is thread-safe.
     * 
     * \tparam  T   Base data type of the histogram elements
     * \tparam  ND  Dimensionality of the histogram
     */
44
45
46
    template<typename T, size_t ND>
    class ConcurrentGenericHistogramND {
    public:
47
48
49
50
51
52
        /**
         * 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)
         */
53
54
        ConcurrentGenericHistogramND(T mins[ND], T maxs[ND], size_t numBuckets[ND]);

55
56
57
        /**
         * Destructor
         */
58
59
        virtual ~ConcurrentGenericHistogramND();

60
61
62
63
64
65
66
        /**
         * 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;

67
68
69
70
71
72
73
74
75
76
77
        /**
         * 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
         */
78
79
        const tbb::atomic<size_t>* getBuckets() const { return _buckets; };

80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
        /**
         * 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
         */
98
99
        size_t getNumSamples() const { return _numSamples; };

100
101
102
103
104
105
        /**
         * Returns the number of elements in the bucket with the most samples.
         * \return  _maxFilling
         */
        size_t getMaxFilling() const { return _maxFilling; };

106
    protected:
107
108
109
110
111
112
        /**
         * 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.
         */
113
114
        size_t getBucketNumber(size_t dimension, T sample) const;

115
116
117
118
119
        /**
         * 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.
         */
120
        size_t getArrayIndex(size_t bucketNumbers[ND]) const;
121

122
123
124
125
126
127
        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
128
        tbb::atomic<size_t> _maxFilling;    ///< number of elements in the bucket with the most samples
129
130
131
132
133
    };

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

    template<typename T, size_t ND>
schultezub's avatar
schultezub committed
134
    campvis::ConcurrentGenericHistogramND<T, ND>::ConcurrentGenericHistogramND(T mins[ND], T maxs[ND], size_t numBuckets[ND]) 
135
136
137
138
139
140
141
142
143
144
145
        : _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];
        }

146
        _buckets = new tbb::atomic<size_t>[_arraySize + 1];
147
148
        for (size_t i = 0; i < _arraySize; ++i)
            _buckets[i] = 0;
149
150
        _numSamples = 0;
        _maxFilling = 0;
151
152
153
    }

    template<typename T, size_t ND>
schultezub's avatar
schultezub committed
154
    campvis::ConcurrentGenericHistogramND<T, ND>::~ConcurrentGenericHistogramND() {
155
156
157
        delete [] _buckets;
    }

158
    template<typename T, size_t ND>
schultezub's avatar
schultezub committed
159
    size_t campvis::ConcurrentGenericHistogramND<T, ND>::getNumBuckets(size_t dimension) const {
160
161
162
163
        tgtAssert(dimension < ND, "Dimension out of bounds.");
        return _numBuckets[dimension];
    }

164
    template<typename T, size_t ND>
schultezub's avatar
schultezub committed
165
    void campvis::ConcurrentGenericHistogramND<T, ND>::addSample(T sample[ND]) {
166
        size_t bucketNumbers[ND];
167
        for (size_t i = 0; i < ND; ++i)
168
            bucketNumbers[i] = getBucketNumber(i, sample[i]);
169
170
171
172
173

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

174
175
176
177
178
179
180
181
        // 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);
    }
182
183

    template<typename T, size_t ND>
schultezub's avatar
schultezub committed
184
    size_t campvis::ConcurrentGenericHistogramND<T, ND>::getBucketNumber(size_t dimension, T sample) const {
185
        tgtAssert(dimension < ND, "Dimension out of bounds.");
186
187
188
189
190

        if (sample < _min[dimension] || sample > _max[dimension]) {
            return _numBuckets[dimension];
        }

191
        double ratio = static_cast<double>(sample - _min[dimension]) / static_cast<double>(_max[dimension] - _min[dimension]);
192
193
194
195
        int toReturn = static_cast<int>(ratio * _numBuckets[dimension]);
        toReturn = std::max(toReturn, 0);
        toReturn = std::min(toReturn, static_cast<int>(_numBuckets[dimension]) - 1);
        return toReturn;
196
197
198
    }

    template<typename T, size_t ND>
199
    size_t campvis::ConcurrentGenericHistogramND<T, ND>::getArrayIndex(size_t bucketNumbers[ND]) const {
200
201
202
        size_t index = 0;
        size_t multiplier = 1;
        for (size_t i = 0; i < ND; ++i) {
203
204
205
            if (bucketNumbers[i] == _numBuckets[i])
                return _arraySize;

206
207
208
209
210
211
212
213
            index += multiplier * bucketNumbers[i];
            multiplier *= _numBuckets[i];
        }
        return index;
    }


}
214
215

#endif // CONCURRENTHISTOGRAM_H__