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   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 < 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_->bucket_count();
     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_GE(bucket_ranges_->bucket_count(), 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
    162