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 // Bitfield manipulation for different integer types T
29 template <typename T>
30 inline void SetBit(unsigned int bit, T *field) {
31  *field |= static_cast<T>(1) << bit;
32 }
33 
34 template <typename T>
35 inline void ClearBit(unsigned int bit, T *field) {
36  *field &= ~(static_cast<T>(1) << bit);
37 }
38 
39 template <typename T>
40 inline bool TestBit(unsigned int bit, const T field) {
41  return field & (static_cast<T>(1) << bit);
42 }
43 
44 
48 template <typename T>
49 std::vector<T> Shuffle(const std::vector<T> &input, Prng *prng) {
50  std::vector<T> shuffled(input);
51  unsigned N = shuffled.size();
52  // No shuffling for the last element
53  for (unsigned i = 0; i < N; ++i) {
54  const unsigned swap_idx = i + prng->Next(N - i);
55  std::swap(shuffled[i], shuffled[swap_idx]);
56  }
57  return shuffled;
58 }
59 
60 
66 template <typename T, typename U>
67 void SortTeam(std::vector<T> *tractor, std::vector<U> *towed) {
68  assert(tractor);
69  assert(towed);
70  assert(tractor->size() == towed->size());
71  int N = tractor->size();
72 
73  // Insertion sort on both, tractor and towed
74  for (int i = 1; i < N; ++i) {
75  T val_tractor = (*tractor)[i];
76  U val_towed = (*towed)[i];
77  int pos;
78  for (pos = i-1; (pos >= 0) && ((*tractor)[pos] > val_tractor); --pos) {
79  (*tractor)[pos+1] = (*tractor)[pos];
80  (*towed)[pos+1] = (*towed)[pos];
81  }
82  (*tractor)[pos+1] = val_tractor;
83  (*towed)[pos+1] = val_towed;
84  }
85 }
86 
87 
88 template <typename hashed_type>
89 struct hash_murmur {
90  size_t operator() (const hashed_type key) const {
91 #ifdef __x86_64__
92  return MurmurHash64A(&key, sizeof(key), 0x9ce603115bba659bLLU);
93 #else
94  return MurmurHash2(&key, sizeof(key), 0x07387a4f);
95 #endif
96  }
97 };
98 
99 
112  public:
113  StopWatch() : running_(false) {}
114 
115  void Start();
116  void Stop();
117  void Reset();
118 
119  double GetTime() const;
120 
121  private:
122  bool running_;
123  timeval start_, end_;
124 };
125 
126 
141 friend class UTLog2Histogram;
142 
143  public:
144  explicit Log2Histogram(unsigned int nbins);
145 
146  void Add(unsigned int value) {
147  unsigned int i;
148  const unsigned int n = this->bins_.size() - 1;
149 
150  for (i = 1; i <= n; i++) {
151  if (value < this->boundary_values_[i]) {
152  atomic_inc32(&(this->bins_[i]));
153  return;
154  }
155  }
156 
157  atomic_inc32(&(this->bins_[0])); // add to overflow bin.
158  }
159 
163  inline uint64_t N() {
164  uint64_t n = 0;
165  unsigned int i;
166  for (i = 0; i <= this->bins_.size() - 1; i++) {
167  n += static_cast<unsigned int>(atomic_read32(&(this->bins_[i])));
168  }
169  return n;
170  }
171 
175  unsigned int GetQuantile(float n);
176 
177  std::string ToString();
178 
179  void PrintLog2Histogram();
180 
181  private:
182  std::vector<atomic_int32> bins_;
183  // boundary_values_ handle the largest value a certain
184  // bin can store in itself.
185  std::vector<unsigned int> boundary_values_;
186 };
187 
193  public:
194  std::vector<atomic_int32> GetBins(const Log2Histogram &h);
195 };
196 
197 
199  public:
200  static bool g_is_enabled; // false by default
201 
202  explicit HighPrecisionTimer(Log2Histogram *recorder)
203  : timestamp_start_(g_is_enabled ? platform_monotonic_time_ns() : 0)
204  , recorder_(recorder)
205  { }
206 
208  if (g_is_enabled)
209  recorder_->Add(platform_monotonic_time_ns() - timestamp_start_);
210  }
211 
212  private:
215 };
216 
217 #ifdef CVMFS_NAMESPACE_GUARD
218 } // namespace CVMFS_NAMESPACE_GUARD
219 #endif
220 
221 #endif // CVMFS_UTIL_ALGORITHM_H_
Definition: prng.h:28
std::vector< T > Shuffle(const std::vector< T > &input, Prng *prng)
Definition: algorithm.h:49
uint64_t timestamp_start_
Definition: algorithm.h:213
std::vector< unsigned int > boundary_values_
Definition: algorithm.h:185
std::vector< atomic_int32 > bins_
Definition: algorithm.h:182
double DiffTimeSeconds(struct timeval start, struct timeval end)
Definition: algorithm.cc:31
Log2Histogram * recorder_
Definition: algorithm.h:214
uint64_t N()
Definition: algorithm.h:163
assert((mem||(size==0))&&"Out Of Memory")
uint64_t platform_monotonic_time_ns()
bool running_
Definition: algorithm.h:122
void SetBit(unsigned int bit, T *field)
Definition: algorithm.h:30
void ClearBit(unsigned int bit, T *field)
Definition: algorithm.h:35
HighPrecisionTimer(Log2Histogram *recorder)
Definition: algorithm.h:202
bool TestBit(unsigned int bit, const T field)
Definition: algorithm.h:40
void Add(unsigned int value)
Definition: algorithm.h:146
static bool g_is_enabled
Definition: algorithm.h:200
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:67
timeval start_
Definition: algorithm.h:123
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:49