GCC Code Coverage Report

Directory: cvmfs/
File: cvmfs/util/algorithm.h
Date: 2024-04-28 02:33:07
Exec Total Coverage
Lines: 42 51 82.4%
Branches: 27 41 65.9%
Line Branch Exec Source
1 /**
2 * This file is part of the CernVM File System.
3 */
4
5 #ifndef CVMFS_UTIL_ALGORITHM_H_
6 #define CVMFS_UTIL_ALGORITHM_H_
7
8 #include <sys/time.h>
9
10 #include <algorithm>
11 #include <string>
12 #include <utility>
13 #include <vector>
14
15 #include "util/atomic.h"
16 #include "util/export.h"
17 #include "util/murmur.hxx"
18 #include "util/platform.h"
19 #include "util/prng.h"
20 #include "util/single_copy.h"
21
22 #ifdef CVMFS_NAMESPACE_GUARD
23 namespace CVMFS_NAMESPACE_GUARD {
24 #endif
25
26
27 CVMFS_EXPORT double DiffTimeSeconds(struct timeval start, struct timeval end);
28
29 // Bitfield manipulation for different integer types T
30 template <typename T>
31 8 inline void SetBit(unsigned int bit, T *field) {
32 8 *field |= static_cast<T>(1) << bit;
33 8 }
34
35 template <typename T>
36 8 inline void ClearBit(unsigned int bit, T *field) {
37 8 *field &= ~(static_cast<T>(1) << bit);
38 8 }
39
40 template <typename T>
41 12 inline bool TestBit(unsigned int bit, const T field) {
42 12 return field & (static_cast<T>(1) << bit);
43 }
44
45
46 /**
47 * Knuth's random shuffle algorithm.
48 */
49 template <typename T>
50 5 std::vector<T> Shuffle(const std::vector<T> &input, Prng *prng) {
51 5 std::vector<T> shuffled(input);
52 5 unsigned N = shuffled.size();
53 // No shuffling for the last element
54
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 3 times.
 20145 for (unsigned i = 0; i < N; ++i) {
55 20140 const unsigned swap_idx = i + prng->Next(N - i);
56 20140 std::swap(shuffled[i], shuffled[swap_idx]);
57 }
58 5 return shuffled;
59 }
60
61
62 /**
63 * Sorts the vector tractor and applies the same permutation to towed. Both
64 * vectors have to be of the same size. Type T must be sortable (< operator).
65 * Uses insertion sort (n^2), only efficient for small vectors.
66 */
67 template <typename T, typename U>
68 12 void SortTeam(std::vector<T> *tractor, std::vector<U> *towed) {
69
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 assert(tractor);
70
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 assert(towed);
71
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 12 times.
 12 assert(tractor->size() == towed->size());
72 12 int N = tractor->size();
73
74 // Insertion sort on both, tractor and towed
75
3/4
✓ Branch 0 taken 87 times.
✓ Branch 1 taken 12 times.
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 104 for (int i = 1; i < N; ++i) {
76
1/2
✓ Branch 2 taken 87 times.
✗ Branch 3 not taken.
 92 T val_tractor = (*tractor)[i];
77
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 92 U val_towed = (*towed)[i];
78 int pos;
79
7/7
✓ Branch 0 taken 1081 times.
✓ Branch 1 taken 5 times.
✓ Branch 3 taken 3 times.
✓ Branch 4 taken 994 times.
✓ Branch 5 taken 87 times.
✓ Branch 6 taken 996 times.
✓ Branch 7 taken 87 times.
 1086 for (pos = i-1; (pos >= 0) && ((*tractor)[pos] > val_tractor); --pos) {
80
1/2
✓ Branch 3 taken 991 times.
✗ Branch 4 not taken.
 994 (*tractor)[pos+1] = (*tractor)[pos];
81
1/2
✓ Branch 3 taken 3 times.
✗ Branch 4 not taken.
 994 (*towed)[pos+1] = (*towed)[pos];
82 }
83
1/2
✓ Branch 2 taken 87 times.
✗ Branch 3 not taken.
 92 (*tractor)[pos+1] = val_tractor;
84
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 92 (*towed)[pos+1] = val_towed;
85 }
86 12 }
87
88
89 template <typename hashed_type>
90 struct hash_murmur {
91 ✗ size_t operator() (const hashed_type key) const {
92 #ifdef __x86_64__
93 ✗ return MurmurHash64A(&key, sizeof(key), 0x9ce603115bba659bLLU);
94 #else
95 return MurmurHash2(&key, sizeof(key), 0x07387a4f);
96 #endif
97 }
98 };
99
100
101 /**
102 * Very simple StopWatch implementation. Currently the implementation does not
103 * allow a restart of a stopped watch. You should always reset the clock before
104 * you reuse it.
105 *
106 * Stopwatch watch();
107 * watch.Start();
108 * // do nasty thing
109 * watch.Stop();
110 * printf("%f", watch.GetTime());
111 */
112 class CVMFS_EXPORT StopWatch : SingleCopy {
113 public:
114 2 StopWatch() : running_(false) {}
115
116 void Start();
117 void Stop();
118 void Reset();
119
120 double GetTime() const;
121
122 private:
123 bool running_;
124 timeval start_, end_;
125 };
126
127
128 /**
129 * Log2Histogram is a simple implementation of
130 * log2 histogram data structure which stores
131 * and prints log2 histogram. It is used for
132 * getting and printing latency metrics of
133 * CVMFS fuse calls.
134 *
135 * Log2Histogram hist(2);
136 * hist.Add(1);
137 * hist.Add(2);
138 * hist.PrintLog2Histogram();
139 */
140
141 class CVMFS_EXPORT Log2Histogram {
142 friend class UTLog2Histogram;
143
144 public:
145 explicit Log2Histogram(unsigned int nbins);
146
147 1048598 void Add(uint64_t value) {
148 unsigned int i;
149 1048598 const unsigned int n = this->bins_.size() - 1;
150
151
2/2
✓ Branch 0 taken 15728783 times.
✓ Branch 1 taken 5 times.
 15728788 for (i = 1; i <= n; i++) {
152
2/2
✓ Branch 1 taken 1048593 times.
✓ Branch 2 taken 14680190 times.
 15728783 if (value < this->boundary_values_[i]) {
153 1048593 atomic_inc32(&(this->bins_[i]));
154 1048593 return;
155 }
156 }
157
158 5 atomic_inc32(&(this->bins_[0])); // add to overflow bin.
159 }
160
161 /**
162 * Returns the total number of elements in the histogram
163 */
164 13 inline uint64_t N() {
165 13 uint64_t n = 0;
166 unsigned int i;
167
2/2
✓ Branch 1 taken 219 times.
✓ Branch 2 taken 13 times.
 232 for (i = 0; i <= this->bins_.size() - 1; i++) {
168 219 n += static_cast<unsigned int>(atomic_read32(&(this->bins_[i])));
169 }
170 13 return n;
171 }
172
173 /**
174 * compute the quantile of order n
175 */
176 unsigned int GetQuantile(float n);
177
178 std::string ToString();
179
180 void PrintLog2Histogram();
181
182 private:
183 std::vector<atomic_int32> bins_;
184 // boundary_values_ handle the largest value a certain
185 // bin can store in itself.
186 std::vector<unsigned int> boundary_values_;
187 };
188
189 /**
190 * UTLog2Histogram class is a helper for the unit tests
191 * to extract internals from Log2Histogram.
192 */
193 class CVMFS_EXPORT UTLog2Histogram {
194 public:
195 std::vector<atomic_int32> GetBins(const Log2Histogram &h);
196 };
197
198
199 class CVMFS_EXPORT HighPrecisionTimer : SingleCopy {
200 public:
201 static bool g_is_enabled; // false by default
202
203 ✗ explicit HighPrecisionTimer(Log2Histogram *recorder)
204 ✗ : timestamp_start_(g_is_enabled ? platform_monotonic_time_ns() : 0)
205 ✗ , recorder_(recorder)
206 ✗ { }
207
208 ✗ ~HighPrecisionTimer() {
209 ✗ if (g_is_enabled)
210 ✗ recorder_->Add(platform_monotonic_time_ns() - timestamp_start_);
211 }
212
213 private:
214 uint64_t timestamp_start_;
215 Log2Histogram *recorder_;
216 };
217
218 #ifdef CVMFS_NAMESPACE_GUARD
219 } // namespace CVMFS_NAMESPACE_GUARD
220 #endif
221
222 #endif // CVMFS_UTIL_ALGORITHM_H_
223