SampleSet -> HistogramSamples (will be reused by SparseHistogram)

base/metrics/sample_vector.cc

+// 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_vector.h"
+
+#include "base/logging.h"
+#include "base/metrics/bucket_ranges.h"
+
+using std::vector;
+
+namespace base {
+
+typedef HistogramBase::Count Count;
+typedef HistogramBase::Sample Sample;
+
+SampleVector::SampleVector(const BucketRanges* bucket_ranges)
+    : counts_(bucket_ranges->size() - 1),
+      bucket_ranges_(bucket_ranges) {
+  CHECK_GE(bucket_ranges_->size(), 2u);
+}
+
+SampleVector::~SampleVector() {}
+
+void SampleVector::Accumulate(Sample value, Count count) {
+  size_t bucket_index = GetBucketIndex(value);
+  counts_[bucket_index] += count;
+  IncreaseSum(count * value);
+  IncreaseRedundantCount(count);
+}
+
+Count SampleVector::GetCount(Sample value) const {
+  size_t bucket_index = GetBucketIndex(value);
+  return counts_[bucket_index];
+}
+
+Count SampleVector::TotalCount() const {
+  Count count = 0;
+  for (size_t i = 0; i < counts_.size(); i++) {
+    count += counts_[i];
+  }
+  return count;
+}
+
+Count SampleVector::GetCountAtIndex(size_t bucket_index) const {
+  DCHECK(bucket_index >= 0 && bucket_index < counts_.size());
+  return counts_[bucket_index];
+}
+
+scoped_ptr<SampleCountIterator> SampleVector::Iterator() const {
+  return scoped_ptr<SampleCountIterator>(
+      new SampleVectorIterator(&counts_, bucket_ranges_));
+}
+
+bool SampleVector::AddSubtractImpl(SampleCountIterator* iter,
+                                   HistogramSamples::Instruction instruction) {
+  HistogramBase::Sample min;
+  HistogramBase::Sample max;
+  HistogramBase::Count count;
+
+  // Go through the iterator and add the counts into correct bucket.
+  size_t index = 0;
+  while (index < counts_.size() && !iter->Done()) {
+    iter->Get(&min, &max, &count);
+    if (min == bucket_ranges_->range(index) &&
+        max == bucket_ranges_->range(index + 1)) {
+      // Sample matches this bucket!
+      counts_[index] +=
+          (instruction ==  HistogramSamples::ADD) ? count : -count;
+      iter->Next();
+    } else if (min > bucket_ranges_->range(index)) {
+      // Sample is larger than current bucket range. Try next.
+      index++;
+    } else {
+      // Sample is smaller than current bucket range. We scan buckets from
+      // smallest to largest, so the sample value must be invalid.
+      return false;
+    }
+  }
+
+  return iter->Done();
+}
+
+// Use simple binary search.  This is very general, but there are better
+// approaches if we knew that the buckets were linearly distributed.
+size_t SampleVector::GetBucketIndex(Sample value) const {
+  size_t bucket_count = bucket_ranges_->size() - 1;
+  CHECK_GE(bucket_count, 1u);
+  CHECK_GE(value, bucket_ranges_->range(0));
+  CHECK_LT(value, bucket_ranges_->range(bucket_count));
+
+  size_t under = 0;
+  size_t over = bucket_count;
+  size_t mid;
+  do {
+    DCHECK_GE(over, under);
+    mid = under + (over - under)/2;
+    if (mid == under)
+      break;
+    if (bucket_ranges_->range(mid) <= value)
+      under = mid;
+    else
+      over = mid;
+  } while (true);
+
+  DCHECK_LE(bucket_ranges_->range(mid), value);
+  CHECK_GT(bucket_ranges_->range(mid + 1), value);
+  return mid;
+}
+
+SampleVectorIterator::SampleVectorIterator(const vector<Count>* counts,
+                                           const BucketRanges* bucket_ranges)
+    : counts_(counts),
+      bucket_ranges_(bucket_ranges),
+      index_(0) {
+  CHECK_GT(bucket_ranges_->size(), counts_->size());
+  SkipEmptyBuckets();
+}
+
+bool SampleVectorIterator::Done() const {
+  return index_ >= counts_->size();
+}
+
+void SampleVectorIterator::Next() {
+  CHECK(!Done());

[Ilya Sherman, 2012/09/21 08:52:12]

nit: DCHECK

[kaiwang, 2012/09/21 19:51:18]

Done.

+  index_++;
+  SkipEmptyBuckets();
+}
+
+void SampleVectorIterator::Get(HistogramBase::Sample* min,
+                               HistogramBase::Sample* max,
+                               HistogramBase::Count* count) const {
+  CHECK(!Done());

[Ilya Sherman, 2012/09/21 08:52:12]

nit: DCHECK

[kaiwang, 2012/09/21 19:51:18]

Done.

+  if (min != NULL)
+    *min = bucket_ranges_->range(index_);
+  if (max != NULL)
+    *max = bucket_ranges_->range(index_ + 1);
+  if (count != NULL)
+    *count = (*counts_)[index_];
+}
+
+bool SampleVectorIterator::GetBucketIndex(size_t* index) const {
+  CHECK(!Done());

[Ilya Sherman, 2012/09/21 08:52:12]

nit: DCHECK

[kaiwang, 2012/09/21 19:51:18]

Done.

+  if (index != NULL)
+    *index = index_;
+  return true;
+}
+
+void SampleVectorIterator::SkipEmptyBuckets() {
+  if (Done())
+    return;
+
+  while (index_ < counts_->size()) {
+    if ((*counts_)[index_] != 0)
+      return;
+    index_++;
+  }
+}
+
+}  // namespace base