rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2012 Google Inc. |
| 3 | * |
| 4 | * Use of this source code is governed by a BSD-style license that can be |
| 5 | * found in the LICENSE file. |
| 6 | */ |
| 7 | |
| 8 | #include "Test.h" |
tfarina@chromium.org | e4fafb1 | 2013-12-12 21:11:12 +0000 | [diff] [blame] | 9 | #include "TestClassDef.h" |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 10 | #include "SkRandom.h" |
| 11 | #include "SkRTree.h" |
| 12 | #include "SkTSort.h" |
| 13 | |
| 14 | static const size_t MIN_CHILDREN = 6; |
| 15 | static const size_t MAX_CHILDREN = 11; |
| 16 | |
bsalomon@google.com | 373ebc6 | 2012-09-26 13:08:56 +0000 | [diff] [blame] | 17 | static const int NUM_RECTS = 200; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 18 | static const size_t NUM_ITERATIONS = 100; |
| 19 | static const size_t NUM_QUERIES = 50; |
| 20 | |
| 21 | struct DataRect { |
| 22 | SkIRect rect; |
| 23 | void* data; |
| 24 | }; |
| 25 | |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 26 | static SkIRect random_rect(SkRandom& rand) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 27 | SkIRect rect = {0,0,0,0}; |
| 28 | while (rect.isEmpty()) { |
| 29 | rect.fLeft = rand.nextS() % 1000; |
| 30 | rect.fRight = rand.nextS() % 1000; |
| 31 | rect.fTop = rand.nextS() % 1000; |
| 32 | rect.fBottom = rand.nextS() % 1000; |
| 33 | rect.sort(); |
| 34 | } |
| 35 | return rect; |
| 36 | } |
| 37 | |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 38 | static void random_data_rects(SkRandom& rand, DataRect out[], int n) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 39 | for (int i = 0; i < n; ++i) { |
| 40 | out[i].rect = random_rect(rand); |
| 41 | out[i].data = reinterpret_cast<void*>(i); |
| 42 | } |
| 43 | } |
| 44 | |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 45 | static bool verify_query(SkIRect query, DataRect rects[], |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 46 | SkTDArray<void*>& found) { |
| 47 | SkTDArray<void*> expected; |
| 48 | // manually intersect with every rectangle |
bsalomon@google.com | 373ebc6 | 2012-09-26 13:08:56 +0000 | [diff] [blame] | 49 | for (int i = 0; i < NUM_RECTS; ++i) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 50 | if (SkIRect::IntersectsNoEmptyCheck(query, rects[i].rect)) { |
| 51 | expected.push(rects[i].data); |
| 52 | } |
| 53 | } |
| 54 | |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 55 | if (expected.count() != found.count()) { |
| 56 | return false; |
| 57 | } |
| 58 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 59 | if (0 == expected.count()) { |
| 60 | return true; |
| 61 | } |
| 62 | |
| 63 | // Just cast to long since sorting by the value of the void*'s was being problematic... |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 64 | SkTQSort(reinterpret_cast<long*>(expected.begin()), |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 65 | reinterpret_cast<long*>(expected.end() - 1)); |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 66 | SkTQSort(reinterpret_cast<long*>(found.begin()), |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 67 | reinterpret_cast<long*>(found.end() - 1)); |
| 68 | return found == expected; |
| 69 | } |
| 70 | |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 71 | static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, DataRect rects[], |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 72 | SkRTree& tree) { |
robertphillips@google.com | 178a267 | 2012-09-13 13:25:30 +0000 | [diff] [blame] | 73 | for (size_t i = 0; i < NUM_QUERIES; ++i) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 74 | SkTDArray<void*> hits; |
| 75 | SkIRect query = random_rect(rand); |
| 76 | tree.search(query, &hits); |
| 77 | REPORTER_ASSERT(reporter, verify_query(query, rects, hits)); |
| 78 | } |
| 79 | } |
| 80 | |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 81 | static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 82 | DataRect rects[NUM_RECTS]; |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 83 | SkRandom rand; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 84 | REPORTER_ASSERT(reporter, NULL != rtree); |
| 85 | |
| 86 | int expectedDepthMin = -1; |
| 87 | int expectedDepthMax = -1; |
| 88 | |
| 89 | int tmp = NUM_RECTS; |
| 90 | while (tmp > 0) { |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 91 | tmp -= static_cast<int>(pow(static_cast<double>(MAX_CHILDREN), |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 92 | static_cast<double>(expectedDepthMin + 1))); |
| 93 | ++expectedDepthMin; |
| 94 | } |
| 95 | |
| 96 | tmp = NUM_RECTS; |
| 97 | while (tmp > 0) { |
| 98 | tmp -= static_cast<int>(pow(static_cast<double>(MIN_CHILDREN), |
| 99 | static_cast<double>(expectedDepthMax + 1))); |
| 100 | ++expectedDepthMax; |
| 101 | } |
| 102 | |
robertphillips@google.com | 178a267 | 2012-09-13 13:25:30 +0000 | [diff] [blame] | 103 | for (size_t i = 0; i < NUM_ITERATIONS; ++i) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 104 | random_data_rects(rand, rects, NUM_RECTS); |
| 105 | |
| 106 | // First try bulk-loaded inserts |
bsalomon@google.com | 373ebc6 | 2012-09-26 13:08:56 +0000 | [diff] [blame] | 107 | for (int i = 0; i < NUM_RECTS; ++i) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 108 | rtree->insert(rects[i].data, rects[i].rect, true); |
| 109 | } |
| 110 | rtree->flushDeferredInserts(); |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 111 | run_queries(reporter, rand, rects, *rtree); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 112 | REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount()); |
| 113 | REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() && |
| 114 | expectedDepthMax >= rtree->getDepth()); |
| 115 | rtree->clear(); |
| 116 | REPORTER_ASSERT(reporter, 0 == rtree->getCount()); |
| 117 | |
| 118 | // Then try immediate inserts |
bsalomon@google.com | 373ebc6 | 2012-09-26 13:08:56 +0000 | [diff] [blame] | 119 | for (int i = 0; i < NUM_RECTS; ++i) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 120 | rtree->insert(rects[i].data, rects[i].rect); |
| 121 | } |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 122 | run_queries(reporter, rand, rects, *rtree); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 123 | REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount()); |
| 124 | REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() && |
| 125 | expectedDepthMax >= rtree->getDepth()); |
| 126 | rtree->clear(); |
| 127 | REPORTER_ASSERT(reporter, 0 == rtree->getCount()); |
| 128 | |
| 129 | // And for good measure try immediate inserts, but in reversed order |
| 130 | for (int i = NUM_RECTS - 1; i >= 0; --i) { |
| 131 | rtree->insert(rects[i].data, rects[i].rect); |
| 132 | } |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 133 | run_queries(reporter, rand, rects, *rtree); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 134 | REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount()); |
| 135 | REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() && |
| 136 | expectedDepthMax >= rtree->getDepth()); |
| 137 | rtree->clear(); |
| 138 | REPORTER_ASSERT(reporter, 0 == rtree->getCount()); |
| 139 | } |
| 140 | } |
| 141 | |
tfarina@chromium.org | e4fafb1 | 2013-12-12 21:11:12 +0000 | [diff] [blame] | 142 | DEF_TEST(RTree, reporter) { |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 143 | SkRTree* rtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN); |
| 144 | SkAutoUnref au(rtree); |
| 145 | rtree_test_main(rtree, reporter); |
| 146 | |
| 147 | // Rtree that orders input rectangles on deferred insert. |
sglez@google.com | ffb71f2 | 2013-08-30 17:43:31 +0000 | [diff] [blame] | 148 | SkRTree* unsortedRtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN, 1, false); |
| 149 | SkAutoUnref auo(unsortedRtree); |
| 150 | rtree_test_main(unsortedRtree, reporter); |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 151 | } |