Landing Recent QUIC changes until 9/11/2015 02:59 UTC.

relnote: Change QUIC's last_stop_waiting_frames vector into a single
last_stop_waiting_frame so we only process the most recent stop waiting
frame.

Merge internal change: 102813220
https://codereview.chromium.org/1351703002/

relnote: Deprecate FLAGS_quic_process_frames_inline.

Merge internal change: 102676622
https://codereview.chromium.org/1349833006/

relnote: Switch QuicDispatcher::closed_session_list_ to a vector<>.
No functional change.

This does not have a visible performance impact in the microbenchmark,
though list<> iteration takes up around 0.4% of the CPU of a running
internal server.

Merge internal change: 102666435
https://codereview.chromium.org/1346393002/

relnote: Deprecate FLAGS_quic_use_conservative_receive_buffer.

Merge internal change: 102661974
https://codereview.chromium.org/1345343002/

relnote:  Deprecate FLAGS_quic_do_path_mtu_discovery.

Merge internal change: 102655931
https://codereview.chromium.org/1346383002/

relnote: Fixes bug in QUIC's cubic code that caused inflation in
congestion window after quiescence.  Flag protected under
FLAGS_reset_cubic_epoch_when_app_limited

cr/101977605 fixed the standard Cubic implementation, this fixes cubic
quantized in bytes.

Merge internal change: 102389856
https://codereview.chromium.org/1347073003/

relnote: Remove unused counter of time wait list map as b/23531792 is
fixed. No functional change expected.

Merge internal change: 102382958
https://codereview.chromium.org/1350863004/

QUIC - Added ReliableQuicStreamPeer::WriteOrBufferData and
QuicSession::set_error methods.

The following is the internal note:

Adding a quic retry requests test, with associated fixes.

retry_backend:
  --moved response counting to shared code
  --implemented partial header sending and retry validation for QUIC
quic fixes:
  --Added QuicWriter::Clear, fixing a bug where headers were not sent to
    backends on retry.
  --Fixed but where double calling Quit() on the test backend caused
     notification crash.
  --Addressed TODO to handle [Start/Stop]ListeningForDisconnect
  --Handled several bugs with backend connections for dead connections
    being reused.
  --Fixed a bug where immediate failed connection resulted in accessing
    the still null client_ in QuicBackendChannel

relnote: minor QUIC refactors for quic-to-backend retries

Merge internal change: 102242554
https://codereview.chromium.org/1347973003/

relnote: n/a (comment only). Fix comment for GetNextServerNonce to refer
to nonces instead of connection IDs.

Merge internal change: 102241989
https://codereview.chromium.org/1350813004/

relnote: Added an option(BWRS) for Server bandwidth resumption.

Merge internal change: 102239461
https://codereview.chromium.org/1345983003/

relnote: n/a (comment). This (new) comment only made sense in the
context of there being an (obsolete) kSVER, which no longer exists.

Merge internal change: 102238117
https://codereview.chromium.org/1350583002/

relnote: Avoid 2 somewhat redundant allocations in QUIC
AckNotifierManager.

This does not show up visibly in microbenchmarks, though on loaded
machines the alloc/realloc of the list in OnPacketRetransmitted takes up
~0.05% of the CPU and the implicit construction of the hash_map entry
takes up ~0.2% of the CPU, the latter being redundant if no notifiers
are meant to be added.

Merge internal change: 102170476
https://codereview.chromium.org/1346873002/

relnote: n/a (test only). Disable stateless reject support in the QUIC
end to end tests. Causing failures when new QUIC versions are introduced.

Stateless rejects are not yet used in production, flag protected and
blocked on b/12896829.

Merge internal change: 102168430
https://codereview.chromium.org/1347933003/

relnote: Use an IntervalSet for QuicAckFrame::missing_packets if
FLAGS_quic_packet_queue_use_interval_set is set.

Note: the microbenchmark results are a bit skewed. I don't know why.
However, every indication is that this is broadly more efficient.

<deleted benchmark results>.

Rename NumPacketsTestOnly to NumPacketsSlow.

Merge internal change: 102154816
https://codereview.chromium.org/1350573002/

QUIC - Added Interval and IntervalSet classes. These classed will be
used by QuicAckFrame::missing_packets.

These classes are required by CL: 102154816
https://codereview.chromium.org/1340403002/

R=rch@chromium.org

Review URL: https://codereview.chromium.org/1347283002

