5 #ifndef CVMFS_UTIL_ALGORITHM_H_
6 #define CVMFS_UTIL_ALGORITHM_H_
21 #ifdef CVMFS_NAMESPACE_GUARD
22 namespace CVMFS_NAMESPACE_GUARD {
30 inline void SetBit(
unsigned int bit, T *field) {
31 *field |=
static_cast<T
>(1) << bit;
35 inline void ClearBit(
unsigned int bit, T *field) {
36 *field &= ~(
static_cast<T
>(1) << bit);
40 inline bool TestBit(
unsigned int bit,
const T field) {
41 return field & (
static_cast<T
>(1) << bit);
49 std::vector<T>
Shuffle(
const std::vector<T> &input,
Prng *prng) {
50 std::vector<T> shuffled(input);
51 unsigned N = shuffled.size();
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]);
66 template <
typename T,
typename U>
67 void SortTeam(std::vector<T> *tractor, std::vector<U> *towed) {
70 assert(tractor->size() == towed->size());
71 int N = tractor->size();
74 for (
int i = 1; i < N; ++i) {
75 T val_tractor = (*tractor)[i];
76 U val_towed = (*towed)[i];
78 for (pos = i-1; (pos >= 0) && ((*tractor)[pos] > val_tractor); --pos) {
79 (*tractor)[pos+1] = (*tractor)[pos];
80 (*towed)[pos+1] = (*towed)[pos];
82 (*tractor)[pos+1] = val_tractor;
83 (*towed)[pos+1] = val_towed;
88 template <
typename hashed_type>
90 size_t operator() (
const hashed_type key)
const {
92 return MurmurHash64A(&key,
sizeof(key), 0x9ce603115bba659bLLU);
119 double GetTime()
const;
146 void Add(uint64_t value) {
148 const unsigned int n = this->bins_.size() - 1;
150 for (i = 1; i <= n; i++) {
151 if (value < this->boundary_values_[i]) {
152 atomic_inc32(&(this->bins_[i]));
157 atomic_inc32(&(this->bins_[0]));
163 inline uint64_t
N() {
166 for (i = 0; i <= this->bins_.size() - 1; i++) {
167 n +=
static_cast<unsigned int>(atomic_read32(&(this->bins_[i])));
175 unsigned int GetQuantile(
float n);
177 std::string ToString();
179 void PrintLog2Histogram();
204 , recorder_(recorder)
217 #ifdef CVMFS_NAMESPACE_GUARD
221 #endif // CVMFS_UTIL_ALGORITHM_H_
std::vector< T > Shuffle(const std::vector< T > &input, Prng *prng)
uint64_t timestamp_start_
std::vector< unsigned int > boundary_values_
std::vector< atomic_int32 > bins_
double DiffTimeSeconds(struct timeval start, struct timeval end)
Log2Histogram * recorder_
assert((mem||(size==0))&&"Out Of Memory")
void SetBit(unsigned int bit, T *field)
void ClearBit(unsigned int bit, T *field)
HighPrecisionTimer(Log2Histogram *recorder)
bool TestBit(unsigned int bit, const T field)
uint64_t MurmurHash64A(const void *key, int len, uint64_t seed)
void SortTeam(std::vector< T > *tractor, std::vector< U > *towed)
uint32_t MurmurHash2(const void *key, int len, uint32_t seed)
uint32_t Next(const uint64_t boundary)