1 files changed, 122 insertions, 0 deletions
diff --git a/chromium/net/third_party/quiche/src/quic/quartc/quartc_interval_counter.h b/chromium/net/third_party/quiche/src/quic/quartc/quartc_interval_counter.h
new file mode 100644
index 00000000000..fe3b083c695
--- /dev/null
+++ b/chromium/net/third_party/quiche/src/quic/quartc/quartc_interval_counter.h
@@ -0,0 +1,122 @@
+// Copyright (c) 2018 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 QUICHE_QUIC_QUARTC_QUARTC_INTERVAL_COUNTER_H_
+#define QUICHE_QUIC_QUARTC_QUARTC_INTERVAL_COUNTER_H_
+
+#include <stddef.h>
+#include <vector>
+
+#include "net/third_party/quiche/src/quic/core/quic_interval.h"
+#include "net/third_party/quiche/src/quic/core/quic_interval_set.h"
+
+namespace quic {
+
+// QuartcIntervalCounter counts the number of times each value appears within
+// a set of potentially overlapping intervals.
+//
+// QuartcIntervalCounter is not intended for widespread use.  Consider replacing
+// it with a full interval-map if more use cases arise.
+//
+// QuartcIntervalCounter is only suitable for cases where the maximum count is
+// expected to remain low.  (For example, counting the number of times the same
+// portions of stream data are lost.)  It is inefficient when the maximum count
+// becomes high.
+template <typename T>
+class QuartcIntervalCounter {
+ public:
+  // Adds |interval| to the counter.  The count associated with each value in
+  // |interval| is incremented by one.  |interval| may overlap with previous
+  // intervals added to the counter.
+  //
+  // For each possible value:
+  //  - If the value is present in both |interval| and the counter, the count
+  //  associated with that value is incremented by one.
+  //  - If the value is present in |interval| but not counter, the count
+  //  associated with that value is set to one (incremented from zero).
+  //  - If the value is absent from |interval|, the count is unchanged.
+  //
+  // Time complexity is O(|MaxCount| * the complexity of adding an interval to a
+  // QuicIntervalSet).
+  void AddInterval(QuicInterval<T> interval);
+
+  // Removes an interval from the counter.  This method may be called to prune
+  // irrelevant intervals from the counter.  This is useful to prevent unbounded
+  // growth.
+  //
+  // Time complexity is O(|MaxCount| * the complexity of removing an interval
+  // from a QuicIntervalSet).
+  void RemoveInterval(QuicInterval<T> interval);
+
+  // Returns the maximum number of times any single value has appeared in
+  // intervals added to the counter.
+  //
+  // Time complexity is constant.
+  size_t MaxCount() const { return intervals_by_count_.size(); }
+
+  // Returns the maximum number of times a particular value has appeared in
+  // intervals added to the counter.
+  //
+  // Time complexity is O(|MaxCount| * log(number of non-contiguous intervals)).
+  size_t Count(const T& value) const;
+
+ private:
+  // Each entry in this vector represents the intervals of values counted at
+  // least i + 1 times, where i is the index of the entry.
+  //
+  // Whenever an interval is added to the counter, each value in the interval is
+  // added to the first entry which does not already contain that value.  If
+  // part of an interval is already present in the last entry, a new entry is
+  // added containing that part.
+  //
+  // Note that this means each value present in one of the interval sets will be
+  // present in all previous sets.
+  std::vector<QuicIntervalSet<T>> intervals_by_count_;
+};
+
+template <typename T>
+void QuartcIntervalCounter<T>::AddInterval(QuicInterval<T> interval) {
+  // After the Nth iteration, |leftover| contains the parts of |interval| that
+  // are already present in the first N entries.  These parts of |interval| have
+  // been added to the counter more than N times.
+  QuicIntervalSet<T> leftover(interval);
+  for (auto& intervals : intervals_by_count_) {
+    QuicIntervalSet<T> tmp = leftover;
+    leftover.Intersection(intervals);
+    intervals.Union(tmp);
+  }
+
+  // Whatever ranges are still in |leftover| are already in all the entries
+  // Add a new entry containing |leftover|.
+  if (!leftover.Empty()) {
+    intervals_by_count_.push_back(leftover);
+  }
+}
+
+template <typename T>
+void QuartcIntervalCounter<T>::RemoveInterval(QuicInterval<T> interval) {
+  // Remove the interval from each entry in the vector, popping any entries that
+  // become empty.
+  for (size_t i = intervals_by_count_.size(); i > 0; --i) {
+    intervals_by_count_[i - 1].Difference(interval);
+    if (intervals_by_count_[i - 1].Empty()) {
+      intervals_by_count_.pop_back();
+    }
+  }
+}
+
+template <typename T>
+size_t QuartcIntervalCounter<T>::Count(const T& value) const {
+  // The index of the last entry containing |value| gives its count.
+  for (size_t i = intervals_by_count_.size(); i > 0; --i) {
+    if (intervals_by_count_[i - 1].Contains(value)) {
+      return i;
+    }
+  }
+  return 0;
+}
+
+}  // namespace quic
+
+#endif  // QUICHE_QUIC_QUARTC_QUARTC_INTERVAL_COUNTER_H_