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->size() - 1),
  19       bucket_ranges_(bucket_ranges) {
  20   CHECK_GE(bucket_ranges_->size(), 2u);
  21 }
  22
  23 SampleVector::~SampleVector() {}
  24
  25 void 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
  32 Count SampleVector::GetCount(Sample value) const {
  33   size_t bucket_index = GetBucketIndex(value);
  34   return counts_[bucket_index];
  35 }
  36
  37 Count 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
  45 Count SampleVector::GetCountAtIndex(size_t bucket_index) const {
  46   DCHECK(bucket_index >= 0 && bucket_index < counts_.size());
  47   return counts_[bucket_index];
  48 }
  49
  50 scoped_ptr<SampleCountIterator> SampleVector::Iterator() const {
  51   return scoped_ptr<SampleCountIterator>(
  52       new SampleVectorIterator(&counts_, bucket_ranges_));
  53 }
  54
  55 bool 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.
  85 size_t SampleVector::GetBucketIndex(Sample value) const {
  86   size_t bucket_count = bucket_ranges_->size() - 1;
  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
 110 SampleVectorIterator::SampleVectorIterator(const vector<Count>* counts,
 111                                            const BucketRanges* bucket_ranges)
 112     : counts_(counts),
 113       bucket_ranges_(bucket_ranges),
 114       index_(0) {
 115   CHECK_GT(bucket_ranges_->size(), counts_->size());
 116   SkipEmptyBuckets();
 117 }
 118
 119 SampleVectorIterator::~SampleVectorIterator() {}
 120
 121 bool SampleVectorIterator::Done() const {
 122   return index_ >= counts_->size();
 123 }
 124
 125 void SampleVectorIterator::Next() {
 126   DCHECK(!Done());
 127   index_++;
 128   SkipEmptyBuckets();
 129 }
 130
 131 void 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
 143 bool SampleVectorIterator::GetBucketIndex(size_t* index) const {
 144   DCHECK(!Done());
 145   if (index != NULL)
 146     *index = index_;
 147   return true;
 148 }
 149
 150 void 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