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 <cmath> | 11 #include <cmath> |
11 | 12 |
12 #include "base/logging.h" | 13 #include "base/logging.h" |
| 14 #include "base/numerics/saturated_arithmetic.h" |
13 | 15 |
14 namespace cc { | 16 namespace cc { |
15 | 17 |
16 RTree::RTree() : num_data_elements_(0u) {} | 18 RTree::RTree() : num_data_elements_(0u), nodes_(sizeof(Node)) {} |
17 | 19 |
18 RTree::~RTree() {} | 20 RTree::~RTree() {} |
19 | 21 |
20 RTree::Node* RTree::AllocateNodeAtLevel(int level) { | 22 RTree::Node* RTree::AllocateNodeAtLevel(int level) { |
21 nodes_.push_back(Node()); | 23 Node& node = nodes_.AllocateAndConstruct<Node>(); |
22 Node& node = nodes_.back(); | |
23 node.num_children = 0; | 24 node.num_children = 0; |
24 node.level = level; | 25 node.level = level; |
25 return &node; | 26 return &node; |
26 } | 27 } |
27 | 28 |
28 RTree::Branch RTree::BuildRecursive(std::vector<Branch>* branches, int level) { | 29 RTree::Branch RTree::BuildRecursive(std::vector<Branch>* branches, int level) { |
29 // Only one branch. It will be the root. | 30 // Only one branch. It will be the root. |
30 if (branches->size() == 1) | 31 if (branches->size() == 1) |
31 return (*branches)[0]; | 32 return (*branches)[0]; |
32 | 33 |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
69 } | 70 } |
70 } | 71 } |
71 Node* node = AllocateNodeAtLevel(level); | 72 Node* node = AllocateNodeAtLevel(level); |
72 node->num_children = 1; | 73 node->num_children = 1; |
73 node->children[0] = (*branches)[current_branch]; | 74 node->children[0] = (*branches)[current_branch]; |
74 | 75 |
75 Branch branch; | 76 Branch branch; |
76 branch.bounds = (*branches)[current_branch].bounds; | 77 branch.bounds = (*branches)[current_branch].bounds; |
77 branch.subtree = node; | 78 branch.subtree = node; |
78 ++current_branch; | 79 ++current_branch; |
| 80 int x = branch.bounds.x(); |
| 81 int y = branch.bounds.y(); |
| 82 int right = branch.bounds.right(); |
| 83 int bottom = branch.bounds.bottom(); |
79 for (int k = 1; k < increment_by && current_branch < branches->size(); | 84 for (int k = 1; k < increment_by && current_branch < branches->size(); |
80 ++k) { | 85 ++k) { |
81 branch.bounds.Union((*branches)[current_branch].bounds); | 86 // We use a custom union instead of gfx::Rect::Union here, since this |
| 87 // bypasses some empty checks and extra setters, which improves |
| 88 // performance. |
| 89 auto& bounds = (*branches)[current_branch].bounds; |
| 90 x = std::min(x, bounds.x()); |
| 91 y = std::min(y, bounds.y()); |
| 92 right = std::max(right, bounds.right()); |
| 93 bottom = std::max(bottom, bounds.bottom()); |
| 94 |
82 node->children[k] = (*branches)[current_branch]; | 95 node->children[k] = (*branches)[current_branch]; |
83 ++node->num_children; | 96 ++node->num_children; |
84 ++current_branch; | 97 ++current_branch; |
85 } | 98 } |
| 99 branch.bounds.SetRect(x, y, base::SaturatedSubtraction(right, x), |
| 100 base::SaturatedSubtraction(bottom, y)); |
| 101 |
86 DCHECK_LT(new_branch_index, current_branch); | 102 DCHECK_LT(new_branch_index, current_branch); |
87 (*branches)[new_branch_index] = branch; | 103 (*branches)[new_branch_index] = branch; |
88 ++new_branch_index; | 104 ++new_branch_index; |
89 } | 105 } |
90 } | 106 } |
91 branches->resize(new_branch_index); | 107 branches->resize(new_branch_index); |
92 return BuildRecursive(branches, level + 1); | 108 return BuildRecursive(branches, level + 1); |
93 } | 109 } |
94 | 110 |
95 void RTree::Search(const gfx::Rect& query, std::vector<size_t>* results) const { | 111 void RTree::Search(const gfx::Rect& query, std::vector<size_t>* results) const { |
(...skipping 12 matching lines...) Expand all Loading... |
108 SearchRecursive(node->children[i].subtree, query, results); | 124 SearchRecursive(node->children[i].subtree, query, results); |
109 } | 125 } |
110 } | 126 } |
111 } | 127 } |
112 | 128 |
113 gfx::Rect RTree::GetBounds() const { | 129 gfx::Rect RTree::GetBounds() const { |
114 return root_.bounds; | 130 return root_.bounds; |
115 } | 131 } |
116 | 132 |
117 } // namespace cc | 133 } // namespace cc |
OLD | NEW |