1c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Copyright (c) 2013 The Chromium Authors. All rights reserved. 2c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 3c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// found in the LICENSE file. 4c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 5c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "net/spdy/spdy_priority_forest.h" 6c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 7c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "base/basictypes.h" 8c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "testing/gtest/include/gtest/gtest.h" 9c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 10c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)namespace net { 11c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 12c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)TEST(SpdyPriorityForestTest, AddAndRemoveNodes) { 13c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) SpdyPriorityForest<uint32,int16> forest; 14c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(0, forest.num_nodes()); 15c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.NodeExists(1)); 16c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 17c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.AddRootNode(1, 1000)); 18c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(1, forest.num_nodes()); 19c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ASSERT_TRUE(forest.NodeExists(1)); 20c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(1000, forest.GetPriority(1)); 21c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.NodeExists(5)); 22c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 23c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.AddRootNode(5, 50)); 24c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.AddRootNode(5, 500)); 25c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(2, forest.num_nodes()); 26c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.NodeExists(1)); 27c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ASSERT_TRUE(forest.NodeExists(5)); 28c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(50, forest.GetPriority(5)); 29c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.NodeExists(13)); 30c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 31c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.AddRootNode(13, 130)); 32c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(3, forest.num_nodes()); 33c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.NodeExists(1)); 34c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.NodeExists(5)); 35c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ASSERT_TRUE(forest.NodeExists(13)); 36c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(130, forest.GetPriority(13)); 37c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 38c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.RemoveNode(5)); 39c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.RemoveNode(5)); 40c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(2, forest.num_nodes()); 41c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.NodeExists(1)); 42c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.NodeExists(5)); 43c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.NodeExists(13)); 44c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 45c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // The parent node 19 doesn't exist, so this should fail: 46c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.AddNonRootNode(7, 19, false)); 47c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // This should succed, creating node 7: 48c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.AddNonRootNode(7, 13, false)); 49c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Now node 7 already exists, so this should fail: 50c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.AddNonRootNode(7, 1, false)); 51c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Node 13 already has a child (7), so this should fail: 52c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.AddNonRootNode(17, 13, false)); 53c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 54c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ASSERT_TRUE(forest.ValidateInvariantsForTests()); 55c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 56c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 57c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)TEST(SpdyPriorityForestTest, SetParent) { 58c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) SpdyPriorityForest<uint32,int16> forest; 59c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddRootNode(1, 1000); 60c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(2, 1, false); 61c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(3, 2, false); 62c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(5, 3, false); 63c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(7, 5, false); 64c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(9, 7, false); 65c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddRootNode(11, 2000); 66c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(13, 11, false); 67c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // We can't set the parent of a nonexistent node, or set the parent of an 68c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // existing node to a nonexistent node. 69c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.SetParent(99, 13, false)); 70c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.SetParent(5, 99, false)); 71c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // We can't make a node a child a node that already has a child: 72c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.SetParent(13, 7, false)); 73c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.SetParent(3, 11, false)); 74c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // These would create cycles: 75c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.SetParent(11, 13, false)); 76c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.SetParent(1, 9, false)); 77c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.SetParent(3, 9, false)); 78c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // But this change is legit: 79c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(7u, forest.GetChild(5)); 80c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.SetParent(7, 13, false)); 81c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(0u, forest.GetChild(5)); 82c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(13u, forest.GetParent(7)); 83c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(7u, forest.GetChild(13)); 84c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // So is this change (now that 9 is no longer a descendant of 1): 85c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.SetParent(1, 9, false)); 86c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(9u, forest.GetParent(1)); 87c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(1u, forest.GetChild(9)); 88c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // We must allow setting the parent of a node to its same parent (even though 89c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // that parent of course has a child already), so that we can change 90c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // orderedness. 91c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(1u, forest.GetParent(2)); 92c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(2u, forest.GetChild(1)); 93c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.IsNodeUnordered(2)); 94c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.SetParent(2, 1, true)); 95c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(1u, forest.GetParent(2)); 96c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(2u, forest.GetChild(1)); 97c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.IsNodeUnordered(2)); 98c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 99c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ASSERT_TRUE(forest.ValidateInvariantsForTests()); 100c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 101c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 102c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)TEST(SpdyPriorityForestTest, RemoveNodesFromMiddleOfChain) { 103c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) SpdyPriorityForest<uint32,int16> forest; 104c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddRootNode(1, 1000); 105c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(2, 1, false); 106c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(3, 2, true); 107c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(5, 3, false); 108c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(7, 5, true); 109c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(9, 7, true); 110c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 111c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Remove a node from the middle, with unordered links on both sides. The 112c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // new merged link should also be unordered. 113c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.NodeExists(7)); 114c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(7u, forest.GetChild(5)); 115c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(7u, forest.GetParent(9)); 116c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.IsNodeUnordered(9)); 117c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.RemoveNode(7)); 118c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.NodeExists(7)); 119c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(9u, forest.GetChild(5)); 120c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(5u, forest.GetParent(9)); 121c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.IsNodeUnordered(9)); 122c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 123c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Remove another node from the middle, with an unordered link on only one 124c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // side. The new merged link should be ordered. 125c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.NodeExists(2)); 126c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(2u, forest.GetChild(1)); 127c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(2u, forest.GetParent(3)); 128c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.IsNodeUnordered(2)); 129c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.IsNodeUnordered(3)); 130c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.RemoveNode(2)); 131c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.NodeExists(2)); 132c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(3u, forest.GetChild(1)); 133c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(1u, forest.GetParent(3)); 134c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.IsNodeUnordered(3)); 135c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 136c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Try removing the root. 137c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.NodeExists(1)); 138c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(0u, forest.GetParent(1)); 139c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(1000, forest.GetPriority(1)); 140c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(1u, forest.GetParent(3)); 141c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(0, forest.GetPriority(3)); 142c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.RemoveNode(1)); 143c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.NodeExists(1)); 144c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(0u, forest.GetParent(3)); 145c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(1000, forest.GetPriority(3)); 146c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 147c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Now try removing the tail. 148c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.NodeExists(9)); 149c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(9u, forest.GetChild(5)); 150c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.RemoveNode(9)); 151c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.NodeExists(9)); 152c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(0u, forest.GetChild(5)); 153c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 154c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ASSERT_TRUE(forest.ValidateInvariantsForTests()); 155c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 156c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 157c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)TEST(SpdyPriorityForestTest, MergeOrderedAndUnorderedLinks1) { 158c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) SpdyPriorityForest<uint32,int16> forest; 159c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddRootNode(1, 1000); 160c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(2, 1, true); 161c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(3, 2, false); 162c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 163c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(2u, forest.GetChild(1)); 164c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(3u, forest.GetChild(2)); 165c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(1u, forest.GetParent(2)); 166c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(2u, forest.GetParent(3)); 167c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.IsNodeUnordered(2)); 168c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.IsNodeUnordered(3)); 169c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.RemoveNode(2)); 170c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.NodeExists(2)); 171c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(3u, forest.GetChild(1)); 172c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(1u, forest.GetParent(3)); 173c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.IsNodeUnordered(3)); 174c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 175c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ASSERT_TRUE(forest.ValidateInvariantsForTests()); 176c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 177c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 178c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)TEST(SpdyPriorityForestTest, MergeOrderedAndUnorderedLinks2) { 179c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) SpdyPriorityForest<uint32,int16> forest; 180c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddRootNode(1, 1000); 181c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(2, 1, false); 182c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(3, 2, true); 183c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 184c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(2u, forest.GetChild(1)); 185c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(3u, forest.GetChild(2)); 186c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(1u, forest.GetParent(2)); 187c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(2u, forest.GetParent(3)); 188c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.IsNodeUnordered(2)); 189c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.IsNodeUnordered(3)); 190c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.RemoveNode(2)); 191c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.NodeExists(2)); 192c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(3u, forest.GetChild(1)); 193c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(1u, forest.GetParent(3)); 194c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.IsNodeUnordered(3)); 195c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 196c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ASSERT_TRUE(forest.ValidateInvariantsForTests()); 197c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 198c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 199c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)TEST(SpdyPriorityForestTest, WeightedSelectionOfForests) { 200c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) SpdyPriorityForest<uint32,int16> forest; 201c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddRootNode(1, 10); 202c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddRootNode(3, 20); 203c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddRootNode(5, 70); 204c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(70, forest.GetPriority(5)); 205c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.SetPriority(5, 40)); 206c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.SetPriority(7, 80)); 207c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(40, forest.GetPriority(5)); 208c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(7, 3, false); 209c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.IsMarkedReadyToRead(1)); 210c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.MarkReadyToRead(1)); 211c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.IsMarkedReadyToRead(1)); 212c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.MarkReadyToRead(5)); 213c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.MarkReadyToRead(7)); 214c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.MarkReadyToRead(99)); 215c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 216c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) int counts[8] = {0}; 217c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) for (int i = 0; i < 7000; ++i) { 218c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const uint32 node_id = forest.NextNodeToRead(); 219c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ASSERT_TRUE(node_id == 1 || node_id == 5 || node_id == 7) 220c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) << "node_id is " << node_id; 221c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ++counts[node_id]; 222c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 223c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 224c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // In theory, these could fail even if the weighted random selection is 225c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // implemented correctly, but it's very unlikely. 226c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_GE(counts[1], 800); EXPECT_LE(counts[1], 1200); 227c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_GE(counts[7], 1600); EXPECT_LE(counts[7], 2400); 228c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_GE(counts[5], 3200); EXPECT_LE(counts[5], 4800); 229c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 230c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // If we unmark all but one node, then we know for sure that that node will 231c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // be selected next. 232c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.MarkNoLongerReadyToRead(1)); 233c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.MarkNoLongerReadyToRead(7)); 234c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.MarkNoLongerReadyToRead(99)); 235c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(5u, forest.NextNodeToRead()); 236c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 237c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ASSERT_TRUE(forest.ValidateInvariantsForTests()); 238c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 239c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 240c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)TEST(SpdyPriorityForestTest, SelectionBetweenUnorderedNodes) { 241c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) SpdyPriorityForest<uint32,int16> forest; 242c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddRootNode(1, 1000); 243c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(2, 1, false); 244c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(3, 2, true); 245c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(4, 3, true); 246c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(5, 4, true); 247c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(6, 5, true); 248c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) forest.AddNonRootNode(7, 6, false); 249c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.IsMarkedReadyToWrite(2)); 250c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.MarkReadyToWrite(2)); 251c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.IsMarkedReadyToWrite(2)); 252c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.MarkReadyToWrite(4)); 253c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.MarkReadyToWrite(6)); 254c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.MarkReadyToWrite(7)); 255c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.MarkReadyToWrite(99)); 256c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 257c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) int counts[8] = {0}; 258c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) for (int i = 0; i < 6000; ++i) { 259c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const uint32 node_id = forest.NextNodeToWrite(); 260c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ASSERT_TRUE(node_id == 2 || node_id == 4 || node_id == 6) 261c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) << "node_id is " << node_id; 262c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ++counts[node_id]; 263c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 264c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 265c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // In theory, these could fail even if the random selection is implemented 266c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // correctly, but it's very unlikely. 267c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_GE(counts[2], 1600); EXPECT_LE(counts[2], 2400); 268c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_GE(counts[4], 1600); EXPECT_LE(counts[4], 2400); 269c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_GE(counts[6], 1600); EXPECT_LE(counts[6], 2400); 270c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 271c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Once we unmark that group of nodes, the next node up should be node 7, 272c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // which has an ordered dependency on said group. 273c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.MarkNoLongerReadyToWrite(2)); 274c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.MarkNoLongerReadyToWrite(4)); 275c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_TRUE(forest.MarkNoLongerReadyToWrite(6)); 276c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_FALSE(forest.MarkNoLongerReadyToWrite(99)); 277c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) EXPECT_EQ(7u, forest.NextNodeToWrite()); 278c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 279c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ASSERT_TRUE(forest.ValidateInvariantsForTests()); 280c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 281c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 282c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} // namespace net 283