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