1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
|
// 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 <string>
#include "net/third_party/quiche/src/quic/core/quic_packet_number.h"
#include "net/third_party/quiche/src/quic/platform/api/quic_test.h"
namespace quic {
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
|
