1// Copyright 2013 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 "content/browser/download/rate_estimator.h"
6
7#include "base/logging.h"
8
9using base::TimeDelta;
10using base::TimeTicks;
11
12namespace content {
13
14namespace {
15
16static const int kDefaultBucketTimeSeconds = 1;
17static const size_t kDefaultNumBuckets = 10;
18
19} // namespace
20
21RateEstimator::RateEstimator()
22    : history_(kDefaultNumBuckets),
23      bucket_time_(TimeDelta::FromSeconds(kDefaultBucketTimeSeconds)),
24      oldest_index_(0),
25      bucket_count_(1) {
26  ResetBuckets(TimeTicks::Now());
27}
28
29RateEstimator::RateEstimator(TimeDelta bucket_time,
30                             size_t num_buckets,
31                             TimeTicks now)
32    : history_(num_buckets),
33      bucket_time_(bucket_time),
34      oldest_index_(0),
35      bucket_count_(1) {
36  DCHECK(bucket_time_.InSeconds() > 0);
37  ResetBuckets(now);
38}
39
40RateEstimator::~RateEstimator() {
41}
42
43void RateEstimator::Increment(uint32 count) {
44  Increment(count, TimeTicks::Now());
45}
46
47void RateEstimator::Increment(uint32 count, TimeTicks now) {
48  ClearOldBuckets(now);
49  int64 seconds_since_oldest = (now - oldest_time_).InSeconds();
50  DCHECK(seconds_since_oldest >= 0);
51  int64 delta_buckets = seconds_since_oldest / bucket_time_.InSeconds();
52  DCHECK(delta_buckets >= 0);
53  size_t index_offset = static_cast<size_t>(delta_buckets);
54  DCHECK(index_offset <= history_.size());
55  int current_index = (oldest_index_ + delta_buckets) % history_.size();
56  history_[current_index] += count;
57}
58
59uint64 RateEstimator::GetCountPerSecond() const {
60  return GetCountPerSecond(TimeTicks::Now());
61}
62
63uint64 RateEstimator::GetCountPerSecond(TimeTicks now) const {
64  const_cast<RateEstimator*>(this)->ClearOldBuckets(now);
65  // TODO(cbentzel): Support fractional seconds for active bucket?
66  // We explicitly don't check for overflow here. If it happens, unsigned
67  // arithmetic at least guarantees behavior by wrapping around. The estimate
68  // will be off, but the code will still be valid.
69  uint64 total_count = 0;
70  for (size_t i = 0; i < bucket_count_; ++i) {
71    size_t index = (oldest_index_ + i) % history_.size();
72    total_count += history_[index];
73  }
74  return total_count / (bucket_count_ * bucket_time_.InSeconds());
75}
76
77void RateEstimator::ClearOldBuckets(TimeTicks now) {
78  int64 seconds_since_oldest = (now - oldest_time_).InSeconds();
79
80  int64 delta_buckets = seconds_since_oldest / bucket_time_.InSeconds();
81
82  // It's possible (although unlikely) for there to be rollover with TimeTicks.
83  // If that's the case, just reset the history.
84  if (delta_buckets < 0) {
85    ResetBuckets(now);
86    return;
87  }
88  size_t delta_index = static_cast<size_t>(delta_buckets);
89
90  // If we are within the current window, keep the existing data.
91  if (delta_index < history_.size()) {
92    bucket_count_ = delta_index + 1;
93    return;
94  }
95
96  // If it's been long enough that all history data is too stale, just
97  // clear all the buckets.
98  size_t extra_buckets = delta_index - history_.size() + 1;
99  if (extra_buckets > history_.size()) {
100    ResetBuckets(now);
101    return;
102  }
103
104  // Clear out stale buckets in the history.
105  bucket_count_ = history_.size();
106  for (size_t i = 0; i < extra_buckets; ++i) {
107    history_[oldest_index_] = 0;
108    oldest_index_ = (oldest_index_ + 1) % history_.size();
109    oldest_time_ = oldest_time_ + bucket_time_;
110  }
111}
112
113void RateEstimator::ResetBuckets(TimeTicks now) {
114  for (size_t i = 0; i < history_.size(); ++i) {
115    history_[i] = 0;
116  }
117  oldest_index_ = 0;
118  bucket_count_ = 1;
119  oldest_time_ = now;
120}
121
122}  // namespace content
123