CernVM-FS  2.10.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
algorithm.h
Go to the documentation of this file.
1 
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 <vector>
13 
14 #include "atomic.h"
15 #include "murmur.hxx"
16 // TODO(jblomer): should be also part of algorithm
17 #include "platform.h"
18 #include "prng.h"
19 #include "util/single_copy.h"
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 
32 template <typename T>
33 std::vector<T> Shuffle(const std::vector<T> &input, Prng *prng) {
34  std::vector<T> shuffled(input);
35  unsigned N = shuffled.size();
36  // No shuffling for the last element
37  for (unsigned i = 0; i < N; ++i) {
38  const unsigned swap_idx = i + prng->Next(N - i);
39  std::swap(shuffled[i], shuffled[swap_idx]);
40  }
41  return shuffled;
42 }
43 
44 
50 template <typename T, typename U>
51 void SortTeam(std::vector<T> *tractor, std::vector<U> *towed) {
52  assert(tractor);
53  assert(towed);
54  assert(tractor->size() == towed->size());
55  int N = tractor->size();
56 
57  // Insertion sort on both, tractor and towed
58  for (int i = 1; i < N; ++i) {
59  T val_tractor = (*tractor)[i];
60  U val_towed = (*towed)[i];
61  int pos;
62  for (pos = i-1; (pos >= 0) && ((*tractor)[pos] > val_tractor); --pos) {
63  (*tractor)[pos+1] = (*tractor)[pos];
64  (*towed)[pos+1] = (*towed)[pos];
65  }
66  (*tractor)[pos+1] = val_tractor;
67  (*towed)[pos+1] = val_towed;
68  }
69 }
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 
96  public:
97  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 
125 friend class UTLog2Histogram;
126 
127  public:
128  explicit Log2Histogram(unsigned int nbins);
129 
130  void Add(unsigned int value) {
131  unsigned int i;
132  const unsigned int n = this->bins_.size() - 1;
133 
134  for (i = 1; i <= n; i++) {
135  if (value < this->boundary_values_[i]) {
136  atomic_inc32(&(this->bins_[i]));
137  return;
138  }
139  }
140 
141  atomic_inc32(&(this->bins_[0])); // add to overflow bin.
142  }
143 
147  inline uint64_t N() {
148  uint64_t n = 0;
149  unsigned int i;
150  for (i = 0; i <= this->bins_.size() - 1; i++) {
151  n += static_cast<unsigned int>(atomic_read32(&(this->bins_[i])));
152  }
153  return n;
154  }
155 
159  unsigned int GetQuantile(float n);
160 
161  std::string ToString();
162 
163  void PrintLog2Histogram();
164 
165  private:
166  std::vector<atomic_int32> bins_;
167  // boundary_values_ handle the largest value a certain
168  // bin can store in itself.
169  std::vector<unsigned int> boundary_values_;
170 };
171 
177  public:
178  std::vector<atomic_int32> GetBins(const Log2Histogram &h);
179 };
180 
181 
183  public:
184  static bool g_is_enabled; // false by default
185 
186  explicit HighPrecisionTimer(Log2Histogram *recorder)
187  : timestamp_start_(g_is_enabled ? platform_monotonic_time_ns() : 0)
188  , recorder_(recorder)
189  { }
190 
192  if (g_is_enabled)
193  recorder_->Add(platform_monotonic_time_ns() - timestamp_start_);
194  }
195 
196  private:
199 };
200 
201 #ifdef CVMFS_NAMESPACE_GUARD
202 } // namespace CVMFS_NAMESPACE_GUARD
203 #endif
204 
205 #endif // CVMFS_UTIL_ALGORITHM_H_
Definition: prng.h:25
std::vector< T > Shuffle(const std::vector< T > &input, Prng *prng)
Definition: algorithm.h:33
uint64_t timestamp_start_
Definition: algorithm.h:197
std::vector< unsigned int > boundary_values_
Definition: algorithm.h:169
std::vector< atomic_int32 > bins_
Definition: algorithm.h:166
double DiffTimeSeconds(struct timeval start, struct timeval end)
Definition: algorithm.cc:31
Log2Histogram * recorder_
Definition: algorithm.h:198
uint64_t N()
Definition: algorithm.h:147
assert((mem||(size==0))&&"Out Of Memory")
uint64_t platform_monotonic_time_ns()
bool running_
Definition: algorithm.h:106
StopWatch()
Definition: algorithm.h:97
HighPrecisionTimer(Log2Histogram *recorder)
Definition: algorithm.h:186
void Add(unsigned int value)
Definition: algorithm.h:130
static bool g_is_enabled
Definition: algorithm.h:184
uint64_t MurmurHash64A(const void *key, int len, uint64_t seed)
Definition: murmur.hxx:83
void SortTeam(std::vector< T > *tractor, std::vector< U > *towed)
Definition: algorithm.h:51
timeval start_
Definition: algorithm.h:107
uint32_t MurmurHash2(const void *key, int len, uint32_t seed)
Definition: murmur.hxx:23
uint32_t Next(const uint64_t boundary)
Definition: prng.h:46