src/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 <list>
  17
  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   }
  54   bool empty() const {
  55     return h.empty();
  56   }
  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 */