| OLD | NEW |
| 1 // Copyright (c) 2015 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2015 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 "cc/base/rtree.h" | 5 #include "cc/base/rtree.h" |
| 6 | 6 |
| 7 #include <stddef.h> | 7 #include <stddef.h> |
| 8 #include <stdint.h> | 8 #include <stdint.h> |
| 9 | 9 |
| 10 #include <algorithm> | 10 #include <algorithm> |
| 11 #include <cmath> | 11 #include <cmath> |
| 12 | 12 |
| 13 #include "base/logging.h" | 13 #include "base/logging.h" |
| 14 #include "base/numerics/saturated_arithmetic.h" | 14 #include "base/numerics/saturated_arithmetic.h" |
| 15 | 15 |
| 16 namespace cc { | 16 namespace cc { |
| 17 | 17 |
| 18 RTree::RTree() : num_data_elements_(0u) {} | 18 RTree::RTree() : num_data_elements_(0u) {} |
| 19 | 19 |
| 20 RTree::~RTree() {} | 20 RTree::~RTree() {} |
| 21 | 21 |
| 22 RTree::Node* RTree::AllocateNodeAtLevel(int level) { | 22 RTree::Node* RTree::AllocateNodeAtLevel(int level) { |
| 23 // We don't allow reallocations, since that would invalidate references to | 23 // We don't allow reallocations, since that would invalidate references to |
| 24 // existing nodes, so verify that capacity > size. | 24 // existing nodes, so verify that capacity > size. |
| 25 DCHECK_GT(nodes_.capacity(), nodes_.size()); | 25 DCHECK_GT(nodes_.capacity(), nodes_.size()); |
| 26 nodes_.emplace_back(); | 26 nodes_.emplace_back(level); |
| 27 Node& node = nodes_.back(); | 27 return &nodes_.back(); |
| 28 node.num_children = 0; | |
| 29 node.level = level; | |
| 30 return &node; | |
| 31 } | 28 } |
| 32 | 29 |
| 33 RTree::Branch RTree::BuildRecursive(std::vector<Branch>* branches, int level) { | 30 RTree::Branch RTree::BuildRecursive(std::vector<Branch>* branches, int level) { |
| 34 // Only one branch. It will be the root. | 31 // Only one branch. It will be the root. |
| 35 if (branches->size() == 1) | 32 if (branches->size() == 1) |
| 36 return (*branches)[0]; | 33 return (*branches)[0]; |
| 37 | 34 |
| 38 // TODO(vmpstr): Investigate if branches should be sorted in y. | 35 // TODO(vmpstr): Investigate if branches should be sorted in y. |
| 39 // The comment from Skia reads: | 36 // The comment from Skia reads: |
| 40 // We might sort our branches here, but we expect Blink gives us a reasonable | 37 // We might sort our branches here, but we expect Blink gives us a reasonable |
| (...skipping 87 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 128 SearchRecursive(node->children[i].subtree, query, results); | 125 SearchRecursive(node->children[i].subtree, query, results); |
| 129 } | 126 } |
| 130 } | 127 } |
| 131 } | 128 } |
| 132 | 129 |
| 133 gfx::Rect RTree::GetBounds() const { | 130 gfx::Rect RTree::GetBounds() const { |
| 134 return root_.bounds; | 131 return root_.bounds; |
| 135 } | 132 } |
| 136 | 133 |
| 137 } // namespace cc | 134 } // namespace cc |
| OLD | NEW |