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