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