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
10namespace base {
11
12typedef HistogramBase::Count Count;
13typedef HistogramBase::Sample Sample;
14
15SampleVector::SampleVector(const BucketRanges* bucket_ranges)
16    : SampleVector(0, bucket_ranges) {}
17
18SampleVector::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
27SampleVector::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
40SampleVector::~SampleVector() {}
41
42void SampleVector::Accumulate(Sample value, Count count) {
43  size_t bucket_index = GetBucketIndex(value);
44  subtle::NoBarrier_AtomicIncrement(&counts_[bucket_index], count);
45  IncreaseSum(static_cast<int64_t>(count) * value);
46  IncreaseRedundantCount(count);
47}
48
49Count SampleVector::GetCount(Sample value) const {
50  size_t bucket_index = GetBucketIndex(value);
51  return subtle::NoBarrier_Load(&counts_[bucket_index]);
52}
53
54Count SampleVector::TotalCount() const {
55  Count count = 0;
56  for (size_t i = 0; i < counts_size_; i++) {
57    count += subtle::NoBarrier_Load(&counts_[i]);
58  }
59  return count;
60}
61
62Count SampleVector::GetCountAtIndex(size_t bucket_index) const {
63  DCHECK(bucket_index < counts_size_);
64  return subtle::NoBarrier_Load(&counts_[bucket_index]);
65}
66
67std::unique_ptr<SampleCountIterator> SampleVector::Iterator() const {
68  return std::unique_ptr<SampleCountIterator>(
69      new SampleVectorIterator(counts_, counts_size_, bucket_ranges_));
70}
71
72bool SampleVector::AddSubtractImpl(SampleCountIterator* iter,
73                                   HistogramSamples::Operator op) {
74  HistogramBase::Sample min;
75  HistogramBase::Sample max;
76  HistogramBase::Count count;
77
78  // Go through the iterator and add the counts into correct bucket.
79  size_t index = 0;
80  while (index < counts_size_ && !iter->Done()) {
81    iter->Get(&min, &max, &count);
82    if (min == bucket_ranges_->range(index) &&
83        max == bucket_ranges_->range(index + 1)) {
84      // Sample matches this bucket!
85      subtle::NoBarrier_AtomicIncrement(
86          &counts_[index], op == HistogramSamples::ADD ? count : -count);
87      iter->Next();
88    } else if (min > bucket_ranges_->range(index)) {
89      // Sample is larger than current bucket range. Try next.
90      index++;
91    } else {
92      // Sample is smaller than current bucket range. We scan buckets from
93      // smallest to largest, so the sample value must be invalid.
94      return false;
95    }
96  }
97
98  return iter->Done();
99}
100
101// Use simple binary search.  This is very general, but there are better
102// approaches if we knew that the buckets were linearly distributed.
103size_t SampleVector::GetBucketIndex(Sample value) const {
104  size_t bucket_count = bucket_ranges_->bucket_count();
105  CHECK_GE(bucket_count, 1u);
106  CHECK_GE(value, bucket_ranges_->range(0));
107  CHECK_LT(value, bucket_ranges_->range(bucket_count));
108
109  size_t under = 0;
110  size_t over = bucket_count;
111  size_t mid;
112  do {
113    DCHECK_GE(over, under);
114    mid = under + (over - under)/2;
115    if (mid == under)
116      break;
117    if (bucket_ranges_->range(mid) <= value)
118      under = mid;
119    else
120      over = mid;
121  } while (true);
122
123  DCHECK_LE(bucket_ranges_->range(mid), value);
124  CHECK_GT(bucket_ranges_->range(mid + 1), value);
125  return mid;
126}
127
128SampleVectorIterator::SampleVectorIterator(
129    const std::vector<HistogramBase::AtomicCount>* counts,
130    const BucketRanges* bucket_ranges)
131    : counts_(&(*counts)[0]),
132      counts_size_(counts->size()),
133      bucket_ranges_(bucket_ranges),
134      index_(0) {
135  CHECK_GE(bucket_ranges_->bucket_count(), counts_size_);
136  SkipEmptyBuckets();
137}
138
139SampleVectorIterator::SampleVectorIterator(
140    const HistogramBase::AtomicCount* counts,
141    size_t counts_size,
142    const BucketRanges* bucket_ranges)
143    : counts_(counts),
144      counts_size_(counts_size),
145      bucket_ranges_(bucket_ranges),
146      index_(0) {
147  CHECK_GE(bucket_ranges_->bucket_count(), counts_size_);
148  SkipEmptyBuckets();
149}
150
151SampleVectorIterator::~SampleVectorIterator() {}
152
153bool SampleVectorIterator::Done() const {
154  return index_ >= counts_size_;
155}
156
157void SampleVectorIterator::Next() {
158  DCHECK(!Done());
159  index_++;
160  SkipEmptyBuckets();
161}
162
163void SampleVectorIterator::Get(HistogramBase::Sample* min,
164                               HistogramBase::Sample* max,
165                               HistogramBase::Count* count) const {
166  DCHECK(!Done());
167  if (min != NULL)
168    *min = bucket_ranges_->range(index_);
169  if (max != NULL)
170    *max = bucket_ranges_->range(index_ + 1);
171  if (count != NULL)
172    *count = subtle::NoBarrier_Load(&counts_[index_]);
173}
174
175bool SampleVectorIterator::GetBucketIndex(size_t* index) const {
176  DCHECK(!Done());
177  if (index != NULL)
178    *index = index_;
179  return true;
180}
181
182void SampleVectorIterator::SkipEmptyBuckets() {
183  if (Done())
184    return;
185
186  while (index_ < counts_size_) {
187    if (subtle::NoBarrier_Load(&counts_[index_]) != 0)
188      return;
189    index_++;
190  }
191}
192
193}  // namespace base
194