Get rid of dead code that was protected by deprecated --gfe_restart_flag_quic_startup_faster_interval_set
PiperOrigin-RevId: 357625885
Change-Id: Ifeb30d745974aa2432945e588a4f4cd0d4c79e03
diff --git a/quic/core/quic_flags_list.h b/quic/core/quic_flags_list.h
index 93b0e01..b5d5121 100644
--- a/quic/core/quic_flags_list.h
+++ b/quic/core/quic_flags_list.h
@@ -72,7 +72,6 @@
QUIC_FLAG(FLAGS_quic_restart_flag_quic_offload_pacing_to_usps2, false)
QUIC_FLAG(FLAGS_quic_restart_flag_quic_server_temporarily_retain_tls_zero_rtt_keys, true)
QUIC_FLAG(FLAGS_quic_restart_flag_quic_session_tickets_always_enabled, true)
-QUIC_FLAG(FLAGS_quic_restart_flag_quic_startup_faster_interval_set, true)
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_set.h b/quic/core/quic_interval_set.h
index e272b50..fef0893 100644
--- a/quic/core/quic_interval_set.h
+++ b/quic/core/quic_interval_set.h
@@ -57,17 +57,13 @@
#include <utility>
#include <vector>
-#include <iterator>
#include <string>
-#include "absl/types/variant.h"
#include "quic/core/quic_interval.h"
#include "quic/platform/api/quic_containers.h"
-#include "quic/platform/api/quic_flags.h"
#include "quic/platform/api/quic_logging.h"
namespace quic {
-namespace oldquic {
template <typename T>
class QUIC_NO_EXPORT QuicIntervalSet {
@@ -76,887 +72,6 @@
private:
struct QUIC_NO_EXPORT IntervalLess {
- bool operator()(const value_type& a, const value_type& b) const;
- };
- // TODO(wub): Switch to absl::btree_set when it is available in Chromium.
- using Set = std::set<value_type, IntervalLess>;
-
- public:
- using const_iterator = typename Set::const_iterator;
- using const_reverse_iterator = typename Set::const_reverse_iterator;
-
- // Instantiates an empty QuicIntervalSet.
- QuicIntervalSet() {}
-
- // Instantiates an 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 an 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() {
- QUICHE_DCHECK(!Empty());
- intervals_.erase(intervals_.begin());
- }
-
- // Trim all values that is 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.
- 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.
- 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".
- 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();
- }
- };
-
- // Removes overlapping ranges and coalesces adjacent intervals as needed.
- void Compact(const typename Set::iterator& begin,
- const typename Set::iterator& end);
-
- // 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 QUICHE_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'.
- 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".
- 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) {});
- }
-
- // 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) {
- 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;
- std::pair<typename Set::iterator, bool> ins = intervals_.insert(interval);
- if (!ins.second) {
- // This interval already exists.
- return;
- }
- // Determine the minimal range that will have to be compacted. We know that
- // the QuicIntervalSet was valid before the addition of the interval, so only
- // need to start with the interval itself (although Compact takes an open
- // range so begin needs to be the interval to the left). We don't know how
- // many ranges this interval may cover, so we need to find the appropriate
- // interval to end with on the right.
- typename Set::iterator begin = ins.first;
- if (begin != intervals_.begin())
- --begin;
- const value_type target_end(interval.max(), interval.max());
- const typename Set::iterator end = intervals_.upper_bound(target_end);
- Compact(begin, end);
-}
-
-template <typename T>
-bool QuicIntervalSet<T>::Contains(const T& value) const {
- value_type tmp(value, value);
- // Find the first interval with min() > value, then move back one step
- const_iterator it = intervals_.upper_bound(tmp);
- 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);
- 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.
-//
-// Determining the candidate interval takes a couple of steps. First, since the
-// underlying std::set stores intervals, not values, we need to create a "probe
-// interval" suitable for use as a search key. The probe interval used is
-// [value, value). Now we can restate the problem as finding the largest
-// interval in the QuicIntervalSet that is <= the probe interval.
-//
-// This restatement only works if the set's comparator behaves in a certain way.
-// In particular it needs to order first by ascending min(), and then by
-// descending max(). The comparator used by this library is defined in exactly
-// this way. To see why descending max() is required, consider the following
-// example. Assume an QuicIntervalSet containing these intervals:
-//
-// [0, 5) [10, 20) [50, 60)
-//
-// Consider searching for the value 15. The probe interval [15, 15) is created,
-// and [10, 20) is identified as the largest interval in the set <= the probe
-// interval. This is the correct interval needed for the Contains() test, which
-// will then return true.
-//
-// Now consider searching for the value 30. The probe interval [30, 30) is
-// created, and again [10, 20] is identified as the largest interval <= the
-// probe interval. This is again the correct interval needed for the Contains()
-// test, which in this case returns false.
-//
-// Finally, consider searching for the value 10. The probe interval [10, 10) is
-// created. Here the ordering relationship between [10, 10) and [10, 20) becomes
-// vitally important. If [10, 10) were to come before [10, 20), then [0, 5)
-// would be the largest interval <= the probe, leading to the wrong choice of
-// interval for the Contains() test. Therefore [10, 10) needs to come after
-// [10, 20). The simplest way to make this work in the general case is to order
-// by ascending min() but descending max(). In this ordering, the empty interval
-// is larger than any non-empty interval with the same min(). The comparator
-// used by this library is careful to induce this ordering.
-//
-// Another detail involves the choice of which std::set method to use to try to
-// find the candidate interval. The most appropriate entry point is
-// set::upper_bound(), which finds the smallest interval which is > the probe
-// interval. The semantics of upper_bound() are slightly different from what we
-// want (namely, to find the largest 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 {
- value_type tmp(value, value);
- const_iterator it = intervals_.upper_bound(tmp);
- 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(). The candidate interval is the largest
-// interval that is <= the probe interval.
-//
-// The search for the candidate interval only works if the comparator used
-// behaves in a certain way. In particular it needs to order first by ascending
-// min(), and then by descending max(). The comparator used by this library is
-// defined in exactly this way. To see why descending max() is required,
-// consider the following example. Assume an QuicIntervalSet containing these
-// intervals:
-//
-// [0, 5) [10, 20) [50, 60)
-//
-// Consider searching for the probe [15, 17). [10, 20) is the largest interval
-// in the set which is <= the probe interval. This is the correct interval
-// needed for the Contains() test, which will then return true, because [10, 20)
-// contains [15, 17).
-//
-// Now consider searching for the probe [30, 32). Again [10, 20] is the largest
-// interval <= the probe interval. This is again the correct interval needed for
-// the Contains() test, which in this case returns false, because [10, 20) does
-// not contain [30, 32).
-//
-// Finally, consider searching for the probe [10, 12). Here the ordering
-// relationship between [10, 12) and [10, 20) becomes vitally important. If
-// [10, 12) were to come before [10, 20), then [0, 5) would be the largest
-// interval <= the probe, leading to the wrong choice of interval for the
-// Contains() test. Therefore [10, 12) needs to come after [10, 20). The
-// simplest way to make this work in the general case is to order by ascending
-// min() but descending max(). In this ordering, given two intervals with the
-// same min(), the wider one goes before the narrower one. The comparator used
-// by this library is careful to induce this ordering.
-//
-// Another detail involves the choice of which std::set method to use to try to
-// find the candidate interval. The most appropriate entry point is
-// set::upper_bound(), which finds the smallest interval which is > the probe
-// interval. The semantics of upper_bound() are slightly different from what we
-// want (namely, to find the largest 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 value_type& probe) const {
- const_iterator it = intervals_.upper_bound(probe);
- 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_type(value, 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_type(value, value));
-}
-
-template <typename T>
-bool QuicIntervalSet<T>::IsDisjoint(const value_type& interval) const {
- if (interval.Empty())
- return true;
- value_type tmp(interval.min(), interval.min());
- // Find the first interval with min() > interval.min()
- const_iterator it = intervals_.upper_bound(tmp);
- 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) {
- intervals_.insert(other.begin(), other.end());
- Compact(intervals_.begin(), intervals_.end());
-}
-
-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);
- 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) {
- QUICHE_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);
- }
- 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_.
- 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<typename Set::iterator, bool> ins =
- intervals_.insert(intersection);
- QUICHE_DCHECK(ins.second);
- mine = ins.first;
- ++theirs;
- }
- QUICHE_DCHECK(mine != intervals_.end());
- --theirs;
- ++mine;
- }
- QUICHE_DCHECK(Valid());
-}
-
-template <typename T>
-bool QuicIntervalSet<T>::Intersects(const QuicIntervalSet& other) const {
- if (!SpanningInterval().Intersects(other.SpanningInterval())) {
- return false;
- }
-
- const_iterator mine = FindIntersectionCandidate(other);
- if (mine == intervals_.end()) {
- return false;
- }
- const_iterator theirs = other.FindIntersectionCandidate(*mine);
-
- return FindNextIntersectingPair(other, &mine, &theirs);
-}
-
-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) {
- if (!SpanningInterval().Intersects(other.SpanningInterval())) {
- return;
- }
-
- const_iterator mine = FindIntersectionCandidate(other);
- // If no interval in mine reaches the first interval of theirs then we're
- // done.
- if (mine == intervals_.end()) {
- return;
- }
- const_iterator theirs = other.FindIntersectionCandidate(*this);
-
- while (FindNextIntersectingPair(other, &mine, &theirs)) {
- // At this point *mine and *theirs overlap. Remove mine from
- // intervals_ and replace it with the possibly two intervals that are
- // the difference between mine and theirs.
- value_type i(*mine);
- intervals_.erase(mine++);
- value_type lo;
- value_type hi;
- i.Difference(*theirs, &lo, &hi);
-
- if (!lo.Empty()) {
- // We have a low end. This can't intersect anything else.
- std::pair<typename Set::iterator, bool> ins = intervals_.insert(lo);
- QUICHE_DCHECK(ins.second);
- }
-
- if (!hi.Empty()) {
- std::pair<typename Set::iterator, bool> ins = intervals_.insert(hi);
- QUICHE_DCHECK(ins.second);
- mine = ins.first;
- }
- }
- QUICHE_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();
-}
-
-// This method compacts the QuicIntervalSet, merging pairs of overlapping
-// intervals into a single interval. In the steady state, the QuicIntervalSet
-// does not contain any such pairs. However, the way the Union() and Add()
-// methods work is to temporarily put the QuicIntervalSet into such a state and
-// then to call Compact() to "fix it up" so that it is no longer in that state.
-//
-// Compact() needs the interval set to allow two intervals [a,b) and [a,c)
-// (having the same min() but different max()) to briefly coexist in the set at
-// the same time, and be adjacent to each other, so that they can be efficiently
-// located and merged into a single interval. This state would be impossible
-// with a comparator which only looked at min(), as such a comparator would
-// consider such pairs equal. Fortunately, the comparator used by
-// QuicIntervalSet does exactly what is needed, ordering first by ascending
-// min(), then by descending max().
-template <typename T>
-void QuicIntervalSet<T>::Compact(const typename Set::iterator& begin,
- const typename Set::iterator& end) {
- if (begin == end)
- return;
- typename Set::iterator next = begin;
- typename Set::iterator prev = begin;
- typename Set::iterator it = begin;
- ++it;
- ++next;
- while (it != end) {
- ++next;
- if (prev->max() >= it->min()) {
- // Overlapping / coalesced range; merge the two intervals.
- T min = prev->min();
- T max = std::max(prev->max(), it->max());
- value_type i(min, max);
- intervals_.erase(prev);
- intervals_.erase(it);
- std::pair<typename Set::iterator, bool> ins = intervals_.insert(i);
- QUICHE_DCHECK(ins.second);
- prev = ins.first;
- } else {
- prev = it;
- }
- it = next;
- }
-}
-
-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() and then by
-// descending max(). Readers who are satisified with that explanation can stop
-// reading here. The remainder of this comment is for the benefit of future
-// maintainers of this library.
-//
-// The reason for this ordering is that this comparator has to serve two
-// masters. First, it has to maintain the intervals in its internal set in the
-// order that clients expect to see them. Clients see these intervals via the
-// iterators provided by begin()/end() or as a result of invoking Get(). For
-// this reason, the comparator orders intervals by ascending min().
-//
-// If client iteration were the only consideration, then ordering by ascending
-// min() would be good enough. This is because the intervals in the
-// QuicIntervalSet are non-empty, non-adjacent, and mutually disjoint; such
-// intervals happen to always have disjoint min() values, so such a comparator
-// would never even have to look at max() in order to work correctly for this
-// class.
-//
-// However, in addition to ordering by ascending min(), this comparator also has
-// a second responsibility: satisfying the special needs of this library's
-// peculiar internal implementation. These needs require the comparator to order
-// first by ascending min() and then by descending max(). The best way to
-// understand why this is so is to check out the comments associated with the
-// Find() and Compact() methods.
-template <typename T>
-bool QuicIntervalSet<T>::IntervalLess::operator()(const value_type& a,
- const value_type& b) const {
- 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
@@ -970,14 +85,13 @@
bool operator()(T&& point, const value_type& a) const;
};
- typedef QuicOrderedSet<value_type,
- IntervalLess,
- QuicInlinedVector<value_type, 10>>
- Set;
+ using Set = QuicOrderedSet<value_type,
+ IntervalLess,
+ QuicInlinedVector<value_type, 10>>;
public:
- typedef typename Set::const_iterator const_iterator;
- typedef typename Set::const_reverse_iterator const_reverse_iterator;
+ using const_iterator = typename Set::const_iterator;
+ using const_reverse_iterator = typename Set::const_reverse_iterator;
// Instantiates an empty QuicIntervalSet.
QuicIntervalSet() = default;
@@ -1779,333 +893,6 @@
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 ddbe200..14db466 100644
--- a/quic/core/quic_interval_set_test.cc
+++ b/quic/core/quic_interval_set_test.cc
@@ -16,29 +16,14 @@
#include "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 :
- // The parameter is whether to for FLAGS_quic_startup_faster_interval_set.
- public QuicTestWithParam<bool> {
+class QuicIntervalSetTest : public QuicTest {
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);
@@ -75,11 +60,8 @@
QuicIntervalSet<int> is;
QuicIntervalSet<int> other;
};
-INSTANTIATE_TEST_SUITE_P(QuicIntervalSetTest,
- QuicIntervalSetTest,
- ::testing::Bool());
-TEST_P(QuicIntervalSetTest, IsDisjoint) {
+TEST_F(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)));
@@ -180,13 +162,13 @@
<< "and max " << max;
}
-TEST_P(QuicIntervalSetTest, AddInterval) {
+TEST_F(QuicIntervalSetTest, AddInterval) {
QuicIntervalSet<int> s;
s.Add(QuicInterval<int>(0, 10));
EXPECT_TRUE(Check(s, 1, 0, 10));
}
-TEST_P(QuicIntervalSetTest, DecrementIterator) {
+TEST_F(QuicIntervalSetTest, DecrementIterator) {
auto it = is.end();
EXPECT_NE(it, is.begin());
--it;
@@ -195,7 +177,7 @@
EXPECT_EQ(it, is.end());
}
-TEST_P(QuicIntervalSetTest, AddOptimizedForAppend) {
+TEST_F(QuicIntervalSetTest, AddOptimizedForAppend) {
QuicIntervalSet<int> empty_one, empty_two;
empty_one.AddOptimizedForAppend(QuicInterval<int>(0, 99));
EXPECT_TRUE(Check(empty_one, 1, 0, 99));
@@ -224,7 +206,7 @@
EXPECT_TRUE(Check(iset, 3, 100, 150, 199, 250, 251, 350));
}
-TEST_P(QuicIntervalSetTest, PopFront) {
+TEST_F(QuicIntervalSetTest, PopFront) {
QuicIntervalSet<int> iset{{100, 200}, {400, 500}, {700, 800}};
EXPECT_TRUE(Check(iset, 3, 100, 200, 400, 500, 700, 800));
@@ -238,7 +220,7 @@
EXPECT_TRUE(iset.Empty());
}
-TEST_P(QuicIntervalSetTest, TrimLessThan) {
+TEST_F(QuicIntervalSetTest, TrimLessThan) {
QuicIntervalSet<int> iset{{100, 200}, {400, 500}, {700, 800}};
EXPECT_TRUE(Check(iset, 3, 100, 200, 400, 500, 700, 800));
@@ -265,7 +247,7 @@
EXPECT_TRUE(iset.Empty());
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetBasic) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetBasic) {
// Test Add, Get, Contains and Find
QuicIntervalSet<int> iset;
EXPECT_TRUE(iset.Empty());
@@ -390,7 +372,7 @@
EXPECT_FALSE(iset.Contains(i2));
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetContainsEmpty) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetContainsEmpty) {
const QuicIntervalSet<int> empty;
const QuicIntervalSet<int> other_empty;
const QuicIntervalSet<int> non_empty({{10, 20}, {40, 50}});
@@ -400,7 +382,7 @@
EXPECT_FALSE(non_empty.Contains(empty));
}
-TEST_P(QuicIntervalSetTest, Equality) {
+TEST_F(QuicIntervalSetTest, Equality) {
QuicIntervalSet<int> is_copy = is;
EXPECT_EQ(is, is);
EXPECT_EQ(is, is_copy);
@@ -409,7 +391,7 @@
EXPECT_EQ(QuicIntervalSet<int>(), QuicIntervalSet<int>());
}
-TEST_P(QuicIntervalSetTest, LowerAndUpperBound) {
+TEST_F(QuicIntervalSetTest, LowerAndUpperBound) {
QuicIntervalSet<int> intervals;
intervals.Add(10, 20);
intervals.Add(30, 40);
@@ -455,7 +437,7 @@
EXPECT_EQ(intervals.UpperBound(50), intervals.end());
}
-TEST_P(QuicIntervalSetTest, SpanningInterval) {
+TEST_F(QuicIntervalSetTest, SpanningInterval) {
// Spanning interval of an empty set is empty:
{
QuicIntervalSet<int> iset;
@@ -486,14 +468,14 @@
}
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetUnion) {
+TEST_F(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_P(QuicIntervalSetTest, QuicIntervalSetIntersection) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersection) {
EXPECT_TRUE(is.Intersects(other));
EXPECT_TRUE(other.Intersects(is));
is.Intersection(other);
@@ -503,7 +485,7 @@
EXPECT_TRUE(other.Intersects(is));
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionBothEmpty) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionBothEmpty) {
QuicIntervalSet<std::string> mine, theirs;
EXPECT_FALSE(mine.Intersects(theirs));
EXPECT_FALSE(theirs.Intersects(mine));
@@ -513,7 +495,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionEmptyMine) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionEmptyMine) {
QuicIntervalSet<std::string> mine;
QuicIntervalSet<std::string> theirs("a", "b");
EXPECT_FALSE(mine.Intersects(theirs));
@@ -524,7 +506,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionEmptyTheirs) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionEmptyTheirs) {
QuicIntervalSet<std::string> mine("a", "b");
QuicIntervalSet<std::string> theirs;
EXPECT_FALSE(mine.Intersects(theirs));
@@ -535,7 +517,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionTheirsBeforeMine) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionTheirsBeforeMine) {
QuicIntervalSet<std::string> mine("y", "z");
QuicIntervalSet<std::string> theirs;
theirs.Add("a", "b");
@@ -548,7 +530,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionMineBeforeTheirs) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionMineBeforeTheirs) {
QuicIntervalSet<std::string> mine;
mine.Add("a", "b");
mine.Add("c", "d");
@@ -561,7 +543,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_P(QuicIntervalSetTest,
+TEST_F(QuicIntervalSetTest,
QuicIntervalSetIntersectionTheirsBeforeMineInt64Singletons) {
QuicIntervalSet<int64_t> mine({{10, 15}});
QuicIntervalSet<int64_t> theirs({{-20, -5}});
@@ -573,7 +555,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_P(QuicIntervalSetTest,
+TEST_F(QuicIntervalSetTest,
QuicIntervalSetIntersectionMineBeforeTheirsIntSingletons) {
QuicIntervalSet<int> mine({{10, 15}});
QuicIntervalSet<int> theirs({{90, 95}});
@@ -585,7 +567,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionTheirsBetweenMine) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionTheirsBetweenMine) {
QuicIntervalSet<int64_t> mine({{0, 5}, {40, 50}});
QuicIntervalSet<int64_t> theirs({{10, 15}});
EXPECT_FALSE(mine.Intersects(theirs));
@@ -596,7 +578,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionMineBetweenTheirs) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionMineBetweenTheirs) {
QuicIntervalSet<int> mine({{20, 25}});
QuicIntervalSet<int> theirs({{10, 15}, {30, 32}});
EXPECT_FALSE(mine.Intersects(theirs));
@@ -607,7 +589,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionAlternatingIntervals) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionAlternatingIntervals) {
QuicIntervalSet<int> mine, theirs;
mine.Add(10, 20);
mine.Add(40, 50);
@@ -623,7 +605,7 @@
EXPECT_FALSE(theirs.Intersects(mine));
}
-TEST_P(QuicIntervalSetTest,
+TEST_F(QuicIntervalSetTest,
QuicIntervalSetIntersectionAdjacentAlternatingNonIntersectingIntervals) {
// Make sure that intersection with adjacent interval set is empty.
const QuicIntervalSet<int> x1({{0, 10}});
@@ -649,7 +631,7 @@
EXPECT_TRUE(result3.Empty()) << result3;
}
-TEST_P(QuicIntervalSetTest,
+TEST_F(QuicIntervalSetTest,
QuicIntervalSetIntersectionAlternatingIntersectingIntervals) {
const QuicIntervalSet<int> x1({{0, 10}});
const QuicIntervalSet<int> y1({{-50, 1}, {9, 95}});
@@ -678,7 +660,7 @@
EXPECT_EQ(result3, expected_result3);
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionIdentical) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionIdentical) {
QuicIntervalSet<int> copy(is);
EXPECT_TRUE(copy.Intersects(is));
EXPECT_TRUE(is.Intersects(copy));
@@ -686,7 +668,7 @@
EXPECT_EQ(copy, is);
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionSuperset) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionSuperset) {
QuicIntervalSet<int> mine(-1, 10000);
EXPECT_TRUE(mine.Intersects(is));
EXPECT_TRUE(is.Intersects(mine));
@@ -694,7 +676,7 @@
EXPECT_EQ(is, mine);
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionSubset) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionSubset) {
QuicIntervalSet<int> copy(is);
QuicIntervalSet<int> theirs(-1, 10000);
EXPECT_TRUE(copy.Intersects(theirs));
@@ -703,7 +685,7 @@
EXPECT_EQ(copy, is);
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetIntersectionLargeSet) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionLargeSet) {
QuicIntervalSet<int> mine, theirs;
// mine: [0, 9), [10, 19), ..., [990, 999)
for (int i = 0; i < 1000; i += 10) {
@@ -721,7 +703,7 @@
EXPECT_TRUE(theirs.Intersects(mine));
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetDifference) {
+TEST_F(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));
@@ -730,7 +712,7 @@
EXPECT_TRUE(is.Empty());
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetDifferenceSingleBounds) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceSingleBounds) {
std::vector<QuicInterval<int>> ivals(other.begin(), other.end());
for (const QuicInterval<int>& ival : ivals) {
is.Difference(ival.min(), ival.max());
@@ -739,7 +721,7 @@
700, 770, 900, 1000, 1100, 1200, 1900, 2000, 2100, 2200));
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetDifferenceSingleInterval) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceSingleInterval) {
std::vector<QuicInterval<int>> ivals(other.begin(), other.end());
for (const QuicInterval<int>& ival : ivals) {
is.Difference(ival);
@@ -748,7 +730,7 @@
700, 770, 900, 1000, 1100, 1200, 1900, 2000, 2100, 2200));
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetDifferenceAlternatingIntervals) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceAlternatingIntervals) {
QuicIntervalSet<int> mine, theirs;
mine.Add(10, 20);
mine.Add(40, 50);
@@ -761,7 +743,7 @@
EXPECT_TRUE(Check(mine, 3, 10, 20, 40, 50, 60, 70));
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetDifferenceEmptyMine) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceEmptyMine) {
QuicIntervalSet<std::string> mine, theirs;
theirs.Add("a", "b");
@@ -769,7 +751,7 @@
EXPECT_TRUE(mine.Empty());
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetDifferenceEmptyTheirs) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceEmptyTheirs) {
QuicIntervalSet<std::string> mine, theirs;
mine.Add("a", "b");
@@ -779,7 +761,7 @@
EXPECT_EQ("b", mine.begin()->max());
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetDifferenceTheirsBeforeMine) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceTheirsBeforeMine) {
QuicIntervalSet<std::string> mine, theirs;
mine.Add("y", "z");
theirs.Add("a", "b");
@@ -790,7 +772,7 @@
EXPECT_EQ("z", mine.begin()->max());
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetDifferenceMineBeforeTheirs) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceMineBeforeTheirs) {
QuicIntervalSet<std::string> mine, theirs;
mine.Add("a", "b");
theirs.Add("y", "z");
@@ -801,7 +783,7 @@
EXPECT_EQ("b", mine.begin()->max());
}
-TEST_P(QuicIntervalSetTest, QuicIntervalSetDifferenceIdentical) {
+TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceIdentical) {
QuicIntervalSet<std::string> mine;
mine.Add("a", "b");
mine.Add("c", "d");
@@ -811,7 +793,7 @@
EXPECT_TRUE(mine.Empty());
}
-TEST_P(QuicIntervalSetTest, EmptyComplement) {
+TEST_F(QuicIntervalSetTest, EmptyComplement) {
// The complement of an empty set is the input interval:
QuicIntervalSet<int> iset;
iset.Complement(100, 200);
@@ -891,7 +873,7 @@
return result;
}
-TEST_P(QuicIntervalSetTest, SingleIntervalComplement) {
+TEST_F(QuicIntervalSetTest, SingleIntervalComplement) {
// Verify the complement of a set with one interval (i):
// |----- i -----|
// |----- args -----|
@@ -941,7 +923,7 @@
return result;
}
-TEST_P(QuicIntervalSetTest, MultiIntervalComplement) {
+TEST_F(QuicIntervalSetTest, MultiIntervalComplement) {
// Initialize a small test set:
QuicIntervalSet<int> iset;
iset.Add(100, 200);
@@ -984,7 +966,7 @@
}
// Verifies ToString, operator<< don't assert.
-TEST_P(QuicIntervalSetTest, ToString) {
+TEST_F(QuicIntervalSetTest, ToString) {
QuicIntervalSet<int> iset;
iset.Add(300, 400);
iset.Add(100, 200);
@@ -997,14 +979,14 @@
EXPECT_EQ("{ }", QuicIntervalSet<int>().ToString());
}
-TEST_P(QuicIntervalSetTest, ConstructionDiscardsEmptyInterval) {
+TEST_F(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_P(QuicIntervalSetTest, Swap) {
+TEST_F(QuicIntervalSetTest, Swap) {
QuicIntervalSet<int> a, b;
a.Add(300, 400);
b.Add(100, 200);
@@ -1017,7 +999,7 @@
EXPECT_TRUE(Check(b, 2, 100, 200, 500, 600));
}
-TEST_P(QuicIntervalSetTest, OutputReturnsOstreamRef) {
+TEST_F(QuicIntervalSetTest, OutputReturnsOstreamRef) {
std::stringstream ss;
const QuicIntervalSet<int> v(QuicInterval<int>(1, 2));
auto return_type_is_a_ref = [](std::ostream&) {};
@@ -1033,7 +1015,7 @@
bool operator==(const NotOstreamable&) const { return true; }
};
-TEST_P(QuicIntervalSetTest, IntervalOfTypeWithNoOstreamSupport) {
+TEST_F(QuicIntervalSetTest, IntervalOfTypeWithNoOstreamSupport) {
const NotOstreamable v;
const QuicIntervalSet<NotOstreamable> d(QuicInterval<NotOstreamable>(v, v));
// EXPECT_EQ builds a string representation of d. If d::operator<<()
@@ -1042,52 +1024,48 @@
EXPECT_EQ(d, d);
}
-class QuicIntervalSetInitTest : public QuicTestWithParam<bool> {
+class QuicIntervalSetInitTest : public QuicTest {
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_P(QuicIntervalSetInitTest, DirectInit) {
+TEST_F(QuicIntervalSetInitTest, DirectInit) {
std::initializer_list<QuicInterval<int>> il = {{0, 1}, {2, 3}, {3, 4}};
QuicIntervalSet<int> s(il);
EXPECT_THAT(s, ElementsAreArray(intervals_));
}
-TEST_P(QuicIntervalSetInitTest, CopyInit) {
+TEST_F(QuicIntervalSetInitTest, CopyInit) {
std::initializer_list<QuicInterval<int>> il = {{0, 1}, {2, 3}, {3, 4}};
QuicIntervalSet<int> s = il;
EXPECT_THAT(s, ElementsAreArray(intervals_));
}
-TEST_P(QuicIntervalSetInitTest, AssignIterPair) {
+TEST_F(QuicIntervalSetInitTest, AssignIterPair) {
QuicIntervalSet<int> s(0, 1000); // Make sure assign clears.
s.assign(intervals_.begin(), intervals_.end());
EXPECT_THAT(s, ElementsAreArray(intervals_));
}
-TEST_P(QuicIntervalSetInitTest, AssignInitList) {
+TEST_F(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_P(QuicIntervalSetInitTest, AssignmentInitList) {
+TEST_F(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_P(QuicIntervalSetInitTest, BracedInitThenBracedAssign) {
+TEST_F(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
