Report max interframe delay over window insdead of interframe delay sum

webrtc/rtc_base/moving_max_counter.h

+/*
+ *  Copyright (c) 2017 The WebRTC project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+#ifndef WEBRTC_RTC_BASE_MOVING_MAX_COUNTER_H_
+#define WEBRTC_RTC_BASE_MOVING_MAX_COUNTER_H_
+
+#include <stdint.h>
+
+#include <deque>
+#include <limits>
+#include <utility>
+
+#include "webrtc/rtc_base/checks.h"
+#include "webrtc/rtc_base/constructormagic.h"
+#include "webrtc/rtc_base/optional.h"
+
+namespace rtc {
+
+// Implements moving max: can add samples to it and calculate maximum over some
+// fixed moving window.
+//
+// Window size is configured at constructor.
+// Samples can be added with |Add()| and max over current window is returned by
+// |MovingMax|. |current_time_ms| in successive calls to Add and MovingMax
+// should never decrease as if it's a wallclock time.
+// Not thread-safe even if you only call const methods.
+template <class T>
+class MovingMaxCounter {
+ public:
+  explicit MovingMaxCounter(int64_t window_length_ms);
+  // Advances the current time, and adds a new sample. The new current time must
+  // be at least as large as the old current time.
+  void Add(const T& sample, int64_t current_time_ms);
+  // Advances the current time, and returns the maximum sample in the time
+  // window ending at the current time. The new current time must be at least as
+  // large as the old current time.
+  rtc::Optional<T> Max(int64_t current_time_ms) const;
+  void Reset();
+
+ private:
+  // Throws out obsolete samples. Is |const| because it is always safe to throw
+  // out old elements as long as |current_time_ms| parameters to public methods
+  // are always increasing.
+  void RollWindow(int64_t new_time_ms) const;
+  const int64_t window_length_ms_;
+  // Samples in the window are stored as pairs <time, sample> in this deque in
+  // chronological order. Samples what can't be maximum in any window are
+  // thrown out - deque always contains non-increasing sequence of samples.
+  // Is |mutable| because |MovingMax()| may be called on const instances yet it
+  // will remove obsolete samples to speed up consecutive calls.
+  mutable std::deque<std::pair<int64_t, T>> samples_;
+#if RTC_DCHECK_IS_ON
+  mutable int64_t last_call_time_ms_;
+#endif
+  RTC_DISALLOW_COPY_AND_ASSIGN(MovingMaxCounter);
+};
+
+template <class T>
+MovingMaxCounter<T>::MovingMaxCounter(int64_t window_length_ms)
+    : window_length_ms_(window_length_ms)
+#if RTC_DCHECK_IS_ON
+      , last_call_time_ms_(std::numeric_limits<int64_t>::min())
+#endif
+      {}
+
+template <class T>
+void MovingMaxCounter<T>::Add(const T& sample, int64_t current_time_ms) {
+#if RTC_DCHECK_IS_ON
+  RTC_DCHECK_GE(current_time_ms, last_call_time_ms_);
+  last_call_time_ms_ = current_time_ms;
+#endif
+  RollWindow(current_time_ms);
+  // Remove samples what will never be maximum in any window: newly added sample
+  // will always be in all windows the previous samples are. Thus, smaller
+  // samples could be removed. This will maintain the invariant - deque contains
+  // non-increasing sequence of values.
+  while (!samples_.empty() && samples_.back().second < sample) {
+    samples_.pop_back();
+  }
+  // Add the new sample but only if there's no existing sample at the same time.
+  // Due to checks above, already existing element will be larger and new sample
+  // will never be a maximum in any window.
+  if (samples_.empty() || samples_.back().first < current_time_ms) {
+    samples_.emplace_back(std::make_pair(current_time_ms, sample));
+  }
+}
+
+template <class T>
+rtc::Optional<T> MovingMaxCounter<T>::Max(int64_t current_time_ms) const {
+#if RTC_DCHECK_IS_ON
+  RTC_DCHECK_GE(current_time_ms, last_call_time_ms_);
+  last_call_time_ms_ = current_time_ms;
+#endif
+  RollWindow(current_time_ms);
+  rtc::Optional<T> res;
+  if (!samples_.empty()) {
+    res.emplace(samples_.front().second);
+  }
+  return res;
+}
+
+template <class T>
+void MovingMaxCounter<T>::Reset() {
+  samples_.clear();
+}
+
+template <class T>
+void MovingMaxCounter<T>::RollWindow(int64_t new_time_ms) const {
+  const int64_t window_begin_ms = new_time_ms - window_length_ms_;
+  auto it = samples_.begin();
+  while (it != samples_.end() && it->first < window_begin_ms) {
+    ++it;
+  }
+  samples_.erase(samples_.begin(), it);
+}
+
+}  // namespace rtc
+
+#endif  // WEBRTC_RTC_BASE_MOVING_MAX_COUNTER_H_