ilnik | a79cc28 | 2017-08-23 05:24:10 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (c) 2017 The WebRTC project authors. All Rights Reserved. |
| 3 | * |
| 4 | * Use of this source code is governed by a BSD-style license |
| 5 | * that can be found in the LICENSE file in the root of the source |
| 6 | * tree. An additional intellectual property rights grant can be found |
| 7 | * in the file PATENTS. All contributing project authors may |
| 8 | * be found in the AUTHORS file in the root of the source tree. |
| 9 | */ |
| 10 | |
Mirko Bonadei | 92ea95e | 2017-09-15 06:47:31 +0200 | [diff] [blame] | 11 | #ifndef RTC_BASE_MOVING_MAX_COUNTER_H_ |
| 12 | #define RTC_BASE_MOVING_MAX_COUNTER_H_ |
ilnik | a79cc28 | 2017-08-23 05:24:10 -0700 | [diff] [blame] | 13 | |
| 14 | #include <stdint.h> |
| 15 | |
| 16 | #include <deque> |
| 17 | #include <limits> |
| 18 | #include <utility> |
| 19 | |
Mirko Bonadei | 92ea95e | 2017-09-15 06:47:31 +0200 | [diff] [blame] | 20 | #include "api/optional.h" |
| 21 | #include "rtc_base/checks.h" |
| 22 | #include "rtc_base/constructormagic.h" |
ilnik | a79cc28 | 2017-08-23 05:24:10 -0700 | [diff] [blame] | 23 | |
| 24 | namespace rtc { |
| 25 | |
| 26 | // Implements moving max: can add samples to it and calculate maximum over some |
| 27 | // fixed moving window. |
| 28 | // |
| 29 | // Window size is configured at constructor. |
| 30 | // Samples can be added with |Add()| and max over current window is returned by |
| 31 | // |MovingMax|. |current_time_ms| in successive calls to Add and MovingMax |
| 32 | // should never decrease as if it's a wallclock time. |
| 33 | template <class T> |
| 34 | class MovingMaxCounter { |
| 35 | public: |
| 36 | explicit MovingMaxCounter(int64_t window_length_ms); |
| 37 | // Advances the current time, and adds a new sample. The new current time must |
| 38 | // be at least as large as the old current time. |
| 39 | void Add(const T& sample, int64_t current_time_ms); |
| 40 | // Advances the current time, and returns the maximum sample in the time |
| 41 | // window ending at the current time. The new current time must be at least as |
| 42 | // large as the old current time. |
| 43 | rtc::Optional<T> Max(int64_t current_time_ms); |
| 44 | void Reset(); |
| 45 | |
| 46 | private: |
| 47 | // Throws out obsolete samples. |
| 48 | void RollWindow(int64_t new_time_ms); |
| 49 | const int64_t window_length_ms_; |
| 50 | // This deque stores (timestamp, sample) pairs in chronological order; new |
| 51 | // pairs are only ever added at the end. However, because they can't affect |
| 52 | // the Max() calculation, pairs older than window_length_ms_ are discarded, |
| 53 | // and if an older pair has a sample that's smaller than that of a younger |
| 54 | // pair, the older pair is discarded. As a result, the sequence of timestamps |
| 55 | // is strictly increasing, and the sequence of samples is strictly decreasing. |
| 56 | std::deque<std::pair<int64_t, T>> samples_; |
| 57 | #if RTC_DCHECK_IS_ON |
| 58 | int64_t last_call_time_ms_ = std::numeric_limits<int64_t>::min(); |
| 59 | #endif |
| 60 | RTC_DISALLOW_COPY_AND_ASSIGN(MovingMaxCounter); |
| 61 | }; |
| 62 | |
| 63 | template <class T> |
| 64 | MovingMaxCounter<T>::MovingMaxCounter(int64_t window_length_ms) |
| 65 | : window_length_ms_(window_length_ms) {} |
| 66 | |
| 67 | template <class T> |
| 68 | void MovingMaxCounter<T>::Add(const T& sample, int64_t current_time_ms) { |
| 69 | RollWindow(current_time_ms); |
| 70 | // Remove samples that will never be maximum in any window: newly added sample |
| 71 | // will always be in all windows the previous samples are. Thus, smaller or |
| 72 | // equal samples could be removed. This will maintain the invariant - deque |
| 73 | // contains strictly decreasing sequence of values. |
| 74 | while (!samples_.empty() && samples_.back().second <= sample) { |
| 75 | samples_.pop_back(); |
| 76 | } |
| 77 | // Add the new sample but only if there's no existing sample at the same time. |
| 78 | // Due to checks above, the already existing element will be larger, so the |
| 79 | // new sample will never be the maximum in any window. |
| 80 | if (samples_.empty() || samples_.back().first < current_time_ms) { |
| 81 | samples_.emplace_back(std::make_pair(current_time_ms, sample)); |
| 82 | } |
| 83 | } |
| 84 | |
| 85 | template <class T> |
| 86 | rtc::Optional<T> MovingMaxCounter<T>::Max(int64_t current_time_ms) { |
| 87 | RollWindow(current_time_ms); |
| 88 | rtc::Optional<T> res; |
| 89 | if (!samples_.empty()) { |
| 90 | res.emplace(samples_.front().second); |
| 91 | } |
| 92 | return res; |
| 93 | } |
| 94 | |
| 95 | template <class T> |
| 96 | void MovingMaxCounter<T>::Reset() { |
| 97 | samples_.clear(); |
| 98 | } |
| 99 | |
| 100 | template <class T> |
| 101 | void MovingMaxCounter<T>::RollWindow(int64_t new_time_ms) { |
| 102 | #if RTC_DCHECK_IS_ON |
| 103 | RTC_DCHECK_GE(new_time_ms, last_call_time_ms_); |
| 104 | last_call_time_ms_ = new_time_ms; |
| 105 | #endif |
| 106 | const int64_t window_begin_ms = new_time_ms - window_length_ms_; |
| 107 | auto it = samples_.begin(); |
| 108 | while (it != samples_.end() && it->first < window_begin_ms) { |
| 109 | ++it; |
| 110 | } |
| 111 | samples_.erase(samples_.begin(), it); |
| 112 | } |
| 113 | |
| 114 | } // namespace rtc |
| 115 | |
Mirko Bonadei | 92ea95e | 2017-09-15 06:47:31 +0200 | [diff] [blame] | 116 | #endif // RTC_BASE_MOVING_MAX_COUNTER_H_ |