blob: cdaca61c277645d78ccb0c5ac3a715a7cb8de02d (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
// vim: ts=8 sw=2 smarttab
/*
* Ceph - scalable distributed file system
*
* This is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License version 2.1, as published by the Free Software
* Foundation. See file COPYING.
* Copyright 2013 Inktank
*/
#ifndef CEPH_HISTOGRAM_H
#define CEPH_HISTOGRAM_H
#include <list>
#include "include/encoding.h"
#include "include/intarith.h"
namespace ceph {
class Formatter;
}
/**
* power of 2 histogram
*/
struct pow2_hist_t { //
/**
* histogram
*
* bin size is 2^index
* value is count of elements that are <= the current bin but > the previous bin.
*/
std::vector<int32_t> h;
private:
/// expand to at least another's size
void _expand_to(unsigned s) {
if (s > h.size())
h.resize(s, 0);
}
/// drop useless trailing 0's
void _contract() {
unsigned p = h.size();
while (p > 0 && h[p-1] == 0)
--p;
h.resize(p);
}
public:
void clear() {
h.clear();
}
bool empty() const {
return h.empty();
}
void set_bin(int bin, int32_t count) {
_expand_to(bin + 1);
h[bin] = count;
_contract();
}
void add(int32_t v) {
int bin = cbits(v);
_expand_to(bin + 1);
h[bin]++;
_contract();
}
bool operator==(const pow2_hist_t &r) const {
return h == r.h;
}
/// get a value's position in the histogram.
///
/// positions are represented as values in the range [0..1000000]
/// (millionths on the unit interval).
///
/// @param v [in] value (non-negative)
/// @param lower [out] pointer to lower-bound (0..1000000)
/// @param upper [out] pointer to the upper bound (0..1000000)
int get_position_micro(int32_t v, uint64_t *lower, uint64_t *upper) {
if (v < 0)
return -1;
unsigned bin = cbits(v);
uint64_t lower_sum = 0, upper_sum = 0, total = 0;
for (unsigned i=0; i<h.size(); ++i) {
if (i <= bin)
upper_sum += h[i];
if (i < bin)
lower_sum += h[i];
total += h[i];
}
if (total > 0) {
*lower = lower_sum * 1000000 / total;
*upper = upper_sum * 1000000 / total;
}
return 0;
}
void add(const pow2_hist_t& o) {
_expand_to(o.h.size());
for (unsigned p = 0; p < o.h.size(); ++p)
h[p] += o.h[p];
_contract();
}
void sub(const pow2_hist_t& o) {
_expand_to(o.h.size());
for (unsigned p = 0; p < o.h.size(); ++p)
h[p] -= o.h[p];
_contract();
}
int32_t upper_bound() const {
return 1 << h.size();
}
/// decay histogram by N bits (default 1, for a halflife)
void decay(int bits = 1);
void dump(ceph::Formatter *f) const;
void encode(ceph::buffer::list &bl) const;
void decode(ceph::buffer::list::const_iterator &bl);
static void generate_test_instances(std::list<pow2_hist_t*>& o);
};
WRITE_CLASS_ENCODER(pow2_hist_t)
#endif /* CEPH_HISTOGRAM_H */
|
