Implement a flag-protected version of the QuicIntervalSet performance improvements.
I tried to make it easy to review: The diff between the first two snapshots the code that simply duplicates the old code into the new code, putting the two versions of the code into two different naespaces (newquic and oldquic). Then the diff from the second snapshot to the present is all the changes to the oldcode to make it work as the newcode
(Originally this appeared as a set of changes: cl/337932377 cl/337932365 cl/337783824 cl/337932380 cl/337932384 cl/337932371 cl/337932361.)
Protected by FLAGS_quic_restart_flag_quic_startup_faster_interval_set.
PiperOrigin-RevId: 343903036
Change-Id: I9f9aaad3d8a86be0e1426e06e5dc3f6e7d2c5476
diff --git a/quic/core/quic_flags_list.h b/quic/core/quic_flags_list.h
index 127b9c0..584946a 100644
--- a/quic/core/quic_flags_list.h
+++ b/quic/core/quic_flags_list.h
@@ -85,6 +85,7 @@
QUIC_FLAG(FLAGS_quic_restart_flag_quic_enable_zero_rtt_for_tls_v2, true)
QUIC_FLAG(FLAGS_quic_restart_flag_quic_offload_pacing_to_usps2, false)
QUIC_FLAG(FLAGS_quic_restart_flag_quic_session_tickets_always_enabled, true)
+QUIC_FLAG(FLAGS_quic_restart_flag_quic_startup_faster_interval_set, false)
QUIC_FLAG(FLAGS_quic_restart_flag_quic_support_release_time_for_gso, false)
QUIC_FLAG(FLAGS_quic_restart_flag_quic_testonly_default_false, false)
QUIC_FLAG(FLAGS_quic_restart_flag_quic_testonly_default_true, true)
diff --git a/quic/core/quic_interval.h b/quic/core/quic_interval.h
index 9e87ecd..045646d 100644
--- a/quic/core/quic_interval.h
+++ b/quic/core/quic_interval.h
@@ -152,6 +152,16 @@
// *this was modified.
bool IntersectWith(const QuicInterval& i);
+ // Returns true iff this and other have disjoint closures. For nonempty
+ // intervals, that means there is at least one point between this and other.
+ // Roughly speaking that means the intervals don't intersect, and they are not
+ // adjacent. Empty intervals are always separated from any other interval.
+ bool Separated(const QuicInterval& other) const {
+ if (Empty() || other.Empty())
+ return true;
+ return other.max() < min() || max() < other.min();
+ }
+
// Calculates the smallest QuicInterval containing both *this i, and updates
// *this to represent that QuicInterval, and returns true iff *this was
// modified.
diff --git a/quic/core/quic_interval_set.h b/quic/core/quic_interval_set.h
index 7ab0647..af64e29 100644
--- a/quic/core/quic_interval_set.h
+++ b/quic/core/quic_interval_set.h
@@ -57,12 +57,17 @@
#include <utility>
#include <vector>
+#include <iterator>
#include <string>
+#include "absl/types/variant.h"
#include "net/third_party/quiche/src/quic/core/quic_interval.h"
+#include "net/third_party/quiche/src/quic/platform/api/quic_containers.h"
+#include "net/third_party/quiche/src/quic/platform/api/quic_flags.h"
#include "net/third_party/quiche/src/quic/platform/api/quic_logging.h"
namespace quic {
+namespace oldquic {
template <typename T>
class QUIC_NO_EXPORT QuicIntervalSet {
@@ -942,6 +947,1165 @@
return a.min() < b.min() || (a.min() == b.min() && a.max() > b.max());
}
+} // namespace oldquic
+
+namespace newquic {
+template <typename T>
+class QUIC_NO_EXPORT QuicIntervalSet {
+ public:
+ typedef QuicInterval<T> value_type;
+
+ private:
+ struct QUIC_NO_EXPORT IntervalLess {
+ using is_transparent = void;
+ bool operator()(const value_type& a, const value_type& b) const;
+ // These transparent overloads are used when we do all of our searches (via
+ // Set::lower_bound() and Set::upper_bound()), which avoids the need to
+ // construct an interval when we are looking for a point and also avoids
+ // needing to worry about comparing overlapping intervals in the overload
+ // that takes two value_types (the one just above this comment).
+ bool operator()(const value_type& a, const T& point) const;
+ bool operator()(const value_type& a, T&& point) const;
+ bool operator()(const T& point, const value_type& a) const;
+ bool operator()(T&& point, const value_type& a) const;
+ };
+
+ typedef QuicOrderedSet<value_type,
+ IntervalLess,
+ QuicInlinedVector<value_type, 10>>
+ Set;
+
+ public:
+ typedef typename Set::const_iterator const_iterator;
+ typedef typename Set::const_reverse_iterator const_reverse_iterator;
+
+ // Instantiates an empty QuicIntervalSet.
+ QuicIntervalSet() = default;
+
+ // Instantiates a QuicIntervalSet containing exactly one initial half-open
+ // interval [min, max), unless the given interval is empty, in which case the
+ // QuicIntervalSet will be empty.
+ explicit QuicIntervalSet(const value_type& interval) { Add(interval); }
+
+ // Instantiates a QuicIntervalSet containing the half-open interval [min,
+ // max).
+ QuicIntervalSet(const T& min, const T& max) { Add(min, max); }
+
+ QuicIntervalSet(std::initializer_list<value_type> il) { assign(il); }
+
+ // Clears this QuicIntervalSet.
+ void Clear() { intervals_.clear(); }
+
+ // Returns the number of disjoint intervals contained in this QuicIntervalSet.
+ size_t Size() const { return intervals_.size(); }
+
+ // Returns the smallest interval that contains all intervals in this
+ // QuicIntervalSet, or the empty interval if the set is empty.
+ value_type SpanningInterval() const;
+
+ // Adds "interval" to this QuicIntervalSet. Adding the empty interval has no
+ // effect.
+ void Add(const value_type& interval);
+
+ // Adds the interval [min, max) to this QuicIntervalSet. Adding the empty
+ // interval has no effect.
+ void Add(const T& min, const T& max) { Add(value_type(min, max)); }
+
+ // Same semantics as Add(const value_type&), but optimized for the case where
+ // rbegin()->min() <= |interval|.min() <= rbegin()->max().
+ void AddOptimizedForAppend(const value_type& interval) {
+ if (Empty()) {
+ Add(interval);
+ return;
+ }
+
+ const_reverse_iterator last_interval = intervals_.rbegin();
+
+ // If interval.min() is outside of [last_interval->min, last_interval->max],
+ // we can not simply extend last_interval->max.
+ if (interval.min() < last_interval->min() ||
+ interval.min() > last_interval->max()) {
+ Add(interval);
+ return;
+ }
+
+ if (interval.max() <= last_interval->max()) {
+ // interval is fully contained by last_interval.
+ return;
+ }
+
+ // Extend last_interval.max to interval.max, in place.
+ //
+ // Set does not allow in-place updates due to the potential of violating its
+ // ordering requirements. But we know setting the max of the last interval
+ // is safe w.r.t set ordering and other invariants of QuicIntervalSet, so we
+ // force an in-place update for performance.
+ const_cast<value_type*>(&(*last_interval))->SetMax(interval.max());
+ }
+
+ // Same semantics as Add(const T&, const T&), but optimized for the case where
+ // rbegin()->max() == |min|.
+ void AddOptimizedForAppend(const T& min, const T& max) {
+ AddOptimizedForAppend(value_type(min, max));
+ }
+
+ // TODO(wub): Similar to AddOptimizedForAppend, we can also have a
+ // AddOptimizedForPrepend if there is a use case.
+
+ // Remove the first interval.
+ // REQUIRES: !Empty()
+ void PopFront() {
+ DCHECK(!Empty());
+ intervals_.erase(intervals_.begin());
+ }
+
+ // Trim all values that are smaller than |value|. Which means
+ // a) If all values in an interval is smaller than |value|, the entire
+ // interval is removed.
+ // b) If some but not all values in an interval is smaller than |value|, the
+ // min of that interval is raised to |value|.
+ // Returns true if some intervals are trimmed.
+ bool TrimLessThan(const T& value) {
+ // Number of intervals that are fully or partially trimmed.
+ size_t num_intervals_trimmed = 0;
+
+ while (!intervals_.empty()) {
+ const_iterator first_interval = intervals_.begin();
+ if (first_interval->min() >= value) {
+ break;
+ }
+
+ ++num_intervals_trimmed;
+
+ if (first_interval->max() <= value) {
+ // a) Trim the entire interval.
+ intervals_.erase(first_interval);
+ continue;
+ }
+
+ // b) Trim a prefix of the interval.
+ //
+ // Set does not allow in-place updates due to the potential of violating
+ // its ordering requirements. But increasing the min of the first interval
+ // will not break the ordering, hence the const_cast.
+ const_cast<value_type*>(&(*first_interval))->SetMin(value);
+ break;
+ }
+
+ return num_intervals_trimmed != 0;
+ }
+
+ // Returns true if this QuicIntervalSet is empty.
+ bool Empty() const { return intervals_.empty(); }
+
+ // Returns true if any interval in this QuicIntervalSet contains the indicated
+ // value.
+ bool Contains(const T& value) const;
+
+ // Returns true if there is some interval in this QuicIntervalSet that wholly
+ // contains the given interval. An interval O "wholly contains" a non-empty
+ // interval I if O.Contains(p) is true for every p in I. This is the same
+ // definition used by value_type::Contains(). This method returns false on
+ // the empty interval, due to a (perhaps unintuitive) convention inherited
+ // from value_type.
+ // Example:
+ // Assume an QuicIntervalSet containing the entries { [10,20), [30,40) }.
+ // Contains(Interval(15, 16)) returns true, because [10,20) contains
+ // [15,16). However, Contains(Interval(15, 35)) returns false.
+ bool Contains(const value_type& interval) const;
+
+ // Returns true if for each interval in "other", there is some (possibly
+ // different) interval in this QuicIntervalSet which wholly contains it. See
+ // Contains(const value_type& interval) for the meaning of "wholly contains".
+ // Perhaps unintuitively, this method returns false if "other" is the empty
+ // set. The algorithmic complexity of this method is O(other.Size() *
+ // log(this->Size())). The method could be rewritten to run in O(other.Size()
+ // + this->Size()), and this alternative could be implemented as a free
+ // function using the public API.
+ bool Contains(const QuicIntervalSet<T>& other) const;
+
+ // Returns true if there is some interval in this QuicIntervalSet that wholly
+ // contains the interval [min, max). See Contains(const value_type&).
+ bool Contains(const T& min, const T& max) const {
+ return Contains(value_type(min, max));
+ }
+
+ // Returns true if for some interval in "other", there is some interval in
+ // this QuicIntervalSet that intersects with it. See value_type::Intersects()
+ // for the definition of interval intersection. Runs in time O(n+m) where n
+ // is the number of intervals in this and m is the number of intervals in
+ // other.
+ bool Intersects(const QuicIntervalSet& other) const;
+
+ // Returns an iterator to the value_type in the QuicIntervalSet that contains
+ // the given value. In other words, returns an iterator to the unique interval
+ // [min, max) in the QuicIntervalSet that has the property min <= value < max.
+ // If there is no such interval, this method returns end().
+ const_iterator Find(const T& value) const;
+
+ // Returns an iterator to the value_type in the QuicIntervalSet that wholly
+ // contains the given interval. In other words, returns an iterator to the
+ // unique interval outer in the QuicIntervalSet that has the property that
+ // outer.Contains(interval). If there is no such interval, or if interval is
+ // empty, returns end().
+ const_iterator Find(const value_type& interval) const;
+
+ // Returns an iterator to the value_type in the QuicIntervalSet that wholly
+ // contains [min, max). In other words, returns an iterator to the unique
+ // interval outer in the QuicIntervalSet that has the property that
+ // outer.Contains(Interval<T>(min, max)). If there is no such interval, or if
+ // interval is empty, returns end().
+ const_iterator Find(const T& min, const T& max) const {
+ return Find(value_type(min, max));
+ }
+
+ // Returns an iterator pointing to the first value_type which contains or
+ // goes after the given value.
+ //
+ // Example:
+ // [10, 20) [30, 40)
+ // ^ LowerBound(10)
+ // ^ LowerBound(15)
+ // ^ LowerBound(20)
+ // ^ LowerBound(25)
+ const_iterator LowerBound(const T& value) const;
+
+ // Returns an iterator pointing to the first value_type which goes after
+ // the given value.
+ //
+ // Example:
+ // [10, 20) [30, 40)
+ // ^ UpperBound(10)
+ // ^ UpperBound(15)
+ // ^ UpperBound(20)
+ // ^ UpperBound(25)
+ const_iterator UpperBound(const T& value) const;
+
+ // Returns true if every value within the passed interval is not Contained
+ // within the QuicIntervalSet.
+ // Note that empty intervals are always considered disjoint from the
+ // QuicIntervalSet (even though the QuicIntervalSet doesn't `Contain` them).
+ bool IsDisjoint(const value_type& interval) const;
+
+ // Merges all the values contained in "other" into this QuicIntervalSet.
+ //
+ // Performance: Let n == Size() and m = other.Size(). Union() runs in O(m)
+ // Set operations, so that if Set is a tree, it runs in time O(m log(n+m)) and
+ // if Set is a flat_set it runs in time O(m(n+m)). In principle, for the
+ // flat_set, we should be able to make this run in time O(n+m).
+ //
+ // TODO(bradleybear): Make Union() run in time O(n+m) for flat_set. This may
+ // require an additional template parameter to indicate that the Set is a
+ // linear-time data structure instead of a log-time data structure.
+ void Union(const QuicIntervalSet& other);
+
+ // Modifies this QuicIntervalSet so that it contains only those values that
+ // are currently present both in *this and in the QuicIntervalSet "other".
+ void Intersection(const QuicIntervalSet& other);
+
+ // Mutates this QuicIntervalSet so that it contains only those values that are
+ // currently in *this but not in "interval".
+ void Difference(const value_type& interval);
+
+ // Mutates this QuicIntervalSet so that it contains only those values that are
+ // currently in *this but not in the interval [min, max).
+ void Difference(const T& min, const T& max);
+
+ // Mutates this QuicIntervalSet so that it contains only those values that are
+ // currently in *this but not in the QuicIntervalSet "other". Runs in time
+ // O(n+m) where n is this->Size(), m is other.Size(), regardless of whether
+ // the Set is a flat_set or a std::set.
+ void Difference(const QuicIntervalSet& other);
+
+ // Mutates this QuicIntervalSet so that it contains only those values that are
+ // in [min, max) but not currently in *this.
+ void Complement(const T& min, const T& max);
+
+ // QuicIntervalSet's begin() iterator. The invariants of QuicIntervalSet
+ // guarantee that for each entry e in the set, e.min() < e.max() (because the
+ // entries are non-empty) and for each entry f that appears later in the set,
+ // e.max() < f.min() (because the entries are ordered, pairwise-disjoint, and
+ // non-adjacent). Modifications to this QuicIntervalSet invalidate these
+ // iterators.
+ const_iterator begin() const { return intervals_.begin(); }
+
+ // QuicIntervalSet's end() iterator.
+ const_iterator end() const { return intervals_.end(); }
+
+ // QuicIntervalSet's rbegin() and rend() iterators. Iterator invalidation
+ // semantics are the same as those for begin() / end().
+ const_reverse_iterator rbegin() const { return intervals_.rbegin(); }
+
+ const_reverse_iterator rend() const { return intervals_.rend(); }
+
+ template <typename Iter>
+ void assign(Iter first, Iter last) {
+ Clear();
+ for (; first != last; ++first)
+ Add(*first);
+ }
+
+ void assign(std::initializer_list<value_type> il) {
+ assign(il.begin(), il.end());
+ }
+
+ // Returns a human-readable representation of this set. This will typically be
+ // (though is not guaranteed to be) of the form
+ // "[a1, b1) [a2, b2) ... [an, bn)"
+ // where the intervals are in the same order as given by traversal from
+ // begin() to end(). This representation is intended for human consumption;
+ // computer programs should not rely on the output being in exactly this form.
+ std::string ToString() const;
+
+ QuicIntervalSet& operator=(std::initializer_list<value_type> il) {
+ assign(il.begin(), il.end());
+ return *this;
+ }
+
+ friend bool operator==(const QuicIntervalSet& a, const QuicIntervalSet& b) {
+ return a.Size() == b.Size() &&
+ std::equal(a.begin(), a.end(), b.begin(), NonemptyIntervalEq());
+ }
+
+ friend bool operator!=(const QuicIntervalSet& a, const QuicIntervalSet& b) {
+ return !(a == b);
+ }
+
+ private:
+ // Simple member-wise equality, since all intervals are non-empty.
+ struct QUIC_NO_EXPORT NonemptyIntervalEq {
+ bool operator()(const value_type& a, const value_type& b) const {
+ return a.min() == b.min() && a.max() == b.max();
+ }
+ };
+
+ // Returns true if this set is valid (i.e. all intervals in it are non-empty,
+ // non-adjacent, and mutually disjoint). Currently this is used as an
+ // integrity check by the Intersection() and Difference() methods, but is only
+ // invoked for debug builds (via DCHECK).
+ bool Valid() const;
+
+ // Finds the first interval that potentially intersects 'other'.
+ const_iterator FindIntersectionCandidate(const QuicIntervalSet& other) const;
+
+ // Finds the first interval that potentially intersects 'interval'. More
+ // precisely, return an interator it pointing at the last interval J such that
+ // interval <= J. If all the intervals are > J then return begin().
+ const_iterator FindIntersectionCandidate(const value_type& interval) const;
+
+ // Helper for Intersection() and Difference(): Finds the next pair of
+ // intervals from 'x' and 'y' that intersect. 'mine' is an iterator
+ // over x->intervals_. 'theirs' is an iterator over y.intervals_. 'mine'
+ // and 'theirs' are advanced until an intersecting pair is found.
+ // Non-intersecting intervals (aka "holes") from x->intervals_ can be
+ // optionally erased by "on_hole". "on_hole" must return an iterator to the
+ // first element in 'x' after the hole, or x->intervals_.end() if no elements
+ // exist after the hole.
+ template <typename X, typename Func>
+ static bool FindNextIntersectingPairImpl(X* x,
+ const QuicIntervalSet& y,
+ const_iterator* mine,
+ const_iterator* theirs,
+ Func on_hole);
+
+ // The variant of the above method that doesn't mutate this QuicIntervalSet.
+ bool FindNextIntersectingPair(const QuicIntervalSet& other,
+ const_iterator* mine,
+ const_iterator* theirs) const {
+ return FindNextIntersectingPairImpl(
+ this, other, mine, theirs,
+ [](const QuicIntervalSet*, const_iterator, const_iterator end) {
+ return end;
+ });
+ }
+
+ // The variant of the above method that mutates this QuicIntervalSet by
+ // erasing holes.
+ bool FindNextIntersectingPairAndEraseHoles(const QuicIntervalSet& other,
+ const_iterator* mine,
+ const_iterator* theirs) {
+ return FindNextIntersectingPairImpl(
+ this, other, mine, theirs,
+ [](QuicIntervalSet* x, const_iterator from, const_iterator to) {
+ return x->intervals_.erase(from, to);
+ });
+ }
+
+ // The representation for the intervals. The intervals in this set are
+ // non-empty, pairwise-disjoint, non-adjacent and ordered in ascending order
+ // by min().
+ Set intervals_;
+};
+
+template <typename T>
+auto operator<<(std::ostream& out, const QuicIntervalSet<T>& seq)
+ -> decltype(out << *seq.begin()) {
+ out << "{";
+ for (const auto& interval : seq) {
+ out << " " << interval;
+ }
+ out << " }";
+
+ return out;
+}
+
+//==============================================================================
+// Implementation details: Clients can stop reading here.
+
+template <typename T>
+typename QuicIntervalSet<T>::value_type QuicIntervalSet<T>::SpanningInterval()
+ const {
+ value_type result;
+ if (!intervals_.empty()) {
+ result.SetMin(intervals_.begin()->min());
+ result.SetMax(intervals_.rbegin()->max());
+ }
+ return result;
+}
+
+template <typename T>
+void QuicIntervalSet<T>::Add(const value_type& interval) {
+ if (interval.Empty())
+ return;
+ const_iterator it = intervals_.lower_bound(interval.min());
+ value_type the_union = interval;
+ if (it != intervals_.begin()) {
+ --it;
+ if (it->Separated(the_union)) {
+ ++it;
+ }
+ }
+ // Don't erase the elements one at a time, since that will produce quadratic
+ // work on a flat_set, and apparently an extra log-factor of work for a
+ // tree-based set. Instead identify the first and last intervals that need to
+ // be erased, and call erase only once.
+ const_iterator start = it;
+ while (it != intervals_.end() && !it->Separated(the_union)) {
+ the_union.SpanningUnion(*it);
+ ++it;
+ }
+ intervals_.erase(start, it);
+ intervals_.insert(the_union);
+}
+
+template <typename T>
+bool QuicIntervalSet<T>::Contains(const T& value) const {
+ // Find the first interval with min() > value, then move back one step
+ const_iterator it = intervals_.upper_bound(value);
+ if (it == intervals_.begin())
+ return false;
+ --it;
+ return it->Contains(value);
+}
+
+template <typename T>
+bool QuicIntervalSet<T>::Contains(const value_type& interval) const {
+ // Find the first interval with min() > value, then move back one step.
+ const_iterator it = intervals_.upper_bound(interval.min());
+ if (it == intervals_.begin())
+ return false;
+ --it;
+ return it->Contains(interval);
+}
+
+template <typename T>
+bool QuicIntervalSet<T>::Contains(const QuicIntervalSet<T>& other) const {
+ if (!SpanningInterval().Contains(other.SpanningInterval())) {
+ return false;
+ }
+
+ for (const_iterator i = other.begin(); i != other.end(); ++i) {
+ // If we don't contain the interval, can return false now.
+ if (!Contains(*i)) {
+ return false;
+ }
+ }
+ return true;
+}
+
+// This method finds the interval that Contains() "value", if such an interval
+// exists in the QuicIntervalSet. The way this is done is to locate the
+// "candidate interval", the only interval that could *possibly* contain value,
+// and test it using Contains(). The candidate interval is the interval with the
+// largest min() having min() <= value.
+//
+// Another detail involves the choice of which Set method to use to try to find
+// the candidate interval. The most appropriate entry point is
+// Set::upper_bound(), which finds the least interval with a min > the
+// value. The semantics of upper_bound() are slightly different from what we
+// want (namely, to find the greatest interval which is <= the probe interval)
+// but they are close enough; the interval found by upper_bound() will always be
+// one step past the interval we are looking for (if it exists) or at begin()
+// (if it does not). Getting to the proper interval is a simple matter of
+// decrementing the iterator.
+template <typename T>
+typename QuicIntervalSet<T>::const_iterator QuicIntervalSet<T>::Find(
+ const T& value) const {
+ const_iterator it = intervals_.upper_bound(value);
+ if (it == intervals_.begin())
+ return intervals_.end();
+ --it;
+ if (it->Contains(value))
+ return it;
+ else
+ return intervals_.end();
+}
+
+// This method finds the interval that Contains() the interval "probe", if such
+// an interval exists in the QuicIntervalSet. The way this is done is to locate
+// the "candidate interval", the only interval that could *possibly* contain
+// "probe", and test it using Contains(). We use the same algorithm as for
+// Find(value), except that instead of checking that the value is contained, we
+// check that the probe is contained.
+template <typename T>
+typename QuicIntervalSet<T>::const_iterator QuicIntervalSet<T>::Find(
+ const value_type& probe) const {
+ const_iterator it = intervals_.upper_bound(probe.min());
+ if (it == intervals_.begin())
+ return intervals_.end();
+ --it;
+ if (it->Contains(probe))
+ return it;
+ else
+ return intervals_.end();
+}
+
+template <typename T>
+typename QuicIntervalSet<T>::const_iterator QuicIntervalSet<T>::LowerBound(
+ const T& value) const {
+ const_iterator it = intervals_.lower_bound(value);
+ if (it == intervals_.begin()) {
+ return it;
+ }
+
+ // The previous intervals_.lower_bound() checking is essentially based on
+ // interval.min(), so we need to check whether the `value` is contained in
+ // the previous interval.
+ --it;
+ if (it->Contains(value)) {
+ return it;
+ } else {
+ return ++it;
+ }
+}
+
+template <typename T>
+typename QuicIntervalSet<T>::const_iterator QuicIntervalSet<T>::UpperBound(
+ const T& value) const {
+ return intervals_.upper_bound(value);
+}
+
+template <typename T>
+bool QuicIntervalSet<T>::IsDisjoint(const value_type& interval) const {
+ if (interval.Empty())
+ return true;
+ // Find the first interval with min() > interval.min()
+ const_iterator it = intervals_.upper_bound(interval.min());
+ if (it != intervals_.end() && interval.max() > it->min())
+ return false;
+ if (it == intervals_.begin())
+ return true;
+ --it;
+ return it->max() <= interval.min();
+}
+
+template <typename T>
+void QuicIntervalSet<T>::Union(const QuicIntervalSet& other) {
+ for (const value_type& interval : other.intervals_) {
+ Add(interval);
+ }
+}
+
+template <typename T>
+typename QuicIntervalSet<T>::const_iterator
+QuicIntervalSet<T>::FindIntersectionCandidate(
+ const QuicIntervalSet& other) const {
+ return FindIntersectionCandidate(*other.intervals_.begin());
+}
+
+template <typename T>
+typename QuicIntervalSet<T>::const_iterator
+QuicIntervalSet<T>::FindIntersectionCandidate(
+ const value_type& interval) const {
+ // Use upper_bound to efficiently find the first interval in intervals_
+ // where min() is greater than interval.min(). If the result
+ // isn't the beginning of intervals_ then move backwards one interval since
+ // the interval before it is the first candidate where max() may be
+ // greater than interval.min().
+ // In other words, no interval before that can possibly intersect with any
+ // of other.intervals_.
+ const_iterator mine = intervals_.upper_bound(interval.min());
+ if (mine != intervals_.begin()) {
+ --mine;
+ }
+ return mine;
+}
+
+template <typename T>
+template <typename X, typename Func>
+bool QuicIntervalSet<T>::FindNextIntersectingPairImpl(X* x,
+ const QuicIntervalSet& y,
+ const_iterator* mine,
+ const_iterator* theirs,
+ Func on_hole) {
+ CHECK(x != nullptr);
+ if ((*mine == x->intervals_.end()) || (*theirs == y.intervals_.end())) {
+ return false;
+ }
+ while (!(**mine).Intersects(**theirs)) {
+ const_iterator erase_first = *mine;
+ // Skip over intervals in 'mine' that don't reach 'theirs'.
+ while (*mine != x->intervals_.end() && (**mine).max() <= (**theirs).min()) {
+ ++(*mine);
+ }
+ *mine = on_hole(x, erase_first, *mine);
+ // We're done if the end of intervals_ is reached.
+ if (*mine == x->intervals_.end()) {
+ return false;
+ }
+ // Skip over intervals 'theirs' that don't reach 'mine'.
+ while (*theirs != y.intervals_.end() &&
+ (**theirs).max() <= (**mine).min()) {
+ ++(*theirs);
+ }
+ // If the end of other.intervals_ is reached, we're done.
+ if (*theirs == y.intervals_.end()) {
+ on_hole(x, *mine, x->intervals_.end());
+ return false;
+ }
+ }
+ return true;
+}
+
+template <typename T>
+void QuicIntervalSet<T>::Intersection(const QuicIntervalSet& other) {
+ if (!SpanningInterval().Intersects(other.SpanningInterval())) {
+ intervals_.clear();
+ return;
+ }
+
+ const_iterator mine = FindIntersectionCandidate(other);
+ // Remove any intervals that cannot possibly intersect with other.intervals_.
+ mine = intervals_.erase(intervals_.begin(), mine);
+ const_iterator theirs = other.FindIntersectionCandidate(*this);
+
+ while (FindNextIntersectingPairAndEraseHoles(other, &mine, &theirs)) {
+ // OK, *mine and *theirs intersect. Now, we find the largest
+ // span of intervals in other (starting at theirs) - say [a..b]
+ // - that intersect *mine, and we replace *mine with (*mine
+ // intersect x) for all x in [a..b] Note that subsequent
+ // intervals in this can't intersect any intervals in [a..b) --
+ // they may only intersect b or subsequent intervals in other.
+ value_type i(*mine);
+ intervals_.erase(mine);
+ mine = intervals_.end();
+ value_type intersection;
+ while (theirs != other.intervals_.end() &&
+ i.Intersects(*theirs, &intersection)) {
+ std::pair<const_iterator, bool> ins = intervals_.insert(intersection);
+ DCHECK(ins.second);
+ mine = ins.first;
+ ++theirs;
+ }
+ DCHECK(mine != intervals_.end());
+ --theirs;
+ ++mine;
+ }
+ DCHECK(Valid());
+}
+
+template <typename T>
+bool QuicIntervalSet<T>::Intersects(const QuicIntervalSet& other) const {
+ // Don't bother to handle nonoverlapping spanning intervals as a special case.
+ // This code runs in time O(n+m), as guaranteed, even for that case .
+ // Handling the nonoverlapping spanning intervals as a special case doesn't
+ // improve the asymptotics but does make the code more complex.
+ auto mine = intervals_.begin();
+ auto theirs = other.intervals_.begin();
+ while (mine != intervals_.end() && theirs != other.intervals_.end()) {
+ if (mine->Intersects(*theirs))
+ return true;
+ else if (*mine < *theirs)
+ ++mine;
+ else
+ ++theirs;
+ }
+ return false;
+}
+
+template <typename T>
+void QuicIntervalSet<T>::Difference(const value_type& interval) {
+ if (!SpanningInterval().Intersects(interval)) {
+ return;
+ }
+ Difference(QuicIntervalSet<T>(interval));
+}
+
+template <typename T>
+void QuicIntervalSet<T>::Difference(const T& min, const T& max) {
+ Difference(value_type(min, max));
+}
+
+template <typename T>
+void QuicIntervalSet<T>::Difference(const QuicIntervalSet& other) {
+ // In order to avoid quadratic-time when using a flat set, we don't try to
+ // update intervals_ in place. Instead we build up a new result_, always
+ // inserting at the end which is O(1) time per insertion. Since the number of
+ // elements in the result is O(Size() + other.Size()), the cost for all the
+ // insertions is also O(Size() + other.Size()).
+ //
+ // We look at all the elements of intervals_, so that's O(Size()).
+ //
+ // We also look at all the elements of other.intervals_, for O(other.Size()).
+ if (Empty())
+ return;
+ Set result;
+ const_iterator mine = intervals_.begin();
+ value_type myinterval = *mine;
+ const_iterator theirs = other.intervals_.begin();
+ while (mine != intervals_.end()) {
+ // Loop invariants:
+ // myinterval is nonempty.
+ // mine points at a range that is a suffix of myinterval.
+ DCHECK(!myinterval.Empty());
+ DCHECK(myinterval.max() == mine->max());
+
+ // There are 3 cases.
+ // myinterval is completely before theirs (treat theirs==end() as if it is
+ // infinity).
+ // --> consume myinterval into result.
+ // myinterval is completely after theirs
+ // --> theirs can no longer affect us, so ++theirs.
+ // myinterval touches theirs with a prefix of myinterval not touching
+ // *theirs.
+ // --> consume the prefix of myinterval into the result.
+ // myinterval touches theirs, with the first element of myinterval in
+ // *theirs.
+ // -> reduce myinterval
+ if (theirs == other.intervals_.end() || myinterval.max() <= theirs->min()) {
+ // Keep all of my_interval.
+ result.insert(result.end(), myinterval);
+ myinterval.Clear();
+ } else if (theirs->max() <= myinterval.min()) {
+ ++theirs;
+ } else if (myinterval.min() < theirs->min()) {
+ // Keep a nonempty prefix of my interval.
+ result.insert(result.end(), value_type(myinterval.min(), theirs->min()));
+ myinterval.SetMin(theirs->max());
+ } else {
+ // myinterval starts at or after *theirs, chop down myinterval.
+ myinterval.SetMin(theirs->max());
+ }
+ // if myinterval became empty, find the next interval
+ if (myinterval.Empty()) {
+ ++mine;
+ if (mine != intervals_.end()) {
+ myinterval = *mine;
+ }
+ }
+ }
+ std::swap(result, intervals_);
+ DCHECK(Valid());
+}
+
+template <typename T>
+void QuicIntervalSet<T>::Complement(const T& min, const T& max) {
+ QuicIntervalSet<T> span(min, max);
+ span.Difference(*this);
+ intervals_.swap(span.intervals_);
+}
+
+template <typename T>
+std::string QuicIntervalSet<T>::ToString() const {
+ std::ostringstream os;
+ os << *this;
+ return os.str();
+}
+
+template <typename T>
+bool QuicIntervalSet<T>::Valid() const {
+ const_iterator prev = end();
+ for (const_iterator it = begin(); it != end(); ++it) {
+ // invalid or empty interval.
+ if (it->min() >= it->max())
+ return false;
+ // Not sorted, not disjoint, or adjacent.
+ if (prev != end() && prev->max() >= it->min())
+ return false;
+ prev = it;
+ }
+ return true;
+}
+
+// This comparator orders intervals first by ascending min(). The Set never
+// contains overlapping intervals, so that suffices.
+template <typename T>
+bool QuicIntervalSet<T>::IntervalLess::operator()(const value_type& a,
+ const value_type& b) const {
+ // This overload is probably used only by Set::insert().
+ return a.min() < b.min();
+}
+
+// It appears that the Set::lower_bound(T) method uses only two overloads of the
+// comparison operator that take a T as the second argument.. In contrast
+// Set::upper_bound(T) uses the two overloads that take T as the first argument.
+template <typename T>
+bool QuicIntervalSet<T>::IntervalLess::operator()(const value_type& a,
+ const T& point) const {
+ // Compare an interval to a point.
+ return a.min() < point;
+}
+
+template <typename T>
+bool QuicIntervalSet<T>::IntervalLess::operator()(const value_type& a,
+ T&& point) const {
+ // Compare an interval to a point
+ return a.min() < point;
+}
+
+// It appears that the Set::upper_bound(T) method uses only the next two
+// overloads of the comparison operator.
+template <typename T>
+bool QuicIntervalSet<T>::IntervalLess::operator()(const T& point,
+ const value_type& a) const {
+ // Compare an interval to a point.
+ return point < a.min();
+}
+
+template <typename T>
+bool QuicIntervalSet<T>::IntervalLess::operator()(T&& point,
+ const value_type& a) const {
+ // Compare an interval to a point.
+ return point < a.min();
+}
+
+} // namespace newquic
+
+// TODO(bradleybear): Get rid of this when we get rid of
+// quic_startup_faster_interval_set_flag.
+class QUIC_NO_EXPORT QuicIntervalSetParameterSetter {
+ private:
+ // friend the tests so that we can SetUseFasterIntervalSet in the tests.
+ template <typename T>
+ friend class QuicIntervalSet;
+ friend void Quic_Test_Set_Fast(bool fast);
+ static bool* UseFasterIntervalSetAddress() {
+ static bool result = GetQuicRestartFlag(quic_startup_faster_interval_set);
+ return &result;
+ }
+ static void SetUseFasterIntervalSet(bool use) {
+ *UseFasterIntervalSetAddress() = use;
+ }
+ static bool UseFasterIntervalSet() { return *UseFasterIntervalSetAddress(); }
+};
+
+template <typename T>
+class QUIC_NO_EXPORT QuicIntervalSet {
+ template <class old_iterator, class new_iterator>
+ class InternalIterator;
+ using OldSet = oldquic::QuicIntervalSet<T>;
+ using NewSet = newquic::QuicIntervalSet<T>;
+ using QISet = absl::variant<OldSet, NewSet>;
+
+ public:
+ typedef QuicInterval<T> value_type;
+ using const_iterator = InternalIterator<typename OldSet::const_iterator,
+ typename NewSet::const_iterator>;
+ using const_reverse_iterator =
+ InternalIterator<typename OldSet::const_reverse_iterator,
+ typename NewSet::const_reverse_iterator>;
+
+ QuicIntervalSet()
+ : qiset_(QuicIntervalSetParameterSetter::UseFasterIntervalSet()
+ ? QISet(NewSet())
+ : QISet(OldSet())) {}
+
+ explicit QuicIntervalSet(const value_type& interval)
+ : qiset_(QuicIntervalSetParameterSetter::UseFasterIntervalSet()
+ ? QISet(NewSet(interval))
+ : QISet(OldSet(interval))) {}
+
+ QuicIntervalSet(const T& min, const T& max)
+ : qiset_(QuicIntervalSetParameterSetter::UseFasterIntervalSet()
+ ? QISet(NewSet(min, max))
+ : QISet(OldSet(min, max))) {}
+
+ QuicIntervalSet(std::initializer_list<value_type> il)
+ : qiset_(QuicIntervalSetParameterSetter::UseFasterIntervalSet()
+ ? QISet(NewSet(il))
+ : QISet(OldSet(il))) {}
+
+ void Clear() {
+ return absl::visit([](auto& s) { s.Clear(); }, qiset_);
+ }
+ size_t Size() const {
+ return absl::visit([](const auto& s) { return s.Size(); }, qiset_);
+ }
+ value_type SpanningInterval() const {
+ return absl::visit([](auto& s) { return s.SpanningInterval(); }, qiset_);
+ }
+ void Add(const value_type& interval) {
+ return absl::visit([&](auto& s) { return s.Add(interval); }, qiset_);
+ }
+ void Add(const T& min, const T& max) {
+ return absl::visit([&](auto& s) { return s.Add(min, max); }, qiset_);
+ }
+ void AddOptimizedForAppend(const value_type& interval) {
+ return absl::visit(
+ [&](auto& s) { return s.AddOptimizedForAppend(interval); }, qiset_);
+ }
+ void AddOptimizedForAppend(const T& min, const T& max) {
+ return absl::visit(
+ [&](auto& s) { return s.AddOptimizedForAppend(min, max); }, qiset_);
+ }
+ void PopFront() {
+ return absl::visit([](auto& s) { return s.PopFront(); }, qiset_);
+ }
+ bool Empty() const {
+ return absl::visit([](auto& s) { return s.Empty(); }, qiset_);
+ }
+ bool Contains(const T& value) const {
+ return absl::visit([&](auto& s) { return s.Contains(value); }, qiset_);
+ }
+ bool Contains(const value_type& interval) const {
+ return absl::visit([&](auto& s) { return s.Contains(interval); }, qiset_);
+ }
+ bool Contains(const T& min, const T& max) const {
+ return absl::visit([&](auto& s) { return s.Contains(min, max); }, qiset_);
+ }
+
+ private:
+ template <class A, class B, class C>
+ struct overloader : A, B, C {
+ overloader(A a, B b, C c) : A(a), B(b), C(c) {}
+ using A::operator();
+ using B::operator();
+ using C::operator();
+ };
+ template <class A, class B, class C>
+ static auto make_visitor(A a, B b, C c) {
+ return overloader<A, B, C>(a, b, c);
+ }
+
+ public:
+ bool Contains(const QuicIntervalSet<T>& other) const {
+ return absl::visit(
+ make_visitor(
+ // Sadly C++11's templated lambda system isn't quite powerful enough
+ // to specify that the two auto&& arguments are the same, so we have
+ // to specify two functions.
+ [](const OldSet& a, const OldSet& b) { return a.Contains(b); },
+ [](const NewSet& a, const NewSet& b) { return a.Contains(b); },
+ // If the types mismatch then return false. This shouldn't happen
+ // in production since we capture the
+ // quic_startup_faster_interval_set flag very early. But tests can
+ // make it happen.
+ []([[maybe_unused]] auto&& a, [[maybe_unused]] auto&& b) {
+ return false;
+ }),
+ qiset_, other.qiset_);
+ }
+ bool Intersects(const QuicIntervalSet& other) const {
+ return absl::visit(
+ make_visitor(
+ [](const OldSet& a, const OldSet& b) { return a.Intersects(b); },
+ [](const NewSet& a, const NewSet& b) { return a.Intersects(b); },
+ []([[maybe_unused]] auto&& a, [[maybe_unused]] auto&& b) {
+ return false;
+ }),
+ qiset_, other.qiset_);
+ }
+ const_iterator Find(const T& value) const {
+ return absl::visit([&](auto& s) { return const_iterator(s.Find(value)); },
+ qiset_);
+ }
+ const_iterator Find(const T& min, const T& max) const {
+ return absl::visit(
+ [&](auto& s) { return const_iterator(s.Find(min, max)); }, qiset_);
+ }
+ const_iterator LowerBound(const T& value) const {
+ return absl::visit(
+ [&](auto& s) { return const_iterator(s.LowerBound(value)); }, qiset_);
+ }
+ const_iterator UpperBound(const T& value) const {
+ return absl::visit(
+ [&](auto& s) { return const_iterator(s.UpperBound(value)); }, qiset_);
+ }
+ bool IsDisjoint(const value_type& interval) const {
+ return absl::visit([&](auto& s) { return s.IsDisjoint(interval); }, qiset_);
+ }
+ void Union(const QuicIntervalSet& other) {
+ return absl::visit(
+ make_visitor([](OldSet& a, const OldSet& b) { return a.Union(b); },
+ [](NewSet& a, const NewSet& b) { return a.Union(b); },
+ []([[maybe_unused]] auto&& a, [[maybe_unused]] auto&& b) {
+ return void();
+ }),
+ qiset_, other.qiset_);
+ }
+ void Intersection(const QuicIntervalSet& other) {
+ return absl::visit(
+ make_visitor(
+ [](OldSet& a, const OldSet& b) { return a.Intersection(b); },
+ [](NewSet& a, const NewSet& b) { return a.Intersection(b); },
+ []([[maybe_unused]] auto&& a, [[maybe_unused]] auto&& b) {
+ return void();
+ }),
+ qiset_, other.qiset_);
+ }
+ void Difference(const value_type& interval) {
+ return absl::visit([&](auto& s) { return s.Difference(interval); }, qiset_);
+ }
+ void Difference(const T& min, const T& max) {
+ return absl::visit([&](auto& s) { return s.Difference(min, max); }, qiset_);
+ }
+ void Difference(const QuicIntervalSet& other) {
+ return absl::visit(
+ make_visitor([](OldSet& a, const OldSet& b) { return a.Difference(b); },
+ [](NewSet& a, const NewSet& b) { return a.Difference(b); },
+ []([[maybe_unused]] auto&& a, [[maybe_unused]] auto&& b) {
+ return void();
+ }),
+ qiset_, other.qiset_);
+ }
+
+ void Complement(const T& min, const T& max) {
+ return absl::visit([&](auto& s) { return s.Complement(min, max); }, qiset_);
+ }
+ bool TrimLessThan(const T& value) {
+ return absl::visit([&](auto& s) { return s.TrimLessThan(value); }, qiset_);
+ }
+ const_iterator begin() const {
+ return absl::visit([](auto& s) { return const_iterator(s.begin()); },
+ qiset_);
+ }
+ const_iterator end() const {
+ return absl::visit([](auto& s) { return const_iterator(s.end()); }, qiset_);
+ }
+ const_reverse_iterator rbegin() const {
+ return absl::visit(
+ [](auto& s) { return const_reverse_iterator(s.rbegin()); }, qiset_);
+ }
+ const_reverse_iterator rend() const {
+ return absl::visit([](auto& s) { return const_reverse_iterator(s.rend()); },
+ qiset_);
+ }
+ template <typename Iter>
+ void assign(Iter first, Iter last) {
+ return absl::visit([&](auto& s) { return s.assign(first, last); }, qiset_);
+ }
+ void assign(std::initializer_list<value_type> il) {
+ return absl::visit([&](auto& s) { return s.assign(il); }, qiset_);
+ }
+ std::string ToString() const {
+ return absl::visit([](auto& s) { return s.ToString(); }, qiset_);
+ }
+ friend bool operator==(const QuicIntervalSet& a, const QuicIntervalSet& b) {
+ return absl::visit(
+ make_visitor([](const OldSet& a, const OldSet& b) { return a == b; },
+ [](const NewSet& a, const NewSet& b) { return a == b; },
+ []([[maybe_unused]] auto&& a, [[maybe_unused]] auto&& b) {
+ return false;
+ }),
+ a.qiset_, b.qiset_);
+ }
+ friend bool operator!=(const QuicIntervalSet& a, const QuicIntervalSet& b) {
+ return absl::visit(
+ make_visitor([](const OldSet& a, const OldSet& b) { return a != b; },
+ [](const NewSet& a, const NewSet& b) { return a != b; },
+ []([[maybe_unused]] auto&& a, [[maybe_unused]] auto&& b) {
+ return true;
+ }),
+ a.qiset_, b.qiset_);
+ }
+
+ private:
+ template <class old_iterator, class new_iterator>
+ // This same idea appeared in cl/338686797 as IteratorWrapper. Perhaps we
+ // should implement it once and for all.
+ class InternalIterator
+ : public std::iterator<std::forward_iterator_tag, // iterator category
+ QuicIntervalSet::value_type, // value_type
+ ptrdiff_t, // difference_type
+ const value_type*, // pointer
+ const value_type& // reference
+ > {
+ public:
+ const value_type* operator->() const {
+ return absl::visit([](auto& it) { return &*it; }, it_);
+ }
+ const value_type& operator*() const {
+ // Must return &*it (rather than just returning *it) since, for some
+ // iterators (especially const_iterators) return a value_type instead of a
+ // value_type&. The standard says that it must return a "reference,
+ // convertible to T" but doesn't actually say that the "reference" must be
+ // a reference type. The standard isn't very clear, but the simpler code
+ // doesn't work.
+ return *absl::visit([](auto& it) { return &*it; }, it_);
+ }
+ InternalIterator& operator++() {
+ absl::visit([](auto& it) { ++it; }, it_);
+ return *this;
+ }
+ InternalIterator& operator--() {
+ absl::visit([](auto& it) { --it; }, it_);
+ return *this;
+ }
+
+ private:
+ friend QuicIntervalSet;
+ // The following doesn't work for some compiler combinations:
+ // explicit InternalIterator(old_iterator it) : it_(std::move(it)) {}
+ // explicit InternalIterator(new_iterator it) : it_(std::move(it)) {}
+ // So we are using emplace instead.
+ explicit InternalIterator(old_iterator it) {
+ it_.template emplace<0>(std::move(it));
+ }
+ explicit InternalIterator(new_iterator it) {
+ it_.template emplace<1>(std::move(it));
+ }
+ friend bool operator==(const InternalIterator& a,
+ const InternalIterator& b) {
+ return absl::visit(
+ make_visitor([](const old_iterator& a,
+ const old_iterator& b) { return a == b; },
+ [](const new_iterator& a, const new_iterator& b) {
+ return a == b;
+ },
+ []([[maybe_unused]] auto&& a,
+ [[maybe_unused]] auto&& b) { return false; }),
+ a.it_, b.it_);
+ }
+ friend bool operator!=(const InternalIterator& a,
+ const InternalIterator& b) {
+ return absl::visit(
+ make_visitor([](const old_iterator& a,
+ const old_iterator& b) { return a != b; },
+ [](const new_iterator& a, const new_iterator& b) {
+ return a != b;
+ },
+ []([[maybe_unused]] auto&& a,
+ [[maybe_unused]] auto&& b) { return true; }),
+ a.it_, b.it_);
+ }
+ absl::variant<old_iterator, new_iterator> it_;
+ };
+
+ QISet qiset_;
+};
+
+template <typename T>
+auto operator<<(std::ostream& out, const QuicIntervalSet<T>& seq)
+ -> decltype(out << *seq.begin()) {
+ out << "{";
+ for (const auto& interval : seq) {
+ out << " " << interval;
+ }
+ out << " }";
+
+ return out;
+}
+
} // namespace quic
#endif // QUICHE_QUIC_CORE_QUIC_INTERVAL_SET_H_
diff --git a/quic/core/quic_interval_set_test.cc b/quic/core/quic_interval_set_test.cc
index 30d08b8..3df079c 100644
--- a/quic/core/quic_interval_set_test.cc
+++ b/quic/core/quic_interval_set_test.cc
@@ -16,14 +16,29 @@
#include "net/third_party/quiche/src/quic/platform/api/quic_test.h"
namespace quic {
+
+// Fully instantiate a QuicIntervalSet to check for compile-time errors on the
+// templated code.
+template class QuicIntervalSet<int>;
+
+void Quic_Test_Set_Fast(bool fast) {
+ QuicIntervalSetParameterSetter::SetUseFasterIntervalSet(fast);
+}
+
namespace test {
-namespace {
using ::testing::ElementsAreArray;
-class QuicIntervalSetTest : public QuicTest {
+class QuicIntervalSetTest :
+ // The parameter is whether to for FLAGS_quic_startup_faster_interval_set.
+ public QuicTestWithParam<bool> {
protected:
virtual void SetUp() {
+ Quic_Test_Set_Fast(GetParam());
+ // Must make new sets, since the representation depends on the flag.
+ is = QuicIntervalSet<int>();
+ other = QuicIntervalSet<int>();
+
// Initialize two QuicIntervalSets for union, intersection, and difference
// tests
is.Add(100, 200);
@@ -60,8 +75,11 @@
QuicIntervalSet<int> is;
QuicIntervalSet<int> other;
};
+INSTANTIATE_TEST_SUITE_P(QuicIntervalSetTest,
+ QuicIntervalSetTest,
+ ::testing::Bool());
-TEST_F(QuicIntervalSetTest, IsDisjoint) {
+TEST_P(QuicIntervalSetTest, IsDisjoint) {
EXPECT_TRUE(is.IsDisjoint(QuicInterval<int>(0, 99)));
EXPECT_TRUE(is.IsDisjoint(QuicInterval<int>(0, 100)));
EXPECT_TRUE(is.IsDisjoint(QuicInterval<int>(200, 200)));
@@ -162,7 +180,22 @@
<< "and max " << max;
}
-TEST_F(QuicIntervalSetTest, AddOptimizedForAppend) {
+TEST_P(QuicIntervalSetTest, AddInterval) {
+ QuicIntervalSet<int> s;
+ s.Add(QuicInterval<int>(0, 10));
+ EXPECT_TRUE(Check(s, 1, 0, 10));
+}
+
+TEST_P(QuicIntervalSetTest, DecrementIterator) {
+ auto it = is.end();
+ EXPECT_NE(it, is.begin());
+ --it;
+ EXPECT_EQ(*it, QuicInterval<int>(2100, 2200));
+ ++it;
+ EXPECT_EQ(it, is.end());
+}
+
+TEST_P(QuicIntervalSetTest, AddOptimizedForAppend) {
QuicIntervalSet<int> empty_one, empty_two;
empty_one.AddOptimizedForAppend(QuicInterval<int>(0, 99));
EXPECT_TRUE(Check(empty_one, 1, 0, 99));
@@ -191,7 +224,7 @@
EXPECT_TRUE(Check(iset, 3, 100, 150, 199, 250, 251, 350));
}
-TEST_F(QuicIntervalSetTest, PopFront) {
+TEST_P(QuicIntervalSetTest, PopFront) {
QuicIntervalSet<int> iset{{100, 200}, {400, 500}, {700, 800}};
EXPECT_TRUE(Check(iset, 3, 100, 200, 400, 500, 700, 800));
@@ -205,7 +238,7 @@
EXPECT_TRUE(iset.Empty());
}
-TEST_F(QuicIntervalSetTest, TrimLessThan) {
+TEST_P(QuicIntervalSetTest, TrimLessThan) {
QuicIntervalSet<int> iset{{100, 200}, {400, 500}, {700, 800}};
EXPECT_TRUE(Check(iset, 3, 100, 200, 400, 500, 700, 800));
@@ -232,7 +265,7 @@
EXPECT_TRUE(iset.Empty());
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetBasic) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetBasic) {
// Test Add, Get, Contains and Find
QuicIntervalSet<int> iset;
EXPECT_TRUE(iset.Empty());
@@ -350,9 +383,14 @@
EXPECT_FALSE(iset.Contains(iset_contains));
EXPECT_FALSE(iset.Contains(QuicInterval<int>()));
EXPECT_FALSE(iset.Contains(QuicIntervalSet<int>()));
+
+ // Check the case where the query set isn't contained, but the spanning
+ // intervals do overlap.
+ QuicIntervalSet<int> i2({{220, 230}});
+ EXPECT_FALSE(iset.Contains(i2));
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetContainsEmpty) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetContainsEmpty) {
const QuicIntervalSet<int> empty;
const QuicIntervalSet<int> other_empty;
const QuicIntervalSet<int> non_empty({{10, 20}, {40, 50}});
@@ -362,7 +400,7 @@
EXPECT_FALSE(non_empty.Contains(empty));
}
-TEST_F(QuicIntervalSetTest, Equality) {
+TEST_P(QuicIntervalSetTest, Equality) {
QuicIntervalSet<int> is_copy = is;
EXPECT_EQ(is, is);
EXPECT_EQ(is, is_copy);
@@ -371,7 +409,7 @@
EXPECT_EQ(QuicIntervalSet<int>(), QuicIntervalSet<int>());
}
-TEST_F(QuicIntervalSetTest, LowerAndUpperBound) {
+TEST_P(QuicIntervalSetTest, LowerAndUpperBound) {
QuicIntervalSet<int> intervals;
intervals.Add(10, 20);
intervals.Add(30, 40);
@@ -417,7 +455,7 @@
EXPECT_EQ(intervals.UpperBound(50), intervals.end());
}
-TEST_F(QuicIntervalSetTest, SpanningInterval) {
+TEST_P(QuicIntervalSetTest, SpanningInterval) {
// Spanning interval of an empty set is empty:
{
QuicIntervalSet<int> iset;
@@ -448,14 +486,14 @@
}
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetUnion) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetUnion) {
is.Union(other);
EXPECT_TRUE(Check(is, 12, 50, 70, 100, 200, 300, 400, 470, 600, 650, 670, 700,
830, 870, 1000, 1100, 1230, 1270, 1830, 1900, 2000, 2100,
2200, 2250, 2270));
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersection) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersection) {
EXPECT_TRUE(is.Intersects(other));
EXPECT_TRUE(other.Intersects(is));
is.Intersection(other);
@@ -465,7 +503,7 @@
EXPECT_TRUE(other.Intersects(is));
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionBothEmpty) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionBothEmpty) {
QuicIntervalSet<std::string> mine, theirs;
EXPECT_FALSE(mine.Intersects(theirs));
EXPECT_FALSE(theirs.Intersects(mine));
@@ -475,7 +513,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionEmptyMine) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionEmptyMine) {
QuicIntervalSet<std::string> mine;
QuicIntervalSet<std::string> theirs("a", "b");
EXPECT_FALSE(mine.Intersects(theirs));
@@ -486,7 +524,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionEmptyTheirs) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionEmptyTheirs) {
QuicIntervalSet<std::string> mine("a", "b");
QuicIntervalSet<std::string> theirs;
EXPECT_FALSE(mine.Intersects(theirs));
@@ -497,7 +535,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionTheirsBeforeMine) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionTheirsBeforeMine) {
QuicIntervalSet<std::string> mine("y", "z");
QuicIntervalSet<std::string> theirs;
theirs.Add("a", "b");
@@ -510,7 +548,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionMineBeforeTheirs) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionMineBeforeTheirs) {
QuicIntervalSet<std::string> mine;
mine.Add("a", "b");
mine.Add("c", "d");
@@ -523,7 +561,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_F(QuicIntervalSetTest,
+TEST_P(QuicIntervalSetTest,
QuicIntervalSetIntersectionTheirsBeforeMineInt64Singletons) {
QuicIntervalSet<int64_t> mine({{10, 15}});
QuicIntervalSet<int64_t> theirs({{-20, -5}});
@@ -535,7 +573,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_F(QuicIntervalSetTest,
+TEST_P(QuicIntervalSetTest,
QuicIntervalSetIntersectionMineBeforeTheirsIntSingletons) {
QuicIntervalSet<int> mine({{10, 15}});
QuicIntervalSet<int> theirs({{90, 95}});
@@ -547,7 +585,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionTheirsBetweenMine) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionTheirsBetweenMine) {
QuicIntervalSet<int64_t> mine({{0, 5}, {40, 50}});
QuicIntervalSet<int64_t> theirs({{10, 15}});
EXPECT_FALSE(mine.Intersects(theirs));
@@ -558,7 +596,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionMineBetweenTheirs) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionMineBetweenTheirs) {
QuicIntervalSet<int> mine({{20, 25}});
QuicIntervalSet<int> theirs({{10, 15}, {30, 32}});
EXPECT_FALSE(mine.Intersects(theirs));
@@ -569,7 +607,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionAlternatingIntervals) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionAlternatingIntervals) {
QuicIntervalSet<int> mine, theirs;
mine.Add(10, 20);
mine.Add(40, 50);
@@ -585,7 +623,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_F(QuicIntervalSetTest,
+TEST_P(QuicIntervalSetTest,
QuicIntervalSetIntersectionAdjacentAlternatingNonIntersectingIntervals) {
// Make sure that intersection with adjacent interval set is empty.
const QuicIntervalSet<int> x1({{0, 10}});
@@ -611,7 +649,7 @@
EXPECT_TRUE(result3.Empty()) << result3;
}
-TEST_F(QuicIntervalSetTest,
+TEST_P(QuicIntervalSetTest,
QuicIntervalSetIntersectionAlternatingIntersectingIntervals) {
const QuicIntervalSet<int> x1({{0, 10}});
const QuicIntervalSet<int> y1({{-50, 1}, {9, 95}});
@@ -640,7 +678,7 @@
EXPECT_EQ(result3, expected_result3);
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionIdentical) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionIdentical) {
QuicIntervalSet<int> copy(is);
EXPECT_TRUE(copy.Intersects(is));
EXPECT_TRUE(is.Intersects(copy));
@@ -648,7 +686,7 @@
EXPECT_EQ(copy, is);
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionSuperset) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionSuperset) {
QuicIntervalSet<int> mine(-1, 10000);
EXPECT_TRUE(mine.Intersects(is));
EXPECT_TRUE(is.Intersects(mine));
@@ -656,7 +694,7 @@
EXPECT_EQ(is, mine);
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionSubset) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionSubset) {
QuicIntervalSet<int> copy(is);
QuicIntervalSet<int> theirs(-1, 10000);
EXPECT_TRUE(copy.Intersects(theirs));
@@ -665,7 +703,7 @@
EXPECT_EQ(copy, is);
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionLargeSet) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionLargeSet) {
QuicIntervalSet<int> mine, theirs;
// mine: [0, 9), [10, 19), ..., [990, 999)
for (int i = 0; i < 1000; i += 10) {
@@ -683,7 +721,7 @@
EXPECT_TRUE(theirs.Intersects(mine));
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetDifference) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetDifference) {
is.Difference(other);
EXPECT_TRUE(Check(is, 10, 100, 200, 300, 350, 360, 370, 380, 400, 530, 600,
700, 770, 900, 1000, 1100, 1200, 1900, 2000, 2100, 2200));
@@ -692,7 +730,7 @@
EXPECT_TRUE(is.Empty());
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceSingleBounds) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetDifferenceSingleBounds) {
std::vector<QuicInterval<int>> ivals(other.begin(), other.end());
for (const QuicInterval<int>& ival : ivals) {
is.Difference(ival.min(), ival.max());
@@ -701,7 +739,7 @@
700, 770, 900, 1000, 1100, 1200, 1900, 2000, 2100, 2200));
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceSingleInterval) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetDifferenceSingleInterval) {
std::vector<QuicInterval<int>> ivals(other.begin(), other.end());
for (const QuicInterval<int>& ival : ivals) {
is.Difference(ival);
@@ -710,7 +748,7 @@
700, 770, 900, 1000, 1100, 1200, 1900, 2000, 2100, 2200));
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceAlternatingIntervals) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetDifferenceAlternatingIntervals) {
QuicIntervalSet<int> mine, theirs;
mine.Add(10, 20);
mine.Add(40, 50);
@@ -723,7 +761,7 @@
EXPECT_TRUE(Check(mine, 3, 10, 20, 40, 50, 60, 70));
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceEmptyMine) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetDifferenceEmptyMine) {
QuicIntervalSet<std::string> mine, theirs;
theirs.Add("a", "b");
@@ -731,7 +769,7 @@
EXPECT_TRUE(mine.Empty());
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceEmptyTheirs) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetDifferenceEmptyTheirs) {
QuicIntervalSet<std::string> mine, theirs;
mine.Add("a", "b");
@@ -741,7 +779,7 @@
EXPECT_EQ("b", mine.begin()->max());
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceTheirsBeforeMine) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetDifferenceTheirsBeforeMine) {
QuicIntervalSet<std::string> mine, theirs;
mine.Add("y", "z");
theirs.Add("a", "b");
@@ -752,7 +790,7 @@
EXPECT_EQ("z", mine.begin()->max());
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceMineBeforeTheirs) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetDifferenceMineBeforeTheirs) {
QuicIntervalSet<std::string> mine, theirs;
mine.Add("a", "b");
theirs.Add("y", "z");
@@ -763,7 +801,7 @@
EXPECT_EQ("b", mine.begin()->max());
}
-TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceIdentical) {
+TEST_P(QuicIntervalSetTest, QuicIntervalSetDifferenceIdentical) {
QuicIntervalSet<std::string> mine;
mine.Add("a", "b");
mine.Add("c", "d");
@@ -773,7 +811,7 @@
EXPECT_TRUE(mine.Empty());
}
-TEST_F(QuicIntervalSetTest, EmptyComplement) {
+TEST_P(QuicIntervalSetTest, EmptyComplement) {
// The complement of an empty set is the input interval:
QuicIntervalSet<int> iset;
iset.Complement(100, 200);
@@ -853,7 +891,7 @@
return result;
}
-TEST_F(QuicIntervalSetTest, SingleIntervalComplement) {
+TEST_P(QuicIntervalSetTest, SingleIntervalComplement) {
// Verify the complement of a set with one interval (i):
// |----- i -----|
// |----- args -----|
@@ -903,7 +941,7 @@
return result;
}
-TEST_F(QuicIntervalSetTest, MultiIntervalComplement) {
+TEST_P(QuicIntervalSetTest, MultiIntervalComplement) {
// Initialize a small test set:
QuicIntervalSet<int> iset;
iset.Add(100, 200);
@@ -946,7 +984,7 @@
}
// Verifies ToString, operator<< don't assert.
-TEST_F(QuicIntervalSetTest, ToString) {
+TEST_P(QuicIntervalSetTest, ToString) {
QuicIntervalSet<int> iset;
iset.Add(300, 400);
iset.Add(100, 200);
@@ -959,14 +997,14 @@
EXPECT_EQ("{ }", QuicIntervalSet<int>().ToString());
}
-TEST_F(QuicIntervalSetTest, ConstructionDiscardsEmptyInterval) {
+TEST_P(QuicIntervalSetTest, ConstructionDiscardsEmptyInterval) {
EXPECT_TRUE(QuicIntervalSet<int>(QuicInterval<int>(2, 2)).Empty());
EXPECT_TRUE(QuicIntervalSet<int>(2, 2).Empty());
EXPECT_FALSE(QuicIntervalSet<int>(QuicInterval<int>(2, 3)).Empty());
EXPECT_FALSE(QuicIntervalSet<int>(2, 3).Empty());
}
-TEST_F(QuicIntervalSetTest, Swap) {
+TEST_P(QuicIntervalSetTest, Swap) {
QuicIntervalSet<int> a, b;
a.Add(300, 400);
b.Add(100, 200);
@@ -979,7 +1017,7 @@
EXPECT_TRUE(Check(b, 2, 100, 200, 500, 600));
}
-TEST_F(QuicIntervalSetTest, OutputReturnsOstreamRef) {
+TEST_P(QuicIntervalSetTest, OutputReturnsOstreamRef) {
std::stringstream ss;
const QuicIntervalSet<int> v(QuicInterval<int>(1, 2));
auto return_type_is_a_ref = [](std::ostream&) {};
@@ -995,7 +1033,7 @@
bool operator==(const NotOstreamable&) const { return true; }
};
-TEST_F(QuicIntervalSetTest, IntervalOfTypeWithNoOstreamSupport) {
+TEST_P(QuicIntervalSetTest, IntervalOfTypeWithNoOstreamSupport) {
const NotOstreamable v;
const QuicIntervalSet<NotOstreamable> d(QuicInterval<NotOstreamable>(v, v));
// EXPECT_EQ builds a string representation of d. If d::operator<<()
@@ -1004,48 +1042,52 @@
EXPECT_EQ(d, d);
}
-class QuicIntervalSetInitTest : public QuicTest {
+class QuicIntervalSetInitTest : public QuicTestWithParam<bool> {
protected:
+ virtual void SetUp() { Quic_Test_Set_Fast(GetParam()); }
const std::vector<QuicInterval<int>> intervals_{{0, 1}, {2, 4}};
};
+INSTANTIATE_TEST_SUITE_P(QuicIntervalSetInitTest,
+ QuicIntervalSetInitTest,
+ ::testing::Bool());
-TEST_F(QuicIntervalSetInitTest, DirectInit) {
+TEST_P(QuicIntervalSetInitTest, DirectInit) {
std::initializer_list<QuicInterval<int>> il = {{0, 1}, {2, 3}, {3, 4}};
QuicIntervalSet<int> s(il);
EXPECT_THAT(s, ElementsAreArray(intervals_));
}
-TEST_F(QuicIntervalSetInitTest, CopyInit) {
+TEST_P(QuicIntervalSetInitTest, CopyInit) {
std::initializer_list<QuicInterval<int>> il = {{0, 1}, {2, 3}, {3, 4}};
QuicIntervalSet<int> s = il;
EXPECT_THAT(s, ElementsAreArray(intervals_));
}
-TEST_F(QuicIntervalSetInitTest, AssignIterPair) {
+TEST_P(QuicIntervalSetInitTest, AssignIterPair) {
QuicIntervalSet<int> s(0, 1000); // Make sure assign clears.
s.assign(intervals_.begin(), intervals_.end());
EXPECT_THAT(s, ElementsAreArray(intervals_));
}
-TEST_F(QuicIntervalSetInitTest, AssignInitList) {
+TEST_P(QuicIntervalSetInitTest, AssignInitList) {
QuicIntervalSet<int> s(0, 1000); // Make sure assign clears.
s.assign({{0, 1}, {2, 3}, {3, 4}});
EXPECT_THAT(s, ElementsAreArray(intervals_));
}
-TEST_F(QuicIntervalSetInitTest, AssignmentInitList) {
+TEST_P(QuicIntervalSetInitTest, AssignmentInitList) {
std::initializer_list<QuicInterval<int>> il = {{0, 1}, {2, 3}, {3, 4}};
QuicIntervalSet<int> s;
s = il;
EXPECT_THAT(s, ElementsAreArray(intervals_));
}
-TEST_F(QuicIntervalSetInitTest, BracedInitThenBracedAssign) {
+TEST_P(QuicIntervalSetInitTest, BracedInitThenBracedAssign) {
QuicIntervalSet<int> s{{0, 1}, {2, 3}, {3, 4}};
s = {{0, 1}, {2, 4}};
EXPECT_THAT(s, ElementsAreArray(intervals_));
}
-} // namespace
} // namespace test
+
} // namespace quic
diff --git a/quic/core/quic_interval_test.cc b/quic/core/quic_interval_test.cc
index 209299d..ee89285 100644
--- a/quic/core/quic_interval_test.cc
+++ b/quic/core/quic_interval_test.cc
@@ -375,6 +375,19 @@
EXPECT_TRUE(d.Difference(d8, &diff) && diff.empty());
}
+TEST_F(QuicIntervalTest, Separated) {
+ using QI = QuicInterval<int>;
+ EXPECT_FALSE(QI(100, 200).Separated(QI(100, 200)));
+ EXPECT_FALSE(QI(100, 200).Separated(QI(200, 300)));
+ EXPECT_TRUE(QI(100, 200).Separated(QI(201, 300)));
+ EXPECT_FALSE(QI(100, 200).Separated(QI(0, 100)));
+ EXPECT_TRUE(QI(100, 200).Separated(QI(0, 99)));
+ EXPECT_FALSE(QI(100, 200).Separated(QI(150, 170)));
+ EXPECT_FALSE(QI(150, 170).Separated(QI(100, 200)));
+ EXPECT_FALSE(QI(100, 200).Separated(QI(150, 250)));
+ EXPECT_FALSE(QI(150, 250).Separated(QI(100, 200)));
+}
+
TEST_F(QuicIntervalTest, Length) {
const QuicInterval<int> empty1;
const QuicInterval<int> empty2(1, 1);
diff --git a/quic/platform/api/quic_containers.h b/quic/platform/api/quic_containers.h
index d0c63a5..fa4610b 100644
--- a/quic/platform/api/quic_containers.h
+++ b/quic/platform/api/quic_containers.h
@@ -52,6 +52,14 @@
template <typename T, size_t N, typename A = std::allocator<T>>
using QuicInlinedVector = QuicInlinedVectorImpl<T, N, A>;
+// An ordered set of values.
+//
+// DOES NOT GUARANTEE POINTER OR ITERATOR STABILITY!
+template <typename Key,
+ typename Compare = std::less<Key>,
+ typename Rep = std::vector<Key>>
+using QuicOrderedSet = QuicOrderedSetImpl<Key, Compare, Rep>;
+
} // namespace quic
#endif // QUICHE_QUIC_PLATFORM_API_QUIC_CONTAINERS_H_
