1 // Copyright (c) 2017 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #include "net/third_party/quiche/src/quic/core/packet_number_indexed_queue.h"
6 
7 #include <limits>
8 #include <map>
9 #include <string>
10 
11 #include "net/third_party/quiche/src/quic/core/quic_packet_number.h"
12 #include "net/third_party/quiche/src/quic/platform/api/quic_test.h"
13 
14 namespace quic {
15 namespace {
16 
17 class PacketNumberIndexedQueueTest : public QuicTest {
18  public:
PacketNumberIndexedQueueTest()19   PacketNumberIndexedQueueTest() {}
20 
21  protected:
22   PacketNumberIndexedQueue<std::string> queue_;
23 };
24 
TEST_F(PacketNumberIndexedQueueTest,InitialState)25 TEST_F(PacketNumberIndexedQueueTest, InitialState) {
26   EXPECT_TRUE(queue_.IsEmpty());
27   EXPECT_FALSE(queue_.first_packet().IsInitialized());
28   EXPECT_FALSE(queue_.last_packet().IsInitialized());
29   EXPECT_EQ(0u, queue_.number_of_present_entries());
30   EXPECT_EQ(0u, queue_.entry_slots_used());
31 }
32 
TEST_F(PacketNumberIndexedQueueTest,InsertingContinuousElements)33 TEST_F(PacketNumberIndexedQueueTest, InsertingContinuousElements) {
34   ASSERT_TRUE(queue_.Emplace(QuicPacketNumber(1001), "one"));
35   EXPECT_EQ("one", *queue_.GetEntry(QuicPacketNumber(1001)));
36 
37   ASSERT_TRUE(queue_.Emplace(QuicPacketNumber(1002), "two"));
38   EXPECT_EQ("two", *queue_.GetEntry(QuicPacketNumber(1002)));
39 
40   EXPECT_FALSE(queue_.IsEmpty());
41   EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet());
42   EXPECT_EQ(QuicPacketNumber(1002u), queue_.last_packet());
43   EXPECT_EQ(2u, queue_.number_of_present_entries());
44   EXPECT_EQ(2u, queue_.entry_slots_used());
45 }
46 
TEST_F(PacketNumberIndexedQueueTest,InsertingOutOfOrder)47 TEST_F(PacketNumberIndexedQueueTest, InsertingOutOfOrder) {
48   queue_.Emplace(QuicPacketNumber(1001), "one");
49 
50   ASSERT_TRUE(queue_.Emplace(QuicPacketNumber(1003), "three"));
51   EXPECT_EQ(nullptr, queue_.GetEntry(QuicPacketNumber(1002)));
52   EXPECT_EQ("three", *queue_.GetEntry(QuicPacketNumber(1003)));
53 
54   EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet());
55   EXPECT_EQ(QuicPacketNumber(1003u), queue_.last_packet());
56   EXPECT_EQ(2u, queue_.number_of_present_entries());
57   EXPECT_EQ(3u, queue_.entry_slots_used());
58 
59   ASSERT_FALSE(queue_.Emplace(QuicPacketNumber(1002), "two"));
60 }
61 
TEST_F(PacketNumberIndexedQueueTest,InsertingIntoPast)62 TEST_F(PacketNumberIndexedQueueTest, InsertingIntoPast) {
63   queue_.Emplace(QuicPacketNumber(1001), "one");
64   EXPECT_FALSE(queue_.Emplace(QuicPacketNumber(1000), "zero"));
65 }
66 
TEST_F(PacketNumberIndexedQueueTest,InsertingDuplicate)67 TEST_F(PacketNumberIndexedQueueTest, InsertingDuplicate) {
68   queue_.Emplace(QuicPacketNumber(1001), "one");
69   EXPECT_FALSE(queue_.Emplace(QuicPacketNumber(1001), "one"));
70 }
71 
TEST_F(PacketNumberIndexedQueueTest,RemoveInTheMiddle)72 TEST_F(PacketNumberIndexedQueueTest, RemoveInTheMiddle) {
73   queue_.Emplace(QuicPacketNumber(1001), "one");
74   queue_.Emplace(QuicPacketNumber(1002), "two");
75   queue_.Emplace(QuicPacketNumber(1003), "three");
76 
77   ASSERT_TRUE(queue_.Remove(QuicPacketNumber(1002)));
78   EXPECT_EQ(nullptr, queue_.GetEntry(QuicPacketNumber(1002)));
79 
80   EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet());
81   EXPECT_EQ(QuicPacketNumber(1003u), queue_.last_packet());
82   EXPECT_EQ(2u, queue_.number_of_present_entries());
83   EXPECT_EQ(3u, queue_.entry_slots_used());
84 
85   EXPECT_FALSE(queue_.Emplace(QuicPacketNumber(1002), "two"));
86   EXPECT_TRUE(queue_.Emplace(QuicPacketNumber(1004), "four"));
87 }
88 
TEST_F(PacketNumberIndexedQueueTest,RemoveAtImmediateEdges)89 TEST_F(PacketNumberIndexedQueueTest, RemoveAtImmediateEdges) {
90   queue_.Emplace(QuicPacketNumber(1001), "one");
91   queue_.Emplace(QuicPacketNumber(1002), "two");
92   queue_.Emplace(QuicPacketNumber(1003), "three");
93   ASSERT_TRUE(queue_.Remove(QuicPacketNumber(1001)));
94   EXPECT_EQ(nullptr, queue_.GetEntry(QuicPacketNumber(1001)));
95   ASSERT_TRUE(queue_.Remove(QuicPacketNumber(1003)));
96   EXPECT_EQ(nullptr, queue_.GetEntry(QuicPacketNumber(1003)));
97 
98   EXPECT_EQ(QuicPacketNumber(1002u), queue_.first_packet());
99   EXPECT_EQ(QuicPacketNumber(1003u), queue_.last_packet());
100   EXPECT_EQ(1u, queue_.number_of_present_entries());
101   EXPECT_EQ(2u, queue_.entry_slots_used());
102 
103   EXPECT_TRUE(queue_.Emplace(QuicPacketNumber(1004), "four"));
104 }
105 
TEST_F(PacketNumberIndexedQueueTest,RemoveAtDistantFront)106 TEST_F(PacketNumberIndexedQueueTest, RemoveAtDistantFront) {
107   queue_.Emplace(QuicPacketNumber(1001), "one");
108   queue_.Emplace(QuicPacketNumber(1002), "one (kinda)");
109   queue_.Emplace(QuicPacketNumber(2001), "two");
110 
111   EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet());
112   EXPECT_EQ(QuicPacketNumber(2001u), queue_.last_packet());
113   EXPECT_EQ(3u, queue_.number_of_present_entries());
114   EXPECT_EQ(1001u, queue_.entry_slots_used());
115 
116   ASSERT_TRUE(queue_.Remove(QuicPacketNumber(1002)));
117   EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet());
118   EXPECT_EQ(QuicPacketNumber(2001u), queue_.last_packet());
119   EXPECT_EQ(2u, queue_.number_of_present_entries());
120   EXPECT_EQ(1001u, queue_.entry_slots_used());
121 
122   ASSERT_TRUE(queue_.Remove(QuicPacketNumber(1001)));
123   EXPECT_EQ(QuicPacketNumber(2001u), queue_.first_packet());
124   EXPECT_EQ(QuicPacketNumber(2001u), queue_.last_packet());
125   EXPECT_EQ(1u, queue_.number_of_present_entries());
126   EXPECT_EQ(1u, queue_.entry_slots_used());
127 }
128 
TEST_F(PacketNumberIndexedQueueTest,RemoveAtDistantBack)129 TEST_F(PacketNumberIndexedQueueTest, RemoveAtDistantBack) {
130   queue_.Emplace(QuicPacketNumber(1001), "one");
131   queue_.Emplace(QuicPacketNumber(2001), "two");
132 
133   EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet());
134   EXPECT_EQ(QuicPacketNumber(2001u), queue_.last_packet());
135 
136   ASSERT_TRUE(queue_.Remove(QuicPacketNumber(2001)));
137   EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet());
138   EXPECT_EQ(QuicPacketNumber(2001u), queue_.last_packet());
139 }
140 
TEST_F(PacketNumberIndexedQueueTest,ClearAndRepopulate)141 TEST_F(PacketNumberIndexedQueueTest, ClearAndRepopulate) {
142   queue_.Emplace(QuicPacketNumber(1001), "one");
143   queue_.Emplace(QuicPacketNumber(2001), "two");
144 
145   ASSERT_TRUE(queue_.Remove(QuicPacketNumber(1001)));
146   ASSERT_TRUE(queue_.Remove(QuicPacketNumber(2001)));
147   EXPECT_TRUE(queue_.IsEmpty());
148   EXPECT_FALSE(queue_.first_packet().IsInitialized());
149   EXPECT_FALSE(queue_.last_packet().IsInitialized());
150 
151   EXPECT_TRUE(queue_.Emplace(QuicPacketNumber(101), "one"));
152   EXPECT_TRUE(queue_.Emplace(QuicPacketNumber(201), "two"));
153   EXPECT_EQ(QuicPacketNumber(101u), queue_.first_packet());
154   EXPECT_EQ(QuicPacketNumber(201u), queue_.last_packet());
155 }
156 
TEST_F(PacketNumberIndexedQueueTest,FailToRemoveElementsThatNeverExisted)157 TEST_F(PacketNumberIndexedQueueTest, FailToRemoveElementsThatNeverExisted) {
158   ASSERT_FALSE(queue_.Remove(QuicPacketNumber(1000)));
159   queue_.Emplace(QuicPacketNumber(1001), "one");
160   ASSERT_FALSE(queue_.Remove(QuicPacketNumber(1000)));
161   ASSERT_FALSE(queue_.Remove(QuicPacketNumber(1002)));
162 }
163 
TEST_F(PacketNumberIndexedQueueTest,FailToRemoveElementsTwice)164 TEST_F(PacketNumberIndexedQueueTest, FailToRemoveElementsTwice) {
165   queue_.Emplace(QuicPacketNumber(1001), "one");
166   ASSERT_TRUE(queue_.Remove(QuicPacketNumber(1001)));
167   ASSERT_FALSE(queue_.Remove(QuicPacketNumber(1001)));
168   ASSERT_FALSE(queue_.Remove(QuicPacketNumber(1001)));
169 }
170 
TEST_F(PacketNumberIndexedQueueTest,RemoveUpTo)171 TEST_F(PacketNumberIndexedQueueTest, RemoveUpTo) {
172   queue_.Emplace(QuicPacketNumber(1001), "one");
173   queue_.Emplace(QuicPacketNumber(2001), "two");
174   EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet());
175   EXPECT_EQ(2u, queue_.number_of_present_entries());
176 
177   queue_.RemoveUpTo(QuicPacketNumber(1001));
178   EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet());
179   EXPECT_EQ(2u, queue_.number_of_present_entries());
180 
181   // Remove up to 1100, since [1100, 2001) are !present, they should be cleaned
182   // up from the front.
183   queue_.RemoveUpTo(QuicPacketNumber(1100));
184   EXPECT_EQ(QuicPacketNumber(2001u), queue_.first_packet());
185   EXPECT_EQ(1u, queue_.number_of_present_entries());
186 
187   queue_.RemoveUpTo(QuicPacketNumber(2001));
188   EXPECT_EQ(QuicPacketNumber(2001u), queue_.first_packet());
189   EXPECT_EQ(1u, queue_.number_of_present_entries());
190 
191   queue_.RemoveUpTo(QuicPacketNumber(2002));
192   EXPECT_FALSE(queue_.first_packet().IsInitialized());
193   EXPECT_EQ(0u, queue_.number_of_present_entries());
194 }
195 
TEST_F(PacketNumberIndexedQueueTest,ConstGetter)196 TEST_F(PacketNumberIndexedQueueTest, ConstGetter) {
197   queue_.Emplace(QuicPacketNumber(1001), "one");
198   const auto& const_queue = queue_;
199 
200   EXPECT_EQ("one", *const_queue.GetEntry(QuicPacketNumber(1001)));
201   EXPECT_EQ(nullptr, const_queue.GetEntry(QuicPacketNumber(1002)));
202 }
203 
204 }  // namespace
205 }  // namespace quic
206