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