From 423f6461e98ba28730d05e5894804a4970a09bde Mon Sep 17 00:00:00 2001
From: robertphillips <robertphillips@google.com>
Date: Mon, 19 Oct 2015 12:15:55 -0700
Subject: Add SkTTopoSort

BUG=skia:4094

Review URL: https://codereview.chromium.org/1414503003
---
 bench/TopoSortBench.cpp | 79 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 79 insertions(+)
 create mode 100644 bench/TopoSortBench.cpp

(limited to 'bench/TopoSortBench.cpp')

diff --git a/bench/TopoSortBench.cpp b/bench/TopoSortBench.cpp
new file mode 100644
index 0000000000..3fa1c0ff97
--- /dev/null
+++ b/bench/TopoSortBench.cpp
@@ -0,0 +1,79 @@
+/*
+ * 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"
+
+#include "sk_tool_utils.h"
+
+class TopoSortBench : public Benchmark {
+public:
+    TopoSortBench() { }
+
+    ~TopoSortBench() override {
+        sk_tool_utils::TopoTestNode::DeallocNodes(&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 {
+        sk_tool_utils::TopoTestNode::AllocNodes(&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();
+            }
+
+            sk_tool_utils::TopoTestNode::Shuffle(&fGraph, &fRand);
+
+            SkDEBUGCODE(bool actualResult =) SkTTopoSort<sk_tool_utils::TopoTestNode>(&fGraph);
+            SkASSERT(actualResult);
+
+#ifdef SK_DEBUG
+            for (int j = 0; j < fGraph.count(); ++j) {
+                SkASSERT(fGraph[j]->check());
+            }
+#endif
+        }
+    }
+
+private:
+    static const int kNumElements = 1000;
+    static const int kMaxEdges = 5;
+
+    SkTDArray<sk_tool_utils::TopoTestNode*> fGraph;
+    SkRandom fRand;
+
+    typedef Benchmark INHERITED;
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+DEF_BENCH( return new TopoSortBench(); )
+
-- 
cgit v1.2.3