Project import generated by Copybara.
PiperOrigin-RevId: 237361882
Change-Id: I109a68f44db867b20f8c6a7732b0ce657133e52a
diff --git a/quic/quartc/quartc_interval_counter.h b/quic/quartc/quartc_interval_counter.h
new file mode 100644
index 0000000..fe3b083
--- /dev/null
+++ b/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_
