blob: 8f1451035ecce1a97acd9dd60d50e5a39e033554 [file] [log] [blame]
// 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