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

1 files changed, 148 insertions, 0 deletions

diff --git a/bench/GrOrderedSetBench.cpp b/bench/GrOrderedSetBench.cpp
new file mode 100644
index 0000000000..4d32f0dc04
--- /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