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 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 += 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 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 counts_[index] += (op == HistogramSamples::ADD) ? count : -count;
70 iter->Next();
71 } else if (min > bucket_ranges_->range(index)) {
72 // Sample is larger than current bucket range. Try next.
73 index++;
74 } else {
75 // Sample is smaller than current bucket range. We scan buckets from
76 // smallest to largest, so the sample value must be invalid.
77 return false;
78 }
79 }
80
81 return iter->Done();
82 }
83
84 // Use simple binary search. This is very general, but there are better
85 // approaches if we knew that the buckets were linearly distributed.
GetBucketIndex(Sample value) const86 size_t SampleVector::GetBucketIndex(Sample value) const {
87 size_t bucket_count = bucket_ranges_->bucket_count();
88 CHECK_GE(bucket_count, 1u);
89 CHECK_GE(value, bucket_ranges_->range(0));
90 CHECK_LT(value, bucket_ranges_->range(bucket_count));
91
92 size_t under = 0;
93 size_t over = bucket_count;
94 size_t mid;
95 do {
96 DCHECK_GE(over, under);
97 mid = under + (over - under)/2;
98 if (mid == under)
99 break;
100 if (bucket_ranges_->range(mid) <= value)
101 under = mid;
102 else
103 over = mid;
104 } while (true);
105
106 DCHECK_LE(bucket_ranges_->range(mid), value);
107 CHECK_GT(bucket_ranges_->range(mid + 1), value);
108 return mid;
109 }
110
SampleVectorIterator(const vector<Count> * counts,const BucketRanges * bucket_ranges)111 SampleVectorIterator::SampleVectorIterator(const vector<Count>* counts,
112 const BucketRanges* bucket_ranges)
113 : counts_(counts),
114 bucket_ranges_(bucket_ranges),
115 index_(0) {
116 CHECK_GE(bucket_ranges_->bucket_count(), counts_->size());
117 SkipEmptyBuckets();
118 }
119
~SampleVectorIterator()120 SampleVectorIterator::~SampleVectorIterator() {}
121
Done() const122 bool SampleVectorIterator::Done() const {
123 return index_ >= counts_->size();
124 }
125
Next()126 void SampleVectorIterator::Next() {
127 DCHECK(!Done());
128 index_++;
129 SkipEmptyBuckets();
130 }
131
Get(HistogramBase::Sample * min,HistogramBase::Sample * max,HistogramBase::Count * count) const132 void SampleVectorIterator::Get(HistogramBase::Sample* min,
133 HistogramBase::Sample* max,
134 HistogramBase::Count* count) const {
135 DCHECK(!Done());
136 if (min != NULL)
137 *min = bucket_ranges_->range(index_);
138 if (max != NULL)
139 *max = bucket_ranges_->range(index_ + 1);
140 if (count != NULL)
141 *count = (*counts_)[index_];
142 }
143
GetBucketIndex(size_t * index) const144 bool SampleVectorIterator::GetBucketIndex(size_t* index) const {
145 DCHECK(!Done());
146 if (index != NULL)
147 *index = index_;
148 return true;
149 }
150
SkipEmptyBuckets()151 void SampleVectorIterator::SkipEmptyBuckets() {
152 if (Done())
153 return;
154
155 while (index_ < counts_->size()) {
156 if ((*counts_)[index_] != 0)
157 return;
158 index_++;
159 }
160 }
161
162 } // namespace base
163