Internal QUICHE change
PiperOrigin-RevId: 278613873
Change-Id: I7362668613bfb081adefa1fcb185c0b0f3df74ac
diff --git a/quic/core/frames/quic_ack_frame.cc b/quic/core/frames/quic_ack_frame.cc
index 389f1c0..72e806c 100644
--- a/quic/core/frames/quic_ack_frame.cc
+++ b/quic/core/frames/quic_ack_frame.cc
@@ -15,13 +15,6 @@
const QuicPacketCount kMaxPrintRange = 128;
-uint64_t PacketNumberIntervalLength(
- const QuicInterval<QuicPacketNumber>& interval) {
- if (interval.Empty()) {
- return 0u;
- }
- return interval.max() - interval.min();
-}
} // namespace
bool IsAwaitingPacket(const QuicAckFrame& ack_frame,
@@ -86,77 +79,8 @@
if (!packet_number.IsInitialized()) {
return;
}
- // Check if the deque is empty
- if (packet_number_deque_.empty()) {
- packet_number_deque_.push_front(
- QuicInterval<QuicPacketNumber>(packet_number, packet_number + 1));
- return;
- }
- QuicInterval<QuicPacketNumber> back = packet_number_deque_.back();
-
- // Check for the typical case,
- // when the next packet in order is acked
- if (back.max() == packet_number) {
- packet_number_deque_.back().SetMax(packet_number + 1);
- return;
- }
- // Check if the next packet in order is skipped
- if (back.max() < packet_number) {
- packet_number_deque_.push_back(
- QuicInterval<QuicPacketNumber>(packet_number, packet_number + 1));
- return;
- }
-
- QuicInterval<QuicPacketNumber> front = packet_number_deque_.front();
- // Check if the packet can be popped on the front
- if (front.min() > packet_number + 1) {
- packet_number_deque_.push_front(
- QuicInterval<QuicPacketNumber>(packet_number, packet_number + 1));
- return;
- }
- if (front.min() == packet_number + 1) {
- packet_number_deque_.front().SetMin(packet_number);
- return;
- }
-
- int i = packet_number_deque_.size() - 1;
- // Iterating through the queue backwards
- // to find a proper place for the packet
- while (i >= 0) {
- QuicInterval<QuicPacketNumber> packet_interval = packet_number_deque_[i];
- DCHECK(packet_interval.min() < packet_interval.max());
- // Check if the packet is contained in an interval already
- if (packet_interval.Contains(packet_number)) {
- return;
- }
-
- // Check if the packet can extend an interval.
- if (packet_interval.max() == packet_number) {
- packet_number_deque_[i].SetMax(packet_number + 1);
- return;
- }
- // Check if the packet can extend an interval
- // and merge two intervals if needed.
- // There is no need to merge an interval in the previous
- // if statement, as all merges will happen here.
- if (packet_interval.min() == packet_number + 1) {
- packet_number_deque_[i].SetMin(packet_number);
- if (i > 0 && packet_number == packet_number_deque_[i - 1].max()) {
- packet_number_deque_[i - 1].SetMax(packet_interval.max());
- packet_number_deque_.erase(packet_number_deque_.begin() + i);
- }
- return;
- }
-
- // Check if we need to make a new interval for the packet
- if (packet_interval.max() < packet_number + 1) {
- packet_number_deque_.insert(
- packet_number_deque_.begin() + i + 1,
- QuicInterval<QuicPacketNumber>(packet_number, packet_number + 1));
- return;
- }
- i--;
- }
+ packet_number_intervals_.AddOptimizedForAppend(packet_number,
+ packet_number + 1);
}
void PacketNumberQueue::AddRange(QuicPacketNumber lower,
@@ -164,136 +88,93 @@
if (!lower.IsInitialized() || !higher.IsInitialized() || lower >= higher) {
return;
}
- if (packet_number_deque_.empty()) {
- packet_number_deque_.push_front(
- QuicInterval<QuicPacketNumber>(lower, higher));
- return;
- }
- QuicInterval<QuicPacketNumber> back = packet_number_deque_.back();
- if (back.max() == lower) {
- // Check for the typical case,
- // when the next packet in order is acked
- packet_number_deque_.back().SetMax(higher);
- return;
- }
- if (back.max() < lower) {
- // Check if the next packet in order is skipped
- packet_number_deque_.push_back(
- QuicInterval<QuicPacketNumber>(lower, higher));
- return;
- }
- QuicInterval<QuicPacketNumber> front = packet_number_deque_.front();
- // Check if the packets are being added in reverse order
- if (front.min() == higher) {
- packet_number_deque_.front().SetMin(lower);
- } else if (front.min() > higher) {
- packet_number_deque_.push_front(
- QuicInterval<QuicPacketNumber>(lower, higher));
+ const auto new_interval = QuicInterval<QuicPacketNumber>(lower, higher);
- } else {
+ if (!packet_number_intervals_.Empty() &&
+ packet_number_intervals_.SpanningInterval().Intersects(new_interval)) {
+ // TODO(wub): Remove this QUIC_BUG, or the AddRange method entirely.
// Ranges must be above or below all existing ranges.
QUIC_BUG << "AddRange only supports adding packets above or below the "
<< "current min:" << Min() << " and max:" << Max()
<< ", but adding [" << lower << "," << higher << ")";
+ return;
}
+
+ packet_number_intervals_.AddOptimizedForAppend(new_interval);
}
bool PacketNumberQueue::RemoveUpTo(QuicPacketNumber higher) {
if (!higher.IsInitialized() || Empty()) {
return false;
}
- const QuicPacketNumber old_min = Min();
- while (!packet_number_deque_.empty()) {
- QuicInterval<QuicPacketNumber> front = packet_number_deque_.front();
- if (front.max() < higher) {
- packet_number_deque_.pop_front();
- } else if (front.min() < higher && front.max() >= higher) {
- packet_number_deque_.front().SetMin(higher);
- if (front.max() == higher) {
- packet_number_deque_.pop_front();
- }
- break;
- } else {
- break;
- }
- }
-
- return Empty() || old_min != Min();
+ return packet_number_intervals_.TrimLessThan(higher);
}
void PacketNumberQueue::RemoveSmallestInterval() {
- QUIC_BUG_IF(packet_number_deque_.size() < 2)
+ // TODO(wub): Move this QUIC_BUG to upper level.
+ QUIC_BUG_IF(packet_number_intervals_.Size() < 2)
<< (Empty() ? "No intervals to remove."
: "Can't remove the last interval.");
- packet_number_deque_.pop_front();
+ packet_number_intervals_.PopFront();
}
void PacketNumberQueue::Clear() {
- packet_number_deque_.clear();
+ packet_number_intervals_.Clear();
}
bool PacketNumberQueue::Contains(QuicPacketNumber packet_number) const {
- if (!packet_number.IsInitialized() || packet_number_deque_.empty()) {
+ if (!packet_number.IsInitialized()) {
return false;
}
- if (packet_number_deque_.front().min() > packet_number ||
- packet_number_deque_.back().max() <= packet_number) {
- return false;
- }
- for (QuicInterval<QuicPacketNumber> interval : packet_number_deque_) {
- if (interval.Contains(packet_number)) {
- return true;
- }
- }
- return false;
+ return packet_number_intervals_.Contains(packet_number);
}
bool PacketNumberQueue::Empty() const {
- return packet_number_deque_.empty();
+ return packet_number_intervals_.Empty();
}
QuicPacketNumber PacketNumberQueue::Min() const {
DCHECK(!Empty());
- return packet_number_deque_.front().min();
+ return packet_number_intervals_.begin()->min();
}
QuicPacketNumber PacketNumberQueue::Max() const {
DCHECK(!Empty());
- return packet_number_deque_.back().max() - 1;
+ return packet_number_intervals_.rbegin()->max() - 1;
}
QuicPacketCount PacketNumberQueue::NumPacketsSlow() const {
QuicPacketCount n_packets = 0;
- for (QuicInterval<QuicPacketNumber> interval : packet_number_deque_) {
- n_packets += PacketNumberIntervalLength(interval);
+ for (const auto& interval : packet_number_intervals_) {
+ n_packets += interval.Length();
}
return n_packets;
}
size_t PacketNumberQueue::NumIntervals() const {
- return packet_number_deque_.size();
+ return packet_number_intervals_.Size();
}
PacketNumberQueue::const_iterator PacketNumberQueue::begin() const {
- return packet_number_deque_.begin();
+ return packet_number_intervals_.begin();
}
PacketNumberQueue::const_iterator PacketNumberQueue::end() const {
- return packet_number_deque_.end();
+ return packet_number_intervals_.end();
}
PacketNumberQueue::const_reverse_iterator PacketNumberQueue::rbegin() const {
- return packet_number_deque_.rbegin();
+ return packet_number_intervals_.rbegin();
}
PacketNumberQueue::const_reverse_iterator PacketNumberQueue::rend() const {
- return packet_number_deque_.rend();
+ return packet_number_intervals_.rend();
}
QuicPacketCount PacketNumberQueue::LastIntervalLength() const {
DCHECK(!Empty());
- return PacketNumberIntervalLength(packet_number_deque_.back());
+ return packet_number_intervals_.rbegin()->Length();
}
// Largest min...max range for packet numbers where we print the numbers
diff --git a/quic/core/frames/quic_ack_frame.h b/quic/core/frames/quic_ack_frame.h
index 771d93e..18675a8 100644
--- a/quic/core/frames/quic_ack_frame.h
+++ b/quic/core/frames/quic_ack_frame.h
@@ -8,6 +8,7 @@
#include <ostream>
#include "net/third_party/quiche/src/quic/core/quic_interval.h"
+#include "net/third_party/quiche/src/quic/core/quic_interval_set.h"
#include "net/third_party/quiche/src/quic/core/quic_types.h"
#include "net/third_party/quiche/src/quic/platform/api/quic_containers.h"
#include "net/third_party/quiche/src/quic/platform/api/quic_export.h"
@@ -28,9 +29,8 @@
PacketNumberQueue& operator=(const PacketNumberQueue& other);
PacketNumberQueue& operator=(PacketNumberQueue&& other);
- typedef QuicDeque<QuicInterval<QuicPacketNumber>>::const_iterator
- const_iterator;
- typedef QuicDeque<QuicInterval<QuicPacketNumber>>::const_reverse_iterator
+ typedef QuicIntervalSet<QuicPacketNumber>::const_iterator const_iterator;
+ typedef QuicIntervalSet<QuicPacketNumber>::const_reverse_iterator
const_reverse_iterator;
// Adds |packet_number| to the set of packets in the queue.
@@ -38,6 +38,7 @@
// Adds packets between [lower, higher) to the set of packets in the queue. It
// is undefined behavior to call this with |higher| < |lower|.
+ // NOTE(wub): Only used in tests as of Nov 2019.
void AddRange(QuicPacketNumber lower, QuicPacketNumber higher);
// Removes packets with values less than |higher| from the set of packets in
@@ -86,7 +87,7 @@
const PacketNumberQueue& q);
private:
- QuicDeque<QuicInterval<QuicPacketNumber>> packet_number_deque_;
+ QuicIntervalSet<QuicPacketNumber> packet_number_intervals_;
};
struct QUIC_EXPORT_PRIVATE QuicAckFrame {
diff --git a/quic/core/quic_framer.cc b/quic/core/quic_framer.cc
index 761645e..353d4e6 100644
--- a/quic/core/quic_framer.cc
+++ b/quic/core/quic_framer.cc
@@ -148,6 +148,7 @@
return (Delta(target, a) < Delta(target, b)) ? a : b;
}
+// TODO(wub): Remove this function & replace the callsites to interval.Length().
uint64_t PacketNumberIntervalLength(
const QuicInterval<QuicPacketNumber>& interval) {
if (interval.Empty()) {
diff --git a/quic/core/quic_interval_set.h b/quic/core/quic_interval_set.h
index 0465a01..28153c1 100644
--- a/quic/core/quic_interval_set.h
+++ b/quic/core/quic_interval_set.h
@@ -73,6 +73,7 @@
struct QUIC_NO_EXPORT IntervalLess {
bool operator()(const value_type& a, const value_type& b) const;
};
+ // TODO(wub): Switch to absl::btree_set when it is available in Chromium.
typedef std::set<value_type, IntervalLess> Set;
public:
@@ -152,6 +153,49 @@
// TODO(wub): Similar to AddOptimizedForAppend, we can also have a
// AddOptimizedForPrepend if there is a use case.
+ // Remove the first interval.
+ // REQUIRES: !Empty()
+ void PopFront() {
+ DCHECK(!Empty());
+ intervals_.erase(intervals_.begin());
+ }
+
+ // Trim all values that is smaller than |value|. Which means
+ // a) If all values in an interval is smaller than |value|, the entire
+ // interval is removed.
+ // b) If some but not all values in an interval is smaller than |value|, the
+ // min of that interval is raised to |value|.
+ // Returns true if some intervals are trimmed.
+ bool TrimLessThan(const T& value) {
+ // Number of intervals that are fully or partially trimmed.
+ size_t num_intervals_trimmed = 0;
+
+ while (!intervals_.empty()) {
+ const_iterator first_interval = intervals_.begin();
+ if (first_interval->min() >= value) {
+ break;
+ }
+
+ ++num_intervals_trimmed;
+
+ if (first_interval->max() <= value) {
+ // a) Trim the entire interval.
+ intervals_.erase(first_interval);
+ continue;
+ }
+
+ // b) Trim a prefix of the interval.
+ //
+ // Set does not allow in-place updates due to the potential of violating
+ // its ordering requirements. But increasing the min of the first interval
+ // will not break the ordering, hence the const_cast.
+ const_cast<value_type*>(&(*first_interval))->SetMin(value);
+ break;
+ }
+
+ return num_intervals_trimmed != 0;
+ }
+
// Returns true if this QuicIntervalSet is empty.
bool Empty() const { return intervals_.empty(); }
diff --git a/quic/core/quic_interval_set_test.cc b/quic/core/quic_interval_set_test.cc
index 3fb483a..efa8fe7 100644
--- a/quic/core/quic_interval_set_test.cc
+++ b/quic/core/quic_interval_set_test.cc
@@ -191,6 +191,47 @@
EXPECT_TRUE(Check(iset, 3, 100, 150, 199, 250, 251, 350));
}
+TEST_F(QuicIntervalSetTest, PopFront) {
+ QuicIntervalSet<int> iset{{100, 200}, {400, 500}, {700, 800}};
+ EXPECT_TRUE(Check(iset, 3, 100, 200, 400, 500, 700, 800));
+
+ iset.PopFront();
+ EXPECT_TRUE(Check(iset, 2, 400, 500, 700, 800));
+
+ iset.PopFront();
+ EXPECT_TRUE(Check(iset, 1, 700, 800));
+
+ iset.PopFront();
+ EXPECT_TRUE(iset.Empty());
+}
+
+TEST_F(QuicIntervalSetTest, TrimLessThan) {
+ QuicIntervalSet<int> iset{{100, 200}, {400, 500}, {700, 800}};
+ EXPECT_TRUE(Check(iset, 3, 100, 200, 400, 500, 700, 800));
+
+ EXPECT_FALSE(iset.TrimLessThan(99));
+ EXPECT_FALSE(iset.TrimLessThan(100));
+ EXPECT_TRUE(Check(iset, 3, 100, 200, 400, 500, 700, 800));
+
+ EXPECT_TRUE(iset.TrimLessThan(101));
+ EXPECT_TRUE(Check(iset, 3, 101, 200, 400, 500, 700, 800));
+
+ EXPECT_TRUE(iset.TrimLessThan(199));
+ EXPECT_TRUE(Check(iset, 3, 199, 200, 400, 500, 700, 800));
+
+ EXPECT_TRUE(iset.TrimLessThan(450));
+ EXPECT_TRUE(Check(iset, 2, 450, 500, 700, 800));
+
+ EXPECT_TRUE(iset.TrimLessThan(500));
+ EXPECT_TRUE(Check(iset, 1, 700, 800));
+
+ EXPECT_TRUE(iset.TrimLessThan(801));
+ EXPECT_TRUE(iset.Empty());
+
+ EXPECT_FALSE(iset.TrimLessThan(900));
+ EXPECT_TRUE(iset.Empty());
+}
+
TEST_F(QuicIntervalSetTest, QuicIntervalSetBasic) {
// Test Add, Get, Contains and Find
QuicIntervalSet<int> iset;
