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