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