Currently job artifacts in CI/CD pipelines on LRZ GitLab never expire. Starting from Wed 26.1.2022 the default expiration time will be 30 days (GitLab default). Currently existing artifacts in already completed jobs will not be affected by the change. The latest artifacts for all jobs in the latest successful pipelines will be kept. More information: https://gitlab.lrz.de/help/user/admin_area/settings/continuous_integration.html#default-artifacts-expiration

concurrenthistogram.h 8.62 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
121
        size_t getArrayIndex(size_t* bucketNumbers) const;

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
167
        size_t bucketNumbers[ND];
        for(int 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

        if (sample < _min[dimension] || sample > _max[dimension]) {
            return _numBuckets[dimension];
#ifdef CAMPVIS_DEBUG_NOTNOW
schultezub's avatar
schultezub committed
190
            LWARNINGC("CAMPVis.core.tools.ConcurrentGenericHistogramND", "Added sample " << sample << " out of bounds for dimension " << dimension << ".");
191
#endif
192
193
        }

194
195
196
197
198
        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
199
    size_t campvis::ConcurrentGenericHistogramND<T, ND>::getArrayIndex(size_t* bucketNumbers) 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__