Cr-Commit-Position: refs/heads/master@{#349565}

35 files changed, 2958 insertions, 345 deletions

diff --git a/net/net.gypi b/net/net.gypi
index b125f65..34bdd79 100644
--- a/net/net.gypi
+++ b/net/net.gypi
@@ -276,6 +276,8 @@
       'quic/crypto/strike_register.cc',
       'quic/crypto/strike_register.h',
       'quic/crypto/strike_register_client.h',
+      'quic/interval.h',
+      'quic/interval_set.h',
       'quic/iovector.cc',
       'quic/iovector.h',
       'quic/p2p/quic_p2p_crypto_config.cc',
@@ -1500,6 +1502,8 @@
       'quic/crypto/quic_crypto_server_config_test.cc',
       'quic/crypto/quic_random_test.cc',
       'quic/crypto/strike_register_test.cc',
+      'quic/interval_test.cc',
+      'quic/interval_set_test.cc',
       'quic/iovector_test.cc',
       'quic/network_connection_unittest.cc',
       'quic/p2p/quic_p2p_session_test.cc',
diff --git a/net/quic/congestion_control/cubic_bytes.cc b/net/quic/congestion_control/cubic_bytes.cc
index 40259ce..e538b2b 100644
--- a/net/quic/congestion_control/cubic_bytes.cc
+++ b/net/quic/congestion_control/cubic_bytes.cc
@@ -79,6 +79,18 @@ void CubicBytes::Reset() {
   last_target_congestion_window_ = 0;
 }
 
+void CubicBytes::OnApplicationLimited() {
+  // When sender is not using the available congestion window, the window does
+  // not grow. But to be RTT-independent, Cubic assumes that the sender has been
+  // using the entire window during the time since the beginning of the current
+  // "epoch" (the end of the last loss recovery period). Since
+  // application-limited periods break this assumption, we reset the epoch when
+  // in such a period. This reset effectively freezes congestion window growth
+  // through application-limited periods and allows Cubic growth to continue
+  // when the entire window is being used.
+  epoch_ = QuicTime::Zero();
+}
+
 QuicByteCount CubicBytes::CongestionWindowAfterPacketLoss(
     QuicByteCount current_congestion_window) {
   if (current_congestion_window < last_max_congestion_window_) {
@@ -158,7 +170,7 @@ QuicByteCount CubicBytes::CongestionWindowAfterAck(
     target_congestion_window = estimated_tcp_congestion_window_;
   }
 
-  DVLOG(1) << "Target congestion_window: " << target_congestion_window;
+  DVLOG(1) << "Final target congestion_window: " << target_congestion_window;
   return target_congestion_window;
 }
 
diff --git a/net/quic/congestion_control/cubic_bytes.h b/net/quic/congestion_control/cubic_bytes.h
index 1df9f37..9b4e2ad 100644
--- a/net/quic/congestion_control/cubic_bytes.h
+++ b/net/quic/congestion_control/cubic_bytes.h
@@ -39,6 +39,10 @@ class NET_EXPORT_PRIVATE CubicBytes {
                                          QuicByteCount current,
                                          QuicTime::Delta delay_min);
 
+  // Call on ack arrival when sender is unable to use the available congestion
+  // window. Resets Cubic state during quiescence.
+  void OnApplicationLimited();
+
  private:
   static const QuicTime::Delta MaxCubicTimeInterval() {
     return QuicTime::Delta::FromMilliseconds(30);
diff --git a/net/quic/congestion_control/send_algorithm_interface.cc b/net/quic/congestion_control/send_algorithm_interface.cc
index eaad6ca..d1b0ec5 100644
--- a/net/quic/congestion_control/send_algorithm_interface.cc
+++ b/net/quic/congestion_control/send_algorithm_interface.cc
@@ -6,7 +6,6 @@
 
 #include "net/quic/congestion_control/tcp_cubic_bytes_sender.h"
 #include "net/quic/congestion_control/tcp_cubic_sender.h"
-#include "net/quic/quic_flags.h"
 #include "net/quic/quic_protocol.h"
 
 namespace net {
@@ -21,9 +20,7 @@ SendAlgorithmInterface* SendAlgorithmInterface::Create(
     QuicConnectionStats* stats,
     QuicPacketCount initial_congestion_window) {
   const QuicPacketCount max_congestion_window =
-      (kDefaultSocketReceiveBuffer * (FLAGS_quic_use_conservative_receive_buffer
-                                          ? kConservativeReceiveBufferFraction
-                                          : kUsableRecieveBufferFraction)) /
+      (kDefaultSocketReceiveBuffer * kConservativeReceiveBufferFraction) /
       kDefaultTCPMSS;
   switch (congestion_control_type) {
     case kCubic:
diff --git a/net/quic/congestion_control/tcp_cubic_bytes_sender.cc b/net/quic/congestion_control/tcp_cubic_bytes_sender.cc
index 9f15e9f..c123fd2 100644
--- a/net/quic/congestion_control/tcp_cubic_bytes_sender.cc
+++ b/net/quic/congestion_control/tcp_cubic_bytes_sender.cc
@@ -10,6 +10,7 @@
 #include "net/quic/congestion_control/rtt_stats.h"
 #include "net/quic/crypto/crypto_protocol.h"
 #include "net/quic/proto/cached_network_parameters.pb.h"
+#include "net/quic/quic_flags.h"
 
 using std::max;
 using std::min;
@@ -297,8 +298,11 @@ void TcpCubicBytesSender::MaybeIncreaseCwnd(
     QuicByteCount bytes_in_flight) {
   LOG_IF(DFATAL, InRecovery()) << "Never increase the CWND during recovery.";
   if (!IsCwndLimited(bytes_in_flight)) {
-    // We don't update the congestion window unless we are close to using the
-    // window we have available.
+    // Do not increase the congestion window unless the sender is close to using
+    // the current window.
+    if (FLAGS_reset_cubic_epoch_when_app_limited) {
+      cubic_.OnApplicationLimited();
+    }
     return;
   }
   if (congestion_window_ >= max_congestion_window_) {
diff --git a/net/quic/congestion_control/tcp_cubic_bytes_sender_test.cc b/net/quic/congestion_control/tcp_cubic_bytes_sender_test.cc
index dbc9a73..ff30bb5 100644
--- a/net/quic/congestion_control/tcp_cubic_bytes_sender_test.cc
+++ b/net/quic/congestion_control/tcp_cubic_bytes_sender_test.cc
@@ -11,10 +11,12 @@
 #include "net/quic/congestion_control/rtt_stats.h"
 #include "net/quic/crypto/crypto_protocol.h"
 #include "net/quic/proto/cached_network_parameters.pb.h"
+#include "net/quic/quic_flags.h"
 #include "net/quic/quic_protocol.h"
 #include "net/quic/quic_utils.h"
 #include "net/quic/test_tools/mock_clock.h"
 #include "net/quic/test_tools/quic_config_peer.h"
+#include "net/quic/test_tools/quic_test_utils.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace net {
@@ -402,6 +404,46 @@ TEST_F(TcpCubicBytesSenderTest, RetransmissionDelay) {
       sender_->BandwidthEstimate().ToBytesPerSecond());
 }
 
+TEST_F(TcpCubicBytesSenderTest, TcpCubicResetEpochOnQuiescence) {
+  ValueRestore<bool> old_flag(&FLAGS_reset_cubic_epoch_when_app_limited, true);
+  const int kMaxCongestionWindow = 50;
+  const QuicByteCount kMaxCongestionWindowBytes =
+      kMaxCongestionWindow * kDefaultTCPMSS;
+  int num_sent = SendAvailableSendWindow();
+
+  // Make sure we fall out of slow start.
+  QuicByteCount saved_cwnd = sender_->GetCongestionWindow();
+  LoseNPackets(1);
+  EXPECT_GT(saved_cwnd, sender_->GetCongestionWindow());
+
+  // Ack the rest of the outstanding packets to get out of recovery.
+  for (int i = 1; i < num_sent; ++i) {
+    AckNPackets(1);
+  }
+  EXPECT_EQ(0u, bytes_in_flight_);
+
+  // Send a new window of data and ack all; cubic growth should occur.
+  saved_cwnd = sender_->GetCongestionWindow();
+  num_sent = SendAvailableSendWindow();
+  for (int i = 0; i < num_sent; ++i) {
+    AckNPackets(1);
+  }
+  EXPECT_LT(saved_cwnd, sender_->GetCongestionWindow());
+  EXPECT_GT(kMaxCongestionWindowBytes, sender_->GetCongestionWindow());
+  EXPECT_EQ(0u, bytes_in_flight_);
+
+  // Quiescent time of 100 seconds
+  clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(100000));
+
+  // Send new window of data and ack one packet. Cubic epoch should have
+  // been reset; ensure cwnd increase is not dramatic.
+  saved_cwnd = sender_->GetCongestionWindow();
+  SendAvailableSendWindow();
+  AckNPackets(1);
+  EXPECT_NEAR(saved_cwnd, sender_->GetCongestionWindow(), kDefaultTCPMSS);
+  EXPECT_GT(kMaxCongestionWindowBytes, sender_->GetCongestionWindow());
+}
+
 TEST_F(TcpCubicBytesSenderTest, MultipleLossesInOneWindow) {
   SendAvailableSendWindow();
   const QuicByteCount initial_window = sender_->GetCongestionWindow();
diff --git a/net/quic/crypto/crypto_protocol.h b/net/quic/crypto/crypto_protocol.h
index 11b6567..a518b00 100644
--- a/net/quic/crypto/crypto_protocol.h
+++ b/net/quic/crypto/crypto_protocol.h
@@ -102,6 +102,7 @@ const QuicTag kFRTT = TAG('F', 'R', 'T', 'T');
 // Enable bandwidth resumption experiment.
 const QuicTag kBWRE = TAG('B', 'W', 'R', 'E');  // Bandwidth resumption.
 const QuicTag kBWMX = TAG('B', 'W', 'M', 'X');  // Max bandwidth resumption.
+const QuicTag kBWRS = TAG('B', 'W', 'R', 'S');  // Server bandwidth resumption.
 
 // Enable path MTU discovery experiment.
 const QuicTag kMTUH = TAG('M', 'T', 'U', 'H');  // High-target MTU discovery.
@@ -117,7 +118,7 @@ const QuicTag kX59R = TAG('X', '5', '9', 'R');   // X.509 certificate, RSA keys
 const QuicTag kCHID = TAG('C', 'H', 'I', 'D');   // Channel ID.
 
 // Client hello tags
-const QuicTag kVER  = TAG('V', 'E', 'R', '\0');  // Version (new)
+const QuicTag kVER  = TAG('V', 'E', 'R', '\0');  // Version
 const QuicTag kNONC = TAG('N', 'O', 'N', 'C');   // The client's nonce
 const QuicTag kKEXS = TAG('K', 'E', 'X', 'S');   // Key exchange methods
 const QuicTag kAEAD = TAG('A', 'E', 'A', 'D');   // Authenticated
diff --git a/net/quic/crypto/quic_crypto_client_config.h b/net/quic/crypto/quic_crypto_client_config.h
index 4eb4caf..5df8403 100644
--- a/net/quic/crypto/quic_crypto_client_config.h
+++ b/net/quic/crypto/quic_crypto_client_config.h
@@ -132,8 +132,8 @@ class NET_EXPORT_PRIVATE QuicCryptoClientConfig : public QuicCryptoConfig {
     bool has_server_nonce() const;
 
     // This function should only be called when has_server_nonce is true.
-    // Returns the next connection_id specified by the server and removes it
-    // from the queue of ids.
+    // Returns the next server_nonce specified by the server and removes it
+    // from the queue of nonces.
     std::string GetNextServerNonce();
 
     // SetProofVerifyDetails takes ownership of |details|.
diff --git a/net/quic/interval.h b/net/quic/interval.h
new file mode 100644
index 0000000..070a260
--- /dev/null
+++ b/net/quic/interval.h
@@ -0,0 +1,360 @@
+// Copyright 2015 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.
+//
+// An Interval<T> is a data structure used to represent a contiguous, mutable
+// range over an ordered type T. Supported operations include testing a value to
+// see whether it is included in the interval, comparing two intervals, and
+// performing their union, intersection, and difference. For the purposes of
+// this library, an "ordered type" is any type that induces a total order on its
+// values via its less-than operator (operator<()). Examples of such types are
+// basic arithmetic types like int and double as well as class types like
+// string.
+//
+// An Interval<T> is represented using the usual C++ STL convention, namely as
+// the half-open interval [min, max). A point p is considered to be contained in
+// the interval iff p >= min && p < max. One consequence of this definition is
+// that for any non-empty interval, min is contained in the interval but max is
+// not. There is no canonical representation for the empty interval; rather, any
+// interval where max <= min is regarded as empty. As a consequence, two empty
+// intervals will still compare as equal despite possibly having different
+// underlying min() or max() values. Also beware of the terminology used here:
+// the library uses the terms "min" and "max" rather than "begin" and "end" as
+// is conventional for the STL.
+//
+// T is required to be default- and copy-constructable, to have an assignment
+// operator, and the full complement of comparison operators (<, <=, ==, !=, >=,
+// >).  A difference operator (operator-()) is required if Interval<T>::Length
+// is used.
+//
+// For equality comparisons, Interval<T> supports an Equals() method and an
+// operator==() which delegates to it. Two intervals are considered equal if
+// either they are both empty or if their corresponding min and max fields
+// compare equal. For ordered comparisons, Interval<T> also provides the
+// comparator Interval<T>::Less and an operator<() which delegates to it.
+// Unfortunately this comparator is currently buggy because its behavior is
+// inconsistent with Equals(): two empty ranges with different representations
+// may be regarded as equivalent by Equals() but regarded as different by
+// the comparator. Bug 9240050 has been created to address this.
+//
+// This class is thread-compatible if T is thread-compatible. (See
+// go/thread-compatible).
+//
+// Examples:
+//   Interval<int> r1(0, 100);  // The interval [0, 100).
+//   EXPECT_TRUE(r1.Contains(0));
+//   EXPECT_TRUE(r1.Contains(50));
+//   EXPECT_FALSE(r1.Contains(100));  // 100 is just outside the interval.
+//
+//   Interval<int> r2(50, 150);  // The interval [50, 150).
+//   EXPECT_TRUE(r1.Intersects(r2));
+//   EXPECT_FALSE(r1.Contains(r2));
+//   EXPECT_TRUE(r1.IntersectWith(r2));  // Mutates r1.
+//   EXPECT_EQ(Interval<int>(50, 100), r1);  // r1 is now [50, 100).
+//
+//   Interval<int> r3(1000, 2000);  // The interval [1000, 2000).
+//   EXPECT_TRUE(r1.IntersectWith(r3));  // Mutates r1.
+//   EXPECT_TRUE(r1.Empty());  // Now r1 is empty.
+//   EXPECT_FALSE(r1.Contains(r1.min()));  // e.g. doesn't contain its own min.
+
+#ifndef NET_QUIC_INTERVAL_H_
+#define NET_QUIC_INTERVAL_H_
+
+#include <stddef.h>
+#include <algorithm>
+#include <ostream>
+#include <string>
+#include <utility>
+#include <vector>
+
+namespace net {
+
+template <typename T>
+class Interval {
+ private:
+// TODO(rtenneti): Implement after suupport for std::decay.
+#if 0
+  // Type trait for deriving the return type for Interval::Length.  If
+  // operator-() is not defined for T, then the return type is void.  This makes
+  // the signature for Length compile so that the class can be used for such T,
+  // but code that calls Length would still generate a compilation error.
+  template <typename U>
+  class DiffTypeOrVoid {
+   private:
+    template <typename V>
+    static auto f(const V* v) -> decltype(*v - *v);
+    template <typename V>
+    static void f(...);
+
+   public:
+    using type = typename std::decay<decltype(f<U>(0))>::type;
+  };
+#endif
+
+ public:
+  // Compatibility alias.
+  using Less = std::less<Interval>;
+
+  // Construct an Interval representing an empty interval.
+  Interval() : min_(), max_() {}
+
+  // Construct an Interval representing the interval [min, max). If min < max,
+  // the constructed object will represent the non-empty interval containing all
+  // values from min up to (but not including) max. On the other hand, if min >=
+  // max, the constructed object will represent the empty interval.
+  Interval(const T& min, const T& max) : min_(min), max_(max) {}
+
+  const T& min() const { return min_; }
+  const T& max() const { return max_; }
+  void SetMin(const T& t) { min_ = t; }
+  void SetMax(const T& t) { max_ = t; }
+
+  void Set(const T& min, const T& max) {
+    SetMin(min);
+    SetMax(max);
+  }
+
+  void Clear() { *this = {}; }
+  void CopyFrom(const Interval& i) { *this = i; }
+  bool Equals(const Interval& i) const { return *this == i; }
+  bool Empty() const { return min() >= max(); }
+
+  // Returns the length of this interval. The value returned is zero if
+  // IsEmpty() is true; otherwise the value returned is max() - min().
+  const T Length() const { return (min_ >= max_ ? min_ : max_) - min_; }
+
+  // Returns true iff t >= min() && t < max().
+  bool Contains(const T& t) const { return min() <= t && max() > t; }
+
+  // Returns true iff *this and i are non-empty, and *this includes i. "*this
+  // includes i" means that for all t, if i.Contains(t) then this->Contains(t).
+  // Note the unintuitive consequence of this definition: this method always
+  // returns false when i is the empty interval.
+  bool Contains(const Interval& i) const {
+    return !Empty() && !i.Empty() && min() <= i.min() && max() >= i.max();
+  }
+
+  // Returns true iff there exists some point t for which this->Contains(t) &&
+  // i.Contains(t) evaluates to true, i.e. if the intersection is non-empty.
+  bool Intersects(const Interval& i) const {
+    return !Empty() && !i.Empty() && min() < i.max() && max() > i.min();
+  }
+
+  // Returns true iff there exists some point t for which this->Contains(t) &&
+  // i.Contains(t) evaluates to true, i.e. if the intersection is non-empty.
+  // Furthermore, if the intersection is non-empty and the intersection pointer
+  // is not null, this method stores the calculated intersection in
+  // *intersection.
+  bool Intersects(const Interval& i, Interval* out) const;
+
+  // Sets *this to be the intersection of itself with i. Returns true iff
+  // *this was modified.
+  bool IntersectWith(const Interval& i);
+
+  // Calculates the smallest interval containing both *this i, and updates *this
+  // to represent that interval, and returns true iff *this was modified.
+  bool SpanningUnion(const Interval& i);
+
+  // Determines the difference between two intervals by finding all points that
+  // are contained in *this but not in i, coalesces those points into the
+  // largest possible contiguous intervals, and appends those intervals to the
+  // *difference vector. Intuitively this can be thought of as "erasing" i from
+  // *this. This will either completely erase *this (leaving nothing behind),
+  // partially erase some of *this from the left or right side (leaving some
+  // residual behind), or erase a hole in the middle of *this (leaving behind an
+  // interval on either side). Therefore, 0, 1, or 2 intervals will be appended
+  // to *difference. The method returns true iff the intersection of *this and i
+  // is non-empty. The caller owns the vector and the Interval* pointers
+  // inside it. The difference vector is required to be non-null.
+  bool Difference(const Interval& i, std::vector<Interval*>* difference) const;
+
+  // Determines the difference between two intervals as in
+  // Difference(Interval&, vector*), but stores the results directly in out
+  // parameters rather than dynamically allocating an Interval* and appending
+  // it to a vector. If two results are generated, the one with the smaller
+  // value of min() will be stored in *lo and the other in *hi. Otherwise (if
+  // fewer than two results are generated), unused arguments will be set to the
+  // empty interval (it is possible that *lo will be empty and *hi non-empty).
+  // The method returns true iff the intersection of *this and i is non-empty.
+  bool Difference(const Interval& i, Interval* lo, Interval* hi) const;
+
+  friend bool operator==(const Interval& a, const Interval& b) {
+    bool ae = a.Empty();
+    bool be = b.Empty();
+    if (ae && be)
+      return true;  // All empties are equal.
+    if (ae != be)
+      return false;  // Empty cannot equal nonempty.
+    return a.min() == b.min() && a.max() == b.max();
+  }
+
+  friend bool operator!=(const Interval& a, const Interval& b) {
+    return !(a == b);
+  }
+
+  // Defines a comparator which can be used to induce an order on Intervals, so
+  // that, for example, they can be stored in an ordered container such as
+  // std::set. The ordering is arbitrary, but does provide the guarantee that,
+  // for non-empty intervals X and Y, if X contains Y, then X <= Y.
+  // TODO(kosak): The current implementation of this comparator has a problem
+  // because the ordering it induces is inconsistent with that of Equals(). In
+  // particular, this comparator does not properly consider all empty intervals
+  // equivalent. Bug b/9240050 has been created to track this.
+  friend bool operator<(const Interval& a, const Interval& b) {
+    return a.min() < b.min() || (a.min() == b.min() && a.max() > b.max());
+  }
+
+  friend std::ostream& operator<<(std::ostream& out, const Interval& i) {
+    return out << "[" << i.min() << ", " << i.max() << ")";
+  }
+
+ private:
+  T min_;  // Inclusive lower bound.
+  T max_;  // Exclusive upper bound.
+};
+
+//==============================================================================
+// Implementation details: Clients can stop reading here.
+
+template <typename T>
+bool Interval<T>::Intersects(const Interval& i, Interval* out) const {
+  if (!Intersects(i))
+    return false;
+  if (out != nullptr) {
+    *out = Interval(std::max(min(), i.min()), std::min(max(), i.max()));
+  }
+  return true;
+}
+
+template <typename T>
+bool Interval<T>::IntersectWith(const Interval& i) {
+  if (Empty())
+    return false;
+  bool modified = false;
+  if (i.min() > min()) {
+    SetMin(i.min());
+    modified = true;
+  }
+  if (i.max() < max()) {
+    SetMax(i.max());
+    modified = true;
+  }
+  return modified;
+}
+
+template <typename T>
+bool Interval<T>::SpanningUnion(const Interval& i) {
+  if (i.Empty())
+    return false;
+  if (Empty()) {
+    *this = i;
+    return true;
+  }
+  bool modified = false;
+  if (i.min() < min()) {
+    SetMin(i.min());
+    modified = true;
+  }
+  if (i.max() > max()) {
+    SetMax(i.max());
+    modified = true;
+  }
+  return modified;
+}
+
+template <typename T>
+bool Interval<T>::Difference(const Interval& i,
+                             std::vector<Interval*>* difference) const {
+  if (Empty()) {
+    // <empty> - <i> = <empty>
+    return false;
+  }
+  if (i.Empty()) {
+    // <this> - <empty> = <this>
+    difference->push_back(new Interval(*this));
+    return false;
+  }
+  if (min() < i.max() && min() >= i.min() && max() > i.max()) {
+    //            [------ this ------)
+    // [------ i ------)
+    //                 [-- result ---)
+    difference->push_back(new Interval(i.max(), max()));
+    return true;
+  }
+  if (max() > i.min() && max() <= i.max() && min() < i.min()) {
+    // [------ this ------)
+    //            [------ i ------)
+    // [- result -)
+    difference->push_back(new Interval(min(), i.min()));
+    return true;
+  }
+  if (min() < i.min() && max() > i.max()) {
+    // [------- this --------)
+    //      [---- i ----)
+    // [ R1 )           [ R2 )
+    // There are two results: R1 and R2.
+    difference->push_back(new Interval(min(), i.min()));
+    difference->push_back(new Interval(i.max(), max()));
+    return true;
+  }
+  if (min() >= i.min() && max() <= i.max()) {
+    //   [--- this ---)
+    // [------ i --------)
+    // Intersection is <this>, so difference yields the empty interval.
+    // Nothing is appended to *difference.
+    return true;
+  }
+  // No intersection. Append <this>.
+  difference->push_back(new Interval(*this));
+  return false;
+}
+
+template <typename T>
+bool Interval<T>::Difference(const Interval& i,
+                             Interval* lo,
+                             Interval* hi) const {
+  // Initialize *lo and *hi to empty
+  *lo = {};
+  *hi = {};
+  if (Empty())
+    return false;
+  if (i.Empty()) {
+    *lo = *this;
+    return false;
+  }
+  if (min() < i.max() && min() >= i.min() && max() > i.max()) {
+    //            [------ this ------)
+    // [------ i ------)
+    //                 [-- result ---)
+    *hi = Interval(i.max(), max());
+    return true;
+  }
+  if (max() > i.min() && max() <= i.max() && min() < i.min()) {
+    // [------ this ------)
+    //            [------ i ------)
+    // [- result -)
+    *lo = Interval(min(), i.min());
+    return true;
+  }
+  if (min() < i.min() && max() > i.max()) {
+    // [------- this --------)
+    //      [---- i ----)
+    // [ R1 )           [ R2 )
+    // There are two results: R1 and R2.
+    *lo = Interval(min(), i.min());
+    *hi = Interval(i.max(), max());
+    return true;
+  }
+  if (min() >= i.min() && max() <= i.max()) {
+    //   [--- this ---)
+    // [------ i --------)
+    // Intersection is <this>, so difference yields the empty interval.
+    return true;
+  }
+  *lo = *this;  // No intersection.
+  return false;
+}
+
+}  // namespace net
+
+#endif  // NET_QUIC_INTERVAL_H_
diff --git a/net/quic/interval_set.h b/net/quic/interval_set.h
new file mode 100644
index 0000000..eae4fd7
--- /dev/null
+++ b/net/quic/interval_set.h
@@ -0,0 +1,856 @@
+// Copyright 2015 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.
+//
+// IntervalSet<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
+// IntervalSet, comparing two IntervalSets, and performing IntervalSet union,
+// intersection, and difference.
+//
+// IntervalSet maintains the minimum number of entries needed to represent the
+// set of underlying intervals. When the IntervalSet 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 Interval<T>.
+//
+// IntervalSet has constant-time move operations.
+//
+// This class is thread-compatible if T is thread-compatible. (See
+// go/thread-compatible).
+//
+// Examples:
+//   IntervalSet<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)));
+
+#ifndef NET_QUIC_INTERVAL_SET_H_
+#define NET_QUIC_INTERVAL_SET_H_
+
+#include <stddef.h>
+#include <algorithm>
+#include <set>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include "base/logging.h"
+#include "net/quic/interval.h"
+
+namespace net {
+
+template <typename T>
+class IntervalSet {
+ private:
+  struct IntervalComparator {
+    bool operator()(const Interval<T>& a, const Interval<T>& b) const;
+  };
+  typedef std::set<Interval<T>, IntervalComparator> Set;
+
+ public:
+  typedef typename Set::value_type value_type;
+  typedef typename Set::const_iterator const_iterator;
+  typedef typename Set::const_reverse_iterator const_reverse_iterator;
+
+  // Instantiates an empty IntervalSet.
+  IntervalSet() {}
+
+  // Instantiates an IntervalSet containing exactly one initial half-open
+  // interval [min, max), unless the given interval is empty, in which case the
+  // IntervalSet will be empty.
+  explicit IntervalSet(const Interval<T>& interval) { Add(interval); }
+
+  // Instantiates an IntervalSet containing the half-open interval [min, max).
+  IntervalSet(const T& min, const T& max) { Add(min, max); }
+
+// TODO(rtenneti): Implement after suupport for std::initializer_list.
+#if 0
+  IntervalSet(std::initializer_list<value_type> il) { assign(il); }
+#endif
+
+  // Clears this IntervalSet.
+  void Clear() { intervals_.clear(); }
+
+  // Returns the number of disjoint intervals contained in this IntervalSet.
+  size_t Size() const { return intervals_.size(); }
+
+  // Returns the smallest interval that contains all intervals in this
+  // IntervalSet, or the empty interval if the set is empty.
+  Interval<T> SpanningInterval() const;
+
+  // Adds "interval" to this IntervalSet. Adding the empty interval has no
+  // effect.
+  void Add(const Interval<T>& interval);
+
+  // Adds the interval [min, max) to this IntervalSet. Adding the empty interval
+  // has no effect.
+  void Add(const T& min, const T& max) { Add(Interval<T>(min, max)); }
+
+  // DEPRECATED(kosak). Use Union() instead. This method merges all of the
+  // values contained in "other" into this IntervalSet.
+  void Add(const IntervalSet& other);
+
+  // Returns true if this IntervalSet represents exactly the same set of
+  // intervals as the ones represented by "other".
+  bool Equals(const IntervalSet& other) const;
+
+  // Returns true if this IntervalSet is empty.
+  bool Empty() const { return intervals_.empty(); }
+
+  // Returns true if any interval in this IntervalSet contains the indicated
+  // value.
+  bool Contains(const T& value) const;
+
+  // Returns true if there is some interval in this IntervalSet 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 Interval<T>::Contains(). This method returns false on
+  // the empty interval, due to a (perhaps unintuitive) convention inherited
+  // from Interval<T>.
+  // Example:
+  //   Assume an IntervalSet 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 Interval<T>& interval) const;
+
+  // Returns true if for each interval in "other", there is some (possibly
+  // different) interval in this IntervalSet which wholly contains it. See
+  // Contains(const Interval<T>& 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())), which is not efficient. The method could be rewritten
+  // to run in O(other.Size() + this->Size()).
+  bool Contains(const IntervalSet<T>& other) const;
+
+  // Returns true if there is some interval in this IntervalSet that wholly
+  // contains the interval [min, max). See Contains(const Interval<T>&).
+  bool Contains(const T& min, const T& max) const {
+    return Contains(Interval<T>(min, max));
+  }
+
+  // Returns true if for some interval in "other", there is some interval in
+  // this IntervalSet that intersects with it. See Interval<T>::Intersects()
+  // for the definition of interval intersection.
+  bool Intersects(const IntervalSet& other) const;
+
+  // Returns an iterator to the Interval<T> in the IntervalSet that contains the
+  // given value. In other words, returns an iterator to the unique interval
+  // [min, max) in the IntervalSet 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 Interval<T> in the IntervalSet that wholly
+  // contains the given interval. In other words, returns an iterator to the
+  // unique interval outer in the IntervalSet 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 Interval<T>& interval) const;
+
+  // Returns an iterator to the Interval<T> in the IntervalSet that wholly
+  // contains [min, max). In other words, returns an iterator to the unique
+  // interval outer in the IntervalSet 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(Interval<T>(min, max));
+  }
+
+  // Returns true if every value within the passed interval is not Contained
+  // within the IntervalSet.
+  bool IsDisjoint(const Interval<T>& interval) const;
+
+  // Merges all the values contained in "other" into this IntervalSet.
+  void Union(const IntervalSet& other);
+
+  // Modifies this IntervalSet so that it contains only those values that are
+  // currently present both in *this and in the IntervalSet "other".
+  void Intersection(const IntervalSet& other);
+
+  // Mutates this IntervalSet so that it contains only those values that are
+  // currently in *this but not in "interval".
+  void Difference(const Interval<T>& interval);
+
+  // Mutates this IntervalSet 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 IntervalSet so that it contains only those values that are
+  // currently in *this but not in the IntervalSet "other".
+  void Difference(const IntervalSet& other);
+
+  // Mutates this IntervalSet 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);
+
+  // IntervalSet's begin() iterator. The invariants of IntervalSet 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 IntervalSet invalidate these
+  // iterators.
+  const_iterator begin() const { return intervals_.begin(); }
+
+  // IntervalSet's end() iterator.
+  const_iterator end() const { return intervals_.end(); }
+
+  // IntervalSet'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(); }
+
+  // Appends the intervals in this IntervalSet to the end of *out.
+  void Get(std::vector<Interval<T>>* out) const {
+    out->insert(out->end(), begin(), end());
+  }
+
+  // Copies the intervals in this IntervalSet to the given output iterator.
+  template <typename Iter>
+  Iter Get(Iter out_iter) const {
+    return std::copy(begin(), end(), out_iter);
+  }
+
+  template <typename Iter>
+  void assign(Iter first, Iter last) {
+    Clear();
+    for (; first != last; ++first)
+      Add(*first);
+  }
+
+// TODO(rtenneti): Implement after suupport for std::initializer_list.
+#if 0
+  void assign(std::initializer_list<value_type> il) {
+    assign(il.begin(), il.end());
+  }
+#endif
+
+  // 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;
+
+  // Equality for IntervalSet<T>. Delegates to Equals().
+  bool operator==(const IntervalSet& other) const { return Equals(other); }
+
+  // Inequality for IntervalSet<T>. Delegates to Equals() (and returns its
+  // negation).
+  bool operator!=(const IntervalSet& other) const { return !Equals(other); }
+
+// TODO(rtenneti): Implement after suupport for std::initializer_list.
+#if 0
+  IntervalSet& operator=(std::initializer_list<value_type> il) {
+    assign(il.begin(), il.end());
+    return *this;
+  }
+#endif
+
+  // Swap this IntervalSet with *other. This is a constant-time operation.
+  void Swap(IntervalSet<T>* other) { intervals_.swap(other->intervals_); }
+
+ private:
+  // 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 DCHECK).
+  bool Valid() const;
+
+  // Finds the first interval that potentially intersects 'other'.
+  const_iterator FindIntersectionCandidate(const IntervalSet& other) const;
+
+  // Finds the first interval that potentially intersects 'interval'.
+  const_iterator FindIntersectionCandidate(const Interval<T>& 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 IntervalSet& y,
+                                           const_iterator* mine,
+                                           const_iterator* theirs,
+                                           Func on_hole);
+
+  // The variant of the above method that doesn't mutate this IntervalSet.
+  bool FindNextIntersectingPair(const IntervalSet& other,
+                                const_iterator* mine,
+                                const_iterator* theirs) const {
+    return FindNextIntersectingPairImpl(
+        this, other, mine, theirs,
+        [](const IntervalSet*, const_iterator, const_iterator) {});
+  }
+
+  // The variant of the above method that mutates this IntervalSet by erasing
+  // holes.
+  bool FindNextIntersectingPairAndEraseHoles(const IntervalSet& other,
+                                             const_iterator* mine,
+                                             const_iterator* theirs) {
+    return FindNextIntersectingPairImpl(
+        this, other, mine, theirs,
+        [](IntervalSet* 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>
+std::ostream& operator<<(std::ostream& out, const IntervalSet<T>& seq);
+
+template <typename T>
+void swap(IntervalSet<T>& x, IntervalSet<T>& y);
+
+//==============================================================================
+// Implementation details: Clients can stop reading here.
+
+template <typename T>
+Interval<T> IntervalSet<T>::SpanningInterval() const {
+  Interval<T> result;
+  if (!intervals_.empty()) {
+    result.SetMin(intervals_.begin()->min());
+    result.SetMax(intervals_.rbegin()->max());
+  }
+  return result;
+}
+
+template <typename T>
+void IntervalSet<T>::Add(const Interval<T>& 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 IntervalSet 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 Interval<T> target_end(interval.max(), interval.max());
+  const typename Set::iterator end = intervals_.upper_bound(target_end);
+  Compact(begin, end);
+}
+
+template <typename T>
+void IntervalSet<T>::Add(const IntervalSet& other) {
+  for (const_iterator it = other.begin(); it != other.end(); ++it) {
+    Add(*it);
+  }
+}
+
+template <typename T>
+bool IntervalSet<T>::Equals(const IntervalSet& other) const {
+  if (intervals_.size() != other.intervals_.size())
+    return false;
+  for (typename Set::iterator i = intervals_.begin(),
+                              j = other.intervals_.begin();
+       i != intervals_.end(); ++i, ++j) {
+    // Simple member-wise equality, since all intervals are non-empty.
+    if (i->min() != j->min() || i->max() != j->max())
+      return false;
+  }
+  return true;
+}
+
+template <typename T>
+bool IntervalSet<T>::Contains(const T& value) const {
+  Interval<T> 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 IntervalSet<T>::Contains(const Interval<T>& 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 IntervalSet<T>::Contains(const IntervalSet<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 IntervalSet. 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 IntervalSet 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 IntervalSet 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 IntervalSet<T>::const_iterator IntervalSet<T>::Find(
+    const T& value) const {
+  Interval<T> 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 IntervalSet. 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 IntervalSet 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 IntervalSet<T>::const_iterator IntervalSet<T>::Find(
+    const Interval<T>& 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>
+bool IntervalSet<T>::IsDisjoint(const Interval<T>& interval) const {
+  Interval<T> 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 IntervalSet<T>::Union(const IntervalSet& other) {
+  intervals_.insert(other.begin(), other.end());
+  Compact(intervals_.begin(), intervals_.end());
+}
+
+template <typename T>
+typename IntervalSet<T>::const_iterator
+IntervalSet<T>::FindIntersectionCandidate(const IntervalSet& other) const {
+  return FindIntersectionCandidate(*other.intervals_.begin());
+}
+
+template <typename T>
+typename IntervalSet<T>::const_iterator
+IntervalSet<T>::FindIntersectionCandidate(const Interval<T>& 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 IntervalSet<T>::FindNextIntersectingPairImpl(X* x,
+                                                  const IntervalSet& y,
+                                                  const_iterator* mine,
+                                                  const_iterator* theirs,
+                                                  Func on_hole) {
+  CHECK(x != nullptr);
+  if ((*mine == x->intervals_.end()) || (*theirs == y.intervals_.end())) {
+    return false;
+  }
+  while (!(**mine).Intersects(**theirs)) {
+    const_iterator erase_first = *mine;
+    // Skip over intervals in 'mine' that don't reach 'theirs'.
+    while (*mine != x->intervals_.end() && (**mine).max() <= (**theirs).min()) {
+      ++(*mine);
+    }
+    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 IntervalSet<T>::Intersection(const IntervalSet& 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.
+    Interval<T> i(*mine);
+    intervals_.erase(mine);
+    mine = intervals_.end();
+    Interval<T> intersection;
+    while (theirs != other.intervals_.end() &&
+           i.Intersects(*theirs, &intersection)) {
+      std::pair<typename Set::iterator, bool> ins =
+          intervals_.insert(intersection);
+      DCHECK(ins.second);
+      mine = ins.first;
+      ++theirs;
+    }
+    DCHECK(mine != intervals_.end());
+    --theirs;
+    ++mine;
+  }
+  DCHECK(Valid());
+}
+
+template <typename T>
+bool IntervalSet<T>::Intersects(const IntervalSet& 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 IntervalSet<T>::Difference(const Interval<T>& interval) {
+  if (!SpanningInterval().Intersects(interval)) {
+    return;
+  }
+  Difference(IntervalSet<T>(interval));
+}
+
+template <typename T>
+void IntervalSet<T>::Difference(const T& min, const T& max) {
+  Difference(Interval<T>(min, max));
+}
+
+template <typename T>
+void IntervalSet<T>::Difference(const IntervalSet& 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.
+    Interval<T> i(*mine);
+    intervals_.erase(mine++);
+    Interval<T> lo;
+    Interval<T> 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);
+      DCHECK(ins.second);
+    }
+
+    if (!hi.Empty()) {
+      std::pair<typename Set::iterator, bool> ins = intervals_.insert(hi);
+      DCHECK(ins.second);
+      mine = ins.first;
+    }
+  }
+  DCHECK(Valid());
+}
+
+template <typename T>
+void IntervalSet<T>::Complement(const T& min, const T& max) {
+  IntervalSet<T> span(min, max);
+  span.Difference(*this);
+  intervals_.swap(span.intervals_);
+}
+
+template <typename T>
+std::string IntervalSet<T>::ToString() const {
+  std::ostringstream os;
+  os << *this;
+  return os.str();
+}
+
+// This method compacts the IntervalSet, merging pairs of overlapping intervals
+// into a single interval. In the steady state, the IntervalSet does not contain
+// any such pairs. However, the way the Union() and Add() methods work is to
+// temporarily put the IntervalSet 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 IntervalSet
+// does exactly what is needed, ordering first by ascending min(), then by
+// descending max().
+template <typename T>
+void IntervalSet<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());
+      Interval<T> i(min, max);
+      intervals_.erase(prev);
+      intervals_.erase(it);
+      std::pair<typename Set::iterator, bool> ins = intervals_.insert(i);
+      DCHECK(ins.second);
+      prev = ins.first;
+    } else {
+      prev = it;
+    }
+    it = next;
+  }
+}
+
+template <typename T>
+bool IntervalSet<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;
+}
+
+template <typename T>
+inline std::ostream& operator<<(std::ostream& out, const IntervalSet<T>& seq) {
+// TODO(rtenneti): Implement << method of IntervalSet.
+#if 0
+  util::gtl::LogRangeToStream(out, seq.begin(), seq.end(),
+                              util::gtl::LogLegacy());
+#endif  // 0
+  return out;
+}
+
+template <typename T>
+void swap(IntervalSet<T>& x, IntervalSet<T>& y) {
+  x.Swap(&y);
+}
+
+// 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 IntervalSet
+// 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>
+inline bool IntervalSet<T>::IntervalComparator::operator()(
+    const Interval<T>& a,
+    const Interval<T>& b) const {
+  return (a.min() < b.min() || (a.min() == b.min() && a.max() > b.max()));
+}
+
+}  // namespace net
+
+#endif  // NET_QUIC_INTERVAL_SET_H_
diff --git a/net/quic/interval_set_test.cc b/net/quic/interval_set_test.cc
new file mode 100644
index 0000000..e3c351f
--- /dev/null
+++ b/net/quic/interval_set_test.cc
@@ -0,0 +1,983 @@
+// Copyright 2015 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.
+
+#include "net/quic/interval_set.h"
+
+#include <stdarg.h>
+#include <algorithm>
+#include <iostream>
+#include <iterator>
+#include <limits>
+#include <vector>
+
+#include "base/logging.h"
+#include "net/test/gtest_util.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+using std::pair;
+using std::string;
+using std::vector;
+
+namespace net {
+namespace test {
+namespace {
+
+using ::testing::ElementsAreArray;
+
+class IntervalSetTest : public ::testing::Test {
+ protected:
+  void SetUp() override {
+    // Initialize two IntervalSets for union, intersection, and difference
+    // tests
+    is.Add(100, 200);
+    is.Add(300, 400);
+    is.Add(500, 600);
+    is.Add(700, 800);
+    is.Add(900, 1000);
+    is.Add(1100, 1200);
+    is.Add(1300, 1400);
+    is.Add(1500, 1600);
+    is.Add(1700, 1800);
+    is.Add(1900, 2000);
+    is.Add(2100, 2200);
+
+    // Lots of different cases:
+    other.Add(50, 70);      // disjoint, at the beginning
+    other.Add(2250, 2270);  // disjoint, at the end
+    other.Add(650, 670);    // disjoint, in the middle
+    other.Add(350, 360);    // included
+    other.Add(370, 380);    // also included (two at once)
+    other.Add(470, 530);    // overlaps low end
+    other.Add(770, 830);    // overlaps high end
+    other.Add(870, 900);    // meets at low end
+    other.Add(1200, 1230);  // meets at high end
+    other.Add(1270, 1830);  // overlaps multiple ranges
+  }
+
+  void TearDown() override {
+    is.Clear();
+    EXPECT_TRUE(is.Empty());
+    other.Clear();
+    EXPECT_TRUE(other.Empty());
+  }
+  IntervalSet<int> is;
+  IntervalSet<int> other;
+};
+
+TEST_F(IntervalSetTest, IsDisjoint) {
+  EXPECT_TRUE(is.IsDisjoint(Interval<int>(0, 99)));
+  EXPECT_TRUE(is.IsDisjoint(Interval<int>(0, 100)));
+  EXPECT_TRUE(is.IsDisjoint(Interval<int>(200, 200)));
+  EXPECT_TRUE(is.IsDisjoint(Interval<int>(200, 299)));
+  EXPECT_TRUE(is.IsDisjoint(Interval<int>(400, 407)));
+  EXPECT_TRUE(is.IsDisjoint(Interval<int>(405, 499)));
+  EXPECT_TRUE(is.IsDisjoint(Interval<int>(2300, 2300)));
+  EXPECT_TRUE(
+      is.IsDisjoint(Interval<int>(2300, std::numeric_limits<int>::max())));
+  EXPECT_FALSE(is.IsDisjoint(Interval<int>(100, 100)));
+  EXPECT_FALSE(is.IsDisjoint(Interval<int>(100, 105)));
+  EXPECT_FALSE(is.IsDisjoint(Interval<int>(199, 300)));
+  EXPECT_FALSE(is.IsDisjoint(Interval<int>(250, 450)));
+  EXPECT_FALSE(is.IsDisjoint(Interval<int>(299, 400)));
+  EXPECT_FALSE(is.IsDisjoint(Interval<int>(250, 2000)));
+  EXPECT_FALSE(
+      is.IsDisjoint(Interval<int>(2199, std::numeric_limits<int>::max())));
+}
+
+// Base helper method for verifying the contents of an interval set.
+// Returns true iff <is> contains <count> intervals whose successive
+// endpoints match the sequence of args in <ap>:
+static bool VA_Check(const IntervalSet<int>& is, size_t count, va_list ap) {
+  vector<Interval<int>> intervals;
+  is.Get(&intervals);
+  if (count != intervals.size()) {
+    LOG(ERROR) << "Expected " << count << " intervals, got " << intervals.size()
+               << ": " << is.ToString();
+    return false;
+  }
+  if (count != is.Size()) {
+    LOG(ERROR) << "Expected " << count << " intervals, got Size " << is.Size()
+               << ": " << is.ToString();
+    return false;
+  }
+  bool result = true;
+  for (size_t i = 0; i < count; i++) {
+    int min = va_arg(ap, int);
+    int max = va_arg(ap, int);
+    if (min != intervals[i].min() || max != intervals[i].max()) {
+      LOG(ERROR) << "Expected: [" << min << ", " << max << ") got "
+                 << intervals[i] << " in " << is.ToString();
+      result = false;
+    }
+  }
+  return result;
+}
+
+static bool Check(const IntervalSet<int>& is, int count, ...) {
+  va_list ap;
+  va_start(ap, count);
+  const bool result = VA_Check(is, count, ap);
+  va_end(ap);
+  return result;
+}
+
+// Some helper functions for testing Contains and Find, which are logically the
+// same.
+static void TestContainsAndFind(const IntervalSet<int>& is, int value) {
+  EXPECT_TRUE(is.Contains(value)) << "Set does not contain " << value;
+  auto it = is.Find(value);
+  EXPECT_NE(it, is.end()) << "No iterator to interval containing " << value;
+  EXPECT_TRUE(it->Contains(value)) << "Iterator does not contain " << value;
+}
+
+static void TestContainsAndFind(const IntervalSet<int>& is, int min, int max) {
+  EXPECT_TRUE(is.Contains(min, max))
+      << "Set does not contain interval with min " << min << "and max " << max;
+  auto it = is.Find(min, max);
+  EXPECT_NE(it, is.end()) << "No iterator to interval with min " << min
+                          << "and max " << max;
+  EXPECT_TRUE(it->Contains(Interval<int>(min, max)))
+      << "Iterator does not contain interval with min " << min << "and max "
+      << max;
+}
+
+static void TestNotContainsAndFind(const IntervalSet<int>& is, int value) {
+  EXPECT_FALSE(is.Contains(value)) << "Set contains " << value;
+  auto it = is.Find(value);
+  EXPECT_EQ(it, is.end()) << "There is iterator to interval containing "
+                          << value;
+}
+
+static void TestNotContainsAndFind(const IntervalSet<int>& is,
+                                   int min,
+                                   int max) {
+  EXPECT_FALSE(is.Contains(min, max)) << "Set contains interval with min "
+                                      << min << "and max " << max;
+  auto it = is.Find(min, max);
+  EXPECT_EQ(it, is.end()) << "There is iterator to interval with min " << min
+                          << "and max " << max;
+}
+
+TEST_F(IntervalSetTest, IntervalSetBasic) {
+  // Test Add, Get, Contains and Find
+  IntervalSet<int> iset;
+  EXPECT_TRUE(iset.Empty());
+  EXPECT_EQ(0u, iset.Size());
+  iset.Add(100, 200);
+  EXPECT_FALSE(iset.Empty());
+  EXPECT_EQ(1u, iset.Size());
+  iset.Add(100, 150);
+  iset.Add(150, 200);
+  iset.Add(130, 170);
+  iset.Add(90, 150);
+  iset.Add(170, 220);
+  iset.Add(300, 400);
+  iset.Add(250, 450);
+  EXPECT_FALSE(iset.Empty());
+  EXPECT_EQ(2u, iset.Size());
+  EXPECT_TRUE(Check(iset, 2, 90, 220, 250, 450));
+
+  // Test two intervals with a.max == b.min, that will just join up.
+  iset.Clear();
+  iset.Add(100, 200);
+  iset.Add(200, 300);
+  EXPECT_FALSE(iset.Empty());
+  EXPECT_EQ(1u, iset.Size());
+  EXPECT_TRUE(Check(iset, 1, 100, 300));
+
+  // Test adding two sets together.
+  iset.Clear();
+  IntervalSet<int> iset_add;
+  iset.Add(100, 200);
+  iset.Add(100, 150);
+  iset.Add(150, 200);
+  iset.Add(130, 170);
+  iset_add.Add(90, 150);
+  iset_add.Add(170, 220);
+  iset_add.Add(300, 400);
+  iset_add.Add(250, 450);
+
+  iset.Add(iset_add);
+  EXPECT_FALSE(iset.Empty());
+  EXPECT_EQ(2u, iset.Size());
+  EXPECT_TRUE(Check(iset, 2, 90, 220, 250, 450));
+
+  // Test Get() (using an output iterator), begin()/end(), and rbegin()/rend()
+  // to iterate over intervals.
+  {
+    vector<Interval<int>> expected;
+    iset.Get(&expected);
+
+    vector<Interval<int>> actual1;
+    iset.Get(back_inserter(actual1));
+    ASSERT_EQ(expected.size(), actual1.size());
+
+    vector<Interval<int>> actual2;
+    std::copy(iset.begin(), iset.end(), back_inserter(actual2));
+    ASSERT_EQ(expected.size(), actual2.size());
+
+    for (size_t i = 0; i < expected.size(); i++) {
+      EXPECT_EQ(expected[i].min(), actual1[i].min());
+      EXPECT_EQ(expected[i].max(), actual1[i].max());
+
+      EXPECT_EQ(expected[i].min(), actual2[i].min());
+      EXPECT_EQ(expected[i].max(), actual2[i].max());
+    }
+
+    // Ensure that the rbegin()/rend() iterators correctly yield the intervals
+    // in reverse order.
+    EXPECT_THAT(vector<Interval<int>>(iset.rbegin(), iset.rend()),
+                ElementsAreArray(expected.rbegin(), expected.rend()));
+  }
+
+  TestNotContainsAndFind(iset, 89);
+  TestContainsAndFind(iset, 90);
+  TestContainsAndFind(iset, 120);
+  TestContainsAndFind(iset, 219);
+  TestNotContainsAndFind(iset, 220);
+  TestNotContainsAndFind(iset, 235);
+  TestNotContainsAndFind(iset, 249);
+  TestContainsAndFind(iset, 250);
+  TestContainsAndFind(iset, 300);
+  TestContainsAndFind(iset, 449);
+  TestNotContainsAndFind(iset, 450);
+  TestNotContainsAndFind(iset, 451);
+
+  TestNotContainsAndFind(iset, 50, 60);
+  TestNotContainsAndFind(iset, 50, 90);
+  TestNotContainsAndFind(iset, 50, 200);
+  TestNotContainsAndFind(iset, 90, 90);
+  TestContainsAndFind(iset, 90, 200);
+  TestContainsAndFind(iset, 100, 200);
+  TestContainsAndFind(iset, 100, 220);
+  TestNotContainsAndFind(iset, 100, 221);
+  TestNotContainsAndFind(iset, 220, 220);
+  TestNotContainsAndFind(iset, 240, 300);
+  TestContainsAndFind(iset, 250, 300);
+  TestContainsAndFind(iset, 260, 300);
+  TestContainsAndFind(iset, 300, 450);
+  TestNotContainsAndFind(iset, 300, 451);
+
+  IntervalSet<int> iset_contains;
+  iset_contains.Add(50, 90);
+  EXPECT_FALSE(iset.Contains(iset_contains));
+  iset_contains.Clear();
+
+  iset_contains.Add(90, 200);
+  EXPECT_TRUE(iset.Contains(iset_contains));
+  iset_contains.Add(100, 200);
+  EXPECT_TRUE(iset.Contains(iset_contains));
+  iset_contains.Add(100, 220);
+  EXPECT_TRUE(iset.Contains(iset_contains));
+  iset_contains.Add(250, 300);
+  EXPECT_TRUE(iset.Contains(iset_contains));
+  iset_contains.Add(300, 450);
+  EXPECT_TRUE(iset.Contains(iset_contains));
+  iset_contains.Add(300, 451);
+  EXPECT_FALSE(iset.Contains(iset_contains));
+  EXPECT_FALSE(iset.Contains(Interval<int>()));
+  EXPECT_FALSE(iset.Contains(IntervalSet<int>()));
+}
+
+TEST_F(IntervalSetTest, IntervalSetContainsEmpty) {
+  const IntervalSet<int> empty;
+  const IntervalSet<int> other_empty;
+  EXPECT_FALSE(empty.Contains(empty));
+  EXPECT_FALSE(empty.Contains(other_empty));
+// TODO(rtenneti): Implement after suupport for std::initializer_list.
+#if 0
+  const IntervalSet<int> non_empty({{10, 20}, {40, 50}});
+  EXPECT_FALSE(empty.Contains(non_empty));
+  EXPECT_FALSE(non_empty.Contains(empty));
+#endif
+}
+
+TEST_F(IntervalSetTest, Equality) {
+  IntervalSet<int> is_copy = is;
+  EXPECT_TRUE(is.Equals(is));
+  EXPECT_EQ(is, is);
+  EXPECT_TRUE(is.Equals(is_copy));
+  EXPECT_EQ(is, is_copy);
+  EXPECT_FALSE(is.Equals(other));
+  EXPECT_NE(is, other);
+  EXPECT_FALSE(is.Equals(IntervalSet<int>()));
+  EXPECT_NE(is, IntervalSet<int>());
+  EXPECT_TRUE(IntervalSet<int>().Equals(IntervalSet<int>()));
+  EXPECT_EQ(IntervalSet<int>(), IntervalSet<int>());
+}
+
+TEST_F(IntervalSetTest, SpanningInterval) {
+  // Spanning interval of an empty set is empty:
+  {
+    IntervalSet<int> iset;
+    const Interval<int>& ival = iset.SpanningInterval();
+    EXPECT_TRUE(ival.Empty());
+  }
+
+  // Spanning interval of a set with one interval is that interval:
+  {
+    IntervalSet<int> iset;
+    iset.Add(100, 200);
+    const Interval<int>& ival = iset.SpanningInterval();
+    EXPECT_EQ(100, ival.min());
+    EXPECT_EQ(200, ival.max());
+  }
+
+  // Spanning interval of a set with multiple elements is determined
+  // by the endpoints of the first and last element:
+  {
+    const Interval<int>& ival = is.SpanningInterval();
+    EXPECT_EQ(100, ival.min());
+    EXPECT_EQ(2200, ival.max());
+  }
+  {
+    const Interval<int>& ival = other.SpanningInterval();
+    EXPECT_EQ(50, ival.min());
+    EXPECT_EQ(2270, ival.max());
+  }
+}
+
+TEST_F(IntervalSetTest, IntervalSetUnion) {
+  is.Union(other);
+  EXPECT_TRUE(Check(is, 12, 50, 70, 100, 200, 300, 400, 470, 600, 650, 670, 700,
+                    830, 870, 1000, 1100, 1230, 1270, 1830, 1900, 2000, 2100,
+                    2200, 2250, 2270));
+}
+
+TEST_F(IntervalSetTest, IntervalSetIntersection) {
+  EXPECT_TRUE(is.Intersects(other));
+  EXPECT_TRUE(other.Intersects(is));
+  is.Intersection(other);
+  EXPECT_TRUE(Check(is, 7, 350, 360, 370, 380, 500, 530, 770, 800, 1300, 1400,
+                    1500, 1600, 1700, 1800));
+  EXPECT_TRUE(is.Intersects(other));
+  EXPECT_TRUE(other.Intersects(is));
+}
+
+TEST_F(IntervalSetTest, IntervalSetIntersectionBothEmpty) {
+  IntervalSet<string> mine, theirs;
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+  mine.Intersection(theirs);
+  EXPECT_TRUE(mine.Empty());
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+}
+
+TEST_F(IntervalSetTest, IntervalSetIntersectionEmptyMine) {
+  IntervalSet<string> mine;
+  IntervalSet<string> theirs("a", "b");
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+  mine.Intersection(theirs);
+  EXPECT_TRUE(mine.Empty());
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+}
+
+TEST_F(IntervalSetTest, IntervalSetIntersectionEmptyTheirs) {
+  IntervalSet<string> mine("a", "b");
+  IntervalSet<string> theirs;
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+  mine.Intersection(theirs);
+  EXPECT_TRUE(mine.Empty());
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+}
+
+TEST_F(IntervalSetTest, IntervalSetIntersectionTheirsBeforeMine) {
+  IntervalSet<string> mine("y", "z");
+  IntervalSet<string> theirs;
+  theirs.Add("a", "b");
+  theirs.Add("c", "d");
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+  mine.Intersection(theirs);
+  EXPECT_TRUE(mine.Empty());
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+}
+
+TEST_F(IntervalSetTest, IntervalSetIntersectionMineBeforeTheirs) {
+  IntervalSet<string> mine;
+  mine.Add("a", "b");
+  mine.Add("c", "d");
+  IntervalSet<string> theirs("y", "z");
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+  mine.Intersection(theirs);
+  EXPECT_TRUE(mine.Empty());
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+}
+
+// TODO(rtenneti): Implement after suupport for std::initializer_list.
+#if 0
+TEST_F(IntervalSetTest,
+       IntervalSetIntersectionTheirsBeforeMineInt64Singletons) {
+  IntervalSet<int64> mine({{10, 15}});
+  IntervalSet<int64> theirs({{-20, -5}});
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+  mine.Intersection(theirs);
+  EXPECT_TRUE(mine.Empty());
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+}
+
+TEST_F(IntervalSetTest, IntervalSetIntersectionMineBeforeTheirsIntSingletons) {
+  IntervalSet<int> mine({{10, 15}});
+  IntervalSet<int> theirs({{90, 95}});
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+  mine.Intersection(theirs);
+  EXPECT_TRUE(mine.Empty());
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+}
+
+TEST_F(IntervalSetTest, IntervalSetIntersectionTheirsBetweenMine) {
+  IntervalSet<int64> mine({{0, 5}, {40, 50}});
+  IntervalSet<int64> theirs({{10, 15}});
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+  mine.Intersection(theirs);
+  EXPECT_TRUE(mine.Empty());
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+}
+
+TEST_F(IntervalSetTest, IntervalSetIntersectionMineBetweenTheirs) {
+  IntervalSet<int> mine({{20, 25}});
+  IntervalSet<int> theirs({{10, 15}, {30, 32}});
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+  mine.Intersection(theirs);
+  EXPECT_TRUE(mine.Empty());
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+}
+#endif  // 0
+
+TEST_F(IntervalSetTest, IntervalSetIntersectionAlternatingIntervals) {
+  IntervalSet<int> mine, theirs;
+  mine.Add(10, 20);
+  mine.Add(40, 50);
+  mine.Add(60, 70);
+  theirs.Add(25, 39);
+  theirs.Add(55, 59);
+  theirs.Add(75, 79);
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+  mine.Intersection(theirs);
+  EXPECT_TRUE(mine.Empty());
+  EXPECT_FALSE(mine.Intersects(theirs));
+  EXPECT_FALSE(theirs.Intersects(mine));
+}
+
+// TODO(rtenneti): Implement after suupport for std::initializer_list.
+#if 0
+TEST_F(IntervalSetTest,
+       IntervalSetIntersectionAdjacentAlternatingNonIntersectingIntervals) {
+  // Make sure that intersection with adjacent interval set is empty.
+  const IntervalSet<int> x1({{0, 10}});
+  const IntervalSet<int> y1({{-50, 0}, {10, 95}});
+
+  IntervalSet<int> result1 = x1;
+  result1.Intersection(y1);
+  EXPECT_TRUE(result1.Empty()) << result1;
+
+  const IntervalSet<int16> x2({{0, 10}, {20, 30}, {40, 90}});
+  const IntervalSet<int16> y2(
+      {{-50, -40}, {-2, 0}, {10, 20}, {32, 40}, {90, 95}});
+
+  IntervalSet<int16> result2 = x2;
+  result2.Intersection(y2);
+  EXPECT_TRUE(result2.Empty()) << result2;
+
+  const IntervalSet<int64> x3({{-1, 5}, {5, 10}});
+  const IntervalSet<int64> y3({{-10, -1}, {10, 95}});
+
+  IntervalSet<int64> result3 = x3;
+  result3.Intersection(y3);
+  EXPECT_TRUE(result3.Empty()) << result3;
+}
+
+TEST_F(IntervalSetTest,
+       IntervalSetIntersectionAlternatingIntersectingIntervals) {
+  const IntervalSet<int> x1({{0, 10}});
+  const IntervalSet<int> y1({{-50, 1}, {9, 95}});
+  const IntervalSet<int> expected_result1({{0, 1}, {9, 10}});
+
+  IntervalSet<int> result1 = x1;
+  result1.Intersection(y1);
+  EXPECT_EQ(result1, expected_result1);
+
+  const IntervalSet<int16> x2({{0, 10}, {20, 30}, {40, 90}});
+  const IntervalSet<int16> y2(
+      {{-50, -40}, {-2, 2}, {9, 21}, {32, 41}, {85, 95}});
+  const IntervalSet<int16> expected_result2(
+      {{0, 2}, {9, 10}, {20, 21}, {40, 41}, {85, 90}});
+
+  IntervalSet<int16> result2 = x2;
+  result2.Intersection(y2);
+  EXPECT_EQ(result2, expected_result2);
+
+  const IntervalSet<int64> x3({{-1, 5}, {5, 10}});
+  const IntervalSet<int64> y3({{-10, 3}, {4, 95}});
+  const IntervalSet<int64> expected_result3({{-1, 3}, {4, 10}});
+
+  IntervalSet<int64> result3 = x3;
+  result3.Intersection(y3);
+  EXPECT_EQ(result3, expected_result3);
+}
+
+#endif  // 0
+
+TEST_F(IntervalSetTest, IntervalSetIntersectionIdentical) {
+  IntervalSet<int> copy(is);
+  EXPECT_TRUE(copy.Intersects(is));
+  EXPECT_TRUE(is.Intersects(copy));
+  is.Intersection(copy);
+  EXPECT_EQ(copy, is);
+}
+
+TEST_F(IntervalSetTest, IntervalSetIntersectionSuperset) {
+  IntervalSet<int> mine(-1, 10000);
+  EXPECT_TRUE(mine.Intersects(is));
+  EXPECT_TRUE(is.Intersects(mine));
+  mine.Intersection(is);
+  EXPECT_EQ(is, mine);
+}
+
+TEST_F(IntervalSetTest, IntervalSetIntersectionSubset) {
+  IntervalSet<int> copy(is);
+  IntervalSet<int> theirs(-1, 10000);
+  EXPECT_TRUE(copy.Intersects(theirs));
+  EXPECT_TRUE(theirs.Intersects(copy));
+  is.Intersection(theirs);
+  EXPECT_EQ(copy, is);
+}
+
+TEST_F(IntervalSetTest, IntervalSetIntersectionLargeSet) {
+  IntervalSet<int> mine, theirs;
+  // mine: [0, 9), [10, 19), ..., [990, 999)
+  for (int i = 0; i < 1000; i += 10) {
+    mine.Add(i, i + 9);
+  }
+
+  theirs.Add(500, 520);
+  theirs.Add(535, 545);
+  theirs.Add(801, 809);
+  EXPECT_TRUE(mine.Intersects(theirs));
+  EXPECT_TRUE(theirs.Intersects(mine));
+  mine.Intersection(theirs);
+  EXPECT_TRUE(Check(mine, 5, 500, 509, 510, 519, 535, 539, 540, 545, 801, 809));
+  EXPECT_TRUE(mine.Intersects(theirs));
+  EXPECT_TRUE(theirs.Intersects(mine));
+}
+
+TEST_F(IntervalSetTest, IntervalSetDifference) {
+  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));
+  IntervalSet<int> copy = is;
+  is.Difference(copy);
+  EXPECT_TRUE(is.Empty());
+}
+
+TEST_F(IntervalSetTest, IntervalSetDifferenceSingleBounds) {
+  vector<Interval<int>> ivals;
+  other.Get(&ivals);
+  for (size_t i = 0; i < ivals.size(); ++i) {
+    is.Difference(ivals[i].min(), ivals[i].max());
+  }
+  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));
+}
+
+TEST_F(IntervalSetTest, IntervalSetDifferenceSingleInterval) {
+  vector<Interval<int>> ivals;
+  other.Get(&ivals);
+  for (size_t i = 0; i < ivals.size(); ++i) {
+    is.Difference(ivals[i]);
+  }
+  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));
+}
+
+TEST_F(IntervalSetTest, IntervalSetDifferenceAlternatingIntervals) {
+  IntervalSet<int> mine, theirs;
+  mine.Add(10, 20);
+  mine.Add(40, 50);
+  mine.Add(60, 70);
+  theirs.Add(25, 39);
+  theirs.Add(55, 59);
+  theirs.Add(75, 79);
+
+  mine.Difference(theirs);
+  EXPECT_TRUE(Check(mine, 3, 10, 20, 40, 50, 60, 70));
+}
+
+TEST_F(IntervalSetTest, IntervalSetDifferenceEmptyMine) {
+  IntervalSet<string> mine, theirs;
+  theirs.Add("a", "b");
+
+  mine.Difference(theirs);
+  EXPECT_TRUE(mine.Empty());
+}
+
+TEST_F(IntervalSetTest, IntervalSetDifferenceEmptyTheirs) {
+  IntervalSet<string> mine, theirs;
+  mine.Add("a", "b");
+
+  mine.Difference(theirs);
+  EXPECT_EQ(1u, mine.Size());
+  EXPECT_EQ("a", mine.begin()->min());
+  EXPECT_EQ("b", mine.begin()->max());
+}
+
+TEST_F(IntervalSetTest, IntervalSetDifferenceTheirsBeforeMine) {
+  IntervalSet<string> mine, theirs;
+  mine.Add("y", "z");
+  theirs.Add("a", "b");
+
+  mine.Difference(theirs);
+  EXPECT_EQ(1u, mine.Size());
+  EXPECT_EQ("y", mine.begin()->min());
+  EXPECT_EQ("z", mine.begin()->max());
+}
+
+TEST_F(IntervalSetTest, IntervalSetDifferenceMineBeforeTheirs) {
+  IntervalSet<string> mine, theirs;
+  mine.Add("a", "b");
+  theirs.Add("y", "z");
+
+  mine.Difference(theirs);
+  EXPECT_EQ(1u, mine.Size());
+  EXPECT_EQ("a", mine.begin()->min());
+  EXPECT_EQ("b", mine.begin()->max());
+}
+
+TEST_F(IntervalSetTest, IntervalSetDifferenceIdentical) {
+  IntervalSet<string> mine;
+  mine.Add("a", "b");
+  mine.Add("c", "d");
+  IntervalSet<string> theirs(mine);
+
+  mine.Difference(theirs);
+  EXPECT_TRUE(mine.Empty());
+}
+
+TEST_F(IntervalSetTest, EmptyComplement) {
+  // The complement of an empty set is the input interval:
+  IntervalSet<int> iset;
+  iset.Complement(100, 200);
+  EXPECT_TRUE(Check(iset, 1, 100, 200));
+}
+
+TEST(IntervalSetMultipleCompactionTest, OuterCovering) {
+  IntervalSet<int> iset;
+  // First add a bunch of disjoint ranges
+  iset.Add(100, 150);
+  iset.Add(200, 250);
+  iset.Add(300, 350);
+  iset.Add(400, 450);
+  EXPECT_TRUE(Check(iset, 4, 100, 150, 200, 250, 300, 350, 400, 450));
+  // Now add a big range that covers all of these ranges
+  iset.Add(0, 500);
+  EXPECT_TRUE(Check(iset, 1, 0, 500));
+}
+
+TEST(IntervalSetMultipleCompactionTest, InnerCovering) {
+  IntervalSet<int> iset;
+  // First add a bunch of disjoint ranges
+  iset.Add(100, 150);
+  iset.Add(200, 250);
+  iset.Add(300, 350);
+  iset.Add(400, 450);
+  EXPECT_TRUE(Check(iset, 4, 100, 150, 200, 250, 300, 350, 400, 450));
+  // Now add a big range that partially covers the left and right most ranges.
+  iset.Add(125, 425);
+  EXPECT_TRUE(Check(iset, 1, 100, 450));
+}
+
+TEST(IntervalSetMultipleCompactionTest, LeftCovering) {
+  IntervalSet<int> iset;
+  // First add a bunch of disjoint ranges
+  iset.Add(100, 150);
+  iset.Add(200, 250);
+  iset.Add(300, 350);
+  iset.Add(400, 450);
+  EXPECT_TRUE(Check(iset, 4, 100, 150, 200, 250, 300, 350, 400, 450));
+  // Now add a big range that partially covers the left most range.
+  iset.Add(125, 500);
+  EXPECT_TRUE(Check(iset, 1, 100, 500));
+}
+
+TEST(IntervalSetMultipleCompactionTest, RightCovering) {
+  IntervalSet<int> iset;
+  // First add a bunch of disjoint ranges
+  iset.Add(100, 150);
+  iset.Add(200, 250);
+  iset.Add(300, 350);
+  iset.Add(400, 450);
+  EXPECT_TRUE(Check(iset, 4, 100, 150, 200, 250, 300, 350, 400, 450));
+  // Now add a big range that partially covers the right most range.
+  iset.Add(0, 425);
+  EXPECT_TRUE(Check(iset, 1, 0, 450));
+}
+
+// Helper method for testing and verifying the results of a one-interval
+// completement case.
+static bool CheckOneComplement(int add_min,
+                               int add_max,
+                               int comp_min,
+                               int comp_max,
+                               int count,
+                               ...) {
+  IntervalSet<int> iset;
+  iset.Add(add_min, add_max);
+  iset.Complement(comp_min, comp_max);
+  bool result = true;
+  va_list ap;
+  va_start(ap, count);
+  if (!VA_Check(iset, count, ap)) {
+    result = false;
+  }
+  va_end(ap);
+  return result;
+}
+
+TEST_F(IntervalSetTest, SingleIntervalComplement) {
+  // Verify the complement of a set with one interval (i):
+  //                     |-----   i  -----|
+  // |----- args -----|
+  EXPECT_TRUE(CheckOneComplement(0, 10, 50, 150, 1, 50, 150));
+
+  //          |-----   i  -----|
+  //    |----- args -----|
+  EXPECT_TRUE(CheckOneComplement(50, 150, 0, 100, 1, 0, 50));
+
+  //    |-----   i  -----|
+  //    |----- args -----|
+  EXPECT_TRUE(CheckOneComplement(50, 150, 50, 150, 0));
+
+  //    |----------   i  ----------|
+  //        |----- args -----|
+  EXPECT_TRUE(CheckOneComplement(50, 500, 100, 300, 0));
+
+  //        |----- i -----|
+  //    |---------- args  ----------|
+  EXPECT_TRUE(CheckOneComplement(50, 500, 0, 800, 2, 0, 50, 500, 800));
+
+  //    |-----   i  -----|
+  //          |----- args -----|
+  EXPECT_TRUE(CheckOneComplement(50, 150, 100, 300, 1, 150, 300));
+
+  //    |-----   i  -----|
+  //                        |----- args -----|
+  EXPECT_TRUE(CheckOneComplement(50, 150, 200, 300, 1, 200, 300));
+}
+
+// Helper method that copies <iset> and takes its complement,
+// returning false if Check succeeds.
+static bool CheckComplement(const IntervalSet<int>& iset,
+                            int comp_min,
+                            int comp_max,
+                            int count,
+                            ...) {
+  IntervalSet<int> iset_copy = iset;
+  iset_copy.Complement(comp_min, comp_max);
+  bool result = true;
+  va_list ap;
+  va_start(ap, count);
+  if (!VA_Check(iset_copy, count, ap)) {
+    result = false;
+  }
+  va_end(ap);
+  return result;
+}
+
+TEST_F(IntervalSetTest, MultiIntervalComplement) {
+  // Initialize a small test set:
+  IntervalSet<int> iset;
+  iset.Add(100, 200);
+  iset.Add(300, 400);
+  iset.Add(500, 600);
+
+  //                     |-----   i  -----|
+  // |----- comp -----|
+  EXPECT_TRUE(CheckComplement(iset, 0, 50, 1, 0, 50));
+
+  //          |-----   i  -----|
+  //    |----- comp -----|
+  EXPECT_TRUE(CheckComplement(iset, 0, 200, 1, 0, 100));
+  EXPECT_TRUE(CheckComplement(iset, 0, 220, 2, 0, 100, 200, 220));
+
+  //    |-----   i  -----|
+  //    |----- comp -----|
+  EXPECT_TRUE(CheckComplement(iset, 100, 600, 2, 200, 300, 400, 500));
+
+  //    |----------   i  ----------|
+  //        |----- comp -----|
+  EXPECT_TRUE(CheckComplement(iset, 300, 400, 0));
+  EXPECT_TRUE(CheckComplement(iset, 250, 400, 1, 250, 300));
+  EXPECT_TRUE(CheckComplement(iset, 300, 450, 1, 400, 450));
+  EXPECT_TRUE(CheckComplement(iset, 250, 450, 2, 250, 300, 400, 450));
+
+  //        |----- i -----|
+  //    |---------- comp  ----------|
+  EXPECT_TRUE(
+      CheckComplement(iset, 0, 700, 4, 0, 100, 200, 300, 400, 500, 600, 700));
+
+  //    |-----   i  -----|
+  //          |----- comp -----|
+  EXPECT_TRUE(CheckComplement(iset, 400, 700, 2, 400, 500, 600, 700));
+  EXPECT_TRUE(CheckComplement(iset, 350, 700, 2, 400, 500, 600, 700));
+
+  //    |-----   i  -----|
+  //                        |----- comp -----|
+  EXPECT_TRUE(CheckComplement(iset, 700, 800, 1, 700, 800));
+}
+
+// Verifies ToString, operator<< don't assert.
+// TODO(rtenneti): Implement ToString() method of IntervalSet.
+TEST_F(IntervalSetTest, DISABLED_ToString) {
+  IntervalSet<int> iset;
+  iset.Add(300, 400);
+  iset.Add(100, 200);
+  iset.Add(500, 600);
+  EXPECT_TRUE(!iset.ToString().empty());
+  VLOG(2) << iset.ToString();
+  // Order and format of ToString() output is guaranteed.
+  EXPECT_EQ("[100, 200) [300, 400) [500, 600)", iset.ToString());
+  EXPECT_EQ("[1, 2)", IntervalSet<int>(1, 2).ToString());
+  EXPECT_EQ("", IntervalSet<int>().ToString());
+}
+
+TEST_F(IntervalSetTest, ConstructionDiscardsEmptyInterval) {
+  EXPECT_TRUE(IntervalSet<int>(Interval<int>(2, 2)).Empty());
+  EXPECT_TRUE(IntervalSet<int>(2, 2).Empty());
+  EXPECT_FALSE(IntervalSet<int>(Interval<int>(2, 3)).Empty());
+  EXPECT_FALSE(IntervalSet<int>(2, 3).Empty());
+}
+
+TEST_F(IntervalSetTest, Swap) {
+  IntervalSet<int> a, b;
+  a.Add(300, 400);
+  b.Add(100, 200);
+  b.Add(500, 600);
+  a.Swap(&b);
+  EXPECT_TRUE(Check(a, 2, 100, 200, 500, 600));
+  EXPECT_TRUE(Check(b, 1, 300, 400));
+  swap(a, b);
+  EXPECT_TRUE(Check(a, 1, 300, 400));
+  EXPECT_TRUE(Check(b, 2, 100, 200, 500, 600));
+}
+
+// TODO(rtenneti): Enabled these tests.
+#if 0
+static void BM_Difference(int iters) {
+  //  StopBenchmarkTiming();
+  IntervalSet<int> difference_set;
+  int start = 10;
+  for (int i = 0; i < 1000000; ++i) {
+    difference_set.Add(start, start+5);
+    start += 7;
+  }
+
+  // Create an interval somewhere in the middle of the difference set.
+  // StartBenchmarkTiming();
+  for (int i = 0; i < iters; ++i) {
+    IntervalSet<int> initial(1000000, 1000020);
+    initial.Difference(difference_set);
+  }
+}
+
+BENCHMARK(BM_Difference);
+
+static void BM_IntersectionSmallAndLarge(int iters, int size) {
+  // Intersects constant size 'mine' with large 'theirs'.
+  StopBenchmarkTiming();
+  IntervalSet<int> theirs;
+  for (int i = 0; i < size; ++i) {
+    theirs.Add(2 * i, 2 * i + 1);
+  }
+
+  StartBenchmarkTiming();
+  for (int i = 0; i < iters; ++i) {
+    // 'mine' starts in the middle of 'theirs'.
+    IntervalSet<int> mine(size, size + 10);
+    mine.Intersection(theirs);
+  }
+}
+
+BENCHMARK_RANGE(BM_IntersectionSmallAndLarge, 0, 1 << 23);
+
+static void BM_IntersectionIdentical(int iters, int size) {
+  // Intersects identical 'mine' and 'theirs'.
+  StopBenchmarkTiming();
+  IntervalSet<int> mine;
+  for (int i = 0; i < size; ++i) {
+    mine.Add(2 * i, 2 * i + 1);
+  }
+  IntervalSet<int> theirs(mine);
+
+  StartBenchmarkTiming();
+  for (int i = 0; i < iters; ++i) {
+    mine.Intersection(theirs);
+  }
+}
+
+BENCHMARK_RANGE(BM_IntersectionIdentical, 0, 1 << 23);
+
+class IntervalSetInitTest : public testing::Test {
+ protected:
+  const std::vector<Interval<int>> intervals_{{0, 1}, {2, 4}};
+};
+
+TEST_F(IntervalSetInitTest, DirectInit) {
+  std::initializer_list<Interval<int>> il = {{0, 1}, {2, 3}, {3, 4}};
+  IntervalSet<int> s(il);
+  EXPECT_THAT(s, ElementsAreArray(intervals_));
+}
+
+TEST_F(IntervalSetInitTest, CopyInit) {
+  std::initializer_list<Interval<int>> il = {{0, 1}, {2, 3}, {3, 4}};
+  IntervalSet<int> s = il;
+  EXPECT_THAT(s, ElementsAreArray(intervals_));
+}
+
+TEST_F(IntervalSetInitTest, AssignIterPair) {
+  IntervalSet<int> s(0, 1000);  // Make sure assign clears.
+  s.assign(intervals_.begin(), intervals_.end());
+  EXPECT_THAT(s, ElementsAreArray(intervals_));
+}
+
+TEST_F(IntervalSetInitTest, AssignInitList) {
+  IntervalSet<int> s(0, 1000);  // Make sure assign clears.
+  s.assign({{0, 1}, {2, 3}, {3, 4}});
+  EXPECT_THAT(s, ElementsAreArray(intervals_));
+}
+
+TEST_F(IntervalSetInitTest, AssignmentInitList) {
+  std::initializer_list<Interval<int>> il = {{0, 1}, {2, 3}, {3, 4}};
+  IntervalSet<int> s;
+  s = il;
+  EXPECT_THAT(s, ElementsAreArray(intervals_));
+}
+
+TEST_F(IntervalSetInitTest, BracedInitThenBracedAssign) {
+  IntervalSet<int> s{{0, 1}, {2, 3}, {3, 4}};
+  s = {{0, 1}, {2, 4}};
+  EXPECT_THAT(s, ElementsAreArray(intervals_));
+}
+
+#endif  // 0
+
+}  // namespace
+}  // namespace test
+}  // namespace net
diff --git a/net/quic/interval_test.cc b/net/quic/interval_test.cc
new file mode 100644
index 0000000..0157124e
--- /dev/null
+++ b/net/quic/interval_test.cc
@@ -0,0 +1,337 @@
+// Copyright 2015 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.
+//
+// ----------------------------------------------------------------------
+//
+// Unittest for the Interval class.
+//
+// Author: Will Neveitt (wneveitt@google.com)
+// ----------------------------------------------------------------------
+
+#include "net/quic/interval.h"
+
+#include <string>
+#include <utility>
+
+#include "base/basictypes.h"
+#include "base/logging.h"
+#include "base/stl_util.h"
+#include "net/test/gtest_util.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+using std::pair;
+using std::string;
+using std::vector;
+
+namespace net {
+namespace test {
+namespace {
+
+class IntervalTest : public ::testing::Test {
+ protected:
+  // Test intersection between the two intervals i1 and i2.  Tries
+  // i1.IntersectWith(i2) and vice versa. The intersection should change i1 iff
+  // changes_i1 is true, and the same for changes_i2.  The resulting
+  // intersection should be result.
+  void TestIntersect(const Interval<int64>& i1,
+                     const Interval<int64>& i2,
+                     bool changes_i1,
+                     bool changes_i2,
+                     const Interval<int64>& result) {
+    Interval<int64> i;
+    i.CopyFrom(i1);
+    EXPECT_TRUE(i.IntersectWith(i2) == changes_i1 && i.Equals(result));
+    i.CopyFrom(i2);
+    EXPECT_TRUE(i.IntersectWith(i1) == changes_i2 && i.Equals(result));
+  }
+};
+
+TEST_F(IntervalTest, ConstructorsCopyAndClear) {
+  Interval<int32> empty;
+  EXPECT_TRUE(empty.Empty());
+
+  Interval<int32> d2(0, 100);
+  EXPECT_EQ(0, d2.min());
+  EXPECT_EQ(100, d2.max());
+  EXPECT_EQ(Interval<int32>(0, 100), d2);
+  EXPECT_NE(Interval<int32>(0, 99), d2);
+
+  empty.CopyFrom(d2);
+  EXPECT_EQ(0, d2.min());
+  EXPECT_EQ(100, d2.max());
+  EXPECT_TRUE(empty.Equals(d2));
+  EXPECT_EQ(empty, d2);
+  EXPECT_TRUE(d2.Equals(empty));
+  EXPECT_EQ(d2, empty);
+
+  Interval<int32> max_less_than_min(40, 20);
+  EXPECT_TRUE(max_less_than_min.Empty());
+  EXPECT_EQ(40, max_less_than_min.min());
+  EXPECT_EQ(20, max_less_than_min.max());
+
+  Interval<int> d3(10, 20);
+  d3.Clear();
+  EXPECT_TRUE(d3.Empty());
+}
+
+TEST_F(IntervalTest, GettersSetters) {
+  Interval<int32> d1(100, 200);
+
+  // SetMin:
+  d1.SetMin(30);
+  EXPECT_EQ(30, d1.min());
+  EXPECT_EQ(200, d1.max());
+
+  // SetMax:
+  d1.SetMax(220);
+  EXPECT_EQ(30, d1.min());
+  EXPECT_EQ(220, d1.max());
+
+  // Set:
+  d1.Clear();
+  d1.Set(30, 220);
+  EXPECT_EQ(30, d1.min());
+  EXPECT_EQ(220, d1.max());
+
+  // SpanningUnion:
+  Interval<int32> d2;
+  EXPECT_TRUE(!d1.SpanningUnion(d2));
+  EXPECT_EQ(30, d1.min());
+  EXPECT_EQ(220, d1.max());
+
+  EXPECT_TRUE(d2.SpanningUnion(d1));
+  EXPECT_EQ(30, d2.min());
+  EXPECT_EQ(220, d2.max());
+
+  d2.SetMin(40);
+  d2.SetMax(100);
+  EXPECT_TRUE(!d1.SpanningUnion(d2));
+  EXPECT_EQ(30, d1.min());
+  EXPECT_EQ(220, d1.max());
+
+  d2.SetMin(20);
+  d2.SetMax(100);
+  EXPECT_TRUE(d1.SpanningUnion(d2));
+  EXPECT_EQ(20, d1.min());
+  EXPECT_EQ(220, d1.max());
+
+  d2.SetMin(50);
+  d2.SetMax(300);
+  EXPECT_TRUE(d1.SpanningUnion(d2));
+  EXPECT_EQ(20, d1.min());
+  EXPECT_EQ(300, d1.max());
+
+  d2.SetMin(0);
+  d2.SetMax(500);
+  EXPECT_TRUE(d1.SpanningUnion(d2));
+  EXPECT_EQ(0, d1.min());
+  EXPECT_EQ(500, d1.max());
+
+  d2.SetMin(100);
+  d2.SetMax(0);
+  EXPECT_TRUE(!d1.SpanningUnion(d2));
+  EXPECT_EQ(0, d1.min());
+  EXPECT_EQ(500, d1.max());
+  EXPECT_TRUE(d2.SpanningUnion(d1));
+  EXPECT_EQ(0, d2.min());
+  EXPECT_EQ(500, d2.max());
+}
+
+TEST_F(IntervalTest, CoveringOps) {
+  const Interval<int64> empty;
+  const Interval<int64> d(100, 200);
+  const Interval<int64> d1(0, 50);
+  const Interval<int64> d2(50, 110);
+  const Interval<int64> d3(110, 180);
+  const Interval<int64> d4(180, 220);
+  const Interval<int64> d5(220, 300);
+  const Interval<int64> d6(100, 150);
+  const Interval<int64> d7(150, 200);
+  const Interval<int64> d8(0, 300);
+
+  // Intersection:
+  EXPECT_TRUE(d.Intersects(d));
+  EXPECT_TRUE(!empty.Intersects(d) && !d.Intersects(empty));
+  EXPECT_TRUE(!d.Intersects(d1) && !d1.Intersects(d));
+  EXPECT_TRUE(d.Intersects(d2) && d2.Intersects(d));
+  EXPECT_TRUE(d.Intersects(d3) && d3.Intersects(d));
+  EXPECT_TRUE(d.Intersects(d4) && d4.Intersects(d));
+  EXPECT_TRUE(!d.Intersects(d5) && !d5.Intersects(d));
+  EXPECT_TRUE(d.Intersects(d6) && d6.Intersects(d));
+  EXPECT_TRUE(d.Intersects(d7) && d7.Intersects(d));
+  EXPECT_TRUE(d.Intersects(d8) && d8.Intersects(d));
+
+  Interval<int64> i;
+  EXPECT_TRUE(d.Intersects(d, &i) && d.Equals(i));
+  EXPECT_TRUE(!empty.Intersects(d, NULL) && !d.Intersects(empty, NULL));
+  EXPECT_TRUE(!d.Intersects(d1, NULL) && !d1.Intersects(d, NULL));
+  EXPECT_TRUE(d.Intersects(d2, &i) && i.Equals(Interval<int64>(100, 110)));
+  EXPECT_TRUE(d2.Intersects(d, &i) && i.Equals(Interval<int64>(100, 110)));
+  EXPECT_TRUE(d.Intersects(d3, &i) && i.Equals(d3));
+  EXPECT_TRUE(d3.Intersects(d, &i) && i.Equals(d3));
+  EXPECT_TRUE(d.Intersects(d4, &i) && i.Equals(Interval<int64>(180, 200)));
+  EXPECT_TRUE(d4.Intersects(d, &i) && i.Equals(Interval<int64>(180, 200)));
+  EXPECT_TRUE(!d.Intersects(d5, NULL) && !d5.Intersects(d, NULL));
+  EXPECT_TRUE(d.Intersects(d6, &i) && i.Equals(d6));
+  EXPECT_TRUE(d6.Intersects(d, &i) && i.Equals(d6));
+  EXPECT_TRUE(d.Intersects(d7, &i) && i.Equals(d7));
+  EXPECT_TRUE(d7.Intersects(d, &i) && i.Equals(d7));
+  EXPECT_TRUE(d.Intersects(d8, &i) && i.Equals(d));
+  EXPECT_TRUE(d8.Intersects(d, &i) && i.Equals(d));
+
+  // Test IntersectsWith().
+  // Arguments are TestIntersect(i1, i2, changes_i1, changes_i2, result).
+  TestIntersect(empty, d, false, true, empty);
+  TestIntersect(d, d1, true, true, empty);
+  TestIntersect(d1, d2, true, true, empty);
+  TestIntersect(d, d2, true, true, Interval<int64>(100, 110));
+  TestIntersect(d8, d, true, false, d);
+  TestIntersect(d8, d1, true, false, d1);
+  TestIntersect(d8, d5, true, false, d5);
+
+  // Contains:
+  EXPECT_TRUE(!empty.Contains(d) && !d.Contains(empty));
+  EXPECT_TRUE(d.Contains(d));
+  EXPECT_TRUE(!d.Contains(d1) && !d1.Contains(d));
+  EXPECT_TRUE(!d.Contains(d2) && !d2.Contains(d));
+  EXPECT_TRUE(d.Contains(d3) && !d3.Contains(d));
+  EXPECT_TRUE(!d.Contains(d4) && !d4.Contains(d));
+  EXPECT_TRUE(!d.Contains(d5) && !d5.Contains(d));
+  EXPECT_TRUE(d.Contains(d6) && !d6.Contains(d));
+  EXPECT_TRUE(d.Contains(d7) && !d7.Contains(d));
+  EXPECT_TRUE(!d.Contains(d8) && d8.Contains(d));
+
+  EXPECT_TRUE(d.Contains(100));
+  EXPECT_TRUE(!d.Contains(200));
+  EXPECT_TRUE(d.Contains(150));
+  EXPECT_TRUE(!d.Contains(99));
+  EXPECT_TRUE(!d.Contains(201));
+
+  // Difference:
+  vector<Interval<int64>*> diff;
+
+  EXPECT_TRUE(!d.Difference(empty, &diff));
+  EXPECT_EQ(1u, diff.size());
+  EXPECT_EQ(100u, diff[0]->min());
+  EXPECT_EQ(200u, diff[0]->max());
+  STLDeleteElements(&diff);
+  EXPECT_TRUE(!empty.Difference(d, &diff) && diff.empty());
+
+  EXPECT_TRUE(d.Difference(d, &diff) && diff.empty());
+  EXPECT_TRUE(!d.Difference(d1, &diff));
+  EXPECT_EQ(1u, diff.size());
+  EXPECT_EQ(100u, diff[0]->min());
+  EXPECT_EQ(200u, diff[0]->max());
+  STLDeleteElements(&diff);
+
+  Interval<int64> lo;
+  Interval<int64> hi;
+
+  EXPECT_TRUE(d.Difference(d2, &lo, &hi));
+  EXPECT_TRUE(lo.Empty());
+  EXPECT_EQ(110u, hi.min());
+  EXPECT_EQ(200u, hi.max());
+  EXPECT_TRUE(d.Difference(d2, &diff));
+  EXPECT_EQ(1u, diff.size());
+  EXPECT_EQ(110u, diff[0]->min());
+  EXPECT_EQ(200u, diff[0]->max());
+  STLDeleteElements(&diff);
+
+  EXPECT_TRUE(d.Difference(d3, &lo, &hi));
+  EXPECT_EQ(100u, lo.min());
+  EXPECT_EQ(110u, lo.max());
+  EXPECT_EQ(180u, hi.min());
+  EXPECT_EQ(200u, hi.max());
+  EXPECT_TRUE(d.Difference(d3, &diff));
+  EXPECT_EQ(2u, diff.size());
+  EXPECT_EQ(100u, diff[0]->min());
+  EXPECT_EQ(110u, diff[0]->max());
+  EXPECT_EQ(180u, diff[1]->min());
+  EXPECT_EQ(200u, diff[1]->max());
+  STLDeleteElements(&diff);
+
+  EXPECT_TRUE(d.Difference(d4, &lo, &hi));
+  EXPECT_EQ(100u, lo.min());
+  EXPECT_EQ(180u, lo.max());
+  EXPECT_TRUE(hi.Empty());
+  EXPECT_TRUE(d.Difference(d4, &diff));
+  EXPECT_EQ(1u, diff.size());
+  EXPECT_EQ(100u, diff[0]->min());
+  EXPECT_EQ(180u, diff[0]->max());
+  STLDeleteElements(&diff);
+
+  EXPECT_FALSE(d.Difference(d5, &lo, &hi));
+  EXPECT_EQ(100u, lo.min());
+  EXPECT_EQ(200u, lo.max());
+  EXPECT_TRUE(hi.Empty());
+  EXPECT_FALSE(d.Difference(d5, &diff));
+  EXPECT_EQ(1u, diff.size());
+  EXPECT_EQ(100u, diff[0]->min());
+  EXPECT_EQ(200u, diff[0]->max());
+  STLDeleteElements(&diff);
+
+  EXPECT_TRUE(d.Difference(d6, &lo, &hi));
+  EXPECT_TRUE(lo.Empty());
+  EXPECT_EQ(150u, hi.min());
+  EXPECT_EQ(200u, hi.max());
+  EXPECT_TRUE(d.Difference(d6, &diff));
+  EXPECT_EQ(1u, diff.size());
+  EXPECT_EQ(150u, diff[0]->min());
+  EXPECT_EQ(200u, diff[0]->max());
+  STLDeleteElements(&diff);
+
+  EXPECT_TRUE(d.Difference(d7, &lo, &hi));
+  EXPECT_EQ(100u, lo.min());
+  EXPECT_EQ(150u, lo.max());
+  EXPECT_TRUE(hi.Empty());
+  EXPECT_TRUE(d.Difference(d7, &diff));
+  EXPECT_EQ(1u, diff.size());
+  EXPECT_EQ(100u, diff[0]->min());
+  EXPECT_EQ(150u, diff[0]->max());
+  STLDeleteElements(&diff);
+
+  EXPECT_TRUE(d.Difference(d8, &lo, &hi));
+  EXPECT_TRUE(lo.Empty());
+  EXPECT_TRUE(hi.Empty());
+  EXPECT_TRUE(d.Difference(d8, &diff) && diff.empty());
+}
+
+TEST_F(IntervalTest, Length) {
+  const Interval<int> empty1;
+  const Interval<int> empty2(1, 1);
+  const Interval<int> empty3(1, 0);
+  const Interval<base::TimeDelta> empty4(
+      base::TimeDelta() + base::TimeDelta::FromSeconds(1), base::TimeDelta());
+  const Interval<int> d1(1, 2);
+  const Interval<int> d2(0, 50);
+  const Interval<base::TimeDelta> d3(
+      base::TimeDelta(), base::TimeDelta() + base::TimeDelta::FromSeconds(1));
+  const Interval<base::TimeDelta> d4(
+      base::TimeDelta() + base::TimeDelta::FromHours(1),
+      base::TimeDelta() + base::TimeDelta::FromMinutes(90));
+
+  EXPECT_EQ(0, empty1.Length());
+  EXPECT_EQ(0, empty2.Length());
+  EXPECT_EQ(0, empty3.Length());
+  EXPECT_EQ(base::TimeDelta(), empty4.Length());
+  EXPECT_EQ(1, d1.Length());
+  EXPECT_EQ(50, d2.Length());
+  EXPECT_EQ(base::TimeDelta::FromSeconds(1), d3.Length());
+  EXPECT_EQ(base::TimeDelta::FromMinutes(30), d4.Length());
+}
+
+TEST_F(IntervalTest, IntervalOfTypeWithNoOperatorMinus) {
+  // Interval<T> should work even if T does not support operator-().  We just
+  // can't call Interval<T>::Length() for such types.
+  const Interval<string> d1("a", "b");
+  const Interval<pair<int, int>> d2({1, 2}, {4, 3});
+  EXPECT_EQ("a", d1.min());
+  EXPECT_EQ("b", d1.max());
+  EXPECT_EQ(std::make_pair(1, 2), d2.min());
+  EXPECT_EQ(std::make_pair(4, 3), d2.max());
+}
+
+}  // unnamed namespace
+}  // namespace test
+}  // namespace net
diff --git a/net/quic/quic_ack_notifier_manager.cc b/net/quic/quic_ack_notifier_manager.cc
index 65b4163..d492b25 100644
--- a/net/quic/quic_ack_notifier_manager.cc
+++ b/net/quic/quic_ack_notifier_manager.cc
@@ -70,12 +70,17 @@ void AckNotifierManager::OnPacketRetransmitted(
 
   // The old packet number is no longer of interest, copy the updated
   // AckNotifiers to the new packet number before deleting the old.
+  // TODO(rtenneti): use std::move whne chromium supports it.
+  // ack_notifier_map_[new_packet_number] = std::move(ack_notifier_list);
   ack_notifier_map_[new_packet_number] = ack_notifier_list;
   ack_notifier_map_.erase(map_it);
 }
 
 void AckNotifierManager::OnSerializedPacket(
     const SerializedPacket& serialized_packet) {
+  if (serialized_packet.notifiers.empty()) {
+    return;
+  }
   // Inform each attached AckNotifier of the packet's serialization.
   AckNotifierList& notifier_list =
       ack_notifier_map_[serialized_packet.packet_number];
diff --git a/net/quic/quic_connection.cc b/net/quic/quic_connection.cc
index ac0bc7b..97895bd 100644
--- a/net/quic/quic_connection.cc
+++ b/net/quic/quic_connection.cc
@@ -325,6 +325,7 @@ QuicConnection::QuicConnection(QuicConnectionId connection_id,
            << connection_id;
   framer_.set_visitor(this);
   framer_.set_received_entropy_calculator(&received_packet_manager_);
+  last_stop_waiting_frame_.least_unacked = 0;
   stats_.connection_creation_time = clock_->ApproximateNow();
   sent_packet_manager_.set_network_change_visitor(this);
   // Allow the packet writer to potentially reduce the packet size to a value
@@ -450,15 +451,6 @@ void QuicConnection::MaybeSetFecAlarm(QuicPacketNumber packet_number) {
 }
 
 void QuicConnection::OnPacket() {
-  DCHECK(last_stream_frames_.empty() &&
-         last_ack_frames_.empty() &&
-         last_stop_waiting_frames_.empty() &&
-         last_rst_frames_.empty() &&
-         last_goaway_frames_.empty() &&
-         last_window_update_frames_.empty() &&
-         last_blocked_frames_.empty() &&
-         last_ping_frames_.empty() &&
-         last_close_frames_.empty());
   last_packet_decrypted_ = false;
   last_packet_revived_ = false;
 }
@@ -716,13 +708,9 @@ bool QuicConnection::OnStreamFrame(const QuicStreamFrame& frame) {
     SendConnectionClose(QUIC_UNENCRYPTED_STREAM_DATA);
     return false;
   }
-  if (FLAGS_quic_process_frames_inline) {
-    visitor_->OnStreamFrame(frame);
-    stats_.stream_bytes_received += frame.data.size();
-    should_last_packet_instigate_acks_ = true;
-  } else {
-    last_stream_frames_.push_back(frame);
-  }
+  visitor_->OnStreamFrame(frame);
+  stats_.stream_bytes_received += frame.data.size();
+  should_last_packet_instigate_acks_ = true;
   return connected_;
 }
 
@@ -743,20 +731,19 @@ bool QuicConnection::OnAckFrame(const QuicAckFrame& incoming_ack) {
     return false;
   }
 
-  if (FLAGS_quic_process_frames_inline) {
-    ProcessAckFrame(incoming_ack);
-    if (incoming_ack.is_truncated) {
-      should_last_packet_instigate_acks_ = true;
-    }
-    if (!incoming_ack.missing_packets.Empty() &&
-        GetLeastUnacked() > incoming_ack.missing_packets.Min()) {
-      ++stop_waiting_count_;
-    } else {
-      stop_waiting_count_ = 0;
-    }
+  ProcessAckFrame(incoming_ack);
+  if (incoming_ack.is_truncated) {
+    should_last_packet_instigate_acks_ = true;
+  }
+  // If the peer is still waiting for a packet that we are no longer planning to
+  // send, send an ack to raise the high water mark.
+  if (!incoming_ack.missing_packets.Empty() &&
+      GetLeastUnacked() > incoming_ack.missing_packets.Min()) {
+    ++stop_waiting_count_;
   } else {
-    last_ack_frames_.push_back(incoming_ack);
+    stop_waiting_count_ = 0;
   }
+
   return connected_;
 }
 
@@ -798,7 +785,7 @@ bool QuicConnection::OnStopWaitingFrame(const QuicStopWaitingFrame& frame) {
     debug_visitor_->OnStopWaitingFrame(frame);
   }
 
-  last_stop_waiting_frames_.push_back(frame);
+  last_stop_waiting_frame_ = frame;
   return connected_;
 }
 
@@ -807,11 +794,7 @@ bool QuicConnection::OnPingFrame(const QuicPingFrame& frame) {
   if (debug_visitor_ != nullptr) {
     debug_visitor_->OnPingFrame(frame);
   }
-  if (FLAGS_quic_process_frames_inline) {
-    should_last_packet_instigate_acks_ = true;
-  } else {
-    last_ping_frames_.push_back(frame);
-  }
+  should_last_packet_instigate_acks_ = true;
   return true;
 }
 
@@ -911,12 +894,8 @@ bool QuicConnection::OnRstStreamFrame(const QuicRstStreamFrame& frame) {
            << "RST_STREAM_FRAME received for stream: " << frame.stream_id
            << " with error: "
            << QuicUtils::StreamErrorToString(frame.error_code);
-  if (FLAGS_quic_process_frames_inline) {
-    visitor_->OnRstStream(frame);
-    should_last_packet_instigate_acks_ = true;
-  } else {
-    last_rst_frames_.push_back(frame);
-  }
+  visitor_->OnRstStream(frame);
+  should_last_packet_instigate_acks_ = true;
   return connected_;
 }
 
@@ -930,11 +909,7 @@ bool QuicConnection::OnConnectionCloseFrame(
            << connection_id()
            << " with error: " << QuicUtils::ErrorToString(frame.error_code)
            << " " << frame.error_details;
-  if (FLAGS_quic_process_frames_inline) {
-    CloseConnection(frame.error_code, true);
-  } else {
-    last_close_frames_.push_back(frame);
-  }
+  CloseConnection(frame.error_code, true);
   return connected_;
 }
 
@@ -949,12 +924,8 @@ bool QuicConnection::OnGoAwayFrame(const QuicGoAwayFrame& frame) {
            << " and reason: " << frame.reason_phrase;
 
   goaway_received_ = true;
-  if (FLAGS_quic_process_frames_inline) {
-    visitor_->OnGoAway(frame);
-    should_last_packet_instigate_acks_ = true;
-  } else {
-    last_goaway_frames_.push_back(frame);
-  }
+  visitor_->OnGoAway(frame);
+  should_last_packet_instigate_acks_ = true;
   return connected_;
 }
 
@@ -966,12 +937,8 @@ bool QuicConnection::OnWindowUpdateFrame(const QuicWindowUpdateFrame& frame) {
   DVLOG(1) << ENDPOINT
            << "WINDOW_UPDATE_FRAME received for stream: " << frame.stream_id
            << " with byte offset: " << frame.byte_offset;
-  if (FLAGS_quic_process_frames_inline) {
-    visitor_->OnWindowUpdateFrame(frame);
-    should_last_packet_instigate_acks_ = true;
-  } else {
-    last_window_update_frames_.push_back(frame);
-  }
+  visitor_->OnWindowUpdateFrame(frame);
+  should_last_packet_instigate_acks_ = true;
   return connected_;
 }
 
@@ -982,12 +949,8 @@ bool QuicConnection::OnBlockedFrame(const QuicBlockedFrame& frame) {
   }
   DVLOG(1) << ENDPOINT
            << "BLOCKED_FRAME received for stream: " << frame.stream_id;
-  if (FLAGS_quic_process_frames_inline) {
-    visitor_->OnBlockedFrame(frame);
-    should_last_packet_instigate_acks_ = true;
-  } else {
-    last_blocked_frames_.push_back(frame);
-  }
+  visitor_->OnBlockedFrame(frame);
+  should_last_packet_instigate_acks_ = true;
   return connected_;
 }
 
@@ -999,17 +962,8 @@ void QuicConnection::OnPacketComplete() {
   }
 
   DVLOG(1) << ENDPOINT << (last_packet_revived_ ? "Revived" : "Got")
-           << " packet " << last_header_.packet_packet_number << " with "  //
-           << last_stream_frames_.size() << " stream frames, "             //
-           << last_ack_frames_.size() << " acks, "                         //
-           << last_stop_waiting_frames_.size() << " stop_waiting, "        //
-           << last_rst_frames_.size() << " rsts, "                         //
-           << last_goaway_frames_.size() << " goaways, "                   //
-           << last_window_update_frames_.size() << " window updates, "     //
-           << last_blocked_frames_.size() << " blocked, "                  //
-           << last_ping_frames_.size() << " pings, "                       //
-           << last_close_frames_.size() << " closes "                      //
-           << "for " << last_header_.public_header.connection_id;
+           << " packet " << last_header_.packet_packet_number << "for "
+           << last_header_.public_header.connection_id;
 
   ++num_packets_received_since_last_ack_sent_;
 
@@ -1028,56 +982,10 @@ void QuicConnection::OnPacketComplete() {
         last_size_, last_header_, time_of_last_received_packet_);
   }
 
-  if (!FLAGS_quic_process_frames_inline) {
-    for (const QuicStreamFrame& frame : last_stream_frames_) {
-      visitor_->OnStreamFrame(frame);
-      stats_.stream_bytes_received += frame.data.size();
-      if (!connected_) {
-        return;
-      }
-    }
-
-    // Process window updates, blocked, stream resets, acks, then stop waiting.
-    for (const QuicWindowUpdateFrame& frame : last_window_update_frames_) {
-      visitor_->OnWindowUpdateFrame(frame);
-      if (!connected_) {
-        return;
-      }
-    }
-    for (const QuicBlockedFrame& frame : last_blocked_frames_) {
-      visitor_->OnBlockedFrame(frame);
-      if (!connected_) {
-        return;
-      }
-    }
-    for (const QuicGoAwayFrame& frame : last_goaway_frames_) {
-      visitor_->OnGoAway(frame);
-      if (!connected_) {
-        return;
-      }
-    }
-    for (const QuicRstStreamFrame& frame : last_rst_frames_) {
-      visitor_->OnRstStream(frame);
-      if (!connected_) {
-        return;
-      }
-    }
-    for (const QuicAckFrame& frame : last_ack_frames_) {
-      ProcessAckFrame(frame);
-      if (!connected_) {
-        return;
-      }
-    }
-    if (!last_close_frames_.empty()) {
-      CloseConnection(last_close_frames_[0].error_code, true);
-      DCHECK(!connected_);
-      return;
-    }
-  }
   // Continue to process stop waiting frames later, because the packet needs
   // to be considered 'received' before the entropy can be updated.
-  for (const QuicStopWaitingFrame& frame : last_stop_waiting_frames_) {
-    ProcessStopWaitingFrame(frame);
+  if (last_stop_waiting_frame_.least_unacked > 0) {
+    ProcessStopWaitingFrame(last_stop_waiting_frame_);
     if (!connected_) {
       return;
     }
@@ -1090,7 +998,6 @@ void QuicConnection::OnPacketComplete() {
     ack_alarm_->Cancel();
   }
 
-  UpdateStopWaitingCount();
   ClearLastFrames();
   MaybeCloseIfTooManyOutstandingPackets();
 }
@@ -1120,20 +1027,8 @@ void QuicConnection::MaybeQueueAck() {
 }
 
 void QuicConnection::ClearLastFrames() {
-  if (FLAGS_quic_process_frames_inline) {
-    should_last_packet_instigate_acks_ = false;
-    last_stop_waiting_frames_.clear();
-    return;
-  }
-  last_stream_frames_.clear();
-  last_ack_frames_.clear();
-  last_stop_waiting_frames_.clear();
-  last_rst_frames_.clear();
-  last_goaway_frames_.clear();
-  last_window_update_frames_.clear();
-  last_blocked_frames_.clear();
-  last_ping_frames_.clear();
-  last_close_frames_.clear();
+  should_last_packet_instigate_acks_ = false;
+  last_stop_waiting_frame_.least_unacked = 0;
 }
 
 void QuicConnection::MaybeCloseIfTooManyOutstandingPackets() {
@@ -1167,20 +1062,9 @@ void QuicConnection::PopulateStopWaitingFrame(
 }
 
 bool QuicConnection::ShouldLastPacketInstigateAck() const {
-  if (FLAGS_quic_process_frames_inline && should_last_packet_instigate_acks_) {
+  if (should_last_packet_instigate_acks_) {
     return true;
   }
-  if (!FLAGS_quic_process_frames_inline) {
-    if (!last_stream_frames_.empty() || !last_goaway_frames_.empty() ||
-        !last_rst_frames_.empty() || !last_window_update_frames_.empty() ||
-        !last_blocked_frames_.empty() || !last_ping_frames_.empty()) {
-      return true;
-    }
-
-    if (!last_ack_frames_.empty() && last_ack_frames_.back().is_truncated) {
-      return true;
-    }
-  }
   // Always send an ack every 20 packets in order to allow the peer to discard
   // information from the SentPacketManager and provide an RTT measurement.
   if (num_packets_received_since_last_ack_sent_ >=
@@ -1190,21 +1074,6 @@ bool QuicConnection::ShouldLastPacketInstigateAck() const {
   return false;
 }
 
-void QuicConnection::UpdateStopWaitingCount() {
-  if (last_ack_frames_.empty()) {
-    return;
-  }
-
-  // If the peer is still waiting for a packet that we are no longer planning to
-  // send, send an ack to raise the high water mark.
-  if (!last_ack_frames_.back().missing_packets.Empty() &&
-      GetLeastUnacked() > last_ack_frames_.back().missing_packets.Min()) {
-    ++stop_waiting_count_;
-  } else {
-    stop_waiting_count_ = 0;
-  }
-}
-
 QuicPacketNumber QuicConnection::GetLeastUnacked() const {
   return sent_packet_manager_.GetLeastUnacked();
 }
@@ -2278,10 +2147,6 @@ void QuicConnection::SetRetransmissionAlarm() {
 }
 
 void QuicConnection::MaybeSetMtuAlarm() {
-  if (!FLAGS_quic_do_path_mtu_discovery) {
-    return;
-  }
-
   // Do not set the alarm if the target size is less than the current size.
   // This covers the case when |mtu_discovery_target_| is at its default value,
   // zero.
diff --git a/net/quic/quic_connection.h b/net/quic/quic_connection.h
index 07a7218..8cf3227 100644
--- a/net/quic/quic_connection.h
+++ b/net/quic/quic_connection.h
@@ -733,10 +733,6 @@ class NET_EXPORT_PRIVATE QuicConnection
   // Checks if the last packet should instigate an ack.
   bool ShouldLastPacketInstigateAck() const;
 
-  // Checks if the peer is waiting for packets that have been given up on, and
-  // therefore an ack frame should be sent with a larger least_unacked.
-  void UpdateStopWaitingCount();
-
   // Sends any packets which are a response to the last packet, including both
   // acks and pending writes if an ack opened the congestion window.
   void MaybeSendInResponseToPacket();
@@ -812,15 +808,7 @@ class NET_EXPORT_PRIVATE QuicConnection
   QuicByteCount last_size_;  // Size of the last received packet.
   EncryptionLevel last_decrypted_packet_level_;
   QuicPacketHeader last_header_;
-  std::vector<QuicStreamFrame> last_stream_frames_;
-  std::vector<QuicAckFrame> last_ack_frames_;
-  std::vector<QuicStopWaitingFrame> last_stop_waiting_frames_;
-  std::vector<QuicRstStreamFrame> last_rst_frames_;
-  std::vector<QuicGoAwayFrame> last_goaway_frames_;
-  std::vector<QuicWindowUpdateFrame> last_window_update_frames_;
-  std::vector<QuicBlockedFrame> last_blocked_frames_;
-  std::vector<QuicPingFrame> last_ping_frames_;
-  std::vector<QuicConnectionCloseFrame> last_close_frames_;
+  QuicStopWaitingFrame last_stop_waiting_frame_;
   bool should_last_packet_instigate_acks_;
 
   // Track some peer state so we can do less bookkeeping
diff --git a/net/quic/quic_connection_logger.cc b/net/quic/quic_connection_logger.cc
index 9635102..5c371c61 100644
--- a/net/quic/quic_connection_logger.cc
+++ b/net/quic/quic_connection_logger.cc
@@ -366,9 +366,9 @@ void QuicConnectionLogger::OnFrameAddedToPacket(const QuicFrame& frame) {
       const uint8 max_ranges = std::numeric_limits<uint8>::max();
       // Compute an upper bound on the number of NACK ranges. If the bound
       // is below the max, then it clearly isn't truncated.
-      if (missing_packets.NumPackets() < max_ranges ||
+      if (missing_packets.NumPacketsSlow() < max_ranges ||
           (missing_packets.Max() - missing_packets.Min() -
-           missing_packets.NumPackets() + 1) < max_ranges) {
+           missing_packets.NumPacketsSlow() + 1) < max_ranges) {
         break;
       }
       size_t num_ranges = 0;
diff --git a/net/quic/quic_connection_test.cc b/net/quic/quic_connection_test.cc
index 95bd004..388070e 100644
--- a/net/quic/quic_connection_test.cc
+++ b/net/quic/quic_connection_test.cc
@@ -17,7 +17,6 @@
 #include "net/quic/crypto/quic_decrypter.h"
 #include "net/quic/crypto/quic_encrypter.h"
 #include "net/quic/quic_ack_notifier.h"
-#include "net/quic/quic_flags.h"
 #include "net/quic/quic_protocol.h"
 #include "net/quic/quic_utils.h"
 #include "net/quic/test_tools/mock_clock.h"
@@ -541,8 +540,6 @@ class TestConnection : public QuicConnection {
   void EnablePathMtuDiscovery(MockSendAlgorithm* send_algorithm) {
     ASSERT_EQ(Perspective::IS_CLIENT, perspective());
 
-    FLAGS_quic_do_path_mtu_discovery = true;
-
     QuicConfig config;
     QuicTagVector connection_options;
     connection_options.push_back(kMTUH);
@@ -3358,9 +3355,6 @@ TEST_P(QuicConnectionTest, SendMtuDiscoveryPacket) {
 TEST_P(QuicConnectionTest, MtuDiscoveryDisabled) {
   EXPECT_TRUE(connection_.connected());
 
-  // Restore the current value FLAGS_quic_do_path_mtu_discovery after the test.
-  ValueRestore<bool> old_flag(&FLAGS_quic_do_path_mtu_discovery, true);
-
   const QuicPacketCount number_of_packets = kPacketsBetweenMtuProbesBase * 2;
   for (QuicPacketCount i = 0; i < number_of_packets; i++) {
     SendStreamDataToPeer(3, ".", i, /*fin=*/false, nullptr);
@@ -3374,8 +3368,6 @@ TEST_P(QuicConnectionTest, MtuDiscoveryDisabled) {
 TEST_P(QuicConnectionTest, MtuDiscoveryEnabled) {
   EXPECT_TRUE(connection_.connected());
 
-  // Restore the current value FLAGS_quic_do_path_mtu_discovery after the test.
-  ValueRestore<bool> old_flag(&FLAGS_quic_do_path_mtu_discovery, true);
   connection_.EnablePathMtuDiscovery(send_algorithm_);
 
   // Send enough packets so that the next one triggers path MTU discovery.
@@ -3419,8 +3411,6 @@ TEST_P(QuicConnectionTest, MtuDiscoveryEnabled) {
 TEST_P(QuicConnectionTest, MtuDiscoveryFailed) {
   EXPECT_TRUE(connection_.connected());
 
-  // Restore the current value FLAGS_quic_do_path_mtu_discovery after the test.
-  ValueRestore<bool> old_flag(&FLAGS_quic_do_path_mtu_discovery, true);
   connection_.EnablePathMtuDiscovery(send_algorithm_);
 
   const QuicTime::Delta rtt = QuicTime::Delta::FromMilliseconds(100);
@@ -3536,8 +3526,6 @@ TEST_P(QuicConnectionTest, MtuDiscoveryWriterLimited) {
 TEST_P(QuicConnectionTest, NoMtuDiscoveryAfterConnectionClosed) {
   EXPECT_TRUE(connection_.connected());
 
-  // Restore the current value FLAGS_quic_do_path_mtu_discovery after the test.
-  ValueRestore<bool> old_flag(&FLAGS_quic_do_path_mtu_discovery, true);
   connection_.EnablePathMtuDiscovery(send_algorithm_);
 
   // Send enough packets so that the next one triggers path MTU discovery.
diff --git a/net/quic/quic_flags.cc b/net/quic/quic_flags.cc
index 0895d25..08a5f47 100644
--- a/net/quic/quic_flags.cc
+++ b/net/quic/quic_flags.cc
@@ -46,16 +46,6 @@ bool FLAGS_enable_quic_stateless_reject_support = true;
 // If true, flow controller may grow the receive window size if necessary.
 bool FLAGS_quic_auto_tune_receive_window = true;
 
-// Enables server-side path MTU discovery in QUIC.
-bool FLAGS_quic_do_path_mtu_discovery = true;
-
-// Process QUIC frames as soon as they're parsed, instead of waiting for the
-// packet's parsing to complete.
-bool FLAGS_quic_process_frames_inline = true;
-
-// Estimate that only 60% of QUIC's receive buffer is usable as opposed to 95%.
-bool FLAGS_quic_use_conservative_receive_buffer = true;
-
 // Limits QUIC's max CWND to 200 packets.
 bool FLAGS_quic_limit_max_cwnd = true;
 
@@ -82,3 +72,7 @@ bool FLAGS_quic_limit_mtu_by_writer = true;
 // QUIC-specific flag. If true, Cubic's epoch is reset when the sender is
 // application-limited.
 bool FLAGS_reset_cubic_epoch_when_app_limited = true;
+
+// If true, use an interval set as the internal representation of a packet queue
+// instead of a set.
+bool FLAGS_quic_packet_queue_use_interval_set = true;
diff --git a/net/quic/quic_flags.h b/net/quic/quic_flags.h
index a791b21..ed8d0e1 100644
--- a/net/quic/quic_flags.h
+++ b/net/quic/quic_flags.h
@@ -19,9 +19,6 @@ NET_EXPORT_PRIVATE extern int64 FLAGS_quic_time_wait_list_seconds;
 NET_EXPORT_PRIVATE extern int64 FLAGS_quic_time_wait_list_max_connections;
 NET_EXPORT_PRIVATE extern bool FLAGS_enable_quic_stateless_reject_support;
 NET_EXPORT_PRIVATE extern bool FLAGS_quic_auto_tune_receive_window;
-NET_EXPORT_PRIVATE extern bool FLAGS_quic_do_path_mtu_discovery;
-NET_EXPORT_PRIVATE extern bool FLAGS_quic_process_frames_inline;
-NET_EXPORT_PRIVATE extern bool FLAGS_quic_use_conservative_receive_buffer;
 NET_EXPORT_PRIVATE extern bool FLAGS_quic_limit_max_cwnd;
 NET_EXPORT_PRIVATE extern bool FLAGS_quic_require_handshake_confirmation;
 NET_EXPORT_PRIVATE extern bool FLAGS_quic_disable_truncated_ack_handling;
@@ -29,5 +26,6 @@ NET_EXPORT_PRIVATE extern bool FLAGS_send_goaway_after_client_migration;
 NET_EXPORT_PRIVATE extern bool FLAGS_quic_close_connection_out_of_order_sending;
 NET_EXPORT_PRIVATE extern bool FLAGS_quic_limit_mtu_by_writer;
 NET_EXPORT_PRIVATE extern bool FLAGS_reset_cubic_epoch_when_app_limited;
+NET_EXPORT_PRIVATE extern bool FLAGS_quic_packet_queue_use_interval_set;
 
 #endif  // NET_QUIC_QUIC_FLAGS_H_
diff --git a/net/quic/quic_framer.cc b/net/quic/quic_framer.cc
index 6d99ad4..a04824a 100644
--- a/net/quic/quic_framer.cc
+++ b/net/quic/quic_framer.cc
@@ -989,7 +989,9 @@ QuicFramer::AckFrameInfo QuicFramer::GetAckFrameInfo(
   }
   DCHECK_GE(frame.largest_observed, frame.missing_packets.Max());
   size_t cur_range_length = 0;
-  PacketNumberSet::const_iterator iter = frame.missing_packets.begin();
+  PacketNumberQueue::const_iterator iter = frame.missing_packets.begin();
+  // TODO(jdorfman): Switch this logic to use the intervals in PacketNumberQueue
+  // instead of reconstructing them from the sequence.
   QuicPacketNumber last_missing = *iter;
   ++iter;
   for (; iter != frame.missing_packets.end(); ++iter) {
diff --git a/net/quic/quic_framer_test.cc b/net/quic/quic_framer_test.cc
index ccaf05f..45710c1 100644
--- a/net/quic/quic_framer_test.cc
+++ b/net/quic/quic_framer_test.cc
@@ -1723,7 +1723,7 @@ TEST_P(QuicFramerTest, AckFrameTwoTimestamp) {
   const QuicAckFrame& frame = *visitor_.ack_frames_[0];
   EXPECT_EQ(0xBA, frame.entropy_hash);
   EXPECT_EQ(UINT64_C(0x0123456789ABF), frame.largest_observed);
-  ASSERT_EQ(1u, frame.missing_packets.NumPackets());
+  ASSERT_EQ(1u, frame.missing_packets.NumPacketsSlow());
   ASSERT_EQ(2u, frame.received_packet_times.size());
   EXPECT_EQ(UINT64_C(0x0123456789ABE), frame.missing_packets.Min());
 
@@ -1839,7 +1839,7 @@ TEST_P(QuicFramerTest, AckFrameOneTimestamp) {
   const QuicAckFrame& frame = *visitor_.ack_frames_[0];
   EXPECT_EQ(0xBA, frame.entropy_hash);
   EXPECT_EQ(UINT64_C(0x0123456789ABF), frame.largest_observed);
-  ASSERT_EQ(1u, frame.missing_packets.NumPackets());
+  ASSERT_EQ(1u, frame.missing_packets.NumPacketsSlow());
   ASSERT_EQ(1u, frame.received_packet_times.size());
   EXPECT_EQ(UINT64_C(0x0123456789ABE), frame.missing_packets.Min());
 
@@ -1941,7 +1941,7 @@ TEST_P(QuicFramerTest, AckFrame) {
   const QuicAckFrame& frame = *visitor_.ack_frames_[0];
   EXPECT_EQ(0xBA, frame.entropy_hash);
   EXPECT_EQ(UINT64_C(0x0123456789ABF), frame.largest_observed);
-  ASSERT_EQ(1u, frame.missing_packets.NumPackets());
+  ASSERT_EQ(1u, frame.missing_packets.NumPacketsSlow());
   EXPECT_EQ(UINT64_C(0x0123456789ABE), frame.missing_packets.Min());
 
   const size_t kReceivedEntropyOffset = kQuicFrameTypeSize;
@@ -2039,7 +2039,7 @@ TEST_P(QuicFramerTest, AckFrameRevivedPackets) {
   const QuicAckFrame& frame = *visitor_.ack_frames_[0];
   EXPECT_EQ(0xBA, frame.entropy_hash);
   EXPECT_EQ(UINT64_C(0x0123456789ABF), frame.largest_observed);
-  ASSERT_EQ(1u, frame.missing_packets.NumPackets());
+  ASSERT_EQ(1u, frame.missing_packets.NumPacketsSlow());
   EXPECT_EQ(UINT64_C(0x0123456789ABE), frame.missing_packets.Min());
 
   const size_t kReceivedEntropyOffset = kQuicFrameTypeSize;
@@ -2197,7 +2197,7 @@ TEST_P(QuicFramerTest, AckFrame500Nacks) {
   EXPECT_EQ(0xBA, frame->entropy_hash);
   EXPECT_EQ(UINT64_C(0x0123456789ABF), frame->largest_observed);
   EXPECT_EQ(0u, frame->revived_packets.size());
-  ASSERT_EQ(500u, frame->missing_packets.NumPackets());
+  ASSERT_EQ(500u, frame->missing_packets.NumPacketsSlow());
   EXPECT_EQ(UINT64_C(0x0123456789ABE) - 499, frame->missing_packets.Min());
   EXPECT_EQ(UINT64_C(0x0123456789ABE), frame->missing_packets.Max());
 
@@ -4264,7 +4264,7 @@ TEST_P(QuicFramerTest, AckTruncationLargePacket) {
   QuicAckFrame& processed_ack_frame = *visitor_.ack_frames_[0];
   EXPECT_TRUE(processed_ack_frame.is_truncated);
   EXPECT_EQ(510u, processed_ack_frame.largest_observed);
-  ASSERT_EQ(255u, processed_ack_frame.missing_packets.NumPackets());
+  ASSERT_EQ(255u, processed_ack_frame.missing_packets.NumPacketsSlow());
   EXPECT_EQ(1u, processed_ack_frame.missing_packets.Min());
   EXPECT_EQ(509u, processed_ack_frame.missing_packets.Max());
 }
@@ -4300,7 +4300,7 @@ TEST_P(QuicFramerTest, AckTruncationSmallPacket) {
   QuicAckFrame& processed_ack_frame = *visitor_.ack_frames_[0];
   EXPECT_TRUE(processed_ack_frame.is_truncated);
   EXPECT_EQ(476u, processed_ack_frame.largest_observed);
-  ASSERT_EQ(238u, processed_ack_frame.missing_packets.NumPackets());
+  ASSERT_EQ(238u, processed_ack_frame.missing_packets.NumPacketsSlow());
   EXPECT_EQ(1u, processed_ack_frame.missing_packets.Min());
   EXPECT_EQ(475u, processed_ack_frame.missing_packets.Max());
 }
diff --git a/net/quic/quic_http_stream_test.cc b/net/quic/quic_http_stream_test.cc
index 84d1bf4..91d5719 100644
--- a/net/quic/quic_http_stream_test.cc
+++ b/net/quic/quic_http_stream_test.cc
@@ -25,7 +25,6 @@
 #include "net/quic/quic_connection.h"
 #include "net/quic/quic_connection_helper.h"
 #include "net/quic/quic_default_packet_writer.h"
-#include "net/quic/quic_flags.h"
 #include "net/quic/quic_http_utils.h"
 #include "net/quic/quic_reliable_client_stream.h"
 #include "net/quic/quic_write_blocked_list.h"
@@ -719,11 +718,7 @@ TEST_P(QuicHttpStreamTest, SendChunkedPostRequestWithOneEmptyDataPacket) {
 TEST_P(QuicHttpStreamTest, DestroyedEarly) {
   SetRequest("GET", "/", DEFAULT_PRIORITY);
   AddWrite(ConstructRequestHeadersPacket(1, kFin, DEFAULT_PRIORITY));
-  if (!FLAGS_quic_process_frames_inline) {
-    AddWrite(ConstructRstStreamCancelledPacket(2));
-  } else {
-    AddWrite(ConstructAckAndRstStreamPacket(2));
-  }
+  AddWrite(ConstructAckAndRstStreamPacket(2));
   use_closing_stream_ = true;
   Initialize();
 
@@ -758,11 +753,7 @@ TEST_P(QuicHttpStreamTest, DestroyedEarly) {
 TEST_P(QuicHttpStreamTest, Priority) {
   SetRequest("GET", "/", MEDIUM);
   AddWrite(ConstructRequestHeadersPacket(1, kFin, MEDIUM));
-  if (!FLAGS_quic_process_frames_inline) {
-    AddWrite(ConstructRstStreamCancelledPacket(2));
-  } else {
-    AddWrite(ConstructAckAndRstStreamPacket(2));
-  }
+  AddWrite(ConstructAckAndRstStreamPacket(2));
   use_closing_stream_ = true;
   Initialize();
 
diff --git a/net/quic/quic_protocol.cc b/net/quic/quic_protocol.cc
index ebc3ef6..a153bec 100644
--- a/net/quic/quic_protocol.cc
+++ b/net/quic/quic_protocol.cc
@@ -5,6 +5,7 @@
 #include "net/quic/quic_protocol.h"
 
 #include "base/stl_util.h"
+#include "net/quic/quic_flags.h"
 #include "net/quic/quic_utils.h"
 
 using base::StringPiece;
@@ -314,74 +315,242 @@ ostream& operator<<(ostream& os, const QuicStopWaitingFrame& sent_info) {
   return os;
 }
 
-PacketNumberQueue::PacketNumberQueue() {}
+PacketNumberQueue::const_iterator::const_iterator(
+    PacketNumberSet::const_iterator set_iter)
+    : use_interval_set_(false), set_iter_(set_iter) {}
+
+PacketNumberQueue::const_iterator::const_iterator(
+    IntervalSet<QuicPacketNumber>::const_iterator interval_set_iter,
+    QuicPacketNumber first,
+    QuicPacketNumber last)
+    : use_interval_set_(true),
+      interval_set_iter_(interval_set_iter),
+      current_(first),
+      last_(last) {}
+
+PacketNumberQueue::const_iterator::const_iterator(const const_iterator& other) =
+    default;
+// TODO(rtenneti): on windows RValue reference gives errors.
+// PacketNumberQueue::const_iterator::const_iterator(const_iterator&& other) =
+//    default;
+PacketNumberQueue::const_iterator::~const_iterator(){};
+
+PacketNumberQueue::const_iterator& PacketNumberQueue::const_iterator::operator=(
+    const const_iterator& other) = default;
+// TODO(rtenneti): on windows RValue reference gives errors.
+// PacketNumberQueue::const_iterator&
+// PacketNumberQueue::const_iterator::operator=(
+//    const_iterator&& other) = default;
+
+bool PacketNumberQueue::const_iterator::operator!=(
+    const const_iterator& other) const {
+  if (use_interval_set_) {
+    return current_ != other.current_;
+  } else {
+    return set_iter_ != other.set_iter_;
+  }
+}
+
+bool PacketNumberQueue::const_iterator::operator==(
+    const const_iterator& other) const {
+  if (use_interval_set_) {
+    return current_ == other.current_;
+  } else {
+    return set_iter_ == other.set_iter_;
+  }
+}
+
+PacketNumberQueue::const_iterator::value_type
+    PacketNumberQueue::const_iterator::
+    operator*() const {
+  if (use_interval_set_) {
+    return current_;
+  } else {
+    return *set_iter_;
+  }
+}
+
+PacketNumberQueue::const_iterator& PacketNumberQueue::const_iterator::
+operator++() {
+  if (use_interval_set_) {
+    ++current_;
+    if (current_ < last_) {
+      if (current_ >= interval_set_iter_->max()) {
+        ++interval_set_iter_;
+        current_ = interval_set_iter_->min();
+      }
+    } else {
+      current_ = last_;
+    }
+  } else {
+    ++set_iter_;
+  }
+  return *this;
+}
 
+PacketNumberQueue::const_iterator PacketNumberQueue::const_iterator::operator++(
+    int /* postincrement */) {
+  PacketNumberQueue::const_iterator preincrement(*this);
+  operator++();
+  return preincrement;
+}
+
+PacketNumberQueue::PacketNumberQueue()
+    : use_interval_set_(FLAGS_quic_packet_queue_use_interval_set) {}
+
+PacketNumberQueue::PacketNumberQueue(const PacketNumberQueue& other) = default;
+PacketNumberQueue& PacketNumberQueue::operator=(
+    const PacketNumberQueue& other) = default;
+// TODO(rtenneti): on windows RValue reference gives errors.
+// PacketNumberQueue::PacketNumberQueue(PacketNumberQueue&& other) = default;
 PacketNumberQueue::~PacketNumberQueue() {}
 
+// TODO(rtenneti): on windows RValue reference gives errors.
+// PacketNumberQueue& PacketNumberQueue::operator=(PacketNumberQueue&& other) =
+//    default;
+
 void PacketNumberQueue::Add(QuicPacketNumber packet_number) {
-  packet_numbers_.insert(packet_number);
+  if (use_interval_set_) {
+    packet_number_intervals_.Add(packet_number, packet_number + 1);
+  } else {
+    packet_number_set_.insert(packet_number);
+  }
 }
 
 void PacketNumberQueue::Add(QuicPacketNumber lower, QuicPacketNumber higher) {
-  for (QuicPacketNumber packet_number = lower; packet_number < higher;
-       ++packet_number) {
-    Add(packet_number);
+  if (use_interval_set_) {
+    packet_number_intervals_.Add(lower, higher);
+  } else {
+    for (QuicPacketNumber packet_number = lower; packet_number < higher;
+         ++packet_number) {
+      Add(packet_number);
+    }
   }
 }
 
 void PacketNumberQueue::Remove(QuicPacketNumber packet_number) {
-  packet_numbers_.erase(packet_number);
+  if (use_interval_set_) {
+    packet_number_intervals_.Difference(packet_number, packet_number + 1);
+  } else {
+    packet_number_set_.erase(packet_number);
+  }
 }
 
 bool PacketNumberQueue::RemoveUpTo(QuicPacketNumber higher) {
-  size_t orig_size = packet_numbers_.size();
-  packet_numbers_.erase(packet_numbers_.begin(),
-                        packet_numbers_.lower_bound(higher));
-  return orig_size != packet_numbers_.size();
+  if (use_interval_set_) {
+    if (Empty()) {
+      return false;
+    }
+    const QuicPacketNumber old_min = Min();
+    packet_number_intervals_.Difference(0, higher);
+    return Empty() || old_min != Min();
+  } else {
+    const size_t orig_size = packet_number_set_.size();
+    packet_number_set_.erase(packet_number_set_.begin(),
+                             packet_number_set_.lower_bound(higher));
+    return orig_size != packet_number_set_.size();
+  }
 }
 
 bool PacketNumberQueue::Contains(QuicPacketNumber packet_number) const {
-  return ContainsKey(packet_numbers_, packet_number);
+  if (use_interval_set_) {
+    return packet_number_intervals_.Contains(packet_number);
+  } else {
+    return ContainsKey(packet_number_set_, packet_number);
+  }
 }
 
 bool PacketNumberQueue::Empty() const {
-  return packet_numbers_.empty();
+  if (use_interval_set_) {
+    return packet_number_intervals_.Empty();
+  } else {
+    return packet_number_set_.empty();
+  }
 }
 
 QuicPacketNumber PacketNumberQueue::Min() const {
   DCHECK(!Empty());
-  return *packet_numbers_.begin();
+  if (use_interval_set_) {
+    return packet_number_intervals_.begin()->min();
+  } else {
+    return *packet_number_set_.begin();
+  }
 }
 
 QuicPacketNumber PacketNumberQueue::Max() const {
   DCHECK(!Empty());
-  return *packet_numbers_.rbegin();
+  if (use_interval_set_) {
+    return packet_number_intervals_.rbegin()->max() - 1;
+  } else {
+    return *packet_number_set_.rbegin();
+  }
 }
 
-size_t PacketNumberQueue::NumPackets() const {
-  return packet_numbers_.size();
+size_t PacketNumberQueue::NumPacketsSlow() const {
+  if (use_interval_set_) {
+    size_t num_packets = 0;
+    for (const auto& interval : packet_number_intervals_) {
+      num_packets += interval.Length();
+    }
+    return num_packets;
+  } else {
+    return packet_number_set_.size();
+  }
 }
 
-PacketNumberQueue::iterator PacketNumberQueue::begin() const {
-  return packet_numbers_.begin();
+PacketNumberQueue::const_iterator PacketNumberQueue::begin() const {
+  if (use_interval_set_) {
+    QuicPacketNumber first;
+    QuicPacketNumber last;
+    if (packet_number_intervals_.Empty()) {
+      first = 0;
+      last = 0;
+    } else {
+      first = packet_number_intervals_.begin()->min();
+      last = packet_number_intervals_.rbegin()->max();
+    }
+    return const_iterator(packet_number_intervals_.begin(), first, last);
+  } else {
+    return const_iterator(packet_number_set_.begin());
+  }
 }
 
-PacketNumberQueue::iterator PacketNumberQueue::end() const {
-  return packet_numbers_.end();
+PacketNumberQueue::const_iterator PacketNumberQueue::end() const {
+  if (use_interval_set_) {
+    QuicPacketNumber last = packet_number_intervals_.Empty()
+                                ? 0
+                                : packet_number_intervals_.rbegin()->max();
+    return const_iterator(packet_number_intervals_.end(), last, last);
+  } else {
+    return const_iterator(packet_number_set_.end());
+  }
 }
 
 PacketNumberQueue::const_iterator PacketNumberQueue::lower_bound(
     QuicPacketNumber packet_number) const {
-  return packet_numbers_.lower_bound(packet_number);
-}
-
-PacketNumberQueue::const_iterator PacketNumberQueue::upper_bound(
-    QuicPacketNumber packet_number) const {
-  return packet_numbers_.upper_bound(packet_number);
+  if (use_interval_set_) {
+    QuicPacketNumber first;
+    QuicPacketNumber last;
+    if (packet_number_intervals_.Empty()) {
+      first = 0;
+      last = 0;
+      return const_iterator(packet_number_intervals_.begin(), first, last);
+    }
+    if (!packet_number_intervals_.Contains(packet_number)) {
+      return end();
+    }
+    IntervalSet<QuicPacketNumber>::const_iterator it =
+        packet_number_intervals_.Find(packet_number);
+    first = packet_number;
+    last = packet_number_intervals_.rbegin()->max();
+    return const_iterator(it, first, last);
+  } else {
+    return const_iterator(packet_number_set_.lower_bound(packet_number));
+  }
 }
 
 ostream& operator<<(ostream& os, const PacketNumberQueue& q) {
-  for (QuicPacketNumber packet_number : q.packet_numbers_) {
+  for (QuicPacketNumber packet_number : q) {
     os << packet_number << " ";
   }
   return os;
diff --git a/net/quic/quic_protocol.h b/net/quic/quic_protocol.h
index 42b96bd..4361206 100644
--- a/net/quic/quic_protocol.h
+++ b/net/quic/quic_protocol.h
@@ -24,6 +24,7 @@
 #include "net/base/iovec.h"
 #include "net/base/ip_endpoint.h"
 #include "net/base/net_export.h"
+#include "net/quic/interval_set.h"
 #include "net/quic/quic_bandwidth.h"
 #include "net/quic/quic_time.h"
 #include "net/quic/quic_types.h"
@@ -727,16 +728,55 @@ struct NET_EXPORT_PRIVATE QuicStopWaitingFrame {
 // larger new packet numbers are added, with the occasional random access.
 class NET_EXPORT_PRIVATE PacketNumberQueue {
  public:
+  // TODO(jdorfman): Once this is completely switched over to IntervalSet,
+  // remove const_iterator and change the callers to iterate over the intervals.
+  class NET_EXPORT_PRIVATE const_iterator
+      : public std::iterator<std::input_iterator_tag,
+                             QuicPacketNumber,
+                             std::ptrdiff_t,
+                             const QuicPacketNumber*,
+                             const QuicPacketNumber&> {
+   public:
+    explicit const_iterator(PacketNumberSet::const_iterator set_iter);
+    const_iterator(
+        IntervalSet<QuicPacketNumber>::const_iterator interval_set_iter,
+        QuicPacketNumber first,
+        QuicPacketNumber last);
+    const_iterator(const const_iterator& other);
+    const_iterator& operator=(const const_iterator& other);
+    // TODO(rtenneti): on windows RValue reference gives errors.
+    // const_iterator(const_iterator&& other);
+    ~const_iterator();
+
+    // TODO(rtenneti): on windows RValue reference gives errors.
+    // const_iterator& operator=(const_iterator&& other);
+    bool operator!=(const const_iterator& other) const;
+    bool operator==(const const_iterator& other) const;
+    value_type operator*() const;
+    const_iterator& operator++();
+    const_iterator operator++(int /* postincrement */);
+
+   private:
+    bool use_interval_set_;
+    PacketNumberSet::const_iterator set_iter_;
+    IntervalSet<QuicPacketNumber>::const_iterator interval_set_iter_;
+    QuicPacketNumber current_;
+    QuicPacketNumber last_;
+  };
+
   PacketNumberQueue();
   ~PacketNumberQueue();
-
-  using iterator = PacketNumberSet::iterator;
-  using const_iterator = PacketNumberSet::const_iterator;
+  PacketNumberQueue(const PacketNumberQueue& other);
+  PacketNumberQueue& operator=(const PacketNumberQueue& other);
+  // TODO(rtenneti): on windows RValue reference gives errors.
+  // PacketNumberQueue(PacketNumberQueue&& other);
+  // PacketNumberQueue& operator=(PacketNumberQueue&& other);
 
   // Adds |packet_number| to the set of packets in the queue.
   void Add(QuicPacketNumber packet_number);
 
-  // Adds packets between [lower, higher) to the set of packets in the queue.
+  // Adds packets between [lower, higher) to the set of packets in the queue. It
+  // is undefined behavior to call this with |higher| < |lower|.
   void Add(QuicPacketNumber lower, QuicPacketNumber higher);
 
   // Removes |packet_number| from the set of packets in the queue.
@@ -760,21 +800,25 @@ class NET_EXPORT_PRIVATE PacketNumberQueue {
   // behavior to call this if the queue is empty.
   QuicPacketNumber Max() const;
 
-  // Returns the number of unique packets stored in the queue.
-  size_t NumPackets() const;
+  // Returns the number of unique packets stored in the queue. Inefficient; only
+  // exposed for testing.
+  size_t NumPacketsSlow() const;
 
-  iterator begin() const;
-  iterator end() const;
+  // Returns iterators over the individual packet numbers.
+  const_iterator begin() const;
+  const_iterator end() const;
   const_iterator lower_bound(QuicPacketNumber packet_number) const;
-  const_iterator upper_bound(QuicPacketNumber packet_number) const;
+  // TODO(rtenneti): Implement upper_bound.
+  // const_iterator upper_bound(QuicPacketNumber packet_number) const;
 
   NET_EXPORT_PRIVATE friend std::ostream& operator<<(
       std::ostream& os,
       const PacketNumberQueue& q);
 
  private:
-  // TODO(jdorfman): Can be optimized using an interval set like data structure.
-  PacketNumberSet packet_numbers_;
+  bool use_interval_set_;
+  PacketNumberSet packet_number_set_;
+  IntervalSet<QuicPacketNumber> packet_number_intervals_;
 };
 
 struct NET_EXPORT_PRIVATE QuicAckFrame {
diff --git a/net/quic/quic_protocol_test.cc b/net/quic/quic_protocol_test.cc
index d5ad0e9..c74d3d1 100644
--- a/net/quic/quic_protocol_test.cc
+++ b/net/quic/quic_protocol_test.cc
@@ -169,7 +169,7 @@ TEST(PacketNumberQueueTest, AddRange) {
   EXPECT_FALSE(queue.Contains(52));
   EXPECT_TRUE(queue.Contains(53));
   EXPECT_FALSE(queue.Contains(54));
-  EXPECT_EQ(51u, queue.NumPackets());
+  EXPECT_EQ(51u, queue.NumPacketsSlow());
   EXPECT_EQ(1u, queue.Min());
   EXPECT_EQ(53u, queue.Max());
 
@@ -194,7 +194,7 @@ TEST(PacketNumberQueueTest, Removal) {
   EXPECT_TRUE(queue.Contains(52));
   EXPECT_FALSE(queue.Contains(53));
   EXPECT_TRUE(queue.Contains(54));
-  EXPECT_EQ(48u, queue.NumPackets());
+  EXPECT_EQ(48u, queue.NumPacketsSlow());
   EXPECT_EQ(51u, queue.Min());
   EXPECT_EQ(99u, queue.Max());
 
@@ -208,12 +208,12 @@ TEST(PacketNumberQueueTest, Removal) {
 TEST(PacketNumberQueueTest, Empty) {
   PacketNumberQueue queue;
   EXPECT_TRUE(queue.Empty());
-  EXPECT_EQ(0u, queue.NumPackets());
+  EXPECT_EQ(0u, queue.NumPacketsSlow());
 
   queue.Add(1, 100);
   EXPECT_TRUE(queue.RemoveUpTo(100));
   EXPECT_TRUE(queue.Empty());
-  EXPECT_EQ(0u, queue.NumPackets());
+  EXPECT_EQ(0u, queue.NumPacketsSlow());
 }
 
 // Tests that logging the state of a PacketNumberQueue does not crash.
@@ -244,8 +244,8 @@ TEST(PacketNumberQueueTest, Iterators) {
   PacketNumberQueue::const_iterator it_low = queue.lower_bound(10);
   EXPECT_EQ(10u, *it_low);
 
-  PacketNumberQueue::const_iterator it_up = queue.upper_bound(60);
-  EXPECT_EQ(61u, *it_up);
+  it_low = queue.lower_bound(101);
+  EXPECT_TRUE(queue.end() == it_low);
 }
 
 }  // namespace
diff --git a/net/quic/quic_received_packet_manager_test.cc b/net/quic/quic_received_packet_manager_test.cc
index 293dba9..4cc6183 100644
--- a/net/quic/quic_received_packet_manager_test.cc
+++ b/net/quic/quic_received_packet_manager_test.cc
@@ -341,7 +341,7 @@ TEST_F(QuicReceivedPacketManagerTest, RevivedPacket) {
 
   QuicAckFrame ack;
   received_manager_.UpdateReceivedPacketInfo(&ack, QuicTime::Zero());
-  EXPECT_EQ(1u, ack.missing_packets.NumPackets());
+  EXPECT_EQ(1u, ack.missing_packets.NumPacketsSlow());
   EXPECT_EQ(2u, ack.missing_packets.Min());
   EXPECT_EQ(1u, ack.revived_packets.size());
   EXPECT_EQ(2u, *ack.revived_packets.begin());
diff --git a/net/quic/quic_sent_packet_manager.cc b/net/quic/quic_sent_packet_manager.cc
index 715bdf5..4984f70 100644
--- a/net/quic/quic_sent_packet_manager.cc
+++ b/net/quic/quic_sent_packet_manager.cc
@@ -170,9 +170,7 @@ void QuicSentPacketManager::SetFromConfig(const QuicConfig& config) {
         max(kMinSocketReceiveBuffer,
             static_cast<QuicByteCount>(config.ReceivedSocketReceiveBuffer()));
     QuicByteCount max_cwnd_bytes = static_cast<QuicByteCount>(
-        receive_buffer_bytes_ * (FLAGS_quic_use_conservative_receive_buffer
-                                     ? kConservativeReceiveBufferFraction
-                                     : kUsableRecieveBufferFraction));
+        receive_buffer_bytes_ * kConservativeReceiveBufferFraction);
     if (FLAGS_quic_limit_max_cwnd) {
       max_cwnd_bytes =
           min(max_cwnd_bytes, kMaxCongestionWindow * kDefaultTCPMSS);
diff --git a/net/quic/quic_sent_packet_manager_test.cc b/net/quic/quic_sent_packet_manager_test.cc
index afebe42..b057a1d 100644
--- a/net/quic/quic_sent_packet_manager_test.cc
+++ b/net/quic/quic_sent_packet_manager_test.cc
@@ -1591,52 +1591,8 @@ TEST_F(QuicSentPacketManagerTest, NegotiateNewRTOFromOptionsAtClient) {
   EXPECT_TRUE(QuicSentPacketManagerPeer::GetUseNewRto(&manager_));
 }
 
-TEST_F(QuicSentPacketManagerTest, NegotiateReceiveWindowFromOptions) {
-  ValueRestore<bool> old_flag(&FLAGS_quic_use_conservative_receive_buffer,
-                              false);
-  EXPECT_EQ(kDefaultSocketReceiveBuffer,
-            QuicSentPacketManagerPeer::GetReceiveWindow(&manager_));
-
-  // Try to set a size below the minimum and ensure it gets set to the min.
-  QuicConfig client_config;
-  QuicConfigPeer::SetReceivedSocketReceiveBuffer(&client_config, 1024);
-  EXPECT_CALL(*send_algorithm_, SetFromConfig(_, _));
-  EXPECT_CALL(*send_algorithm_,
-              SetMaxCongestionWindow(kMinSocketReceiveBuffer * 0.95));
-  EXPECT_CALL(*send_algorithm_, PacingRate())
-      .WillRepeatedly(Return(QuicBandwidth::Zero()));
-  EXPECT_CALL(*send_algorithm_, GetCongestionWindow())
-      .WillOnce(Return(10 * kDefaultTCPMSS));
-  EXPECT_CALL(*network_change_visitor_, OnCongestionWindowChange());
-  EXPECT_CALL(*network_change_visitor_, OnRttChange());
-  manager_.SetFromConfig(client_config);
-
-  EXPECT_EQ(kMinSocketReceiveBuffer,
-            QuicSentPacketManagerPeer::GetReceiveWindow(&manager_));
-
-  // Ensure the smaller send window only allows 16 packets to be sent.
-  for (QuicPacketNumber i = 1; i <= 16; ++i) {
-    EXPECT_CALL(*send_algorithm_, TimeUntilSend(_, _, _)).WillOnce(Return(
-        QuicTime::Delta::Zero()));
-    EXPECT_EQ(QuicTime::Delta::Zero(),
-              manager_.TimeUntilSend(clock_.Now(), HAS_RETRANSMITTABLE_DATA));
-    EXPECT_CALL(*send_algorithm_, OnPacketSent(_, BytesInFlight(), i, 1024,
-                                               HAS_RETRANSMITTABLE_DATA))
-        .WillOnce(Return(true));
-    SerializedPacket packet(CreatePacket(i, true));
-    manager_.OnPacketSent(&packet, 0, clock_.Now(), 1024, NOT_RETRANSMISSION,
-                          HAS_RETRANSMITTABLE_DATA);
-  }
-  EXPECT_CALL(*send_algorithm_, TimeUntilSend(_, _, _))
-      .WillOnce(Return(QuicTime::Delta::Infinite()));
-  EXPECT_EQ(QuicTime::Delta::Infinite(),
-            manager_.TimeUntilSend(clock_.Now(), HAS_RETRANSMITTABLE_DATA));
-}
-
 TEST_F(QuicSentPacketManagerTest,
        NegotiateConservativeReceiveWindowFromOptions) {
-  ValueRestore<bool> old_flag(&FLAGS_quic_use_conservative_receive_buffer,
-                              true);
   EXPECT_EQ(kDefaultSocketReceiveBuffer,
             QuicSentPacketManagerPeer::GetReceiveWindow(&manager_));
 
diff --git a/net/quic/quic_session.h b/net/quic/quic_session.h
index 457b2b3..da4a319 100644
--- a/net/quic/quic_session.h
+++ b/net/quic/quic_session.h
@@ -260,6 +260,7 @@ class NET_EXPORT_PRIVATE QuicSession : public QuicConnectionVisitorInterface {
       QuicStreamId largest_peer_created_stream_id) {
     largest_peer_created_stream_id_ = largest_peer_created_stream_id;
   }
+  void set_error(QuicErrorCode error) { error_ = error; }
 
  private:
   friend class test::QuicSessionPeer;
diff --git a/net/quic/test_tools/reliable_quic_stream_peer.cc b/net/quic/test_tools/reliable_quic_stream_peer.cc
index bd1ab00..a2646b7 100644
--- a/net/quic/test_tools/reliable_quic_stream_peer.cc
+++ b/net/quic/test_tools/reliable_quic_stream_peer.cc
@@ -8,6 +8,8 @@
 
 #include "net/quic/reliable_quic_stream.h"
 
+using base::StringPiece;
+
 namespace net {
 namespace test {
 
@@ -63,5 +65,14 @@ bool ReliableQuicStreamPeer::StreamContributesToConnectionFlowControl(
   return stream->stream_contributes_to_connection_flow_control_;
 }
 
+// static
+void ReliableQuicStreamPeer::WriteOrBufferData(
+    ReliableQuicStream* stream,
+    StringPiece data,
+    bool fin,
+    QuicAckNotifier::DelegateInterface* ack_notifier_delegate) {
+  stream->WriteOrBufferData(data, fin, ack_notifier_delegate);
+}
+
 }  // namespace test
 }  // namespace net
diff --git a/net/quic/test_tools/reliable_quic_stream_peer.h b/net/quic/test_tools/reliable_quic_stream_peer.h
index 8fffbbe..7ea7ff3 100644
--- a/net/quic/test_tools/reliable_quic_stream_peer.h
+++ b/net/quic/test_tools/reliable_quic_stream_peer.h
@@ -6,6 +6,8 @@
 #define NET_QUIC_TEST_TOOLS_RELIABLE_QUIC_STREAM_PEER_H_
 
 #include "base/basictypes.h"
+#include "base/strings/string_piece.h"
+#include "net/quic/quic_ack_notifier.h"
 #include "net/quic/quic_protocol.h"
 
 namespace net {
@@ -31,6 +33,12 @@ class ReliableQuicStreamPeer {
   static bool StreamContributesToConnectionFlowControl(
       ReliableQuicStream* stream);
 
+  static void WriteOrBufferData(
+      ReliableQuicStream* stream,
+      base::StringPiece data,
+      bool fin,
+      QuicAckNotifier::DelegateInterface* ack_notifier_delegate);
+
  private:
   DISALLOW_COPY_AND_ASSIGN(ReliableQuicStreamPeer);
 };
diff --git a/net/tools/quic/end_to_end_test.cc b/net/tools/quic/end_to_end_test.cc
index 1a97b90..651f499 100644
--- a/net/tools/quic/end_to_end_test.cc
+++ b/net/tools/quic/end_to_end_test.cc
@@ -159,9 +159,12 @@ vector<TestParams> GetTestParams() {
   for (const QuicTag congestion_control_tag : {kRENO, kQBIC}) {
     for (const bool use_fec : {false, true}) {
       for (const QuicVersionVector& client_versions : client_version_buckets) {
-        for (bool client_supports_stateless_rejects : {true, false}) {
-          for (bool server_uses_stateless_rejects_if_peer_supported :
-               {true, false}) {
+        // A number of end to end tests fail when stateless rejects are enabled
+        // *and* there are more than two QUIC versions.
+        // TODO(b/23745998) Re-enable client stateless reject support.
+        for (bool client_supports_stateless_rejects : {false}) {
+          // TODO(b/23745998) Re-enable server stateless reject support.
+          for (bool server_uses_stateless_rejects_if_peer_supported : {false}) {
             for (bool auto_tune_flow_control_window : {true, false}) {
               CHECK(!client_versions.empty());
               // Add an entry for server and client supporting all versions.
diff --git a/net/tools/quic/quic_dispatcher.h b/net/tools/quic/quic_dispatcher.h
index fdce9e1..1fec494 100644
--- a/net/tools/quic/quic_dispatcher.h
+++ b/net/tools/quic/quic_dispatcher.h
@@ -8,6 +8,8 @@
 #ifndef NET_TOOLS_QUIC_QUIC_DISPATCHER_H_
 #define NET_TOOLS_QUIC_QUIC_DISPATCHER_H_
 
+#include <vector>
+
 #include "base/basictypes.h"
 #include "base/containers/hash_tables.h"
 #include "base/memory/scoped_ptr.h"
@@ -249,7 +251,7 @@ class QuicDispatcher : public QuicServerSessionVisitor,
   scoped_ptr<QuicTimeWaitListManager> time_wait_list_manager_;
 
   // The list of closed but not-yet-deleted sessions.
-  std::list<QuicServerSession*> closed_session_list_;
+  std::vector<QuicServerSession*> closed_session_list_;
 
   // The helper used for all connections.
   scoped_ptr<QuicConnectionHelperInterface> helper_;
diff --git a/net/tools/quic/quic_time_wait_list_manager.cc b/net/tools/quic/quic_time_wait_list_manager.cc
index c34aa1b..68d1b9e 100644
--- a/net/tools/quic/quic_time_wait_list_manager.cc
+++ b/net/tools/quic/quic_time_wait_list_manager.cc
@@ -88,8 +88,7 @@ QuicTimeWaitListManager::QuicTimeWaitListManager(
           helper->CreateAlarm(new ConnectionIdCleanUpAlarm(this))),
       clock_(helper->GetClock()),
       writer_(writer),
-      visitor_(visitor),
-      num_connections_(0) {
+      visitor_(visitor) {
   SetConnectionIdCleanUpAlarm();
 }
 
@@ -118,7 +117,6 @@ void QuicTimeWaitListManager::AddConnectionIdToTimeWait(
     num_packets = it->second.num_packets;
     delete it->second.close_packet;
     connection_id_map_.erase(it);
-    --num_connections_;
   }
   TrimTimeWaitListIfNeeded();
   DCHECK_LT(num_connections(),
@@ -126,7 +124,6 @@ void QuicTimeWaitListManager::AddConnectionIdToTimeWait(
   ConnectionIdData data(num_packets, version, clock_->ApproximateNow(),
                         close_packet, connection_rejected_statelessly);
   connection_id_map_.insert(std::make_pair(connection_id, data));
-  ++num_connections_;
   if (new_connection_id) {
     visitor_->OnConnectionAddedToTimeWaitList(connection_id);
   }
@@ -291,7 +288,6 @@ bool QuicTimeWaitListManager::MaybeExpireOldestConnection(
   const QuicConnectionId connection_id = it->first;
   delete it->second.close_packet;
   connection_id_map_.erase(it);
-  --num_connections_;
   visitor_->OnConnectionRemovedFromTimeWaitList(connection_id);
   return true;
 }
diff --git a/net/tools/quic/quic_time_wait_list_manager.h b/net/tools/quic/quic_time_wait_list_manager.h
index c2368dc..9a9eccd 100644
--- a/net/tools/quic/quic_time_wait_list_manager.h
+++ b/net/tools/quic/quic_time_wait_list_manager.h
@@ -101,7 +101,7 @@ class QuicTimeWaitListManager : public QuicBlockedWriterInterface {
   QuicVersion GetQuicVersionFromConnectionId(QuicConnectionId connection_id);
 
   // The number of connections on the time-wait list.
-  size_t num_connections() const { return num_connections_; }
+  size_t num_connections() const { return connection_id_map_.size(); }
 
  protected:
   virtual QuicEncryptedPacket* BuildPublicReset(
@@ -190,12 +190,6 @@ class QuicTimeWaitListManager : public QuicBlockedWriterInterface {
   // Interface that manages blocked writers.
   QuicServerSessionVisitor* visitor_;
 
-  // Number of connection IDs in |connection_id_map_|. According to b/23531792,
-  // cost of size() of linked_hash_map is linear instead of constant, and a
-  // separate counter is maintained so that cost of num_connections() is
-  // constant. TODO(b/23531792): Remove this counter.
-  size_t num_connections_;
-
   DISALLOW_COPY_AND_ASSIGN(QuicTimeWaitListManager);
 };