Support computing percentiles on a rolling window of samples

cc/scheduler/rolling_sample_window.cc

Index: cc/scheduler/rolling_sample_window.cc
diff --git a/cc/scheduler/rolling_sample_window.cc b/cc/scheduler/rolling_sample_window.cc
new file mode 100644
index 0000000000000000000000000000000000000000..fb7c1a58e7f64681e4298d063a0714b3a045469c
--- /dev/null
+++ b/cc/scheduler/rolling_sample_window.cc
@@ -0,0 +1,62 @@
+// Copyright 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <cmath>
+
+#include "cc/scheduler/rolling_sample_window.h"
+
+namespace cc {
+
+RollingSampleWindow::RollingSampleWindow(size_t max_size)
+    : max_size_(max_size) {
+}
+
+RollingSampleWindow::~RollingSampleWindow() {
+}
+
+void RollingSampleWindow::InsertSample(base::TimeDelta time) {
+  if (max_size_ == 0)
+    return;
+
+  if (sample_set_.size() == max_size_) {
+    sample_set_.erase(chronological_sample_list_.front());
+    chronological_sample_list_.pop_front();
+  }
+
+  TimeDeltaMultiset::iterator it = sample_set_.insert(time);
+  chronological_sample_list_.push_back(it);
+}
+
+void RollingSampleWindow::Clear() {
+  chronological_sample_list_.clear();
+  sample_set_.clear();
+}
+
+base::TimeDelta RollingSampleWindow::Percentile(double percent) const {
+  double fraction = percent / 100.0;
+
+  if (sample_set_.size() == 0 || fraction <= 0.0)
+    return base::TimeDelta();
+
+  if (fraction >= 1.0)
+    return *(sample_set_.rbegin());
+
+  size_t num_smaller_samples =
+      static_cast<size_t>(std::ceil(fraction * sample_set_.size())) - 1;
+
+  if (num_smaller_samples > sample_set_.size() / 2) {
+    size_t num_larger_samples = sample_set_.size() - num_smaller_samples - 1;
+    TimeDeltaMultiset::const_reverse_iterator it = sample_set_.rbegin();
+    for (size_t i = 0; i < num_larger_samples; i++)
+      it++;
+    return *it;
+  }
+
+  TimeDeltaMultiset::const_iterator it = sample_set_.begin();
+  for (size_t i = 0; i < num_smaller_samples; i++)
+    it++;
+  return *it;
+}
+
+}  // namespace cc