base/metrics/sample_vector.cc

   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
  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
  23 SampleVector::~SampleVector() {}
  24
  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
  33 Count SampleVector::GetCount(Sample value) const {
  34   size_t bucket_index = GetBucketIndex(value);
  35   return counts_[bucket_index];
  36 }
  37
  38 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
  46 Count SampleVector::GetCountAtIndex(size_t bucket_index) const {
  47   DCHECK(bucket_index < counts_.size());
  48   return counts_[bucket_index];
  49 }
  50
  51 scoped_ptr<SampleCountIterator> SampleVector::Iterator() const {
  52   return scoped_ptr<SampleCountIterator>(
  53       new SampleVectorIterator(&counts_, bucket_ranges_));
  54 }
  55
  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.
  86 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
 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
 120 SampleVectorIterator::~SampleVectorIterator() {}
 121
 122 bool SampleVectorIterator::Done() const {
 123   return index_ >= counts_->size();
 124 }
 125
 126 void SampleVectorIterator::Next() {
 127   DCHECK(!Done());
 128   index_++;
 129   SkipEmptyBuckets();
 130 }
 131
 132 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
 144 bool SampleVectorIterator::GetBucketIndex(size_t* index) const {
 145   DCHECK(!Done());
 146   if (index != NULL)
 147     *index = index_;
 148   return true;
 149 }
 150
 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