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 <string> |
13 |
|
|
#include <vector> |
14 |
|
|
|
15 |
|
|
#include "murmur.h" |
16 |
|
|
// TODO(jblomer): should be also part of algorithm |
17 |
|
|
#include "prng.h" |
18 |
|
|
#include "util/single_copy.h" |
19 |
|
|
|
20 |
|
|
|
21 |
|
|
#ifdef CVMFS_NAMESPACE_GUARD |
22 |
|
|
namespace CVMFS_NAMESPACE_GUARD { |
23 |
|
|
#endif |
24 |
|
|
|
25 |
|
|
|
26 |
|
|
double DiffTimeSeconds(struct timeval start, struct timeval end); |
27 |
|
|
|
28 |
|
|
|
29 |
|
|
/** |
30 |
|
|
* Knuth's random shuffle algorithm. |
31 |
|
|
*/ |
32 |
|
|
template <typename T> |
33 |
|
11 |
std::vector<T> Shuffle(const std::vector<T> &input, Prng *prng) { |
34 |
|
11 |
std::vector<T> shuffled(input); |
35 |
|
11 |
unsigned N = shuffled.size(); |
36 |
|
|
// No shuffling for the last element |
37 |
✓✓✓✓
|
80535 |
for (unsigned i = 0; i < N; ++i) { |
38 |
|
80524 |
const unsigned swap_idx = i + prng->Next(N - i); |
39 |
|
80524 |
std::swap(shuffled[i], shuffled[swap_idx]); |
40 |
|
|
} |
41 |
|
11 |
return shuffled; |
42 |
|
|
} |
43 |
|
|
|
44 |
|
|
|
45 |
|
|
/** |
46 |
|
|
* Sorts the vector tractor and applies the same permutation to towed. Both |
47 |
|
|
* vectors have to be of the same size. Type T must be sortable (< operator). |
48 |
|
|
* Uses insertion sort (n^2), only efficient for small vectors. |
49 |
|
|
*/ |
50 |
|
|
template <typename T, typename U> |
51 |
|
5 |
void SortTeam(std::vector<T> *tractor, std::vector<U> *towed) { |
52 |
✗✓✗✗
|
5 |
assert(tractor); |
53 |
✗✓✗✗
|
5 |
assert(towed); |
54 |
✗✗✓✗
|
5 |
assert(tractor->size() == towed->size()); |
55 |
|
5 |
unsigned N = tractor->size(); |
56 |
|
|
|
57 |
|
|
// Insertion sort on both, tractor and towed |
58 |
✗✓✓✗
✗✗✗ |
5 |
for (unsigned i = 1; i < N; ++i) { |
59 |
|
5 |
T val_tractor = (*tractor)[i]; |
60 |
|
5 |
U val_towed = (*towed)[i]; |
61 |
|
|
int pos; |
62 |
✓✓✓✓
✓✓✗✗
✗✗✗✗
|
8 |
for (pos = i-1; (pos >= 0) && ((*tractor)[pos] > val_tractor); --pos) { |
63 |
|
3 |
(*tractor)[pos+1] = (*tractor)[pos]; |
64 |
|
3 |
(*towed)[pos+1] = (*towed)[pos]; |
65 |
|
|
} |
66 |
|
5 |
(*tractor)[pos+1] = val_tractor; |
67 |
|
5 |
(*towed)[pos+1] = val_towed; |
68 |
|
|
} |
69 |
|
5 |
} |
70 |
|
|
|
71 |
|
|
|
72 |
|
|
template <typename hashed_type> |
73 |
|
|
struct hash_murmur { |
74 |
|
|
size_t operator() (const hashed_type key) const { |
75 |
|
|
#ifdef __x86_64__ |
76 |
|
|
return MurmurHash64A(&key, sizeof(key), 0x9ce603115bba659bLLU); |
77 |
|
|
#else |
78 |
|
|
return MurmurHash2(&key, sizeof(key), 0x07387a4f); |
79 |
|
|
#endif |
80 |
|
|
} |
81 |
|
|
}; |
82 |
|
|
|
83 |
|
|
|
84 |
|
|
/** |
85 |
|
|
* Very simple StopWatch implementation. Currently the implementation does not |
86 |
|
|
* allow a restart of a stopped watch. You should always reset the clock before |
87 |
|
|
* you reuse it. |
88 |
|
|
* |
89 |
|
|
* Stopwatch watch(); |
90 |
|
|
* watch.Start(); |
91 |
|
|
* // do nasty thing |
92 |
|
|
* watch.Stop(); |
93 |
|
|
* printf("%f", watch.GetTime()); |
94 |
|
|
*/ |
95 |
|
|
class StopWatch : SingleCopy { |
96 |
|
|
public: |
97 |
|
2 |
StopWatch() : running_(false) {} |
98 |
|
|
|
99 |
|
|
void Start(); |
100 |
|
|
void Stop(); |
101 |
|
|
void Reset(); |
102 |
|
|
|
103 |
|
|
double GetTime() const; |
104 |
|
|
|
105 |
|
|
private: |
106 |
|
|
bool running_; |
107 |
|
|
timeval start_, end_; |
108 |
|
|
}; |
109 |
|
|
|
110 |
|
|
|
111 |
|
|
#ifdef CVMFS_NAMESPACE_GUARD |
112 |
|
|
} // namespace CVMFS_NAMESPACE_GUARD |
113 |
|
|
#endif |
114 |
|
|
|
115 |
|
|
#endif // CVMFS_UTIL_ALGORITHM_H_ |