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