Fast implementation of QuadTree
Rewritten to avoid memory allocations.
BUG=skia:2242
R=tomhudson@google.com, mtklein@google.com, reed@google.com, robertphillips@google.com
Author: iancottrell@google.com
Review URL: https://codereview.chromium.org/187233002
git-svn-id: http://skia.googlecode.com/svn/trunk@13826 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/tests/BBoxHierarchyTest.cpp b/tests/BBoxHierarchyTest.cpp
index a562da2..662cc37 100644
--- a/tests/BBoxHierarchyTest.cpp
+++ b/tests/BBoxHierarchyTest.cpp
@@ -13,7 +13,7 @@
static const size_t RTREE_MIN_CHILDREN = 6;
static const size_t RTREE_MAX_CHILDREN = 11;
-static const size_t QUADTREE_MIN_CHILDREN = 4;
+static const size_t QUADTREE_MIN_CHILDREN = 0;
static const size_t QUADTREE_MAX_CHILDREN = 0; // No hard limit for quadtree
static const int NUM_RECTS = 200;
@@ -126,7 +126,9 @@
REPORTER_ASSERT(reporter, 0 == tree->getCount());
// Then try immediate inserts
- for (int i = 0; i < NUM_RECTS; ++i) {
+ 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);
@@ -138,7 +140,9 @@
REPORTER_ASSERT(reporter, 0 == tree->getCount());
// And for good measure try immediate inserts, but in reversed order
- for (int i = NUM_RECTS - 1; i >= 0; --i) {
+ 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);
@@ -166,14 +170,14 @@
// QuadTree
{
- SkQuadTree* quadtree = SkQuadTree::Create(
- SkIRect::MakeLTRB(-MAX_SIZE, -MAX_SIZE, MAX_SIZE, MAX_SIZE));
+ SkQuadTree* quadtree = SkNEW_ARGS(SkQuadTree, (
+ SkIRect::MakeLTRB(-MAX_SIZE, -MAX_SIZE, MAX_SIZE, MAX_SIZE)));
SkAutoUnref au(quadtree);
tree_test_main(quadtree, QUADTREE_MIN_CHILDREN, QUADTREE_MAX_CHILDREN, reporter);
// QuadTree that orders input rectangles on deferred insert.
- SkQuadTree* unsortedQuadTree = SkQuadTree::Create(
- SkIRect::MakeLTRB(-MAX_SIZE, -MAX_SIZE, MAX_SIZE, MAX_SIZE));
+ SkQuadTree* unsortedQuadTree = SkNEW_ARGS(SkQuadTree, (
+ SkIRect::MakeLTRB(-MAX_SIZE, -MAX_SIZE, MAX_SIZE, MAX_SIZE)));
SkAutoUnref auo(unsortedQuadTree);
tree_test_main(unsortedQuadTree, QUADTREE_MIN_CHILDREN, QUADTREE_MAX_CHILDREN, reporter);
}
diff --git a/tests/ObjectPoolTest.cpp b/tests/ObjectPoolTest.cpp
new file mode 100644
index 0000000..404448e
--- /dev/null
+++ b/tests/ObjectPoolTest.cpp
@@ -0,0 +1,68 @@
+/*
+ * 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 "SkTObjectPool.h"
+#include "SkTObjectPool.h"
+#include "Test.h"
+
+class PoolEntry {
+public:
+private:
+ SK_DECLARE_INTERNAL_SLIST_INTERFACE(PoolEntry);
+};
+
+static const int kNumItemsPerBlock = 3;
+typedef SkTObjectPool<PoolEntry, kNumItemsPerBlock> ObjectPoolType;
+
+static bool verifyPool(skiatest::Reporter* reporter,
+ const ObjectPoolType& pool,
+ const char* stage,
+ int available, int blocks) {
+ if (available != pool.available()) {
+ ERRORF(reporter, "%s - Pool available is %d not %d",
+ stage, pool.available(), available);
+ return false;
+ }
+ if (blocks != pool.blocks()) {
+ ERRORF(reporter, "%s - Pool blocks is %d not %d",
+ stage, pool.blocks(), blocks);
+ return false;
+ }
+ return true;
+}
+
+static const int kNumToAcquire = kNumItemsPerBlock * 5;
+static void testObjectPool(skiatest::Reporter* reporter) {
+ ObjectPoolType pool;
+ SkTInternalSList<PoolEntry> used;
+ verifyPool(reporter, pool, "empty", 0, 0);
+ for (int index = 0; index < kNumToAcquire; ++index) {
+ used.push(pool.acquire());
+ int blocks = (index / kNumItemsPerBlock) + 1;
+ int available = (blocks * kNumItemsPerBlock) - (index + 1);
+ if (!verifyPool(reporter, pool, "acquire", available, blocks)) {
+ return;
+ }
+ }
+ int available = pool.available();
+ int blocks = pool.blocks();
+ for (int index = 0; index < kNumToAcquire / 2; ++index) {
+ pool.release(used.pop());
+ ++available;
+ if (!verifyPool(reporter, pool, "release", available, blocks)) {
+ return;
+ }
+ }
+ available += used.getCount();
+ pool.releaseAll(&used);
+ REPORTER_ASSERT(reporter, used.isEmpty());
+ verifyPool(reporter, pool, "releaseAll", available, blocks);
+}
+
+DEF_TEST(ObjectPool, reporter) {
+ testObjectPool(reporter);
+}
diff --git a/tests/SListTest.cpp b/tests/SListTest.cpp
new file mode 100644
index 0000000..72a8281
--- /dev/null
+++ b/tests/SListTest.cpp
@@ -0,0 +1,111 @@
+/*
+ * 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 "SkTInternalSList.h"
+#include "Test.h"
+
+class SListEntry {
+public:
+ SListEntry* next() { return getSListNext(); }
+private:
+ SK_DECLARE_INTERNAL_SLIST_INTERFACE(SListEntry);
+};
+
+static bool verifyEmptyList(skiatest::Reporter* reporter,
+ const SkTInternalSList<SListEntry>& list,
+ const char* stage) {
+
+ if (!list.isEmpty()) {
+ ERRORF(reporter, "%s - List not empty", stage);
+ return false;
+ }
+ if (0 != list.getCount()) {
+ ERRORF(reporter, "%s - List count is not zero, %d instead", stage, list.getCount());
+ return false;
+ }
+ if (NULL != list.head()) {
+ ERRORF(reporter, "%s - List has elements when empty", stage);
+ return false;
+ }
+ return true;
+}
+
+static bool verifyList(skiatest::Reporter* reporter,
+ const SkTInternalSList<SListEntry>& list,
+ const char* stage,
+ SListEntry* start, int count, int step = 1) {
+ SListEntry* next = list.head();
+ if (list.getCount() != count) {
+ ERRORF(reporter, "%s - List was too short, %d instead of %d", stage, list.getCount(), count);
+ return false;
+ }
+ int index = 0;
+ for(SListEntry* value = start; index < count; value += step, ++index) {
+ if (NULL == next) {
+ ERRORF(reporter, "%s - List too short, should be %d", stage, count);
+ return false;
+ }
+ if (next!= value) {
+ ERRORF(reporter, "%s - List entries at index %d of %d don't match", stage, index, count);
+ return false;
+ }
+ next = next->next();
+ }
+ if (NULL != next) {
+ ERRORF(reporter, "%s - List too long, should be %d", stage, count);
+ return false;
+ }
+ return true;
+}
+
+static void testTInternalSList(skiatest::Reporter* reporter) {
+ // Build a test array of data
+ static const int testArraySize = 10;
+ SListEntry testArray[testArraySize];
+ // Basic add remove tests
+ SkTInternalSList<SListEntry> list;
+ verifyEmptyList(reporter, list, "start");
+ // Push values in, testing on the way
+ for (int index = 0; index < testArraySize; ++index) {
+ list.push(&testArray[index]);
+ if (!verifyList(reporter, list, "push", &testArray[index], index+1, -1)) {
+ return;
+ }
+ }
+ // Now remove them again
+ for (int index = testArraySize - 1; index >= 0; --index) {
+ REPORTER_ASSERT(reporter, &testArray[index] == list.pop());
+ if ((index != 0) &&
+ !verifyList(reporter, list, "pop", &testArray[index-1], index, -1)) {
+ return;
+ }
+ }
+ verifyEmptyList(reporter, list, "end");
+ // Move between list tests
+ for (int index = 0; index < testArraySize; ++index) {
+ list.push(&testArray[index]);
+ }
+ verifyList(reporter, list, "swap", &testArray[testArraySize-1], testArraySize, -1);
+ SkTInternalSList<SListEntry> other;
+ // Check swap moves the list over unchanged
+ other.swap(&list);
+ verifyEmptyList(reporter, list, "swap");
+ verifyList(reporter, other, "swap", &testArray[testArraySize-1], testArraySize, -1);
+ // Check pushAll optimizes to a swap when one of the is empty
+ list.pushAll(&other);
+ verifyList(reporter, list, "pushAll-empty", &testArray[testArraySize-1], testArraySize, -1);
+ verifyEmptyList(reporter, other, "pushAll-empty");
+ // Check pushAll when non empty works
+ other.push(list.pop());
+ other.pushAll(&list);
+ verifyEmptyList(reporter, list, "pushAll");
+ verifyList(reporter, other, "pushAll", &testArray[0], testArraySize, 1);
+}
+
+DEF_TEST(SList, reporter) {
+ testTInternalSList(reporter);
+}