Add SpdyPriorityForest class

This lands server change 44685956.

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

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@192910 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 811 insertions, 0 deletions

diff --git a/net/net.gyp b/net/net.gyp
index 4a4f1fa..69024d7 100644
--- a/net/net.gyp
+++ b/net/net.gyp
@@ -849,6 +849,7 @@
         'spdy/spdy_http_utils.h',
         'spdy/spdy_io_buffer.cc',
         'spdy/spdy_io_buffer.h',
+        'spdy/spdy_priority_forest.h',
         'spdy/spdy_protocol.cc',
         'spdy/spdy_protocol.h',
         'spdy/spdy_proxy_client_socket.cc',
@@ -1635,6 +1636,7 @@
         'spdy/spdy_http_utils_unittest.cc',
         'spdy/spdy_network_transaction_spdy3_unittest.cc',
         'spdy/spdy_network_transaction_spdy2_unittest.cc',
+        'spdy/spdy_priority_forest_test.cc',
         'spdy/spdy_protocol_test.cc',
         'spdy/spdy_proxy_client_socket_spdy3_unittest.cc',
         'spdy/spdy_proxy_client_socket_spdy2_unittest.cc',
diff --git a/net/spdy/spdy_priority_forest.h b/net/spdy/spdy_priority_forest.h
new file mode 100644
index 0000000..cc7200d
--- /dev/null
+++ b/net/spdy/spdy_priority_forest.h
@@ -0,0 +1,527 @@
+// Copyright (c) 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef NET_SPDY_SPDY_PRIORITY_FOREST_H_
+#define NET_SPDY_SPDY_PRIORITY_FOREST_H_
+
+#include <map>
+#include <set>
+
+#include "base/basictypes.h"
+#include "base/hash_tables.h"
+#include "base/logging.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/rand_util.h"
+
+namespace net {
+
+// This data structure implements the SPDY prioriziation data structures
+// defined in this document: http://go/spdy4-prioritization
+//
+// 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.
+//
+// The NodeId and Priority types must be POD that support comparison (most
+// likely, they will be numbers).
+template <typename NodeId, typename Priority>
+class SpdyPriorityForest {
+ public:
+  SpdyPriorityForest();
+  ~SpdyPriorityForest();
+
+  // Return the number of nodes currently in the forest.
+  int num_nodes() const;
+
+  // Return true if the forest contains a node with the given ID.
+  bool NodeExists(NodeId node_id) const;
+
+  // Add a new root node to the forest, with the given priority.  Returns true
+  // on success, or false if the node_id already exists within the forest.
+  bool AddRootNode(NodeId node_id, Priority priority);
+
+  // Add a new node to the forest, with the given parent.  Returns true on
+  // success.  Returns false and has no effect if the new node already exists,
+  // or if the parent doesn't exist, or if the parent already has a child.
+  bool AddNonRootNode(NodeId node_id, NodeId parent_id, bool unordered);
+
+  // Remove an existing node from the forest.  Returns true on success, or
+  // false if the node doesn't exist.
+  bool RemoveNode(NodeId node_id);
+
+  // Get the priority of the given node.  If the node doesn't exist, or is not
+  // a root node (and thus has no priority), returns Priority().
+  Priority GetPriority(NodeId node_id) const;
+
+  // Get the parent of the given node.  If the node doesn't exist, or is a root
+  // node (and thus has no parent), returns NodeId().
+  NodeId GetParent(NodeId node_id) const;
+
+  // Determine if the given node is unordered with respect to its parent.  If
+  // the node doesn't exist, or is a root node (and thus has no parent),
+  // returns false.
+  bool IsNodeUnordered(NodeId node_id) const;
+
+  // Get the child of the given node.  If the node doesn't exist, or has no
+  // child, returns NodeId().
+  NodeId GetChild(NodeId node_id) const;
+
+  // Set the priority of the given node.  If the node was not already a root
+  // node, this makes it a root node.  Returns true on success, or false if the
+  // node doesn't exist.
+  bool SetPriority(NodeId node_id, Priority priority);
+
+  // Set the parent of the given node.  If the node was a root node, this makes
+  // it no longer a root.  Returns true on success.  Returns false and has no
+  // effect if (1) the node and/or the parent doesn't exist, (2) the new parent
+  // already has a different child than the node, or (3) if the new parent is a
+  // descendant of the node (so this would have created a cycle).
+  bool SetParent(NodeId node_id, NodeId parent_id, bool unordered);
+
+  // Check if a node is marked as ready to read.  Returns false if the node
+  // doesn't exist.
+  bool IsMarkedReadyToRead(NodeId node_id) const;
+  // Mark the node as ready or not ready to read.  Returns true on success, or
+  // false if the node doesn't exist.
+  bool MarkReadyToRead(NodeId node_id);
+  bool MarkNoLongerReadyToRead(NodeId node_id);
+  // Return the ID of the next node that we should read, or return NodeId() if
+  // no node in the forest is ready to read.
+  NodeId NextNodeToRead();
+
+  // Check if a node is marked as ready to write.  Returns false if the node
+  // doesn't exist.
+  bool IsMarkedReadyToWrite(NodeId node_id) const;
+  // Mark the node as ready or not ready to write.  Returns true on success, or
+  // false if the node doesn't exist.
+  bool MarkReadyToWrite(NodeId node_id);
+  bool MarkNoLongerReadyToWrite(NodeId node_id);
+  // Return the ID of the next node that we should write, or return NodeId() if
+  // no node in the forest is ready to write.
+  NodeId NextNodeToWrite();
+
+  // Return true if all internal invariants hold (useful for unit tests).
+  // Unless there are bugs, this should always return true.
+  bool ValidateInvariantsForTests() const;
+
+ private:
+  enum NodeType { ROOT_NODE, NONROOT_ORDERED, NONROOT_UNORDERED };
+  struct Node {
+    Node() : type(ROOT_NODE), flags(0), child() {
+      depends_on.priority = Priority();
+    }
+    NodeType type;
+    unsigned int flags;  // bitfield of flags
+    union {
+      Priority priority;  // used for root nodes
+      NodeId parent_id;  // used for non-root nodes
+    } depends_on;
+    NodeId child;  // node ID of child (or NodeId() for no child)
+  };
+
+  typedef base::hash_map<NodeId, Node> NodeMap;
+
+  // Constants for the Node.flags bitset:
+  // kReadToRead: set for nodes that are ready for reading
+  static const unsigned int kReadyToRead = (1 << 0);
+  // kReadToWrite: set for nodes that are ready for writing
+  static const unsigned int kReadyToWrite = (1 << 1);
+
+  // Common code for IsMarkedReadyToRead and IsMarkedReadyToWrite.
+  bool IsMarked(NodeId node_id, unsigned int flag) const;
+  // Common code for MarkReadyToRead and MarkReadyToWrite.
+  bool Mark(NodeId node_id, unsigned int flag);
+  // Common code for MarkNoLongerReadyToRead and MarkNoLongerReadyToWrite.
+  bool Unmark(NodeId node_id, unsigned int flag);
+  // Common code for NextNodeToRead and NextNodeToWrite;
+  NodeId FirstMarkedNode(unsigned int flag);
+  // Get the given node, or return NULL if it doesn't exist.
+  const Node* FindNode(NodeId node_id) const;
+
+  NodeMap all_nodes_;  // maps from node IDs to Node objects
+
+  DISALLOW_COPY_AND_ASSIGN(SpdyPriorityForest);
+};
+
+template <typename NodeId, typename Priority>
+SpdyPriorityForest<NodeId, Priority>::SpdyPriorityForest() {}
+
+template <typename NodeId, typename Priority>
+SpdyPriorityForest<NodeId, Priority>::~SpdyPriorityForest() {}
+
+template <typename NodeId, typename Priority>
+int SpdyPriorityForest<NodeId, Priority>::num_nodes() const {
+  return all_nodes_.size();
+}
+
+template <typename NodeId, typename Priority>
+bool SpdyPriorityForest<NodeId, Priority>::NodeExists(NodeId node_id) const {
+  return all_nodes_.count(node_id) != 0;
+}
+
+template <typename NodeId, typename Priority>
+bool SpdyPriorityForest<NodeId, Priority>::AddRootNode(
+    NodeId node_id, Priority priority) {
+  if (NodeExists(node_id)) {
+    return false;
+  }
+  Node* new_node = &all_nodes_[node_id];
+  new_node->type = ROOT_NODE;
+  new_node->depends_on.priority = priority;
+  return true;
+}
+
+template <typename NodeId, typename Priority>
+bool SpdyPriorityForest<NodeId, Priority>::AddNonRootNode(
+    NodeId node_id, NodeId parent_id, bool unordered) {
+  if (NodeExists(node_id) || !NodeExists(parent_id)) {
+    return false;
+  }
+
+  Node* parent = &all_nodes_[parent_id];
+  if (parent->child != NodeId()) {
+    return false;
+  }
+
+  Node* new_node = &all_nodes_[node_id];
+  new_node->type = (unordered ? NONROOT_UNORDERED : NONROOT_ORDERED);
+  new_node->depends_on.parent_id = parent_id;
+  parent->child = node_id;
+  return true;
+}
+
+template <typename NodeId, typename Priority>
+bool SpdyPriorityForest<NodeId, Priority>::RemoveNode(NodeId node_id) {
+  if (!NodeExists(node_id)) {
+    return false;
+  }
+  const Node& node = all_nodes_[node_id];
+
+  // If the node to be removed is not a root node, we need to change its
+  // parent's child ID.
+  if (node.type != ROOT_NODE) {
+    DCHECK(NodeExists(node.depends_on.parent_id));
+    Node* parent = &all_nodes_[node.depends_on.parent_id];
+    DCHECK_EQ(node_id, parent->child);
+    parent->child = node.child;
+  }
+
+  // If the node has a child, we need to change the child's priority or parent.
+  if (node.child != NodeId()) {
+    DCHECK(NodeExists(node.child));
+    Node* child = &all_nodes_[node.child];
+    DCHECK_NE(ROOT_NODE, child->type);
+    DCHECK_EQ(node_id, child->depends_on.parent_id);
+    // Make the child's new depends_on be the node's depends_on (whether that
+    // be a priority or a parent node ID).
+    child->depends_on = node.depends_on;
+    // If the removed node was a root, its child is now a root.  Otherwise, the
+    // child will be be unordered if and only if it was already unordered and
+    // the removed not is also not ordered.
+    if (node.type == ROOT_NODE) {
+      child->type = ROOT_NODE;
+    } else if (node.type == NONROOT_ORDERED) {
+      child->type = NONROOT_ORDERED;
+    }
+  }
+
+  // Delete the node.
+  all_nodes_.erase(node_id);
+  return true;
+}
+
+template <typename NodeId, typename Priority>
+Priority SpdyPriorityForest<NodeId, Priority>::GetPriority(
+    NodeId node_id) const {
+  const Node* node = FindNode(node_id);
+  if (node != NULL && node->type == ROOT_NODE) {
+    return node->depends_on.priority;
+  } else {
+    return Priority();
+  }
+}
+
+template <typename NodeId, typename Priority>
+NodeId SpdyPriorityForest<NodeId, Priority>::GetParent(NodeId node_id) const {
+  const Node* node = FindNode(node_id);
+  if (node != NULL && node->type != ROOT_NODE) {
+    return node->depends_on.parent_id;
+  } else {
+    return NodeId();
+  }
+}
+
+template <typename NodeId, typename Priority>
+bool SpdyPriorityForest<NodeId, Priority>::IsNodeUnordered(
+    NodeId node_id) const {
+  const Node* node = FindNode(node_id);
+  return node != NULL && node->type == NONROOT_UNORDERED;
+}
+
+template <typename NodeId, typename Priority>
+NodeId SpdyPriorityForest<NodeId, Priority>::GetChild(NodeId node_id) const {
+  const Node* node = FindNode(node_id);
+  if (node != NULL) {
+    return node->child;
+  } else {
+    return NodeId();
+  }
+}
+
+template <typename NodeId, typename Priority>
+bool SpdyPriorityForest<NodeId, Priority>::SetPriority(
+    NodeId node_id, Priority priority) {
+  if (!NodeExists(node_id)) {
+    return false;
+  }
+
+  Node* node = &all_nodes_[node_id];
+  // If this is not already a root node, we need to make it be a root node.
+  if (node->type != ROOT_NODE) {
+    DCHECK(NodeExists(node->depends_on.parent_id));
+    Node* parent = &all_nodes_[node->depends_on.parent_id];
+    parent->child = NodeId();
+    node->type = ROOT_NODE;
+  }
+
+  node->depends_on.priority = priority;
+  return true;
+}
+
+template <typename NodeId, typename Priority>
+bool SpdyPriorityForest<NodeId, Priority>::SetParent(
+    NodeId node_id, NodeId parent_id, bool unordered) {
+  if (!NodeExists(node_id) || !NodeExists(parent_id)) {
+    return false;
+  }
+
+  Node* node = &all_nodes_[node_id];
+  Node* new_parent = &all_nodes_[parent_id];
+  // If the new parent is already the node's parent, all we have to do is
+  // update the node type and we're done.
+  if (new_parent->child == node_id) {
+    node->type = (unordered ? NONROOT_UNORDERED : NONROOT_ORDERED);
+    return true;
+  }
+  // Otherwise, if the new parent already has a child, we fail.
+  if (new_parent->child != NodeId()) {
+    return false;
+  }
+
+  // Next, make sure we won't create a cycle.
+  if (node_id == parent_id) return false;
+  Node* last = node;
+  NodeId last_id = node_id;
+  while (last->child != NodeId()) {
+    if (last->child == parent_id) return false;
+    last_id = last->child;
+    DCHECK(NodeExists(last_id));
+    last = &all_nodes_[last_id];
+  }
+
+  // If the node is not a root, we need clear its old parent's child field
+  // (unless the old parent is the same as the new parent).
+  if (node->type != ROOT_NODE) {
+    const NodeId old_parent_id = node->depends_on.parent_id;
+    DCHECK(NodeExists(old_parent_id));
+    DCHECK(old_parent_id != parent_id);
+    Node* old_parent = &all_nodes_[old_parent_id];
+    DCHECK_EQ(node_id, old_parent->child);
+    old_parent->child = NodeId();
+  }
+
+  // Make the change.
+  node->type = (unordered ? NONROOT_UNORDERED : NONROOT_ORDERED);
+  node->depends_on.parent_id = parent_id;
+  new_parent->child = node_id;
+  return true;
+}
+
+template <typename NodeId, typename Priority>
+bool SpdyPriorityForest<NodeId, Priority>::IsMarkedReadyToRead(
+    NodeId node_id) const {
+  return IsMarked(node_id, kReadyToRead);
+}
+
+template <typename NodeId, typename Priority>
+bool SpdyPriorityForest<NodeId, Priority>::MarkReadyToRead(NodeId node_id) {
+  return Mark(node_id, kReadyToRead);
+}
+
+template <typename NodeId, typename Priority>
+bool SpdyPriorityForest<NodeId, Priority>::MarkNoLongerReadyToRead(
+    NodeId node_id) {
+  return Unmark(node_id, kReadyToRead);
+}
+
+template <typename NodeId, typename Priority>
+NodeId SpdyPriorityForest<NodeId, Priority>::NextNodeToRead() {
+  return FirstMarkedNode(kReadyToRead);
+}
+
+template <typename NodeId, typename Priority>
+bool SpdyPriorityForest<NodeId, Priority>::IsMarkedReadyToWrite(
+    NodeId node_id) const {
+  return IsMarked(node_id, kReadyToWrite);
+}
+
+template <typename NodeId, typename Priority>
+bool SpdyPriorityForest<NodeId, Priority>::MarkReadyToWrite(NodeId node_id) {
+  return Mark(node_id, kReadyToWrite);
+}
+
+template <typename NodeId, typename Priority>
+bool SpdyPriorityForest<NodeId, Priority>::MarkNoLongerReadyToWrite(
+    NodeId node_id) {
+  return Unmark(node_id, kReadyToWrite);
+}
+
+template <typename NodeId, typename Priority>
+NodeId SpdyPriorityForest<NodeId, Priority>::NextNodeToWrite() {
+  return FirstMarkedNode(kReadyToWrite);
+}
+
+template <typename NodeId, typename Priority>
+bool SpdyPriorityForest<NodeId, Priority>::IsMarked(
+    NodeId node_id, unsigned int flag) const {
+  const Node* node = FindNode(node_id);
+  return node != NULL && (node->flags & flag) != 0;
+}
+
+template <typename NodeId, typename Priority>
+bool SpdyPriorityForest<NodeId, Priority>::Mark(
+    NodeId node_id, unsigned int flag) {
+  if (!NodeExists(node_id)) {
+    return false;
+  }
+  all_nodes_[node_id].flags |= flag;
+  return true;
+}
+
+template <typename NodeId, typename Priority>
+bool SpdyPriorityForest<NodeId, Priority>::Unmark(
+    NodeId node_id, unsigned int flag) {
+  if (!NodeExists(node_id)) {
+    return false;
+  }
+  all_nodes_[node_id].flags &= ~flag;
+  return true;
+}
+
+template <typename NodeId, typename Priority>
+NodeId SpdyPriorityForest<NodeId, Priority>::FirstMarkedNode(
+    unsigned int flag) {
+  // TODO(mdsteele): This is an *incredibly* stupid brute force solution.
+
+  // Get all root nodes that have at least one marked child.
+  uint64 total_weight = 0;
+  std::map<uint64, NodeId> roots;  // maps cumulative weight to root node ID
+  for (typename NodeMap::const_iterator iter = all_nodes_.begin();
+       iter != all_nodes_.end(); ++iter) {
+    const NodeId root_id = iter->first;
+    const Node& root = iter->second;
+    if (root.type == ROOT_NODE) {
+      // See if there is at least one marked node in this root's chain.
+      for (const Node* node = &root; ; node = &all_nodes_[node->child]) {
+        if ((node->flags & flag) != 0) {
+          total_weight += static_cast<uint64>(root.depends_on.priority);
+          roots[total_weight] = root_id;
+          break;
+        }
+        if (node->child == NodeId()) {
+          break;
+        }
+        DCHECK(NodeExists(node->child));
+      }
+    }
+  }
+
+  // If there are no ready nodes, then return NodeId().
+  if (total_weight == 0) {
+    DCHECK(roots.empty());
+    return NodeId();
+  } else {
+    DCHECK(!roots.empty());
+  }
+
+  // Randomly select a tree to use.
+  typename std::map<uint64, NodeId>::const_iterator root_iter =
+      roots.upper_bound(base::RandGenerator(total_weight));
+  DCHECK(root_iter != roots.end());
+  const NodeId root_id = root_iter->second;
+
+  // Find the first node in the chain that is ready.
+  NodeId node_id = root_id;
+  while (true) {
+    DCHECK(NodeExists(node_id));
+    Node* node = &all_nodes_[node_id];
+    if ((node->flags & flag) != 0) {
+      // There might be more nodes that are ready and that are linked to this
+      // one in an unordered chain.  Find all of them, then pick one randomly.
+      std::vector<NodeId> group;
+      group.push_back(node_id);
+      for (Node* next = node; next->child != NodeId();) {
+        DCHECK(NodeExists(next->child));
+        Node *child = &all_nodes_[next->child];
+        DCHECK_NE(ROOT_NODE, child->type);
+        if (child->type != NONROOT_UNORDERED) {
+          break;
+        }
+        if ((child->flags & flag) != 0) {
+          group.push_back(next->child);
+        }
+        next = child;
+      }
+      return group[base::RandGenerator(group.size())];
+    }
+    node_id = node->child;
+  }
+}
+
+template <typename NodeId, typename Priority>
+const typename SpdyPriorityForest<NodeId, Priority>::Node*
+SpdyPriorityForest<NodeId, Priority>::FindNode(NodeId node_id) const {
+  typename NodeMap::const_iterator iter = all_nodes_.find(node_id);
+  if (iter == all_nodes_.end()) {
+    return NULL;
+  }
+  return &iter->second;
+}
+
+template <typename NodeId, typename Priority>
+bool SpdyPriorityForest<NodeId, Priority>::ValidateInvariantsForTests() const {
+  for (typename NodeMap::const_iterator iter = all_nodes_.begin();
+       iter != all_nodes_.end(); ++iter) {
+    const NodeId node_id = iter->first;
+    const Node& node = iter->second;
+    if (node.type != ROOT_NODE &&
+        (!NodeExists(node.depends_on.parent_id) ||
+         GetChild(node.depends_on.parent_id) != node_id)) {
+      return false;
+    }
+    if (node.child != NodeId()) {
+      if (!NodeExists(node.child) || node_id != GetParent(node.child)) {
+        return false;
+      }
+    }
+
+    NodeId child_id = node.child;
+    int count = 0;
+    while (child_id != NodeId()) {
+      if (count > num_nodes() || node_id == child_id) {
+        return false;
+      }
+      child_id = GetChild(child_id);
+      ++count;
+    }
+  }
+  return true;
+}
+
+}  // namespace net
+
+#endif  // NET_SPDY_SPDY_PRIORITY_FOREST_H_
diff --git a/net/spdy/spdy_priority_forest_test.cc b/net/spdy/spdy_priority_forest_test.cc
new file mode 100644
index 0000000..58b21d4
--- /dev/null
+++ b/net/spdy/spdy_priority_forest_test.cc
@@ -0,0 +1,282 @@
+// Copyright (c) 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/spdy/spdy_priority_forest.h"
+
+#include "base/basictypes.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace net {
+
+TEST(SpdyPriorityForestTest, AddAndRemoveNodes) {
+  SpdyPriorityForest<uint32,int16> forest;
+  EXPECT_EQ(0, forest.num_nodes());
+  EXPECT_FALSE(forest.NodeExists(1));
+
+  EXPECT_TRUE(forest.AddRootNode(1, 1000));
+  EXPECT_EQ(1, forest.num_nodes());
+  ASSERT_TRUE(forest.NodeExists(1));
+  EXPECT_EQ(1000, forest.GetPriority(1));
+  EXPECT_FALSE(forest.NodeExists(5));
+
+  EXPECT_TRUE(forest.AddRootNode(5, 50));
+  EXPECT_FALSE(forest.AddRootNode(5, 500));
+  EXPECT_EQ(2, forest.num_nodes());
+  EXPECT_TRUE(forest.NodeExists(1));
+  ASSERT_TRUE(forest.NodeExists(5));
+  EXPECT_EQ(50, forest.GetPriority(5));
+  EXPECT_FALSE(forest.NodeExists(13));
+
+  EXPECT_TRUE(forest.AddRootNode(13, 130));
+  EXPECT_EQ(3, forest.num_nodes());
+  EXPECT_TRUE(forest.NodeExists(1));
+  EXPECT_TRUE(forest.NodeExists(5));
+  ASSERT_TRUE(forest.NodeExists(13));
+  EXPECT_EQ(130, forest.GetPriority(13));
+
+  EXPECT_TRUE(forest.RemoveNode(5));
+  EXPECT_FALSE(forest.RemoveNode(5));
+  EXPECT_EQ(2, forest.num_nodes());
+  EXPECT_TRUE(forest.NodeExists(1));
+  EXPECT_FALSE(forest.NodeExists(5));
+  EXPECT_TRUE(forest.NodeExists(13));
+
+  // The parent node 19 doesn't exist, so this should fail:
+  EXPECT_FALSE(forest.AddNonRootNode(7, 19, false));
+  // This should succed, creating node 7:
+  EXPECT_TRUE(forest.AddNonRootNode(7, 13, false));
+  // Now node 7 already exists, so this should fail:
+  EXPECT_FALSE(forest.AddNonRootNode(7, 1, false));
+  // Node 13 already has a child (7), so this should fail:
+  EXPECT_FALSE(forest.AddNonRootNode(17, 13, false));
+
+  ASSERT_TRUE(forest.ValidateInvariantsForTests());
+}
+
+TEST(SpdyPriorityForestTest, SetParent) {
+  SpdyPriorityForest<uint32,int16> forest;
+  forest.AddRootNode(1, 1000);
+  forest.AddNonRootNode(2, 1, false);
+  forest.AddNonRootNode(3, 2, false);
+  forest.AddNonRootNode(5, 3, false);
+  forest.AddNonRootNode(7, 5, false);
+  forest.AddNonRootNode(9, 7, false);
+  forest.AddRootNode(11, 2000);
+  forest.AddNonRootNode(13, 11, false);
+  // We can't set the parent of a nonexistent node, or set the parent of an
+  // existing node to a nonexistent node.
+  EXPECT_FALSE(forest.SetParent(99, 13, false));
+  EXPECT_FALSE(forest.SetParent(5, 99, false));
+  // We can't make a node a child a node that already has a child:
+  EXPECT_FALSE(forest.SetParent(13, 7, false));
+  EXPECT_FALSE(forest.SetParent(3, 11, false));
+  // These would create cycles:
+  EXPECT_FALSE(forest.SetParent(11, 13, false));
+  EXPECT_FALSE(forest.SetParent(1, 9, false));
+  EXPECT_FALSE(forest.SetParent(3, 9, false));
+  // But this change is legit:
+  EXPECT_EQ(7u, forest.GetChild(5));
+  EXPECT_TRUE(forest.SetParent(7, 13, false));
+  EXPECT_EQ(0u, forest.GetChild(5));
+  EXPECT_EQ(13u, forest.GetParent(7));
+  EXPECT_EQ(7u, forest.GetChild(13));
+  // So is this change (now that 9 is no longer a descendant of 1):
+  EXPECT_TRUE(forest.SetParent(1, 9, false));
+  EXPECT_EQ(9u, forest.GetParent(1));
+  EXPECT_EQ(1u, forest.GetChild(9));
+  // We must allow setting the parent of a node to its same parent (even though
+  // that parent of course has a child already), so that we can change
+  // orderedness.
+  EXPECT_EQ(1u, forest.GetParent(2));
+  EXPECT_EQ(2u, forest.GetChild(1));
+  EXPECT_FALSE(forest.IsNodeUnordered(2));
+  EXPECT_TRUE(forest.SetParent(2, 1, true));
+  EXPECT_EQ(1u, forest.GetParent(2));
+  EXPECT_EQ(2u, forest.GetChild(1));
+  EXPECT_TRUE(forest.IsNodeUnordered(2));
+
+  ASSERT_TRUE(forest.ValidateInvariantsForTests());
+}
+
+TEST(SpdyPriorityForestTest, RemoveNodesFromMiddleOfChain) {
+  SpdyPriorityForest<uint32,int16> forest;
+  forest.AddRootNode(1, 1000);
+  forest.AddNonRootNode(2, 1, false);
+  forest.AddNonRootNode(3, 2, true);
+  forest.AddNonRootNode(5, 3, false);
+  forest.AddNonRootNode(7, 5, true);
+  forest.AddNonRootNode(9, 7, true);
+
+  // Remove a node from the middle, with unordered links on both sides.  The
+  // new merged link should also be unordered.
+  EXPECT_TRUE(forest.NodeExists(7));
+  EXPECT_EQ(7u, forest.GetChild(5));
+  EXPECT_EQ(7u, forest.GetParent(9));
+  EXPECT_TRUE(forest.IsNodeUnordered(9));
+  EXPECT_TRUE(forest.RemoveNode(7));
+  EXPECT_FALSE(forest.NodeExists(7));
+  EXPECT_EQ(9u, forest.GetChild(5));
+  EXPECT_EQ(5u, forest.GetParent(9));
+  EXPECT_TRUE(forest.IsNodeUnordered(9));
+
+  // Remove another node from the middle, with an unordered link on only one
+  // side.  The new merged link should be ordered.
+  EXPECT_TRUE(forest.NodeExists(2));
+  EXPECT_EQ(2u, forest.GetChild(1));
+  EXPECT_EQ(2u, forest.GetParent(3));
+  EXPECT_FALSE(forest.IsNodeUnordered(2));
+  EXPECT_TRUE(forest.IsNodeUnordered(3));
+  EXPECT_TRUE(forest.RemoveNode(2));
+  EXPECT_FALSE(forest.NodeExists(2));
+  EXPECT_EQ(3u, forest.GetChild(1));
+  EXPECT_EQ(1u, forest.GetParent(3));
+  EXPECT_FALSE(forest.IsNodeUnordered(3));
+
+  // Try removing the root.
+  EXPECT_TRUE(forest.NodeExists(1));
+  EXPECT_EQ(0u, forest.GetParent(1));
+  EXPECT_EQ(1000, forest.GetPriority(1));
+  EXPECT_EQ(1u, forest.GetParent(3));
+  EXPECT_EQ(0, forest.GetPriority(3));
+  EXPECT_TRUE(forest.RemoveNode(1));
+  EXPECT_FALSE(forest.NodeExists(1));
+  EXPECT_EQ(0u, forest.GetParent(3));
+  EXPECT_EQ(1000, forest.GetPriority(3));
+
+  // Now try removing the tail.
+  EXPECT_TRUE(forest.NodeExists(9));
+  EXPECT_EQ(9u, forest.GetChild(5));
+  EXPECT_TRUE(forest.RemoveNode(9));
+  EXPECT_FALSE(forest.NodeExists(9));
+  EXPECT_EQ(0u, forest.GetChild(5));
+
+  ASSERT_TRUE(forest.ValidateInvariantsForTests());
+}
+
+TEST(SpdyPriorityForestTest, MergeOrderedAndUnorderedLinks1) {
+  SpdyPriorityForest<uint32,int16> forest;
+  forest.AddRootNode(1, 1000);
+  forest.AddNonRootNode(2, 1, true);
+  forest.AddNonRootNode(3, 2, false);
+
+  EXPECT_EQ(2u, forest.GetChild(1));
+  EXPECT_EQ(3u, forest.GetChild(2));
+  EXPECT_EQ(1u, forest.GetParent(2));
+  EXPECT_EQ(2u, forest.GetParent(3));
+  EXPECT_TRUE(forest.IsNodeUnordered(2));
+  EXPECT_FALSE(forest.IsNodeUnordered(3));
+  EXPECT_TRUE(forest.RemoveNode(2));
+  EXPECT_FALSE(forest.NodeExists(2));
+  EXPECT_EQ(3u, forest.GetChild(1));
+  EXPECT_EQ(1u, forest.GetParent(3));
+  EXPECT_FALSE(forest.IsNodeUnordered(3));
+
+  ASSERT_TRUE(forest.ValidateInvariantsForTests());
+}
+
+TEST(SpdyPriorityForestTest, MergeOrderedAndUnorderedLinks2) {
+  SpdyPriorityForest<uint32,int16> forest;
+  forest.AddRootNode(1, 1000);
+  forest.AddNonRootNode(2, 1, false);
+  forest.AddNonRootNode(3, 2, true);
+
+  EXPECT_EQ(2u, forest.GetChild(1));
+  EXPECT_EQ(3u, forest.GetChild(2));
+  EXPECT_EQ(1u, forest.GetParent(2));
+  EXPECT_EQ(2u, forest.GetParent(3));
+  EXPECT_FALSE(forest.IsNodeUnordered(2));
+  EXPECT_TRUE(forest.IsNodeUnordered(3));
+  EXPECT_TRUE(forest.RemoveNode(2));
+  EXPECT_FALSE(forest.NodeExists(2));
+  EXPECT_EQ(3u, forest.GetChild(1));
+  EXPECT_EQ(1u, forest.GetParent(3));
+  EXPECT_FALSE(forest.IsNodeUnordered(3));
+
+  ASSERT_TRUE(forest.ValidateInvariantsForTests());
+}
+
+TEST(SpdyPriorityForestTest, WeightedSelectionOfForests) {
+  SpdyPriorityForest<uint32,int16> forest;
+  forest.AddRootNode(1, 10);
+  forest.AddRootNode(3, 20);
+  forest.AddRootNode(5, 70);
+  EXPECT_EQ(70, forest.GetPriority(5));
+  EXPECT_TRUE(forest.SetPriority(5, 40));
+  EXPECT_FALSE(forest.SetPriority(7, 80));
+  EXPECT_EQ(40, forest.GetPriority(5));
+  forest.AddNonRootNode(7, 3, false);
+  EXPECT_FALSE(forest.IsMarkedReadyToRead(1));
+  EXPECT_TRUE(forest.MarkReadyToRead(1));
+  EXPECT_TRUE(forest.IsMarkedReadyToRead(1));
+  EXPECT_TRUE(forest.MarkReadyToRead(5));
+  EXPECT_TRUE(forest.MarkReadyToRead(7));
+  EXPECT_FALSE(forest.MarkReadyToRead(99));
+
+  int counts[8] = {0};
+  for (int i = 0; i < 7000; ++i) {
+    const uint32 node_id = forest.NextNodeToRead();
+    ASSERT_TRUE(node_id == 1 || node_id == 5 || node_id == 7)
+        << "node_id is " << node_id;
+    ++counts[node_id];
+  }
+
+  // In theory, these could fail even if the weighted random selection is
+  // implemented correctly, but it's very unlikely.
+  EXPECT_GE(counts[1],  800); EXPECT_LE(counts[1], 1200);
+  EXPECT_GE(counts[7], 1600); EXPECT_LE(counts[7], 2400);
+  EXPECT_GE(counts[5], 3200); EXPECT_LE(counts[5], 4800);
+
+  // If we unmark all but one node, then we know for sure that that node will
+  // be selected next.
+  EXPECT_TRUE(forest.MarkNoLongerReadyToRead(1));
+  EXPECT_TRUE(forest.MarkNoLongerReadyToRead(7));
+  EXPECT_FALSE(forest.MarkNoLongerReadyToRead(99));
+  EXPECT_EQ(5u, forest.NextNodeToRead());
+
+  ASSERT_TRUE(forest.ValidateInvariantsForTests());
+}
+
+TEST(SpdyPriorityForestTest, SelectionBetweenUnorderedNodes) {
+  SpdyPriorityForest<uint32,int16> forest;
+  forest.AddRootNode(1, 1000);
+  forest.AddNonRootNode(2, 1, false);
+  forest.AddNonRootNode(3, 2, true);
+  forest.AddNonRootNode(4, 3, true);
+  forest.AddNonRootNode(5, 4, true);
+  forest.AddNonRootNode(6, 5, true);
+  forest.AddNonRootNode(7, 6, false);
+  EXPECT_FALSE(forest.IsMarkedReadyToWrite(2));
+  EXPECT_TRUE(forest.MarkReadyToWrite(2));
+  EXPECT_TRUE(forest.IsMarkedReadyToWrite(2));
+  EXPECT_TRUE(forest.MarkReadyToWrite(4));
+  EXPECT_TRUE(forest.MarkReadyToWrite(6));
+  EXPECT_TRUE(forest.MarkReadyToWrite(7));
+  EXPECT_FALSE(forest.MarkReadyToWrite(99));
+
+  int counts[8] = {0};
+  for (int i = 0; i < 6000; ++i) {
+    const uint32 node_id = forest.NextNodeToWrite();
+    ASSERT_TRUE(node_id == 2 || node_id == 4 || node_id == 6)
+        << "node_id is " << node_id;
+    ++counts[node_id];
+  }
+
+  // In theory, these could fail even if the random selection is implemented
+  // correctly, but it's very unlikely.
+  EXPECT_GE(counts[2], 1600); EXPECT_LE(counts[2], 2400);
+  EXPECT_GE(counts[4], 1600); EXPECT_LE(counts[4], 2400);
+  EXPECT_GE(counts[6], 1600); EXPECT_LE(counts[6], 2400);
+
+  // Once we unmark that group of nodes, the next node up should be node 7,
+  // which has an ordered dependency on said group.
+  EXPECT_TRUE(forest.MarkNoLongerReadyToWrite(2));
+  EXPECT_TRUE(forest.MarkNoLongerReadyToWrite(4));
+  EXPECT_TRUE(forest.MarkNoLongerReadyToWrite(6));
+  EXPECT_FALSE(forest.MarkNoLongerReadyToWrite(99));
+  EXPECT_EQ(7u, forest.NextNodeToWrite());
+
+  ASSERT_TRUE(forest.ValidateInvariantsForTests());
+}
+
+}  // namespace net