| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright 2014 The Chromium Authors. All rights reserved. | |
| 2 // Use of this source code is governed by a BSD-style license that can be | |
| 3 // found in the LICENSE file. | |
| 4 | |
| 5 #ifndef NET_SPDY_SPDY_PRIORITY_TREE_H_ | |
| 6 #define NET_SPDY_SPDY_PRIORITY_TREE_H_ | |
| 7 | |
| 8 #include <cmath> | |
| 9 #include <list> | |
| 10 #include <map> | |
| 11 #include <queue> | |
| 12 #include <set> | |
| 13 | |
| 14 #include "base/basictypes.h" | |
| 15 #include "base/containers/hash_tables.h" | |
| 16 #include "base/logging.h" | |
| 17 #include "base/memory/scoped_ptr.h" | |
| 18 | |
| 19 namespace net { | |
| 20 | |
| 21 // This data structure implements the HTTP2 prioritization data structure | |
| 22 // defined in draft standard: | |
| 23 // http://tools.ietf.org/html/draft-ietf-httpbis-http2-13 | |
| 24 // | |
| 25 // Nodes can be added and removed, and dependencies between them defined. Each | |
| 26 // node can have at most one parent and at most one child (forming a list), but | |
| 27 // there can be multiple lists, with each list root having its own priority. | |
| 28 // Individual nodes can also be marked as ready to read/write, and then the | |
| 29 // whole structure can be queried to pick the next node to read/write out of | |
| 30 // those ready. | |
| 31 // | |
| 32 // The NodeId type must be a POD that supports comparison (most | |
| 33 // likely, it will be a number). | |
| 34 | |
| 35 namespace test { | |
| 36 template <typename NodeId> | |
| 37 class SpdyPriorityTreePeer; | |
| 38 } | |
| 39 | |
| 40 const int kRootNodeId = 0; | |
| 41 const int kDefaultWeight = 16; | |
| 42 const int kMinWeight = 1; | |
| 43 const int kMaxWeight = 256; | |
| 44 | |
| 45 template <typename NodeId> | |
| 46 class SpdyPriorityTree { | |
| 47 typedef std::vector<std::pair<NodeId, float> > PriorityNodeList; | |
| 48 | |
| 49 public: | |
| 50 SpdyPriorityTree(); | |
| 51 ~SpdyPriorityTree(); | |
| 52 | |
| 53 typedef std::list<NodeId> List; | |
| 54 struct Node { | |
| 55 Node(); | |
| 56 ~Node(); | |
| 57 | |
| 58 NodeId id; | |
| 59 NodeId parent_id; | |
| 60 int weight; // Weights can range between 1 and 256 (inclusive). | |
| 61 // The total weight of this node's direct descendants. | |
| 62 int total_child_weights; | |
| 63 // The total weight of direct descendants that are writeable | |
| 64 // (ready to write and not blocked). This value does not necessarily | |
| 65 // reflect the current state of the tree; instead, we lazily update it | |
| 66 // on calls to PropagateNodeState(node.id). | |
| 67 int total_writeable_child_weights; | |
| 68 List* child_list; // node ID's of children, if any | |
| 69 bool blocked; // Is the associated stream write-blocked? | |
| 70 bool ready; // Does the stream have data ready for writing? | |
| 71 float priority; // The fraction of resources to dedicate to this node. | |
| 72 }; | |
| 73 | |
| 74 // Orders in descending order of priority. | |
| 75 struct NodePriorityComparator { | |
| 76 bool operator ()(const std::pair<NodeId, float>& lhs, | |
| 77 const std::pair<NodeId, float>& rhs); | |
| 78 }; | |
| 79 | |
| 80 friend class test::SpdyPriorityTreePeer<NodeId>; | |
| 81 | |
| 82 // Return the number of nodes currently in the tree. | |
| 83 int num_nodes() const; | |
| 84 | |
| 85 // Return true if the tree contains a node with the given ID. | |
| 86 bool NodeExists(NodeId node_id) const; | |
| 87 | |
| 88 // Add a new node with the given weight and parent. Non-exclusive nodes | |
| 89 // simply get added below the parent node. If exclusive = true, the node | |
| 90 // becomes the parent's sole child and the parent's previous children | |
| 91 // become the children of the new node. | |
| 92 // Returns true on success. Returns false if the node already exists | |
| 93 // in the tree, or if the parent node does not exist. | |
| 94 bool AddNode(NodeId node_id, NodeId parent_id, int weight, bool exclusive); | |
| 95 | |
| 96 // Remove an existing node from the tree. Returns true on success, or | |
| 97 // false if the node doesn't exist. | |
| 98 bool RemoveNode(NodeId node_id); | |
| 99 | |
| 100 // Get the weight of the given node. | |
| 101 int GetWeight(NodeId node_id) const; | |
| 102 | |
| 103 // Get the parent of the given node. If the node doesn't exist, or is a root | |
| 104 // node (and thus has no parent), returns NodeId(). | |
| 105 NodeId GetParent(NodeId node_id) const; | |
| 106 | |
| 107 // Get the child list of the given node. If the node doesn't exist, or has no | |
| 108 // child, returns NULL. | |
| 109 std::list<NodeId>* GetChildren(NodeId node_id) const; | |
| 110 | |
| 111 // Set the priority of the given node. | |
| 112 bool SetWeight(NodeId node_id, int weight); | |
| 113 | |
| 114 // Set the parent of the given node. Returns true on success. | |
| 115 // Returns false and has no effect if the node and/or the parent doesn't | |
| 116 // exist. If the new parent is a descendant of the node (i.e. this would have | |
| 117 // created a cycle) then we rearrange the topology of the tree as described | |
| 118 // in the HTTP2 spec. | |
| 119 bool SetParent(NodeId node_id, NodeId parent_id, bool exclusive); | |
| 120 | |
| 121 // Returns true if the node parent_id has child_id in its child_list. | |
| 122 bool HasChild(NodeId parent_id, NodeId child_id) const; | |
| 123 | |
| 124 // Mark a node as blocked or unblocked. Return true on success, or false | |
| 125 // if unable to mark the specified node. | |
| 126 bool SetBlocked(NodeId node_id, bool blocked); | |
| 127 | |
| 128 // Mark whether or not a node is ready to write; i.e. whether there is | |
| 129 // buffered data for the associated stream. Return true on success, or false | |
| 130 // if unable to mark the specified node. | |
| 131 bool SetReady(NodeId node_id, bool ready); | |
| 132 | |
| 133 // Return true if all internal invariants hold (useful for unit tests). | |
| 134 // Unless there are bugs, this should always return true. | |
| 135 bool ValidateInvariantsForTests() const; | |
| 136 | |
| 137 // Get the given node, or return NULL if it doesn't exist. | |
| 138 const Node* FindNode(NodeId node_id) const; | |
| 139 | |
| 140 // Returns an ordered list of writeable nodes and their priorities. | |
| 141 // Priority is calculated as: | |
| 142 // parent's priority * (node's weight / sum of sibling weights) | |
| 143 PriorityNodeList GetPriorityList(); | |
| 144 | |
| 145 protected: | |
| 146 // Update the value of total_writeable_child_weights for the given node | |
| 147 // to reflect the current state of the tree. | |
| 148 void PropagateNodeState(NodeId node); | |
| 149 | |
| 150 private: | |
| 151 typedef base::hash_map<NodeId, Node> NodeMap; | |
| 152 | |
| 153 NodeMap all_nodes_; // maps from node IDs to Node objects | |
| 154 | |
| 155 DISALLOW_COPY_AND_ASSIGN(SpdyPriorityTree); | |
| 156 }; | |
| 157 | |
| 158 template <typename NodeId> | |
| 159 SpdyPriorityTree<NodeId>::SpdyPriorityTree() { | |
| 160 Node* root_node = &all_nodes_[kRootNodeId]; | |
| 161 root_node->id = kRootNodeId; | |
| 162 root_node->weight = kDefaultWeight; | |
| 163 root_node->parent_id = static_cast<NodeId>(kRootNodeId); | |
| 164 root_node->child_list = new std::list<NodeId>; | |
| 165 root_node->priority = 1.0; | |
| 166 root_node->ready = true; | |
| 167 } | |
| 168 | |
| 169 template <typename NodeId> | |
| 170 SpdyPriorityTree<NodeId>::~SpdyPriorityTree() {} | |
| 171 | |
| 172 template <typename NodeId> | |
| 173 SpdyPriorityTree<NodeId>::Node::Node() : | |
| 174 parent_id(kRootNodeId), | |
| 175 weight(kDefaultWeight), | |
| 176 total_child_weights(0), | |
| 177 total_writeable_child_weights(0), | |
| 178 child_list(), | |
| 179 blocked(false), | |
| 180 ready(false), | |
| 181 priority(0) { | |
| 182 } | |
| 183 | |
| 184 template <typename NodeId> | |
| 185 SpdyPriorityTree<NodeId>::Node::~Node() { | |
| 186 delete child_list; | |
| 187 } | |
| 188 | |
| 189 template <typename NodeId> | |
| 190 bool SpdyPriorityTree<NodeId>::NodePriorityComparator::operator ()( | |
| 191 const std::pair<NodeId, float>& lhs, | |
| 192 const std::pair<NodeId, float>& rhs) { | |
| 193 return lhs.second > rhs.second; | |
| 194 } | |
| 195 | |
| 196 template <typename NodeId> | |
| 197 int SpdyPriorityTree<NodeId>::num_nodes() const { | |
| 198 return all_nodes_.size(); | |
| 199 } | |
| 200 | |
| 201 template <typename NodeId> | |
| 202 bool SpdyPriorityTree<NodeId>::NodeExists(NodeId node_id) const { | |
| 203 return all_nodes_.count(node_id) != 0; | |
| 204 } | |
| 205 | |
| 206 template <typename NodeId> | |
| 207 bool SpdyPriorityTree<NodeId>::AddNode(NodeId node_id, | |
| 208 NodeId parent_id, | |
| 209 int weight, | |
| 210 bool exclusive) { | |
| 211 if (NodeExists(node_id) || !NodeExists(parent_id)) { | |
| 212 return false; | |
| 213 } | |
| 214 if (weight < kMinWeight || weight > kMaxWeight) { | |
| 215 return false; | |
| 216 } | |
| 217 Node* parent = &all_nodes_[parent_id]; | |
| 218 Node* new_node = &all_nodes_[node_id]; | |
| 219 new_node->id = node_id; | |
| 220 new_node->weight = weight; | |
| 221 new_node->parent_id = parent_id; | |
| 222 if (exclusive) { | |
| 223 // Move the parent's current children below the new node. | |
| 224 new_node->child_list = parent->child_list; | |
| 225 new_node->total_child_weights = parent->total_child_weights; | |
| 226 // Update each child's parent_id. | |
| 227 for (typename List::iterator it = new_node->child_list->begin(); | |
| 228 it != new_node->child_list->end(); ++it) { | |
| 229 Node* child = &all_nodes_[*it]; | |
| 230 child->parent_id = node_id; | |
| 231 } | |
| 232 // Clear parent's old child data. | |
| 233 parent->child_list = new std::list<NodeId>; | |
| 234 parent->total_child_weights = 0; | |
| 235 } else { | |
| 236 new_node->child_list = new std::list<NodeId>; | |
| 237 } | |
| 238 // Add new node to parent. | |
| 239 parent->child_list->push_back(node_id); | |
| 240 parent->total_child_weights += weight; | |
| 241 return true; | |
| 242 } | |
| 243 | |
| 244 template <typename NodeId> | |
| 245 bool SpdyPriorityTree<NodeId>::RemoveNode(NodeId node_id) { | |
| 246 if (node_id == static_cast<NodeId>(kRootNodeId) || !NodeExists(node_id)) { | |
| 247 return false; | |
| 248 } | |
| 249 const Node& node = all_nodes_[node_id]; | |
| 250 | |
| 251 DCHECK(NodeExists(node.parent_id)); | |
| 252 Node* parent = &all_nodes_[node.parent_id]; | |
| 253 // Remove the node id from parent's child list. | |
| 254 parent->child_list->remove(node_id); | |
| 255 parent->total_child_weights -= node.weight; | |
| 256 | |
| 257 // Move the node's children to the parent's child list. | |
| 258 if (node.child_list != NULL) { | |
| 259 // Update each child's parent_id and weight. | |
| 260 for (typename List::iterator it = node.child_list->begin(); | |
| 261 it != node.child_list->end(); ++it) { | |
| 262 Node* child = &all_nodes_[*it]; | |
| 263 child->parent_id = node.parent_id; | |
| 264 // Divide the removed node's weight among its children, rounding to the | |
| 265 // nearest valid weight. | |
| 266 float float_weight = node.weight * static_cast<float>(child->weight) / | |
| 267 static_cast<float>(node.total_child_weights); | |
| 268 int new_weight = std::floor(float_weight + 0.5); | |
| 269 if (new_weight == 0) { | |
| 270 new_weight = 1; | |
| 271 } | |
| 272 child->weight = new_weight; | |
| 273 parent->total_child_weights += child->weight; | |
| 274 } | |
| 275 parent->child_list->splice(parent->child_list->end(), *node.child_list); | |
| 276 } | |
| 277 | |
| 278 // Delete the node. | |
| 279 all_nodes_.erase(node_id); | |
| 280 return true; | |
| 281 } | |
| 282 | |
| 283 template <typename NodeId> | |
| 284 int SpdyPriorityTree<NodeId>::GetWeight(NodeId node_id) const { | |
| 285 const Node* node = FindNode(node_id); | |
| 286 if (node != NULL) { | |
| 287 return node->weight; | |
| 288 } | |
| 289 return 0; | |
| 290 } | |
| 291 | |
| 292 template <typename NodeId> | |
| 293 NodeId SpdyPriorityTree<NodeId>::GetParent(NodeId node_id) const { | |
| 294 const Node* node = FindNode(node_id); | |
| 295 if (node != NULL && node->id != static_cast<NodeId>(kRootNodeId)) { | |
| 296 return node->parent_id; | |
| 297 } | |
| 298 return static_cast<NodeId>(kRootNodeId); | |
| 299 } | |
| 300 | |
| 301 template <typename NodeId> | |
| 302 std::list<NodeId>* SpdyPriorityTree<NodeId>::GetChildren(NodeId node_id) const { | |
| 303 const Node* node = FindNode(node_id); | |
| 304 if (node != NULL) { | |
| 305 return node->child_list; | |
| 306 } | |
| 307 return NULL; | |
| 308 } | |
| 309 | |
| 310 template <typename NodeId> | |
| 311 bool SpdyPriorityTree<NodeId>::SetWeight( | |
| 312 NodeId node_id, int weight) { | |
| 313 if (!NodeExists(node_id)) { | |
| 314 return false; | |
| 315 } | |
| 316 if (weight < kMinWeight || weight > kMaxWeight) { | |
| 317 return false; | |
| 318 } | |
| 319 | |
| 320 Node* node = &all_nodes_[node_id]; | |
| 321 Node* parent = &all_nodes_[node->parent_id]; | |
| 322 | |
| 323 parent->total_child_weights += (weight - node->weight); | |
| 324 node->weight = weight; | |
| 325 | |
| 326 return true; | |
| 327 } | |
| 328 | |
| 329 | |
| 330 template <typename NodeId> | |
| 331 bool SpdyPriorityTree<NodeId>::SetParent( | |
| 332 NodeId node_id, NodeId parent_id, bool exclusive) { | |
| 333 if (!NodeExists(node_id) || !NodeExists(parent_id)) { | |
| 334 return false; | |
| 335 } | |
| 336 if (node_id == parent_id) return false; | |
| 337 | |
| 338 Node* node = &all_nodes_[node_id]; | |
| 339 Node* new_parent = &all_nodes_[parent_id]; | |
| 340 // If the new parent is already the node's parent, we're done. | |
| 341 if (node->parent_id == parent_id) { | |
| 342 return true; | |
| 343 } | |
| 344 | |
| 345 // Next, check to see if the new parent is currently a descendant | |
| 346 // of the node. | |
| 347 Node* last = new_parent; | |
| 348 NodeId last_id = parent_id; | |
| 349 bool cycle_exists = false; | |
| 350 while (last->parent_id != static_cast<NodeId>(kRootNodeId)) { | |
| 351 if (last->parent_id == node_id) { | |
| 352 cycle_exists = true; | |
| 353 break; | |
| 354 } | |
| 355 last_id = last->parent_id; | |
| 356 DCHECK(NodeExists(last_id)); | |
| 357 last = &all_nodes_[last_id]; | |
| 358 } | |
| 359 | |
| 360 if (cycle_exists) { | |
| 361 // The new parent moves to the level of the current node. | |
| 362 SetParent(parent_id, node->parent_id, false); | |
| 363 } | |
| 364 | |
| 365 // Remove node from old parent's child list. | |
| 366 const NodeId old_parent_id = node->parent_id; | |
| 367 DCHECK(NodeExists(old_parent_id)); | |
| 368 Node* old_parent = &all_nodes_[old_parent_id]; | |
| 369 old_parent->child_list->remove(node_id); | |
| 370 old_parent->total_child_weights -= node->weight; | |
| 371 | |
| 372 // Make the change. | |
| 373 node->parent_id = parent_id; | |
| 374 new_parent->child_list->push_back(node_id); | |
| 375 new_parent->total_child_weights += node->weight; | |
| 376 return true; | |
| 377 } | |
| 378 | |
| 379 template <typename NodeId> | |
| 380 bool SpdyPriorityTree<NodeId>::SetBlocked(NodeId node_id, bool blocked) { | |
| 381 if (!NodeExists(node_id)) { | |
| 382 return false; | |
| 383 } | |
| 384 | |
| 385 Node* node = &all_nodes_[node_id]; | |
| 386 node->blocked = blocked; | |
| 387 return true; | |
| 388 } | |
| 389 | |
| 390 template <typename NodeId> | |
| 391 bool SpdyPriorityTree<NodeId>::SetReady(NodeId node_id, bool ready) { | |
| 392 if (!NodeExists(node_id)) { | |
| 393 return false; | |
| 394 } | |
| 395 Node* node = &all_nodes_[node_id]; | |
| 396 node->ready = ready; | |
| 397 return true; | |
| 398 } | |
| 399 | |
| 400 template <typename NodeId> | |
| 401 void SpdyPriorityTree<NodeId>::PropagateNodeState(NodeId node_id) { | |
| 402 // Reset total_writeable_child_weights to its maximum value. | |
| 403 Node* node = &all_nodes_[node_id]; | |
| 404 node->total_writeable_child_weights = node->total_child_weights; | |
| 405 for (typename List::iterator it = node->child_list->begin(); | |
| 406 it != node->child_list->end(); ++it) { | |
| 407 PropagateNodeState(*it); | |
| 408 } | |
| 409 if (node->total_writeable_child_weights == 0 && | |
| 410 (node->blocked || !node->ready)) { | |
| 411 // Tell the parent that this entire subtree is unwriteable. | |
| 412 Node* parent = &all_nodes_[node->parent_id]; | |
| 413 parent->total_writeable_child_weights -= node->weight; | |
| 414 } | |
| 415 } | |
| 416 | |
| 417 template <typename NodeId> | |
| 418 const typename SpdyPriorityTree<NodeId>::Node* | |
| 419 SpdyPriorityTree<NodeId>::FindNode(NodeId node_id) const { | |
| 420 typename NodeMap::const_iterator iter = all_nodes_.find(node_id); | |
| 421 if (iter == all_nodes_.end()) { | |
| 422 return NULL; | |
| 423 } | |
| 424 return &iter->second; | |
| 425 } | |
| 426 | |
| 427 template <typename NodeId> | |
| 428 bool SpdyPriorityTree<NodeId>::HasChild(NodeId parent_id, | |
| 429 NodeId child_id) const { | |
| 430 const Node* parent = FindNode(parent_id); | |
| 431 return parent->child_list->end() != | |
| 432 std::find(parent->child_list->begin(), | |
| 433 parent->child_list->end(), | |
| 434 child_id); | |
| 435 } | |
| 436 | |
| 437 template <typename NodeId> | |
| 438 std::vector<std::pair<NodeId, float> > | |
| 439 SpdyPriorityTree<NodeId>::GetPriorityList() { | |
| 440 typedef std::pair<NodeId, float> PriorityNode; | |
| 441 typedef std::vector<PriorityNode> PriorityList; | |
| 442 PriorityList priority_list; | |
| 443 | |
| 444 // Update total_writeable_child_weights to reflect the current | |
| 445 // state of the tree. | |
| 446 PropagateNodeState(kRootNodeId); | |
| 447 | |
| 448 List queue; | |
| 449 const Node* root_node = FindNode(kRootNodeId); | |
| 450 DCHECK(root_node->priority == 1.0); | |
| 451 // Start by examining our top-level nodes. | |
| 452 for (typename List::iterator it = root_node->child_list->begin(); | |
| 453 it != root_node->child_list->end(); ++it) { | |
| 454 queue.push_back(*it); | |
| 455 } | |
| 456 while (!queue.empty()) { | |
| 457 NodeId current_node_id = queue.front(); | |
| 458 Node* current_node = &all_nodes_[current_node_id]; | |
| 459 const Node* parent_node = FindNode(current_node->parent_id); | |
| 460 if (current_node->blocked || !current_node->ready) { | |
| 461 if (current_node->total_writeable_child_weights > 0) { | |
| 462 // This node isn't writeable, but it has writeable children. | |
| 463 // Calculate the total fraction of resources we can allot | |
| 464 // to this subtree. | |
| 465 current_node->priority = parent_node->priority * | |
| 466 (static_cast<float>(current_node->weight) / | |
| 467 static_cast<float>(parent_node->total_writeable_child_weights)); | |
| 468 // Examine the children. | |
| 469 for (typename List::iterator it = current_node->child_list->begin(); | |
| 470 it != current_node->child_list->end(); ++it) { | |
| 471 queue.push_back(*it); | |
| 472 } | |
| 473 } else { | |
| 474 // There's nothing to see in this subtree. | |
| 475 current_node->priority = 0; | |
| 476 } | |
| 477 } else { | |
| 478 // This node is writeable; calculate its priority. | |
| 479 current_node->priority = parent_node->priority * | |
| 480 (static_cast<float>(current_node->weight) / | |
| 481 static_cast<float>(parent_node->total_writeable_child_weights)); | |
| 482 // Add this node to the priority list. | |
| 483 priority_list.push_back(PriorityNode(current_node_id, | |
| 484 current_node->priority)); | |
| 485 } | |
| 486 // Remove this node from the queue. | |
| 487 queue.pop_front(); | |
| 488 } | |
| 489 | |
| 490 // Sort the nodes in descending order of priority. | |
| 491 std::sort(priority_list.begin(), priority_list.end(), | |
| 492 NodePriorityComparator()); | |
| 493 | |
| 494 return priority_list; | |
| 495 } | |
| 496 | |
| 497 template <typename NodeId> | |
| 498 bool SpdyPriorityTree<NodeId>::ValidateInvariantsForTests() const { | |
| 499 int total_nodes = 0; | |
| 500 int nodes_visited = 0; | |
| 501 // Iterate through all nodes in the map. | |
| 502 for (typename NodeMap::const_iterator iter = all_nodes_.begin(); | |
| 503 iter != all_nodes_.end(); ++iter) { | |
| 504 ++total_nodes; | |
| 505 ++nodes_visited; | |
| 506 const Node& node = iter->second; | |
| 507 // All nodes except the root should have a parent, and should appear in | |
| 508 // the child_list of that parent. | |
| 509 if (node.id != static_cast<NodeId>(kRootNodeId) && | |
| 510 (!NodeExists(node.parent_id) || | |
| 511 !HasChild(node.parent_id, node.id))) { | |
| 512 DLOG(INFO) << "Parent node " << node.parent_id | |
| 513 << " does not exist, or does not list node " << node.id | |
| 514 << " as its child."; | |
| 515 return false; | |
| 516 } | |
| 517 | |
| 518 if (!node.child_list->empty()) { | |
| 519 int total_child_weights = 0; | |
| 520 // Iterate through the node's children. | |
| 521 for (typename List::iterator it = node.child_list->begin(); | |
| 522 it != node.child_list->end(); ++it) { | |
| 523 ++nodes_visited; | |
| 524 // Each node in the list should exist and should have this node | |
| 525 // set as its parent. | |
| 526 if (!NodeExists(*it) || node.id != GetParent(*it)) { | |
| 527 DLOG(INFO) << "Child node " << *it << " does not exist, " | |
| 528 << "or does not list " << node.id << " as its parent."; | |
| 529 return false; | |
| 530 } | |
| 531 const Node* child = FindNode(*it); | |
| 532 total_child_weights += child->weight; | |
| 533 } | |
| 534 // Verify that total_child_weights is correct. | |
| 535 if (total_child_weights != node.total_child_weights) { | |
| 536 DLOG(INFO) << "Child weight totals do not agree. For node " << node.id | |
| 537 << " total_child_weights has value " | |
| 538 << node.total_child_weights | |
| 539 << ", expected " << total_child_weights; | |
| 540 return false; | |
| 541 } | |
| 542 } | |
| 543 } | |
| 544 | |
| 545 // Make sure num_nodes reflects the total number of nodes the map contains. | |
| 546 if (total_nodes != num_nodes()) { | |
| 547 DLOG(INFO) << "Map contains incorrect number of nodes."; | |
| 548 return false; | |
| 549 } | |
| 550 // Validate the validation function; we should have visited each node twice | |
| 551 // (except for the root) | |
| 552 DCHECK(nodes_visited == 2*num_nodes() - 1); | |
| 553 return true; | |
| 554 } | |
| 555 | |
| 556 } // namespace net | |
| 557 | |
| 558 #endif // NET_SPDY_SPDY_PRIORITY_TREE_H_ | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 992733002:
Remove //net (except for Android test stuff) and sdch (Closed)
Base URL: git@github.com:domokit/mojo.git@master