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