BBHs: void* data -> unsigned data
Now that the old backend's not using BBHs, we can specialize them for
SkRecord's needs. The only thing we really want to store is op index, which
should always be small enough to fit into an unsigned (unsigned also helps keep
it straight from other ints floating around).
This means we'll need half (32-bit) or a quarter (64-bit) the bytes in SkTileGrid,
because we don't have to store an extra int for ordering.
BUG=skia:2834
Review URL: https://codereview.chromium.org/617393004
diff --git a/bench/RTreeBench.cpp b/bench/RTreeBench.cpp
index 5442f7e..21c1d79 100644
--- a/bench/RTreeBench.cpp
+++ b/bench/RTreeBench.cpp
@@ -51,8 +51,7 @@
SkRandom rand;
for (int i = 0; i < loops; ++i) {
for (int j = 0; j < NUM_BUILD_RECTS; ++j) {
- fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUILD_RECTS),
- fBulkLoad);
+ fTree->insert(j, fProc(rand, j, NUM_BUILD_RECTS), fBulkLoad);
}
fTree->flushDeferredInserts();
fTree->clear();
@@ -104,9 +103,7 @@
virtual void onPreDraw() SK_OVERRIDE {
SkRandom rand;
for (int j = 0; j < NUM_QUERY_RECTS; ++j) {
- fTree->insert(reinterpret_cast<void*>(j),
- fProc(rand, j, NUM_QUERY_RECTS),
- fBulkLoad);
+ fTree->insert(j, fProc(rand, j, NUM_QUERY_RECTS), fBulkLoad);
}
fTree->flushDeferredInserts();
}
@@ -114,7 +111,7 @@
virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
SkRandom rand;
for (int i = 0; i < loops; ++i) {
- SkTDArray<void*> hits;
+ SkTDArray<unsigned> hits;
SkRect query;
switch(fQuery) {
case kSmall_QueryType:
diff --git a/gyp/tests.gypi b/gyp/tests.gypi
index 6afc7f0..d176cb9 100644
--- a/gyp/tests.gypi
+++ b/gyp/tests.gypi
@@ -49,7 +49,6 @@
'../tests/AnnotationTest.cpp',
'../tests/AsADashTest.cpp',
'../tests/AtomicTest.cpp',
- '../tests/BBoxHierarchyTest.cpp',
'../tests/BitSetTest.cpp',
'../tests/BitmapCopyTest.cpp',
'../tests/BitmapGetColorTest.cpp',
diff --git a/src/core/SkBBoxHierarchy.h b/src/core/SkBBoxHierarchy.h
index fd9680c..53eabc8 100644
--- a/src/core/SkBBoxHierarchy.h
+++ b/src/core/SkBBoxHierarchy.h
@@ -14,42 +14,25 @@
#include "SkRefCnt.h"
/**
- * Interface for a client class that implements utility methods needed
- * by SkBBoxHierarchy that require intrinsic knowledge of the data
- * object type that is stored in the bounding box hierarchy.
- */
-class SkBBoxHierarchyClient {
-public:
- virtual ~SkBBoxHierarchyClient() {}
-
- /**
- * Implements a rewind stop condition used by rewindInserts
- * Must returns true if 'data' points to an object that should be re-wound
- * by rewinfInserts.
- */
- virtual bool shouldRewind(void* data) = 0;
-};
-
-/**
- * Interface for a spatial data structure that associates user data pointers with axis-aligned
+ * Interface for a spatial data structure that associates user data with axis-aligned
* bounding boxes, and allows efficient retrieval of intersections with query rectangles.
*/
class SkBBoxHierarchy : public SkRefCnt {
public:
SK_DECLARE_INST_COUNT(SkBBoxHierarchy)
- SkBBoxHierarchy() : fClient(NULL) {}
+ SkBBoxHierarchy() {}
/**
- * Insert a data pointer and corresponding bounding box
- * @param data The data pointer, may be NULL
+ * Insert opIndex and corresponding bounding box
+ * @param opIndex Any value, will be returned in order.
* @param bounds The bounding box, should not be empty
* @param defer Whether or not it is acceptable to delay insertion of this element (building up
* an entire spatial data structure at once is often faster and produces better
* structures than repeated inserts) until flushDeferredInserts is called or the first
* search.
*/
- virtual void insert(void* data, const SkRect& bounds, bool defer = false) = 0;
+ virtual void insert(unsigned opIndex, const SkRect& bounds, bool defer = false) = 0;
/**
* If any insertions have been deferred, this forces them to be inserted
@@ -57,9 +40,9 @@
virtual void flushDeferredInserts() = 0;
/**
- * Populate 'results' with data pointers corresponding to bounding boxes that intersect 'query'
+ * Populate results with sorted opIndex corresponding to bounding boxes that intersect query.
*/
- virtual void search(const SkRect& query, SkTDArray<void*>* results) const = 0;
+ virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const = 0;
virtual void clear() = 0;
@@ -78,19 +61,6 @@
*/
virtual int getDepth() const = 0;
- /**
- * Rewinds all the most recently inserted data elements until an element
- * is encountered for which client->shouldRewind(data) returns false. May
- * not rewind elements that were inserted prior to the last call to
- * flushDeferredInserts.
- */
- virtual void rewindInserts() = 0;
-
- void setClient(SkBBoxHierarchyClient* client) { fClient = client; }
-
-protected:
- SkBBoxHierarchyClient* fClient;
-
private:
typedef SkRefCnt INHERITED;
};
diff --git a/src/core/SkRTree.cpp b/src/core/SkRTree.cpp
index 17872ba..4a081db 100644
--- a/src/core/SkRTree.cpp
+++ b/src/core/SkRTree.cpp
@@ -44,7 +44,7 @@
this->clear();
}
-void SkRTree::insert(void* data, const SkRect& fbounds, bool defer) {
+void SkRTree::insert(unsigned opIndex, const SkRect& fbounds, bool defer) {
SkIRect bounds;
if (fbounds.isLargest()) {
bounds.setLargest();
@@ -59,7 +59,7 @@
}
Branch newBranch;
newBranch.fBounds = bounds;
- newBranch.fChild.data = data;
+ newBranch.fChild.opIndex = opIndex;
if (this->isEmpty()) {
// since a bulk-load into an existing tree is as of yet unimplemented (and arguably not
// of vital importance right now), we only batch up inserts if the tree is empty.
@@ -109,7 +109,7 @@
this->validate();
}
-void SkRTree::search(const SkRect& fquery, SkTDArray<void*>* results) const {
+void SkRTree::search(const SkRect& fquery, SkTDArray<unsigned>* results) const {
SkIRect query;
fquery.roundOut(&query);
this->validate();
@@ -309,11 +309,11 @@
return fMinChildren - 1 + k;
}
-void SkRTree::search(Node* root, const SkIRect query, SkTDArray<void*>* results) const {
+void SkRTree::search(Node* root, const SkIRect query, SkTDArray<unsigned>* results) const {
for (int i = 0; i < root->fNumChildren; ++i) {
if (SkIRect::IntersectsNoEmptyCheck(root->child(i)->fBounds, query)) {
if (root->isLeaf()) {
- results->push(root->child(i)->fChild.data);
+ results->push(root->child(i)->fChild.opIndex);
} else {
this->search(root->child(i)->fChild.subtree, query, results);
}
@@ -448,14 +448,6 @@
}
}
-void SkRTree::rewindInserts() {
- SkASSERT(this->isEmpty()); // Currently only supports deferred inserts
- while (!fDeferredInserts.isEmpty() &&
- fClient->shouldRewind(fDeferredInserts.top().fChild.data)) {
- fDeferredInserts.pop();
- }
-}
-
///////////////////////////////////////////////////////////////////////////////////////////////////
static inline uint32_t get_area(const SkIRect& rect) {
diff --git a/src/core/SkRTree.h b/src/core/SkRTree.h
index 8e98024..85469cc 100644
--- a/src/core/SkRTree.h
+++ b/src/core/SkRTree.h
@@ -63,11 +63,11 @@
* Insert a node, consisting of bounds and a data value into the tree, if we don't immediately
* need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load
* a large batch of nodes at once, which tends to be faster and produce a better tree).
- * @param data The data value
+ * @param opIndex The data value
* @param bounds The corresponding bounding box
* @param defer Can this insert be deferred? (this may be ignored)
*/
- virtual void insert(void* data, const SkRect& bounds, bool defer = false) SK_OVERRIDE;
+ virtual void insert(unsigned opIndex, const SkRect& bounds, bool defer = false) SK_OVERRIDE;
/**
* If any inserts have been deferred, this will add them into the tree
@@ -77,7 +77,7 @@
/**
* Given a query rectangle, populates the passed-in array with the elements it intersects
*/
- virtual void search(const SkRect& query, SkTDArray<void*>* results) const SK_OVERRIDE;
+ virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE;
virtual void clear() SK_OVERRIDE;
bool isEmpty() const { return 0 == fCount; }
@@ -94,8 +94,6 @@
*/
virtual int getCount() const SK_OVERRIDE { return fCount; }
- virtual void rewindInserts() SK_OVERRIDE;
-
private:
struct Node;
@@ -106,7 +104,7 @@
struct Branch {
union {
Node* subtree;
- void* data;
+ unsigned opIndex;
} fChild;
SkIRect fBounds;
};
@@ -162,7 +160,7 @@
int chooseSubtree(Node* root, Branch* branch);
SkIRect computeBounds(Node* n);
int distributeChildren(Branch* children);
- void search(Node* root, const SkIRect query, SkTDArray<void*>* results) const;
+ void search(Node* root, const SkIRect query, SkTDArray<unsigned>* results) const;
/**
* This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm, this
diff --git a/src/core/SkRecordDraw.cpp b/src/core/SkRecordDraw.cpp
index c693b05..13b06b5 100644
--- a/src/core/SkRecordDraw.cpp
+++ b/src/core/SkRecordDraw.cpp
@@ -23,7 +23,7 @@
SkRect query = { 0, 0, 0, 0 };
(void)canvas->getClipBounds(&query);
- SkTDArray<void*> ops;
+ SkTDArray<unsigned> ops;
bbh->search(query, &ops);
SkRecords::Draw draw(canvas);
@@ -31,7 +31,7 @@
if (callback && callback->abortDrawing()) {
return;
}
- record.visit<void>((uintptr_t)ops[i], draw); // See FillBounds below.
+ record.visit<void>(ops[i], draw);
}
} else {
// Draw all ops.
@@ -156,9 +156,9 @@
// Finally feed all stored bounds into the BBH. They'll be returned in this order.
SkASSERT(bbh);
- for (uintptr_t i = 0; i < record.count(); i++) {
+ for (unsigned i = 0; i < record.count(); i++) {
if (!fBounds[i].isEmpty()) {
- bbh->insert((void*)i, fBounds[i], true/*ok to defer*/);
+ bbh->insert(i, fBounds[i], true/*ok to defer*/);
}
}
bbh->flushDeferredInserts();
diff --git a/src/core/SkTileGrid.cpp b/src/core/SkTileGrid.cpp
index 2eea6db..8cdebcb 100644
--- a/src/core/SkTileGrid.cpp
+++ b/src/core/SkTileGrid.cpp
@@ -12,7 +12,7 @@
, fYTiles(yTiles)
, fInfo(info)
, fCount(0)
- , fTiles(SkNEW_ARRAY(SkTDArray<Entry>, xTiles * yTiles)) {
+ , fTiles(SkNEW_ARRAY(SkTDArray<unsigned>, xTiles * yTiles)) {
// Margin is offset by 1 as a provision for AA and
// to cancel-out the outset applied by getClipDeviceBounds.
fInfo.fMargin.fHeight++;
@@ -23,7 +23,7 @@
SkDELETE_ARRAY(fTiles);
}
-void SkTileGrid::insert(void* data, const SkRect& fbounds, bool) {
+void SkTileGrid::insert(unsigned opIndex, const SkRect& fbounds, bool) {
SkASSERT(!fbounds.isEmpty());
SkIRect dilatedBounds;
if (fbounds.isLargest()) {
@@ -51,10 +51,9 @@
int maxY = SkMax32(0, SkMin32((dilatedBounds.bottom() - 1) / fInfo.fTileInterval.height(),
fYTiles - 1));
- Entry entry = { fCount++, data };
for (int y = minY; y <= maxY; y++) {
for (int x = minX; x <= maxX; x++) {
- fTiles[y * fXTiles + x].push(entry);
+ fTiles[y * fXTiles + x].push(opIndex);
}
}
}
@@ -69,7 +68,7 @@
// require 512 tiles of size 256 x 256 pixels.
static const int kStackAllocationTileCount = 1024;
-void SkTileGrid::search(const SkRect& query, SkTDArray<void*>* results) const {
+void SkTileGrid::search(const SkRect& query, SkTDArray<unsigned>* results) const {
SkIRect adjusted;
query.roundOut(&adjusted);
@@ -102,24 +101,20 @@
if (tilesHit == 1) {
// A performance shortcut. The merging code below would work fine here too.
- const SkTDArray<Entry>& tile = fTiles[startY * fXTiles + startX];
- results->setCount(tile.count());
- for (int i = 0; i < tile.count(); i++) {
- (*results)[i] = tile[i].data;
- }
+ *results = fTiles[startY * fXTiles + startX];
return;
}
// We've got to merge the data in many tiles into a single sorted and deduplicated stream.
- // We do a simple k-way merge based on the order the data was inserted.
+ // We do a simple k-way merge based on the value of opIndex.
// Gather pointers to the starts and ends of the tiles to merge.
- SkAutoSTArray<kStackAllocationTileCount, const Entry*> starts(tilesHit), ends(tilesHit);
+ SkAutoSTArray<kStackAllocationTileCount, const unsigned*> starts(tilesHit), ends(tilesHit);
int i = 0;
for (int x = startX; x < endX; x++) {
for (int y = startY; y < endY; y++) {
starts[i] = fTiles[y * fXTiles + x].begin();
- ends[i] = fTiles[y * fXTiles + x].end();
+ ends[i] = fTiles[y * fXTiles + x].end();
i++;
}
}
@@ -129,10 +124,10 @@
while (true) {
// The tiles themselves are already ordered, so the earliest is at the front of some tile.
// It may be at the front of several, even all, tiles.
- const Entry* earliest = NULL;
+ const unsigned* earliest = NULL;
for (int i = 0; i < starts.count(); i++) {
if (starts[i] < ends[i]) {
- if (NULL == earliest || starts[i]->order < earliest->order) {
+ if (NULL == earliest || *starts[i]< *earliest) {
earliest = starts[i];
}
}
@@ -144,9 +139,9 @@
}
// We did find an earliest entry. Output it, and step forward every tile that contains it.
- results->push(earliest->data);
+ results->push(*earliest);
for (int i = 0; i < starts.count(); i++) {
- if (starts[i] < ends[i] && starts[i]->order == earliest->order) {
+ if (starts[i] < ends[i] && *starts[i] == *earliest) {
starts[i]++;
}
}
@@ -159,11 +154,3 @@
}
}
-void SkTileGrid::rewindInserts() {
- SkASSERT(fClient);
- for (int i = 0; i < fXTiles * fYTiles; i++) {
- while (!fTiles[i].isEmpty() && fClient->shouldRewind(fTiles[i].top().data)) {
- fTiles[i].pop();
- }
- }
-}
diff --git a/src/core/SkTileGrid.h b/src/core/SkTileGrid.h
index 1e34a61..97564c6 100644
--- a/src/core/SkTileGrid.h
+++ b/src/core/SkTileGrid.h
@@ -23,20 +23,20 @@
virtual ~SkTileGrid();
/**
- * Insert a data pointer and corresponding bounding box
- * @param data An arbitrary data pointer, may be NULL.
+ * Insert a opIndex value and corresponding bounding box
+ * @param opIndex
* @param bounds The bounding box, should not be empty.
* @param defer Ignored; SkTileGrid does not defer insertions.
*/
- virtual void insert(void* data, const SkRect& bounds, bool) SK_OVERRIDE;
+ virtual void insert(unsigned opIndex, const SkRect& bounds, bool) SK_OVERRIDE;
virtual void flushDeferredInserts() SK_OVERRIDE {};
/**
- * Populate 'results' with data pointers corresponding to bounding boxes that intersect 'query'.
+ * Populate 'results' with opIndexes corresponding to bounding boxes that intersect 'query'.
* This will be fastest if the query is an exact match to a single grid tile.
*/
- virtual void search(const SkRect& query, SkTDArray<void*>* results) const SK_OVERRIDE;
+ virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE;
virtual void clear() SK_OVERRIDE;
@@ -44,23 +44,16 @@
virtual int getDepth() const SK_OVERRIDE { return -1; }
- virtual void rewindInserts() SK_OVERRIDE;
-
// For testing.
int tileCount(int x, int y) { return fTiles[y * fXTiles + x].count(); }
private:
- struct Entry {
- size_t order; // Insertion order. Used to preserve order when merging multiple tiles.
- void* data;
- };
-
const int fXTiles, fYTiles;
SkTileGridFactory::TileGridInfo fInfo;
size_t fCount;
- // (fXTiles * fYTiles) SkTDArrays, each listing data overlapping that tile in insertion order.
- SkTDArray<Entry>* fTiles;
+ // (fXTiles * fYTiles) SkTDArrays, each listing ops overlapping that tile in order.
+ SkTDArray<unsigned>* fTiles;
typedef SkBBoxHierarchy INHERITED;
};
diff --git a/src/gpu/GrRecordReplaceDraw.cpp b/src/gpu/GrRecordReplaceDraw.cpp
index c8b2670..b069e60 100644
--- a/src/gpu/GrRecordReplaceDraw.cpp
+++ b/src/gpu/GrRecordReplaceDraw.cpp
@@ -11,7 +11,7 @@
#include "SkRecordDraw.h"
#include "SkRecords.h"
-GrReplacements::ReplacementInfo* GrReplacements::newReplacement(uint32_t pictureID,
+GrReplacements::ReplacementInfo* GrReplacements::newReplacement(uint32_t pictureID,
unsigned int start,
const SkMatrix& ctm) {
ReplacementInfo* replacement = SkNEW_ARGS(ReplacementInfo, (pictureID, start, ctm));
@@ -30,8 +30,8 @@
fReplacementHash.reset();
}
-const GrReplacements::ReplacementInfo* GrReplacements::lookupByStart(uint32_t pictureID,
- size_t start,
+const GrReplacements::ReplacementInfo* GrReplacements::lookupByStart(uint32_t pictureID,
+ size_t start,
const SkMatrix& ctm) const {
return fReplacementHash.find(ReplacementInfo::Key(pictureID, start, ctm));
}
@@ -94,7 +94,7 @@
return;
}
- record->visit<void>((uintptr_t)fOps[fIndex], *this);
+ record->visit<void>(fOps[fIndex], *this);
}
} else {
@@ -121,29 +121,29 @@
draw.draw();
}
void operator()(const SkRecords::SaveLayer& sl) {
-
+
// For a saveLayer command, check if it can be replaced by a drawBitmap
// call and, if so, draw it and then update the current op index accordingly.
size_t startOffset;
if (fOps.count()) {
- startOffset = (uintptr_t)fOps[fIndex];
+ startOffset = fOps[fIndex];
} else {
startOffset = fIndex;
}
const GrReplacements::ReplacementInfo* ri = fReplacements->lookupByStart(
- fPicture->uniqueID(),
- startOffset,
+ fPicture->uniqueID(),
+ startOffset,
fCanvas->getTotalMatrix());
if (ri) {
draw_replacement_bitmap(ri, fCanvas, fInitialMatrix);
if (fPicture->fBBH.get()) {
- while ((uintptr_t)fOps[fIndex] < ri->fStop) {
+ while (fOps[fIndex] < ri->fStop) {
++fIndex;
}
- SkASSERT((uintptr_t)fOps[fIndex] == ri->fStop);
+ SkASSERT(fOps[fIndex] == ri->fStop);
} else {
fIndex = ri->fStop;
}
@@ -161,7 +161,7 @@
const SkMatrix fInitialMatrix;
SkDrawPictureCallback* fCallback;
- SkTDArray<void*> fOps;
+ SkTDArray<unsigned> fOps;
int fIndex;
typedef Draw INHERITED;
diff --git a/tests/BBoxHierarchyTest.cpp b/tests/BBoxHierarchyTest.cpp
deleted file mode 100644
index 71b9699..0000000
--- a/tests/BBoxHierarchyTest.cpp
+++ /dev/null
@@ -1,170 +0,0 @@
-/*
- * Copyright 2012 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
-
-#include "Test.h"
-#include "SkRandom.h"
-#include "SkRTree.h"
-#include "SkTSort.h"
-
-static const size_t RTREE_MIN_CHILDREN = 6;
-static const size_t RTREE_MAX_CHILDREN = 11;
-
-static const int NUM_RECTS = 200;
-static const size_t NUM_ITERATIONS = 100;
-static const size_t NUM_QUERIES = 50;
-
-static const SkScalar MAX_SIZE = 1000.0f;
-
-struct DataRect {
- SkRect rect;
- void* data;
-};
-
-static SkRect random_rect(SkRandom& rand) {
- SkRect rect = {0,0,0,0};
- while (rect.isEmpty()) {
- rect.fLeft = rand.nextRangeF(0, MAX_SIZE);
- rect.fRight = rand.nextRangeF(0, MAX_SIZE);
- rect.fTop = rand.nextRangeF(0, MAX_SIZE);
- rect.fBottom = rand.nextRangeF(0, MAX_SIZE);
- rect.sort();
- }
- return rect;
-}
-
-static void random_data_rects(SkRandom& rand, DataRect out[], int n) {
- for (int i = 0; i < n; ++i) {
- out[i].rect = random_rect(rand);
- out[i].data = reinterpret_cast<void*>(i);
- }
-}
-
-static bool verify_query(SkRect query, DataRect rects[],
- SkTDArray<void*>& found) {
- // TODO(mtklein): no need to do this after everything's SkRects
- query.roundOut();
-
- SkTDArray<void*> expected;
- // manually intersect with every rectangle
- for (int i = 0; i < NUM_RECTS; ++i) {
- if (SkRect::Intersects(query, rects[i].rect)) {
- expected.push(rects[i].data);
- }
- }
-
- if (expected.count() != found.count()) {
- return false;
- }
-
- if (0 == expected.count()) {
- return true;
- }
-
- // Just cast to long since sorting by the value of the void*'s was being problematic...
- SkTQSort(reinterpret_cast<long*>(expected.begin()),
- reinterpret_cast<long*>(expected.end() - 1));
- SkTQSort(reinterpret_cast<long*>(found.begin()),
- reinterpret_cast<long*>(found.end() - 1));
- return found == expected;
-}
-
-static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, DataRect rects[],
- SkBBoxHierarchy& tree) {
- for (size_t i = 0; i < NUM_QUERIES; ++i) {
- SkTDArray<void*> hits;
- SkRect query = random_rect(rand);
- tree.search(query, &hits);
- REPORTER_ASSERT(reporter, verify_query(query, rects, hits));
- }
-}
-
-static void tree_test_main(SkBBoxHierarchy* tree, int minChildren, int maxChildren,
- skiatest::Reporter* reporter) {
- DataRect rects[NUM_RECTS];
- SkRandom rand;
- REPORTER_ASSERT(reporter, tree);
-
- int expectedDepthMin = -1;
- int expectedDepthMax = -1;
-
- int tmp = NUM_RECTS;
- if (maxChildren > 0) {
- while (tmp > 0) {
- tmp -= static_cast<int>(pow(static_cast<double>(maxChildren),
- static_cast<double>(expectedDepthMin + 1)));
- ++expectedDepthMin;
- }
- }
-
- tmp = NUM_RECTS;
- if (minChildren > 0) {
- while (tmp > 0) {
- tmp -= static_cast<int>(pow(static_cast<double>(minChildren),
- static_cast<double>(expectedDepthMax + 1)));
- ++expectedDepthMax;
- }
- }
-
- for (size_t i = 0; i < NUM_ITERATIONS; ++i) {
- random_data_rects(rand, rects, NUM_RECTS);
-
- // First try bulk-loaded inserts
- for (int i = 0; i < NUM_RECTS; ++i) {
- tree->insert(rects[i].data, rects[i].rect, true);
- }
- tree->flushDeferredInserts();
- run_queries(reporter, rand, rects, *tree);
- REPORTER_ASSERT(reporter, NUM_RECTS == tree->getCount());
- REPORTER_ASSERT(reporter,
- ((expectedDepthMin <= 0) || (expectedDepthMin <= tree->getDepth())) &&
- ((expectedDepthMax <= 0) || (expectedDepthMax >= tree->getDepth())));
- tree->clear();
- REPORTER_ASSERT(reporter, 0 == tree->getCount());
-
- // Then try immediate inserts
- tree->insert(rects[0].data, rects[0].rect);
- tree->flushDeferredInserts();
- for (int i = 1; i < NUM_RECTS; ++i) {
- tree->insert(rects[i].data, rects[i].rect);
- }
- run_queries(reporter, rand, rects, *tree);
- REPORTER_ASSERT(reporter, NUM_RECTS == tree->getCount());
- REPORTER_ASSERT(reporter,
- ((expectedDepthMin <= 0) || (expectedDepthMin <= tree->getDepth())) &&
- ((expectedDepthMax <= 0) || (expectedDepthMax >= tree->getDepth())));
- tree->clear();
- REPORTER_ASSERT(reporter, 0 == tree->getCount());
-
- // And for good measure try immediate inserts, but in reversed order
- tree->insert(rects[NUM_RECTS - 1].data, rects[NUM_RECTS - 1].rect);
- tree->flushDeferredInserts();
- for (int i = NUM_RECTS - 2; i >= 0; --i) {
- tree->insert(rects[i].data, rects[i].rect);
- }
- run_queries(reporter, rand, rects, *tree);
- REPORTER_ASSERT(reporter, NUM_RECTS == tree->getCount());
- REPORTER_ASSERT(reporter,
- ((expectedDepthMin < 0) || (expectedDepthMin <= tree->getDepth())) &&
- ((expectedDepthMax < 0) || (expectedDepthMax >= tree->getDepth())));
- tree->clear();
- REPORTER_ASSERT(reporter, 0 == tree->getCount());
- }
-}
-
-DEF_TEST(BBoxHierarchy, reporter) {
- // RTree
- {
- SkRTree* rtree = SkRTree::Create(RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN);
- SkAutoUnref au(rtree);
- tree_test_main(rtree, RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, reporter);
-
- // Rtree that orders input rectangles on deferred insert.
- SkRTree* unsortedRtree = SkRTree::Create(RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, 1, false);
- SkAutoUnref auo(unsortedRtree);
- tree_test_main(unsortedRtree, RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, reporter);
- }
-}
diff --git a/tests/PictureTest.cpp b/tests/PictureTest.cpp
index c41b327..0518dd3 100644
--- a/tests/PictureTest.cpp
+++ b/tests/PictureTest.cpp
@@ -1865,17 +1865,16 @@
CountingBBH() : searchCalls(0) {}
- virtual void search(const SkRect& query, SkTDArray<void*>* results) const {
+ virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE {
this->searchCalls++;
}
// All other methods unimplemented.
- virtual void insert(void* data, const SkRect& bounds, bool defer) {}
- virtual void flushDeferredInserts() {}
- virtual void clear() {}
- virtual int getCount() const { return 0; }
- virtual int getDepth() const { return 0; }
- virtual void rewindInserts() {}
+ virtual void insert(unsigned opIndex, const SkRect& bounds, bool defer) SK_OVERRIDE {}
+ virtual void flushDeferredInserts() SK_OVERRIDE {}
+ virtual void clear() SK_OVERRIDE {}
+ virtual int getCount() const SK_OVERRIDE { return 0; }
+ virtual int getDepth() const SK_OVERRIDE { return 0; }
};
class SpoonFedBBHFactory : public SkBBHFactory {
diff --git a/tests/RTreeTest.cpp b/tests/RTreeTest.cpp
index 40af5fe..6e0622c 100644
--- a/tests/RTreeTest.cpp
+++ b/tests/RTreeTest.cpp
@@ -17,11 +17,6 @@
static const size_t NUM_ITERATIONS = 100;
static const size_t NUM_QUERIES = 50;
-struct DataRect {
- SkRect rect;
- void* data;
-};
-
static SkRect random_rect(SkRandom& rand) {
SkRect rect = {0,0,0,0};
while (rect.isEmpty()) {
@@ -34,24 +29,22 @@
return rect;
}
-static void random_data_rects(SkRandom& rand, DataRect out[], int n) {
+static void random_data_rects(SkRandom& rand, SkRect out[], int n) {
for (int i = 0; i < n; ++i) {
- out[i].rect = random_rect(rand);
- out[i].data = reinterpret_cast<void*>(i);
+ out[i] = random_rect(rand);
}
}
-static bool verify_query(SkRect query, DataRect rects[],
- SkTDArray<void*>& found) {
+static bool verify_query(SkRect query, SkRect rects[], SkTDArray<unsigned>& found) {
// TODO(mtklein): no need to do this after everything's SkRects
query.roundOut();
- SkTDArray<void*> expected;
+ SkTDArray<unsigned> expected;
// manually intersect with every rectangle
for (int i = 0; i < NUM_RECTS; ++i) {
- if (SkRect::Intersects(query, rects[i].rect)) {
- expected.push(rects[i].data);
+ if (SkRect::Intersects(query, rects[i])) {
+ expected.push(i);
}
}
@@ -63,18 +56,16 @@
return true;
}
- // Just cast to long since sorting by the value of the void*'s was being problematic...
- SkTQSort(reinterpret_cast<long*>(expected.begin()),
- reinterpret_cast<long*>(expected.end() - 1));
- SkTQSort(reinterpret_cast<long*>(found.begin()),
- reinterpret_cast<long*>(found.end() - 1));
+ // skia:2834. RTree doesn't always return results in order.
+ SkTQSort(expected.begin(), expected.end() -1);
+ SkTQSort(found.begin(), found.end() -1);
return found == expected;
}
-static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, DataRect rects[],
+static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, SkRect rects[],
SkRTree& tree) {
for (size_t i = 0; i < NUM_QUERIES; ++i) {
- SkTDArray<void*> hits;
+ SkTDArray<unsigned> hits;
SkRect query = random_rect(rand);
tree.search(query, &hits);
REPORTER_ASSERT(reporter, verify_query(query, rects, hits));
@@ -82,7 +73,7 @@
}
static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) {
- DataRect rects[NUM_RECTS];
+ SkRect rects[NUM_RECTS];
SkRandom rand;
REPORTER_ASSERT(reporter, rtree);
@@ -108,7 +99,7 @@
// First try bulk-loaded inserts
for (int i = 0; i < NUM_RECTS; ++i) {
- rtree->insert(rects[i].data, rects[i].rect, true);
+ rtree->insert(i, rects[i], true);
}
rtree->flushDeferredInserts();
run_queries(reporter, rand, rects, *rtree);
@@ -120,7 +111,7 @@
// Then try immediate inserts
for (int i = 0; i < NUM_RECTS; ++i) {
- rtree->insert(rects[i].data, rects[i].rect);
+ rtree->insert(i, rects[i]);
}
run_queries(reporter, rand, rects, *rtree);
REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
@@ -131,7 +122,7 @@
// And for good measure try immediate inserts, but in reversed order
for (int i = NUM_RECTS - 1; i >= 0; --i) {
- rtree->insert(rects[i].data, rects[i].rect);
+ rtree->insert(i, rects[i]);
}
run_queries(reporter, rand, rects, *rtree);
REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
diff --git a/tests/RecordDrawTest.cpp b/tests/RecordDrawTest.cpp
index 33efbd8..ac3883b 100644
--- a/tests/RecordDrawTest.cpp
+++ b/tests/RecordDrawTest.cpp
@@ -98,24 +98,23 @@
}
struct TestBBH : public SkBBoxHierarchy {
- virtual void insert(void* data, const SkRect& bounds, bool defer) SK_OVERRIDE {
- Entry e = { (uintptr_t)data, bounds };
- entries.push(e);
+ virtual void insert(unsigned opIndex, const SkRect& bounds, bool defer) SK_OVERRIDE {
+ Entry e = { opIndex, bounds };
+ fEntries.push(e);
}
- virtual int getCount() const SK_OVERRIDE { return entries.count(); }
+ virtual int getCount() const SK_OVERRIDE { return fEntries.count(); }
virtual void flushDeferredInserts() SK_OVERRIDE {}
- virtual void search(const SkRect& query, SkTDArray<void*>* results) const SK_OVERRIDE {}
+ virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE {}
virtual void clear() SK_OVERRIDE {}
- virtual void rewindInserts() SK_OVERRIDE {}
virtual int getDepth() const SK_OVERRIDE { return -1; }
struct Entry {
- uintptr_t data;
+ unsigned opIndex;
SkRect bounds;
};
- SkTDArray<Entry> entries;
+ SkTDArray<Entry> fEntries;
};
// Like a==b, with a little slop recognizing that float equality can be weird.
@@ -140,11 +139,11 @@
TestBBH bbh;
SkRecordFillBounds(record, &bbh);
- REPORTER_ASSERT(r, bbh.entries.count() == 5);
- for (int i = 0; i < bbh.entries.count(); i++) {
- REPORTER_ASSERT(r, bbh.entries[i].data == (uintptr_t)i);
+ REPORTER_ASSERT(r, bbh.fEntries.count() == 5);
+ for (int i = 0; i < bbh.fEntries.count(); i++) {
+ REPORTER_ASSERT(r, bbh.fEntries[i].opIndex == (unsigned)i);
- REPORTER_ASSERT(r, sloppy_rect_eq(SkRect::MakeWH(400, 480), bbh.entries[i].bounds));
+ REPORTER_ASSERT(r, sloppy_rect_eq(SkRect::MakeWH(400, 480), bbh.fEntries[i].bounds));
}
}
@@ -165,13 +164,13 @@
TestBBH bbh;
SkRecordFillBounds(record, &bbh);
- REPORTER_ASSERT(r, bbh.entries.count() == 2);
+ REPORTER_ASSERT(r, bbh.fEntries.count() == 2);
// We can make these next assertions confidently because SkRecordFillBounds
// builds its bounds by overestimating font metrics in a platform-independent way.
// If that changes, these tests will need to be more flexible.
- REPORTER_ASSERT(r, sloppy_rect_eq(bbh.entries[0].bounds, SkRect::MakeLTRB(-86, 6, 116, 54)));
- REPORTER_ASSERT(r, sloppy_rect_eq(bbh.entries[1].bounds, SkRect::MakeLTRB(-56, 26, 156, 94)));
+ REPORTER_ASSERT(r, sloppy_rect_eq(bbh.fEntries[0].bounds, SkRect::MakeLTRB(-86, 6, 116, 54)));
+ REPORTER_ASSERT(r, sloppy_rect_eq(bbh.fEntries[1].bounds, SkRect::MakeLTRB(-56, 26, 156, 94)));
}
// Base test to ensure start/stop range is respected
@@ -252,9 +251,9 @@
// The saveLayer, clipRect, and restore bounds were incorrectly (0,0,70,50).
TestBBH bbh;
SkRecordFillBounds(record, &bbh);
- REPORTER_ASSERT(r, bbh.entries.count() == 4);
- REPORTER_ASSERT(r, sloppy_rect_eq(bbh.entries[0].bounds, SkRect::MakeLTRB(0, 0, 50, 50)));
- REPORTER_ASSERT(r, sloppy_rect_eq(bbh.entries[1].bounds, SkRect::MakeLTRB(0, 0, 50, 50)));
- REPORTER_ASSERT(r, sloppy_rect_eq(bbh.entries[2].bounds, SkRect::MakeLTRB(0, 0, 40, 40)));
- REPORTER_ASSERT(r, sloppy_rect_eq(bbh.entries[3].bounds, SkRect::MakeLTRB(0, 0, 50, 50)));
+ REPORTER_ASSERT(r, bbh.fEntries.count() == 4);
+ REPORTER_ASSERT(r, sloppy_rect_eq(bbh.fEntries[0].bounds, SkRect::MakeLTRB(0, 0, 50, 50)));
+ REPORTER_ASSERT(r, sloppy_rect_eq(bbh.fEntries[1].bounds, SkRect::MakeLTRB(0, 0, 50, 50)));
+ REPORTER_ASSERT(r, sloppy_rect_eq(bbh.fEntries[2].bounds, SkRect::MakeLTRB(0, 0, 40, 40)));
+ REPORTER_ASSERT(r, sloppy_rect_eq(bbh.fEntries[3].bounds, SkRect::MakeLTRB(0, 0, 50, 50)));
}
diff --git a/tests/TileGridTest.cpp b/tests/TileGridTest.cpp
index 16434ab..6529901 100644
--- a/tests/TileGridTest.cpp
+++ b/tests/TileGridTest.cpp
@@ -31,14 +31,14 @@
SkTDArray<SkRect> fRects;
};
-static void verifyTileHits(skiatest::Reporter* reporter, SkRect rect,
- uint32_t tileMask, int borderPixels = 0) {
+static void verify_tile_hits(skiatest::Reporter* reporter, SkRect rect,
+ uint32_t tileMask, int borderPixels = 0) {
SkTileGridFactory::TileGridInfo info;
info.fMargin.set(borderPixels, borderPixels);
info.fOffset.setZero();
info.fTileInterval.set(10 - 2 * borderPixels, 10 - 2 * borderPixels);
SkTileGrid grid(2, 2, info);
- grid.insert(NULL, rect, false);
+ grid.insert(0, rect, false);
REPORTER_ASSERT(reporter, grid.tileCount(0, 0) ==
((tileMask & kTopLeft_Tile)? 1 : 0));
REPORTER_ASSERT(reporter, grid.tileCount(1, 0) ==
@@ -223,29 +223,28 @@
DEF_TEST(TileGrid, reporter) {
// Out of bounds
- verifyTileHits(reporter, SkRect::MakeXYWH(30, 0, 1, 1), 0);
- verifyTileHits(reporter, SkRect::MakeXYWH(0, 30, 1, 1), 0);
- verifyTileHits(reporter, SkRect::MakeXYWH(-10, 0, 1, 1), 0);
- verifyTileHits(reporter, SkRect::MakeXYWH(0, -10, 1, 1), 0);
+ verify_tile_hits(reporter, SkRect::MakeXYWH(30, 0, 1, 1), 0);
+ verify_tile_hits(reporter, SkRect::MakeXYWH(0, 30, 1, 1), 0);
+ verify_tile_hits(reporter, SkRect::MakeXYWH(-10, 0, 1, 1), 0);
+ verify_tile_hits(reporter, SkRect::MakeXYWH(0, -10, 1, 1), 0);
// Dilation for AA consideration
- verifyTileHits(reporter, SkRect::MakeXYWH(0, 0, 9, 9), kTopLeft_Tile);
- verifyTileHits(reporter, SkRect::MakeXYWH(0, 0, 10, 10), kAll_Tile);
- verifyTileHits(reporter, SkRect::MakeXYWH(9, 9, 1, 1), kAll_Tile);
- verifyTileHits(reporter, SkRect::MakeXYWH(10, 10, 1, 1), kAll_Tile);
- verifyTileHits(reporter, SkRect::MakeXYWH(11, 11, 1, 1), kBottomRight_Tile);
+ verify_tile_hits(reporter, SkRect::MakeXYWH(0, 0, 9, 9), kTopLeft_Tile);
+ verify_tile_hits(reporter, SkRect::MakeXYWH(0, 0, 10, 10), kAll_Tile);
+ verify_tile_hits(reporter, SkRect::MakeXYWH(9, 9, 1, 1), kAll_Tile);
+ verify_tile_hits(reporter, SkRect::MakeXYWH(10, 10, 1, 1), kAll_Tile);
+ verify_tile_hits(reporter, SkRect::MakeXYWH(11, 11, 1, 1), kBottomRight_Tile);
// BorderPixels
- verifyTileHits(reporter, SkRect::MakeXYWH(0, 0, 6, 6), kTopLeft_Tile, 1);
- verifyTileHits(reporter, SkRect::MakeXYWH(0, 0, 7, 7), kAll_Tile, 1);
- verifyTileHits(reporter, SkRect::MakeXYWH(9, 9, 1, 1), kAll_Tile, 1);
- verifyTileHits(reporter, SkRect::MakeXYWH(10, 10, 1, 1), kBottomRight_Tile, 1);
- verifyTileHits(reporter, SkRect::MakeXYWH(17, 17, 1, 1), kBottomRight_Tile, 1);
+ verify_tile_hits(reporter, SkRect::MakeXYWH(0, 0, 6, 6), kTopLeft_Tile, 1);
+ verify_tile_hits(reporter, SkRect::MakeXYWH(0, 0, 7, 7), kAll_Tile, 1);
+ verify_tile_hits(reporter, SkRect::MakeXYWH(9, 9, 1, 1), kAll_Tile, 1);
+ verify_tile_hits(reporter, SkRect::MakeXYWH(10, 10, 1, 1), kBottomRight_Tile, 1);
+ verify_tile_hits(reporter, SkRect::MakeXYWH(17, 17, 1, 1), kBottomRight_Tile, 1);
// BBoxes that overlap tiles
- verifyTileHits(reporter, SkRect::MakeXYWH(5, 5, 10, 1), kTopLeft_Tile | kTopRight_Tile);
- verifyTileHits(reporter, SkRect::MakeXYWH(5, 5, 1, 10), kTopLeft_Tile |
- kBottomLeft_Tile);
- verifyTileHits(reporter, SkRect::MakeXYWH(5, 5, 10, 10), kAll_Tile);
- verifyTileHits(reporter, SkRect::MakeXYWH(-10, -10, 40, 40), kAll_Tile);
+ verify_tile_hits(reporter, SkRect::MakeXYWH(5, 5, 10, 1), kTopLeft_Tile | kTopRight_Tile);
+ verify_tile_hits(reporter, SkRect::MakeXYWH(5, 5, 1, 10), kTopLeft_Tile | kBottomLeft_Tile);
+ verify_tile_hits(reporter, SkRect::MakeXYWH(5, 5, 10, 10), kAll_Tile);
+ verify_tile_hits(reporter, SkRect::MakeXYWH(-10, -10, 40, 40),kAll_Tile);
}