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