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
SampleVector(const BucketRanges * bucket_ranges)15 SampleVector::SampleVector(const BucketRanges* bucket_ranges)
16 : SampleVector(0, bucket_ranges) {}
17
SampleVector(uint64_t id,const BucketRanges * bucket_ranges)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
SampleVector(uint64_t id,HistogramBase::AtomicCount * counts,size_t,Metadata * meta,const BucketRanges * bucket_ranges)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
~SampleVector()40 SampleVector::~SampleVector() {}
41
Accumulate(Sample value,Count count)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
GetCount(Sample value) const50 Count SampleVector::GetCount(Sample value) const {
51 size_t bucket_index = GetBucketIndex(value);
52 return subtle::NoBarrier_Load(&counts_[bucket_index]);
53 }
54
TotalCount() const55 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
GetCountAtIndex(size_t bucket_index) const63 Count SampleVector::GetCountAtIndex(size_t bucket_index) const {
64 DCHECK(bucket_index < counts_size_);
65 return subtle::NoBarrier_Load(&counts_[bucket_index]);
66 }
67
Iterator() const68 scoped_ptr<SampleCountIterator> SampleVector::Iterator() const {
69 return scoped_ptr<SampleCountIterator>(
70 new SampleVectorIterator(counts_, counts_size_, bucket_ranges_));
71 }
72
AddSubtractImpl(SampleCountIterator * iter,HistogramSamples::Operator op)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.
GetBucketIndex(Sample value) const106 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
SampleVectorIterator(const std::vector<HistogramBase::AtomicCount> * counts,const BucketRanges * bucket_ranges)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
SampleVectorIterator(const HistogramBase::AtomicCount * counts,size_t counts_size,const BucketRanges * bucket_ranges)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
~SampleVectorIterator()154 SampleVectorIterator::~SampleVectorIterator() {}
155
Done() const156 bool SampleVectorIterator::Done() const {
157 return index_ >= counts_size_;
158 }
159
Next()160 void SampleVectorIterator::Next() {
161 DCHECK(!Done());
162 index_++;
163 SkipEmptyBuckets();
164 }
165
Get(HistogramBase::Sample * min,HistogramBase::Sample * max,HistogramBase::Count * count) const166 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
GetBucketIndex(size_t * index) const178 bool SampleVectorIterator::GetBucketIndex(size_t* index) const {
179 DCHECK(!Done());
180 if (index != NULL)
181 *index = index_;
182 return true;
183 }
184
SkipEmptyBuckets()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