Extend Histogram class to support custom range definitions

Some users have a small sparsely separated enumerated list
of plausible samples which don't fit well into a default
(log space) histogarm, or a consistently spaced (LinearHistogram).

This implementation does not yet support renderer histograms of this
sort, but it at least unblocks the dependent bug that needs support
for these sparse histograms in the browser.

The bulk of this patch was written by Raman Tenetti, in CL 1706012.

BUG=40953
r=eroman
Review URL: http://codereview.chromium.org/1737017

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@45998 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 205 insertions, 15 deletions

diff --git a/base/histogram.cc b/base/histogram.cc
index c7a64af..dd02c31 100644
--- a/base/histogram.cc
+++ b/base/histogram.cc
@@ -180,7 +180,7 @@ void Histogram::WriteAscii(bool graph_it, const std::string& newline,
 bool Histogram::ValidateBucketRanges() const {
   // Standard assertions that all bucket ranges should satisfy.
   DCHECK(ranges_.size() == bucket_count_ + 1);
-  DCHECK_EQ(0, ranges_[0]);
+  DCHECK_EQ(ranges_[0], 0);
   DCHECK(declared_min() == ranges_[1]);
   DCHECK(declared_max() == ranges_[bucket_count_ - 1]);
   DCHECK(kSampleType_MAX == ranges_[bucket_count_]);
@@ -194,10 +194,10 @@ void Histogram::Initialize() {
   if (declared_max_ >= kSampleType_MAX)
     declared_max_ = kSampleType_MAX - 1;
   DCHECK(declared_min_ <= declared_max_);
-  DCHECK_LT(1u, bucket_count_);
+  DCHECK_GT(bucket_count_, 1u);
   size_t maximal_bucket_count = declared_max_ - declared_min_ + 2;
   DCHECK(bucket_count_ <= maximal_bucket_count);
-  DCHECK_EQ(0, ranges_[0]);
+  DCHECK_EQ(ranges_[0], 0);
   ranges_[bucket_count_] = kSampleType_MAX;
   InitializeBucketRange();
   DCHECK(ValidateBucketRanges());
@@ -325,7 +325,7 @@ void Histogram::WriteAsciiHeader(const SampleSet& snapshot,
                 histogram_name().c_str(),
                 sample_count);
   if (0 == sample_count) {
-    DCHECK_EQ(0, snapshot.sum());
+    DCHECK_EQ(snapshot.sum(), 0);
   } else {
     double average = static_cast<float>(snapshot.sum()) / sample_count;
     double variance = static_cast<float>(snapshot.square_sum())/sample_count
@@ -646,7 +646,7 @@ bool LinearHistogram::PrintEmptyBucket(size_t index) const {
 
 
 void LinearHistogram::InitializeBucketRange() {
-  DCHECK_LT(0, declared_min());  // 0 is the underflow bucket here.
+  DCHECK_GT(declared_min(), 0);  // 0 is the underflow bucket here.
   double min = declared_min();
   double max = declared_max();
   size_t i;
@@ -691,6 +691,70 @@ scoped_refptr<Histogram> BooleanHistogram::FactoryGet(const std::string& name,
 
 
 //------------------------------------------------------------------------------
+// CustomHistogram:
+//------------------------------------------------------------------------------
+
+scoped_refptr<Histogram> CustomHistogram::FactoryGet(
+    const std::string& name, const std::vector<int>& custom_ranges,
+    Flags flags) {
+  scoped_refptr<Histogram> histogram(NULL);
+
+  // Remove the duplicates in the custom ranges array.
+  std::vector<int> ranges = custom_ranges;
+  ranges.push_back(0);  // Ensure we have a zero value.
+  std::sort(ranges.begin(), ranges.end());
+  ranges.erase(std::unique(ranges.begin(), ranges.end()), ranges.end());
+  if (ranges.size() <= 1) {
+    DCHECK(false);
+    // Note that we pushed a 0 in above, so for defensive code....
+    ranges.push_back(1);  // Put in some data so we can index to [1].
+  }
+
+  DCHECK_LT(ranges.back(), kSampleType_MAX);
+
+  if (StatisticsRecorder::FindHistogram(name, &histogram)) {
+    DCHECK(histogram.get());
+    DCHECK_EQ(histogram->histogram_type(), CUSTOM_HISTOGRAM);
+  } else {
+    histogram = new CustomHistogram(name, ranges);
+    scoped_refptr<Histogram> registered_histogram(NULL);
+    StatisticsRecorder::FindHistogram(name, &registered_histogram);
+    if (registered_histogram.get() &&
+        registered_histogram.get() != histogram.get())
+      histogram = registered_histogram;
+  }
+
+  DCHECK_EQ(histogram->histogram_type(), CUSTOM_HISTOGRAM);
+  DCHECK(histogram->HasConstructorArguments(ranges[1], ranges.back(),
+                                            ranges.size()));
+  histogram->SetFlags(flags);
+  return histogram;
+}
+
+CustomHistogram::CustomHistogram(const std::string& name,
+    const std::vector<int>& custom_ranges)
+    : Histogram(name, custom_ranges[1], custom_ranges.back(),
+                custom_ranges.size()) {
+  DCHECK_GT(custom_ranges.size(), 1u);
+  DCHECK_EQ(custom_ranges[0], 0);
+  ranges_vector_ = &custom_ranges;
+  InitializeBucketRange();
+  ranges_vector_ = NULL;
+  DCHECK(ValidateBucketRanges());
+}
+
+void CustomHistogram::InitializeBucketRange() {
+  DCHECK(ranges_vector_->size() <= bucket_count());
+  for (size_t index = 0; index < ranges_vector_->size(); ++index) {
+    SetBucketRange(index, (*ranges_vector_)[index]);
+  }
+}
+
+double CustomHistogram::GetBucketSize(Count current, size_t i) const {
+  return 1;
+}
+
+//------------------------------------------------------------------------------
 // The next section handles global (central) support for all histograms, as well
 // as startup/teardown of this service.
 //------------------------------------------------------------------------------
diff --git a/base/histogram.h b/base/histogram.h
index f16dde0..1737b85 100644
--- a/base/histogram.h
+++ b/base/histogram.h
@@ -90,6 +90,12 @@
     counter->Add(sample); \
   } while (0)
 
+#define HISTOGRAM_CUSTOM_ENUMERATION(name, sample, custom_ranges) do { \
+    static scoped_refptr<Histogram> counter = CustomHistogram::FactoryGet( \
+        name, custom_ranges, Histogram::kNoFlags); \
+    counter->Add(sample); \
+  } while (0)
+
 
 //------------------------------------------------------------------------------
 // Define Debug vs non-debug flavors of macros.
@@ -107,6 +113,8 @@
     HISTOGRAM_CUSTOM_COUNTS(name, sample, min, max, bucket_count)
 #define DHISTOGRAM_ENUMERATION(name, sample, boundary_value) \
     HISTOGRAM_ENUMERATION(name, sample, boundary_value)
+#define DHISTOGRAM_CUSTOM_ENUMERATION(name, sample, custom_ranges) \
+    HISTOGRAM_CUSTOM_ENUMERATION(name, sample, custom_ranges)
 
 #else  // NDEBUG
 
@@ -120,6 +128,8 @@
 #define DHISTOGRAM_CUSTOM_COUNTS(name, sample, min, max, bucket_count) \
     do {} while (0)
 #define DHISTOGRAM_ENUMERATION(name, sample, boundary_value) do {} while (0)
+#define DHISTOGRAM_CUSTOM_ENUMERATION(name, sample, custom_ranges) \
+    do {} while (0)
 
 #endif  // NDEBUG
 
@@ -186,13 +196,19 @@
     counter->Add(sample); \
   } while (0)
 
+#define UMA_HISTOGRAM_CUSTOM_ENUMERATION(name, sample, custom_ranges) do { \
+    static scoped_refptr<Histogram> counter = CustomHistogram::FactoryGet( \
+        name, custom_ranges, Histogram::kUmaTargetedHistogramFlag); \
+    counter->Add(sample); \
+  } while (0)
 
 //------------------------------------------------------------------------------
 
-class Pickle;
+class BooleanHistogram;
+class CustomHistogram;
 class Histogram;
 class LinearHistogram;
-class BooleanHistogram;
+class Pickle;
 
 namespace disk_cache {
   class StatsHistogram;
@@ -214,12 +230,14 @@ class Histogram : public base::RefCountedThreadSafe<Histogram> {
     HISTOGRAM,
     LINEAR_HISTOGRAM,
     BOOLEAN_HISTOGRAM,
+    CUSTOM_HISTOGRAM,
     NOT_VALID_IN_RENDERER
   };
 
   enum BucketLayout {
     EXPONENTIAL,
-    LINEAR
+    LINEAR,
+    CUSTOM
   };
 
   enum Flags {
@@ -482,8 +500,6 @@ class LinearHistogram : public Histogram {
   LinearHistogram(const std::string& name, base::TimeDelta minimum,
                   base::TimeDelta maximum, size_t bucket_count);
 
-  virtual ~LinearHistogram() {}
-
   // Initialize ranges_ mapping.
   virtual void InitializeBucketRange();
   virtual double GetBucketSize(Count current, size_t i) const;
@@ -527,6 +543,31 @@ class BooleanHistogram : public LinearHistogram {
 };
 
 //------------------------------------------------------------------------------
+
+// CustomHistogram is a histogram for a set of custom integers.
+class CustomHistogram : public Histogram {
+ public:
+  virtual ClassType histogram_type() const { return CUSTOM_HISTOGRAM; }
+
+  static scoped_refptr<Histogram> FactoryGet(const std::string& name,
+      const std::vector<int>& custom_ranges, Flags flags);
+
+ protected:
+  CustomHistogram(const std::string& name,
+                  const std::vector<int>& custom_ranges);
+
+  // Initialize ranges_ mapping.
+  virtual void InitializeBucketRange();
+  virtual double GetBucketSize(Count current, size_t i) const;
+
+ private:
+  // Temporary pointer used during construction/initialization, and then NULLed.
+  const std::vector<int>* ranges_vector_;
+
+  DISALLOW_COPY_AND_ASSIGN(CustomHistogram);
+};
+
+//------------------------------------------------------------------------------
 // StatisticsRecorder handles all histograms in the system.  It provides a
 // general place for histograms to register, and supports a global API for
 // accessing (i.e., dumping, or graphing) the data in all the histograms.
diff --git a/base/histogram_unittest.cc b/base/histogram_unittest.cc
index f702a2e..56c733b 100644
--- a/base/histogram_unittest.cc
+++ b/base/histogram_unittest.cc
@@ -29,6 +29,17 @@ TEST(HistogramTest, StartupShutdownTest) {
   scoped_refptr<Histogram> linear_histogram1 = LinearHistogram::FactoryGet(
       "Test1LinearHistogram", 1, 1000, 10, Histogram::kNoFlags);
 
+  std::vector<int> custom_ranges;
+  custom_ranges.push_back(1);
+  custom_ranges.push_back(5);
+  custom_ranges.push_back(10);
+  custom_ranges.push_back(20);
+  custom_ranges.push_back(30);
+  scoped_refptr<Histogram> custom_histogram = CustomHistogram::FactoryGet(
+      "TestCustomHistogram", custom_ranges, Histogram::kNoFlags);
+  scoped_refptr<Histogram> custom_histogram1 = CustomHistogram::FactoryGet(
+      "Test1CustomHistogram", custom_ranges, Histogram::kNoFlags);
+
   // Use standard macros (but with fixed samples)
   HISTOGRAM_TIMES("Test2Histogram", TimeDelta::FromDays(1));
   HISTOGRAM_COUNTS("Test3Histogram", 30);
@@ -74,32 +85,51 @@ TEST(HistogramTest, RecordedStartupTest) {
 
   scoped_refptr<Histogram> linear_histogram = LinearHistogram::FactoryGet(
       "TestLinearHistogram", 1, 1000, 10, Histogram::kNoFlags);
+  histograms.clear();
+  StatisticsRecorder::GetHistograms(&histograms);  // Load up lists
+  EXPECT_EQ(3U, histograms.size());
+
   scoped_refptr<Histogram> linear_histogram1 = LinearHistogram::FactoryGet(
       "Test1LinearHistogram", 1, 1000, 10, Histogram::kNoFlags);
   histograms.clear();
   StatisticsRecorder::GetHistograms(&histograms);  // Load up lists
   EXPECT_EQ(4U, histograms.size());
 
+  std::vector<int> custom_ranges;
+  custom_ranges.push_back(1);
+  custom_ranges.push_back(5);
+  custom_ranges.push_back(10);
+  custom_ranges.push_back(20);
+  custom_ranges.push_back(30);
+  scoped_refptr<Histogram> custom_histogram = CustomHistogram::FactoryGet(
+      "TestCustomHistogram", custom_ranges, Histogram::kNoFlags);
+  scoped_refptr<Histogram> custom_histogram1 = CustomHistogram::FactoryGet(
+      "TestCustomHistogram", custom_ranges, Histogram::kNoFlags);
+
+  histograms.clear();
+  StatisticsRecorder::GetHistograms(&histograms);  // Load up lists
+  EXPECT_EQ(5U, histograms.size());
+
   // Use standard macros (but with fixed samples)
   HISTOGRAM_TIMES("Test2Histogram", TimeDelta::FromDays(1));
   HISTOGRAM_COUNTS("Test3Histogram", 30);
   histograms.clear();
   StatisticsRecorder::GetHistograms(&histograms);  // Load up lists
-  EXPECT_EQ(6U, histograms.size());
+  EXPECT_EQ(7U, histograms.size());
 
   HISTOGRAM_ENUMERATION("TestEnumerationHistogram", 20, 200);
   histograms.clear();
   StatisticsRecorder::GetHistograms(&histograms);  // Load up lists
-  EXPECT_EQ(7U, histograms.size());
+  EXPECT_EQ(8U, histograms.size());
 
   DHISTOGRAM_TIMES("Test4Histogram", TimeDelta::FromDays(1));
   DHISTOGRAM_COUNTS("Test5Histogram", 30);
   histograms.clear();
   StatisticsRecorder::GetHistograms(&histograms);  // Load up lists
 #ifndef NDEBUG
-  EXPECT_EQ(9U, histograms.size());
+  EXPECT_EQ(10U, histograms.size());
 #else
-  EXPECT_EQ(7U, histograms.size());
+  EXPECT_EQ(8U, histograms.size());
 #endif
 }
 
@@ -164,10 +194,65 @@ TEST(HistogramTest, RangeTest) {
   EXPECT_EQ(32, transitioning_histogram->ranges(14));
   EXPECT_EQ(INT_MAX, transitioning_histogram->ranges(15));
 
+  std::vector<int> custom_ranges;
+  custom_ranges.push_back(0);
+  custom_ranges.push_back(9);
+  custom_ranges.push_back(10);
+  custom_ranges.push_back(11);
+  custom_ranges.push_back(300);
+  scoped_refptr<Histogram> test_custom_histogram = CustomHistogram::FactoryGet(
+      "TestCustomRangeHistogram", custom_ranges, Histogram::kNoFlags);
+
+  EXPECT_EQ(custom_ranges[0], test_custom_histogram->ranges(0));
+  EXPECT_EQ(custom_ranges[1], test_custom_histogram->ranges(1));
+  EXPECT_EQ(custom_ranges[2], test_custom_histogram->ranges(2));
+  EXPECT_EQ(custom_ranges[3], test_custom_histogram->ranges(3));
+  EXPECT_EQ(custom_ranges[4], test_custom_histogram->ranges(4));
+
   recorder.GetHistograms(&histograms);
-  EXPECT_EQ(5U, histograms.size());
+  EXPECT_EQ(6U, histograms.size());
 }
 
+TEST(HistogramTest, CustomRangeTest) {
+  StatisticsRecorder recorder;
+  StatisticsRecorder::Histograms histograms;
+
+  // Check that missing leading zero is handled by an auto-insertion.
+  std::vector<int> custom_ranges;
+  // Don't include a zero.
+  custom_ranges.push_back(9);
+  custom_ranges.push_back(10);
+  custom_ranges.push_back(11);
+  scoped_refptr<Histogram> test_custom_histogram = CustomHistogram::FactoryGet(
+      "TestCustomRangeHistogram", custom_ranges, Histogram::kNoFlags);
+
+  EXPECT_EQ(0, test_custom_histogram->ranges(0));  // Auto added
+  EXPECT_EQ(custom_ranges[0], test_custom_histogram->ranges(1));
+  EXPECT_EQ(custom_ranges[1], test_custom_histogram->ranges(2));
+  EXPECT_EQ(custom_ranges[2], test_custom_histogram->ranges(3));
+
+  // Check that unsorted data with dups is handled gracefully.
+  const int kSmall = 7;
+  const int kMid = 8;
+  const int kBig = 9;
+  custom_ranges.clear();
+  custom_ranges.push_back(kBig);
+  custom_ranges.push_back(kMid);
+  custom_ranges.push_back(kSmall);
+  custom_ranges.push_back(kSmall);
+  custom_ranges.push_back(kMid);
+  custom_ranges.push_back(0);  // Push an explicit zero.
+  custom_ranges.push_back(kBig);
+
+  scoped_refptr<Histogram> unsorted_histogram = CustomHistogram::FactoryGet(
+      "TestCustomUnsortedDupedHistogram", custom_ranges, Histogram::kNoFlags);
+  EXPECT_EQ(0, unsorted_histogram->ranges(0));
+  EXPECT_EQ(kSmall, unsorted_histogram->ranges(1));
+  EXPECT_EQ(kMid, unsorted_histogram->ranges(2));
+  EXPECT_EQ(kBig, unsorted_histogram->ranges(3));
+}
+
+
 // Make sure histogram handles out-of-bounds data gracefully.
 TEST(HistogramTest, BoundsTest) {
   const size_t kBucketCount = 50;