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

Side by Side Diff: ui/gfx/geometry/r_tree.h

Issue 342723002: Repairs crash in RTreeBase::Node::LeastAreaEnlargement (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: crash fix and test added Created 6 years, 6 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 | « no previous file | ui/gfx/geometry/r_tree.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 2014 The Chromium Authors. All rights reserved. 1 // Copyright 2014 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 UI_GFX_GEOMETRY_R_TREE_H_ 5 // Defines a hierarchical bounding rectangle data structure for Rect objects,
6 #define UI_GFX_GEOMETRY_R_TREE_H_
7
8 #include <vector>
9
10 #include "base/containers/hash_tables.h"
11 #include "base/gtest_prod_util.h"
12 #include "base/macros.h"
13 #include "base/memory/scoped_ptr.h"
14 #include "base/memory/scoped_vector.h"
15 #include "ui/gfx/geometry/rect.h"
16 #include "ui/gfx/gfx_export.h"
17
18 namespace gfx {
19
20 // Defines a heirarchical bounding rectangle data structure for Rect objects,
21 // associated with a generic unique key K for efficient spatial queries. The 6 // associated with a generic unique key K for efficient spatial queries. The
22 // R*-tree algorithm is used to build the trees. Based on the papers: 7 // R*-tree algorithm is used to build the trees. Based on the papers:
23 // 8 //
24 // A Guttman 'R-trees: a dynamic index structure for spatial searching', Proc 9 // A Guttman 'R-trees: a dynamic index structure for spatial searching', Proc
25 // ACM SIGMOD Int Conf on Management of Data, 47-57, 1984 10 // ACM SIGMOD Int Conf on Management of Data, 47-57, 1984
26 // 11 //
27 // N Beckmann, H-P Kriegel, R Schneider, B Seeger 'The R*-tree: an efficient and 12 // N Beckmann, H-P Kriegel, R Schneider, B Seeger 'The R*-tree: an efficient and
28 // robust access method for points and rectangles', Proc ACM SIGMOD Int Conf on 13 // robust access method for points and rectangles', Proc ACM SIGMOD Int Conf on
29 // Management of Data, 322-331, 1990 14 // Management of Data, 322-331, 1990
30 class GFX_EXPORT RTree { 15
16 #ifndef UI_GFX_GEOMETRY_R_TREE_H_
17 #define UI_GFX_GEOMETRY_R_TREE_H_
18
19 #include "r_tree_base.h"
20
21 namespace gfx {
22
23 template <typename Key>
24 class RTree : public RTreeBase {
31 public: 25 public:
26 typedef base::hash_set<Key> Matches;
27
28 // RTrees organize pairs of keys and rectangles in a hierarchical bounding
29 // box structure. This allows for queries of the tree within logarithmic time.
30 // |min_children| and |max_children| allows for adjustment of the average size
31 // of the nodes within RTree, which adjusts the base of the logarithm in the
32 // algorithm runtime. Some parts of insertion and deletion are polynomial
33 // in the size of the individual node, so the trade-off with larger nodes is
34 // potentially faster queries but slower insertions and deletions. Generally
35 // it is worth considering how much overlap between rectangles of different
36 // keys will occur in the tree, and trying to set |max_children| as a
37 // reasonable upper bound to the number of overlapping rectangles expected.
38 // Then |min_children| can bet set to a quantity slightly less than half of
39 // that.
32 RTree(size_t min_children, size_t max_children); 40 RTree(size_t min_children, size_t max_children);
33 ~RTree(); 41 ~RTree();
34 42
35 // Insert a new rect into the tree, associated with provided key. Note that if 43 // Insert a new rect into the tree, associated with provided key. Note that if
36 // rect is empty, this rect will not actually be inserted. Duplicate keys 44 // |rect| is empty, the |key| will not actually be inserted. Duplicate keys
37 // overwrite old entries. 45 // overwrite old entries.
38 void Insert(const Rect& rect, intptr_t key); 46 void Insert(const Rect& rect, Key key);
39 47
40 // If present, remove the supplied key from the tree. 48 // If present, remove the supplied |key| from the tree.
41 void Remove(intptr_t key); 49 void Remove(Key key);
42 50
43 // Fills a supplied list matches_out with all keys having bounding rects 51 // Fills |matches_out| with all keys having bounding rects intersecting
44 // intersecting query_rect. 52 // |query_rect|.
45 void Query(const Rect& query_rect, 53 void AppendIntersectingRecords(const Rect& query_rect,
46 base::hash_set<intptr_t>* matches_out) const; 54 Matches* matches_out) const;
47 55
48 // Removes all objects from the tree.
49 void Clear(); 56 void Clear();
50 57
51 private: 58 private:
52 // Private data structure class for storing internal nodes or leaves with keys 59 friend class RTreeTest;
53 // of R-Trees. Note that "leaf" nodes can still have children, the children 60 friend class RTreeNodeTest;
54 // will all be Nodes with non-NULL record pointers. 61
55 class GFX_EXPORT Node { 62 class Record : public RecordBase {
56 public: 63 public:
57 // Level counts from -1 for "record" Nodes, that is Nodes that wrap key 64 Record(const Rect& rect, const Key& key);
58 // values, to 0 for leaf Nodes, that is Nodes that only have record 65 virtual ~Record();
59 // children, up to the root Node, which has level equal to the height of the 66 const Key& key() const { return key_; }
60 // tree.
61 explicit Node(int level);
62
63 // Builds a new record Node.
64 Node(const Rect& rect, intptr_t key);
65
66 virtual ~Node();
67
68 // Deletes all children and any attached record.
69 void Clear();
70
71 // Recursive call to build a list of rects that intersect the query_rect.
72 void Query(const Rect& query_rect,
73 base::hash_set<intptr_t>* matches_out) const;
74
75 // Recompute our bounds by taking the union of all children rects. Will then
76 // call RecomputeBounds() on our parent for recursive bounds recalculation
77 // up to the root.
78 void RecomputeBounds();
79
80 // Removes number_to_remove nodes from this Node, and appends them to the
81 // supplied list. Does not repair bounds upon completion.
82 void RemoveNodesForReinsert(size_t number_to_remove,
83 ScopedVector<Node>* nodes);
84
85 // Given a pointer to a child node within this Node, remove it from our
86 // list. If that child had any children, append them to the supplied orphan
87 // list. Returns the new count of this node after removal. Does not
88 // recompute bounds, as this node itself may be removed if it now has too
89 // few children.
90 size_t RemoveChild(Node* child_node, ScopedVector<Node>* orphans);
91
92 // Does what it says on the tin. Returns NULL if no children. Does not
93 // recompute bounds.
94 scoped_ptr<Node> RemoveAndReturnLastChild();
95
96 // Given a node, returns the best fit node for insertion of that node at
97 // the nodes level().
98 Node* ChooseSubtree(Node* node);
99
100 // Adds the provided node to this Node. Returns the new count of records
101 // stored in the Node. Will recompute the bounds of this node after
102 // addition.
103 size_t AddChild(Node* node);
104
105 // Returns a sibling to this Node with at least min_children and no greater
106 // than max_children of this Node's children assigned to it, and having the
107 // same parent. Bounds will be valid on both Nodes after this call.
108 Node* Split(size_t min_children, size_t max_children);
109
110 // For record nodes only, to support re-insert, allows setting the rect.
111 void SetRect(const Rect& rect);
112
113 // Returns a pointer to the parent of this Node, or NULL if no parent.
114 Node* parent() const { return parent_; }
115
116 // 0 level() would mean that this Node is a leaf. 1 would mean that this
117 // Node has children that are leaves. Calling level() on root_ returns the
118 // height of the tree - 1. A level of -1 means that this is a Record node.
119 int level() const { return level_; }
120
121 const Rect& rect() const { return rect_; }
122
123 size_t count() const { return children_.size(); }
124
125 intptr_t key() const { return key_; }
126 67
127 private: 68 private:
128 // Returns all records stored in this node and its children. 69 Key key_;
129 void GetAllValues(base::hash_set<intptr_t>* matches_out) const;
130 70
131 // Used for sorting Nodes along vertical and horizontal axes 71 DISALLOW_COPY_AND_ASSIGN(Record);
132 static bool CompareVertical(Node* a, Node* b);
133
134 static bool CompareHorizontal(Node* a, Node* b);
135
136 static bool CompareCenterDistanceFromParent(Node* a, Node* b);
137
138 // Returns the increase in overlap value, as defined in Beckmann et al as
139 // the sum of the areas of the intersection of each |children_| rectangle
140 // (excepting the candidate child) with the argument rectangle. The
141 // expanded_rect argument is computed as the union of the candidate child
142 // rect and the argument rect, and is included here to avoid recomputation.
143 // Here the candidate child is indicated by index in |children_|, and
144 // expanded_rect is the alread-computed union of candidate's rect and
145 // rect.
146 int OverlapIncreaseToAdd(const Rect& rect,
147 size_t candidate,
148 const Rect& expanded_rect);
149
150 // Bounds recomputation without calling parents to do the same.
151 void RecomputeBoundsNoParents();
152
153 // Split() helper methods.
154 //
155 // Given two vectors of Nodes sorted by vertical or horizontal bounds, this
156 // function populates two vectors of Rectangles in which the ith element is
157 // the Union of all bounding rectangles [0,i] in the associated sorted array
158 // of Nodes.
159 static void BuildLowBounds(const std::vector<Node*>& vertical_sort,
160 const std::vector<Node*>& horizontal_sort,
161 std::vector<Rect>* vertical_bounds,
162 std::vector<Rect>* horizontal_bounds);
163
164 // Given two vectors of Nodes sorted by vertical or horizontal bounds, this
165 // function populates two vectors of Rectangles in which the ith element is
166 // the Union of all bounding rectangles [i, count()) in the associated
167 // sorted array of Nodes.
168 static void BuildHighBounds(const std::vector<Node*>& vertical_sort,
169 const std::vector<Node*>& horizontal_sort,
170 std::vector<Rect>* vertical_bounds,
171 std::vector<Rect>* horizontal_bounds);
172
173 // Returns true if this is a vertical split, false if a horizontal one.
174 // Based on ChooseSplitAxis algorithm in Beckmann et al. Chooses the axis
175 // with the lowest sum of margin values of bounding boxes.
176 static bool ChooseSplitAxis(const std::vector<Rect>& low_vertical_bounds,
177 const std::vector<Rect>& high_vertical_bounds,
178 const std::vector<Rect>& low_horizontal_bounds,
179 const std::vector<Rect>& high_horizontal_bounds,
180 size_t min_children,
181 size_t max_children);
182
183 // Used by SplitNode to calculate optimal index of split, after determining
184 // along which axis to sort and split the children rectangles. Returns the
185 // index to the first element in the split children as sorted by the bounds
186 // vectors.
187 static size_t ChooseSplitIndex(size_t min_children,
188 size_t max_children,
189 const std::vector<Rect>& low_bounds,
190 const std::vector<Rect>& high_bounds);
191
192 // Takes our children_ and divides them into a new node, starting at index
193 // split_index in sorted_children.
194 Node* DivideChildren(const std::vector<Rect>& low_bounds,
195 const std::vector<Rect>& high_bounds,
196 const std::vector<Node*>& sorted_children,
197 size_t split_index);
198
199 // Returns a pointer to the child node that will result in the least overlap
200 // increase with the addition of node_rect, as defined in the Beckmann et al
201 // paper, or NULL if there's a tie found. Requires a precomputed vector of
202 // expanded rectangles where the ith rectangle in the vector is the union of
203 // |children_|[i] and node_rect.
204 Node* LeastOverlapIncrease(const Rect& node_rect,
205 const std::vector<Rect>& expanded_rects);
206
207 // Returns a pointer to the child node that will result in the least area
208 // enlargement if the argument node rectangle were to be added to that
209 // nodes' bounding box. Requires a precomputed vector of expanded rectangles
210 // where the ith rectangle in the vector is the union of |children_|[i] and
211 // node_rect.
212 Node* LeastAreaEnlargement(const Rect& node_rect,
213 const std::vector<Rect>& expanded_rects);
214
215 // This Node's bounding rectangle.
216 Rect rect_;
217
218 // The height of the node in the tree, counting from -1 at the record node
219 // to 0 at the leaf up to the root node which has level equal to the height
220 // of the tree.
221 int level_;
222
223 // Pointers to all of our children Nodes.
224 ScopedVector<Node> children_;
225
226 // A weak pointer to our parent Node in the RTree. The root node will have a
227 // NULL value for |parent_|.
228 Node* parent_;
229
230 // If this is a record Node, then |key_| will be non-NULL and will contain
231 // the key data. Otherwise, NULL.
232 intptr_t key_;
233
234 friend class RTreeTest;
235 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeBuildHighBounds);
236 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeBuildLowBounds);
237 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeChooseSplitAxisAndIndex);
238 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeChooseSubtree);
239 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareCenterDistanceFromParent);
240 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareHorizontal);
241 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareVertical);
242 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeDivideChildren);
243 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeLeastAreaEnlargement);
244 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeLeastOverlapIncrease);
245 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeOverlapIncreaseToAdd);
246 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveAndReturnLastChild);
247 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveChildNoOrphans);
248 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveChildOrphans);
249 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveNodesForReinsert);
250 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeSplit);
251
252 DISALLOW_COPY_AND_ASSIGN(Node);
253 }; 72 };
254 73
255 // Supports re-insertion of Nodes based on the strategies outlined in
256 // Beckmann et al.
257 void InsertNode(Node* node, int* highset_reinsert_level);
258
259 // Supports removal of nodes for tree without deletion.
260 void RemoveNode(Node* node);
261
262 // A pointer to the root node in the RTree.
263 scoped_ptr<Node> root_;
264
265 // The parameters used to define the shape of the RTree.
266 size_t min_children_;
267 size_t max_children_;
268
269 // A map of supplied keys to their Node representation within the RTree, for 74 // A map of supplied keys to their Node representation within the RTree, for
270 // efficient retrieval of keys without requiring a bounding rect. 75 // efficient retrieval of keys without requiring a bounding rect.
271 base::hash_map<intptr_t, Node*> record_map_; 76 typedef base::hash_map<Key, Record*> RecordMap;
272 77 RecordMap record_map_;
273 friend class RTreeTest;
274 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeBuildHighBounds);
275 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeBuildLowBounds);
276 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeChooseSplitAxisAndIndex);
277 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeChooseSubtree);
278 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareCenterDistanceFromParent);
279 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareHorizontal);
280 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareVertical);
281 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeDivideChildren);
282 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeLeastAreaEnlargement);
283 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeLeastOverlapIncrease);
284 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeOverlapIncreaseToAdd);
285 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveAndReturnLastChild);
286 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveChildNoOrphans);
287 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveChildOrphans);
288 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveNodesForReinsert);
289 FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeSplit);
290 78
291 DISALLOW_COPY_AND_ASSIGN(RTree); 79 DISALLOW_COPY_AND_ASSIGN(RTree);
292 }; 80 };
293 81
82 template <typename Key>
83 RTree<Key>::RTree(size_t min_children, size_t max_children)
84 : RTreeBase(min_children, max_children) {
85 }
86
87 template <typename Key>
88 RTree<Key>::~RTree() {
89 }
90
91 template <typename Key>
92 void RTree<Key>::Insert(const Rect& rect, Key key) {
93 scoped_ptr<NodeBase> record;
94 // Check if this key is already present in the tree.
95 typename RecordMap::iterator it(record_map_.find(key));
96
97 if (it != record_map_.end()) {
98 // We will re-use this node structure, regardless of re-insert or return.
99 Record* existing_record = it->second;
100 // If the new rect and the current rect are identical we can skip the rest
101 // of Insert() as nothing has changed.
102 if (existing_record->rect() == rect)
103 return;
104
105 // Remove the node from the tree in its current position.
106 record = RemoveNode(existing_record);
107
108 PruneRootIfNecessary();
109
110 // If we are replacing this key with an empty rectangle we just remove the
111 // old node from the list and return, thus preventing insertion of empty
112 // rectangles into our spatial database.
113 if (rect.IsEmpty()) {
114 record_map_.erase(it);
115 return;
116 }
117
118 // Reset the rectangle to the new value.
119 record->set_rect(rect);
120 } else {
121 if (rect.IsEmpty())
122 return;
123
124 record.reset(new Record(rect, key));
125 record_map_.insert(std::make_pair(key, static_cast<Record*>(record.get())));
126 }
127
128 int highest_reinsert_level = -1;
129 InsertNode(record.Pass(), &highest_reinsert_level);
130 }
131
132 template <typename Key>
133 void RTree<Key>::Clear() {
134 record_map_.clear();
135 ResetRoot();
136 }
137
138 template <typename Key>
139 void RTree<Key>::Remove(Key key) {
140 // Search the map for the leaf parent that has the provided record.
141 typename RecordMap::iterator it = record_map_.find(key);
142 if (it == record_map_.end())
143 return;
144
145 Record* record = it->second;
146 record_map_.erase(it);
147 RemoveNode(record);
148
149 // Lastly check the root. If it has only one non-leaf child, delete it and
150 // replace it with its child.
151 PruneRootIfNecessary();
152 }
153
154 template <typename Key>
155 void RTree<Key>::AppendIntersectingRecords(
156 const Rect& query_rect, Matches* matches_out) const {
157 RTreeBase::Records matching_records;
158 root()->AppendIntersectingRecords(query_rect, &matching_records);
159 for (RTreeBase::Records::const_iterator it = matching_records.begin();
160 it != matching_records.end();
161 ++it) {
162 const Record* record = static_cast<const Record*>(*it);
163 matches_out->insert(record->key());
164 }
165 }
166
167
168 // RTree::Record --------------------------------------------------------------
169
170 template <typename Key>
171 RTree<Key>::Record::Record(const Rect& rect, const Key& key)
172 : RecordBase(rect),
173 key_(key) {
174 }
175
176 template <typename Key>
177 RTree<Key>::Record::~Record() {
178 }
179
294 } // namespace gfx 180 } // namespace gfx
295 181
296 #endif // UI_GFX_GEOMETRY_R_TREE_H_ 182 #endif // UI_GFX_GEOMETRY_R_TREE_H_
OLDNEW
« no previous file with comments | « no previous file | ui/gfx/geometry/r_tree.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698