Add SampleMap and use it in SparseHistogram

BUG=139612


Review URL: https://chromiumcodereview.appspot.com/11022002

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

10 files changed, 334 insertions, 35 deletions

diff --git a/base/metrics/histogram_samples.h b/base/metrics/histogram_samples.h
index 778b11d..c55b584 100644
--- a/base/metrics/histogram_samples.h
+++ b/base/metrics/histogram_samples.h
@@ -42,11 +42,9 @@ class BASE_EXPORT HistogramSamples {
   HistogramBase::Count redundant_count() const { return redundant_count_; }
 
  protected:
-  // Based on |instruction| type, add or subtract sample counts data from the
-  // iterator.
-  enum Instruction { ADD, SUBTRACT };
-  virtual bool AddSubtractImpl(SampleCountIterator* iter,
-                               Instruction instruction) = 0;
+  // Based on |op| type, add or subtract sample counts data from the iterator.
+  enum Operator { ADD, SUBTRACT };
+  virtual bool AddSubtractImpl(SampleCountIterator* iter, Operator op) = 0;
 
   void IncreaseSum(int64 diff);
   void IncreaseRedundantCount(HistogramBase::Count diff);
diff --git a/base/metrics/sample_map.cc b/base/metrics/sample_map.cc
new file mode 100644
index 0000000..9bd78e7
--- /dev/null
+++ b/base/metrics/sample_map.cc
@@ -0,0 +1,91 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/metrics/sample_map.h"
+
+#include "base/logging.h"
+
+using std::map;
+
+namespace base {
+
+typedef HistogramBase::Count Count;
+typedef HistogramBase::Sample Sample;
+
+SampleMap::SampleMap() {}
+
+SampleMap::~SampleMap() {}
+
+void SampleMap::Accumulate(Sample value, Count count) {
+  sample_counts_[value] += count;
+  IncreaseSum(count * value);
+  IncreaseRedundantCount(count);
+}
+
+Count SampleMap::GetCount(Sample value) const {
+  map<Sample, Count>::const_iterator it = sample_counts_.find(value);
+  if (it == sample_counts_.end())
+    return 0;
+  return it->second;
+}
+
+Count SampleMap::TotalCount() const {
+  Count count = 0;
+  for (map<Sample, Count>::const_iterator it = sample_counts_.begin();
+       it != sample_counts_.end();
+       ++it) {
+    count += it->second;
+  }
+  return count;
+}
+
+scoped_ptr<SampleCountIterator> SampleMap::Iterator() const {
+  return scoped_ptr<SampleCountIterator>(new SampleMapIterator(sample_counts_));
+}
+
+void SampleMap::ResetRedundantCount(Count count) {
+  IncreaseRedundantCount(-redundant_count());
+  IncreaseRedundantCount(count);
+}
+
+bool SampleMap::AddSubtractImpl(SampleCountIterator* iter,
+                                HistogramSamples::Operator op) {
+  Sample min;
+  Sample max;
+  Count count;
+  for (; !iter->Done(); iter->Next()) {
+    iter->Get(&min, &max, &count);
+    if (min + 1 != max)
+      return false;  // SparseHistogram only supports bucket with size 1.
+    sample_counts_[min] += (op ==  HistogramSamples::ADD) ? count : -count;
+  }
+  return true;
+}
+
+SampleMapIterator::SampleMapIterator(const SampleToCountMap& sample_counts)
+    : iter_(sample_counts.begin()),
+      end_(sample_counts.end()) {}
+
+SampleMapIterator::~SampleMapIterator() {}
+
+bool SampleMapIterator::Done() const {
+  return iter_ == end_;
+}
+
+void SampleMapIterator::Next() {
+  DCHECK(!Done());
+  iter_++;
+}
+
+void SampleMapIterator::Get(Sample* min, Sample* max, Count* count) const {
+  DCHECK(!Done());
+  if (min != NULL)
+    *min = iter_->first;
+  if (max != NULL)
+    *max = iter_->first + 1;
+  if (count != NULL)
+    *count = iter_->second;
+}
+
+}  // namespace base
diff --git a/base/metrics/sample_map.h b/base/metrics/sample_map.h
new file mode 100644
index 0000000..65a31f1
--- /dev/null
+++ b/base/metrics/sample_map.h
@@ -0,0 +1,67 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// SampleMap implements HistogramSamples interface. It is used by the
+// SparseHistogram class to store samples.
+
+#ifndef BASE_METRICS_SAMPLE_MAP_H_
+#define BASE_METRICS_SAMPLE_MAP_H_
+
+#include <map>
+
+#include "base/compiler_specific.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/metrics/histogram_base.h"
+#include "base/metrics/histogram_samples.h"
+
+namespace base {
+
+class BASE_EXPORT_PRIVATE SampleMap : public HistogramSamples {
+ public:
+  SampleMap();
+  virtual ~SampleMap();
+
+  // HistogramSamples implementation:
+  virtual void Accumulate(HistogramBase::Sample value,
+                          HistogramBase::Count count) OVERRIDE;
+  virtual HistogramBase::Count GetCount(
+      HistogramBase::Sample value) const OVERRIDE;
+  virtual HistogramBase::Count TotalCount() const OVERRIDE;
+  virtual scoped_ptr<SampleCountIterator> Iterator() const OVERRIDE;
+
+  void ResetRedundantCount(HistogramBase::Count count);
+
+ protected:
+  virtual bool AddSubtractImpl(
+      SampleCountIterator* iter,
+      HistogramSamples::Operator op) OVERRIDE;  // |op| is ADD or SUBTRACT.
+
+ private:
+  std::map<HistogramBase::Sample, HistogramBase::Count> sample_counts_;
+
+  DISALLOW_COPY_AND_ASSIGN(SampleMap);
+};
+
+class BASE_EXPORT_PRIVATE SampleMapIterator : public SampleCountIterator {
+ public:
+  typedef std::map<HistogramBase::Sample, HistogramBase::Count>
+      SampleToCountMap;
+
+  SampleMapIterator(const SampleToCountMap& sample_counts);
+  virtual ~SampleMapIterator();
+
+  // SampleCountIterator implementation:
+  virtual bool Done() const OVERRIDE;
+  virtual void Next() OVERRIDE;
+  virtual void Get(HistogramBase::Sample* min,
+                   HistogramBase::Sample* max,
+                   HistogramBase::Count* count) const OVERRIDE;
+ private:
+  SampleToCountMap::const_iterator iter_;
+  const SampleToCountMap::const_iterator end_;
+};
+
+}  // namespace base
+
+#endif  // BASE_METRICS_SAMPLE_MAP_H_
diff --git a/base/metrics/sample_map_unittest.cc b/base/metrics/sample_map_unittest.cc
new file mode 100644
index 0000000..1a53ee7
--- /dev/null
+++ b/base/metrics/sample_map_unittest.cc
@@ -0,0 +1,123 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/memory/scoped_ptr.h"
+#include "base/metrics/sample_map.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace base {
+namespace {
+
+TEST(SampleMapTest, AccumulateTest) {
+  SampleMap samples;
+
+  samples.Accumulate(1, 100);
+  samples.Accumulate(2, 200);
+  samples.Accumulate(1, -200);
+  EXPECT_EQ(-100, samples.GetCount(1));
+  EXPECT_EQ(200, samples.GetCount(2));
+
+  EXPECT_EQ(300, samples.sum());
+  EXPECT_EQ(100, samples.TotalCount());
+  EXPECT_EQ(samples.redundant_count(), samples.TotalCount());
+}
+
+TEST(SampleMapTest, AddSubtractTest) {
+  SampleMap samples1;
+  SampleMap samples2;
+
+  samples1.Accumulate(1, 100);
+  samples1.Accumulate(2, 100);
+  samples1.Accumulate(3, 100);
+
+  samples2.Accumulate(1, 200);
+  samples2.Accumulate(2, 200);
+  samples2.Accumulate(4, 200);
+
+  samples1.Add(samples2);
+  EXPECT_EQ(300, samples1.GetCount(1));
+  EXPECT_EQ(300, samples1.GetCount(2));
+  EXPECT_EQ(100, samples1.GetCount(3));
+  EXPECT_EQ(200, samples1.GetCount(4));
+  EXPECT_EQ(2000, samples1.sum());
+  EXPECT_EQ(900, samples1.TotalCount());
+  EXPECT_EQ(samples1.redundant_count(), samples1.TotalCount());
+
+  samples1.Subtract(samples2);
+  EXPECT_EQ(100, samples1.GetCount(1));
+  EXPECT_EQ(100, samples1.GetCount(2));
+  EXPECT_EQ(100, samples1.GetCount(3));
+  EXPECT_EQ(0, samples1.GetCount(4));
+  EXPECT_EQ(600, samples1.sum());
+  EXPECT_EQ(300, samples1.TotalCount());
+  EXPECT_EQ(samples1.redundant_count(), samples1.TotalCount());
+}
+
+TEST(SampleMapIteratorTest, IterateTest) {
+  SampleMap samples;
+  samples.Accumulate(1, 100);
+  samples.Accumulate(2, 200);
+  samples.Accumulate(4, -300);
+  samples.Accumulate(5, 0);
+
+  scoped_ptr<SampleCountIterator> it = samples.Iterator();
+
+  HistogramBase::Sample min;
+  HistogramBase::Sample max;
+  HistogramBase::Count count;
+
+  it->Get(&min, &max, &count);
+  EXPECT_EQ(1, min);
+  EXPECT_EQ(2, max);
+  EXPECT_EQ(100, count);
+  EXPECT_FALSE(it->GetBucketIndex(NULL));
+
+  it->Next();
+  it->Get(&min, &max, &count);
+  EXPECT_EQ(2, min);
+  EXPECT_EQ(3, max);
+  EXPECT_EQ(200, count);
+
+  it->Next();
+  it->Get(&min, &max, &count);
+  EXPECT_EQ(4, min);
+  EXPECT_EQ(5, max);
+  EXPECT_EQ(-300, count);
+
+  it->Next();
+  it->Get(&min, &max, &count);
+  EXPECT_EQ(5, min);
+  EXPECT_EQ(6, max);
+  EXPECT_EQ(0, count);
+
+  it->Next();
+  EXPECT_TRUE(it->Done());
+}
+
+#if (!defined(NDEBUG) || defined(DCHECK_ALWAYS_ON)) && GTEST_HAS_DEATH_TEST
+
+TEST(SampleMapIteratorDeathTest, IterateDoneTest) {
+  SampleMap samples;
+
+  scoped_ptr<SampleCountIterator> it = samples.Iterator();
+
+  EXPECT_TRUE(it->Done());
+
+  HistogramBase::Sample min;
+  HistogramBase::Sample max;
+  HistogramBase::Count count;
+  EXPECT_DEATH(it->Get(&min, &max, &count), "");
+
+  EXPECT_DEATH(it->Next(), "");
+
+  samples.Accumulate(1, 100);
+  it = samples.Iterator();
+  EXPECT_FALSE(it->Done());
+}
+
+#endif
+// (!defined(NDEBUG) || defined(DCHECK_ALWAYS_ON)) && GTEST_HAS_DEATH_TEST
+
+}  // namespace
+}  // namespace base
diff --git a/base/metrics/sample_vector.cc b/base/metrics/sample_vector.cc
index 327a1f2..f90d80b 100644
--- a/base/metrics/sample_vector.cc
+++ b/base/metrics/sample_vector.cc
@@ -53,7 +53,7 @@ scoped_ptr<SampleCountIterator> SampleVector::Iterator() const {
 }
 
 bool SampleVector::AddSubtractImpl(SampleCountIterator* iter,
-                                   HistogramSamples::Instruction instruction) {
+                                   HistogramSamples::Operator op) {
   HistogramBase::Sample min;
   HistogramBase::Sample max;
   HistogramBase::Count count;
@@ -65,8 +65,7 @@ bool SampleVector::AddSubtractImpl(SampleCountIterator* iter,
     if (min == bucket_ranges_->range(index) &&
         max == bucket_ranges_->range(index + 1)) {
       // Sample matches this bucket!
-      counts_[index] +=
-          (instruction ==  HistogramSamples::ADD) ? count : -count;
+      counts_[index] += (op ==  HistogramSamples::ADD) ? count : -count;
       iter->Next();
     } else if (min > bucket_ranges_->range(index)) {
       // Sample is larger than current bucket range. Try next.
@@ -117,6 +116,8 @@ SampleVectorIterator::SampleVectorIterator(const vector<Count>* counts,
   SkipEmptyBuckets();
 }
 
+SampleVectorIterator::~SampleVectorIterator() {}
+
 bool SampleVectorIterator::Done() const {
   return index_ >= counts_->size();
 }
diff --git a/base/metrics/sample_vector.h b/base/metrics/sample_vector.h
index 8938d36..67c344a 100644
--- a/base/metrics/sample_vector.h
+++ b/base/metrics/sample_vector.h
@@ -39,7 +39,7 @@ class BASE_EXPORT_PRIVATE SampleVector : public HistogramSamples {
  protected:
   virtual bool AddSubtractImpl(
       SampleCountIterator* iter,
-      HistogramSamples::Instruction instruction) OVERRIDE;
+      HistogramSamples::Operator op) OVERRIDE;  // |op| is ADD or SUBTRACT.
 
   virtual size_t GetBucketIndex(HistogramBase::Sample value) const;
 
@@ -58,6 +58,7 @@ class BASE_EXPORT_PRIVATE SampleVectorIterator : public SampleCountIterator {
  public:
   SampleVectorIterator(const std::vector<HistogramBase::Count>* counts,
                        const BucketRanges* bucket_ranges);
+  virtual ~SampleVectorIterator();
 
   // SampleCountIterator implementation:
   virtual bool Done() const OVERRIDE;
@@ -65,6 +66,8 @@ class BASE_EXPORT_PRIVATE SampleVectorIterator : public SampleCountIterator {
   virtual void Get(HistogramBase::Sample* min,
                    HistogramBase::Sample* max,
                    HistogramBase::Count* count) const OVERRIDE;
+
+  // SampleVector uses predefined buckets, so iterator can return bucket index.
   virtual bool GetBucketIndex(size_t* index) const OVERRIDE;
 
  private:
diff --git a/base/metrics/sample_vector_unittest.cc b/base/metrics/sample_vector_unittest.cc
index 13e5e8b..dbbbd15 100644
--- a/base/metrics/sample_vector_unittest.cc
+++ b/base/metrics/sample_vector_unittest.cc
@@ -168,8 +168,8 @@ TEST(SampleVectorDeathTest, AddSubtractBucketNotMatchTest) {
   EXPECT_DEATH(samples1.Subtract(samples2), "");
 }
 
-// (!defined(NDEBUG) || defined(DCHECK_ALWAYS_ON)) && GTEST_HAS_DEATH_TEST
 #endif
+// (!defined(NDEBUG) || defined(DCHECK_ALWAYS_ON)) && GTEST_HAS_DEATH_TEST
 
 TEST(SampleVectorIteratorTest, IterateTest) {
   BucketRanges ranges(5);
@@ -258,8 +258,8 @@ TEST(SampleVectorIteratorDeathTest, IterateDoneTest) {
   EXPECT_FALSE(it->Done());
 }
 
-// (!defined(NDEBUG) || defined(DCHECK_ALWAYS_ON)) && GTEST_HAS_DEATH_TEST
 #endif
+// (!defined(NDEBUG) || defined(DCHECK_ALWAYS_ON)) && GTEST_HAS_DEATH_TEST
 
 }  // namespace
 }  // namespace base
diff --git a/base/metrics/sparse_histogram.cc b/base/metrics/sparse_histogram.cc
index 05a68b5..bc1913f 100644
--- a/base/metrics/sparse_histogram.cc
+++ b/base/metrics/sparse_histogram.cc
@@ -5,14 +5,18 @@
 #include "base/metrics/sparse_histogram.h"
 
 #include "base/metrics/statistics_recorder.h"
+#include "base/synchronization/lock.h"
 
+using std::map;
 using std::string;
 
 namespace base {
 
+typedef HistogramBase::Count Count;
+typedef HistogramBase::Sample Sample;
+
 // static
-HistogramBase* SparseHistogram::FactoryGet(const string& name,
-                                           int32 flags) {
+HistogramBase* SparseHistogram::FactoryGet(const string& name, int32 flags) {
   // TODO(kaiwang): Register and get SparseHistogram with StatisticsRecorder.
   HistogramBase* histogram = new SparseHistogram(name);
   histogram->SetFlags(flags);
@@ -23,12 +27,21 @@ SparseHistogram::~SparseHistogram() {}
 
 void SparseHistogram::Add(Sample value) {
   base::AutoLock auto_lock(lock_);
-  samples_[value]++;
+  sample_counts_[value]++;
+  redundant_count_ += 1;
 }
 
-void SparseHistogram::SnapshotSample(std::map<Sample, Count>* samples) const {
+scoped_ptr<SampleMap> SparseHistogram::SnapshotSamples() const {
+  scoped_ptr<SampleMap> snapshot(new SampleMap());
+
   base::AutoLock auto_lock(lock_);
-  *samples = samples_;
+  for(map<Sample, Count>::const_iterator it = sample_counts_.begin();
+      it != sample_counts_.end();
+      ++it) {
+    snapshot->Accumulate(it->first, it->second);
+  }
+  snapshot->ResetRedundantCount(redundant_count_);
+  return snapshot.Pass();
 }
 
 void SparseHistogram::WriteHTMLGraph(string* output) const {
@@ -40,6 +53,7 @@ void SparseHistogram::WriteAscii(string* output) const {
 }
 
 SparseHistogram::SparseHistogram(const string& name)
-    : HistogramBase(name) {}
+    : HistogramBase(name),
+      redundant_count_(0) {}
 
 }  // namespace base
diff --git a/base/metrics/sparse_histogram.h b/base/metrics/sparse_histogram.h
index 9ef435e..83d5d42 100644
--- a/base/metrics/sparse_histogram.h
+++ b/base/metrics/sparse_histogram.h
@@ -11,7 +11,9 @@
 #include "base/base_export.h"
 #include "base/basictypes.h"
 #include "base/compiler_specific.h"
+#include "base/memory/scoped_ptr.h"
 #include "base/metrics/histogram_base.h"
+#include "base/metrics/sample_map.h"
 #include "base/synchronization/lock.h"
 
 namespace base {
@@ -24,23 +26,23 @@ class BASE_EXPORT_PRIVATE SparseHistogram : public HistogramBase {
 
   virtual ~SparseHistogram();
 
+  // HistogramBase implementation:
   virtual void Add(Sample value) OVERRIDE;
-
-  virtual void SnapshotSample(std::map<Sample, Count>* sample) const;
   virtual void WriteHTMLGraph(std::string* output) const OVERRIDE;
   virtual void WriteAscii(std::string* output) const OVERRIDE;
 
- protected:
+  virtual scoped_ptr<SampleMap> SnapshotSamples() const;
+
+ private:
   // Clients should always use FactoryGet to create SparseHistogram.
   SparseHistogram(const std::string& name);
 
- private:
   friend class SparseHistogramTest;  // For constuctor calling.
 
-  std::map<Sample, Count> samples_;
-
-  // Protects access to above map.
+  // Protects access to |sample_counts_| and |redundant_count_|.
   mutable base::Lock lock_;
+  std::map<HistogramBase::Sample, HistogramBase::Count> sample_counts_;
+  HistogramBase::Count redundant_count_;
 
   DISALLOW_COPY_AND_ASSIGN(SparseHistogram);
 };
diff --git a/base/metrics/sparse_histogram_unittest.cc b/base/metrics/sparse_histogram_unittest.cc
index 1ed0e71..2fe614f 100644
--- a/base/metrics/sparse_histogram_unittest.cc
+++ b/base/metrics/sparse_histogram_unittest.cc
@@ -5,6 +5,7 @@
 #include <string>
 
 #include "base/memory/scoped_ptr.h"
+#include "base/metrics/sample_map.h"
 #include "base/metrics/sparse_histogram.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
@@ -19,22 +20,21 @@ class SparseHistogramTest : public testing::Test {
 
 TEST_F(SparseHistogramTest, BasicTest) {
   scoped_ptr<SparseHistogram> histogram(NewSparseHistogram("Sparse1"));
-  std::map<HistogramBase::Sample, HistogramBase::Count> sample;
-  histogram->SnapshotSample(&sample);
-
-  ASSERT_EQ(0u, sample.size());
+  scoped_ptr<SampleMap> snapshot(histogram->SnapshotSamples());
+  EXPECT_EQ(0, snapshot->TotalCount());
+  EXPECT_EQ(0, snapshot->sum());
 
   histogram->Add(100);
-  histogram->SnapshotSample(&sample);
-  ASSERT_EQ(1u, sample.size());
-  EXPECT_EQ(1, sample[100]);
+  scoped_ptr<SampleMap> snapshot1(histogram->SnapshotSamples());
+  EXPECT_EQ(1, snapshot1->TotalCount());
+  EXPECT_EQ(1, snapshot1->GetCount(100));
 
   histogram->Add(100);
   histogram->Add(101);
-  histogram->SnapshotSample(&sample);
-  ASSERT_EQ(2u, sample.size());
-  EXPECT_EQ(2, sample[100]);
-  EXPECT_EQ(1, sample[101]);
+  scoped_ptr<SampleMap> snapshot2(histogram->SnapshotSamples());
+  EXPECT_EQ(3, snapshot2->TotalCount());
+  EXPECT_EQ(2, snapshot2->GetCount(100));
+  EXPECT_EQ(1, snapshot2->GetCount(101));
 }
 
 }  // namespace base