OLD | NEW |
1 // Copyright (c) 2013 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "net/quic/crypto/strike_register.h" | 5 #include "net/quic/crypto/strike_register.h" |
6 | 6 |
7 #include <limits> | 7 #include <limits> |
8 | 8 |
9 #include "base/logging.h" | 9 #include "base/logging.h" |
10 | 10 |
(...skipping 382 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
393 // DropOldestNode should never be called on an empty tree. | 393 // DropOldestNode should never be called on an empty tree. |
394 DCHECK(internal_node_head_ != kNil); | 394 DCHECK(internal_node_head_ != kNil); |
395 | 395 |
396 // An internal node in a crit-bit tree always has exactly two children. | 396 // An internal node in a crit-bit tree always has exactly two children. |
397 // This means that, if we are removing an external node (which is one of | 397 // This means that, if we are removing an external node (which is one of |
398 // those children), then we also need to remove an internal node. In order | 398 // those children), then we also need to remove an internal node. In order |
399 // to do that we keep pointers to the parent (wherep) and grandparent | 399 // to do that we keep pointers to the parent (wherep) and grandparent |
400 // (whereq) when walking down the tree. | 400 // (whereq) when walking down the tree. |
401 | 401 |
402 uint32 p = internal_node_head_ >> 8, *wherep = &internal_node_head_, | 402 uint32 p = internal_node_head_ >> 8, *wherep = &internal_node_head_, |
403 *whereq = NULL; | 403 *whereq = nullptr; |
404 while ((p & kExternalFlag) == 0) { | 404 while ((p & kExternalFlag) == 0) { |
405 whereq = wherep; | 405 whereq = wherep; |
406 InternalNode* inode = &internal_nodes_[p]; | 406 InternalNode* inode = &internal_nodes_[p]; |
407 // We always go left, towards the smallest element, exploiting the fact | 407 // We always go left, towards the smallest element, exploiting the fact |
408 // that the timestamp is big-endian and at the start of the value. | 408 // that the timestamp is big-endian and at the start of the value. |
409 wherep = &inode->data_[0]; | 409 wherep = &inode->data_[0]; |
410 p = (*wherep) >> 8; | 410 p = (*wherep) >> 8; |
411 } | 411 } |
412 | 412 |
413 const uint32 ext_index = p & ~kExternalFlag; | 413 const uint32 ext_index = p & ~kExternalFlag; |
(...skipping 97 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
511 CHECK_EQ(free_internal_nodes.count(inter), 0u); | 511 CHECK_EQ(free_internal_nodes.count(inter), 0u); |
512 CHECK_EQ(used_internal_nodes->count(inter), 0u); | 512 CHECK_EQ(used_internal_nodes->count(inter), 0u); |
513 used_internal_nodes->insert(inter); | 513 used_internal_nodes->insert(inter); |
514 ValidateTree(inter, bit, bits, free_internal_nodes, free_external_nodes, | 514 ValidateTree(inter, bit, bits, free_internal_nodes, free_external_nodes, |
515 used_internal_nodes, used_external_nodes); | 515 used_internal_nodes, used_external_nodes); |
516 } | 516 } |
517 } | 517 } |
518 } | 518 } |
519 | 519 |
520 } // namespace net | 520 } // namespace net |
OLD | NEW |