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