// Copyright (c) 2019 The Chromium Authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #ifndef QUICHE_QUIC_CORE_QUIC_INTERVAL_SET_H_ #define QUICHE_QUIC_CORE_QUIC_INTERVAL_SET_H_ // QuicIntervalSet<T> is a data structure used to represent a sorted set of // non-empty, non-adjacent, and mutually disjoint intervals. Mutations to an // interval set preserve these properties, altering the set as needed. For // example, adding [2, 3) to a set containing only [1, 2) would result in the // set containing the single interval [1, 3). // // Supported operations include testing whether an Interval is contained in the // QuicIntervalSet, comparing two QuicIntervalSets, and performing // QuicIntervalSet union, intersection, and difference. // // QuicIntervalSet maintains the minimum number of entries needed to represent // the set of underlying intervals. When the QuicIntervalSet is modified (e.g. // due to an Add operation), other interval entries may be coalesced, removed, // or otherwise modified in order to maintain this invariant. The intervals are // maintained in sorted order, by ascending min() value. // // The reader is cautioned to beware of the terminology used here: this library // uses the terms "min" and "max" rather than "begin" and "end" as is // conventional for the STL. The terminology [min, max) refers to the half-open // interval which (if the interval is not empty) contains min but does not // contain max. An interval is considered empty if min >= max. // // T is required to be default- and copy-constructible, to have an assignment // operator, a difference operator (operator-()), and the full complement of // comparison operators (<, <=, ==, !=, >=, >). These requirements are inherited // from value_type. // // QuicIntervalSet has constant-time move operations. // // // Examples: // QuicIntervalSet<int> intervals; // intervals.Add(Interval<int>(10, 20)); // intervals.Add(Interval<int>(30, 40)); // // intervals contains [10,20) and [30,40). // intervals.Add(Interval<int>(15, 35)); // // intervals has been coalesced. It now contains the single range [10,40). // EXPECT_EQ(1, intervals.Size()); // EXPECT_TRUE(intervals.Contains(Interval<int>(10, 40))); // // intervals.Difference(Interval<int>(10, 20)); // // intervals should now contain the single range [20, 40). // EXPECT_EQ(1, intervals.Size()); // EXPECT_TRUE(intervals.Contains(Interval<int>(20, 40))); #include <stddef.h> #include <algorithm> #include <initializer_list> #include <set> #include <sstream> #include <string> #include <utility> #include <vector> #include "quiche/quic/core/quic_interval.h" #include "quiche/quic/platform/api/quic_flags.h" #include "quiche/common/platform/api/quiche_containers.h" #include "quiche/common/platform/api/quiche_logging.h" namespace quic { template <typename T> class QUICHE_NO_EXPORT QuicIntervalSet { … }; template <typename T> auto operator<<(std::ostream& out, const QuicIntervalSet<T>& seq) -> decltype(out << *seq.begin()) { … } //============================================================================== // Implementation details: Clients can stop reading here. template <typename T> typename QuicIntervalSet<T>::value_type QuicIntervalSet<T>::SpanningInterval() const { … } template <typename T> void QuicIntervalSet<T>::Add(const value_type& interval) { … } template <typename T> bool QuicIntervalSet<T>::Contains(const T& value) const { … } template <typename T> bool QuicIntervalSet<T>::Contains(const value_type& interval) const { … } template <typename T> bool QuicIntervalSet<T>::Contains(const QuicIntervalSet<T>& other) const { … } // This method finds the interval that Contains() "value", if such an interval // exists in the QuicIntervalSet. The way this is done is to locate the // "candidate interval", the only interval that could *possibly* contain value, // and test it using Contains(). The candidate interval is the interval with the // largest min() having min() <= value. // // Another detail involves the choice of which Set method to use to try to find // the candidate interval. The most appropriate entry point is // Set::upper_bound(), which finds the least interval with a min > the // value. The semantics of upper_bound() are slightly different from what we // want (namely, to find the greatest interval which is <= the probe interval) // but they are close enough; the interval found by upper_bound() will always be // one step past the interval we are looking for (if it exists) or at begin() // (if it does not). Getting to the proper interval is a simple matter of // decrementing the iterator. template <typename T> typename QuicIntervalSet<T>::const_iterator QuicIntervalSet<T>::Find( const T& value) const { … } // This method finds the interval that Contains() the interval "probe", if such // an interval exists in the QuicIntervalSet. The way this is done is to locate // the "candidate interval", the only interval that could *possibly* contain // "probe", and test it using Contains(). We use the same algorithm as for // Find(value), except that instead of checking that the value is contained, we // check that the probe is contained. template <typename T> typename QuicIntervalSet<T>::const_iterator QuicIntervalSet<T>::Find( const value_type& probe) const { … } template <typename T> typename QuicIntervalSet<T>::const_iterator QuicIntervalSet<T>::LowerBound( const T& value) const { … } template <typename T> typename QuicIntervalSet<T>::const_iterator QuicIntervalSet<T>::UpperBound( const T& value) const { … } template <typename T> bool QuicIntervalSet<T>::IsDisjoint(const value_type& interval) const { … } template <typename T> void QuicIntervalSet<T>::Union(const QuicIntervalSet& other) { … } template <typename T> typename QuicIntervalSet<T>::const_iterator QuicIntervalSet<T>::FindIntersectionCandidate( const QuicIntervalSet& other) const { … } template <typename T> typename QuicIntervalSet<T>::const_iterator QuicIntervalSet<T>::FindIntersectionCandidate( const value_type& interval) const { … } 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) { … } template <typename T> void QuicIntervalSet<T>::Intersection(const QuicIntervalSet& other) { … } template <typename T> bool QuicIntervalSet<T>::Intersects(const QuicIntervalSet& other) const { … } template <typename T> void QuicIntervalSet<T>::Difference(const value_type& interval) { … } template <typename T> void QuicIntervalSet<T>::Difference(const T& min, const T& max) { … } template <typename T> void QuicIntervalSet<T>::Difference(const QuicIntervalSet& other) { … } template <typename T> void QuicIntervalSet<T>::Complement(const T& min, const T& max) { … } template <typename T> std::string QuicIntervalSet<T>::ToString() const { … } template <typename T> bool QuicIntervalSet<T>::Valid() const { … } // This comparator orders intervals first by ascending min(). The Set never // contains overlapping intervals, so that suffices. template <typename T> bool QuicIntervalSet<T>::IntervalLess::operator()(const value_type& a, const value_type& b) const { … } // It appears that the Set::lower_bound(T) method uses only two overloads of the // comparison operator that take a T as the second argument.. In contrast // Set::upper_bound(T) uses the two overloads that take T as the first argument. template <typename T> bool QuicIntervalSet<T>::IntervalLess::operator()(const value_type& a, const T& point) const { … } template <typename T> bool QuicIntervalSet<T>::IntervalLess::operator()(const value_type& a, T&& point) const { … } // It appears that the Set::upper_bound(T) method uses only the next two // overloads of the comparison operator. template <typename T> bool QuicIntervalSet<T>::IntervalLess::operator()(const T& point, const value_type& a) const { … } template <typename T> bool QuicIntervalSet<T>::IntervalLess::operator()(T&& point, const value_type& a) const { … } } // namespace quic #endif // QUICHE_QUIC_CORE_QUIC_INTERVAL_SET_H_
Codebase Browser
chromium