Add a data structure that is structured in the same way as the UnackedPacketMap, in hope we can rep…

net/quic/core/packet_number_indexed_queue_test.cc

+// 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/quic/core/packet_number_indexed_queue.h"
+
+#include <limits>
+#include <map>
+#include <string>
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+using std::string;
+
+namespace net {
+namespace {
+
+class PacketNumberIndexedQueueTest : public ::testing::Test {
+ public:
+  PacketNumberIndexedQueueTest() {}
+
+ protected:
+  PacketNumberIndexedQueue<string> queue_;
+};
+
+TEST_F(PacketNumberIndexedQueueTest, InitialState) {
+  EXPECT_TRUE(queue_.IsEmpty());
+  EXPECT_EQ(0u, queue_.first_packet());
+  EXPECT_EQ(0u, queue_.last_packet());
+  EXPECT_EQ(0u, queue_.number_of_present_entries());
+  EXPECT_EQ(0u, queue_.entry_slots_used());
+}
+
+TEST_F(PacketNumberIndexedQueueTest, InsertingContinuousElements) {
+  ASSERT_TRUE(queue_.Emplace(1001, "one"));
+  EXPECT_EQ("one", *queue_.GetEntry(1001));
+
+  ASSERT_TRUE(queue_.Emplace(1002, "two"));
+  EXPECT_EQ("two", *queue_.GetEntry(1002));
+
+  EXPECT_FALSE(queue_.IsEmpty());
+  EXPECT_EQ(1001u, queue_.first_packet());
+  EXPECT_EQ(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(1001, "one");
+
+  ASSERT_TRUE(queue_.Emplace(1003, "three"));
+  EXPECT_EQ(nullptr, queue_.GetEntry(1002));
+  EXPECT_EQ("three", *queue_.GetEntry(1003));
+
+  EXPECT_EQ(1001u, queue_.first_packet());
+  EXPECT_EQ(1003u, queue_.last_packet());
+  EXPECT_EQ(2u, queue_.number_of_present_entries());
+  EXPECT_EQ(3u, queue_.entry_slots_used());
+
+  ASSERT_FALSE(queue_.Emplace(1002, "two"));
+}
+
+TEST_F(PacketNumberIndexedQueueTest, InsertingIntoPast) {
+  queue_.Emplace(1001, "one");
+  EXPECT_FALSE(queue_.Emplace(1000, "zero"));
+}
+
+TEST_F(PacketNumberIndexedQueueTest, InsertingDuplicate) {
+  queue_.Emplace(1001, "one");
+  EXPECT_FALSE(queue_.Emplace(1001, "one"));
+}
+
+TEST_F(PacketNumberIndexedQueueTest, RemoveInTheMiddle) {
+  queue_.Emplace(1001, "one");
+  queue_.Emplace(1002, "two");
+  queue_.Emplace(1003, "three");
+
+  ASSERT_TRUE(queue_.Remove(1002));
+  EXPECT_EQ(nullptr, queue_.GetEntry(1002));
+
+  EXPECT_EQ(1001u, queue_.first_packet());
+  EXPECT_EQ(1003u, queue_.last_packet());
+  EXPECT_EQ(2u, queue_.number_of_present_entries());
+  EXPECT_EQ(3u, queue_.entry_slots_used());
+
+  EXPECT_FALSE(queue_.Emplace(1002, "two"));
+  EXPECT_TRUE(queue_.Emplace(1004, "four"));
+}
+
+TEST_F(PacketNumberIndexedQueueTest, RemoveAtImmediateEdges) {
+  queue_.Emplace(1001, "one");
+  queue_.Emplace(1002, "two");
+  queue_.Emplace(1003, "three");
+  ASSERT_TRUE(queue_.Remove(1001));
+  EXPECT_EQ(nullptr, queue_.GetEntry(1001));
+  ASSERT_TRUE(queue_.Remove(1003));
+  EXPECT_EQ(nullptr, queue_.GetEntry(1003));
+
+  EXPECT_EQ(1002u, queue_.first_packet());
+  EXPECT_EQ(1003u, queue_.last_packet());
+  EXPECT_EQ(1u, queue_.number_of_present_entries());
+  EXPECT_EQ(2u, queue_.entry_slots_used());
+
+  EXPECT_TRUE(queue_.Emplace(1004, "four"));
+}
+
+TEST_F(PacketNumberIndexedQueueTest, RemoveAtDistantFront) {
+  queue_.Emplace(1001, "one");
+  queue_.Emplace(1002, "one (kinda)");
+  queue_.Emplace(2001, "two");
+
+  EXPECT_EQ(1001u, queue_.first_packet());
+  EXPECT_EQ(2001u, queue_.last_packet());
+  EXPECT_EQ(3u, queue_.number_of_present_entries());
+  EXPECT_EQ(1001u, queue_.entry_slots_used());
+
+  ASSERT_TRUE(queue_.Remove(1002));
+  EXPECT_EQ(1001u, queue_.first_packet());
+  EXPECT_EQ(2001u, queue_.last_packet());
+  EXPECT_EQ(2u, queue_.number_of_present_entries());
+  EXPECT_EQ(1001u, queue_.entry_slots_used());
+
+  ASSERT_TRUE(queue_.Remove(1001));
+  EXPECT_EQ(2001u, queue_.first_packet());
+  EXPECT_EQ(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(1001, "one");
+  queue_.Emplace(2001, "two");
+
+  EXPECT_EQ(1001u, queue_.first_packet());
+  EXPECT_EQ(2001u, queue_.last_packet());
+
+  ASSERT_TRUE(queue_.Remove(2001));
+  EXPECT_EQ(1001u, queue_.first_packet());
+  EXPECT_EQ(2001u, queue_.last_packet());
+}
+
+TEST_F(PacketNumberIndexedQueueTest, ClearAndRepopulate) {
+  queue_.Emplace(1001, "one");
+  queue_.Emplace(2001, "two");
+
+  ASSERT_TRUE(queue_.Remove(1001));
+  ASSERT_TRUE(queue_.Remove(2001));
+  EXPECT_TRUE(queue_.IsEmpty());
+  EXPECT_EQ(0u, queue_.first_packet());
+  EXPECT_EQ(0u, queue_.last_packet());
+
+  EXPECT_TRUE(queue_.Emplace(101, "one"));
+  EXPECT_TRUE(queue_.Emplace(201, "two"));
+  EXPECT_EQ(101u, queue_.first_packet());
+  EXPECT_EQ(201u, queue_.last_packet());
+}
+
+TEST_F(PacketNumberIndexedQueueTest, FailToRemoveElementsThatNeverExisted) {
+  ASSERT_FALSE(queue_.Remove(1000));
+  queue_.Emplace(1001, "one");
+  ASSERT_FALSE(queue_.Remove(1000));
+  ASSERT_FALSE(queue_.Remove(1002));
+}
+
+TEST_F(PacketNumberIndexedQueueTest, FailToRemoveElementsTwice) {
+  queue_.Emplace(1001, "one");
+  ASSERT_TRUE(queue_.Remove(1001));
+  ASSERT_FALSE(queue_.Remove(1001));
+  ASSERT_FALSE(queue_.Remove(1001));
+}
+
+}  // namespace
+}  // namespace net