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