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