| // 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 < 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::Operator op) { |
| 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] += (op == 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(); |
| } |
| |
| SampleVectorIterator::~SampleVectorIterator() {} |
| |
| bool SampleVectorIterator::Done() const { |
| return index_ >= counts_->size(); |
| } |
| |
| void SampleVectorIterator::Next() { |
| DCHECK(!Done()); |
| index_++; |
| SkipEmptyBuckets(); |
| } |
| |
| void SampleVectorIterator::Get(HistogramBase::Sample* min, |
| HistogramBase::Sample* max, |
| HistogramBase::Count* count) const { |
| DCHECK(!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 { |
| DCHECK(!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 |