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