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)#ifndef NET_SPDY_SPDY_PRIORITY_FOREST_H_ 6c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#define NET_SPDY_SPDY_PRIORITY_FOREST_H_ 7c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 8c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include <map> 9c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include <set> 105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include <vector> 11c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 12c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "base/basictypes.h" 137d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)#include "base/containers/hash_tables.h" 14c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "base/logging.h" 15c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "base/memory/scoped_ptr.h" 16c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "base/rand_util.h" 17c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 18c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)namespace net { 19c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 20c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// This data structure implements the SPDY prioriziation data structures 21c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// defined in this document: http://go/spdy4-prioritization 22c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// 23c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Nodes can be added and removed, and dependencies between them defined. Each 24c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// node can have at most one parent and at most one child (forming a list), but 25c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// there can be multiple lists, with each list root having its own priority. 26c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Individual nodes can also be marked as ready to read/write, and then the 27c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// whole structure can be queried to pick the next node to read/write out of 28c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// those ready. 29c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// 30c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// The NodeId and Priority types must be POD that support comparison (most 31c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// likely, they will be numbers). 32c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 33c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)class SpdyPriorityForest { 34c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) public: 35c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) SpdyPriorityForest(); 36c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ~SpdyPriorityForest(); 37c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 38c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Return the number of nodes currently in the forest. 39c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) int num_nodes() const; 40c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 41c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Return true if the forest contains a node with the given ID. 42c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) bool NodeExists(NodeId node_id) const; 43c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 44c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Add a new root node to the forest, with the given priority. Returns true 45c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // on success, or false if the node_id already exists within the forest. 46c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) bool AddRootNode(NodeId node_id, Priority priority); 47c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 48c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Add a new node to the forest, with the given parent. Returns true on 49c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // success. Returns false and has no effect if the new node already exists, 50c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // or if the parent doesn't exist, or if the parent already has a child. 51c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) bool AddNonRootNode(NodeId node_id, NodeId parent_id, bool unordered); 52c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 53c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Remove an existing node from the forest. Returns true on success, or 54c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // false if the node doesn't exist. 55c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) bool RemoveNode(NodeId node_id); 56c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 57c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Get the priority of the given node. If the node doesn't exist, or is not 58c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // a root node (and thus has no priority), returns Priority(). 59c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Priority GetPriority(NodeId node_id) const; 60c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 61c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Get the parent of the given node. If the node doesn't exist, or is a root 62c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // node (and thus has no parent), returns NodeId(). 63c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId GetParent(NodeId node_id) const; 64c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 65c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Determine if the given node is unordered with respect to its parent. If 66c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // the node doesn't exist, or is a root node (and thus has no parent), 67c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // returns false. 68c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) bool IsNodeUnordered(NodeId node_id) const; 69c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 70c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Get the child of the given node. If the node doesn't exist, or has no 71c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // child, returns NodeId(). 72c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId GetChild(NodeId node_id) const; 73c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 74c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Set the priority of the given node. If the node was not already a root 75c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // node, this makes it a root node. Returns true on success, or false if the 76c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // node doesn't exist. 77c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) bool SetPriority(NodeId node_id, Priority priority); 78c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 79c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Set the parent of the given node. If the node was a root node, this makes 80c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // it no longer a root. Returns true on success. Returns false and has no 81c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // effect if (1) the node and/or the parent doesn't exist, (2) the new parent 82c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // already has a different child than the node, or (3) if the new parent is a 83c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // descendant of the node (so this would have created a cycle). 84c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) bool SetParent(NodeId node_id, NodeId parent_id, bool unordered); 85c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 86c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Check if a node is marked as ready to read. Returns false if the node 87c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // doesn't exist. 88c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) bool IsMarkedReadyToRead(NodeId node_id) const; 89c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Mark the node as ready or not ready to read. Returns true on success, or 90c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // false if the node doesn't exist. 91c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) bool MarkReadyToRead(NodeId node_id); 92c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) bool MarkNoLongerReadyToRead(NodeId node_id); 93c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Return the ID of the next node that we should read, or return NodeId() if 94c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // no node in the forest is ready to read. 95c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId NextNodeToRead(); 96c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 97c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Check if a node is marked as ready to write. Returns false if the node 98c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // doesn't exist. 99c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) bool IsMarkedReadyToWrite(NodeId node_id) const; 100c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Mark the node as ready or not ready to write. Returns true on success, or 101c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // false if the node doesn't exist. 102c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) bool MarkReadyToWrite(NodeId node_id); 103c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) bool MarkNoLongerReadyToWrite(NodeId node_id); 104c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Return the ID of the next node that we should write, or return NodeId() if 105c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // no node in the forest is ready to write. 106c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId NextNodeToWrite(); 107c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 108c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Return true if all internal invariants hold (useful for unit tests). 109c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Unless there are bugs, this should always return true. 110c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) bool ValidateInvariantsForTests() const; 111c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 112c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) private: 113c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) enum NodeType { ROOT_NODE, NONROOT_ORDERED, NONROOT_UNORDERED }; 114c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) struct Node { 115c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Node() : type(ROOT_NODE), flags(0), child() { 116c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) depends_on.priority = Priority(); 117c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 118c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeType type; 119c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) unsigned int flags; // bitfield of flags 120c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) union { 121c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Priority priority; // used for root nodes 122c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId parent_id; // used for non-root nodes 123c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } depends_on; 124c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId child; // node ID of child (or NodeId() for no child) 125c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) }; 126c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 127c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) typedef base::hash_map<NodeId, Node> NodeMap; 128c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 129c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Constants for the Node.flags bitset: 130c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // kReadToRead: set for nodes that are ready for reading 131c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) static const unsigned int kReadyToRead = (1 << 0); 132c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // kReadToWrite: set for nodes that are ready for writing 133c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) static const unsigned int kReadyToWrite = (1 << 1); 134c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 135c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Common code for IsMarkedReadyToRead and IsMarkedReadyToWrite. 136c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) bool IsMarked(NodeId node_id, unsigned int flag) const; 137c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Common code for MarkReadyToRead and MarkReadyToWrite. 138c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) bool Mark(NodeId node_id, unsigned int flag); 139c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Common code for MarkNoLongerReadyToRead and MarkNoLongerReadyToWrite. 140c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) bool Unmark(NodeId node_id, unsigned int flag); 141c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Common code for NextNodeToRead and NextNodeToWrite; 142c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId FirstMarkedNode(unsigned int flag); 143c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Get the given node, or return NULL if it doesn't exist. 144c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const Node* FindNode(NodeId node_id) const; 145c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 146c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeMap all_nodes_; // maps from node IDs to Node objects 147c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 148c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DISALLOW_COPY_AND_ASSIGN(SpdyPriorityForest); 149c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)}; 150c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 151c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 152c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)SpdyPriorityForest<NodeId, Priority>::SpdyPriorityForest() {} 153c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 154c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 155c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)SpdyPriorityForest<NodeId, Priority>::~SpdyPriorityForest() {} 156c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 157c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 158c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)int SpdyPriorityForest<NodeId, Priority>::num_nodes() const { 159c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return all_nodes_.size(); 160c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 161c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 162c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 163c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool SpdyPriorityForest<NodeId, Priority>::NodeExists(NodeId node_id) const { 164c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return all_nodes_.count(node_id) != 0; 165c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 166c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 167c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 168c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool SpdyPriorityForest<NodeId, Priority>::AddRootNode( 169c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId node_id, Priority priority) { 170c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (NodeExists(node_id)) { 171c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return false; 172c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 173c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Node* new_node = &all_nodes_[node_id]; 174c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) new_node->type = ROOT_NODE; 175c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) new_node->depends_on.priority = priority; 176c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return true; 177c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 178c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 179c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 180c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool SpdyPriorityForest<NodeId, Priority>::AddNonRootNode( 181c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId node_id, NodeId parent_id, bool unordered) { 182c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (NodeExists(node_id) || !NodeExists(parent_id)) { 183c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return false; 184c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 185c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 186c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Node* parent = &all_nodes_[parent_id]; 187c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (parent->child != NodeId()) { 188c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return false; 189c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 190c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 191c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Node* new_node = &all_nodes_[node_id]; 192c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) new_node->type = (unordered ? NONROOT_UNORDERED : NONROOT_ORDERED); 193c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) new_node->depends_on.parent_id = parent_id; 194c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) parent->child = node_id; 195c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return true; 196c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 197c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 198c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 199c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool SpdyPriorityForest<NodeId, Priority>::RemoveNode(NodeId node_id) { 200c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (!NodeExists(node_id)) { 201c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return false; 202c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 203c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const Node& node = all_nodes_[node_id]; 204c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 205c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // If the node to be removed is not a root node, we need to change its 206c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // parent's child ID. 207c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (node.type != ROOT_NODE) { 208c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK(NodeExists(node.depends_on.parent_id)); 209c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Node* parent = &all_nodes_[node.depends_on.parent_id]; 210c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK_EQ(node_id, parent->child); 211c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) parent->child = node.child; 212c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 213c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 214c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // If the node has a child, we need to change the child's priority or parent. 215c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (node.child != NodeId()) { 216c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK(NodeExists(node.child)); 217c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Node* child = &all_nodes_[node.child]; 218c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK_NE(ROOT_NODE, child->type); 219c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK_EQ(node_id, child->depends_on.parent_id); 220c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Make the child's new depends_on be the node's depends_on (whether that 221c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // be a priority or a parent node ID). 222c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) child->depends_on = node.depends_on; 223c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // If the removed node was a root, its child is now a root. Otherwise, the 224c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // child will be be unordered if and only if it was already unordered and 225c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // the removed not is also not ordered. 226c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (node.type == ROOT_NODE) { 227c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) child->type = ROOT_NODE; 228c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } else if (node.type == NONROOT_ORDERED) { 229c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) child->type = NONROOT_ORDERED; 230c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 231c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 232c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 233c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Delete the node. 234c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) all_nodes_.erase(node_id); 235c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return true; 236c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 237c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 238c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 239c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)Priority SpdyPriorityForest<NodeId, Priority>::GetPriority( 240c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId node_id) const { 241c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const Node* node = FindNode(node_id); 242c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (node != NULL && node->type == ROOT_NODE) { 243c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return node->depends_on.priority; 244c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } else { 245c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return Priority(); 246c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 247c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 248c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 249c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 250c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)NodeId SpdyPriorityForest<NodeId, Priority>::GetParent(NodeId node_id) const { 251c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const Node* node = FindNode(node_id); 252c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (node != NULL && node->type != ROOT_NODE) { 253c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return node->depends_on.parent_id; 254c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } else { 255c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return NodeId(); 256c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 257c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 258c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 259c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 260c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool SpdyPriorityForest<NodeId, Priority>::IsNodeUnordered( 261c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId node_id) const { 262c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const Node* node = FindNode(node_id); 263c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return node != NULL && node->type == NONROOT_UNORDERED; 264c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 265c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 266c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 267c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)NodeId SpdyPriorityForest<NodeId, Priority>::GetChild(NodeId node_id) const { 268c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const Node* node = FindNode(node_id); 269c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (node != NULL) { 270c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return node->child; 271c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } else { 272c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return NodeId(); 273c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 274c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 275c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 276c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 277c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool SpdyPriorityForest<NodeId, Priority>::SetPriority( 278c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId node_id, Priority priority) { 279c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (!NodeExists(node_id)) { 280c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return false; 281c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 282c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 283c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Node* node = &all_nodes_[node_id]; 284c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // If this is not already a root node, we need to make it be a root node. 285c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (node->type != ROOT_NODE) { 286c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK(NodeExists(node->depends_on.parent_id)); 287c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Node* parent = &all_nodes_[node->depends_on.parent_id]; 288c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) parent->child = NodeId(); 289c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) node->type = ROOT_NODE; 290c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 291c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 292c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) node->depends_on.priority = priority; 293c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return true; 294c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 295c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 296c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 297c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool SpdyPriorityForest<NodeId, Priority>::SetParent( 298c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId node_id, NodeId parent_id, bool unordered) { 299c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (!NodeExists(node_id) || !NodeExists(parent_id)) { 300c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return false; 301c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 302c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 303c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Node* node = &all_nodes_[node_id]; 304c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Node* new_parent = &all_nodes_[parent_id]; 305c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // If the new parent is already the node's parent, all we have to do is 306c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // update the node type and we're done. 307c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (new_parent->child == node_id) { 308c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) node->type = (unordered ? NONROOT_UNORDERED : NONROOT_ORDERED); 309c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return true; 310c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 311c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Otherwise, if the new parent already has a child, we fail. 312c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (new_parent->child != NodeId()) { 313c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return false; 314c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 315c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 316c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Next, make sure we won't create a cycle. 317c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (node_id == parent_id) return false; 318c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Node* last = node; 319c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId last_id = node_id; 320c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) while (last->child != NodeId()) { 321c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (last->child == parent_id) return false; 322c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) last_id = last->child; 323c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK(NodeExists(last_id)); 324c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) last = &all_nodes_[last_id]; 325c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 326c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 327c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // If the node is not a root, we need clear its old parent's child field 328c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // (unless the old parent is the same as the new parent). 329c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (node->type != ROOT_NODE) { 330c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const NodeId old_parent_id = node->depends_on.parent_id; 331c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK(NodeExists(old_parent_id)); 332c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK(old_parent_id != parent_id); 333c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Node* old_parent = &all_nodes_[old_parent_id]; 334c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK_EQ(node_id, old_parent->child); 335c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) old_parent->child = NodeId(); 336c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 337c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 338c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Make the change. 339c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) node->type = (unordered ? NONROOT_UNORDERED : NONROOT_ORDERED); 340c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) node->depends_on.parent_id = parent_id; 341c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) new_parent->child = node_id; 342c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return true; 343c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 344c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 345c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 346c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool SpdyPriorityForest<NodeId, Priority>::IsMarkedReadyToRead( 347c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId node_id) const { 348c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return IsMarked(node_id, kReadyToRead); 349c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 350c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 351c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 352c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool SpdyPriorityForest<NodeId, Priority>::MarkReadyToRead(NodeId node_id) { 353c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return Mark(node_id, kReadyToRead); 354c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 355c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 356c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 357c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool SpdyPriorityForest<NodeId, Priority>::MarkNoLongerReadyToRead( 358c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId node_id) { 359c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return Unmark(node_id, kReadyToRead); 360c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 361c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 362c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 363c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)NodeId SpdyPriorityForest<NodeId, Priority>::NextNodeToRead() { 364c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return FirstMarkedNode(kReadyToRead); 365c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 366c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 367c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 368c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool SpdyPriorityForest<NodeId, Priority>::IsMarkedReadyToWrite( 369c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId node_id) const { 370c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return IsMarked(node_id, kReadyToWrite); 371c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 372c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 373c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 374c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool SpdyPriorityForest<NodeId, Priority>::MarkReadyToWrite(NodeId node_id) { 375c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return Mark(node_id, kReadyToWrite); 376c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 377c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 378c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 379c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool SpdyPriorityForest<NodeId, Priority>::MarkNoLongerReadyToWrite( 380c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId node_id) { 381c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return Unmark(node_id, kReadyToWrite); 382c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 383c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 384c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 385c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)NodeId SpdyPriorityForest<NodeId, Priority>::NextNodeToWrite() { 386c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return FirstMarkedNode(kReadyToWrite); 387c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 388c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 389c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 390c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool SpdyPriorityForest<NodeId, Priority>::IsMarked( 391c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId node_id, unsigned int flag) const { 392c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const Node* node = FindNode(node_id); 393c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return node != NULL && (node->flags & flag) != 0; 394c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 395c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 396c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 397c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool SpdyPriorityForest<NodeId, Priority>::Mark( 398c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId node_id, unsigned int flag) { 399c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (!NodeExists(node_id)) { 400c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return false; 401c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 402c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) all_nodes_[node_id].flags |= flag; 403c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return true; 404c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 405c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 406c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 407c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool SpdyPriorityForest<NodeId, Priority>::Unmark( 408c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId node_id, unsigned int flag) { 409c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (!NodeExists(node_id)) { 410c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return false; 411c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 412c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) all_nodes_[node_id].flags &= ~flag; 413c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return true; 414c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 415c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 416c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 417c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)NodeId SpdyPriorityForest<NodeId, Priority>::FirstMarkedNode( 418c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) unsigned int flag) { 419c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // TODO(mdsteele): This is an *incredibly* stupid brute force solution. 420c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 421c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Get all root nodes that have at least one marked child. 422c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) uint64 total_weight = 0; 423c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) std::map<uint64, NodeId> roots; // maps cumulative weight to root node ID 424c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) for (typename NodeMap::const_iterator iter = all_nodes_.begin(); 425c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) iter != all_nodes_.end(); ++iter) { 426c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const NodeId root_id = iter->first; 427c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const Node& root = iter->second; 428c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (root.type == ROOT_NODE) { 429c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // See if there is at least one marked node in this root's chain. 430c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) for (const Node* node = &root; ; node = &all_nodes_[node->child]) { 431c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if ((node->flags & flag) != 0) { 432c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) total_weight += static_cast<uint64>(root.depends_on.priority); 433c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) roots[total_weight] = root_id; 434c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) break; 435c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 436c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (node->child == NodeId()) { 437c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) break; 438c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 439c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK(NodeExists(node->child)); 440c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 441c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 442c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 443c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 444c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // If there are no ready nodes, then return NodeId(). 445c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (total_weight == 0) { 446c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK(roots.empty()); 447c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return NodeId(); 448c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } else { 449c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK(!roots.empty()); 450c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 451c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 452c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Randomly select a tree to use. 453c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) typename std::map<uint64, NodeId>::const_iterator root_iter = 454c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) roots.upper_bound(base::RandGenerator(total_weight)); 455c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK(root_iter != roots.end()); 456c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const NodeId root_id = root_iter->second; 457c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 458c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Find the first node in the chain that is ready. 459c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId node_id = root_id; 460c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) while (true) { 461c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK(NodeExists(node_id)); 462c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Node* node = &all_nodes_[node_id]; 463c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if ((node->flags & flag) != 0) { 464c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // There might be more nodes that are ready and that are linked to this 465c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // one in an unordered chain. Find all of them, then pick one randomly. 466c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) std::vector<NodeId> group; 467c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) group.push_back(node_id); 468c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) for (Node* next = node; next->child != NodeId();) { 469c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK(NodeExists(next->child)); 470c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Node *child = &all_nodes_[next->child]; 471c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK_NE(ROOT_NODE, child->type); 472c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (child->type != NONROOT_UNORDERED) { 473c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) break; 474c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 475c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if ((child->flags & flag) != 0) { 476c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) group.push_back(next->child); 477c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 478c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) next = child; 479c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 480c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return group[base::RandGenerator(group.size())]; 481c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 482c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) node_id = node->child; 483c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 484c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 485c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 486c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 487c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)const typename SpdyPriorityForest<NodeId, Priority>::Node* 488c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)SpdyPriorityForest<NodeId, Priority>::FindNode(NodeId node_id) const { 489c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) typename NodeMap::const_iterator iter = all_nodes_.find(node_id); 490c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (iter == all_nodes_.end()) { 491c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return NULL; 492c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 493c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return &iter->second; 494c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 495c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 496c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <typename NodeId, typename Priority> 497c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool SpdyPriorityForest<NodeId, Priority>::ValidateInvariantsForTests() const { 498c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) for (typename NodeMap::const_iterator iter = all_nodes_.begin(); 499c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) iter != all_nodes_.end(); ++iter) { 500c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const NodeId node_id = iter->first; 501c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const Node& node = iter->second; 502c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (node.type != ROOT_NODE && 503c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) (!NodeExists(node.depends_on.parent_id) || 504c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) GetChild(node.depends_on.parent_id) != node_id)) { 505c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return false; 506c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 507c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (node.child != NodeId()) { 508c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (!NodeExists(node.child) || node_id != GetParent(node.child)) { 509c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return false; 510c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 511c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 512c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 513c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NodeId child_id = node.child; 514c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) int count = 0; 515c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) while (child_id != NodeId()) { 516c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (count > num_nodes() || node_id == child_id) { 517c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return false; 518c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 519c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) child_id = GetChild(child_id); 520c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ++count; 521c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 522c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 523c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return true; 524c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 525c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 526c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} // namespace net 527c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 528c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#endif // NET_SPDY_SPDY_PRIORITY_FOREST_H_ 529