1116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// Copyright 2014 The Chromium Authors. All rights reserved. 2116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// Use of this source code is governed by a BSD-style license that can be 3116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// found in the LICENSE file. 4116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 5116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#ifndef NET_SPDY_SPDY_PRIORITY_TREE_H_ 6116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#define NET_SPDY_SPDY_PRIORITY_TREE_H_ 7116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 8116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include <cmath> 9116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include <list> 10116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include <map> 11116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include <queue> 12116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include <set> 13116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 14116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "base/basictypes.h" 15116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "base/containers/hash_tables.h" 16116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "base/logging.h" 17116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "base/memory/scoped_ptr.h" 18116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 19116680a4aac90f2aa7413d9095a592090648e557Ben Murdochnamespace net { 20116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 21116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// This data structure implements the HTTP2 prioritization data structure 22116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// defined in draft standard: 23116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// http://tools.ietf.org/html/draft-ietf-httpbis-http2-13 24116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// 25116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// Nodes can be added and removed, and dependencies between them defined. Each 26116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// node can have at most one parent and at most one child (forming a list), but 27116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// there can be multiple lists, with each list root having its own priority. 28116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// Individual nodes can also be marked as ready to read/write, and then the 29116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// whole structure can be queried to pick the next node to read/write out of 30116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// those ready. 31116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// 32116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// The NodeId type must be a POD that supports comparison (most 33116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// likely, it will be a number). 34116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 35116680a4aac90f2aa7413d9095a592090648e557Ben Murdochnamespace test { 36116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 37116680a4aac90f2aa7413d9095a592090648e557Ben Murdochclass SpdyPriorityTreePeer; 38116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 39116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 40116680a4aac90f2aa7413d9095a592090648e557Ben Murdochconst int kRootNodeId = 0; 41116680a4aac90f2aa7413d9095a592090648e557Ben Murdochconst int kDefaultWeight = 16; 42116680a4aac90f2aa7413d9095a592090648e557Ben Murdochconst int kMinWeight = 1; 43116680a4aac90f2aa7413d9095a592090648e557Ben Murdochconst int kMaxWeight = 256; 44116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 45116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 46116680a4aac90f2aa7413d9095a592090648e557Ben Murdochclass SpdyPriorityTree { 47116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch typedef std::vector<std::pair<NodeId, float> > PriorityNodeList; 48116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 49116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch public: 50116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch SpdyPriorityTree(); 51116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch ~SpdyPriorityTree(); 52116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 53116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch typedef std::list<NodeId> List; 54116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch struct Node { 55116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node(); 56116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch ~Node(); 57116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 58116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch NodeId id; 59116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch NodeId parent_id; 60116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch int weight; // Weights can range between 1 and 256 (inclusive). 61116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // The total weight of this node's direct descendants. 62116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch int total_child_weights; 63116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // The total weight of direct descendants that are writeable 64116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // (ready to write and not blocked). This value does not necessarily 65116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // reflect the current state of the tree; instead, we lazily update it 66116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // on calls to PropagateNodeState(node.id). 67116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch int total_writeable_child_weights; 68116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch List* child_list; // node ID's of children, if any 69116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool blocked; // Is the associated stream write-blocked? 70116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool ready; // Does the stream have data ready for writing? 71116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch float priority; // The fraction of resources to dedicate to this node. 72116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch }; 73116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 74116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Orders in descending order of priority. 75116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch struct NodePriorityComparator { 76116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool operator ()(const std::pair<NodeId, float>& lhs, 77116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const std::pair<NodeId, float>& rhs); 78116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch }; 79116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 80116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch friend class test::SpdyPriorityTreePeer<NodeId>; 81116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 82116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Return the number of nodes currently in the tree. 83116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch int num_nodes() const; 84116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 85116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Return true if the tree contains a node with the given ID. 86116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool NodeExists(NodeId node_id) const; 87116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 88116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Add a new node with the given weight and parent. Non-exclusive nodes 89116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // simply get added below the parent node. If exclusive = true, the node 90116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // becomes the parent's sole child and the parent's previous children 91116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // become the children of the new node. 92116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Returns true on success. Returns false if the node already exists 93116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // in the tree, or if the parent node does not exist. 94116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool AddNode(NodeId node_id, NodeId parent_id, int weight, bool exclusive); 95116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 96116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Remove an existing node from the tree. Returns true on success, or 97116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // false if the node doesn't exist. 98116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool RemoveNode(NodeId node_id); 99116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 100116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Get the weight of the given node. 101116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch int GetWeight(NodeId node_id) const; 102116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 103116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Get the parent of the given node. If the node doesn't exist, or is a root 104116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // node (and thus has no parent), returns NodeId(). 105116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch NodeId GetParent(NodeId node_id) const; 106116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 107116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Get the child list of the given node. If the node doesn't exist, or has no 108116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // child, returns NULL. 109116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch std::list<NodeId>* GetChildren(NodeId node_id) const; 110116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 111116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Set the priority of the given node. 112116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool SetWeight(NodeId node_id, int weight); 113116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 114116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Set the parent of the given node. Returns true on success. 115116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Returns false and has no effect if the node and/or the parent doesn't 116116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // exist. If the new parent is a descendant of the node (i.e. this would have 117116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // created a cycle) then we rearrange the topology of the tree as described 118116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // in the HTTP2 spec. 119116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool SetParent(NodeId node_id, NodeId parent_id, bool exclusive); 120116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 121116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Returns true if the node parent_id has child_id in its child_list. 122116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool HasChild(NodeId parent_id, NodeId child_id) const; 123116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 124116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Mark a node as blocked or unblocked. Return true on success, or false 125116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // if unable to mark the specified node. 126116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool SetBlocked(NodeId node_id, bool blocked); 127116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 128116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Mark whether or not a node is ready to write; i.e. whether there is 129116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // buffered data for the associated stream. Return true on success, or false 130116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // if unable to mark the specified node. 131116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool SetReady(NodeId node_id, bool ready); 132116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 133116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Return true if all internal invariants hold (useful for unit tests). 134116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Unless there are bugs, this should always return true. 135116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool ValidateInvariantsForTests() const; 136116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 137116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Get the given node, or return NULL if it doesn't exist. 138116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const Node* FindNode(NodeId node_id) const; 139116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 140116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Returns an ordered list of writeable nodes and their priorities. 141116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Priority is calculated as: 142116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // parent's priority * (node's weight / sum of sibling weights) 143116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch PriorityNodeList GetPriorityList(); 144116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 145116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch protected: 146116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Update the value of total_writeable_child_weights for the given node 147116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // to reflect the current state of the tree. 148116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch void PropagateNodeState(NodeId node); 149116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 150116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch private: 151116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch typedef base::hash_map<NodeId, Node> NodeMap; 152116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 153116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch NodeMap all_nodes_; // maps from node IDs to Node objects 154116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 155116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch DISALLOW_COPY_AND_ASSIGN(SpdyPriorityTree); 156116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch}; 157116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 158116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 159116680a4aac90f2aa7413d9095a592090648e557Ben MurdochSpdyPriorityTree<NodeId>::SpdyPriorityTree() { 160116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node* root_node = &all_nodes_[kRootNodeId]; 161116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch root_node->id = kRootNodeId; 162116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch root_node->weight = kDefaultWeight; 163116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch root_node->parent_id = static_cast<NodeId>(kRootNodeId); 164116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch root_node->child_list = new std::list<NodeId>; 165116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch root_node->priority = 1.0; 166116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch root_node->ready = true; 167116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 168116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 169116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 170116680a4aac90f2aa7413d9095a592090648e557Ben MurdochSpdyPriorityTree<NodeId>::~SpdyPriorityTree() {} 171116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 172116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 173116680a4aac90f2aa7413d9095a592090648e557Ben MurdochSpdyPriorityTree<NodeId>::Node::Node() : 174116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch parent_id(kRootNodeId), 175116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch weight(kDefaultWeight), 176116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch total_child_weights(0), 177116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch total_writeable_child_weights(0), 178116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch child_list(), 179116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch blocked(false), 180116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch ready(false), 181116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch priority(0) { 182116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 183116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 184116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 185116680a4aac90f2aa7413d9095a592090648e557Ben MurdochSpdyPriorityTree<NodeId>::Node::~Node() { 186116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch delete child_list; 187116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 188116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 189116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 190116680a4aac90f2aa7413d9095a592090648e557Ben Murdochbool SpdyPriorityTree<NodeId>::NodePriorityComparator::operator ()( 191116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const std::pair<NodeId, float>& lhs, 192116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const std::pair<NodeId, float>& rhs) { 193116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return lhs.second > rhs.second; 194116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 195116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 196116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 197116680a4aac90f2aa7413d9095a592090648e557Ben Murdochint SpdyPriorityTree<NodeId>::num_nodes() const { 198116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return all_nodes_.size(); 199116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 200116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 201116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 202116680a4aac90f2aa7413d9095a592090648e557Ben Murdochbool SpdyPriorityTree<NodeId>::NodeExists(NodeId node_id) const { 203116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return all_nodes_.count(node_id) != 0; 204116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 205116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 206116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 207116680a4aac90f2aa7413d9095a592090648e557Ben Murdochbool SpdyPriorityTree<NodeId>::AddNode(NodeId node_id, 208116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch NodeId parent_id, 209116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch int weight, 210116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool exclusive) { 211116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (NodeExists(node_id) || !NodeExists(parent_id)) { 212116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return false; 213116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 214116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (weight < kMinWeight || weight > kMaxWeight) { 215116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return false; 216116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 217116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node* parent = &all_nodes_[parent_id]; 218116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node* new_node = &all_nodes_[node_id]; 219116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch new_node->id = node_id; 220116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch new_node->weight = weight; 221116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch new_node->parent_id = parent_id; 222116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (exclusive) { 223116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Move the parent's current children below the new node. 224116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch new_node->child_list = parent->child_list; 225116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch new_node->total_child_weights = parent->total_child_weights; 226116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Update each child's parent_id. 227116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (typename List::iterator it = new_node->child_list->begin(); 228116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch it != new_node->child_list->end(); ++it) { 229116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node* child = &all_nodes_[*it]; 230116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch child->parent_id = node_id; 231116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 232116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Clear parent's old child data. 233116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch parent->child_list = new std::list<NodeId>; 234116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch parent->total_child_weights = 0; 235116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } else { 236116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch new_node->child_list = new std::list<NodeId>; 237116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 238116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Add new node to parent. 239116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch parent->child_list->push_back(node_id); 240116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch parent->total_child_weights += weight; 241116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return true; 242116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 243116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 244116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 245116680a4aac90f2aa7413d9095a592090648e557Ben Murdochbool SpdyPriorityTree<NodeId>::RemoveNode(NodeId node_id) { 246116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (node_id == static_cast<NodeId>(kRootNodeId) || !NodeExists(node_id)) { 247116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return false; 248116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 249116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const Node& node = all_nodes_[node_id]; 250116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 251116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch DCHECK(NodeExists(node.parent_id)); 252116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node* parent = &all_nodes_[node.parent_id]; 253116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Remove the node id from parent's child list. 254116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch parent->child_list->remove(node_id); 255116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch parent->total_child_weights -= node.weight; 256116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 257116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Move the node's children to the parent's child list. 258116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (node.child_list != NULL) { 259116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Update each child's parent_id and weight. 260116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (typename List::iterator it = node.child_list->begin(); 261116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch it != node.child_list->end(); ++it) { 262116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node* child = &all_nodes_[*it]; 263116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch child->parent_id = node.parent_id; 264116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Divide the removed node's weight among its children, rounding to the 265116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // nearest valid weight. 266116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch float float_weight = node.weight * static_cast<float>(child->weight) / 267116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch static_cast<float>(node.total_child_weights); 268116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch int new_weight = std::floor(float_weight + 0.5); 269116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (new_weight == 0) { 270116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch new_weight = 1; 271116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 272116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch child->weight = new_weight; 273116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch parent->total_child_weights += child->weight; 274116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 275116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch parent->child_list->splice(parent->child_list->end(), *node.child_list); 276116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 277116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 278116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Delete the node. 279116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch all_nodes_.erase(node_id); 280116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return true; 281116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 282116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 283116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 284116680a4aac90f2aa7413d9095a592090648e557Ben Murdochint SpdyPriorityTree<NodeId>::GetWeight(NodeId node_id) const { 285116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const Node* node = FindNode(node_id); 286116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (node != NULL) { 287116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return node->weight; 288116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 289116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return 0; 290116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 291116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 292116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 293116680a4aac90f2aa7413d9095a592090648e557Ben MurdochNodeId SpdyPriorityTree<NodeId>::GetParent(NodeId node_id) const { 294116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const Node* node = FindNode(node_id); 295116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (node != NULL && node->id != static_cast<NodeId>(kRootNodeId)) { 296116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return node->parent_id; 297116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 298116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return static_cast<NodeId>(kRootNodeId); 299116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 300116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 301116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 302116680a4aac90f2aa7413d9095a592090648e557Ben Murdochstd::list<NodeId>* SpdyPriorityTree<NodeId>::GetChildren(NodeId node_id) const { 303116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const Node* node = FindNode(node_id); 304116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (node != NULL) { 305116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return node->child_list; 306116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 307116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return NULL; 308116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 309116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 310116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 311116680a4aac90f2aa7413d9095a592090648e557Ben Murdochbool SpdyPriorityTree<NodeId>::SetWeight( 312116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch NodeId node_id, int weight) { 313116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (!NodeExists(node_id)) { 314116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return false; 315116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 316116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (weight < kMinWeight || weight > kMaxWeight) { 317116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return false; 318116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 319116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 320116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node* node = &all_nodes_[node_id]; 321116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node* parent = &all_nodes_[node->parent_id]; 322116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 323116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch parent->total_child_weights += (weight - node->weight); 324116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch node->weight = weight; 325116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 326116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return true; 327116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 328116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 329116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 330116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 331116680a4aac90f2aa7413d9095a592090648e557Ben Murdochbool SpdyPriorityTree<NodeId>::SetParent( 332116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch NodeId node_id, NodeId parent_id, bool exclusive) { 333116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (!NodeExists(node_id) || !NodeExists(parent_id)) { 334116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return false; 335116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 336116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (node_id == parent_id) return false; 337116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 338116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node* node = &all_nodes_[node_id]; 339116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node* new_parent = &all_nodes_[parent_id]; 340116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // If the new parent is already the node's parent, we're done. 341116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (node->parent_id == parent_id) { 342116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return true; 343116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 344116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 345116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Next, check to see if the new parent is currently a descendant 346116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // of the node. 347116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node* last = new_parent; 348116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch NodeId last_id = parent_id; 349116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool cycle_exists = false; 350116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch while (last->parent_id != static_cast<NodeId>(kRootNodeId)) { 351116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (last->parent_id == node_id) { 352116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch cycle_exists = true; 353116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch break; 354116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 355116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch last_id = last->parent_id; 356116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch DCHECK(NodeExists(last_id)); 357116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch last = &all_nodes_[last_id]; 358116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 359116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 360116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (cycle_exists) { 361116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // The new parent moves to the level of the current node. 362116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch SetParent(parent_id, node->parent_id, false); 363116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 364116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 365116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Remove node from old parent's child list. 366116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const NodeId old_parent_id = node->parent_id; 367116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch DCHECK(NodeExists(old_parent_id)); 368116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node* old_parent = &all_nodes_[old_parent_id]; 369116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch old_parent->child_list->remove(node_id); 370116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch old_parent->total_child_weights -= node->weight; 371116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 372116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Make the change. 373116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch node->parent_id = parent_id; 374116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch new_parent->child_list->push_back(node_id); 375116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch new_parent->total_child_weights += node->weight; 376116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return true; 377116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 378116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 379116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 380116680a4aac90f2aa7413d9095a592090648e557Ben Murdochbool SpdyPriorityTree<NodeId>::SetBlocked(NodeId node_id, bool blocked) { 381116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (!NodeExists(node_id)) { 382116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return false; 383116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 384116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 385116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node* node = &all_nodes_[node_id]; 386116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch node->blocked = blocked; 387116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return true; 388116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 389116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 390116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 391116680a4aac90f2aa7413d9095a592090648e557Ben Murdochbool SpdyPriorityTree<NodeId>::SetReady(NodeId node_id, bool ready) { 392116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (!NodeExists(node_id)) { 393116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return false; 394116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 395116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node* node = &all_nodes_[node_id]; 396116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch node->ready = ready; 397116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return true; 398116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 399116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 400116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 401116680a4aac90f2aa7413d9095a592090648e557Ben Murdochvoid SpdyPriorityTree<NodeId>::PropagateNodeState(NodeId node_id) { 402116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Reset total_writeable_child_weights to its maximum value. 403116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node* node = &all_nodes_[node_id]; 404116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch node->total_writeable_child_weights = node->total_child_weights; 405116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (typename List::iterator it = node->child_list->begin(); 406116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch it != node->child_list->end(); ++it) { 407116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch PropagateNodeState(*it); 408116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 409116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (node->total_writeable_child_weights == 0 && 410116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch (node->blocked || !node->ready)) { 411116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Tell the parent that this entire subtree is unwriteable. 412116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node* parent = &all_nodes_[node->parent_id]; 413116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch parent->total_writeable_child_weights -= node->weight; 414116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 415116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 416116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 417116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 418116680a4aac90f2aa7413d9095a592090648e557Ben Murdochconst typename SpdyPriorityTree<NodeId>::Node* 419116680a4aac90f2aa7413d9095a592090648e557Ben MurdochSpdyPriorityTree<NodeId>::FindNode(NodeId node_id) const { 420116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch typename NodeMap::const_iterator iter = all_nodes_.find(node_id); 421116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (iter == all_nodes_.end()) { 422116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return NULL; 423116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 424116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return &iter->second; 425116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 426116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 427116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 428116680a4aac90f2aa7413d9095a592090648e557Ben Murdochbool SpdyPriorityTree<NodeId>::HasChild(NodeId parent_id, 429116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch NodeId child_id) const { 430116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const Node* parent = FindNode(parent_id); 431116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return parent->child_list->end() != 432116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch std::find(parent->child_list->begin(), 433116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch parent->child_list->end(), 434116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch child_id); 435116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 436116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 437116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 438116680a4aac90f2aa7413d9095a592090648e557Ben Murdochstd::vector<std::pair<NodeId, float> > 439116680a4aac90f2aa7413d9095a592090648e557Ben MurdochSpdyPriorityTree<NodeId>::GetPriorityList() { 440116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch typedef std::pair<NodeId, float> PriorityNode; 441116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch typedef std::vector<PriorityNode> PriorityList; 442116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch PriorityList priority_list; 443116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 444116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Update total_writeable_child_weights to reflect the current 445116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // state of the tree. 446116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch PropagateNodeState(kRootNodeId); 447116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 448116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch List queue; 449116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const Node* root_node = FindNode(kRootNodeId); 450116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch DCHECK(root_node->priority == 1.0); 451116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Start by examining our top-level nodes. 452116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (typename List::iterator it = root_node->child_list->begin(); 453116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch it != root_node->child_list->end(); ++it) { 454116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch queue.push_back(*it); 455116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 456116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch while (!queue.empty()) { 457116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch NodeId current_node_id = queue.front(); 458116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node* current_node = &all_nodes_[current_node_id]; 459116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const Node* parent_node = FindNode(current_node->parent_id); 460116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (current_node->blocked || !current_node->ready) { 461116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (current_node->total_writeable_child_weights > 0) { 462116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // This node isn't writeable, but it has writeable children. 463116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Calculate the total fraction of resources we can allot 464116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // to this subtree. 465116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch current_node->priority = parent_node->priority * 466116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch (static_cast<float>(current_node->weight) / 467116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch static_cast<float>(parent_node->total_writeable_child_weights)); 468116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Examine the children. 469116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (typename List::iterator it = current_node->child_list->begin(); 470116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch it != current_node->child_list->end(); ++it) { 471116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch queue.push_back(*it); 472116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 473116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } else { 474116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // There's nothing to see in this subtree. 475116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch current_node->priority = 0; 476116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 477116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } else { 478116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // This node is writeable; calculate its priority. 479116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch current_node->priority = parent_node->priority * 480116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch (static_cast<float>(current_node->weight) / 481116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch static_cast<float>(parent_node->total_writeable_child_weights)); 482116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Add this node to the priority list. 483116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch priority_list.push_back(PriorityNode(current_node_id, 484116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch current_node->priority)); 485116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 486116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Remove this node from the queue. 487116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch queue.pop_front(); 488116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 489116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 490116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Sort the nodes in descending order of priority. 491116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch std::sort(priority_list.begin(), priority_list.end(), 492116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch NodePriorityComparator()); 493116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 494116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return priority_list; 495116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 496116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 497116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename NodeId> 498116680a4aac90f2aa7413d9095a592090648e557Ben Murdochbool SpdyPriorityTree<NodeId>::ValidateInvariantsForTests() const { 499116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch int total_nodes = 0; 500116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch int nodes_visited = 0; 501116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Iterate through all nodes in the map. 502116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (typename NodeMap::const_iterator iter = all_nodes_.begin(); 503116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch iter != all_nodes_.end(); ++iter) { 504116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch ++total_nodes; 505116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch ++nodes_visited; 506116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const Node& node = iter->second; 507116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // All nodes except the root should have a parent, and should appear in 508116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // the child_list of that parent. 509116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (node.id != static_cast<NodeId>(kRootNodeId) && 510116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch (!NodeExists(node.parent_id) || 511116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch !HasChild(node.parent_id, node.id))) { 512116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch DLOG(INFO) << "Parent node " << node.parent_id 513116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch << " does not exist, or does not list node " << node.id 514116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch << " as its child."; 515116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return false; 516116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 517116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 518116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (!node.child_list->empty()) { 519116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch int total_child_weights = 0; 520116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Iterate through the node's children. 521116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (typename List::iterator it = node.child_list->begin(); 522116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch it != node.child_list->end(); ++it) { 523116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch ++nodes_visited; 524116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Each node in the list should exist and should have this node 525116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // set as its parent. 526116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (!NodeExists(*it) || node.id != GetParent(*it)) { 527116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch DLOG(INFO) << "Child node " << *it << " does not exist, " 528116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch << "or does not list " << node.id << " as its parent."; 529116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return false; 530116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 531116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const Node* child = FindNode(*it); 532116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch total_child_weights += child->weight; 533116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 534116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Verify that total_child_weights is correct. 535116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (total_child_weights != node.total_child_weights) { 536116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch DLOG(INFO) << "Child weight totals do not agree. For node " << node.id 537116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch << " total_child_weights has value " 538116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch << node.total_child_weights 539116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch << ", expected " << total_child_weights; 540116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return false; 541116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 542116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 543116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 544116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 545116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Make sure num_nodes reflects the total number of nodes the map contains. 546116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (total_nodes != num_nodes()) { 547116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch DLOG(INFO) << "Map contains incorrect number of nodes."; 548116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return false; 549116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 550116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Validate the validation function; we should have visited each node twice 551116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // (except for the root) 552116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch DCHECK(nodes_visited == 2*num_nodes() - 1); 553116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return true; 554116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 555116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 556116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} // namespace net 557116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 558116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#endif // NET_SPDY_SPDY_PRIORITY_TREE_H_ 559