15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved.
25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be
35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file.
45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/metrics/sample_vector.h"
65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/logging.h"
85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/metrics/bucket_ranges.h"
95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using std::vector;
115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace base {
135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef HistogramBase::Count Count;
155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef HistogramBase::Sample Sample;
165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SampleVector::SampleVector(const BucketRanges* bucket_ranges)
18eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch    : counts_(bucket_ranges->bucket_count()),
195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      bucket_ranges_(bucket_ranges) {
20eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  CHECK_GE(bucket_ranges_->bucket_count(), 1u);
215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SampleVector::~SampleVector() {}
245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SampleVector::Accumulate(Sample value, Count count) {
265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  size_t bucket_index = GetBucketIndex(value);
2758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)  subtle::NoBarrier_Store(&counts_[bucket_index],
2858537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)      subtle::NoBarrier_Load(&counts_[bucket_index]) + count);
295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  IncreaseSum(count * value);
305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  IncreaseRedundantCount(count);
315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Count SampleVector::GetCount(Sample value) const {
345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  size_t bucket_index = GetBucketIndex(value);
355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  return subtle::NoBarrier_Load(&counts_[bucket_index]);
365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Count SampleVector::TotalCount() const {
395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Count count = 0;
405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (size_t i = 0; i < counts_.size(); i++) {
415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    count += subtle::NoBarrier_Load(&counts_[i]);
425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return count;
445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Count SampleVector::GetCountAtIndex(size_t bucket_index) const {
47c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  DCHECK(bucket_index < counts_.size());
485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  return subtle::NoBarrier_Load(&counts_[bucket_index]);
495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)scoped_ptr<SampleCountIterator> SampleVector::Iterator() const {
525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return scoped_ptr<SampleCountIterator>(
535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      new SampleVectorIterator(&counts_, bucket_ranges_));
545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool SampleVector::AddSubtractImpl(SampleCountIterator* iter,
575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)                                   HistogramSamples::Operator op) {
585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  HistogramBase::Sample min;
595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  HistogramBase::Sample max;
605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  HistogramBase::Count count;
615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Go through the iterator and add the counts into correct bucket.
635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  size_t index = 0;
645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  while (index < counts_.size() && !iter->Done()) {
655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    iter->Get(&min, &max, &count);
665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (min == bucket_ranges_->range(index) &&
675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)        max == bucket_ranges_->range(index + 1)) {
685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      // Sample matches this bucket!
695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      HistogramBase::Count old_counts =
705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)          subtle::NoBarrier_Load(&counts_[index]);
715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      subtle::NoBarrier_Store(&counts_[index],
725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)          old_counts + ((op ==  HistogramSamples::ADD) ? count : -count));
735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      iter->Next();
745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    } else if (min > bucket_ranges_->range(index)) {
755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      // Sample is larger than current bucket range. Try next.
765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      index++;
775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    } else {
785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      // Sample is smaller than current bucket range. We scan buckets from
795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      // smallest to largest, so the sample value must be invalid.
805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      return false;
815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return iter->Done();
855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use simple binary search.  This is very general, but there are better
885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// approaches if we knew that the buckets were linearly distributed.
895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)size_t SampleVector::GetBucketIndex(Sample value) const {
90eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  size_t bucket_count = bucket_ranges_->bucket_count();
915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK_GE(bucket_count, 1u);
925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK_GE(value, bucket_ranges_->range(0));
935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK_LT(value, bucket_ranges_->range(bucket_count));
945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  size_t under = 0;
965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  size_t over = bucket_count;
975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  size_t mid;
985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  do {
995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    DCHECK_GE(over, under);
1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    mid = under + (over - under)/2;
1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (mid == under)
1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      break;
1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (bucket_ranges_->range(mid) <= value)
1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      under = mid;
1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    else
1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      over = mid;
1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  } while (true);
1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  DCHECK_LE(bucket_ranges_->range(mid), value);
1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK_GT(bucket_ranges_->range(mid + 1), value);
1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return mid;
1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SampleVectorIterator::SampleVectorIterator(const vector<Count>* counts,
1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)                                           const BucketRanges* bucket_ranges)
1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    : counts_(counts),
1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      bucket_ranges_(bucket_ranges),
1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      index_(0) {
119eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  CHECK_GE(bucket_ranges_->bucket_count(), counts_->size());
1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SkipEmptyBuckets();
1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SampleVectorIterator::~SampleVectorIterator() {}
1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool SampleVectorIterator::Done() const {
1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return index_ >= counts_->size();
1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SampleVectorIterator::Next() {
1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  DCHECK(!Done());
1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  index_++;
1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SkipEmptyBuckets();
1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SampleVectorIterator::Get(HistogramBase::Sample* min,
1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)                               HistogramBase::Sample* max,
1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)                               HistogramBase::Count* count) const {
1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  DCHECK(!Done());
1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (min != NULL)
1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    *min = bucket_ranges_->range(index_);
1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (max != NULL)
1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    *max = bucket_ranges_->range(index_ + 1);
1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (count != NULL)
1445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    *count = subtle::NoBarrier_Load(&(*counts_)[index_]);
1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool SampleVectorIterator::GetBucketIndex(size_t* index) const {
1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  DCHECK(!Done());
1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (index != NULL)
1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    *index = index_;
1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return true;
1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SampleVectorIterator::SkipEmptyBuckets() {
1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (Done())
1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return;
1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  while (index_ < counts_->size()) {
1595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    if (subtle::NoBarrier_Load(&(*counts_)[index_]) != 0)
1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      return;
1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    index_++;
1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}  // namespace base
166