Add SkTTopoSort

BUG=skia:4094

Review URL: https://codereview.chromium.org/1414503003

1 files changed, 112 insertions, 0 deletions

diff --git a/src/core/SkTTopoSort.h b/src/core/SkTTopoSort.h
new file mode 100644
index 0000000000..35b85eeb81
--- /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