Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(381)

Side by Side Diff: cc/base/rtree.h

Issue 2871183002: Use emplace_back in RTree::Build (Closed)
Patch Set: Created 3 years, 7 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « AUTHORS ('k') | cc/base/rtree.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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 #ifndef CC_BASE_RTREE_H_ 5 #ifndef CC_BASE_RTREE_H_
6 #define CC_BASE_RTREE_H_ 6 #define CC_BASE_RTREE_H_
7 7
8 #include <stddef.h> 8 #include <stddef.h>
9 #include <stdint.h> 9 #include <stdint.h>
10 10
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after
45 DCHECK_EQ(0u, num_data_elements_); 45 DCHECK_EQ(0u, num_data_elements_);
46 46
47 std::vector<Branch> branches; 47 std::vector<Branch> branches;
48 branches.reserve(items.size()); 48 branches.reserve(items.size());
49 49
50 for (size_t i = 0; i < items.size(); i++) { 50 for (size_t i = 0; i < items.size(); i++) {
51 const gfx::Rect& bounds = bounds_getter(items[i]); 51 const gfx::Rect& bounds = bounds_getter(items[i]);
52 if (bounds.IsEmpty()) 52 if (bounds.IsEmpty())
53 continue; 53 continue;
54 54
55 branches.push_back(Branch()); 55 branches.emplace_back(i, bounds);
56 Branch& branch = branches.back();
57 branch.bounds = bounds;
58 branch.index = i;
59 } 56 }
60 57
61 num_data_elements_ = branches.size(); 58 num_data_elements_ = branches.size();
62 if (num_data_elements_ == 1u) { 59 if (num_data_elements_ == 1u) {
63 nodes_.reserve(1); 60 nodes_.reserve(1);
64 Node* node = AllocateNodeAtLevel(0); 61 Node* node = AllocateNodeAtLevel(0);
65 node->num_children = 1; 62 node->num_children = 1;
66 node->children[0] = branches[0]; 63 node->children[0] = branches[0];
67 root_.subtree = node; 64 root_.subtree = node;
68 root_.bounds = branches[0].bounds; 65 root_.bounds = branches[0].bounds;
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after
108 struct Branch { 105 struct Branch {
109 // When the node level is 0, then the node is a leaf and the branch has a 106 // When the node level is 0, then the node is a leaf and the branch has a
110 // valid index pointing to an element in the vector that was used to build 107 // valid index pointing to an element in the vector that was used to build
111 // this rtree. When the level is not 0, it's an internal node and it has a 108 // this rtree. When the level is not 0, it's an internal node and it has a
112 // valid subtree pointer. 109 // valid subtree pointer.
113 union { 110 union {
114 Node* subtree; 111 Node* subtree;
115 size_t index; 112 size_t index;
116 }; 113 };
117 gfx::Rect bounds; 114 gfx::Rect bounds;
115
116 Branch() {}
117 Branch(size_t index, const gfx::Rect& bounds)
118 : index(index), bounds(bounds) {}
118 }; 119 };
119 120
120 struct Node { 121 struct Node {
121 uint16_t num_children; 122 uint16_t num_children;
122 uint16_t level; 123 uint16_t level;
123 Branch children[kMaxChildren]; 124 Branch children[kMaxChildren];
125
126 explicit Node(uint16_t level) : num_children(0), level(level) {}
124 }; 127 };
125 128
126 void SearchRecursive(Node* root, 129 void SearchRecursive(Node* root,
127 const gfx::Rect& query, 130 const gfx::Rect& query,
128 std::vector<size_t>* results) const; 131 std::vector<size_t>* results) const;
129 132
130 // Consumes the input array. 133 // Consumes the input array.
131 Branch BuildRecursive(std::vector<Branch>* branches, int level); 134 Branch BuildRecursive(std::vector<Branch>* branches, int level);
132 Node* AllocateNodeAtLevel(int level); 135 Node* AllocateNodeAtLevel(int level);
133 136
134 // This is the count of data elements (rather than total nodes in the tree) 137 // This is the count of data elements (rather than total nodes in the tree)
135 size_t num_data_elements_; 138 size_t num_data_elements_;
136 Branch root_; 139 Branch root_;
137 std::vector<Node> nodes_; 140 std::vector<Node> nodes_;
138 141
139 DISALLOW_COPY_AND_ASSIGN(RTree); 142 DISALLOW_COPY_AND_ASSIGN(RTree);
140 }; 143 };
141 144
142 } // namespace cc 145 } // namespace cc
143 146
144 #endif // CC_BASE_RTREE_H_ 147 #endif // CC_BASE_RTREE_H_
OLDNEW
« no previous file with comments | « AUTHORS ('k') | cc/base/rtree.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698