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
SampleVector(const BucketRanges * bucket_ranges)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
~SampleVector()23 SampleVector::~SampleVector() {}
24
Accumulate(Sample value,Count count)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
GetCount(Sample value) const33 Count SampleVector::GetCount(Sample value) const {
34 size_t bucket_index = GetBucketIndex(value);
35 return subtle::NoBarrier_Load(&counts_[bucket_index]);
36 }
37
TotalCount() const38 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
GetCountAtIndex(size_t bucket_index) const46 Count SampleVector::GetCountAtIndex(size_t bucket_index) const {
47 DCHECK(bucket_index < counts_.size());
48 return subtle::NoBarrier_Load(&counts_[bucket_index]);
49 }
50
Iterator() const51 scoped_ptr<SampleCountIterator> SampleVector::Iterator() const {
52 return scoped_ptr<SampleCountIterator>(
53 new SampleVectorIterator(&counts_, bucket_ranges_));
54 }
55
AddSubtractImpl(SampleCountIterator * iter,HistogramSamples::Operator op)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.
GetBucketIndex(Sample value) const89 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
SampleVectorIterator(const vector<Count> * counts,const BucketRanges * bucket_ranges)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
~SampleVectorIterator()123 SampleVectorIterator::~SampleVectorIterator() {}
124
Done() const125 bool SampleVectorIterator::Done() const {
126 return index_ >= counts_->size();
127 }
128
Next()129 void SampleVectorIterator::Next() {
130 DCHECK(!Done());
131 index_++;
132 SkipEmptyBuckets();
133 }
134
Get(HistogramBase::Sample * min,HistogramBase::Sample * max,HistogramBase::Count * count) const135 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
GetBucketIndex(size_t * index) const147 bool SampleVectorIterator::GetBucketIndex(size_t* index) const {
148 DCHECK(!Done());
149 if (index != NULL)
150 *index = index_;
151 return true;
152 }
153
SkipEmptyBuckets()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