Project import generated by Copybara.
PiperOrigin-RevId: 237361882
Change-Id: I109a68f44db867b20f8c6a7732b0ce657133e52a
diff --git a/quic/core/packet_number_indexed_queue_test.cc b/quic/core/packet_number_indexed_queue_test.cc
new file mode 100644
index 0000000..294d2a4
--- /dev/null
+++ b/quic/core/packet_number_indexed_queue_test.cc
@@ -0,0 +1,179 @@
+// Copyright (c) 2017 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/third_party/quiche/src/quic/core/packet_number_indexed_queue.h"
+
+#include <limits>
+#include <map>
+
+#include "net/third_party/quiche/src/quic/platform/api/quic_string.h"
+#include "net/third_party/quiche/src/quic/platform/api/quic_test.h"
+
+namespace quic {
+namespace {
+
+class PacketNumberIndexedQueueTest : public QuicTest {
+ public:
+ PacketNumberIndexedQueueTest() {}
+
+ protected:
+ PacketNumberIndexedQueue<QuicString> queue_;
+};
+
+TEST_F(PacketNumberIndexedQueueTest, InitialState) {
+ EXPECT_TRUE(queue_.IsEmpty());
+ EXPECT_FALSE(queue_.first_packet().IsInitialized());
+ EXPECT_FALSE(queue_.last_packet().IsInitialized());
+ EXPECT_EQ(0u, queue_.number_of_present_entries());
+ EXPECT_EQ(0u, queue_.entry_slots_used());
+}
+
+TEST_F(PacketNumberIndexedQueueTest, InsertingContinuousElements) {
+ ASSERT_TRUE(queue_.Emplace(QuicPacketNumber(1001), "one"));
+ EXPECT_EQ("one", *queue_.GetEntry(QuicPacketNumber(1001)));
+
+ ASSERT_TRUE(queue_.Emplace(QuicPacketNumber(1002), "two"));
+ EXPECT_EQ("two", *queue_.GetEntry(QuicPacketNumber(1002)));
+
+ EXPECT_FALSE(queue_.IsEmpty());
+ EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet());
+ EXPECT_EQ(QuicPacketNumber(1002u), queue_.last_packet());
+ EXPECT_EQ(2u, queue_.number_of_present_entries());
+ EXPECT_EQ(2u, queue_.entry_slots_used());
+}
+
+TEST_F(PacketNumberIndexedQueueTest, InsertingOutOfOrder) {
+ queue_.Emplace(QuicPacketNumber(1001), "one");
+
+ ASSERT_TRUE(queue_.Emplace(QuicPacketNumber(1003), "three"));
+ EXPECT_EQ(nullptr, queue_.GetEntry(QuicPacketNumber(1002)));
+ EXPECT_EQ("three", *queue_.GetEntry(QuicPacketNumber(1003)));
+
+ EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet());
+ EXPECT_EQ(QuicPacketNumber(1003u), queue_.last_packet());
+ EXPECT_EQ(2u, queue_.number_of_present_entries());
+ EXPECT_EQ(3u, queue_.entry_slots_used());
+
+ ASSERT_FALSE(queue_.Emplace(QuicPacketNumber(1002), "two"));
+}
+
+TEST_F(PacketNumberIndexedQueueTest, InsertingIntoPast) {
+ queue_.Emplace(QuicPacketNumber(1001), "one");
+ EXPECT_FALSE(queue_.Emplace(QuicPacketNumber(1000), "zero"));
+}
+
+TEST_F(PacketNumberIndexedQueueTest, InsertingDuplicate) {
+ queue_.Emplace(QuicPacketNumber(1001), "one");
+ EXPECT_FALSE(queue_.Emplace(QuicPacketNumber(1001), "one"));
+}
+
+TEST_F(PacketNumberIndexedQueueTest, RemoveInTheMiddle) {
+ queue_.Emplace(QuicPacketNumber(1001), "one");
+ queue_.Emplace(QuicPacketNumber(1002), "two");
+ queue_.Emplace(QuicPacketNumber(1003), "three");
+
+ ASSERT_TRUE(queue_.Remove(QuicPacketNumber(1002)));
+ EXPECT_EQ(nullptr, queue_.GetEntry(QuicPacketNumber(1002)));
+
+ EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet());
+ EXPECT_EQ(QuicPacketNumber(1003u), queue_.last_packet());
+ EXPECT_EQ(2u, queue_.number_of_present_entries());
+ EXPECT_EQ(3u, queue_.entry_slots_used());
+
+ EXPECT_FALSE(queue_.Emplace(QuicPacketNumber(1002), "two"));
+ EXPECT_TRUE(queue_.Emplace(QuicPacketNumber(1004), "four"));
+}
+
+TEST_F(PacketNumberIndexedQueueTest, RemoveAtImmediateEdges) {
+ queue_.Emplace(QuicPacketNumber(1001), "one");
+ queue_.Emplace(QuicPacketNumber(1002), "two");
+ queue_.Emplace(QuicPacketNumber(1003), "three");
+ ASSERT_TRUE(queue_.Remove(QuicPacketNumber(1001)));
+ EXPECT_EQ(nullptr, queue_.GetEntry(QuicPacketNumber(1001)));
+ ASSERT_TRUE(queue_.Remove(QuicPacketNumber(1003)));
+ EXPECT_EQ(nullptr, queue_.GetEntry(QuicPacketNumber(1003)));
+
+ EXPECT_EQ(QuicPacketNumber(1002u), queue_.first_packet());
+ EXPECT_EQ(QuicPacketNumber(1003u), queue_.last_packet());
+ EXPECT_EQ(1u, queue_.number_of_present_entries());
+ EXPECT_EQ(2u, queue_.entry_slots_used());
+
+ EXPECT_TRUE(queue_.Emplace(QuicPacketNumber(1004), "four"));
+}
+
+TEST_F(PacketNumberIndexedQueueTest, RemoveAtDistantFront) {
+ queue_.Emplace(QuicPacketNumber(1001), "one");
+ queue_.Emplace(QuicPacketNumber(1002), "one (kinda)");
+ queue_.Emplace(QuicPacketNumber(2001), "two");
+
+ EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet());
+ EXPECT_EQ(QuicPacketNumber(2001u), queue_.last_packet());
+ EXPECT_EQ(3u, queue_.number_of_present_entries());
+ EXPECT_EQ(1001u, queue_.entry_slots_used());
+
+ ASSERT_TRUE(queue_.Remove(QuicPacketNumber(1002)));
+ EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet());
+ EXPECT_EQ(QuicPacketNumber(2001u), queue_.last_packet());
+ EXPECT_EQ(2u, queue_.number_of_present_entries());
+ EXPECT_EQ(1001u, queue_.entry_slots_used());
+
+ ASSERT_TRUE(queue_.Remove(QuicPacketNumber(1001)));
+ EXPECT_EQ(QuicPacketNumber(2001u), queue_.first_packet());
+ EXPECT_EQ(QuicPacketNumber(2001u), queue_.last_packet());
+ EXPECT_EQ(1u, queue_.number_of_present_entries());
+ EXPECT_EQ(1u, queue_.entry_slots_used());
+}
+
+TEST_F(PacketNumberIndexedQueueTest, RemoveAtDistantBack) {
+ queue_.Emplace(QuicPacketNumber(1001), "one");
+ queue_.Emplace(QuicPacketNumber(2001), "two");
+
+ EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet());
+ EXPECT_EQ(QuicPacketNumber(2001u), queue_.last_packet());
+
+ ASSERT_TRUE(queue_.Remove(QuicPacketNumber(2001)));
+ EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet());
+ EXPECT_EQ(QuicPacketNumber(2001u), queue_.last_packet());
+}
+
+TEST_F(PacketNumberIndexedQueueTest, ClearAndRepopulate) {
+ queue_.Emplace(QuicPacketNumber(1001), "one");
+ queue_.Emplace(QuicPacketNumber(2001), "two");
+
+ ASSERT_TRUE(queue_.Remove(QuicPacketNumber(1001)));
+ ASSERT_TRUE(queue_.Remove(QuicPacketNumber(2001)));
+ EXPECT_TRUE(queue_.IsEmpty());
+ EXPECT_FALSE(queue_.first_packet().IsInitialized());
+ EXPECT_FALSE(queue_.last_packet().IsInitialized());
+
+ EXPECT_TRUE(queue_.Emplace(QuicPacketNumber(101), "one"));
+ EXPECT_TRUE(queue_.Emplace(QuicPacketNumber(201), "two"));
+ EXPECT_EQ(QuicPacketNumber(101u), queue_.first_packet());
+ EXPECT_EQ(QuicPacketNumber(201u), queue_.last_packet());
+}
+
+TEST_F(PacketNumberIndexedQueueTest, FailToRemoveElementsThatNeverExisted) {
+ ASSERT_FALSE(queue_.Remove(QuicPacketNumber(1000)));
+ queue_.Emplace(QuicPacketNumber(1001), "one");
+ ASSERT_FALSE(queue_.Remove(QuicPacketNumber(1000)));
+ ASSERT_FALSE(queue_.Remove(QuicPacketNumber(1002)));
+}
+
+TEST_F(PacketNumberIndexedQueueTest, FailToRemoveElementsTwice) {
+ queue_.Emplace(QuicPacketNumber(1001), "one");
+ ASSERT_TRUE(queue_.Remove(QuicPacketNumber(1001)));
+ ASSERT_FALSE(queue_.Remove(QuicPacketNumber(1001)));
+ ASSERT_FALSE(queue_.Remove(QuicPacketNumber(1001)));
+}
+
+TEST_F(PacketNumberIndexedQueueTest, ConstGetter) {
+ queue_.Emplace(QuicPacketNumber(1001), "one");
+ const auto& const_queue = queue_;
+
+ EXPECT_EQ("one", *const_queue.GetEntry(QuicPacketNumber(1001)));
+ EXPECT_EQ(nullptr, const_queue.GetEntry(QuicPacketNumber(1002)));
+}
+
+} // namespace
+} // namespace quic
