Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
245763002:
Adds an RTree data structure to gfx/geometry (Closed)
|
Created:
6 years, 8 months ago by luken Modified:
6 years, 7 months ago CC:
chromium-reviews Base URL:
https://chromium.googlesource.com/chromium/src.git@master Visibility:
Public. |
DescriptionAdds an RTree data structure to gfx/geometry
This code forked originally from code review 218843002.
This patch introduces an implementation of a classical spatial database,
the R*-Tree. This allows for efficient rectangle queries of void* keys
associated with bounded boxes.
BUG=353867
Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=267265
Patch Set 1 #Patch Set 2 : now actually includes the RTree code ;) #Patch Set 3 : adds OWNERS change #
Total comments: 80
Patch Set 4 : changes from view CL #Patch Set 5 : [WIP] checkpointing work from piman's feedback #Patch Set 6 : [WIP] move to whitebox testing #Patch Set 7 : [WIP] back to home machine #Patch Set 8 : [WIP] weekend work #Patch Set 9 : ready for review, thanks #
Total comments: 10
Patch Set 10 : responding to piman early feedback, thanks #
Total comments: 13
Patch Set 11 : responding to pimans feedback, thanks #Patch Set 12 : fixing some clang trybots #
Messages
Total messages: 18 (0 generated)
Thanks
https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.cc File ui/gfx/geometry/r_tree.cc (right): https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:87: size_t number_to_remove, std::list<Node*>* nodes) { Why not std::vector<Node*>? You know the size ahead of time, so you can even reserve() the vector. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:113: size_t RTree::Node::RemoveChild(Node* child_node, std::list<Node*>* orphans) { std::vector here too? You also know the size. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:121: } It seems like we could simply walk the list of children, can't we? It would alleviate some of the overhead of calling a function for each child, and factor some of the processing (e.g. updating child_node's count_). https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:133: first_child->RemoveFromList(); Do we need to --count_ ? https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:168: if (!candidate_node->level_) { This is a loop constant (given checks above). Can we optimize a bit by breaking down into smaller functions, and move the check out of the loop? https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:171: expanded_rect.Union(node->rect_); If node->rect_ is fully contained in candidate_node->rect_, then you found the best candidate, which lets you avoid the O(n) inner loop, and (on average) half of the outer loop. Because of the hierarchical bounding boxes, this seems like a fairly common case, is it worth specializing? https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:186: total_original_overlap += overlap_rect.width() * overlap_rect.height(); nit: overlap_rect.size().GetArea() (other places too). https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:188: expanded_overlap_rect.Intersect(overlap_node->value()->rect_); overlap_node->rect_? https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:196: best_candidate = candidate_node->value(); no ->value() https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:198: least_area_change = AreaChangeToAdd(candidate_node->rect_, node->rect_); AreaChangeToAdd computes the union bounds, that we already computed on line 170. Can we just compute expanded_rect.size().GetArea()-candidate_node->rect_.size().GetArea() ? https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:198: least_area_change = AreaChangeToAdd(candidate_node->rect_, node->rect_); you probably want a continue here. the rest of the loop will trigger (because at this point least_overlap_increase == overlap_increasem and candidate_area_change == least_area_change), leading to more computations that can only cause best_candidate = candidate_node, which is already the case. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:205: overlap_increase == least_overlap_increase) { This is always true if candidate_node->level_ > 0 (because in that case, both overlap_increase and least_overlap_increase are std::numeric_limits<int>::max()). So maybe you can skip that test and/or factor the candidate_node->level_ > 0 case out of the loop (see above). https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:207: AreaChangeToAdd(candidate_node->rect_, node->rect_); You already computed expanded_rect in the (candidate_node->level_ == 0) case, so you might as well move that computation out of the if test and reuse it here. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:392: bool RTree::Node::Validate(size_t min_children, size_t max_children) const { You can never return anything but true (by induction). Make it a void? Alternatively, replace the DCHECKs by returning false. It'd be nice to test things in release too. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:447: int RTree::Node::AreaChangeToAdd(const Rect& bounds, const Rect& rect) { nit: might as well make it a free function (in anonymous namespace) since it doesn't need to access Node's internals. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:466: return a->rect_.bottom() < b->rect_.bottom(); test height() instead of bottom(), since the latter involves an extra addition. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:478: return a->rect_.right() < b->rect_.right(); test width() instead of right(). https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:502: int p_center_y = p->rect_.y() + (p->rect_.height() / 2); nit: it would be more readable to make a free inline function Point CenterOfRect(const Rect& rect), then have Point p_center = CenterOfRect(p->rect_); Point a_center = CenterOfRect(a->rect_); Point b_center = CenterOfRect(b->rect_); and then return (a_center-p_center).LengthSquared() > (b_center-p_center).LengthSquared(); https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:582: return; That goes contrary to the tests below. Either remove this test or remove the ones below, though the later means Insert(empty_rect, key) where key as already in the tree would not update the existing rect (which seems wrong?) Please add a test case for this. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:622: root_ = new Node(0); Should we just do this in the constructor, and save the test here? I don't think there's much to save memory-wise by having this lazily constructed, but you'll pay the cost on every node, every time you rebuild the tree (and remove, and queries, etc.). https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:718: if (needs_bounds_recomputed) { In which case can this be NULL? https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:719: needs_bounds_recomputed->RecomputeBounds(); If we have reinserts, we'll recompute bounds for part of the tree multiple times (at least once more for each later insert). Is there a way to avoid this, e.g. keep track of nodes that changed, and recompute only once in the common ancestors of those nodes? There's a similar concern for Remove() https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:726: Insert((*it), highest_reinsert_level); nit: () superfluous https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:763: Insert((*it), &starting_level); nit: no need for extra () https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h File ui/gfx/geometry/r_tree.h (right): https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:45: void Query(const Rect& query_rect, std::set<void*>* matches_out) const; Why returning a set here? Is seems like returning a vector should be more efficient. At the very least, a hash_set should be strictly more efficient (since we don't care about ordering between keys). https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:64: Node(int level); nit: explicit https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:75: void Query(const Rect& query_rect, std::set<void*>* matches_out) const; hash_set? https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:116: Node* parent() const; nit: inline https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:121: int level() const; nit: inline https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:123: const Rect& rect() const; nit: inline https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:125: size_t count() const; nit: inline https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:131: void GetAllValues(std::set<void*>* matches_out) const; hash_set? https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:163: base::LinkedList<Node> children_; What's the tradeoff here vs a std::vector? We expect the structure to be fairy static, don't we? Shouldn't a std::vector be more efficient? https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:163: base::LinkedList<Node> children_; Also, it'd be nice to use the scoped types (ScopedVector? scoped_ptr? linked_ptr?) to not have to manage memory manually. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:182: void Insert(Node* node, int* highset_reinsert_level); nit: no overloading. InsertNode? https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:184: void Remove(Node* node); nit: no overloading. RemoveNode? https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:195: std::map<void*, Node*> record_map_; Why not using a hash_map here? it should be more efficient generally. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree_u... File ui/gfx/geometry/r_tree_unittest.cc (right): https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree_u... ui/gfx/geometry/r_tree_unittest.cc:11: namespace gfx { I think we want to add several tests around all the heuristics wrt choosing subtrees, or splitting nodes. It's pretty subtle logic... https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree_u... ui/gfx/geometry/r_tree_unittest.cc:30: EXPECT_EQ(c, reinterpret_cast<int>((*it))); nit: extra () around *it
PTAL https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.cc File ui/gfx/geometry/r_tree.cc (right): https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:87: size_t number_to_remove, std::list<Node*>* nodes) { On 2014/04/21 23:59:31, piman wrote: > Why not std::vector<Node*>? You know the size ahead of time, so you can even > reserve() the vector. Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:113: size_t RTree::Node::RemoveChild(Node* child_node, std::list<Node*>* orphans) { On 2014/04/21 23:59:31, piman wrote: > std::vector here too? You also know the size. Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:121: } On 2014/04/21 23:59:31, piman wrote: > It seems like we could simply walk the list of children, can't we? > It would alleviate some of the overhead of calling a function for each child, > and factor some of the processing (e.g. updating child_node's count_). Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:133: first_child->RemoveFromList(); On 2014/04/21 23:59:31, piman wrote: > Do we need to --count_ ? Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:168: if (!candidate_node->level_) { On 2014/04/21 23:59:31, piman wrote: > This is a loop constant (given checks above). Can we optimize a bit by breaking > down into smaller functions, and move the check out of the loop? So the algorithm calls for node selection using minimum overlap increase only on leaves, but asks that we break ties using the non-leaf node selection algorithm of minimum area change to add, breaking ties in that with least area. I broke the overlap increase out to a function, for better readability. Particularly given your observation that with hierarchical bounding boxes overlap increase is likely to be 0 frequently we need to continue to break leaf ties with the non-leaf code. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:171: expanded_rect.Union(node->rect_); On 2014/04/21 23:59:31, piman wrote: > If node->rect_ is fully contained in candidate_node->rect_, then you found the > best candidate, which lets you avoid the O(n) inner loop, and (on average) half > of the outer loop. Because of the hierarchical bounding boxes, this seems like a > fairly common case, is it worth specializing? Yes, good observation, done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:186: total_original_overlap += overlap_rect.width() * overlap_rect.height(); On 2014/04/21 23:59:31, piman wrote: > nit: overlap_rect.size().GetArea() > (other places too). Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:188: expanded_overlap_rect.Intersect(overlap_node->value()->rect_); On 2014/04/21 23:59:31, piman wrote: > overlap_node->rect_? Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:196: best_candidate = candidate_node->value(); On 2014/04/21 23:59:31, piman wrote: > no ->value() Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:198: least_area_change = AreaChangeToAdd(candidate_node->rect_, node->rect_); On 2014/04/21 23:59:31, piman wrote: > you probably want a continue here. > the rest of the loop will trigger (because at this point least_overlap_increase > == overlap_increasem and candidate_area_change == least_area_change), leading to > more computations that can only cause best_candidate = candidate_node, which is > already the case. I don't quite understand this. This code is not in the inner loop, is that what you were thinking we should continue out of? https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:198: least_area_change = AreaChangeToAdd(candidate_node->rect_, node->rect_); On 2014/04/21 23:59:31, piman wrote: > AreaChangeToAdd computes the union bounds, that we already computed on line 170. > Can we just compute > expanded_rect.size().GetArea()-candidate_node->rect_.size().GetArea() ? Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:205: overlap_increase == least_overlap_increase) { On 2014/04/21 23:59:31, piman wrote: > This is always true if candidate_node->level_ > 0 (because in that case, both > overlap_increase and least_overlap_increase are > std::numeric_limits<int>::max()). So maybe you can skip that test and/or factor > the candidate_node->level_ > 0 case out of the loop (see above). The candidadate_node->level_ == 0 case needs this code to resolve (frequent!) ties in overlap increase. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:207: AreaChangeToAdd(candidate_node->rect_, node->rect_); On 2014/04/21 23:59:31, piman wrote: > You already computed expanded_rect in the (candidate_node->level_ == 0) case, so > you might as well move that computation out of the if test and reuse it here. Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:392: bool RTree::Node::Validate(size_t min_children, size_t max_children) const { On 2014/04/21 23:59:31, piman wrote: > You can never return anything but true (by induction). Make it a void? > Alternatively, replace the DCHECKs by returning false. It'd be nice to test > things in release too. Yeah I didn't know that we run unit tests in release mode, which seems obvious that we would now that I think about it. Because I had to make RTreeTest a friend of this class I have moved the Validate() methods over to RTreeTest and refactored them to use the EXPECT_* testing macros. This seems a better fit. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:447: int RTree::Node::AreaChangeToAdd(const Rect& bounds, const Rect& rect) { On 2014/04/21 23:59:31, piman wrote: > nit: might as well make it a free function (in anonymous namespace) since it > doesn't need to access Node's internals. Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:466: return a->rect_.bottom() < b->rect_.bottom(); On 2014/04/21 23:59:31, piman wrote: > test height() instead of bottom(), since the latter involves an extra addition. Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:478: return a->rect_.right() < b->rect_.right(); On 2014/04/21 23:59:31, piman wrote: > test width() instead of right(). Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:502: int p_center_y = p->rect_.y() + (p->rect_.height() / 2); On 2014/04/21 23:59:31, piman wrote: > nit: it would be more readable to make a free inline function Point > CenterOfRect(const Rect& rect), then have > Point p_center = CenterOfRect(p->rect_); > Point a_center = CenterOfRect(a->rect_); > Point b_center = CenterOfRect(b->rect_); > > > and then return (a_center-p_center).LengthSquared() > > (b_center-p_center).LengthSquared(); Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:582: return; On 2014/04/21 23:59:31, piman wrote: > That goes contrary to the tests below. > Either remove this test or remove the ones below, though the later means > Insert(empty_rect, key) where key as already in the tree would not update the > existing rect (which seems wrong?) > > Please add a test case for this. yes, this one is a bug, good catch, removed. I added a test case, InsertEmptyRectReplacementRemovesKey https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:622: root_ = new Node(0); On 2014/04/21 23:59:31, piman wrote: > Should we just do this in the constructor, and save the test here? I don't think > there's much to save memory-wise by having this lazily constructed, but you'll > pay the cost on every node, every time you rebuild the tree (and remove, and > queries, etc.). Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:718: if (needs_bounds_recomputed) { On 2014/04/21 23:59:31, piman wrote: > In which case can this be NULL? Two I can think of: a) inserting direct child of the root without a split. b) any insert resulting in a split of the root (which, granted, could be handled as an else case to the above if on 710) https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:719: needs_bounds_recomputed->RecomputeBounds(); On 2014/04/21 23:59:31, piman wrote: > If we have reinserts, we'll recompute bounds for part of the tree multiple times > (at least once more for each later insert). Is there a way to avoid this, e.g. > keep track of nodes that changed, and recompute only once in the common > ancestors of those nodes? > > There's a similar concern for Remove() Insert() and Remove() as described in both the R-Tree and R*-Tree paper require that the entire tree have valid bounds as entry conditions to their algorithms. I see what you're saying, and it might be possible, but I am worried it would complicate what is already an arguably overcomplicated system. Or am I misunderstanding your feedback here? https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:726: Insert((*it), highest_reinsert_level); On 2014/04/21 23:59:31, piman wrote: > nit: () superfluous Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.c... ui/gfx/geometry/r_tree.cc:763: Insert((*it), &starting_level); On 2014/04/21 23:59:31, piman wrote: > nit: no need for extra () Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h File ui/gfx/geometry/r_tree.h (right): https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:45: void Query(const Rect& query_rect, std::set<void*>* matches_out) const; On 2014/04/21 23:59:31, piman wrote: > Why returning a set here? > Is seems like returning a vector should be more efficient. At the very least, a > hash_set should be strictly more efficient (since we don't care about ordering > between keys). The hashing containers need to be able to hash their key, and complain when given a void*. There's even a comment at the top of base::hash_table to that effect. I want something with better than linear membership query, so a std::set seemed the best compromise. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:64: Node(int level); On 2014/04/21 23:59:31, piman wrote: > nit: explicit Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:75: void Query(const Rect& query_rect, std::set<void*>* matches_out) const; On 2014/04/21 23:59:31, piman wrote: > hash_set? Not on void*. See above. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:116: Node* parent() const; On 2014/04/21 23:59:31, piman wrote: > nit: inline Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:121: int level() const; On 2014/04/21 23:59:31, piman wrote: > nit: inline Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:123: const Rect& rect() const; On 2014/04/21 23:59:31, piman wrote: > nit: inline Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:125: size_t count() const; On 2014/04/21 23:59:31, piman wrote: > nit: inline Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:131: void GetAllValues(std::set<void*>* matches_out) const; On 2014/04/21 23:59:31, piman wrote: > hash_set? Not on void*. See above. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:163: base::LinkedList<Node> children_; On 2014/04/21 23:59:31, piman wrote: > What's the tradeoff here vs a std::vector? We expect the structure to be fairy > static, don't we? Shouldn't a std::vector be more efficient? Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:163: base::LinkedList<Node> children_; On 2014/04/21 23:59:31, piman wrote: > Also, it'd be nice to use the scoped types (ScopedVector? scoped_ptr? > linked_ptr?) to not have to manage memory manually. Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:182: void Insert(Node* node, int* highset_reinsert_level); On 2014/04/21 23:59:31, piman wrote: > nit: no overloading. InsertNode? Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:184: void Remove(Node* node); On 2014/04/21 23:59:31, piman wrote: > nit: no overloading. RemoveNode? Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:195: std::map<void*, Node*> record_map_; On 2014/04/21 23:59:31, piman wrote: > Why not using a hash_map here? it should be more efficient generally. Because I don't know a good way to hash void*. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree_u... File ui/gfx/geometry/r_tree_unittest.cc (right): https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree_u... ui/gfx/geometry/r_tree_unittest.cc:11: namespace gfx { On 2014/04/21 23:59:31, piman wrote: > I think we want to add several tests around all the heuristics wrt choosing > subtrees, or splitting nodes. > It's pretty subtle logic... Done. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree_u... ui/gfx/geometry/r_tree_unittest.cc:30: EXPECT_EQ(c, reinterpret_cast<int>((*it))); On 2014/04/21 23:59:31, piman wrote: > nit: extra () around *it Done.
Early feedback, I still need to look at the tests. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h File ui/gfx/geometry/r_tree.h (right): https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:45: void Query(const Rect& query_rect, std::set<void*>* matches_out) const; On 2014/04/28 01:33:34, luken wrote: > On 2014/04/21 23:59:31, piman wrote: > > Why returning a set here? > > Is seems like returning a vector should be more efficient. At the very least, > a > > hash_set should be strictly more efficient (since we don't care about ordering > > between keys). > The hashing containers need to be able to hash their key, and complain when > given a void*. There's even a comment at the top of base::hash_table to that > effect. I want something with better than linear membership query, so a std::set > seemed the best compromise. hash_set gives you O(1) (much better than linear). You just have to add a hash function (cast to intptr_t, use the int hash function). Or, you could use intptr_t as the key since you don't actually care about it being a pointer. https://codereview.chromium.org/245763002/diff/150001/ui/gfx/geometry/r_tree.cc File ui/gfx/geometry/r_tree.cc (right): https://codereview.chromium.org/245763002/diff/150001/ui/gfx/geometry/r_tree.... ui/gfx/geometry/r_tree.cc:83: std::vector<Node*>* nodes) { nit: it'd be good to return nodes in a ScopedVector as well, to indicate that ownership is transferred. https://codereview.chromium.org/245763002/diff/150001/ui/gfx/geometry/r_tree.... ui/gfx/geometry/r_tree.cc:99: size_t RTree::Node::RemoveChild(Node* child_node, std::vector<Node*>* orphans) { Same here wrt ScopedVector https://codereview.chromium.org/245763002/diff/150001/ui/gfx/geometry/r_tree.... ui/gfx/geometry/r_tree.cc:126: RTree::Node* RTree::Node::RemoveAndReturnLastChild() { return scoped_ptr https://codereview.chromium.org/245763002/diff/150001/ui/gfx/geometry/r_tree.... ui/gfx/geometry/r_tree.cc:199: Node* tied_node = NULL; nit: this could just be a bool. https://codereview.chromium.org/245763002/diff/150001/ui/gfx/geometry/r_tree.... ui/gfx/geometry/r_tree.cc:204: expanded_rect.Union(node->rect_); I would really like if we didn't do redundant computations... that was sort of my feedback on the previous PS. In this case, we computed all these expanded rects for all the children in LeastAreaEnlargement. We threw it out at the end of the function, and recompute it here. I guess that's the side effect of breaking the loop into 2 functions. Can we save that computation so that we can reuse it?
Thanks for continuing to look at this. https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h File ui/gfx/geometry/r_tree.h (right): https://codereview.chromium.org/245763002/diff/40001/ui/gfx/geometry/r_tree.h... ui/gfx/geometry/r_tree.h:45: void Query(const Rect& query_rect, std::set<void*>* matches_out) const; On 2014/04/28 18:24:28, piman wrote: > On 2014/04/28 01:33:34, luken wrote: > > On 2014/04/21 23:59:31, piman wrote: > > > Why returning a set here? > > > Is seems like returning a vector should be more efficient. At the very > least, > > a > > > hash_set should be strictly more efficient (since we don't care about > ordering > > > between keys). > > The hashing containers need to be able to hash their key, and complain when > > given a void*. There's even a comment at the top of base::hash_table to that > > effect. I want something with better than linear membership query, so a > std::set > > seemed the best compromise. > > hash_set gives you O(1) (much better than linear). > > You just have to add a hash function (cast to intptr_t, use the int hash > function). > Or, you could use intptr_t as the key since you don't actually care about it > being a pointer. Done. https://codereview.chromium.org/245763002/diff/150001/ui/gfx/geometry/r_tree.cc File ui/gfx/geometry/r_tree.cc (right): https://codereview.chromium.org/245763002/diff/150001/ui/gfx/geometry/r_tree.... ui/gfx/geometry/r_tree.cc:83: std::vector<Node*>* nodes) { On 2014/04/28 18:24:28, piman wrote: > nit: it'd be good to return nodes in a ScopedVector as well, to indicate that > ownership is transferred. Done. https://codereview.chromium.org/245763002/diff/150001/ui/gfx/geometry/r_tree.... ui/gfx/geometry/r_tree.cc:99: size_t RTree::Node::RemoveChild(Node* child_node, std::vector<Node*>* orphans) { On 2014/04/28 18:24:28, piman wrote: > Same here wrt ScopedVector Done. https://codereview.chromium.org/245763002/diff/150001/ui/gfx/geometry/r_tree.... ui/gfx/geometry/r_tree.cc:126: RTree::Node* RTree::Node::RemoveAndReturnLastChild() { On 2014/04/28 18:24:28, piman wrote: > return scoped_ptr Done. https://codereview.chromium.org/245763002/diff/150001/ui/gfx/geometry/r_tree.... ui/gfx/geometry/r_tree.cc:199: Node* tied_node = NULL; On 2014/04/28 18:24:28, piman wrote: > nit: this could just be a bool. Done. https://codereview.chromium.org/245763002/diff/150001/ui/gfx/geometry/r_tree.... ui/gfx/geometry/r_tree.cc:204: expanded_rect.Union(node->rect_); On 2014/04/28 18:24:28, piman wrote: > I would really like if we didn't do redundant computations... that was sort of > my feedback on the previous PS. > > In this case, we computed all these expanded rects for all the children in > LeastAreaEnlargement. We threw it out at the end of the function, and recompute > it here. I guess that's the side effect of breaking the loop into 2 functions. > > Can we save that computation so that we can reuse it? Done.
LGTM+nits https://codereview.chromium.org/245763002/diff/170001/ui/gfx/geometry/r_tree_... File ui/gfx/geometry/r_tree_unittest.cc (right): https://codereview.chromium.org/245763002/diff/170001/ui/gfx/geometry/r_tree_... ui/gfx/geometry/r_tree_unittest.cc:69: Rect check_bounds(0, 0, 0, 0); nit: Rect check_bounds; works https://codereview.chromium.org/245763002/diff/170001/ui/gfx/geometry/r_tree_... ui/gfx/geometry/r_tree_unittest.cc:128: rt.Insert(Rect(0, 0, 100, 100), static_cast<intptr_t>(1)); nit: static_cast superfluous (here and many places below) https://codereview.chromium.org/245763002/diff/170001/ui/gfx/geometry/r_tree_... ui/gfx/geometry/r_tree_unittest.cc:162: EXPECT_TRUE(*results.begin() == static_cast<intptr_t>(1)); nit: or EXPECT_EQ(results.count(1), 1U); https://codereview.chromium.org/245763002/diff/170001/ui/gfx/geometry/r_tree_... ui/gfx/geometry/r_tree_unittest.cc:298: rt.Insert(Rect(0, 0, 0, 0), static_cast<intptr_t>(50)); nit: Rect() https://codereview.chromium.org/245763002/diff/170001/ui/gfx/geometry/r_tree_... ui/gfx/geometry/r_tree_unittest.cc:332: EXPECT_TRUE(removals[0]->key() == static_cast<intptr_t>(10)); nit: EXPECT_EQ, and you can use 10U instead of the static_cast. https://codereview.chromium.org/245763002/diff/170001/ui/gfx/geometry/r_tree_... ui/gfx/geometry/r_tree_unittest.cc:347: EXPECT_TRUE(removals[0]->key() != removals[1]->key()); nit: you could sort, and EXPECT_EQ that first one is 9U and second one is 11U.
Thanks so much, your feedback really made this CL much better! https://codereview.chromium.org/245763002/diff/170001/ui/gfx/geometry/r_tree_... File ui/gfx/geometry/r_tree_unittest.cc (right): https://codereview.chromium.org/245763002/diff/170001/ui/gfx/geometry/r_tree_... ui/gfx/geometry/r_tree_unittest.cc:69: Rect check_bounds(0, 0, 0, 0); On 2014/04/29 22:43:06, piman wrote: > nit: Rect check_bounds; works Done. https://codereview.chromium.org/245763002/diff/170001/ui/gfx/geometry/r_tree_... ui/gfx/geometry/r_tree_unittest.cc:128: rt.Insert(Rect(0, 0, 100, 100), static_cast<intptr_t>(1)); On 2014/04/29 22:43:06, piman wrote: > nit: static_cast superfluous (here and many places below) Done. https://codereview.chromium.org/245763002/diff/170001/ui/gfx/geometry/r_tree_... ui/gfx/geometry/r_tree_unittest.cc:162: EXPECT_TRUE(*results.begin() == static_cast<intptr_t>(1)); On 2014/04/29 22:43:06, piman wrote: > nit: or EXPECT_EQ(results.count(1), 1U); Done. https://codereview.chromium.org/245763002/diff/170001/ui/gfx/geometry/r_tree_... ui/gfx/geometry/r_tree_unittest.cc:298: rt.Insert(Rect(0, 0, 0, 0), static_cast<intptr_t>(50)); On 2014/04/29 22:43:06, piman wrote: > nit: Rect() Done. https://codereview.chromium.org/245763002/diff/170001/ui/gfx/geometry/r_tree_... ui/gfx/geometry/r_tree_unittest.cc:332: EXPECT_TRUE(removals[0]->key() == static_cast<intptr_t>(10)); On 2014/04/29 22:43:06, piman wrote: > nit: EXPECT_EQ, and you can use 10U instead of the static_cast. Done. https://codereview.chromium.org/245763002/diff/170001/ui/gfx/geometry/r_tree_... ui/gfx/geometry/r_tree_unittest.cc:347: EXPECT_TRUE(removals[0]->key() != removals[1]->key()); On 2014/04/29 22:43:06, piman wrote: > nit: you could sort, and EXPECT_EQ that first one is 9U and second one is 11U. I made a base::hash_set of the result keys, and EXPECT_EQ that count(9) and count(11) are both 1U. Does that work for you?
lgtm https://codereview.chromium.org/245763002/diff/170001/ui/gfx/geometry/r_tree_... File ui/gfx/geometry/r_tree_unittest.cc (right): https://codereview.chromium.org/245763002/diff/170001/ui/gfx/geometry/r_tree_... ui/gfx/geometry/r_tree_unittest.cc:347: EXPECT_TRUE(removals[0]->key() != removals[1]->key()); On 2014/04/29 23:22:47, luken wrote: > On 2014/04/29 22:43:06, piman wrote: > > nit: you could sort, and EXPECT_EQ that first one is 9U and second one is 11U. > > I made a base::hash_set of the result keys, and EXPECT_EQ that count(9) and > count(11) are both 1U. Does that work for you? Sure, that's fine too.
The CQ bit was checked by cpu@chromium.org
CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/luken@chromium.org/245763002/200001
The CQ bit was unchecked by commit-bot@chromium.org
Try jobs failed on following builders: chromium_presubmit on tryserver.chromium
lgtm (since I am now owner of r_tree I have to lgtm my own CL)
lgtm
Rubber stamp LGTM
The CQ bit was checked by cpu@chromium.org
CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/luken@chromium.org/245763002/200001
Message was sent while issue was closed.
Change committed as 267265 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
