| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright 2014 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/spdy/spdy_priority_tree.h" | |
| 6 | |
| 7 #include "testing/gmock/include/gmock/gmock.h" | |
| 8 #include "testing/gtest/include/gtest/gtest.h" | |
| 9 | |
| 10 namespace net { | |
| 11 | |
| 12 using ::testing::ElementsAre; | |
| 13 using ::testing::IsEmpty; | |
| 14 using ::testing::UnorderedElementsAre; | |
| 15 | |
| 16 namespace test { | |
| 17 | |
| 18 template <typename NodeId> | |
| 19 class SpdyPriorityTreePeer { | |
| 20 public: | |
| 21 explicit SpdyPriorityTreePeer(SpdyPriorityTree<NodeId>* tree) : tree_(tree) {} | |
| 22 | |
| 23 void PropagateNodeState(NodeId node_id) { | |
| 24 auto node = tree_->FindNode(node_id); | |
| 25 tree_->PropagateNodeState(node); | |
| 26 } | |
| 27 | |
| 28 int TotalChildWeights(NodeId node_id) const { | |
| 29 return tree_->FindNode(node_id)->total_child_weights; | |
| 30 } | |
| 31 | |
| 32 int TotalWriteableChildWeights(NodeId node_id) const { | |
| 33 return tree_->FindNode(node_id)->total_writeable_child_weights; | |
| 34 } | |
| 35 | |
| 36 bool ValidateInvariants() const { | |
| 37 return tree_->ValidateInvariantsForTests(); | |
| 38 } | |
| 39 | |
| 40 private: | |
| 41 SpdyPriorityTree<NodeId>* tree_; | |
| 42 }; | |
| 43 | |
| 44 class SpdyPriorityTreeTest : public ::testing::Test { | |
| 45 protected: | |
| 46 typedef uint32_t SpdyStreamId; | |
| 47 typedef std::pair<SpdyStreamId, float> PriorityNode; | |
| 48 typedef std::vector<PriorityNode> PriorityList; | |
| 49 | |
| 50 SpdyPriorityTreeTest() : peer(&tree) {} | |
| 51 | |
| 52 SpdyPriorityTree<SpdyStreamId> tree; | |
| 53 SpdyPriorityTreePeer<SpdyStreamId> peer; | |
| 54 }; | |
| 55 | |
| 56 TEST_F(SpdyPriorityTreeTest, AddAndRemoveNodes) { | |
| 57 EXPECT_EQ(1, tree.num_nodes()); | |
| 58 EXPECT_TRUE(tree.NodeExists(0)); | |
| 59 EXPECT_FALSE(tree.NodeExists(1)); | |
| 60 | |
| 61 EXPECT_TRUE(tree.AddNode(1, 0, 100, false)); | |
| 62 EXPECT_EQ(2, tree.num_nodes()); | |
| 63 ASSERT_TRUE(tree.NodeExists(1)); | |
| 64 EXPECT_EQ(100, tree.GetWeight(1)); | |
| 65 EXPECT_FALSE(tree.NodeExists(5)); | |
| 66 EXPECT_THAT(tree.GetChildren(0), ElementsAre(1)); | |
| 67 | |
| 68 EXPECT_TRUE(tree.AddNode(5, 0, 50, false)); | |
| 69 // Should not be able to add a node with an id that already exists. | |
| 70 EXPECT_FALSE(tree.AddNode(5, 1, 50, false)); | |
| 71 EXPECT_EQ(3, tree.num_nodes()); | |
| 72 EXPECT_TRUE(tree.NodeExists(1)); | |
| 73 ASSERT_TRUE(tree.NodeExists(5)); | |
| 74 EXPECT_EQ(50, tree.GetWeight(5)); | |
| 75 EXPECT_FALSE(tree.NodeExists(13)); | |
| 76 | |
| 77 EXPECT_TRUE(tree.AddNode(13, 5, 130, true)); | |
| 78 EXPECT_EQ(4, tree.num_nodes()); | |
| 79 EXPECT_TRUE(tree.NodeExists(1)); | |
| 80 EXPECT_TRUE(tree.NodeExists(5)); | |
| 81 ASSERT_TRUE(tree.NodeExists(13)); | |
| 82 EXPECT_EQ(130, tree.GetWeight(13)); | |
| 83 EXPECT_EQ(5u, tree.GetParent(13)); | |
| 84 | |
| 85 EXPECT_TRUE(tree.RemoveNode(5)); | |
| 86 // Cannot remove a node that has already been removed. | |
| 87 EXPECT_FALSE(tree.RemoveNode(5)); | |
| 88 EXPECT_EQ(3, tree.num_nodes()); | |
| 89 EXPECT_TRUE(tree.NodeExists(1)); | |
| 90 EXPECT_FALSE(tree.NodeExists(5)); | |
| 91 EXPECT_TRUE(tree.NodeExists(13)); | |
| 92 EXPECT_EQ(0u, tree.GetParent(13)); | |
| 93 | |
| 94 // The parent node 19 doesn't exist, so this should fail: | |
| 95 EXPECT_FALSE(tree.AddNode(7, 19, 70, false)); | |
| 96 // This should succeed, creating node 7: | |
| 97 EXPECT_TRUE(tree.AddNode(7, 13, 70, false)); | |
| 98 // Now node 7 already exists, so this should fail: | |
| 99 EXPECT_FALSE(tree.AddNode(7, 1, 70, false)); | |
| 100 // Try adding a second child to node 13: | |
| 101 EXPECT_TRUE(tree.AddNode(17, 13, 170, false)); | |
| 102 | |
| 103 // TODO(birenroy): Add a separate test that verifies weight invariants when | |
| 104 // SetWeight is called. | |
| 105 EXPECT_TRUE(tree.SetWeight(17, 150)); | |
| 106 EXPECT_EQ(150, tree.GetWeight(17)); | |
| 107 | |
| 108 ASSERT_TRUE(peer.ValidateInvariants()); | |
| 109 } | |
| 110 | |
| 111 // Basic case of reparenting a subtree. | |
| 112 TEST_F(SpdyPriorityTreeTest, SetParentBasicNonExclusive) { | |
| 113 /* Tree: | |
| 114 0 | |
| 115 / \ | |
| 116 1 2 | |
| 117 / \ | |
| 118 3 4 | |
| 119 */ | |
| 120 tree.AddNode(1, 0, 100, false); | |
| 121 tree.AddNode(2, 0, 100, false); | |
| 122 tree.AddNode(3, 1, 100, false); | |
| 123 tree.AddNode(4, 1, 100, false); | |
| 124 EXPECT_TRUE(tree.SetParent(1, 2, false)); | |
| 125 EXPECT_THAT(tree.GetChildren(0), ElementsAre(2)); | |
| 126 EXPECT_THAT(tree.GetChildren(1), UnorderedElementsAre(3, 4)); | |
| 127 EXPECT_THAT(tree.GetChildren(2), ElementsAre(1)); | |
| 128 EXPECT_THAT(tree.GetChildren(3), IsEmpty()); | |
| 129 EXPECT_THAT(tree.GetChildren(4), IsEmpty()); | |
| 130 ASSERT_TRUE(peer.ValidateInvariants()); | |
| 131 } | |
| 132 | |
| 133 // Basic case of reparenting a subtree. Result here is the same as the | |
| 134 // non-exclusive case. | |
| 135 TEST_F(SpdyPriorityTreeTest, SetParentBasicExclusive) { | |
| 136 /* Tree: | |
| 137 0 | |
| 138 / \ | |
| 139 1 2 | |
| 140 / \ | |
| 141 3 4 | |
| 142 */ | |
| 143 tree.AddNode(1, 0, 100, false); | |
| 144 tree.AddNode(2, 0, 100, false); | |
| 145 tree.AddNode(3, 1, 100, false); | |
| 146 tree.AddNode(4, 1, 100, false); | |
| 147 EXPECT_TRUE(tree.SetParent(1, 2, true)); | |
| 148 EXPECT_THAT(tree.GetChildren(0), ElementsAre(2)); | |
| 149 EXPECT_THAT(tree.GetChildren(1), UnorderedElementsAre(3, 4)); | |
| 150 EXPECT_THAT(tree.GetChildren(2), ElementsAre(1)); | |
| 151 EXPECT_THAT(tree.GetChildren(3), IsEmpty()); | |
| 152 EXPECT_THAT(tree.GetChildren(4), IsEmpty()); | |
| 153 ASSERT_TRUE(peer.ValidateInvariants()); | |
| 154 } | |
| 155 | |
| 156 // We can't set the parent of a nonexistent node, or set the parent to a | |
| 157 // nonexistent node. | |
| 158 TEST_F(SpdyPriorityTreeTest, SetParentNonexistent) { | |
| 159 tree.AddNode(1, 0, 100, false); | |
| 160 tree.AddNode(2, 0, 100, false); | |
| 161 bool test_bool_values[] = {true, false}; | |
| 162 for (bool exclusive : test_bool_values) { | |
| 163 EXPECT_FALSE(tree.SetParent(1, 3, exclusive)); | |
| 164 EXPECT_FALSE(tree.SetParent(4, 2, exclusive)); | |
| 165 EXPECT_FALSE(tree.SetParent(3, 4, exclusive)); | |
| 166 EXPECT_THAT(tree.GetChildren(0), UnorderedElementsAre(1, 2)); | |
| 167 EXPECT_THAT(tree.GetChildren(1), IsEmpty()); | |
| 168 EXPECT_THAT(tree.GetChildren(2), IsEmpty()); | |
| 169 } | |
| 170 ASSERT_TRUE(peer.ValidateInvariants()); | |
| 171 } | |
| 172 | |
| 173 // We should be able to add multiple children to nodes. | |
| 174 TEST_F(SpdyPriorityTreeTest, SetParentMultipleChildrenNonExclusive) { | |
| 175 /* Tree: | |
| 176 0 | |
| 177 / \ | |
| 178 1 2 | |
| 179 / \ \ | |
| 180 3 4 5 | |
| 181 */ | |
| 182 tree.AddNode(1, 0, 100, false); | |
| 183 tree.AddNode(2, 0, 100, false); | |
| 184 tree.AddNode(3, 1, 100, false); | |
| 185 tree.AddNode(4, 1, 100, false); | |
| 186 tree.AddNode(5, 2, 100, false); | |
| 187 EXPECT_TRUE(tree.SetParent(2, 1, false)); | |
| 188 EXPECT_THAT(tree.GetChildren(0), ElementsAre(1)); | |
| 189 EXPECT_THAT(tree.GetChildren(1), UnorderedElementsAre(2, 3, 4)); | |
| 190 EXPECT_THAT(tree.GetChildren(2), ElementsAre(5)); | |
| 191 EXPECT_THAT(tree.GetChildren(3), IsEmpty()); | |
| 192 EXPECT_THAT(tree.GetChildren(4), IsEmpty()); | |
| 193 EXPECT_THAT(tree.GetChildren(5), IsEmpty()); | |
| 194 ASSERT_TRUE(peer.ValidateInvariants()); | |
| 195 } | |
| 196 | |
| 197 TEST_F(SpdyPriorityTreeTest, SetParentMultipleChildrenExclusive) { | |
| 198 /* Tree: | |
| 199 0 | |
| 200 / \ | |
| 201 1 2 | |
| 202 / \ \ | |
| 203 3 4 5 | |
| 204 */ | |
| 205 tree.AddNode(1, 0, 100, false); | |
| 206 tree.AddNode(2, 0, 100, false); | |
| 207 tree.AddNode(3, 1, 100, false); | |
| 208 tree.AddNode(4, 1, 100, false); | |
| 209 tree.AddNode(5, 2, 100, false); | |
| 210 EXPECT_TRUE(tree.SetParent(2, 1, true)); | |
| 211 EXPECT_THAT(tree.GetChildren(0), ElementsAre(1)); | |
| 212 EXPECT_THAT(tree.GetChildren(1), ElementsAre(2)); | |
| 213 EXPECT_THAT(tree.GetChildren(2), UnorderedElementsAre(3, 4, 5)); | |
| 214 EXPECT_THAT(tree.GetChildren(3), IsEmpty()); | |
| 215 EXPECT_THAT(tree.GetChildren(4), IsEmpty()); | |
| 216 EXPECT_THAT(tree.GetChildren(5), IsEmpty()); | |
| 217 ASSERT_TRUE(peer.ValidateInvariants()); | |
| 218 } | |
| 219 | |
| 220 TEST_F(SpdyPriorityTreeTest, SetParentToChildNonExclusive) { | |
| 221 /* Tree: | |
| 222 0 | |
| 223 | | |
| 224 1 | |
| 225 / \ | |
| 226 2 3 | |
| 227 | | |
| 228 4 | |
| 229 */ | |
| 230 tree.AddNode(1, 0, 100, false); | |
| 231 tree.AddNode(2, 1, 100, false); | |
| 232 tree.AddNode(3, 1, 100, false); | |
| 233 tree.AddNode(4, 2, 100, false); | |
| 234 EXPECT_TRUE(tree.SetParent(1, 2, false)); | |
| 235 EXPECT_THAT(tree.GetChildren(0), ElementsAre(2)); | |
| 236 EXPECT_THAT(tree.GetChildren(1), ElementsAre(3)); | |
| 237 EXPECT_THAT(tree.GetChildren(2), UnorderedElementsAre(1, 4)); | |
| 238 EXPECT_THAT(tree.GetChildren(3), IsEmpty()); | |
| 239 EXPECT_THAT(tree.GetChildren(4), IsEmpty()); | |
| 240 ASSERT_TRUE(peer.ValidateInvariants()); | |
| 241 } | |
| 242 | |
| 243 TEST_F(SpdyPriorityTreeTest, SetParentToChildExclusive) { | |
| 244 /* Tree: | |
| 245 0 | |
| 246 | | |
| 247 1 | |
| 248 / \ | |
| 249 2 3 | |
| 250 | | |
| 251 4 | |
| 252 */ | |
| 253 tree.AddNode(1, 0, 100, false); | |
| 254 tree.AddNode(2, 1, 100, false); | |
| 255 tree.AddNode(3, 1, 100, false); | |
| 256 tree.AddNode(4, 2, 100, false); | |
| 257 EXPECT_TRUE(tree.SetParent(1, 2, true)); | |
| 258 EXPECT_THAT(tree.GetChildren(0), ElementsAre(2)); | |
| 259 EXPECT_THAT(tree.GetChildren(1), UnorderedElementsAre(3, 4)); | |
| 260 EXPECT_THAT(tree.GetChildren(2), ElementsAre(1)); | |
| 261 EXPECT_THAT(tree.GetChildren(3), IsEmpty()); | |
| 262 EXPECT_THAT(tree.GetChildren(4), IsEmpty()); | |
| 263 ASSERT_TRUE(peer.ValidateInvariants()); | |
| 264 } | |
| 265 | |
| 266 TEST_F(SpdyPriorityTreeTest, SetParentToGrandchildNonExclusive) { | |
| 267 /* Tree: | |
| 268 0 | |
| 269 | | |
| 270 1 | |
| 271 / \ | |
| 272 2 3 | |
| 273 / \ | |
| 274 4 5 | |
| 275 | | |
| 276 6 | |
| 277 */ | |
| 278 tree.AddNode(1, 0, 100, false); | |
| 279 tree.AddNode(2, 1, 100, false); | |
| 280 tree.AddNode(3, 1, 100, false); | |
| 281 tree.AddNode(4, 2, 100, false); | |
| 282 tree.AddNode(5, 2, 100, false); | |
| 283 tree.AddNode(6, 4, 100, false); | |
| 284 EXPECT_TRUE(tree.SetParent(1, 4, false)); | |
| 285 EXPECT_THAT(tree.GetChildren(0), ElementsAre(4)); | |
| 286 EXPECT_THAT(tree.GetChildren(1), UnorderedElementsAre(2, 3)); | |
| 287 EXPECT_THAT(tree.GetChildren(2), ElementsAre(5)); | |
| 288 EXPECT_THAT(tree.GetChildren(3), IsEmpty()); | |
| 289 EXPECT_THAT(tree.GetChildren(4), UnorderedElementsAre(1, 6)); | |
| 290 EXPECT_THAT(tree.GetChildren(5), IsEmpty()); | |
| 291 EXPECT_THAT(tree.GetChildren(6), IsEmpty()); | |
| 292 ASSERT_TRUE(peer.ValidateInvariants()); | |
| 293 } | |
| 294 | |
| 295 TEST_F(SpdyPriorityTreeTest, SetParentToGrandchildExclusive) { | |
| 296 /* Tree: | |
| 297 0 | |
| 298 | | |
| 299 1 | |
| 300 / \ | |
| 301 2 3 | |
| 302 / \ | |
| 303 4 5 | |
| 304 | | |
| 305 6 | |
| 306 */ | |
| 307 tree.AddNode(1, 0, 100, false); | |
| 308 tree.AddNode(2, 1, 100, false); | |
| 309 tree.AddNode(3, 1, 100, false); | |
| 310 tree.AddNode(4, 2, 100, false); | |
| 311 tree.AddNode(5, 2, 100, false); | |
| 312 tree.AddNode(6, 4, 100, false); | |
| 313 EXPECT_TRUE(tree.SetParent(1, 4, true)); | |
| 314 EXPECT_THAT(tree.GetChildren(0), ElementsAre(4)); | |
| 315 EXPECT_THAT(tree.GetChildren(1), UnorderedElementsAre(2, 3, 6)); | |
| 316 EXPECT_THAT(tree.GetChildren(2), ElementsAre(5)); | |
| 317 EXPECT_THAT(tree.GetChildren(3), IsEmpty()); | |
| 318 EXPECT_THAT(tree.GetChildren(4), ElementsAre(1)); | |
| 319 EXPECT_THAT(tree.GetChildren(5), IsEmpty()); | |
| 320 EXPECT_THAT(tree.GetChildren(6), IsEmpty()); | |
| 321 ASSERT_TRUE(peer.ValidateInvariants()); | |
| 322 } | |
| 323 | |
| 324 TEST_F(SpdyPriorityTreeTest, SetParentToParent) { | |
| 325 tree.AddNode(1, 0, 100, false); | |
| 326 tree.AddNode(2, 1, 100, false); | |
| 327 tree.AddNode(3, 1, 100, false); | |
| 328 bool test_bool_values[] = {true, false}; | |
| 329 for (bool exclusive : test_bool_values) { | |
| 330 EXPECT_TRUE(tree.SetParent(2, 1, exclusive)); | |
| 331 EXPECT_THAT(tree.GetChildren(0), ElementsAre(1)); | |
| 332 EXPECT_THAT(tree.GetChildren(1), UnorderedElementsAre(2, 3)); | |
| 333 EXPECT_THAT(tree.GetChildren(2), IsEmpty()); | |
| 334 EXPECT_THAT(tree.GetChildren(3), IsEmpty()); | |
| 335 } | |
| 336 ASSERT_TRUE(peer.ValidateInvariants()); | |
| 337 } | |
| 338 | |
| 339 TEST_F(SpdyPriorityTreeTest, SetParentToSelf) { | |
| 340 tree.AddNode(1, 0, 100, false); | |
| 341 EXPECT_FALSE(tree.SetParent(1, 1, false)); | |
| 342 EXPECT_FALSE(tree.SetParent(1, 1, true)); | |
| 343 EXPECT_THAT(tree.GetChildren(0), ElementsAre(1)); | |
| 344 EXPECT_THAT(tree.GetChildren(1), IsEmpty()); | |
| 345 ASSERT_TRUE(peer.ValidateInvariants()); | |
| 346 } | |
| 347 | |
| 348 TEST_F(SpdyPriorityTreeTest, BlockAndUnblock) { | |
| 349 /* Create the tree. | |
| 350 | |
| 351 0 | |
| 352 / | \ | |
| 353 / | \ | |
| 354 1 2 3 | |
| 355 / \ \ \ | |
| 356 4 5 6 7 | |
| 357 /| / \ | |\ | |
| 358 8 9 10 11 12 13 14 | |
| 359 / \ | |
| 360 15 16 | |
| 361 | |
| 362 */ | |
| 363 tree.AddNode(1, 0, 100, false); | |
| 364 tree.AddNode(2, 0, 100, false); | |
| 365 tree.AddNode(3, 0, 100, false); | |
| 366 tree.AddNode(4, 1, 100, false); | |
| 367 tree.AddNode(5, 1, 100, false); | |
| 368 tree.AddNode(8, 4, 100, false); | |
| 369 tree.AddNode(9, 4, 100, false); | |
| 370 tree.AddNode(10, 5, 100, false); | |
| 371 tree.AddNode(11, 5, 100, false); | |
| 372 tree.AddNode(15, 8, 100, false); | |
| 373 tree.AddNode(16, 8, 100, false); | |
| 374 tree.AddNode(12, 2, 100, false); | |
| 375 tree.AddNode(6, 2, 100, true); | |
| 376 tree.AddNode(7, 0, 100, false); | |
| 377 tree.AddNode(13, 7, 100, true); | |
| 378 tree.AddNode(14, 7, 100, false); | |
| 379 tree.SetParent(7, 3, false); | |
| 380 EXPECT_EQ(0u, tree.GetParent(1)); | |
| 381 EXPECT_EQ(0u, tree.GetParent(2)); | |
| 382 EXPECT_EQ(0u, tree.GetParent(3)); | |
| 383 EXPECT_EQ(1u, tree.GetParent(4)); | |
| 384 EXPECT_EQ(1u, tree.GetParent(5)); | |
| 385 EXPECT_EQ(2u, tree.GetParent(6)); | |
| 386 EXPECT_EQ(3u, tree.GetParent(7)); | |
| 387 EXPECT_EQ(4u, tree.GetParent(8)); | |
| 388 EXPECT_EQ(4u, tree.GetParent(9)); | |
| 389 EXPECT_EQ(5u, tree.GetParent(10)); | |
| 390 EXPECT_EQ(5u, tree.GetParent(11)); | |
| 391 EXPECT_EQ(6u, tree.GetParent(12)); | |
| 392 EXPECT_EQ(7u, tree.GetParent(13)); | |
| 393 EXPECT_EQ(7u, tree.GetParent(14)); | |
| 394 EXPECT_EQ(8u, tree.GetParent(15)); | |
| 395 EXPECT_EQ(8u, tree.GetParent(16)); | |
| 396 ASSERT_TRUE(peer.ValidateInvariants()); | |
| 397 | |
| 398 EXPECT_EQ(peer.TotalChildWeights(0), | |
| 399 tree.GetWeight(1) + tree.GetWeight(2) + tree.GetWeight(3)); | |
| 400 EXPECT_EQ(peer.TotalChildWeights(3), tree.GetWeight(7)); | |
| 401 EXPECT_EQ(peer.TotalChildWeights(7), tree.GetWeight(13) + tree.GetWeight(14)); | |
| 402 EXPECT_EQ(peer.TotalChildWeights(13), 0); | |
| 403 EXPECT_EQ(peer.TotalChildWeights(14), 0); | |
| 404 | |
| 405 // Set all nodes ready to write. | |
| 406 EXPECT_TRUE(tree.SetReady(1, true)); | |
| 407 EXPECT_TRUE(tree.SetReady(2, true)); | |
| 408 EXPECT_TRUE(tree.SetReady(3, true)); | |
| 409 EXPECT_TRUE(tree.SetReady(4, true)); | |
| 410 EXPECT_TRUE(tree.SetReady(5, true)); | |
| 411 EXPECT_TRUE(tree.SetReady(6, true)); | |
| 412 EXPECT_TRUE(tree.SetReady(7, true)); | |
| 413 EXPECT_TRUE(tree.SetReady(8, true)); | |
| 414 EXPECT_TRUE(tree.SetReady(9, true)); | |
| 415 EXPECT_TRUE(tree.SetReady(10, true)); | |
| 416 EXPECT_TRUE(tree.SetReady(11, true)); | |
| 417 EXPECT_TRUE(tree.SetReady(12, true)); | |
| 418 EXPECT_TRUE(tree.SetReady(13, true)); | |
| 419 EXPECT_TRUE(tree.SetReady(14, true)); | |
| 420 EXPECT_TRUE(tree.SetReady(15, true)); | |
| 421 EXPECT_TRUE(tree.SetReady(16, true)); | |
| 422 | |
| 423 // Number of readable child weights should not change because | |
| 424 // 7 has unblocked children. | |
| 425 tree.SetBlocked(7, true); | |
| 426 peer.PropagateNodeState(kRootNodeId); | |
| 427 EXPECT_EQ(peer.TotalChildWeights(3), peer.TotalWriteableChildWeights(3)); | |
| 428 | |
| 429 // Readable children for 7 should decrement. | |
| 430 // Number of readable child weights for 3 still should not change. | |
| 431 tree.SetBlocked(13, true); | |
| 432 peer.PropagateNodeState(kRootNodeId); | |
| 433 EXPECT_EQ(peer.TotalChildWeights(3), peer.TotalWriteableChildWeights(3)); | |
| 434 EXPECT_EQ(tree.GetWeight(14), peer.TotalWriteableChildWeights(7)); | |
| 435 | |
| 436 // Once 14 becomes blocked, readable children for 7 and 3 should both be | |
| 437 // decremented. Total readable weights at the root should still be the same | |
| 438 // because 3 is still writeable. | |
| 439 tree.SetBlocked(14, true); | |
| 440 peer.PropagateNodeState(kRootNodeId); | |
| 441 EXPECT_EQ(0, peer.TotalWriteableChildWeights(3)); | |
| 442 EXPECT_EQ(0, peer.TotalWriteableChildWeights(7)); | |
| 443 EXPECT_EQ(peer.TotalChildWeights(0), | |
| 444 tree.GetWeight(1) + tree.GetWeight(2) + tree.GetWeight(3)); | |
| 445 | |
| 446 // And now the root should be decremented as well. | |
| 447 tree.SetBlocked(3, true); | |
| 448 peer.PropagateNodeState(kRootNodeId); | |
| 449 EXPECT_EQ(tree.GetWeight(1) + tree.GetWeight(2), | |
| 450 peer.TotalWriteableChildWeights(0)); | |
| 451 | |
| 452 // Unblocking 7 should propagate all the way up to the root. | |
| 453 tree.SetBlocked(7, false); | |
| 454 peer.PropagateNodeState(kRootNodeId); | |
| 455 EXPECT_EQ(peer.TotalWriteableChildWeights(0), | |
| 456 tree.GetWeight(1) + tree.GetWeight(2) + tree.GetWeight(3)); | |
| 457 EXPECT_EQ(peer.TotalWriteableChildWeights(3), tree.GetWeight(7)); | |
| 458 EXPECT_EQ(0, peer.TotalWriteableChildWeights(7)); | |
| 459 | |
| 460 // Ditto for reblocking 7. | |
| 461 tree.SetBlocked(7, true); | |
| 462 peer.PropagateNodeState(kRootNodeId); | |
| 463 EXPECT_EQ(peer.TotalWriteableChildWeights(0), | |
| 464 tree.GetWeight(1) + tree.GetWeight(2)); | |
| 465 EXPECT_EQ(0, peer.TotalWriteableChildWeights(3)); | |
| 466 EXPECT_EQ(0, peer.TotalWriteableChildWeights(7)); | |
| 467 ASSERT_TRUE(peer.ValidateInvariants()); | |
| 468 } | |
| 469 | |
| 470 TEST_F(SpdyPriorityTreeTest, GetPriorityList) { | |
| 471 PriorityList expected_list; | |
| 472 PriorityList priority_list; | |
| 473 | |
| 474 /* Create the tree. | |
| 475 | |
| 476 0 | |
| 477 /|\ | |
| 478 1 2 3 | |
| 479 /| |\ | |
| 480 4 5 6 7 | |
| 481 / | |
| 482 8 | |
| 483 | |
| 484 */ | |
| 485 tree.AddNode(1, 0, 10, false); | |
| 486 tree.AddNode(2, 0, 20, false); | |
| 487 tree.AddNode(3, 0, 30, false); | |
| 488 tree.AddNode(4, 1, 10, false); | |
| 489 tree.AddNode(5, 1, 90, false); | |
| 490 tree.AddNode(6, 2, 10, false); | |
| 491 tree.AddNode(7, 2, 10, false); | |
| 492 tree.AddNode(8, 4, 256, false); | |
| 493 | |
| 494 // Set all nodes ready to write. | |
| 495 EXPECT_TRUE(tree.SetReady(1, true)); | |
| 496 EXPECT_TRUE(tree.SetReady(2, true)); | |
| 497 EXPECT_TRUE(tree.SetReady(3, true)); | |
| 498 EXPECT_TRUE(tree.SetReady(4, true)); | |
| 499 EXPECT_TRUE(tree.SetReady(5, true)); | |
| 500 EXPECT_TRUE(tree.SetReady(6, true)); | |
| 501 EXPECT_TRUE(tree.SetReady(7, true)); | |
| 502 EXPECT_TRUE(tree.SetReady(8, true)); | |
| 503 | |
| 504 expected_list.push_back(PriorityNode(3, 1.0/2.0)); | |
| 505 expected_list.push_back(PriorityNode(2, 1.0/3.0)); | |
| 506 expected_list.push_back(PriorityNode(1, 1.0/6.0)); | |
| 507 priority_list = tree.GetPriorityList(); | |
| 508 EXPECT_EQ(expected_list, priority_list); | |
| 509 | |
| 510 // Check that the list updates as expected when a node gets blocked. | |
| 511 EXPECT_TRUE(tree.SetReady(1, false)); | |
| 512 expected_list.clear(); | |
| 513 expected_list.push_back(PriorityNode(3, 1.0/2.0)); | |
| 514 expected_list.push_back(PriorityNode(2, 1.0/3.0)); | |
| 515 expected_list.push_back(PriorityNode(5, 0.9*1.0/6.0)); | |
| 516 expected_list.push_back(PriorityNode(4, 0.1*1.0/6.0)); | |
| 517 priority_list = tree.GetPriorityList(); | |
| 518 EXPECT_EQ(expected_list, priority_list); | |
| 519 | |
| 520 // Block multiple levels of nodes. | |
| 521 EXPECT_TRUE(tree.SetReady(4, false)); | |
| 522 EXPECT_TRUE(tree.SetReady(5, false)); | |
| 523 expected_list.clear(); | |
| 524 expected_list.push_back(PriorityNode(3, 1.0/2.0)); | |
| 525 expected_list.push_back(PriorityNode(2, 1.0/3.0)); | |
| 526 expected_list.push_back(PriorityNode(8, 1.0/6.0)); | |
| 527 priority_list = tree.GetPriorityList(); | |
| 528 EXPECT_EQ(expected_list, priority_list); | |
| 529 | |
| 530 // Remove a node from the tree to make sure priorities | |
| 531 // get redistributed accordingly. | |
| 532 EXPECT_TRUE(tree.RemoveNode(1)); | |
| 533 expected_list.clear(); | |
| 534 expected_list.push_back(PriorityNode(3, 30.0/51.0)); | |
| 535 expected_list.push_back(PriorityNode(2, 20.0/51.0)); | |
| 536 expected_list.push_back(PriorityNode(8, 1.0/51.0)); | |
| 537 priority_list = tree.GetPriorityList(); | |
| 538 EXPECT_EQ(expected_list, priority_list); | |
| 539 | |
| 540 // Block an entire subtree. | |
| 541 EXPECT_TRUE(tree.SetReady(8, false)); | |
| 542 expected_list.clear(); | |
| 543 expected_list.push_back(PriorityNode(3, 0.6)); | |
| 544 expected_list.push_back(PriorityNode(2, 0.4)); | |
| 545 priority_list = tree.GetPriorityList(); | |
| 546 EXPECT_EQ(expected_list, priority_list); | |
| 547 | |
| 548 // Unblock previously blocked nodes. | |
| 549 EXPECT_TRUE(tree.SetReady(4, true)); | |
| 550 EXPECT_TRUE(tree.SetReady(5, true)); | |
| 551 expected_list.clear(); | |
| 552 expected_list.push_back(PriorityNode(3, 1.0/2.0)); | |
| 553 expected_list.push_back(PriorityNode(2, 1.0/3.0)); | |
| 554 expected_list.push_back(PriorityNode(5, 9.0/60.0)); | |
| 555 expected_list.push_back(PriorityNode(4, 1.0/60.0)); | |
| 556 priority_list = tree.GetPriorityList(); | |
| 557 EXPECT_EQ(expected_list, priority_list); | |
| 558 | |
| 559 // Blocked nodes in multiple subtrees. | |
| 560 EXPECT_TRUE(tree.SetReady(2, false)); | |
| 561 EXPECT_TRUE(tree.SetReady(6, false)); | |
| 562 EXPECT_TRUE(tree.SetReady(7, false)); | |
| 563 expected_list.clear(); | |
| 564 expected_list.push_back(PriorityNode(3, 3.0/4.0)); | |
| 565 expected_list.push_back(PriorityNode(5, 9.0/40.0)); | |
| 566 expected_list.push_back(PriorityNode(4, 1.0/40.0)); | |
| 567 priority_list = tree.GetPriorityList(); | |
| 568 EXPECT_EQ(expected_list, priority_list); | |
| 569 } | |
| 570 | |
| 571 TEST_F(SpdyPriorityTreeTest, CalculateRoundedWeights) { | |
| 572 PriorityList expected_list; | |
| 573 PriorityList priority_list; | |
| 574 | |
| 575 /* Create the tree. | |
| 576 | |
| 577 0 | |
| 578 / \ | |
| 579 1 2 | |
| 580 /| |\ |\ | |
| 581 8 3 4 5 6 7 | |
| 582 */ | |
| 583 tree.AddNode(3, 0, 100, false); | |
| 584 tree.AddNode(4, 0, 100, false); | |
| 585 tree.AddNode(5, 0, 100, false); | |
| 586 tree.AddNode(1, 0, 10, true); | |
| 587 tree.AddNode(2, 0, 5, false); | |
| 588 tree.AddNode(6, 2, 1, false); | |
| 589 tree.AddNode(7, 2, 1, false); | |
| 590 tree.AddNode(8, 1, 1, false); | |
| 591 | |
| 592 // Remove higher-level nodes. | |
| 593 tree.RemoveNode(1); | |
| 594 tree.RemoveNode(2); | |
| 595 | |
| 596 // 3.3 rounded down = 3. | |
| 597 EXPECT_EQ(3, tree.GetWeight(3)); | |
| 598 EXPECT_EQ(3, tree.GetWeight(4)); | |
| 599 EXPECT_EQ(3, tree.GetWeight(5)); | |
| 600 // 2.5 rounded up = 3. | |
| 601 EXPECT_EQ(3, tree.GetWeight(6)); | |
| 602 EXPECT_EQ(3, tree.GetWeight(7)); | |
| 603 // 0 is not a valid weight, so round up to 1. | |
| 604 EXPECT_EQ(1, tree.GetWeight(8)); | |
| 605 } | |
| 606 } // namespace test | |
| 607 } // namespace gfe_spdy | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1668773003:
Rename spdy_priority_tree* (Closed)
Base URL: https://chromium.googlesource.com/chromium/src.git@master