Minor code/doc cleanup of SpdyPriorityTree, no functional change.

- Update doc comment to state that Nodes can have multiple children.
- Make Node struct and some related methods private.
- Initialize Node members inline.
- Use nullptr instead of NULL.

This CL lands server change 101618261 by mpw.

BUG=488484

Review URL: https://codereview.chromium.org/1328663002

Cr-Commit-Position: refs/heads/master@{#347945}

2 files changed, 111 insertions, 107 deletions

diff --git a/net/spdy/spdy_priority_tree.h b/net/spdy/spdy_priority_tree.h
index c13268c..66db71a 100644
--- a/net/spdy/spdy_priority_tree.h
+++ b/net/spdy/spdy_priority_tree.h
@@ -18,16 +18,15 @@
 
 namespace net {
 
-// This data structure implements the HTTP2 prioritization data structure
-// defined in draft standard:
-// http://tools.ietf.org/html/draft-ietf-httpbis-http2-13
+// This data structure implements the HTTP/2 stream priority tree defined in
+// section 5.3 of RFC 7540:
+// http://tools.ietf.org/html/rfc7540#section-5.3
 //
-// Nodes can be added and removed, and dependencies between them defined.  Each
-// node can have at most one parent and at most one child (forming a list), but
-// there can be multiple lists, with each list root having its own priority.
-// Individual nodes can also be marked as ready to read/write, and then the
-// whole structure can be queried to pick the next node to read/write out of
-// those ready.
+// Nodes can be added and removed, and dependencies between them defined.
+// Nodes constitute a tree rooted at node ID 0: each node has a single parent
+// node, and 0 or more child nodes.  Individual nodes can be marked as ready to
+// read/write, and then the whole structure can be queried to pick the next
+// node to read/write out of those that are ready.
 //
 // The NodeId type must be a POD that supports comparison (most
 // likely, it will be a number).
@@ -50,27 +49,6 @@ class SpdyPriorityTree {
   SpdyPriorityTree();
   ~SpdyPriorityTree();
 
-  typedef std::list<NodeId> List;
-  struct Node {
-    Node();
-    ~Node();
-
-    NodeId id;
-    NodeId parent_id;
-    int weight;  // Weights can range between 1 and 256 (inclusive).
-    // The total weight of this node's direct descendants.
-    int total_child_weights;
-    // The total weight of direct descendants that are writeable
-    // (ready to write and not blocked). This value does not necessarily
-    // reflect the current state of the tree; instead, we lazily update it
-    // on calls to PropagateNodeState(node.id).
-    int total_writeable_child_weights;
-    List* child_list;  // node ID's of children, if any
-    bool blocked;  // Is the associated stream write-blocked?
-    bool ready;  // Does the stream have data ready for writing?
-    float priority;  // The fraction of resources to dedicate to this node.
-  };
-
   // Orders in descending order of priority.
   struct NodePriorityComparator {
     bool operator ()(const std::pair<NodeId, float>& lhs,
@@ -130,25 +108,53 @@ class SpdyPriorityTree {
   // if unable to mark the specified node.
   bool SetReady(NodeId node_id, bool ready);
 
-  // Return true if all internal invariants hold (useful for unit tests).
-  // Unless there are bugs, this should always return true.
-  bool ValidateInvariantsForTests() const;
-
-  // Get the given node, or return NULL if it doesn't exist.
-  const Node* FindNode(NodeId node_id) const;
-
   // Returns an ordered list of writeable nodes and their priorities.
   // Priority is calculated as:
   // parent's priority * (node's weight / sum of sibling weights)
   PriorityNodeList GetPriorityList();
 
- protected:
+ private:
+  typedef std::list<NodeId> List;
+
+  struct Node {
+    Node();
+    ~Node();
+
+    // ID for this node.
+    NodeId id;
+    // ID of parent node.
+    NodeId parent_id;
+    // Weights can range between 1 and 256 (inclusive).
+    int weight;
+    // The total weight of this node's direct descendants.
+    int total_child_weights;
+    // The total weight of direct descendants that are writeable
+    // (ready to write and not blocked). This value does not necessarily
+    // reflect the current state of the tree; instead, we lazily update it
+    // on calls to PropagateNodeState(node.id).
+    int total_writeable_child_weights;
+    // Node IDs of children, if any.
+    List* child_list;
+    // Is the associated stream write-blocked?
+    bool blocked;
+    // Does the stream have data ready for writing?
+    bool ready;
+    // The fraction of resources to dedicate to this node.
+    float priority;
+  };
+
+  typedef base::hash_map<NodeId, Node> NodeMap;
+
   // Update the value of total_writeable_child_weights for the given node
   // to reflect the current state of the tree.
   void PropagateNodeState(NodeId node);
 
- private:
-  typedef base::hash_map<NodeId, Node> NodeMap;
+  // Get the given node, or return nullptr if it doesn't exist.
+  const Node* FindNode(NodeId node_id) const;
+
+  // Return true if all internal invariants hold (useful for unit tests).
+  // Unless there are bugs, this should always return true.
+  bool ValidateInvariantsForTests() const;
 
   NodeMap all_nodes_;  // maps from node IDs to Node objects
 
diff --git a/net/spdy/spdy_priority_tree_test.cc b/net/spdy/spdy_priority_tree_test.cc
index e84d079..35ff68d 100644
--- a/net/spdy/spdy_priority_tree_test.cc
+++ b/net/spdy/spdy_priority_tree_test.cc
@@ -17,16 +17,39 @@ class SpdyPriorityTreePeer {
  public:
   explicit SpdyPriorityTreePeer(SpdyPriorityTree<NodeId>* tree) : tree_(tree) {}
 
-  void PropagateNodeState(NodeId node) {
-    tree_->PropagateNodeState(node);
+  void PropagateNodeState(NodeId node_id) {
+    tree_->PropagateNodeState(node_id);
+  }
+
+  int TotalChildWeights(NodeId node_id) const {
+    return tree_->FindNode(node_id)->total_child_weights;
+  }
+
+  int TotalWriteableChildWeights(NodeId node_id) const {
+    return tree_->FindNode(node_id)->total_writeable_child_weights;
+  }
+
+  bool ValidateInvariants() const {
+    return tree_->ValidateInvariantsForTests();
   }
 
  private:
   SpdyPriorityTree<NodeId>* tree_;
 };
 
-TEST(SpdyPriorityTreeTest, AddAndRemoveNodes) {
-  SpdyPriorityTree<uint32> tree;
+class SpdyPriorityTreeTest : public ::testing::Test {
+ protected:
+  typedef uint32 SpdyStreamId;
+  typedef std::pair<SpdyStreamId, float> PriorityNode;
+  typedef std::vector<PriorityNode> PriorityList;
+
+  SpdyPriorityTreeTest() : peer(&tree) {}
+
+  SpdyPriorityTree<SpdyStreamId> tree;
+  SpdyPriorityTreePeer<SpdyStreamId> peer;
+};
+
+TEST_F(SpdyPriorityTreeTest, AddAndRemoveNodes) {
   EXPECT_EQ(1, tree.num_nodes());
   EXPECT_TRUE(tree.NodeExists(0));
   EXPECT_FALSE(tree.NodeExists(1));
@@ -79,11 +102,10 @@ TEST(SpdyPriorityTreeTest, AddAndRemoveNodes) {
   EXPECT_TRUE(tree.SetWeight(17, 150));
   EXPECT_EQ(150, tree.GetWeight(17));
 
-  ASSERT_TRUE(tree.ValidateInvariantsForTests());
+  ASSERT_TRUE(peer.ValidateInvariants());
 }
 
-TEST(SpdyPriorityTreeTest, SetParent) {
-  SpdyPriorityTree<uint32> tree;
+TEST_F(SpdyPriorityTreeTest, SetParent) {
   tree.AddNode(1, 0, 100, false);
   tree.AddNode(2, 1, 20, false);
   tree.AddNode(3, 2, 30, false);
@@ -119,10 +141,10 @@ TEST(SpdyPriorityTreeTest, SetParent) {
   EXPECT_EQ(1u, tree.GetParent(2));
   EXPECT_TRUE(tree.HasChild(1, 2));
 
-  ASSERT_TRUE(tree.ValidateInvariantsForTests());
+  ASSERT_TRUE(peer.ValidateInvariants());
 }
 
-TEST(SpdyPriorityTreeTest, BlockAndUnblock) {
+TEST_F(SpdyPriorityTreeTest, BlockAndUnblock) {
   /* Create the tree.
 
            0
@@ -136,8 +158,6 @@ TEST(SpdyPriorityTreeTest, BlockAndUnblock) {
    15 16
 
   */
-  SpdyPriorityTree<uint32> tree;
-  SpdyPriorityTreePeer<uint32> tree_peer(&tree);
   tree.AddNode(1, 0, 100, false);
   tree.AddNode(2, 0, 100, false);
   tree.AddNode(3, 0, 100, false);
@@ -171,18 +191,14 @@ TEST(SpdyPriorityTreeTest, BlockAndUnblock) {
   EXPECT_EQ(7u, tree.GetParent(14));
   EXPECT_EQ(8u, tree.GetParent(15));
   EXPECT_EQ(8u, tree.GetParent(16));
-  ASSERT_TRUE(tree.ValidateInvariantsForTests());
-
-  EXPECT_EQ(tree.FindNode(0)->total_child_weights,
-            tree.FindNode(1)->weight +
-            tree.FindNode(2)->weight +
-            tree.FindNode(3)->weight);
-  EXPECT_EQ(tree.FindNode(3)->total_child_weights,
-            tree.FindNode(7)->weight);
-  EXPECT_EQ(tree.FindNode(7)->total_child_weights,
-            tree.FindNode(13)->weight + tree.FindNode(14)->weight);
-  EXPECT_EQ(tree.FindNode(13)->total_child_weights, 0);
-  EXPECT_EQ(tree.FindNode(14)->total_child_weights, 0);
+  ASSERT_TRUE(peer.ValidateInvariants());
+
+  EXPECT_EQ(peer.TotalChildWeights(0),
+            tree.GetWeight(1) + tree.GetWeight(2) + tree.GetWeight(3));
+  EXPECT_EQ(peer.TotalChildWeights(3), tree.GetWeight(7));
+  EXPECT_EQ(peer.TotalChildWeights(7), tree.GetWeight(13) + tree.GetWeight(14));
+  EXPECT_EQ(peer.TotalChildWeights(13), 0);
+  EXPECT_EQ(peer.TotalChildWeights(14), 0);
 
   // Set all nodes ready to write.
   EXPECT_TRUE(tree.SetReady(1, true));
@@ -205,63 +221,51 @@ TEST(SpdyPriorityTreeTest, BlockAndUnblock) {
   // Number of readable child weights should not change because
   // 7 has unblocked children.
   tree.SetBlocked(7, true);
-  tree_peer.PropagateNodeState(kRootNodeId);
-  EXPECT_EQ(tree.FindNode(3)->total_child_weights,
-            tree.FindNode(3)->total_writeable_child_weights);
+  peer.PropagateNodeState(kRootNodeId);
+  EXPECT_EQ(peer.TotalChildWeights(3), peer.TotalWriteableChildWeights(3));
 
   // Readable children for 7 should decrement.
   // Number of readable child weights for 3 still should not change.
   tree.SetBlocked(13, true);
-  tree_peer.PropagateNodeState(kRootNodeId);
-  EXPECT_EQ(tree.FindNode(3)->total_child_weights,
-            tree.FindNode(3)->total_writeable_child_weights);
-  EXPECT_EQ(tree.FindNode(14)->weight,
-            tree.FindNode(7)->total_writeable_child_weights);
+  peer.PropagateNodeState(kRootNodeId);
+  EXPECT_EQ(peer.TotalChildWeights(3), peer.TotalWriteableChildWeights(3));
+  EXPECT_EQ(tree.GetWeight(14), peer.TotalWriteableChildWeights(7));
 
   // Once 14 becomes blocked, readable children for 7 and 3 should both be
   // decremented. Total readable weights at the root should still be the same
   // because 3 is still writeable.
   tree.SetBlocked(14, true);
-  tree_peer.PropagateNodeState(kRootNodeId);
-  EXPECT_EQ(0, tree.FindNode(3)->total_writeable_child_weights);
-  EXPECT_EQ(0, tree.FindNode(7)->total_writeable_child_weights);
-  EXPECT_EQ(tree.FindNode(0)->total_child_weights,
-            tree.FindNode(1)->weight +
-            tree.FindNode(2)->weight +
-            tree.FindNode(3)->weight);
+  peer.PropagateNodeState(kRootNodeId);
+  EXPECT_EQ(0, peer.TotalWriteableChildWeights(3));
+  EXPECT_EQ(0, peer.TotalWriteableChildWeights(7));
+  EXPECT_EQ(peer.TotalChildWeights(0),
+            tree.GetWeight(1) + tree.GetWeight(2) + tree.GetWeight(3));
 
   // And now the root should be decremented as well.
   tree.SetBlocked(3, true);
-  tree_peer.PropagateNodeState(kRootNodeId);
-  EXPECT_EQ(tree.FindNode(1)->weight + tree.FindNode(2)->weight,
-            tree.FindNode(0)->total_writeable_child_weights);
+  peer.PropagateNodeState(kRootNodeId);
+  EXPECT_EQ(tree.GetWeight(1) + tree.GetWeight(2),
+            peer.TotalWriteableChildWeights(0));
 
   // Unblocking 7 should propagate all the way up to the root.
   tree.SetBlocked(7, false);
-  tree_peer.PropagateNodeState(kRootNodeId);
-  EXPECT_EQ(tree.FindNode(0)->total_writeable_child_weights,
-            tree.FindNode(1)->weight +
-            tree.FindNode(2)->weight +
-            tree.FindNode(3)->weight);
-  EXPECT_EQ(tree.FindNode(3)->total_writeable_child_weights,
-            tree.FindNode(7)->weight);
-  EXPECT_EQ(0, tree.FindNode(7)->total_writeable_child_weights);
+  peer.PropagateNodeState(kRootNodeId);
+  EXPECT_EQ(peer.TotalWriteableChildWeights(0),
+            tree.GetWeight(1) + tree.GetWeight(2) + tree.GetWeight(3));
+  EXPECT_EQ(peer.TotalWriteableChildWeights(3), tree.GetWeight(7));
+  EXPECT_EQ(0, peer.TotalWriteableChildWeights(7));
 
   // Ditto for reblocking 7.
   tree.SetBlocked(7, true);
-  tree_peer.PropagateNodeState(kRootNodeId);
-  EXPECT_EQ(tree.FindNode(0)->total_writeable_child_weights,
-            tree.FindNode(1)->weight + tree.FindNode(2)->weight);
-  EXPECT_EQ(0, tree.FindNode(3)->total_writeable_child_weights);
-  EXPECT_EQ(0, tree.FindNode(7)->total_writeable_child_weights);
-  ASSERT_TRUE(tree.ValidateInvariantsForTests());
+  peer.PropagateNodeState(kRootNodeId);
+  EXPECT_EQ(peer.TotalWriteableChildWeights(0),
+            tree.GetWeight(1) + tree.GetWeight(2));
+  EXPECT_EQ(0, peer.TotalWriteableChildWeights(3));
+  EXPECT_EQ(0, peer.TotalWriteableChildWeights(7));
+  ASSERT_TRUE(peer.ValidateInvariants());
 }
 
-TEST(SpdyPriorityTreeTest, GetPriorityList) {
-  typedef uint32 SpdyStreamId;
-  typedef std::pair<SpdyStreamId, float> PriorityNode;
-  typedef std::vector<PriorityNode> PriorityList;
-
+TEST_F(SpdyPriorityTreeTest, GetPriorityList) {
   PriorityList expected_list;
   PriorityList priority_list;
 
@@ -276,7 +280,6 @@ TEST(SpdyPriorityTreeTest, GetPriorityList) {
      8
 
   */
-  SpdyPriorityTree<uint32> tree;
   tree.AddNode(1, 0, 10, false);
   tree.AddNode(2, 0, 20, false);
   tree.AddNode(3, 0, 30, false);
@@ -363,11 +366,7 @@ TEST(SpdyPriorityTreeTest, GetPriorityList) {
   EXPECT_EQ(expected_list, priority_list);
 }
 
-TEST(SpdyPriorityTreeTest, CalculateRoundedWeights) {
-  typedef uint32 SpdyStreamId;
-  typedef std::pair<SpdyStreamId, float> PriorityNode;
-  typedef std::vector<PriorityNode> PriorityList;
-
+TEST_F(SpdyPriorityTreeTest, CalculateRoundedWeights) {
   PriorityList expected_list;
   PriorityList priority_list;
 
@@ -379,7 +378,6 @@ TEST(SpdyPriorityTreeTest, CalculateRoundedWeights) {
        //|\  |\
       83 4 5 6 7
   */
-  SpdyPriorityTree<uint32> tree;
   tree.AddNode(3, 0, 100, false);
   tree.AddNode(4, 0, 100, false);
   tree.AddNode(5, 0, 100, false);