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 subtle::NoBarrier_Load(&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 += subtle::NoBarrier_Load(&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 subtle::NoBarrier_Load(&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 HistogramBase::Count old_counts = 70 subtle::NoBarrier_Load(&counts_[index]); 71 subtle::NoBarrier_Store(&counts_[index], 72 old_counts + ((op == HistogramSamples::ADD) ? count : -count)); 73 iter->Next(); 74 } else if (min > bucket_ranges_->range(index)) { 75 // Sample is larger than current bucket range. Try next. 76 index++; 77 } else { 78 // Sample is smaller than current bucket range. We scan buckets from 79 // smallest to largest, so the sample value must be invalid. 80 return false; 81 } 82 } 83 84 return iter->Done(); 85 } 86 87 // Use simple binary search. This is very general, but there are better 88 // approaches if we knew that the buckets were linearly distributed. 89 size_t SampleVector::GetBucketIndex(Sample value) const { 90 size_t bucket_count = bucket_ranges_->bucket_count(); 91 CHECK_GE(bucket_count, 1u); 92 CHECK_GE(value, bucket_ranges_->range(0)); 93 CHECK_LT(value, bucket_ranges_->range(bucket_count)); 94 95 size_t under = 0; 96 size_t over = bucket_count; 97 size_t mid; 98 do { 99 DCHECK_GE(over, under); 100 mid = under + (over - under)/2; 101 if (mid == under) 102 break; 103 if (bucket_ranges_->range(mid) <= value) 104 under = mid; 105 else 106 over = mid; 107 } while (true); 108 109 DCHECK_LE(bucket_ranges_->range(mid), value); 110 CHECK_GT(bucket_ranges_->range(mid + 1), value); 111 return mid; 112 } 113 114 SampleVectorIterator::SampleVectorIterator(const vector<Count>* counts, 115 const BucketRanges* bucket_ranges) 116 : counts_(counts), 117 bucket_ranges_(bucket_ranges), 118 index_(0) { 119 CHECK_GE(bucket_ranges_->bucket_count(), counts_->size()); 120 SkipEmptyBuckets(); 121 } 122 123 SampleVectorIterator::~SampleVectorIterator() {} 124 125 bool SampleVectorIterator::Done() const { 126 return index_ >= counts_->size(); 127 } 128 129 void SampleVectorIterator::Next() { 130 DCHECK(!Done()); 131 index_++; 132 SkipEmptyBuckets(); 133 } 134 135 void SampleVectorIterator::Get(HistogramBase::Sample* min, 136 HistogramBase::Sample* max, 137 HistogramBase::Count* count) const { 138 DCHECK(!Done()); 139 if (min != NULL) 140 *min = bucket_ranges_->range(index_); 141 if (max != NULL) 142 *max = bucket_ranges_->range(index_ + 1); 143 if (count != NULL) 144 *count = subtle::NoBarrier_Load(&(*counts_)[index_]); 145 } 146 147 bool SampleVectorIterator::GetBucketIndex(size_t* index) const { 148 DCHECK(!Done()); 149 if (index != NULL) 150 *index = index_; 151 return true; 152 } 153 154 void SampleVectorIterator::SkipEmptyBuckets() { 155 if (Done()) 156 return; 157 158 while (index_ < counts_->size()) { 159 if (subtle::NoBarrier_Load(&(*counts_)[index_]) != 0) 160 return; 161 index_++; 162 } 163 } 164 165 } // namespace base 166