GCC Code Coverage Report

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