summaryrefslogtreecommitdiffstats
path: root/src/common/histogram.h
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-27 18:24:20 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-27 18:24:20 +0000
commit483eb2f56657e8e7f419ab1a4fab8dce9ade8609 (patch)
treee5d88d25d870d5dedacb6bbdbe2a966086a0a5cf /src/common/histogram.h
parentInitial commit. (diff)
downloadceph-483eb2f56657e8e7f419ab1a4fab8dce9ade8609.tar.xz
ceph-483eb2f56657e8e7f419ab1a4fab8dce9ade8609.zip
Adding upstream version 14.2.21.upstream/14.2.21upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/common/histogram.h')
-rw-r--r--src/common/histogram.h128
1 files changed, 128 insertions, 0 deletions
diff --git a/src/common/histogram.h b/src/common/histogram.h
new file mode 100644
index 00000000..139450b7
--- /dev/null
+++ b/src/common/histogram.h
@@ -0,0 +1,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"
+
+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(Formatter *f) const;
+ void encode(bufferlist &bl) const;
+ void decode(bufferlist::const_iterator &bl);
+ static void generate_test_instances(std::list<pow2_hist_t*>& o);
+};
+WRITE_CLASS_ENCODER(pow2_hist_t)
+
+#endif /* CEPH_HISTOGRAM_H */