| // 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 "quiche/quic/core/packet_number_indexed_queue.h" |
| |
| #include <limits> |
| #include <map> |
| #include <string> |
| |
| #include "quiche/quic/core/quic_packet_number.h" |
| #include "quiche/quic/platform/api/quic_test.h" |
| |
| namespace quic::test { |
| namespace { |
| |
| class PacketNumberIndexedQueueTest : public QuicTest { |
| public: |
| PacketNumberIndexedQueueTest() {} |
| |
| protected: |
| PacketNumberIndexedQueue<std::string> 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, RemoveUpTo) { |
| queue_.Emplace(QuicPacketNumber(1001), "one"); |
| queue_.Emplace(QuicPacketNumber(2001), "two"); |
| EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet()); |
| EXPECT_EQ(2u, queue_.number_of_present_entries()); |
| |
| queue_.RemoveUpTo(QuicPacketNumber(1001)); |
| EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet()); |
| EXPECT_EQ(2u, queue_.number_of_present_entries()); |
| |
| // Remove up to 1100, since [1100, 2001) are !present, they should be cleaned |
| // up from the front. |
| queue_.RemoveUpTo(QuicPacketNumber(1100)); |
| EXPECT_EQ(QuicPacketNumber(2001u), queue_.first_packet()); |
| EXPECT_EQ(1u, queue_.number_of_present_entries()); |
| |
| queue_.RemoveUpTo(QuicPacketNumber(2001)); |
| EXPECT_EQ(QuicPacketNumber(2001u), queue_.first_packet()); |
| EXPECT_EQ(1u, queue_.number_of_present_entries()); |
| |
| queue_.RemoveUpTo(QuicPacketNumber(2002)); |
| EXPECT_FALSE(queue_.first_packet().IsInitialized()); |
| EXPECT_EQ(0u, queue_.number_of_present_entries()); |
| } |
| |
| 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::test |