Remove //net (except for Android test stuff) and sdch

net/spdy/spdy_priority_forest.h

Index: net/spdy/spdy_priority_forest.h
diff --git a/net/spdy/spdy_priority_forest.h b/net/spdy/spdy_priority_forest.h
deleted file mode 100644
index 8624bbfe8eeac441b372bb7b2815035c5810a33a..0000000000000000000000000000000000000000
--- a/net/spdy/spdy_priority_forest.h
+++ /dev/null
@@ -1,528 +0,0 @@
-// 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 <vector>
-
-#include "base/basictypes.h"
-#include "base/containers/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_