Split NQE to multiple files

net/nqe/observation_buffer.h

+// Copyright 2016 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.
+
+#ifndef NET_NQE_OBSERVATION_BUFFER_H_
+#define NET_NQE_OBSERVATION_BUFFER_H_
+
+#include <float.h>
+
+#include <algorithm>
+#include <deque>
+#include <vector>
+
+#include "base/gtest_prod_util.h"
+#include "base/macros.h"
+#include "base/time/time.h"
+#include "net/base/net_export.h"
+#include "net/nqe/network_quality_observation_source.h"
+#include "net/nqe/weighted_observation.h"
+
+namespace net {
+
+namespace nqe {
+
+namespace internal {
+
+// Stores observations sorted by time.
+template <typename ValueType>
+class NET_EXPORT_PRIVATE ObservationBuffer {
+ public:
+  explicit ObservationBuffer(double weight_multiplier_per_second)
+      : weight_multiplier_per_second_(weight_multiplier_per_second) {
+    static_assert(kMaximumObservationsBufferSize > 0U,
+                  "Minimum size of observation buffer must be > 0");
+    DCHECK_GE(weight_multiplier_per_second_, 0.0);
+    DCHECK_LE(weight_multiplier_per_second_, 1.0);
+  }
+
+  ~ObservationBuffer() {}
+
+  // Adds |observation| to the buffer. The oldest observation in the buffer
+  // will be evicted to make room if the buffer is already full.
+  void AddObservation(const Observation<ValueType>& observation) {
+    DCHECK_LE(observations_.size(),
+              static_cast<size_t>(kMaximumObservationsBufferSize));
+    // Evict the oldest element if the buffer is already full.
+    if (observations_.size() == kMaximumObservationsBufferSize)
+      observations_.pop_front();
+
+    observations_.push_back(observation);
+    DCHECK_LE(observations_.size(),
+              static_cast<size_t>(kMaximumObservationsBufferSize));
+  }
+
+  // Returns the number of observations in this buffer.
+  size_t Size() const { return static_cast<size_t>(observations_.size()); }
+
+  // Returns the capacity of this buffer.
+  size_t Capacity() const {
+    return static_cast<size_t>(kMaximumObservationsBufferSize);
+  }
+
+  // Clears the observations stored in this buffer.
+  void Clear() { observations_.clear(); }
+
+  // Returns true iff the |percentile| value of the observations in this
+  // buffer is available. Sets |result| to the computed |percentile|
+  // value among all observations since |begin_timestamp|. If the value is
+  // unavailable, false is returned and |result| is not modified. Percentile
+  // value is unavailable if all the values in observation buffer are older
+  // than |begin_timestamp|.
+  // |result| must not be null.
+  bool GetPercentile(const base::TimeTicks& begin_timestamp,
+                     ValueType* result,
+                     int percentile,
+                     const std::vector<NetworkQualityObservationSource>&
+                         disallowed_observation_sources) const {
+    DCHECK(result);
+    DCHECK_GE(Capacity(), Size());
+    // Stores WeightedObservation in increasing order of value.
+    std::vector<WeightedObservation<ValueType>> weighted_observations;
+
+    // Total weight of all observations in |weighted_observations|.
+    double total_weight = 0.0;
+
+    ComputeWeightedObservations(begin_timestamp, weighted_observations,
+                                &total_weight, disallowed_observation_sources);
+    if (weighted_observations.empty())
+      return false;
+
+    DCHECK(!weighted_observations.empty());
+    DCHECK_GT(total_weight, 0.0);
+
+    // |weighted_observations| may have a smaller size than observations_ since
+    // the former contains only the observations later than begin_timestamp.
+    DCHECK_GE(observations_.size(), weighted_observations.size());
+
+    double desired_weight = percentile / 100.0 * total_weight;
+
+    double cumulative_weight_seen_so_far = 0.0;
+    for (const auto& weighted_observation : weighted_observations) {
+      cumulative_weight_seen_so_far += weighted_observation.weight;
+
+      if (cumulative_weight_seen_so_far >= desired_weight) {
+        *result = weighted_observation.value;
+        return true;
+      }
+    }
+
+    // Computation may reach here due to floating point errors. This may happen
+    // if |percentile| was 100 (or close to 100), and |desired_weight| was
+    // slightly larger than |total_weight| (due to floating point errors).
+    // In this case, we return the highest |value| among all observations.
+    // This is same as value of the last observation in the sorted vector.
+    *result = weighted_observations.at(weighted_observations.size() - 1).value;
+    return true;
+  }
+
+ private:
+  // Maximum number of observations that can be held in the ObservationBuffer.
+  static const size_t kMaximumObservationsBufferSize = 300;
+
+  // Computes the weighted observations and stores them in
+  // |weighted_observations| sorted by ascending |WeightedObservation.value|.
+  // Only the observations with timestamp later than |begin_timestamp| are
+  // considered. Also, sets |total_weight| to the total weight of all
+  // observations. Should be called only when there is at least one
+  // observation in the buffer.
+  void ComputeWeightedObservations(
+      const base::TimeTicks& begin_timestamp,
+      std::vector<WeightedObservation<ValueType>>& weighted_observations,
+      double* total_weight,
+      const std::vector<NetworkQualityObservationSource>&
+          disallowed_observation_sources) const {
+    DCHECK_GE(Capacity(), Size());
+
+    weighted_observations.clear();
+    double total_weight_observations = 0.0;
+    base::TimeTicks now = base::TimeTicks::Now();
+
+    for (const auto& observation : observations_) {
+      if (observation.timestamp < begin_timestamp)
+        continue;
+      bool disallowed = false;
+      for (const auto& disallowed_source : disallowed_observation_sources) {
+        if (disallowed_source == observation.source)
+          disallowed = true;
+      }
+      if (disallowed)
+        continue;
+      base::TimeDelta time_since_sample_taken = now - observation.timestamp;
+      double weight = pow(weight_multiplier_per_second_,
+                          time_since_sample_taken.InSeconds());
+      weight = std::max(DBL_MIN, std::min(1.0, weight));
+
+      weighted_observations.push_back(
+          WeightedObservation<ValueType>(observation.value, weight));
+      total_weight_observations += weight;
+    }
+
+    // Sort the samples by value in ascending order.
+    std::sort(weighted_observations.begin(), weighted_observations.end());
+    *total_weight = total_weight_observations;
+  }
+
+  // Holds observations sorted by time, with the oldest observation at the
+  // front of the queue.
+  std::deque<Observation<ValueType>> observations_;
+
+  // The factor by which the weight of an observation reduces every second.
+  // For example, if an observation is 6 seconds old, its weight would be:
+  //     weight_multiplier_per_second_ ^ 6
+  // Calculated from |kHalfLifeSeconds| by solving the following equation:
+  //     weight_multiplier_per_second_ ^ kHalfLifeSeconds = 0.5
+  const double weight_multiplier_per_second_;
+
+  DISALLOW_COPY_AND_ASSIGN(ObservationBuffer);
+};
+
+}  // namespace internal
+
+}  // namespace nqe
+
+}  // namespace net
+
+#endif  // NET_NQE_OBSERVATION_BUFFER_H_