net/spdy/spdy_priority_tree_test.cc

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