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