Add SkTTopoSort

bench/TopoSortBench.cpp

Index: bench/TopoSortBench.cpp
diff --git a/bench/TopoSortBench.cpp b/bench/TopoSortBench.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..505115c580ca3f538bc2ad6118be6f8aee89a006
--- /dev/null
+++ b/bench/TopoSortBench.cpp
@@ -0,0 +1,165 @@
+/*
+ * Copyright 2015 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "Benchmark.h"
+#include "SkRandom.h"
+#include "SkString.h"
+#include "SkTTopoSort.h"
+
+///////////////////////////////////////////////////////////////////////////////
+// Shared with TopoSortTest.cpp
+///////////////////////////////////////////////////////////////////////////////
+
+// A helper object to test the topological sorting code
+class TopoTestNode {
+public:
+    TopoTestNode(int id) : fID(id), fOutputPos(-1), fTempMark(false) { }
+
+    void dependsOn(TopoTestNode* src) {
+        *fDependencies.append() = src;
+    }
+
+    int id() const { return fID; }
+    void reset() { fOutputPos = -1; }
+
+    int outputPos() const { return fOutputPos; }
+
+    // check that the topological sort is valid for this node
+    void check() {
+        SkASSERT(-1 != fOutputPos);
+
+        for (int i = 0; i < fDependencies.count(); ++i) {
+            SkASSERT(-1 != fDependencies[i]->outputPos());
+            // This node should've been output after all the nodes on which it depends
+            SkASSERT(fOutputPos > fDependencies[i]->outputPos());
+        }
+    }
+
+    // The following 7 methods are needed by the topological sort
+    static void SetTempMark(TopoTestNode* node) { node->fTempMark = true; }
+    static void ResetTempMark(TopoTestNode* node) { node->fTempMark = false; }
+    static bool IsTempMarked(TopoTestNode* node) { return node->fTempMark; }
+    static void Output(TopoTestNode* node, int outputPos) { 
+        SkASSERT(-1 != outputPos);
+        node->fOutputPos = outputPos; 
+    }
+    static bool WasOutput(TopoTestNode* node) { return (-1 != node->fOutputPos); }
+    static int NumDependencies(TopoTestNode* node) { return node->fDependencies.count(); }
+    static TopoTestNode* Dependency(TopoTestNode* node, int index) { 
+        return node->fDependencies[index];
+    }
+
+private:
+    int  fID;
+    int  fOutputPos;
+    bool fTempMark;
+
+    SkTDArray<TopoTestNode*> fDependencies;
+};
+
+static void alloc_nodes(SkTDArray<TopoTestNode*>* graph, int num) {
+    graph->setReserve(num);
+
+    for (int i = 0; i < num; ++i) {
+        *graph->append() = new TopoTestNode(i);
+    }
+}
+
+static void dealloc_nodes(SkTDArray<TopoTestNode*>* graph) {
+    for (int i = 0; i < graph->count(); ++i) {
+        delete (*graph)[i];
+    }
+}
+
+#ifdef SK_DEBUG
+static void print(const SkTDArray<TopoTestNode*>& graph) {
+    for (int i = 0; i < graph.count(); ++i) {
+        SkDebugf("%d, ", graph[i]->id());
+    }
+    SkDebugf("\n");
+}
+#endif
+
+// randomize the array
+static void shuffle(SkTDArray<TopoTestNode*>* graph, SkRandom* rand) {
+    for (int i = graph->count()-1; i > 0; --i) {
+        int swap = rand->nextU() % (i+1);
+
+        TopoTestNode* tmp = (*graph)[i];
+        (*graph)[i] = (*graph)[swap];
+        (*graph)[swap] = tmp;
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////////
+///////////////////////////////////////////////////////////////////////////////
+
+class TopoSortBench : public Benchmark {
+public:
+    TopoSortBench() { }
+
+    ~TopoSortBench() override {
+        dealloc_nodes(&fGraph);
+    }
+
+    bool isSuitableFor(Backend backend) override {
+        return kNonRendering_Backend == backend;
+    }
+
+protected:
+    const char* onGetName() override {
+        return "sort_topo_rand";
+    }
+
+    // Delayed initialization only done if onDraw will be called.
+    void onDelayedSetup() override {
+        alloc_nodes(&fGraph, kNumElements);
+
+        for (int i = kNumElements-1; i > 0; --i) {
+            int numEdges = fRand.nextU() % (kMaxEdges+1);
+
+            for (int j = 0; j < numEdges; ++j) {
+                int dep = fRand.nextU() % i;
+
+                fGraph[i]->dependsOn(fGraph[dep]);
+            }
+        }
+    }
+
+    void onDraw(int loops, SkCanvas*) override {
+        for (int i = 0; i < loops; ++i) {
+            for (int j = 0; j < fGraph.count(); ++j) {
+                fGraph[j]->reset();
+            }
+
+            shuffle(&fGraph, &fRand);
+
+            SkDEBUGCODE(bool actualResult =) SkTTopoSort<TopoTestNode>(&fGraph);
+            SkASSERT(actualResult);
+
+#ifdef SK_DEBUG
+            for (int j = 0; j < fGraph.count(); ++j) {
+                fGraph[j]->check();
+            }
+#endif
+        }
+    }
+
+private:
+    static const int kNumElements = 1000;
+    static const int kMaxEdges = 5;
+
+    SkTDArray<TopoTestNode*> fGraph;
+    SkRandom fRand;
+
+    typedef Benchmark INHERITED;
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+DEF_BENCH( return new TopoSortBench(); )
+