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
   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
  16 #include <vector>
  17 #include <list>
  18
  19 #include "include/intarith.h"
  20 #include "include/encoding.h"
  21
  22 namespace ceph {
  23   class Formatter;
  24 }
  25
  26 /**
  27  * power of 2 histogram
  28  */
  29 struct pow2_hist_t { //
  30   /**
  31    * histogram
  32    *
  33    * bin size is 2^index
  34    * value is count of elements that are <= the current bin but > the previous bin.
  35    */
  36   std::vector<int32_t> h;
  37
  38 private:
  39   /// expand to at least another's size
  40   void _expand_to(unsigned s) {
  41     if (s > h.size())
  42       h.resize(s, 0);
  43   }
  44   /// drop useless trailing 0's
  45   void _contract() {
  46     unsigned p = h.size();
  47     while (p > 0 && h[p-1] == 0)
  48       --p;
  49     h.resize(p);
  50   }
  51
  52 public:
  53   void clear() {
  54     h.clear();
  55   }
  56   void set_bin(int bin, int32_t count) {
  57     _expand_to(bin + 1);
  58     h[bin] = count;
  59     _contract();
  60   }
  61
  62   void add(int32_t v) {
  63     int bin = cbits(v);
  64     _expand_to(bin + 1);
  65     h[bin]++;
  66     _contract();
  67   }
  68
  69   bool operator==(const pow2_hist_t &r) const {
  70     return h == r.h;
  71   }
  72
  73   /// get a value's position in the histogram.
  74   ///
  75   /// positions are represented as values in the range [0..1000000]
  76   /// (millionths on the unit interval).
  77   ///
  78   /// @param v [in] value (non-negative)
  79   /// @param lower [out] pointer to lower-bound (0..1000000)
  80   /// @param upper [out] pointer to the upper bound (0..1000000)
  81   int get_position_micro(int32_t v, uint64_t *lower, uint64_t *upper) {
  82     if (v < 0)
  83       return -1;
  84     unsigned bin = cbits(v);
  85     uint64_t lower_sum = 0, upper_sum = 0, total = 0;
  86     for (unsigned i=0; i<h.size(); ++i) {
  87       if (i <= bin)
  88         upper_sum += h[i];
  89       if (i < bin)
  90         lower_sum += h[i];
  91       total += h[i];
  92     }
  93     if (total > 0) {
  94       *lower = lower_sum * 1000000 / total;
  95       *upper = upper_sum * 1000000 / total;
  96     }
  97     return 0;
  98   }
  99
 100   void add(const pow2_hist_t& o) {
 101     _expand_to(o.h.size());
 102     for (unsigned p = 0; p < o.h.size(); ++p)
 103       h[p] += o.h[p];
 104     _contract();
 105   }
 106   void sub(const pow2_hist_t& o) {
 107     _expand_to(o.h.size());
 108     for (unsigned p = 0; p < o.h.size(); ++p)
 109       h[p] -= o.h[p];
 110     _contract();
 111   }
 112
 113   int32_t upper_bound() const {
 114     return 1 << h.size();
 115   }
 116
 117   /// decay histogram by N bits (default 1, for a halflife)
 118   void decay(int bits = 1);
 119
 120   void dump(Formatter *f) const;
 121   void encode(bufferlist &bl) const;
 122   void decode(bufferlist::iterator &bl);
 123   static void generate_test_instances(std::list<pow2_hist_t*>& o);
 124 };
 125 WRITE_CLASS_ENCODER(pow2_hist_t)
 126
 127 #endif /* CEPH_HISTOGRAM_H */