1 files changed, 128 insertions, 0 deletions
diff --git a/src/common/histogram.h b/src/common/histogram.h
new file mode 100644
index 000000000..cdaca61c2
--- /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"
+#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 */