Add GrSet class built on top of RedBlackTree
BUG=skia:
R=bsalomon@google.com
Author: egdaniel@google.com
Review URL: https://codereview.chromium.org/176903003
git-svn-id: http://skia.googlecode.com/svn/trunk@13616 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/bench/GrOrderedSetBench.cpp b/bench/GrOrderedSetBench.cpp
new file mode 100644
index 0000000..4d32f0d
--- /dev/null
+++ b/bench/GrOrderedSetBench.cpp
@@ -0,0 +1,148 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkBenchmark.h"
+#include "SkCanvas.h"
+#include "SkRandom.h"
+#include "SkString.h"
+#if SK_SUPPORT_GPU
+#include "GrOrderedSet.h"
+
+static const int NUM_ELEMENTS = 1000;
+
+// Time how long it takes to build a set
+class GrOrderedSetBuildBench : public SkBenchmark {
+public:
+ GrOrderedSetBuildBench() {
+ fName.append("ordered_set_build");
+ }
+
+ virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
+ return kNonRendering_Backend == backend;
+ }
+
+ virtual ~GrOrderedSetBuildBench() {}
+
+protected:
+ virtual const char* onGetName() SK_OVERRIDE {
+ return fName.c_str();
+ }
+
+ virtual void onPreDraw() SK_OVERRIDE {
+ SkRandom rand;
+ for (int j = 0; j < NUM_ELEMENTS; ++j) {
+ fData[j] = rand.nextU() % NUM_ELEMENTS;
+ }
+ }
+
+ virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
+ for (int i = 0; i < loops; ++i) {
+ GrOrderedSet<int> set;
+ for (int j = 0; j < NUM_ELEMENTS; ++j) {
+ set.insert(fData[j]);
+ }
+ set.reset();
+ }
+ }
+
+private:
+ SkString fName;
+ int fData[NUM_ELEMENTS];
+ typedef SkBenchmark INHERITED;
+};
+
+// Time how long it takes to find elements in a set
+class GrOrderedSetFindBench : public SkBenchmark {
+public:
+ GrOrderedSetFindBench() {
+ fName.append("ordered_set_find");
+ }
+
+ virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
+ return kNonRendering_Backend == backend;
+ }
+
+ virtual ~GrOrderedSetFindBench() {}
+
+protected:
+ virtual const char* onGetName() SK_OVERRIDE {
+ return fName.c_str();
+ }
+
+ virtual void onPreDraw() SK_OVERRIDE {
+ SkRandom rand;
+ for (int j = 0; j < NUM_ELEMENTS; ++j) {
+ fData[j] = rand.nextU() % 1500;
+ fSet.insert(rand.nextU() % NUM_ELEMENTS);
+ }
+ }
+
+ virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
+ for (int i = 0; i < loops; ++i) {
+ for (int j = 0; j < NUM_ELEMENTS; ++j) {
+ fSet.find(fData[j]);
+ }
+ }
+ }
+
+private:
+ SkString fName;
+ int fData[NUM_ELEMENTS];
+ GrOrderedSet<int> fSet;
+ typedef SkBenchmark INHERITED;
+};
+
+// Time how long it takes to iterate over and remove all elements from set
+class GrOrderedSetRemoveBench : public SkBenchmark {
+public:
+ GrOrderedSetRemoveBench() {
+ fName.append("ordered_set_remove");
+ }
+
+ virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
+ return kNonRendering_Backend == backend;
+ }
+
+ virtual ~GrOrderedSetRemoveBench() {}
+
+protected:
+ virtual const char* onGetName() SK_OVERRIDE {
+ return fName.c_str();
+ }
+
+ virtual void onPreDraw() SK_OVERRIDE {
+ SkRandom rand;
+ for (int j = 0; j < NUM_ELEMENTS; ++j) {
+ fSet.insert(rand.nextU() % NUM_ELEMENTS);
+ }
+ }
+
+ virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
+ typedef GrOrderedSet<int>::Iter SetIter;
+ for (int i = 0; i < loops; ++i) {
+ GrOrderedSet<int> testSet;
+ for (SetIter s = fSet.begin(); fSet.end() != s; ++s) {
+ testSet.insert(*s);
+ }
+ for (int j = 0; j < NUM_ELEMENTS; ++j) {
+ testSet.remove(testSet.find(j));
+ }
+ }
+ }
+
+private:
+ SkString fName;
+ GrOrderedSet<int> fSet;
+ typedef SkBenchmark INHERITED;
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+DEF_BENCH(return SkNEW_ARGS(GrOrderedSetBuildBench, ());)
+DEF_BENCH(return SkNEW_ARGS(GrOrderedSetFindBench, ());)
+DEF_BENCH(return SkNEW_ARGS(GrOrderedSetRemoveBench, ());)
+#endif
diff --git a/gyp/bench.gypi b/gyp/bench.gypi
index 2d934d8..8170d81 100644
--- a/gyp/bench.gypi
+++ b/gyp/bench.gypi
@@ -38,6 +38,7 @@
'../bench/GameBench.cpp',
'../bench/GrMemoryPoolBench.cpp',
'../bench/GrResourceCacheBench.cpp',
+ '../bench/GrOrderedSetBench.cpp',
'../bench/GradientBench.cpp',
'../bench/HairlinePathBench.cpp',
'../bench/ImageCacheBench.cpp',
diff --git a/gyp/gpu.gypi b/gyp/gpu.gypi
index a40ff66..fa861dc 100644
--- a/gyp/gpu.gypi
+++ b/gyp/gpu.gypi
@@ -82,6 +82,7 @@
'<(skia_src_path)/gpu/GrInOrderDrawBuffer.h',
'<(skia_src_path)/gpu/GrMemoryPool.cpp',
'<(skia_src_path)/gpu/GrMemoryPool.h',
+ '<(skia_src_path)/gpu/GrOrderedSet.h',
'<(skia_src_path)/gpu/GrOvalRenderer.cpp',
'<(skia_src_path)/gpu/GrOvalRenderer.h',
'<(skia_src_path)/gpu/GrPaint.cpp',
diff --git a/gyp/tests.gypi b/gyp/tests.gypi
index f5143e2..779ffde 100644
--- a/gyp/tests.gypi
+++ b/gyp/tests.gypi
@@ -88,6 +88,7 @@
'../tests/GrDrawTargetTest.cpp',
'../tests/GrMemoryPoolTest.cpp',
'../tests/GrRedBlackTreeTest.cpp',
+ '../tests/GrOrderedSetTest.cpp',
'../tests/GrSurfaceTest.cpp',
'../tests/GrTBSearchTest.cpp',
'../tests/GradientTest.cpp',
diff --git a/src/gpu/GrOrderedSet.h b/src/gpu/GrOrderedSet.h
new file mode 100644
index 0000000..995879e
--- /dev/null
+++ b/src/gpu/GrOrderedSet.h
@@ -0,0 +1,155 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef GrOrderedSet_DEFINED
+#define GrOrderedSet_DEFINED
+
+#include "GrRedBlackTree.h"
+
+template <typename T, typename C = GrLess<T> >
+class GrOrderedSet : public SkNoncopyable {
+public:
+ /**
+ * Creates an empty set
+ */
+ GrOrderedSet() : fComp() {}
+ ~GrOrderedSet() {}
+
+ class Iter;
+
+ /**
+ * @return true if there are no items in the set, false otherwise.
+ */
+ bool empty() const { return fRBTree.empty(); }
+
+ /**
+ * @return the number of items in the set.
+ */
+ int count() const { return fRBTree.count(); }
+
+ /**
+ * Removes all items in the set
+ */
+ void reset() { fRBTree.reset(); }
+
+ /**
+ * Adds an element to set if it does not already exists in the set.
+ * @param t the item to add
+ * @return an iterator to added element or matching element already in set
+ */
+ Iter insert(const T& t);
+
+ /**
+ * Removes the item indicated by an iterator. The iterator will not be valid
+ * afterwards.
+ * @param iter iterator of item to remove. Must be valid (not end()).
+ */
+ void remove(const Iter& iter);
+
+ /**
+ * @return an iterator to the first item in sorted order, or end() if empty
+ */
+ Iter begin();
+
+ /**
+ * Gets the last valid iterator. This is always valid, even on an empty.
+ * However, it can never be dereferenced. Useful as a loop terminator.
+ * @return an iterator that is just beyond the last item in sorted order.
+ */
+ Iter end();
+
+ /**
+ * @return an iterator that to the last item in sorted order, or end() if
+ * empty.
+ */
+ Iter last();
+
+ /**
+ * Finds an occurrence of an item.
+ * @param t the item to find.
+ * @return an iterator to a set element equal to t or end() if none exists.
+ */
+ Iter find(const T& t);
+
+private:
+ GrRedBlackTree<T, C> fRBTree;
+
+ const C fComp;
+};
+
+template <typename T, typename C>
+class GrOrderedSet<T,C>::Iter {
+public:
+ Iter() {}
+ Iter(const Iter& i) { fTreeIter = i.fTreeIter; }
+ Iter& operator =(const Iter& i) {
+ fTreeIter = i.fTreeIter;
+ return *this;
+ }
+ const T& operator *() const { return *fTreeIter; }
+ bool operator ==(const Iter& i) const {
+ return fTreeIter == i.fTreeIter;
+ }
+ bool operator !=(const Iter& i) const { return !(*this == i); }
+ Iter& operator ++() {
+ ++fTreeIter;
+ return *this;
+ }
+ Iter& operator --() {
+ --fTreeIter;
+ return *this;
+ }
+ const typename GrRedBlackTree<T,C>::Iter& getTreeIter() const {
+ return fTreeIter;
+ }
+
+private:
+ friend class GrOrderedSet;
+ explicit Iter(typename GrRedBlackTree<T, C>::Iter iter) {
+ fTreeIter = iter;
+ }
+ typename GrRedBlackTree<T,C>::Iter fTreeIter;
+};
+
+template <typename T, typename C>
+typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::begin() {
+ return Iter(fRBTree.begin());
+}
+
+template <typename T, typename C>
+typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::end() {
+ return Iter(fRBTree.end());
+}
+
+template <typename T, typename C>
+typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::last() {
+ return Iter(fRBTree.last());
+}
+
+template <typename T, typename C>
+typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::find(const T& t) {
+ return Iter(fRBTree.find(t));
+}
+
+template <typename T, typename C>
+typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::insert(const T& t) {
+ if (fRBTree.find(t) == fRBTree.end()) {
+ return Iter(fRBTree.insert(t));
+ } else {
+ return Iter(fRBTree.find(t));
+ }
+}
+
+template <typename T, typename C>
+void GrOrderedSet<T,C>::remove(const typename GrOrderedSet<T,C>::Iter& iter) {
+ if (this->end() != iter) {
+ fRBTree.remove(iter.getTreeIter());
+ }
+}
+
+#endif
+
diff --git a/src/gpu/GrRedBlackTree.h b/src/gpu/GrRedBlackTree.h
index db36e32..6f57754 100644
--- a/src/gpu/GrRedBlackTree.h
+++ b/src/gpu/GrRedBlackTree.h
@@ -23,6 +23,11 @@
bool operator()(const T* a, const T* b) const { return *a < *b; }
};
+class GrStrLess {
+public:
+ bool operator()(const char* a, const char* b) const { return strcmp(a,b) < 0; }
+};
+
/**
* In debug build this will cause full traversals of the tree when the validate
* is called on insert and remove. Useful for debugging but very slow.
diff --git a/tests/GrOrderedSetTest.cpp b/tests/GrOrderedSetTest.cpp
new file mode 100644
index 0000000..cb0fe85
--- /dev/null
+++ b/tests/GrOrderedSetTest.cpp
@@ -0,0 +1,150 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkRandom.h"
+#include "Test.h"
+// This is a GPU-backend specific test
+#if SK_SUPPORT_GPU
+#include "GrOrderedSet.h"
+
+typedef GrOrderedSet<int> Set;
+typedef GrOrderedSet<const char*, GrStrLess> Set2;
+
+DEF_TEST(GrOrderedSetTest, reporter) {
+ Set set;
+
+ REPORTER_ASSERT(reporter, set.empty());
+
+ SkRandom r;
+
+ int count[1000] = {0};
+ // add 10K ints
+ for (int i = 0; i < 10000; ++i) {
+ int x = r.nextU() % 1000;
+ Set::Iter xi = set.insert(x);
+ REPORTER_ASSERT(reporter, *xi == x);
+ REPORTER_ASSERT(reporter, !set.empty());
+ count[x] = 1;
+ }
+ set.insert(0);
+ count[0] = 1;
+ set.insert(999);
+ count[999] = 1;
+ int totalCount = 0;
+ for (int i = 0; i < 1000; ++i) {
+ totalCount += count[i];
+ }
+ REPORTER_ASSERT(reporter, *set.begin() == 0);
+ REPORTER_ASSERT(reporter, *set.last() == 999);
+ REPORTER_ASSERT(reporter, --(++set.begin()) == set.begin());
+ REPORTER_ASSERT(reporter, --set.end() == set.last());
+ REPORTER_ASSERT(reporter, set.count() == totalCount);
+
+ int c = 0;
+ // check that we iterate through the correct number of
+ // elements and they are properly sorted.
+ for (Set::Iter a = set.begin(); set.end() != a; ++a) {
+ Set::Iter b = a;
+ ++b;
+ ++c;
+ REPORTER_ASSERT(reporter, b == set.end() || *a <= *b);
+ }
+ REPORTER_ASSERT(reporter, c == set.count());
+
+ // check that the set finds all ints and only ints added to set
+ for (int i = 0; i < 1000; ++i) {
+ bool existsFind = set.find(i) != set.end();
+ bool existsCount = 0 != count[i];
+ REPORTER_ASSERT(reporter, existsFind == existsCount);
+ }
+ // remove all the ints between 100 and 200.
+ for (int i = 100; i < 200; ++i) {
+ set.remove(set.find(i));
+ if (1 == count[i]) {
+ count[i] = 0;
+ --totalCount;
+ }
+ REPORTER_ASSERT(reporter, set.count() == totalCount);
+ REPORTER_ASSERT(reporter, set.find(i) == set.end());
+ }
+ // remove the 0 entry. (tests removing begin())
+ REPORTER_ASSERT(reporter, *set.begin() == 0);
+ REPORTER_ASSERT(reporter, *(--set.end()) == 999);
+ set.remove(set.find(0));
+ count[0] = 0;
+ --totalCount;
+ REPORTER_ASSERT(reporter, set.count() == totalCount);
+ REPORTER_ASSERT(reporter, set.find(0) == set.end());
+ REPORTER_ASSERT(reporter, 0 < *set.begin());
+
+ // remove all the 999 entries (tests removing last()).
+ set.remove(set.find(999));
+ count[999] = 0;
+ --totalCount;
+ REPORTER_ASSERT(reporter, set.count() == totalCount);
+ REPORTER_ASSERT(reporter, set.find(999) == set.end());
+ REPORTER_ASSERT(reporter, 999 > *(--set.end()));
+ REPORTER_ASSERT(reporter, set.last() == --set.end());
+
+ // Make sure iteration still goes through correct number of entries
+ // and is still sorted correctly.
+ c = 0;
+ for (Set::Iter a = set.begin(); set.end() != a; ++a) {
+ Set::Iter b = a;
+ ++b;
+ ++c;
+ REPORTER_ASSERT(reporter, b == set.end() || *a <= *b);
+ }
+ REPORTER_ASSERT(reporter, c == set.count());
+
+ // repeat check that the set finds all ints and only ints added to set
+ for (int i = 0; i < 1000; ++i) {
+ bool existsFind = set.find(i) != set.end();
+ bool existsCount = 0 != count[i];
+ REPORTER_ASSERT(reporter, existsFind == existsCount);
+ }
+
+ // remove all entries
+ while (!set.empty()) {
+ set.remove(set.begin());
+ }
+
+ // test reset on empty set.
+ set.reset();
+ REPORTER_ASSERT(reporter, set.empty());
+
+
+ // test using c strings
+ const char* char1 = "dog";
+ const char* char2 = "cat";
+ const char* char3 = "dog";
+
+ Set2 set2;
+
+ set2.insert("ape");
+ set2.insert(char1);
+ set2.insert(char2);
+ set2.insert(char3);
+ set2.insert("ant");
+ set2.insert("cat");
+
+ REPORTER_ASSERT(reporter, set2.count() == 4);
+ REPORTER_ASSERT(reporter, set2.find("dog") == set2.last());
+ REPORTER_ASSERT(reporter, set2.find("cat") != set2.end());
+ REPORTER_ASSERT(reporter, set2.find("ant") == set2.begin());
+ REPORTER_ASSERT(reporter, set2.find("bug") == set2.end());
+
+ set2.remove(set2.find("ant"));
+ REPORTER_ASSERT(reporter, set2.find("ant") == set2.end());
+ REPORTER_ASSERT(reporter, set2.count() == 3);
+
+ set2.reset();
+ REPORTER_ASSERT(reporter, set2.empty());
+}
+
+#endif
+