sample_vector.cc revision 58537e28ecd584eab876aee8be7156509866d23a 
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
10using std::vector;
11
12namespace base {
13
14typedef HistogramBase::Count Count;
15typedef HistogramBase::Sample Sample;
16
17SampleVector::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
23SampleVector::~SampleVector() {}
24
25void 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
33Count SampleVector::GetCount(Sample value) const {
34  size_t bucket_index = GetBucketIndex(value);
35  return counts_[bucket_index];
36}
37
38Count 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
46Count SampleVector::GetCountAtIndex(size_t bucket_index) const {
47  DCHECK(bucket_index < counts_.size());
48  return counts_[bucket_index];
49}
50
51scoped_ptr<SampleCountIterator> SampleVector::Iterator() const {
52  return scoped_ptr<SampleCountIterator>(
53      new SampleVectorIterator(&counts_, bucket_ranges_));
54}
55
56bool 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.
86size_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
111SampleVectorIterator::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
120SampleVectorIterator::~SampleVectorIterator() {}
121
122bool SampleVectorIterator::Done() const {
123  return index_ >= counts_->size();
124}
125
126void SampleVectorIterator::Next() {
127  DCHECK(!Done());
128  index_++;
129  SkipEmptyBuckets();
130}
131
132void 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
144bool SampleVectorIterator::GetBucketIndex(size_t* index) const {
145  DCHECK(!Done());
146  if (index != NULL)
147    *index = index_;
148  return true;
149}
150
151void 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