Home | History | Annotate | Download | only in metrics
      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
    163