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 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
    166