]>
git.proxmox.com Git - ceph.git/blob - ceph/src/common/histogram.h
1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 * Ceph - scalable distributed file system
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
13 #ifndef CEPH_HISTOGRAM_H
14 #define CEPH_HISTOGRAM_H
18 #include "include/encoding.h"
25 * power of 2 histogram
27 struct pow2_hist_t
{ //
32 * value is count of elements that are <= the current bin but > the previous bin.
34 std::vector
<int32_t> h
;
37 /// expand to at least another's size
38 void _expand_to(unsigned s
) {
42 /// drop useless trailing 0's
44 unsigned p
= h
.size();
45 while (p
> 0 && h
[p
-1] == 0)
57 void set_bin(int bin
, int32_t count
) {
70 bool operator==(const pow2_hist_t
&r
) const {
74 /// get a value's position in the histogram.
76 /// positions are represented as values in the range [0..1000000]
77 /// (millionths on the unit interval).
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
) {
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
) {
95 *lower
= lower_sum
* 1000000 / total
;
96 *upper
= upper_sum
* 1000000 / total
;
101 void add(const pow2_hist_t
& o
) {
102 _expand_to(o
.h
.size());
103 for (unsigned p
= 0; p
< o
.h
.size(); ++p
)
107 void sub(const pow2_hist_t
& o
) {
108 _expand_to(o
.h
.size());
109 for (unsigned p
= 0; p
< o
.h
.size(); ++p
)
114 int32_t upper_bound() const {
115 return 1 << h
.size();
118 /// decay histogram by N bits (default 1, for a halflife)
119 void decay(int bits
= 1);
121 void dump(ceph::Formatter
*f
) const;
122 void encode(ceph::buffer::list
&bl
) const;
123 void decode(ceph::buffer::list::const_iterator
&bl
);
124 static void generate_test_instances(std::list
<pow2_hist_t
*>& o
);
126 WRITE_CLASS_ENCODER(pow2_hist_t
)
128 #endif /* CEPH_HISTOGRAM_H */