Add GrSet class built on top of RedBlackTree

bench/GrSetBench.cpp

Index: bench/GrSetBench.cpp
diff --git a/bench/GrSetBench.cpp b/bench/GrSetBench.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..42addc55fd1fcd9be93c850ded234bd8e2c85a3e
--- /dev/null
+++ b/bench/GrSetBench.cpp
@@ -0,0 +1,146 @@
+/*
+ * 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"
+#include "GrSet.h"
+
+static const int NUM_ELEMENTS = 1000;
+
+// Time how long it takes to build a set
+class GrSetBuildBench : public SkBenchmark {
+public:
+    GrSetBuildBench() {
+        fName.append("grSet_build");

[bsalomon, 2014/02/26 21:56:09]

For the names maybe we should use "set_<foo>" rather than "grSet". If this
graduates to sk then we'd either have to have an anachronistic name or cause a
discontinuity in the bench history.

Also, maybe set_build_and_destroy for this one? It wouldn't shock if free() from
the ~ was really significant.

+    }
+
+    virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
+        return kNonRendering_Backend == backend;
+    }
+
+    virtual ~GrSetBuildBench() {}
+
+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) {
+            GrSet<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 GrSetFindBench : public SkBenchmark {
+public:
+    GrSetFindBench() {
+        fName.append("grSet_find");
+    }
+
+    virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
+        return kNonRendering_Backend == backend;
+    }
+
+    virtual ~GrSetFindBench() {}
+
+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];
+    GrSet<int> fSet;
+    typedef SkBenchmark INHERITED;
+};
+
+// Time how long it takes to iterate over and remove all elements from set
+class GrSetRemoveBench : public SkBenchmark {
+public:
+    GrSetRemoveBench() {
+        fName.append("grSet_remove");
+    }
+
+    virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
+        return kNonRendering_Backend == backend;
+    }
+
+    virtual ~GrSetRemoveBench() {}
+
+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 GrSet<int>::Iter SetIter;
+        for (int i = 0; i < loops; ++i) {
+            GrSet<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;
+    GrSet<int> fSet;
+    typedef SkBenchmark INHERITED;
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+DEF_BENCH(return SkNEW_ARGS(GrSetBuildBench, ());)
+DEF_BENCH(return SkNEW_ARGS(GrSetFindBench, ());)
+DEF_BENCH(return SkNEW_ARGS(GrSetRemoveBench, ());)