GCC Code Coverage Report

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