Add SkTTopoSort
BUG=skia:4094
Review URL: https://codereview.chromium.org/1414503003
diff --git a/bench/TopoSortBench.cpp b/bench/TopoSortBench.cpp
new file mode 100644
index 0000000..3fa1c0f
--- /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(); )
+
diff --git a/gyp/core.gypi b/gyp/core.gypi
index 089a8c0..c71ea31 100644
--- a/gyp/core.gypi
+++ b/gyp/core.gypi
@@ -275,6 +275,7 @@
'<(skia_src_path)/core/SkTraceEventCommon.h',
'<(skia_src_path)/core/SkTSearch.cpp',
'<(skia_src_path)/core/SkTSort.h',
+ '<(skia_src_path)/core/SkTTopoSort.h',
'<(skia_src_path)/core/SkTypeface.cpp',
'<(skia_src_path)/core/SkTypefaceCache.cpp',
'<(skia_src_path)/core/SkTypefaceCache.h',
diff --git a/src/core/SkTTopoSort.h b/src/core/SkTTopoSort.h
new file mode 100644
index 0000000..35b85ee
--- /dev/null
+++ b/src/core/SkTTopoSort.h
@@ -0,0 +1,112 @@
+/*
+ * Copyright 2015 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkTTopoSort_DEFINED
+#define SkTTopoSort_DEFINED
+
+#include "SkTDArray.h"
+
+#ifdef SK_DEBUG
+template <typename T, typename Traits = T>
+void SkTTopoSort_CheckAllUnmarked(const SkTDArray<T*>& graph) {
+ for (int i = 0; i < graph.count(); ++i) {
+ SkASSERT(!Traits::IsTempMarked(graph[i]));
+ SkASSERT(!Traits::WasOutput(graph[i]));
+ }
+}
+
+template <typename T, typename Traits = T>
+void SkTTopoSort_CleanExit(const SkTDArray<T*>& graph) {
+ for (int i = 0; i < graph.count(); ++i) {
+ SkASSERT(!Traits::IsTempMarked(graph[i]));
+ SkASSERT(Traits::WasOutput(graph[i]));
+ }
+}
+#endif
+
+// Recursively visit a node and all the other nodes it depends on.
+// Return false if there is a loop.
+template <typename T, typename Traits = T>
+bool SkTTopoSort_Visit(T* node, SkTDArray<T*>* result) {
+ if (Traits::IsTempMarked(node)) {
+ // There is a loop.
+ return false;
+ }
+
+ // If the node under consideration has been already been output it means it
+ // (and all the nodes it depends on) are already in 'result'.
+ if (!Traits::WasOutput(node)) {
+ // This node hasn't been output yet. Recursively assess all the
+ // nodes it depends on outputing them first.
+ Traits::SetTempMark(node);
+ for (int i = 0; i < Traits::NumDependencies(node); ++i) {
+ if (!SkTTopoSort_Visit<T, Traits>(Traits::Dependency(node, i), result)) {
+ return false;
+ }
+ }
+ Traits::Output(node, result->count()); // mark this node as output
+ Traits::ResetTempMark(node);
+
+ *result->append() = node;
+ }
+
+ return true;
+}
+
+// Topologically sort the nodes in 'graph'. For this sort, when node 'i' depends
+// on node 'j' it means node 'j' must appear in the result before node 'i'.
+// A false return value means there was a loop and the contents of 'graph' will
+// be in some arbitrary state.
+//
+// Traits requires:
+// static void Output(T* t, int index) { ... } // 'index' is 't's position in the result
+// static bool WasOutput(const T* t) { ... }
+//
+// static void SetTempMark(T* t) { ... } // transiently used during toposort
+// static void ResetTempMark(T* t) { ... }
+// static bool IsTempMarked(const T* t) { ... }
+//
+// static int NumDependencies(const T* t) { ... } // 't' will be output after all the other -
+// static T* Dependency(T* t, int index) { ... } // nodes on which it depends
+// We'll look on T for these by default, or you can pass a custom Traits type.
+//
+// TODO: potentially add a version that takes a seed node and just outputs that
+// node and all the nodes on which it depends. This could be used to partially
+// flush a drawTarget DAG.
+template <typename T, typename Traits = T>
+bool SkTTopoSort(SkTDArray<T*>* graph) {
+ SkTDArray<T*> result;
+
+#ifdef SK_DEBUG
+ SkTTopoSort_CheckAllUnmarked<T, Traits>(*graph);
+#endif
+
+ result.setReserve(graph->count());
+
+ for (int i = 0; i < graph->count(); ++i) {
+ if (Traits::WasOutput((*graph)[i])) {
+ // This node was depended on by some earlier node and has already
+ // been output
+ continue;
+ }
+
+ // Output this node after all the nodes it depends on have been output.
+ if (!SkTTopoSort_Visit<T, Traits>((*graph)[i], &result)) {
+ return false;
+ }
+ }
+
+ SkASSERT(graph->count() == result.count());
+ graph->swap(result);
+
+#ifdef SK_DEBUG
+ SkTTopoSort_CleanExit<T, Traits>(*graph);
+#endif
+ return true;
+}
+
+#endif
diff --git a/tests/TopoSortTest.cpp b/tests/TopoSortTest.cpp
new file mode 100644
index 0000000..358cd8d
--- /dev/null
+++ b/tests/TopoSortTest.cpp
@@ -0,0 +1,142 @@
+/*
+ * 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 "SkRandom.h"
+#include "SkTTopoSort.h"
+#include "Test.h"
+
+#include "sk_tool_utils.h"
+
+typedef void (*CreateGraphPF)(SkTDArray<sk_tool_utils::TopoTestNode*>* graph);
+
+/* Simple diamond
+ * 3
+ * / \
+ * 1 2
+ * \ /
+ * 0
+ */
+static void create_graph0(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
+ sk_tool_utils::TopoTestNode::AllocNodes(graph, 4);
+
+ (*graph)[0]->dependsOn((*graph)[1]);
+ (*graph)[0]->dependsOn((*graph)[2]);
+ (*graph)[1]->dependsOn((*graph)[3]);
+ (*graph)[2]->dependsOn((*graph)[3]);
+}
+
+/* Simple chain
+ * 3
+ * |
+ * 2
+ * |
+ * 1
+ * |
+ * 0
+ */
+static void create_graph1(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
+ sk_tool_utils::TopoTestNode::AllocNodes(graph, 4);
+
+ (*graph)[0]->dependsOn((*graph)[1]);
+ (*graph)[1]->dependsOn((*graph)[2]);
+ (*graph)[2]->dependsOn((*graph)[3]);
+}
+
+/* Loop
+ * 2
+ * / \
+ * 0 --- 1
+ */
+static void create_graph2(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
+ sk_tool_utils::TopoTestNode::AllocNodes(graph, 3);
+
+ (*graph)[0]->dependsOn((*graph)[1]);
+ (*graph)[1]->dependsOn((*graph)[2]);
+ (*graph)[2]->dependsOn((*graph)[0]);
+}
+
+/* Double diamond
+ * 6
+ * / \
+ * 4 5
+ * \ /
+ * 3
+ * / \
+ * 1 2
+ * \ /
+ * 0
+ */
+static void create_graph3(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
+ sk_tool_utils::TopoTestNode::AllocNodes(graph, 7);
+
+ (*graph)[0]->dependsOn((*graph)[1]);
+ (*graph)[0]->dependsOn((*graph)[2]);
+ (*graph)[1]->dependsOn((*graph)[3]);
+ (*graph)[2]->dependsOn((*graph)[3]);
+
+ (*graph)[3]->dependsOn((*graph)[4]);
+ (*graph)[3]->dependsOn((*graph)[5]);
+ (*graph)[4]->dependsOn((*graph)[6]);
+ (*graph)[5]->dependsOn((*graph)[6]);
+}
+
+/* Two independent diamonds
+ * 3 7
+ * / \ / \
+ * 1 2 5 6
+ * \ / \ /
+ * 0 4
+ */
+static void create_graph4(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
+ sk_tool_utils::TopoTestNode::AllocNodes(graph, 8);
+
+ (*graph)[0]->dependsOn((*graph)[1]);
+ (*graph)[0]->dependsOn((*graph)[2]);
+ (*graph)[1]->dependsOn((*graph)[3]);
+ (*graph)[2]->dependsOn((*graph)[3]);
+
+ (*graph)[4]->dependsOn((*graph)[5]);
+ (*graph)[4]->dependsOn((*graph)[6]);
+ (*graph)[5]->dependsOn((*graph)[7]);
+ (*graph)[6]->dependsOn((*graph)[7]);
+}
+
+DEF_TEST(TopoSort, reporter) {
+ SkRandom rand;
+
+ struct {
+ CreateGraphPF fCreate;
+ bool fExpectedResult;
+ } tests[] = {
+ { create_graph0, true },
+ { create_graph1, true },
+ { create_graph2, false },
+ { create_graph3, true },
+ { create_graph4, true },
+ };
+
+ for (size_t i = 0; i < SK_ARRAY_COUNT(tests); ++i) {
+ SkTDArray<sk_tool_utils::TopoTestNode*> graph;
+
+ (tests[i].fCreate)(&graph);
+
+ sk_tool_utils::TopoTestNode::Shuffle(&graph, &rand);
+
+ bool actualResult = SkTTopoSort<sk_tool_utils::TopoTestNode>(&graph);
+ REPORTER_ASSERT(reporter, actualResult == tests[i].fExpectedResult);
+
+ if (tests[i].fExpectedResult) {
+ for (int j = 0; j < graph.count(); ++j) {
+ REPORTER_ASSERT(reporter, graph[j]->check());
+ }
+ }
+
+ //SkDEBUGCODE(print(graph);)
+ sk_tool_utils::TopoTestNode::DeallocNodes(&graph);
+ }
+}
+
diff --git a/tools/sk_tool_utils.h b/tools/sk_tool_utils.h
index 052bade..67fd869 100644
--- a/tools/sk_tool_utils.h
+++ b/tools/sk_tool_utils.h
@@ -12,6 +12,8 @@
#include "SkImageEncoder.h"
#include "SkImageInfo.h"
#include "SkPixelSerializer.h"
+#include "SkRandom.h"
+#include "SkTDArray.h"
#include "SkTypeface.h"
class SkBitmap;
@@ -140,6 +142,96 @@
// so it is slow!
SkBitmap slow_blur(const SkBitmap& src, float sigma);
+ // A helper object to test the topological sorting code (TopoSortBench.cpp & TopoSortTest.cpp)
+ 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
+ bool check() {
+ if (-1 == fOutputPos) {
+ return false;
+ }
+
+ for (int i = 0; i < fDependencies.count(); ++i) {
+ if (-1 == fDependencies[i]->outputPos()) {
+ return false;
+ }
+ // This node should've been output after all the nodes on which it depends
+ if (fOutputPos < fDependencies[i]->outputPos()) {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ // 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];
+ }
+
+ // Helper functions for TopoSortBench & TopoSortTest
+ static void AllocNodes(SkTDArray<TopoTestNode*>* graph, int num) {
+ graph->setReserve(num);
+
+ for (int i = 0; i < num; ++i) {
+ *graph->append() = new TopoTestNode(i);
+ }
+ }
+
+ static void DeallocNodes(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;
+ }
+ }
+
+ private:
+ int fID;
+ int fOutputPos;
+ bool fTempMark;
+
+ SkTDArray<TopoTestNode*> fDependencies;
+ };
+
} // namespace sk_tool_utils
#endif // sk_tool_utils_DEFINED