1// Copyright (c) 2012 The Chromium Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#include "base/metrics/sample_vector.h" 6 7#include "base/logging.h" 8#include "base/metrics/bucket_ranges.h" 9 10using std::vector; 11 12namespace base { 13 14typedef HistogramBase::Count Count; 15typedef HistogramBase::Sample Sample; 16 17SampleVector::SampleVector(const BucketRanges* bucket_ranges) 18 : counts_(bucket_ranges->bucket_count()), 19 bucket_ranges_(bucket_ranges) { 20 CHECK_GE(bucket_ranges_->bucket_count(), 1u); 21} 22 23SampleVector::~SampleVector() {} 24 25void SampleVector::Accumulate(Sample value, Count count) { 26 size_t bucket_index = GetBucketIndex(value); 27 counts_[bucket_index] += count; 28 IncreaseSum(count * value); 29 IncreaseRedundantCount(count); 30} 31 32Count SampleVector::GetCount(Sample value) const { 33 size_t bucket_index = GetBucketIndex(value); 34 return counts_[bucket_index]; 35} 36 37Count SampleVector::TotalCount() const { 38 Count count = 0; 39 for (size_t i = 0; i < counts_.size(); i++) { 40 count += counts_[i]; 41 } 42 return count; 43} 44 45Count SampleVector::GetCountAtIndex(size_t bucket_index) const { 46 DCHECK(bucket_index < counts_.size()); 47 return counts_[bucket_index]; 48} 49 50scoped_ptr<SampleCountIterator> SampleVector::Iterator() const { 51 return scoped_ptr<SampleCountIterator>( 52 new SampleVectorIterator(&counts_, bucket_ranges_)); 53} 54 55bool SampleVector::AddSubtractImpl(SampleCountIterator* iter, 56 HistogramSamples::Operator op) { 57 HistogramBase::Sample min; 58 HistogramBase::Sample max; 59 HistogramBase::Count count; 60 61 // Go through the iterator and add the counts into correct bucket. 62 size_t index = 0; 63 while (index < counts_.size() && !iter->Done()) { 64 iter->Get(&min, &max, &count); 65 if (min == bucket_ranges_->range(index) && 66 max == bucket_ranges_->range(index + 1)) { 67 // Sample matches this bucket! 68 counts_[index] += (op == HistogramSamples::ADD) ? count : -count; 69 iter->Next(); 70 } else if (min > bucket_ranges_->range(index)) { 71 // Sample is larger than current bucket range. Try next. 72 index++; 73 } else { 74 // Sample is smaller than current bucket range. We scan buckets from 75 // smallest to largest, so the sample value must be invalid. 76 return false; 77 } 78 } 79 80 return iter->Done(); 81} 82 83// Use simple binary search. This is very general, but there are better 84// approaches if we knew that the buckets were linearly distributed. 85size_t SampleVector::GetBucketIndex(Sample value) const { 86 size_t bucket_count = bucket_ranges_->bucket_count(); 87 CHECK_GE(bucket_count, 1u); 88 CHECK_GE(value, bucket_ranges_->range(0)); 89 CHECK_LT(value, bucket_ranges_->range(bucket_count)); 90 91 size_t under = 0; 92 size_t over = bucket_count; 93 size_t mid; 94 do { 95 DCHECK_GE(over, under); 96 mid = under + (over - under)/2; 97 if (mid == under) 98 break; 99 if (bucket_ranges_->range(mid) <= value) 100 under = mid; 101 else 102 over = mid; 103 } while (true); 104 105 DCHECK_LE(bucket_ranges_->range(mid), value); 106 CHECK_GT(bucket_ranges_->range(mid + 1), value); 107 return mid; 108} 109 110SampleVectorIterator::SampleVectorIterator(const vector<Count>* counts, 111 const BucketRanges* bucket_ranges) 112 : counts_(counts), 113 bucket_ranges_(bucket_ranges), 114 index_(0) { 115 CHECK_GE(bucket_ranges_->bucket_count(), counts_->size()); 116 SkipEmptyBuckets(); 117} 118 119SampleVectorIterator::~SampleVectorIterator() {} 120 121bool SampleVectorIterator::Done() const { 122 return index_ >= counts_->size(); 123} 124 125void SampleVectorIterator::Next() { 126 DCHECK(!Done()); 127 index_++; 128 SkipEmptyBuckets(); 129} 130 131void SampleVectorIterator::Get(HistogramBase::Sample* min, 132 HistogramBase::Sample* max, 133 HistogramBase::Count* count) const { 134 DCHECK(!Done()); 135 if (min != NULL) 136 *min = bucket_ranges_->range(index_); 137 if (max != NULL) 138 *max = bucket_ranges_->range(index_ + 1); 139 if (count != NULL) 140 *count = (*counts_)[index_]; 141} 142 143bool SampleVectorIterator::GetBucketIndex(size_t* index) const { 144 DCHECK(!Done()); 145 if (index != NULL) 146 *index = index_; 147 return true; 148} 149 150void SampleVectorIterator::SkipEmptyBuckets() { 151 if (Done()) 152 return; 153 154 while (index_ < counts_->size()) { 155 if ((*counts_)[index_] != 0) 156 return; 157 index_++; 158 } 159} 160 161} // namespace base 162