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