Issue 6489055: Add R-Tree data structure. (Closed)
|
Created:
11 years, 10 months ago by rileya Modified:
11 years, 10 months ago CC:
skia-review_googlegroups.com Base URL:
http://skia.googlecode.com/svn/trunk/ Visibility:
Public. |
DescriptionAdd R-Tree data structure.
Committed: https://code.google.com/p/skia/source/detail?r=5401
Patch Set 1 #
Total comments: 27
Patch Set 2 : Add comments, style cleanup. #Patch Set 3 : Remove templated 'T' replace with void ptr, fix bug in bulk load. #Patch Set 4 : No more templates. #Patch Set 5 : Add SkRTree.cpp. #
Total comments: 6
Patch Set 6 : #
Total comments: 2
Patch Set 7 : Various fixes, added comments to BBoxHierarchy, etc. #
Total comments: 4
Patch Set 8 : Add explanation for min/max children, and fix unit test. #Patch Set 9 : One more tweak to the unit test. #Patch Set 10 : Wrap comment. #Patch Set 11 : Fix bug when bulk loading single branch. #
MessagesTotal messages: 20
Sorry about the gigantic CL, but I don't think this can really be broken up too well... This doesn't include anything specific to the Picture stuff, this is just the R-Tree.
Sign in to reply to this message.
On 2012/08/29 21:13:03, rileya wrote: > Sorry about the gigantic CL, but I don't think this can really be broken up too > well... > > This doesn't include anything specific to the Picture stuff, this is just the > R-Tree. I'm not sure this CL adds enough code. So should we also add a bench that throws random rects at the tree? I can imagine we might even want multiple benches that exercise extreme cases: 1. every rect is a subrect of or encloses the previous 2. all rects are tiny/large relative to the overall bounds 3. ... Maybe not all/any of these would be hard cases for the current implementation but it would give us some way of measuring trade-offs for alternate tree-building algs.
Sign in to reply to this message.
does every stitch of code need to be templated? that's a lot of duplication if we ever use this in more than on place.
Sign in to reply to this message.
LGTM + questions & comment suggestions http://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h File src/core/SkRTree.h (right): http://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode197 src/core/SkRTree.h:197: Comment? // Recursively descend the tree to find the final resting spot of 'branch'. Update the bounding boxes on the way up. http://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode245 src/core/SkRTree.h:245: // root's child pointers do not point to leaves, so minimize area increase Don't we have these defined somewhere? http://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode273 src/core/SkRTree.h:273: if (j == i) continue; expand on the "old overlap?" comment? http://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode314 src/core/SkRTree.h:314: // We want choose an axis to split on, then a distribution along that axis; we'll need want _to_ http://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode495 src/core/SkRTree.h:495: Add check that node bounding box includes all children? http://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode532 src/core/SkRTree.h:532: comment here? http://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode547 src/core/SkRTree.h:547: // expand 'out' to include 'joinWith' http://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode550 src/core/SkRTree.h:550: // and we can save the empty check that SkIRect::join requires Add {}s http://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp File tests/RTreeTest.cpp (right): http://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp#newcode81 tests/RTreeTest.cpp:81: test getCount in here? getDepth?
Sign in to reply to this message.
https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h File src/core/SkRTree.h (right): https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode17 src/core/SkRTree.h:17: static inline uint32_t getArea(const SkIRect& rect); i_find_it_easier_to_read_file_local_non_member_functions_named_like_this_because_it_makes_it_more_obvious_that_they_arent_just_missing_a_this_arrow(); https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode242 src/core/SkRTree.h:242: int chooseSubtree(Node* root, Branch* branch) { I don't think it is necessary for this change, but we could consider making this an installable function pointer to play with different metrics (and compare trees w/out recompiling). https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode245 src/core/SkRTree.h:245: // root's child pointers do not point to leaves, so minimize area increase On 2012/08/30 13:25:34, robertphillips wrote: > Don't we have these defined somewhere? We could retype them as int32_t and use INT32_MAX https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode388 src/core/SkRTree.h:388: static bool rectLessX(int&, const Branch lhs, const Branch rhs) { Do these need to be part of the class at all? Also static members AreNamedWithAnInitialCap()
Sign in to reply to this message.
https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp File tests/RTreeTest.cpp (right): https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp#newcode57 tests/RTreeTest.cpp:57: return false; I think this might be clearer w/o the else. The test is then clearly a skip of the array comparison.
Sign in to reply to this message.
@Mike on templating: As we discussed, I can change the T to a void*, T really shouldn't be bigger than a pointer anyways and that would get rid of some templating. Min/max children are convenient as template params, since we can have fixed size arrays in the nodes. @Brian On benches: I have bench tests that I can add as a new CL, though I'm finding that there are a huge number of variables, and I'm ending up with tons of variations (testing tree construction and query performance, bulk-loaded vs immediate insertions, for 4 or 5 different types of rectangle distributions, with several different types of queries, etc, all the permutations end up being a ton of tests...). https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h File src/core/SkRTree.h (right): https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode17 src/core/SkRTree.h:17: static inline uint32_t getArea(const SkIRect& rect); On 2012/08/30 13:48:04, bsalomon wrote: > i_find_it_easier_to_read_file_local_non_member_functions_named_like_this_because_it_makes_it_more_obvious_that_they_arent_just_missing_a_this_arrow(); Fixed. https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode197 src/core/SkRTree.h:197: On 2012/08/30 13:25:34, robertphillips wrote: > Comment? // Recursively descend the tree to find the final resting spot of > 'branch'. Update the bounding boxes on the way up. Added. https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode245 src/core/SkRTree.h:245: // root's child pointers do not point to leaves, so minimize area increase On 2012/08/30 13:48:04, bsalomon wrote: > On 2012/08/30 13:25:34, robertphillips wrote: > > Don't we have these defined somewhere? > > We could retype them as int32_t and use INT32_MAX I may have been a little too aggressive with the int->int32_t replaces, but done. https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode273 src/core/SkRTree.h:273: if (j == i) continue; On 2012/08/30 13:25:34, robertphillips wrote: > expand on the "old overlap?" comment? Done. https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode314 src/core/SkRTree.h:314: // We want choose an axis to split on, then a distribution along that axis; we'll need On 2012/08/30 13:25:34, robertphillips wrote: > want _to_ Fixed. https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode388 src/core/SkRTree.h:388: static bool rectLessX(int&, const Branch lhs, const Branch rhs) { On 2012/08/30 13:48:04, bsalomon wrote: > Do these need to be part of the class at all? Also static members > AreNamedWithAnInitialCap() Because it takes Branches as params, which are inner structs of the RTree, it avoids some ugly template soup in the function headers. But I can change it if that is preferable. https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode495 src/core/SkRTree.h:495: On 2012/08/30 13:25:34, robertphillips wrote: > Add check that node bounding box includes all children? Good call, added. https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode532 src/core/SkRTree.h:532: On 2012/08/30 13:25:34, robertphillips wrote: > comment here? Added. https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode547 src/core/SkRTree.h:547: On 2012/08/30 13:25:34, robertphillips wrote: > // expand 'out' to include 'joinWith' Added. https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode550 src/core/SkRTree.h:550: // and we can save the empty check that SkIRect::join requires On 2012/08/30 13:25:34, robertphillips wrote: > Add {}s Done. https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp File tests/RTreeTest.cpp (right): https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp#newcode57 tests/RTreeTest.cpp:57: return false; On 2012/08/30 13:53:03, robertphillips wrote: > I think this might be clearer w/o the else. The test is then clearly a skip of > the array comparison. Done. https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp#newcode81 tests/RTreeTest.cpp:81: On 2012/08/30 13:25:34, robertphillips wrote: > test getCount in here? getDepth? Since the tree depth is variable depending on the rects/order of insertion/etc I don't see a way of checking that, but I added a check for count.
Sign in to reply to this message.
On 2012/08/30 14:42:28, rileya wrote:
> @Mike on templating: As we discussed, I can change the T to a void*, T really
> shouldn't be bigger than a pointer anyways and that would get rid of some
> templating. Min/max children are convenient as template params, since we can
> have fixed size arrays in the nodes.
pseudo-C:
struct Node {
bool isLeaf() { return 0 == fLevel; }
bool isFull() { return fNumChildren == MAX_CHILDREN; }
uint16_t fNumChildren;
uint16_t fLevel;
Branch* child(int i) {
STATIC_ASSERT(this = 2 * sizeof(uint16_t);
return (Branch*)((char*)this + 2 * sizeof(uint16_t) + i * sizeof(Branch));
}
};
size_t NodeSize = sizeof(Node + fMaxBranch * sizeof(Branch));
Node* newNode = (Node*) chunky_malloc_allocate(NodeSize);
>
> @Brian On benches: I have bench tests that I can add as a new CL, though I'm
> finding that there are a huge number of variables, and I'm ending up with tons
> of variations (testing tree construction and query performance, bulk-loaded vs
> immediate insertions, for 4 or 5 different types of rectangle distributions,
> with several different types of queries, etc, all the permutations end up
being
> a ton of tests...).
Maybe just stick with one rectangle distro for now? Agree on adding as a
separate CL.
>
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h
> File src/core/SkRTree.h (right):
>
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode17
> src/core/SkRTree.h:17: static inline uint32_t getArea(const SkIRect& rect);
> On 2012/08/30 13:48:04, bsalomon wrote:
> >
>
i_find_it_easier_to_read_file_local_non_member_functions_named_like_this_because_it_makes_it_more_obvious_that_they_arent_just_missing_a_this_arrow();
>
> Fixed.
>
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode197
> src/core/SkRTree.h:197:
> On 2012/08/30 13:25:34, robertphillips wrote:
> > Comment? // Recursively descend the tree to find the final resting spot of
> > 'branch'. Update the bounding boxes on the way up.
>
> Added.
>
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode245
> src/core/SkRTree.h:245: // root's child pointers do not point to leaves, so
> minimize area increase
> On 2012/08/30 13:48:04, bsalomon wrote:
> > On 2012/08/30 13:25:34, robertphillips wrote:
> > > Don't we have these defined somewhere?
> >
> > We could retype them as int32_t and use INT32_MAX
>
> I may have been a little too aggressive with the int->int32_t replaces, but
> done.
>
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode273
> src/core/SkRTree.h:273: if (j == i) continue;
> On 2012/08/30 13:25:34, robertphillips wrote:
> > expand on the "old overlap?" comment?
>
> Done.
>
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode314
> src/core/SkRTree.h:314: // We want choose an axis to split on, then a
> distribution along that axis; we'll need
> On 2012/08/30 13:25:34, robertphillips wrote:
> > want _to_
>
> Fixed.
>
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode388
> src/core/SkRTree.h:388: static bool rectLessX(int&, const Branch lhs, const
> Branch rhs) {
> On 2012/08/30 13:48:04, bsalomon wrote:
> > Do these need to be part of the class at all? Also static members
> > AreNamedWithAnInitialCap()
>
> Because it takes Branches as params, which are inner structs of the RTree, it
> avoids some ugly template soup in the function headers. But I can change it if
> that is preferable.
>
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode495
> src/core/SkRTree.h:495:
> On 2012/08/30 13:25:34, robertphillips wrote:
> > Add check that node bounding box includes all children?
>
> Good call, added.
>
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode532
> src/core/SkRTree.h:532:
> On 2012/08/30 13:25:34, robertphillips wrote:
> > comment here?
>
> Added.
>
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode547
> src/core/SkRTree.h:547:
> On 2012/08/30 13:25:34, robertphillips wrote:
> > // expand 'out' to include 'joinWith'
>
> Added.
>
> https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode550
> src/core/SkRTree.h:550: // and we can save the empty check that SkIRect::join
> requires
> On 2012/08/30 13:25:34, robertphillips wrote:
> > Add {}s
>
> Done.
>
> https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp
> File tests/RTreeTest.cpp (right):
>
> https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp#newcode57
> tests/RTreeTest.cpp:57: return false;
> On 2012/08/30 13:53:03, robertphillips wrote:
> > I think this might be clearer w/o the else. The test is then clearly a skip
of
> > the array comparison.
>
> Done.
>
> https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp#newcode81
> tests/RTreeTest.cpp:81:
> On 2012/08/30 13:25:34, robertphillips wrote:
> > test getCount in here? getDepth?
>
> Since the tree depth is variable depending on the rects/order of insertion/etc
I
> don't see a way of checking that, but I added a check for count.
Sign in to reply to this message.
On 2012/08/30 14:54:13, bsalomon wrote:
> On 2012/08/30 14:42:28, rileya wrote:
> > @Mike on templating: As we discussed, I can change the T to a void*, T
really
> > shouldn't be bigger than a pointer anyways and that would get rid of some
> > templating. Min/max children are convenient as template params, since we can
> > have fixed size arrays in the nodes.
>
> pseudo-C:
>
> struct Node {
> bool isLeaf() { return 0 == fLevel; }
> bool isFull() { return fNumChildren == MAX_CHILDREN; }
>
> uint16_t fNumChildren;
> uint16_t fLevel;
> Branch* child(int i) {
> STATIC_ASSERT(this = 2 * sizeof(uint16_t);
> return (Branch*)((char*)this + 2 * sizeof(uint16_t) + i * sizeof(Branch));
remove static assert, 2 * sizeof(uint16_t) -> sizeof(Node)
> }
> };
>
> size_t NodeSize = sizeof(Node + fMaxBranch * sizeof(Branch));
> Node* newNode = (Node*) chunky_malloc_allocate(NodeSize);
>
>
> >
> > @Brian On benches: I have bench tests that I can add as a new CL, though I'm
> > finding that there are a huge number of variables, and I'm ending up with
tons
> > of variations (testing tree construction and query performance, bulk-loaded
vs
> > immediate insertions, for 4 or 5 different types of rectangle distributions,
> > with several different types of queries, etc, all the permutations end up
> being
> > a ton of tests...).
>
> Maybe just stick with one rectangle distro for now? Agree on adding as a
> separate CL.
>
> >
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h
> > File src/core/SkRTree.h (right):
> >
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode17
> > src/core/SkRTree.h:17: static inline uint32_t getArea(const SkIRect& rect);
> > On 2012/08/30 13:48:04, bsalomon wrote:
> > >
> >
>
i_find_it_easier_to_read_file_local_non_member_functions_named_like_this_because_it_makes_it_more_obvious_that_they_arent_just_missing_a_this_arrow();
> >
> > Fixed.
> >
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode197
> > src/core/SkRTree.h:197:
> > On 2012/08/30 13:25:34, robertphillips wrote:
> > > Comment? // Recursively descend the tree to find the final resting spot of
> > > 'branch'. Update the bounding boxes on the way up.
> >
> > Added.
> >
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode245
> > src/core/SkRTree.h:245: // root's child pointers do not point to leaves, so
> > minimize area increase
> > On 2012/08/30 13:48:04, bsalomon wrote:
> > > On 2012/08/30 13:25:34, robertphillips wrote:
> > > > Don't we have these defined somewhere?
> > >
> > > We could retype them as int32_t and use INT32_MAX
> >
> > I may have been a little too aggressive with the int->int32_t replaces, but
> > done.
> >
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode273
> > src/core/SkRTree.h:273: if (j == i) continue;
> > On 2012/08/30 13:25:34, robertphillips wrote:
> > > expand on the "old overlap?" comment?
> >
> > Done.
> >
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode314
> > src/core/SkRTree.h:314: // We want choose an axis to split on, then a
> > distribution along that axis; we'll need
> > On 2012/08/30 13:25:34, robertphillips wrote:
> > > want _to_
> >
> > Fixed.
> >
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode388
> > src/core/SkRTree.h:388: static bool rectLessX(int&, const Branch lhs, const
> > Branch rhs) {
> > On 2012/08/30 13:48:04, bsalomon wrote:
> > > Do these need to be part of the class at all? Also static members
> > > AreNamedWithAnInitialCap()
> >
> > Because it takes Branches as params, which are inner structs of the RTree,
it
> > avoids some ugly template soup in the function headers. But I can change it
if
> > that is preferable.
> >
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode495
> > src/core/SkRTree.h:495:
> > On 2012/08/30 13:25:34, robertphillips wrote:
> > > Add check that node bounding box includes all children?
> >
> > Good call, added.
> >
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode532
> > src/core/SkRTree.h:532:
> > On 2012/08/30 13:25:34, robertphillips wrote:
> > > comment here?
> >
> > Added.
> >
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode547
> > src/core/SkRTree.h:547:
> > On 2012/08/30 13:25:34, robertphillips wrote:
> > > // expand 'out' to include 'joinWith'
> >
> > Added.
> >
> > https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode550
> > src/core/SkRTree.h:550: // and we can save the empty check that
SkIRect::join
> > requires
> > On 2012/08/30 13:25:34, robertphillips wrote:
> > > Add {}s
> >
> > Done.
> >
> > https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp
> > File tests/RTreeTest.cpp (right):
> >
> > https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp#newcode57
> > tests/RTreeTest.cpp:57: return false;
> > On 2012/08/30 13:53:03, robertphillips wrote:
> > > I think this might be clearer w/o the else. The test is then clearly a
skip
> of
> > > the array comparison.
> >
> > Done.
> >
> > https://codereview.appspot.com/6489055/diff/1/tests/RTreeTest.cpp#newcode81
> > tests/RTreeTest.cpp:81:
> > On 2012/08/30 13:25:34, robertphillips wrote:
> > > test getCount in here? getDepth?
> >
> > Since the tree depth is variable depending on the rects/order of
insertion/etc
> I
> > don't see a way of checking that, but I added a check for count.
Sign in to reply to this message.
https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h File src/core/SkRTree.h (right): https://codereview.appspot.com/6489055/diff/1/src/core/SkRTree.h#newcode388 src/core/SkRTree.h:388: static bool rectLessX(int&, const Branch lhs, const Branch rhs) { On 2012/08/30 14:42:28, rileya wrote: > On 2012/08/30 13:48:04, bsalomon wrote: > > Do these need to be part of the class at all? Also static members > > AreNamedWithAnInitialCap() > > Because it takes Branches as params, which are inner structs of the RTree, it > avoids some ugly template soup in the function headers. But I can change it if > that is preferable. Duh, right.
Sign in to reply to this message.
Un-templated it, and moved implementation to a source file.
Sign in to reply to this message.
I like much better now. 1. Can we see how this class gets used for (a) recording and (b) playback? Maybe post other CLs just for reference? 2. How much can be done to fission the API into a recording part and a playback part? i.e. how simple can we make the API look to just the recording-canvas? 3. If we wanted to experiment with different recording techniques, would we want a common baseclass for this guy, or different recording classes but a common playback class? https://codereview.appspot.com/6489055/diff/6003/src/core/SkRTree.h File src/core/SkRTree.h (right): https://codereview.appspot.com/6489055/diff/6003/src/core/SkRTree.h#newcode44 src/core/SkRTree.h:44: nit: parameters should almost never be smaller than an int. Also, is it useful for both values to have defaults? I can say new SkRTree(20); Which would be wacky, since 20 > 15. Default args are great, and they're terrible. Maybe SkRTree(); SkRTree(int min, int max); ?
Sign in to reply to this message.
https://codereview.appspot.com/6489055/diff/6003/src/core/SkRTree.h File src/core/SkRTree.h (right): https://codereview.appspot.com/6489055/diff/6003/src/core/SkRTree.h#newcode71 src/core/SkRTree.h:71: int getCount() const { return fCount; } Maybe a comment about whether this is a count of nodes or insertions https://codereview.appspot.com/6489055/diff/6003/src/core/SkRTree.h#newcode98 src/core/SkRTree.h:98: return reinterpret_cast<Branch*>(reinterpret_cast<char*>(this) + sizeof(Node) Could be shortened to: return reinterpret_cast<Branch*>(this + 1) + index;
Sign in to reply to this message.
Addressed a few more things, also added a base class for this (naming could probably be better: SkBBoxHierarchy), which should help with plugging in and testing alternate spatial data structures.
Sign in to reply to this message.
http://codereview.appspot.com/6489055/diff/6003/src/core/SkRTree.h File src/core/SkRTree.h (right): http://codereview.appspot.com/6489055/diff/6003/src/core/SkRTree.h#newcode44 src/core/SkRTree.h:44: On 2012/08/31 12:00:02, reed1 wrote: > nit: parameters should almost never be smaller than an int. > > Also, is it useful for both values to have defaults? I can say > > new SkRTree(20); > > Which would be wacky, since 20 > 15. > > Default args are great, and they're terrible. Maybe > > SkRTree(); > SkRTree(int min, int max); > ? I just removed the defaults altogether, and changed them to ints (also added some asserts in the constructor to check the min/max are valid). http://codereview.appspot.com/6489055/diff/6003/src/core/SkRTree.h#newcode71 src/core/SkRTree.h:71: int getCount() const { return fCount; } On 2012/08/31 15:51:57, bsalomon wrote: > Maybe a comment about whether this is a count of nodes or insertions Added. http://codereview.appspot.com/6489055/diff/6003/src/core/SkRTree.h#newcode98 src/core/SkRTree.h:98: return reinterpret_cast<Branch*>(reinterpret_cast<char*>(this) + sizeof(Node) On 2012/08/31 15:51:57, bsalomon wrote: > Could be shortened to: > > return reinterpret_cast<Branch*>(this + 1) + index; Good catch. Done.
Sign in to reply to this message.
https://codereview.appspot.com/6489055/diff/8/src/core/SkRTree.cpp File src/core/SkRTree.cpp (right): https://codereview.appspot.com/6489055/diff/8/src/core/SkRTree.cpp#newcode28 src/core/SkRTree.cpp:28: SkASSERT(minChildren > maxChildren && minChildren > 0); maxChildren > minChildren? SkRTree* SkRTree::Create()?
Sign in to reply to this message.
http://codereview.appspot.com/6489055/diff/8/src/core/SkRTree.cpp File src/core/SkRTree.cpp (right): http://codereview.appspot.com/6489055/diff/8/src/core/SkRTree.cpp#newcode28 src/core/SkRTree.cpp:28: SkASSERT(minChildren > maxChildren && minChildren > 0); On 2012/09/04 20:36:50, bsalomon wrote: > maxChildren > minChildren? > > SkRTree* SkRTree::Create()? Whoops, fixed. And added a static create function.
Sign in to reply to this message.
LGTM (with two minor nits) https://codereview.appspot.com/6489055/diff/1014/src/core/SkBBoxHierarchy.h File src/core/SkBBoxHierarchy.h (right): https://codereview.appspot.com/6489055/diff/1014/src/core/SkBBoxHierarchy.h#n... src/core/SkBBoxHierarchy.h:29: * structures than repeated inserts) until flushDeferredInserts is called or the first search. line wrap https://codereview.appspot.com/6489055/diff/1014/src/core/SkRTree.h File src/core/SkRTree.h (right): https://codereview.appspot.com/6489055/diff/1014/src/core/SkRTree.h#newcode46 src/core/SkRTree.h:46: static SkRTree* Create(int minChildren, int maxChildren); Can you document the restrictions on min and max?
Sign in to reply to this message.
Fixed the unit test, and addressed the nits. http://codereview.appspot.com/6489055/diff/1014/src/core/SkBBoxHierarchy.h File src/core/SkBBoxHierarchy.h (right): http://codereview.appspot.com/6489055/diff/1014/src/core/SkBBoxHierarchy.h#ne... src/core/SkBBoxHierarchy.h:29: * structures than repeated inserts) until flushDeferredInserts is called or the first search. On 2012/09/05 13:02:24, bsalomon wrote: > line wrap Fixed. http://codereview.appspot.com/6489055/diff/1014/src/core/SkRTree.h File src/core/SkRTree.h (right): http://codereview.appspot.com/6489055/diff/1014/src/core/SkRTree.h#newcode46 src/core/SkRTree.h:46: static SkRTree* Create(int minChildren, int maxChildren); On 2012/09/05 13:02:24, bsalomon wrote: > Can you document the restrictions on min and max? Done.
Sign in to reply to this message.
On 2012/09/05 13:38:26, rileya wrote: > Fixed the unit test, and addressed the nits. > > http://codereview.appspot.com/6489055/diff/1014/src/core/SkBBoxHierarchy.h > File src/core/SkBBoxHierarchy.h (right): > > http://codereview.appspot.com/6489055/diff/1014/src/core/SkBBoxHierarchy.h#ne... > src/core/SkBBoxHierarchy.h:29: * structures than repeated inserts) until > flushDeferredInserts is called or the first search. > On 2012/09/05 13:02:24, bsalomon wrote: > > line wrap > Fixed. > > http://codereview.appspot.com/6489055/diff/1014/src/core/SkRTree.h > File src/core/SkRTree.h (right): > > http://codereview.appspot.com/6489055/diff/1014/src/core/SkRTree.h#newcode46 > src/core/SkRTree.h:46: static SkRTree* Create(int minChildren, int maxChildren); > On 2012/09/05 13:02:24, bsalomon wrote: > > Can you document the restrictions on min and max? > Done. LGTM
Sign in to reply to this message.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
